izzy/UnrealEngineUWP
0
0
Fork 0
mirror of https://github.com/izzy2lost/UnrealEngineUWP.git synced 2026-03-26 18:15:20 -07:00
Code Issues Packages Projects Releases Wiki Activity
Files
5.3
UnrealEngineUWP/Engine/Plugins/Runtime/GeometryProcessing/Source/DynamicMesh/Private/Operations/MeshBevel.cpp
avudnez 2d99473b92 PR #10645: Fix extra parentheses compilation warning with clang-cl 
#jira UE-190329
#rb matija.kecman

[CL 26544922 by avudnez in 5.3 branch]
2023-07-24 11:55:36 -04:00

1743 lines
54 KiB
C++
Raw Permalink Blame History

// Copyright Epic Games, Inc. All Rights Reserved.
#include "Operations/MeshBevel.h"
#include "GroupTopology.h"
#include "EdgeLoop.h"
#include "DynamicMesh/DynamicMeshChangeTracker.h"
#include "MeshWeights.h"
#include "CompGeom/PolygonTriangulation.h"
#include "DynamicMesh/MeshNormals.h"
#include "DynamicMesh/MeshIndexUtil.h"
#include "MeshRegionBoundaryLoops.h"
#include "Operations/PolyEditingEdgeUtil.h"
#include "Operations/PolyEditingUVUtil.h"
#include "Algo/Count.h"
#include "Distance/DistLine3Line3.h"
using namespace UE::Geometry;
// Uncomment to enable various checks and ensures in the Bevel code.
// We cannot default-enable these checks even in Debug builds, because
// Bevel still frequently hits some of these cases, and those checks/ensures
// make it very difficult to debug a game using Bevel in Geometry Script (eg Lyra sample)
//#define ENABLE_MESH_BEVEL_DEBUG
#ifdef ENABLE_MESH_BEVEL_DEBUG
#define MESH_BEVEL_DEBUG_CHECK(Expr) checkSlow(Expr)
#define MESH_BEVEL_DEBUG_ENSURE(Expr) ensure(Expr)
#else
#define MESH_BEVEL_DEBUG_CHECK(Expr)
#define MESH_BEVEL_DEBUG_ENSURE(Expr) !!(Expr)
#endif
namespace UELocal
{
static void QuadsToTris(const FDynamicMesh3& Mesh, const TArray<FIndex2i>& Quads, TArray<int32>& TrisOut, bool bReset)
{
int32 N = Quads.Num();
if (bReset)
{
TrisOut.Reset();
TrisOut.Reserve(2 * N);
}
for (const FIndex2i& Quad : Quads)
{
if (Mesh.IsTriangle(Quad.A))
{
TrisOut.Add(Quad.A);
}
if (Mesh.IsTriangle(Quad.B))
{
TrisOut.Add(Quad.B);
}
}
};
}
void FMeshBevel::InitializeFromGroupTopology(const FDynamicMesh3& Mesh, const FGroupTopology& Topology)
{
ResultInfo = FGeometryResult(EGeometryResultType::InProgress);
// set up initial problem inputs
for (int32 TopoEdgeID = 0; TopoEdgeID < Topology.Edges.Num(); ++TopoEdgeID)
{
if (Topology.IsIsolatedLoop(TopoEdgeID))
{
FEdgeLoop NewLoop;
NewLoop.InitializeFromEdges(&Mesh, Topology.Edges[TopoEdgeID].Span.Edges);
AddBevelEdgeLoop(Mesh, NewLoop);
}
else
{
AddBevelGroupEdge(Mesh, Topology, TopoEdgeID);
}
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return;
}
}
// precompute topological information necessary to apply bevel to vertices/edges/loops
BuildVertexSets(Mesh);
}
void FMeshBevel::InitializeFromGroupTopologyEdges(const FDynamicMesh3& Mesh, const FGroupTopology& Topology, const TArray<int32>& GroupEdges)
{
ResultInfo = FGeometryResult(EGeometryResultType::InProgress);
// set up initial problem inputs
for (int32 TopoEdgeID : GroupEdges)
{
if (Topology.IsIsolatedLoop(TopoEdgeID))
{
FEdgeLoop NewLoop;
NewLoop.InitializeFromEdges(&Mesh, Topology.Edges[TopoEdgeID].Span.Edges);
AddBevelEdgeLoop(Mesh, NewLoop);
}
else
{
AddBevelGroupEdge(Mesh, Topology, TopoEdgeID);
}
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return;
}
}
// precompute topological information necessary to apply bevel to vertices/edges/loops
BuildVertexSets(Mesh);
}
bool FMeshBevel::InitializeFromGroupTopologyFaces(const FDynamicMesh3& Mesh, const FGroupTopology& Topology, const TArray<int32>& GroupFaces)
{
FGroupTopologySelection Selection;
Selection.SelectedGroupIDs.Append(GroupFaces);
TArray<int32> Triangles;
Topology.GetSelectedTriangles(Selection, Triangles);
return InitializeFromTriangleSet(Mesh, Triangles);
}
bool FMeshBevel::InitializeFromTriangleSet(const FDynamicMesh3& Mesh, const TArray<int32>& Triangles)
{
ResultInfo = FGeometryResult(EGeometryResultType::InProgress);
FMeshRegionBoundaryLoops RegionLoops(&Mesh, Triangles, true);
if (RegionLoops.bFailed)
{
ResultInfo.SetFailed();
return false;
}
// cannot bevel a selection-bowtie vertex, so we have to check for those and fail here
TSet<int32> AllVertices;
for (const FEdgeLoop& Loop : RegionLoops.Loops)
{
for (int32 vid : Loop.Vertices)
{
if (AllVertices.Contains(vid))
{
return false;
}
AllVertices.Add(vid);
}
}
for (const FEdgeLoop& Loop : RegionLoops.Loops)
{
AddBevelEdgeLoop(Mesh, Loop);
}
// precompute topological information necessary to apply bevel to vertices/edges/loops
BuildVertexSets(Mesh);
return true;
}
bool FMeshBevel::Apply(FDynamicMesh3& Mesh, FDynamicMeshChangeTracker* ChangeTracker)
{
// disconnect along bevel graph edges/vertices and save necessary info
UnlinkEdges(Mesh, ChangeTracker);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
UnlinkLoops(Mesh, ChangeTracker);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
UnlinkVertices(Mesh, ChangeTracker);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
FixUpUnlinkedBevelEdges(Mesh);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
// update vertex positions
DisplaceVertices(Mesh, InsetDistance);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
// mesh the bevel corners and edges
CreateBevelMeshing(Mesh);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
// build output list of triangles so it can be re-used in operations below if useful
NewTriangles.Reset();
for (FBevelVertex& Vertex : Vertices)
{
NewTriangles.Append(Vertex.NewTriangles);
}
for (FBevelEdge& Edge : Edges)
{
UELocal::QuadsToTris(Mesh, Edge.StripQuads, NewTriangles, false);
}
for (FBevelLoop& Loop : Loops)
{
UELocal::QuadsToTris(Mesh, Loop.StripQuads, NewTriangles, false);
}
// compute normals
ComputeNormals(Mesh);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
// compute UVs
ComputeUVs(Mesh);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
ComputeMaterialIDs(Mesh);
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return false;
}
// todo: compute other attribs
ResultInfo.SetSuccess(true, Progress);
return true;
}
FMeshBevel::FBevelVertex* FMeshBevel::GetBevelVertexFromVertexID(int32 VertexID)
{
int32* FoundIndex = VertexIDToIndexMap.Find(VertexID);
if (FoundIndex == nullptr)
{
return nullptr;
}
return &Vertices[*FoundIndex];
}
void FMeshBevel::AddBevelGroupEdge(const FDynamicMesh3& Mesh, const FGroupTopology& Topology, int32 GroupEdgeID)
{
const TArray<int32>& MeshEdgeList = Topology.Edges[GroupEdgeID].Span.Edges;
// currently cannot handle boundary edges
if ( Algo::CountIf(MeshEdgeList, [&Mesh](int EdgeID) { return Mesh.IsBoundaryEdge(EdgeID); }) > 0 )
{
return;
}
FIndex2i EdgeCornerIDs = Topology.Edges[GroupEdgeID].EndpointCorners;
FBevelEdge Edge;
for (int32 ci = 0; ci < 2; ++ci)
{
int32 CornerID = EdgeCornerIDs[ci];
FGroupTopology::FCorner Corner = Topology.Corners[CornerID];
int32 VertexID = Corner.VertexID;
Edge.bEndpointBoundaryFlag[ci] = Mesh.IsBoundaryVertex(VertexID);
int32 IncomingEdgeID = (ci == 0) ? MeshEdgeList[0] : MeshEdgeList.Last();
FBevelVertex* VertInfo = GetBevelVertexFromVertexID(VertexID);
if (VertInfo == nullptr)
{
FBevelVertex NewVertex;
NewVertex.CornerID = CornerID;
NewVertex.VertexID = VertexID;
int32 NewIndex = Vertices.Num();
Vertices.Add(NewVertex);
VertexIDToIndexMap.Add(VertexID, NewIndex);
VertInfo = &Vertices[NewIndex];
}
VertInfo->IncomingBevelMeshEdges.Add(IncomingEdgeID);
VertInfo->IncomingBevelTopoEdges.Add(GroupEdgeID);
}
Edge.MeshEdges.Append(MeshEdgeList);
Edge.MeshVertices.Append(Topology.Edges[GroupEdgeID].Span.Vertices);
Edge.GroupEdgeID = GroupEdgeID;
Edge.GroupIDs = Topology.Edges[GroupEdgeID].Groups;
Edge.MeshEdgeTris.Reserve(Edge.MeshEdges.Num());
for (int32 eid : Edge.MeshEdges)
{
Edge.MeshEdgeTris.Add(Mesh.GetEdgeT(eid));
}
Edges.Add(MoveTemp(Edge));
}
void FMeshBevel::AddBevelEdgeLoop(const FDynamicMesh3& Mesh, const FEdgeLoop& MeshEdgeLoop)
{
// currently cannot handle boundary edges
if ( Algo::CountIf(MeshEdgeLoop.Edges, [&Mesh](int EdgeID) { return Mesh.IsBoundaryEdge(EdgeID); }) > 0 )
{
return;
}
FBevelLoop Loop;
Loop.MeshEdges = MeshEdgeLoop.Edges;
Loop.MeshVertices = MeshEdgeLoop.Vertices;
Loop.MeshEdgeTris.Reserve(Loop.MeshEdges.Num());
for (int32 eid : Loop.MeshEdges)
{
Loop.MeshEdgeTris.Add(Mesh.GetEdgeT(eid));
}
Loops.Add(Loop);
}
void FMeshBevel::BuildVertexSets(const FDynamicMesh3& Mesh)
{
// can be parallel
for (FBevelVertex& Vertex : Vertices)
{
// get sorted list of triangles around the vertex
TArray<int> GroupLengths;
TArray<bool> bGroupIsLoop;
EMeshResult Result = Mesh.GetVtxContiguousTriangles(Vertex.VertexID, Vertex.SortedTriangles, GroupLengths, bGroupIsLoop);
if ( Result != EMeshResult::Ok || GroupLengths.Num() != 1 || Vertex.SortedTriangles.Num() < 2)
{
Vertex.VertexType = EBevelVertexType::Unknown;
continue;
}
// GetVtxContiguousTriangles does not return triangles sorted in a consistent direction. This check will
// reverse the ordering such that it is consistently walking counter-clockwise around the vertex (I think...)
FIndex3i Tri0 = Mesh.GetTriangle(Vertex.SortedTriangles[0]).GetCycled(Vertex.VertexID);
FIndex3i Tri1 = Mesh.GetTriangle(Vertex.SortedTriangles[1]).GetCycled(Vertex.VertexID);
if (Tri0.C == Tri1.B)
{
Algo::Reverse(Vertex.SortedTriangles);
}
if (Mesh.IsBoundaryVertex(Vertex.VertexID))
{
Vertex.VertexType = EBevelVertexType::BoundaryVertex;
continue;
}
MESH_BEVEL_DEBUG_CHECK(Vertex.IncomingBevelMeshEdges.Num() != 0); // shouldn't ever happen
if (Vertex.IncomingBevelMeshEdges.Num() == 1)
{
BuildTerminatorVertex(Vertex, Mesh);
}
else
{
BuildJunctionVertex(Vertex, Mesh);
}
if (ResultInfo.CheckAndSetCancelled(Progress))
{
return;
}
}
// At a 'Terminator' vertex we are going to split the one-ring and fill the bevel-side with a quad, which
// will usually leave a single-triangle hole. However if two Terminator vertices are directly connected
// via a non-bevel mesh edge, the two triangles will be connected, ie the hole is quad-shaped. It's easier
// to detect this case here /before/ we split the mesh up into disconnected parts...
for (FBevelVertex& Vertex : Vertices)
{
if (Vertex.VertexType == EBevelVertexType::TerminatorVertex)
{
int32 OtherVertexID = Vertex.TerminatorInfo.B;
int32* OtherBevelVtxIdx = VertexIDToIndexMap.Find(OtherVertexID);
if (OtherBevelVtxIdx != nullptr)
{
// does other vertex have to be a terminator? or can this also happen w/ a junction?
FBevelVertex& OtherVertex = Vertices[*OtherBevelVtxIdx];
if (OtherVertex.VertexType == EBevelVertexType::TerminatorVertex)
{
// want to skip this if the ring-split edge is already a bevel edge
int32 MeshEdgeID = Mesh.FindEdge(Vertex.VertexID, OtherVertex.VertexID);
MESH_BEVEL_DEBUG_CHECK(MeshEdgeID >= 0);
if (Mesh.IsEdge(MeshEdgeID) &&
Vertex.TerminatorInfo.A == MeshEdgeID &&
OtherVertex.TerminatorInfo.A == MeshEdgeID && // do we need the other vertex to use the same edge here? (is this actually a hard constraint on that edge that we should be enforcing??)
Vertex.IncomingBevelMeshEdges.Contains(MeshEdgeID) == false )
{
Vertex.ConnectedBevelVertex = *OtherBevelVtxIdx;
}
}
}
}
}
}
void FMeshBevel::BuildJunctionVertex(FBevelVertex& Vertex, const FDynamicMesh3& Mesh)
{
//
// Now split up the single contiguous one-ring into "Wedges" created by the incoming split-edges
//
// find first split edge, and the triangle/index "after" that first split edge
int32 NT = Vertex.SortedTriangles.Num();
int32 StartTriIndex = -1;
for (int32 k = 0; k < NT; ++k)
{
if (FindSharedEdgeInTriangles(Mesh, Vertex.SortedTriangles[k], Vertex.SortedTriangles[(k + 1) % NT]) == Vertex.IncomingBevelMeshEdges[0])
{
StartTriIndex = (k + 1) % NT; // start at second tri, so that bevel-edge is first edge in wedge
break;
}
}
if (StartTriIndex == -1)
{
Vertex.VertexType = EBevelVertexType::Unknown;
return;
}
// now walk around the one-ring tris, accumulating into current Wedge until we hit another split-edge,
// at which point a new Wedge is spawned
int32 CurTriIndex = StartTriIndex;
FOneRingWedge CurWedge;
CurWedge.WedgeVertex = Vertex.VertexID;
CurWedge.Triangles.Add(Vertex.SortedTriangles[CurTriIndex]);
CurWedge.BorderEdges.A = Vertex.IncomingBevelMeshEdges[0];
for (int32 k = 0; k < NT; ++k)
{
int32 CurTri = Vertex.SortedTriangles[CurTriIndex % NT];
int32 NextTri = Vertex.SortedTriangles[(CurTriIndex + 1) % NT];
int32 SharedEdge = FindSharedEdgeInTriangles(Mesh, CurTri, NextTri);
MESH_BEVEL_DEBUG_CHECK(SharedEdge != -1);
if (Vertex.IncomingBevelMeshEdges.Contains(SharedEdge))
{
// if we found a bevel-edge, close the current wedge and start a new one
CurWedge.BorderEdges.B = SharedEdge;
Vertex.Wedges.Add(CurWedge);
CurWedge = FOneRingWedge();
CurWedge.WedgeVertex = Vertex.VertexID;
CurWedge.BorderEdges.A = SharedEdge;
}
CurWedge.Triangles.Add(NextTri);
CurTriIndex++;
}
// ?? is there a chance that we have a final open wedge here? we iterate one extra time so it shouldn't happen (or could we get an extra wedge then??)
for (FOneRingWedge& Wedge : Vertex.Wedges)
{
Wedge.BorderEdgeTriEdgeIndices.A = Mesh.GetTriEdges(Wedge.Triangles[0]).IndexOf(Wedge.BorderEdges.A);
Wedge.BorderEdgeTriEdgeIndices.B = Mesh.GetTriEdges(Wedge.Triangles.Last()).IndexOf(Wedge.BorderEdges.B);
}
if (Vertex.Wedges.Num() > 1)
{
Vertex.VertexType = EBevelVertexType::JunctionVertex;
}
else
{
Vertex.VertexType = EBevelVertexType::Unknown;
}
}
void FMeshBevel::BuildTerminatorVertex(FBevelVertex& Vertex, const FDynamicMesh3& Mesh)
{
Vertex.VertexType = EBevelVertexType::Unknown;
if (MESH_BEVEL_DEBUG_ENSURE(Vertex.IncomingBevelMeshEdges.Num() == 1) == false)
{
return;
}
int32 IncomingEdgeID = Vertex.IncomingBevelMeshEdges[0];
int32 NumTris = Vertex.SortedTriangles.Num();
// We have one edge coming into the vertex one ring, our main problem is to pick a second
// edge to split the one-ring with. There is no obvious right answer in many cases.
// "other" split edge that we pick
int32 RingSplitEdgeID = -1;
// NOTE: code below assumes we have polygroups on the mesh. In theory we could also support not having polygroups,
// by (eg) picking an arbitrary edge "furthest" from IncomingEdgeID in the exponential map
// Find the ordered set of triangles that are not in either of the groups connected to IncomingEdgeID. Eg imagine
// a cube corner, if we want to bevel IncomingEdgeID along one of the cube edges, we want to add the new edge
// in the "furthest" face (perpendicular to the edge)
FIndex2i IncomingEdgeT = Mesh.GetEdgeT(IncomingEdgeID);
FIndex2i IncomingEdgeGroups(Mesh.GetTriangleGroup(IncomingEdgeT.A), Mesh.GetTriangleGroup(IncomingEdgeT.B));
// Find the first index of Vertex.SortedTriangles that we want to remove.
// This should not be able to fail but if it does, we will just start at 0
// and maybe end up with some bevel failures below
int32 NumTriangles = Vertex.SortedTriangles.Num();
int32 StartIndex = 0;
for (int32 k = 0; k < NumTriangles; ++k)
{
int32 gid = Mesh.GetTriangleGroup(Vertex.SortedTriangles[k]);
if (IncomingEdgeGroups.Contains(gid))
{
StartIndex = k;
break;
}
}
TArray<int32> OtherGroupTris; // sorted wedge of triangles that are not in either of the groups connected to incoming edge
TArray<int32> OtherGroups; // list of group IDs encountered, in-order
for ( int32 k = 0; k < NumTriangles; ++k )
{
// Vertex.SortedTriangles was ordered, ie sequential triangles were connected, but if we filter
// out some triangles it may no longer be sequential in OtherGroupTris, leading to badness.
// But the two groups we are removing should be contiguous, so if we start there, then the
// remaining tris should be contiguous. StartIndex found above should give us that triangle.
int32 ShiftedIndex = (StartIndex + k) % NumTriangles;
int32 tid = Vertex.SortedTriangles[ShiftedIndex];
int32 gid = Mesh.GetTriangleGroup(tid);
if (IncomingEdgeGroups.Contains(gid) == false)
{
OtherGroupTris.Add(tid);
OtherGroups.AddUnique(gid);
}
}
int32 NumRemainingTris = OtherGroupTris.Num();
// Determine which edge to split at in the "other" group triangles. If we only have one group
// then we can try to pick the "middlest" edge. The worst case is when there is only one triangle,
// then we are picking a not-very-good edge no matter what (potentially we should do an edge split or
// face poke in that situation). If we have multiple groups then we probably want to pick one
// of the group-boundary edges inside the triangle-span, ideally the "middlest" but currently we
// are just picking one arbitrarily...
if (OtherGroups.Num() == 1)
{
Vertex.NewGroupID = OtherGroups[0];
if (OtherGroupTris.Num() == 1)
{
FIndex3i TriEdges = Mesh.GetTriEdges(OtherGroupTris[0]);
for (int32 j = 0; j < 3; ++j)
{
if (Mesh.GetEdgeV(TriEdges[j]).Contains(Vertex.VertexID))
{
RingSplitEdgeID = TriEdges[j];
break;
}
}
}
else if (OtherGroupTris.Num() == 2)
{
RingSplitEdgeID = FindSharedEdgeInTriangles(Mesh, OtherGroupTris[0], OtherGroupTris[1]);
}
else
{
// try using the 'middlest' triangle as the 'middlest' edge
// TODO: should compute opening angles here and pick the edge closest to the middle of the angular span!!
int32 j = OtherGroupTris.Num() / 2;
RingSplitEdgeID = FindSharedEdgeInTriangles(Mesh, OtherGroupTris[j], OtherGroupTris[j+1]);
// If the OtherGroupTris list ended up being not contiguous (see above for how that can happen), then
// it's possible that (j) and (j+1) are not connected and the share-edge search will fail. In that case
// we will just linear-search for two connected triangles. If this fails then this vertex will not be bevelled.
if (RingSplitEdgeID == -1)
{
for (int32 k = 0; k < NumRemainingTris; ++k)
{
RingSplitEdgeID = FindSharedEdgeInTriangles(Mesh, OtherGroupTris[k], OtherGroupTris[(k+1)%NumRemainingTris]);
if (RingSplitEdgeID != -1)
{
break;
}
}
}
}
}
else
{
// Search for two adjacent triangles in different groups that have a shared edge. This search
// may need to wrap around if we got unlucky in the triangle ordering in OtherGroupTris
for (int32 k = 0; k < OtherGroupTris.Num(); ++k)
{
int32 TriangleA = OtherGroupTris[k], TriangleB = OtherGroupTris[(k+1)%NumRemainingTris];
if (Mesh.GetTriangleGroup(TriangleA) != Mesh.GetTriangleGroup(TriangleB))
{
RingSplitEdgeID = FindSharedEdgeInTriangles(Mesh, TriangleA, TriangleB);
Vertex.NewGroupID = -1; // allocate a new group for this triangle, this is usually what one would want
break;
}
}
}
if (RingSplitEdgeID == -1)
{
return;
}
// save edgeid/vertexid for the 'terminator edge' that we will disconnect at
FIndex2i SplitEdgeV = Mesh.GetEdgeV(RingSplitEdgeID);
Vertex.TerminatorInfo = FIndex2i(RingSplitEdgeID, SplitEdgeV.OtherElement(Vertex.VertexID));
// split the terminator vertex into two wedges
TArray<int32> SplitTriSets[2];
if (SplitInteriorVertexTrianglesIntoSubsets(&Mesh, Vertex.VertexID, IncomingEdgeID, RingSplitEdgeID, SplitTriSets[0], SplitTriSets[1]) == false)
{
return;
}
// make the wedge list
Vertex.Wedges.SetNum(2);
Vertex.Wedges[0].WedgeVertex = Vertex.VertexID;
Vertex.Wedges[0].Triangles.Append(SplitTriSets[0]);
Vertex.Wedges[1].WedgeVertex = Vertex.VertexID;
Vertex.Wedges[1].Triangles.Append(SplitTriSets[1]);
// We need to know the two border edges of each wedge, because we will use this information
// in later stages. Note that this block is not specific to the TerminatorVertex case
for (FOneRingWedge& Wedge : Vertex.Wedges)
{
int32 NumWedgeTris = Wedge.Triangles.Num();
FIndex2i VtxEdges0 = IndexUtil::FindVertexEdgesInTriangle(Mesh, Wedge.Triangles[0], Vertex.VertexID);
if (NumWedgeTris == 1)
{
// If the wedge only has one tri, both edges are the border edges.
// Note that these are not sorted, ie B might not be the edge shared with the next Wedge.
// Currently this does not matter but it might in the future?
Wedge.BorderEdges.A = VtxEdges0.A;
Wedge.BorderEdges.B = VtxEdges0.B;
}
else
{
// the wedge-border-edge is *not* the edge connected to the next triangle in the wedge-triangle-list
Wedge.BorderEdges.A = ( Mesh.GetEdgeT(VtxEdges0.A).Contains(Wedge.Triangles[1]) ) ? VtxEdges0.B : VtxEdges0.A;
// final wedge-border-edge is the same case, with the last and second-last tris
FIndex2i VtxEdges1 = IndexUtil::FindVertexEdgesInTriangle(Mesh, Wedge.Triangles[NumWedgeTris-1], Vertex.VertexID);
Wedge.BorderEdges.B = ( Mesh.GetEdgeT(VtxEdges1.A).Contains(Wedge.Triangles[NumWedgeTris-2]) ) ? VtxEdges1.B : VtxEdges1.A;
}
// save the index of the border edge in it's triangle, so that when we disconnect the wedges later,
// we can find the new edge ID
Wedge.BorderEdgeTriEdgeIndices.A = Mesh.GetTriEdges(Wedge.Triangles[0]).IndexOf(Wedge.BorderEdges.A);
Wedge.BorderEdgeTriEdgeIndices.B = Mesh.GetTriEdges(Wedge.Triangles.Last()).IndexOf(Wedge.BorderEdges.B);
}
Vertex.VertexType = EBevelVertexType::TerminatorVertex;
}
void FMeshBevel::UnlinkEdges(FDynamicMesh3& Mesh, FDynamicMeshChangeTracker* ChangeTracker)
{
for (FBevelEdge& Edge : Edges)
{
UnlinkBevelEdgeInterior(Mesh, Edge, ChangeTracker);
}
}
namespace UELocal
{
// decomposition of a vertex one-ring into two connected triangle subsets
struct FVertexSplit
{
int32 VertexID;
bool bOK;
TArray<int32> TriSets[2];
};
// walk along a sequence of vertex-splits and make sure that the split triangle sets
// maintain consistent "sides" (see call in UnlinkBevelEdgeInterior for more details)
static void ReconcileTriangleSets(TArray<FVertexSplit>& SplitSequence)
{
int32 N = SplitSequence.Num();
TArray<int32> PrevTriSet0;
for (int32 k = 0; k < N; ++k)
{
if (PrevTriSet0.Num() == 0 && SplitSequence[k].TriSets[0].Num() > 0)
{
PrevTriSet0 = SplitSequence[k].TriSets[0];
}
else
{
bool bFoundInSet0 = false;
for (int32 tid : SplitSequence[k].TriSets[0])
{
if (PrevTriSet0.Contains(tid))
{
bFoundInSet0 = true;
break;
}
}
if (!bFoundInSet0)
{
Swap(SplitSequence[k].TriSets[0], SplitSequence[k].TriSets[1]);
}
PrevTriSet0 = SplitSequence[k].TriSets[0];
}
}
}
};
void FMeshBevel::UnlinkBevelEdgeInterior(
FDynamicMesh3& Mesh,
FBevelEdge& BevelEdge,
FDynamicMeshChangeTracker* ChangeTracker)
{
// figure out what sets of triangles to split each vertex into
int32 N = BevelEdge.MeshVertices.Num();
TArray<UELocal::FVertexSplit> SplitsToProcess;
SplitsToProcess.SetNum(N);
// precompute triangle sets for each vertex we want to split, by "cutting" the one ring into two halves based
// on edges - 2 edges for interior vertices, and 1 edge for a boundary vertex at the start/end of the edge-span
SplitsToProcess[0] = UELocal::FVertexSplit{ BevelEdge.MeshVertices[0], false };
if (BevelEdge.bEndpointBoundaryFlag[0])
{
SplitsToProcess[0].bOK = SplitBoundaryVertexTrianglesIntoSubsets(&Mesh, SplitsToProcess[0].VertexID, BevelEdge.MeshEdges[0],
SplitsToProcess[0].TriSets[0], SplitsToProcess[0].TriSets[1]);
}
for (int32 k = 1; k < N - 1; ++k)
{
SplitsToProcess[k].VertexID = BevelEdge.MeshVertices[k];
if (Mesh.IsBoundaryVertex(SplitsToProcess[k].VertexID))
{
SplitsToProcess[k].bOK = false;
}
else
{
SplitsToProcess[k].bOK = SplitInteriorVertexTrianglesIntoSubsets(&Mesh, SplitsToProcess[k].VertexID,
BevelEdge.MeshEdges[k-1], BevelEdge.MeshEdges[k], SplitsToProcess[k].TriSets[0], SplitsToProcess[k].TriSets[1]);
}
}
SplitsToProcess[N-1] = UELocal::FVertexSplit{ BevelEdge.MeshVertices[N - 1], false };
if (BevelEdge.bEndpointBoundaryFlag[1])
{
SplitsToProcess[N-1].bOK = SplitBoundaryVertexTrianglesIntoSubsets(&Mesh, SplitsToProcess[N-1].VertexID, BevelEdge.MeshEdges[N-2],
SplitsToProcess[N-1].TriSets[0], SplitsToProcess[N-1].TriSets[1]);
}
// SplitInteriorVertexTrianglesIntoSubsets does not consistently order its output sets, ie, if you imagine [Edge0,Edge1] as a path
// cutting through the one ring, the "side" that Set0 and Set1 end up is arbitrary, and depends on the ordering of edges in the triangles of Edge1.
// This might ideally be fixed in the future, but for the time being, all we need is consistency. So we walk from the start of the
// edge to the end, checking for overlap between each tri-one-ring-wedge. If Split[k].TriSet0 does not overlap with Split[k-1].TriSet0, then
// we want to swap TriSet0 and TriSet1 at Split[k].
UELocal::ReconcileTriangleSets(SplitsToProcess);
// apply vertex splits and accumulate new list
N = SplitsToProcess.Num();
for (int32 k = 0; k < N; ++k)
{
const UELocal::FVertexSplit& Split = SplitsToProcess[k];
if (ChangeTracker)
{
ChangeTracker->SaveVertexOneRingTriangles(Split.VertexID, true);
}
bool bDone = false;
if (Split.bOK)
{
FDynamicMesh3::FVertexSplitInfo SplitInfo;
EMeshResult Result = Mesh.SplitVertex(Split.VertexID, Split.TriSets[0], SplitInfo);
if (MESH_BEVEL_DEBUG_ENSURE(Result == EMeshResult::Ok))
{
BevelEdge.NewMeshVertices.Add(SplitInfo.NewVertex);
bDone = true;
}
}
if (!bDone)
{
BevelEdge.NewMeshVertices.Add(Split.VertexID);
}
}
// now build edge correspondences
N = BevelEdge.MeshVertices.Num();
MESH_BEVEL_DEBUG_CHECK(N == BevelEdge.NewMeshVertices.Num());
for (int32 k = 0; k < N-1; ++k)
{
int32 Edge0 = BevelEdge.MeshEdges[k];
int32 Edge1 = Mesh.FindEdge(BevelEdge.NewMeshVertices[k], BevelEdge.NewMeshVertices[k + 1]);
BevelEdge.NewMeshEdges.Add(Edge1);
MESH_BEVEL_DEBUG_CHECK(Edge1 >= 0);
if ( Mesh.IsEdge(Edge1) && Edge0 != Edge1 && MeshEdgePairs.Contains(Edge0) == false )
{
MeshEdgePairs.Add(Edge0, Edge1);
MeshEdgePairs.Add(Edge1, Edge0);
}
}
}
void FMeshBevel::UnlinkBevelLoop(FDynamicMesh3& Mesh, FBevelLoop& BevelLoop, FDynamicMeshChangeTracker* ChangeTracker)
{
int32 N = BevelLoop.MeshVertices.Num();
TArray<UELocal::FVertexSplit> SplitsToProcess;
SplitsToProcess.SetNum(N);
// precompute triangle sets for each vertex we want to split
for (int32 k = 0; k < N; ++k)
{
SplitsToProcess[k].VertexID = BevelLoop.MeshVertices[k];
if (Mesh.IsBoundaryVertex(SplitsToProcess[k].VertexID))
{
// cannot split boundary vertex
SplitsToProcess[k].bOK = false;
}
else
{
int32 PrevEdge = (k == 0) ? BevelLoop.MeshEdges.Last() : BevelLoop.MeshEdges[k-1];
int32 CurEdge = BevelLoop.MeshEdges[k];
SplitsToProcess[k].bOK = SplitInteriorVertexTrianglesIntoSubsets(&Mesh, SplitsToProcess[k].VertexID,
PrevEdge, CurEdge, SplitsToProcess[k].TriSets[0], SplitsToProcess[k].TriSets[1]);
}
}
// fix up triangle sets - see call in UnlinkBevelEdgeInterior() for more info
UELocal::ReconcileTriangleSets(SplitsToProcess);
// apply vertex splits and accumulate new list
N = SplitsToProcess.Num();
for (int32 k = 0; k < N; ++k)
{
const UELocal::FVertexSplit& Split = SplitsToProcess[k];
if (ChangeTracker)
{
ChangeTracker->SaveVertexOneRingTriangles(Split.VertexID, true);
}
bool bDone = false;
if (Split.bOK)
{
FDynamicMesh3::FVertexSplitInfo SplitInfo;
EMeshResult Result = Mesh.SplitVertex(Split.VertexID, Split.TriSets[1], SplitInfo);
if (MESH_BEVEL_DEBUG_ENSURE(Result == EMeshResult::Ok))
{
BevelLoop.NewMeshVertices.Add(SplitInfo.NewVertex);
bDone = true;
}
}
if (!bDone)
{
BevelLoop.NewMeshVertices.Add(Split.VertexID); // failed to split, so we have a shared vertex on both "sides"
}
}
// now build edge correspondences
N = BevelLoop.MeshVertices.Num();
MESH_BEVEL_DEBUG_CHECK(N == BevelLoop.NewMeshVertices.Num());
for (int32 k = 0; k < N; ++k)
{
int32 Edge0 = BevelLoop.MeshEdges[k];
int32 Edge1 = Mesh.FindEdge(BevelLoop.NewMeshVertices[k], BevelLoop.NewMeshVertices[(k + 1)%N]);
BevelLoop.NewMeshEdges.Add(Edge1);
MESH_BEVEL_DEBUG_CHECK(Edge1 >= 0);
if (Mesh.IsEdge(Edge1) && Edge0 != Edge1 && MeshEdgePairs.Contains(Edge0) == false )
{
MeshEdgePairs.Add(Edge0, Edge1);
MeshEdgePairs.Add(Edge1, Edge0);
}
}
}
void FMeshBevel::UnlinkLoops(FDynamicMesh3& Mesh, FDynamicMeshChangeTracker* ChangeTracker)
{
for (FBevelLoop& Loop : Loops)
{
UnlinkBevelLoop(Mesh, Loop, ChangeTracker);
}
}
void FMeshBevel::UnlinkVertices(FDynamicMesh3& Mesh, FDynamicMeshChangeTracker* ChangeTracker)
{
// TODO: currently have to do terminator vertices first because we do some of the
// determination inside the unlink code...
for (FBevelVertex& Vertex : Vertices)
{
if (Vertex.VertexType == EBevelVertexType::TerminatorVertex)
{
UnlinkTerminatorVertex(Mesh, Vertex, ChangeTracker);
}
}
for (FBevelVertex& Vertex : Vertices)
{
if (Vertex.VertexType == EBevelVertexType::JunctionVertex)
{
UnlinkJunctionVertex(Mesh, Vertex, ChangeTracker);
}
}
}
void FMeshBevel::UnlinkJunctionVertex(FDynamicMesh3& Mesh, FBevelVertex& Vertex, FDynamicMeshChangeTracker* ChangeTracker)
{
MESH_BEVEL_DEBUG_CHECK(Vertex.VertexType == EBevelVertexType::JunctionVertex);
if (ChangeTracker)
{
ChangeTracker->SaveVertexOneRingTriangles(Vertex.VertexID, true);
}
int32 NumWedges = Vertex.Wedges.Num();
MESH_BEVEL_DEBUG_CHECK(NumWedges > 1);
// Split triangles around vertex into separate tri-sets based on wedges.
// This will create a new vertex for each wedge.
for (int32 k = 1; k < NumWedges; ++k)
{
FOneRingWedge& Wedge = Vertex.Wedges[k];
FDynamicMesh3::FVertexSplitInfo SplitInfo;
EMeshResult Result = Mesh.SplitVertex(Vertex.VertexID, Wedge.Triangles, SplitInfo);
if (MESH_BEVEL_DEBUG_ENSURE(Result == EMeshResult::Ok))
{
Wedge.WedgeVertex = SplitInfo.NewVertex;
}
}
// update end start/end pairs for each wedge. If we created new edges above, this is
// the first time we will encounter them, so save in edge correspondence map
for (int32 k = 0; k < NumWedges; ++k)
{
FOneRingWedge& Wedge = Vertex.Wedges[k];
for (int32 j = 0; j < 2; ++j)
{
int32 OldWedgeEdgeID = Wedge.BorderEdges[j];
int32 OldWedgeEdgeIndex = Wedge.BorderEdgeTriEdgeIndices[j];
int32 TriangleID = (j == 0) ? Wedge.Triangles[0] : Wedge.Triangles.Last();
int32 CurWedgeEdgeID = Mesh.GetTriEdges(TriangleID)[OldWedgeEdgeIndex];
if (OldWedgeEdgeID != CurWedgeEdgeID)
{
if (MeshEdgePairs.Contains(OldWedgeEdgeID) == false)
{
MeshEdgePairs.Add(OldWedgeEdgeID, CurWedgeEdgeID);
MeshEdgePairs.Add(CurWedgeEdgeID, OldWedgeEdgeID);
}
Wedge.BorderEdges[j] = CurWedgeEdgeID;
}
}
}
}
void FMeshBevel::UnlinkTerminatorVertex(FDynamicMesh3& Mesh, FBevelVertex& BevelVertex, FDynamicMeshChangeTracker* ChangeTracker)
{
MESH_BEVEL_DEBUG_CHECK(BevelVertex.VertexType == EBevelVertexType::TerminatorVertex);
MESH_BEVEL_DEBUG_CHECK(BevelVertex.Wedges.Num() == 2);
if (ChangeTracker)
{
ChangeTracker->SaveVertexOneRingTriangles(BevelVertex.VertexID, true);
}
// split the vertex
FDynamicMesh3::FVertexSplitInfo SplitInfo;
EMeshResult Result = Mesh.SplitVertex(BevelVertex.VertexID, BevelVertex.Wedges[1].Triangles, SplitInfo);
if (MESH_BEVEL_DEBUG_ENSURE(Result == EMeshResult::Ok))
{
BevelVertex.Wedges[1].WedgeVertex = SplitInfo.NewVertex;
// update end start/end pairs for each wedge, and save in the edge correspondence map.
// Note that this is the same block as in UnlinkJunctionVertex
int32 NumWedges = BevelVertex.Wedges.Num();
for (int32 k = 0; k < NumWedges; ++k)
{
FOneRingWedge& Wedge = BevelVertex.Wedges[k];
for (int32 j = 0; j < 2; ++j)
{
int32 OldWedgeEdgeID = Wedge.BorderEdges[j];
int32 OldWedgeEdgeIndex = Wedge.BorderEdgeTriEdgeIndices[j];
int32 TriangleID = (j == 0) ? Wedge.Triangles[0] : Wedge.Triangles.Last();
int32 CurWedgeEdgeID = Mesh.GetTriEdges(TriangleID)[OldWedgeEdgeIndex];
if (OldWedgeEdgeID != CurWedgeEdgeID)
{
if (MeshEdgePairs.Contains(OldWedgeEdgeID) == false)
{
MeshEdgePairs.Add(OldWedgeEdgeID, CurWedgeEdgeID);
MeshEdgePairs.Add(CurWedgeEdgeID, OldWedgeEdgeID);
}
Wedge.BorderEdges[j] = CurWedgeEdgeID;
}
}
}
}
}
void FMeshBevel::FixUpUnlinkedBevelEdges(FDynamicMesh3& Mesh)
{
// Rewrite vertex IDs in BevelEdge vertex lists to correctly match the vertices in the new unlinked wedges.
// We did not know these new vertices in UnlinkBevelEdgeInterior() because we didn't unlink the vertices
// into wedges until afterwards.
for (FBevelEdge& Edge : Edges)
{
// If this is a one-mesh-edge edge, then Edge.NewMeshEdges is incorrect because we could
// not actually unlink the edge in UnlinkBevelEdgeInterior (since there were no interior vertices).
// But now that we have unlinked the vertices, the other edge now exists, and we can find it here.
if (Edge.MeshEdges.Num() == 1)
{
int32* FoundOtherEdge = MeshEdgePairs.Find(Edge.MeshEdges[0]);
MESH_BEVEL_DEBUG_CHECK(FoundOtherEdge != nullptr);
if (FoundOtherEdge != nullptr)
{
Edge.NewMeshEdges[0] = *FoundOtherEdge;
}
else
{
continue; // something went wrong, loop below will break things
}
}
// process start and end vertices of the path
for (int32 j = 0; j < 2; ++j)
{
int32 vi = (j == 0) ? 0 : (Edge.MeshVertices.Num()-1);
int32 ei = (j == 0) ? 0 : (Edge.MeshEdges.Num()-1);
const FBevelVertex* BevelVertex = GetBevelVertexFromVertexID(Edge.MeshVertices[vi]);
int32& V0 = Edge.MeshVertices[vi];
int32& V1 = Edge.NewMeshVertices[vi];
int32 E0 = Edge.MeshEdges[ei], E1 = Edge.NewMeshEdges[ei];
bool bFoundV0 = false, bFoundV1 = false;
for (const FOneRingWedge& Wedge : BevelVertex->Wedges)
{
for (int32 tid : Wedge.Triangles)
{
FIndex3i TriEdges = Mesh.GetTriEdges(tid);
if (TriEdges.Contains(E0) && bFoundV0 == false)
{
MESH_BEVEL_DEBUG_CHECK( Mesh.GetEdgeV(E0).Contains(Wedge.WedgeVertex) );
V0 = Wedge.WedgeVertex;
bFoundV0 = true;
break;
}
else if (TriEdges.Contains(E1) && bFoundV1 == false)
{
MESH_BEVEL_DEBUG_CHECK( Mesh.GetEdgeV(E1).Contains(Wedge.WedgeVertex) );
V1 = Wedge.WedgeVertex;
bFoundV1 = true;
break;
}
}
}
}
}
}
void FMeshBevel::DisplaceVertices(FDynamicMesh3& Mesh, double Distance)
{
// fallback (very bad) technique to compute an inset vertex
auto GetDisplacedVertexPos = [Distance](const FDynamicMesh3& Mesh, int32 VertexID) -> FVector3d
{
FVector3d CurPos = Mesh.GetVertex(VertexID);
FVector3d Centroid = FMeshWeights::MeanValueCentroid(Mesh, VertexID);
return CurPos + Distance * Normalized(Centroid - CurPos);
};
// Basically want to inset any beveled edges inwards into the existing poly-faces.
// To do this we will solve using our standard inset technique, eg similar to FInsetMeshRegion,
// which involves computing 'inset lines' for each edge and then finding nearest-points between
// pairs of lines (which will be the intersection point if the face is planar).
// Need to keep track of the inset line sets for open paths because at the corner vertices we
// will need to combine data from multiple path-line-sets (possibly could do this more efficiently
// as we only ever need the first and last...but small in context)
struct FEdgePathInsetLines
{
TArray<FLine3d> InsetLines0;
TArray<FLine3d> InsetLines1;
};
TArray<FEdgePathInsetLines> AllInsetLines;
AllInsetLines.SetNum(Edges.Num());
// solve open paths
for ( int32 k = 0; k < Edges.Num(); ++k)
{
FBevelEdge& Edge = Edges[k];
UE::Geometry::ComputeInsetLineSegmentsFromEdges(Mesh, Edge.MeshEdges, InsetDistance, AllInsetLines[k].InsetLines0);
UE::Geometry::SolveInsetVertexPositionsFromInsetLines(Mesh, AllInsetLines[k].InsetLines0, Edge.MeshVertices, Edge.NewPositions0, false);
UE::Geometry::ComputeInsetLineSegmentsFromEdges(Mesh, Edge.NewMeshEdges, InsetDistance, AllInsetLines[k].InsetLines1);
UE::Geometry::SolveInsetVertexPositionsFromInsetLines(Mesh, AllInsetLines[k].InsetLines1, Edge.NewMeshVertices, Edge.NewPositions1, false);
}
// solve loops
for (FBevelLoop& Loop : Loops)
{
TArray<FLine3d> InsetLines;
UE::Geometry::ComputeInsetLineSegmentsFromEdges(Mesh, Loop.MeshEdges, InsetDistance, InsetLines);
UE::Geometry::SolveInsetVertexPositionsFromInsetLines(Mesh, InsetLines, Loop.MeshVertices, Loop.NewPositions0, true);
UE::Geometry::ComputeInsetLineSegmentsFromEdges(Mesh, Loop.NewMeshEdges, InsetDistance, InsetLines);
UE::Geometry::SolveInsetVertexPositionsFromInsetLines(Mesh, InsetLines, Loop.NewMeshVertices, Loop.NewPositions1, true);
}
// Now solve corners. For corners, we want to find the 1 or 2 inset-lines corresponding
// to the outgoing bevel-edges at each bevel-vertex-wedge. Unfortunately we do not have
// a precomputed mapping for this so we currently linear-search over the full edge set for
// each wedge. Could do in parallel (eg make list of valid wedges first)
for (FBevelVertex& Vertex : Vertices)
{
if ( (Vertex.VertexType == EBevelVertexType::JunctionVertex)
|| (Vertex.VertexType == EBevelVertexType::TerminatorVertex) )
{
int32 NumWedges = Vertex.Wedges.Num();
for (int32 k = 0; k < NumWedges; ++k)
{
FOneRingWedge& Wedge = Vertex.Wedges[k];
// collect up set of inset lines relevant to this vertex
TArray<FLine3d> SolveLines;
for (int32 j = 0; j < Edges.Num(); ++j)
{
if (Edges[j].MeshVertices[0] == Wedge.WedgeVertex)
{
SolveLines.Add(AllInsetLines[j].InsetLines0[0]);
}
else if (Edges[j].MeshVertices.Last() == Wedge.WedgeVertex)
{
SolveLines.Add(AllInsetLines[j].InsetLines0.Last());
}
else if (Edges[j].NewMeshVertices[0] == Wedge.WedgeVertex)
{
SolveLines.Add(AllInsetLines[j].InsetLines1[0]);
}
else if (Edges[j].NewMeshVertices.Last() == Wedge.WedgeVertex)
{
SolveLines.Add(AllInsetLines[j].InsetLines1.Last());
}
}
// now that we have our line set, use it to solve inset position
FVector3d CurPos = Mesh.GetVertex(Wedge.WedgeVertex);
if (SolveLines.Num() == 1)
{
Wedge.NewPosition = SolveLines[0].NearestPoint(CurPos);
}
else if (SolveLines.Num() == 2)
{
Wedge.NewPosition = UE::Geometry::SolveInsetVertexPositionFromLinePair(CurPos, SolveLines[0], SolveLines[1]);
}
else
{
// Is this even possible? #SolveLines should equal #BoundaryEdges, how can we have more than 2 at a vertex??
// fall back to not-very-good inset technique
Wedge.NewPosition = GetDisplacedVertexPos(Mesh, Wedge.WedgeVertex);
}
}
}
}
auto SetDisplacedPositions = [&GetDisplacedVertexPos](FDynamicMesh3& Mesh, TArray<int32>& VerticesIn, TArray<FVector3d>& PositionsIn, int32 InsetStart, int32 InsetEnd)
{
int32 NumVertices = VerticesIn.Num();
if (PositionsIn.Num() == NumVertices)
{
int32 Stop = NumVertices - InsetEnd;
for (int32 k = InsetStart; k < Stop; ++k)
{
Mesh.SetVertex(VerticesIn[k], PositionsIn[k]);
}
}
};
// now bake in new positions
for (FBevelEdge& Edge : Edges)
{
SetDisplacedPositions(Mesh, Edge.MeshVertices, Edge.NewPositions0, Edge.bEndpointBoundaryFlag[0]?0:1, Edge.bEndpointBoundaryFlag[1]?0:1);
SetDisplacedPositions(Mesh, Edge.NewMeshVertices, Edge.NewPositions1, Edge.bEndpointBoundaryFlag[0]?0:1, Edge.bEndpointBoundaryFlag[1]?0:1);
}
for (FBevelLoop& Loop : Loops)
{
SetDisplacedPositions(Mesh, Loop.MeshVertices, Loop.NewPositions0, 0, 0);
SetDisplacedPositions(Mesh, Loop.NewMeshVertices, Loop.NewPositions1, 0, 0);
}
for (FBevelVertex& Vertex : Vertices)
{
if ( (Vertex.VertexType == EBevelVertexType::JunctionVertex)
|| (Vertex.VertexType == EBevelVertexType::TerminatorVertex) )
{
for (FOneRingWedge& Wedge : Vertex.Wedges)
{
Mesh.SetVertex(Wedge.WedgeVertex, Wedge.NewPosition);
}
}
}
}
void FMeshBevel::AppendJunctionVertexPolygon(FDynamicMesh3& Mesh, FBevelVertex& Vertex)
{
MESH_BEVEL_DEBUG_CHECK(Vertex.VertexType == EBevelVertexType::JunctionVertex);
// UnlinkJunctionVertex() split the terminator vertex into N vertices, one for each
// (now disconnected) triangle-wedge. The wedges are ordered such that their wedge-vertices
// define a polygon with correct winding, so we can just mesh it and append the triangles
TArray<FVector3d> PolygonPoints;
for (FOneRingWedge& Wedge : Vertex.Wedges)
{
PolygonPoints.Add(Mesh.GetVertex(Wedge.WedgeVertex));
}
TArray<FIndex3i> Triangles;
PolygonTriangulation::TriangulateSimplePolygon<double>(PolygonPoints, Triangles);
Vertex.NewGroupID = Mesh.AllocateTriangleGroup();
for (FIndex3i Tri : Triangles)
{
int32 A = Vertex.Wedges[Tri.A].WedgeVertex;
int32 B = Vertex.Wedges[Tri.B].WedgeVertex;
int32 C = Vertex.Wedges[Tri.C].WedgeVertex;
int32 tid = Mesh.AppendTriangle(A, B, C, Vertex.NewGroupID);
if (Mesh.IsTriangle(tid))
{
Vertex.NewTriangles.Add(tid);
}
}
}
void FMeshBevel::AppendTerminatorVertexTriangle(FDynamicMesh3& Mesh, FBevelVertex& Vertex)
{
MESH_BEVEL_DEBUG_CHECK(Vertex.VertexType == EBevelVertexType::TerminatorVertex);
// UnlinkTerminatorVertex() opened up a triangle-shaped hole adjacent to the incoming edge quad-strip
// at the terminator vertex. The Wedges of the terminator vertex contain the vertex IDs of the two
// verts on the quad-strip edge. We need the third vertex. We stored [SplitEdge, FarVertexID] in
// .TerminatorInfo, however FarVertexID may have become a different vertex when we unlinked other
// vertices. So, we will try to use SplitEdge to find it.
// If this turns out to have problems, basically the QuadEdgeID is on the boundary of a 3-edge hole,
// and so it should be straightforward to find the two other boundary edges and that gives the vertex.
int32 RingSplitEdgeID = Vertex.TerminatorInfo.A;
if (Mesh.IsEdge(RingSplitEdgeID))
{
FIndex2i SplitEdgeV = Mesh.GetEdgeV(RingSplitEdgeID);
int32 FarVertexID = SplitEdgeV.OtherElement(Vertex.VertexID);
int32 QuadEdgeID = Mesh.FindEdge(Vertex.Wedges[0].WedgeVertex, Vertex.Wedges[1].WedgeVertex);
if (Mesh.IsEdge(QuadEdgeID))
{
FIndex2i QuadEdgeV = Mesh.GetOrientedBoundaryEdgeV(QuadEdgeID);
// should have computed this GroupID in initial setup
int32 UseGroupID = (Vertex.NewGroupID >= 0) ? Vertex.NewGroupID : Mesh.AllocateTriangleGroup();
int32 tid = Mesh.AppendTriangle(QuadEdgeV.B, QuadEdgeV.A, FarVertexID, UseGroupID);
if (Mesh.IsTriangle(tid))
{
Vertex.NewTriangles.Add(tid);
}
else
{
MESH_BEVEL_DEBUG_CHECK(false);
}
}
else
{
MESH_BEVEL_DEBUG_CHECK(false);
}
}
}
void FMeshBevel::AppendTerminatorVertexPairQuad(FDynamicMesh3& Mesh, FBevelVertex& Vertex0, FBevelVertex& Vertex1)
{
MESH_BEVEL_DEBUG_CHECK(Vertex0.VertexType == EBevelVertexType::TerminatorVertex);
MESH_BEVEL_DEBUG_CHECK(Vertex1.VertexType == EBevelVertexType::TerminatorVertex);
// This is a variant of AppendTerminatorVertexTriangle that handles the case where basically two
// Terminator Vertices are directly connected by a non-beveled mesh edge that was used as the ring-split-edge.
// Since both sides were opened, we have a quad-shaped hole instead of a triangle-shaped hole, with a quad-edge
// at each end. The quad can be filled directly, we just need to sort out ordering/etc
// does not seem like we need to do anything w/ the TerminatorInfo here, we can get everything from wedges
int32 QuadEdgeID0 = Mesh.FindEdge(Vertex0.Wedges[0].WedgeVertex, Vertex0.Wedges[1].WedgeVertex);
int32 QuadEdgeID1 = Mesh.FindEdge(Vertex1.Wedges[0].WedgeVertex, Vertex1.Wedges[1].WedgeVertex);
MESH_BEVEL_DEBUG_CHECK(Mesh.IsEdge(QuadEdgeID0) && Mesh.IsEdge(QuadEdgeID1));
FIndex2i QuadEdgeV0 = Mesh.GetOrientedBoundaryEdgeV(QuadEdgeID0);
FIndex2i QuadEdgeV1 = Mesh.GetOrientedBoundaryEdgeV(QuadEdgeID1);
// make sure that the two opposing/connecting edges exist
MESH_BEVEL_DEBUG_CHECK(
Mesh.FindEdge(QuadEdgeV0.A, QuadEdgeV1.B) != IndexConstants::InvalidID &&
Mesh.FindEdge(QuadEdgeV0.B, QuadEdgeV1.A) != IndexConstants::InvalidID);
// BIASED? should have computed this GroupID in initial setup
int32 UseGroupID = (Vertex0.NewGroupID >= 0) ? Vertex0.NewGroupID : Mesh.AllocateTriangleGroup();
// quad order is V0.B, V0.A, V1.B, V1.A
int32 tid0 = Mesh.AppendTriangle(QuadEdgeV0.B, QuadEdgeV0.A, QuadEdgeV1.B, UseGroupID);
MESH_BEVEL_DEBUG_CHECK(tid0 >= 0);
if (Mesh.IsTriangle(tid0))
{
Vertex0.NewTriangles.Add(tid0);
}
int32 tid1 = Mesh.AppendTriangle(QuadEdgeV0.B, QuadEdgeV1.B, QuadEdgeV1.A, UseGroupID);
MESH_BEVEL_DEBUG_CHECK(tid1 >= 0);
if (Mesh.IsTriangle(tid1))
{
Vertex1.NewTriangles.Add(tid1);
}
}
void FMeshBevel::AppendEdgeQuads(FDynamicMesh3& Mesh, FBevelEdge& Edge)
{
int32 NumEdges = Edge.MeshEdges.Num();
if (NumEdges != Edge.NewMeshEdges.Num())
{
return;
}
Edge.NewGroupID = Mesh.AllocateTriangleGroup();
// At this point each edge-span should be fully disconnected into a set of paired edges,
// so we can trivially join each edge pair with a quad.
for (int32 k = 0; k < NumEdges; ++k)
{
int32 EdgeID0 = Edge.MeshEdges[k];
int32 EdgeID1 = Edge.NewMeshEdges[k];
// in certain cases, like bevel topo-edges with a single mesh-edge, we would not
// have been able to construct the "other" mesh edge when processing the topo-edge
// (where .NewMeshEdges is computed), it would only have been created when processing the
// junction vertex. Currently we do not go back and update .NewMeshEdges in that case, but
// we do store the edge-pair-correspondence in the MeshEdgePairs map.
if (EdgeID0 == EdgeID1)
{
int32* FoundEdgeID1 = MeshEdgePairs.Find(EdgeID0);
if (FoundEdgeID1 != nullptr)
{
EdgeID1 = *FoundEdgeID1;
}
}
FIndex2i QuadTris(IndexConstants::InvalidID, IndexConstants::InvalidID);
if (EdgeID0 != EdgeID1 && Mesh.IsEdge(EdgeID1) )
{
FIndex2i EdgeV0 = Mesh.GetOrientedBoundaryEdgeV(EdgeID0);
FIndex2i EdgeV1 = Mesh.GetOrientedBoundaryEdgeV(EdgeID1);
if (EdgeV0.Contains(EdgeV1.A) || EdgeV0.Contains(EdgeV1.B))
{
// If we hit this case, it means that Edge0 and Edge1 are still connected at one end, and
// so cannot be connected by a Quad, they can only be connected by a single triangle.
// It is unclear how we end up in this situation, it does occur somewhat regularly in complex
// geometry scripts though (eg see UE-157531 for a potential repro).
int32 OtherV = EdgeV0.Contains(EdgeV1.A) ? EdgeV1.B : EdgeV1.A;
QuadTris.A = Mesh.AppendTriangle(EdgeV0.B, EdgeV0.A, OtherV, Edge.NewGroupID);
QuadTris.B = IndexConstants::InvalidID;
}
else
{
QuadTris.A = Mesh.AppendTriangle(EdgeV0.B, EdgeV0.A, EdgeV1.B, Edge.NewGroupID);
QuadTris.B = Mesh.AppendTriangle(EdgeV1.B, EdgeV1.A, EdgeV0.B, Edge.NewGroupID);
}
}
Edge.StripQuads.Add(QuadTris);
}
}
void FMeshBevel::AppendLoopQuads(FDynamicMesh3& Mesh, FBevelLoop& Loop)
{
int32 NumEdges = Loop.MeshEdges.Num();
if (NumEdges != Loop.NewMeshEdges.Num())
{
return;
}
auto GetGroupKey = [&Mesh, &Loop](int32 k)
{
FIndex2i EdgeTris = Loop.MeshEdgeTris[k];
int32 Group0 = Mesh.GetTriangleGroup(EdgeTris.A);
int32 Group1 = Mesh.IsTriangle(EdgeTris.B) ? Mesh.GetTriangleGroup(EdgeTris.B) : -1;
return FIndex2i(FMath::Max(Group0, Group1), FMath::Min(Group0, Group1));
};
TMap<FIndex2i, int> NewGroupIDs;
for (int32 k = 0; k < NumEdges; ++k)
{
FIndex2i GroupKey = GetGroupKey(k);
if (NewGroupIDs.Contains(GroupKey) == false)
{
NewGroupIDs.Add(GroupKey, Mesh.AllocateTriangleGroup());
Loop.NewGroupIDs.Add(NewGroupIDs[GroupKey]);
}
}
// At this point each edge-span should be fully disconnected into a set of paired edges,
// so we can trivially join each edge pair with a quad.
for (int32 k = 0; k < NumEdges; ++k)
{
int32 EdgeID0 = Loop.MeshEdges[k];
int32 EdgeID1 = Loop.NewMeshEdges[k];
// case that happens in AppendEdgeQuads() should never happen for loops...
FIndex2i QuadTris(IndexConstants::InvalidID, IndexConstants::InvalidID);
if (EdgeID0 != EdgeID1 && Mesh.IsEdge(EdgeID1))
{
FIndex2i GroupKey = GetGroupKey(k);
int32 NewGroupID = NewGroupIDs[GroupKey];
FIndex2i EdgeV0 = Mesh.GetOrientedBoundaryEdgeV(EdgeID0);
FIndex2i EdgeV1 = Mesh.GetOrientedBoundaryEdgeV(EdgeID1);
QuadTris.A = Mesh.AppendTriangle(EdgeV0.B, EdgeV0.A, EdgeV1.B, NewGroupID);
QuadTris.B = Mesh.AppendTriangle(EdgeV1.B, EdgeV1.A, EdgeV0.B, NewGroupID);
}
Loop.StripQuads.Add(QuadTris);
}
}
void FMeshBevel::CreateBevelMeshing(FDynamicMesh3& Mesh)
{
for (FBevelVertex& Vertex : Vertices)
{
if (Vertex.VertexType == EBevelVertexType::JunctionVertex)
{
if (Vertex.Wedges.Num() > 2)
{
AppendJunctionVertexPolygon(Mesh, Vertex);
}
}
}
for (FBevelEdge& Edge : Edges)
{
AppendEdgeQuads(Mesh, Edge);
}
for (FBevelLoop& Loop : Loops)
{
AppendLoopQuads(Mesh, Loop);
}
// easier to do terminators last so that we can use quad edge to orient the triangle
TSet<FIndex2i> HandledQuadVtxPairs;
for (FBevelVertex& Vertex : Vertices)
{
if (Vertex.VertexType == EBevelVertexType::TerminatorVertex)
{
if (Vertex.ConnectedBevelVertex >= 0)
{
FBevelVertex& OtherVertex = Vertices[Vertex.ConnectedBevelVertex];
FIndex2i VtxPair(Vertex.VertexID, OtherVertex.VertexID);
VtxPair.Sort();
if (HandledQuadVtxPairs.Contains(VtxPair) == false)
{
AppendTerminatorVertexPairQuad(Mesh, Vertex, OtherVertex);
HandledQuadVtxPairs.Add(VtxPair);
}
}
else
{
AppendTerminatorVertexTriangle(Mesh, Vertex);
}
}
}
}
void FMeshBevel::ComputeNormals(FDynamicMesh3& Mesh)
{
if (Mesh.HasAttributes() == false)
{
return;
}
FDynamicMeshNormalOverlay* NormalOverlay = Mesh.Attributes()->PrimaryNormals();
auto SetNormalsOnTriRegion = [NormalOverlay](const TArray<int32>& Triangles)
{
if (Triangles.Num() > 0)
{
FMeshNormals::InitializeOverlayRegionToPerVertexNormals(NormalOverlay, Triangles);
}
};
for (FBevelVertex& Vertex : Vertices)
{
SetNormalsOnTriRegion(Vertex.NewTriangles);
}
TArray<int32> TriList;
for (FBevelEdge& Edge : Edges)
{
UELocal::QuadsToTris(Mesh, Edge.StripQuads, TriList, true);
SetNormalsOnTriRegion(TriList);
}
for (FBevelLoop& Loop : Loops)
{
UELocal::QuadsToTris(Mesh, Loop.StripQuads, TriList, true);
SetNormalsOnTriRegion(TriList);
}
}
void FMeshBevel::ComputeUVs(FDynamicMesh3& Mesh)
{
if (Mesh.HasAttributes() == false)
{
return;
}
FDynamicMeshUVOverlay* UVOverlay = Mesh.Attributes()->PrimaryUV();
auto SetUVsOnTriRegion = [&Mesh, UVOverlay](const TArray<int32>& Triangles)
{
if (Triangles.Num() > 0)
{
UE::Geometry::ComputeArbitraryTrianglePatchUVs(Mesh, *UVOverlay, Triangles);
}
};
TArray<int32> TriList;
for (FBevelEdge& Edge : Edges)
{
UELocal::QuadsToTris(Mesh, Edge.StripQuads, TriList, true);
SetUVsOnTriRegion(TriList);
}
for (FBevelLoop& Loop : Loops)
{
UELocal::QuadsToTris(Mesh, Loop.StripQuads, TriList, true);
SetUVsOnTriRegion(TriList);
}
// do vertices last because until edges have UVs, the vertex polygons have no neighbour UVs islands
for (FBevelVertex& Vertex : Vertices)
{
SetUVsOnTriRegion(Vertex.NewTriangles);
}
}
void FMeshBevel::ComputeMaterialIDs(FDynamicMesh3& Mesh)
{
if (Mesh.HasAttributes() == false || Mesh.Attributes()->HasMaterialID() == false)
{
return;
}
FDynamicMeshMaterialAttribute* MaterialIDs = Mesh.Attributes()->GetMaterialID();
if (MaterialIDMode == EMaterialIDMode::ConstantMaterialID)
{
for (int32 tid : NewTriangles)
{
MaterialIDs->SetValue(tid, SetConstantMaterialID);
}
}
else
{
auto SetQuadMaterial = [&Mesh, MaterialIDs](const FIndex2i& Quad, int32 MaterialID)
{
if (Quad.A >= 0)
{
MaterialIDs->SetValue(Quad.A, MaterialID);
}
if (Quad.B >= 0)
{
MaterialIDs->SetValue(Quad.B, MaterialID);
}
};
// Try to set materials on the new triangles along a beveled edge based on the adjacent pre-bevel triangles.
// Could be improved to at least be more consistent in ambiguous cases
auto SetEdgeMaterials = [&Mesh, MaterialIDs, this, SetQuadMaterial](const TArray<FIndex2i>& StripQuads, const TArray<FIndex2i>& EdgeTris)
{
int32 NumEdges = EdgeTris.Num();
if (StripQuads.Num() == NumEdges)
{
TArray<int32> SawMaterialIDs;
TArray<int32> AmbiguousEdges;
for (int32 k = 0; k < StripQuads.Num(); ++k)
{
FIndex2i NbrTris = EdgeTris[k];
int MatIDA = MaterialIDs->GetValue(NbrTris.A);
int MatIDB = (NbrTris.A >= 0) ? MaterialIDs->GetValue(NbrTris.B) : MatIDA;
SawMaterialIDs.AddUnique(MatIDA);
SawMaterialIDs.AddUnique(MatIDB);
int SetMaterialID = (MatIDA == MatIDB) ? MatIDA : SetConstantMaterialID;
if (MatIDA != MatIDB)
{
if (MaterialIDMode == EMaterialIDMode::InferMaterialID_ConstantIfAmbiguous)
{
SetMaterialID = SetConstantMaterialID;
}
else
{
AmbiguousEdges.Add(k);
}
}
SetQuadMaterial(StripQuads[k], SetMaterialID);
}
if (AmbiguousEdges.Num() > 0)
{
SawMaterialIDs.Sort();
if (AmbiguousEdges.Num() == NumEdges) // if all ambigous, just pick one
{
for (int32 k : AmbiguousEdges)
{
SetQuadMaterial(StripQuads[k], SawMaterialIDs[0]);
}
}
else
{
// TODO: what we probably want to do here is "infill" from known neighbours.
// for now we will just punt and pick one
for (int32 k : AmbiguousEdges)
{
SetQuadMaterial(StripQuads[k], SawMaterialIDs[0]);
}
}
}
}
else
{
for (const FIndex2i& Quad : StripQuads)
{
SetQuadMaterial(Quad, SetConstantMaterialID);
}
}
};
for (FBevelEdge& Edge : Edges)
{
SetEdgeMaterials(Edge.StripQuads, Edge.MeshEdgeTris);
}
for (FBevelLoop& Loop : Loops)
{
SetEdgeMaterials(Loop.StripQuads, Loop.MeshEdgeTris);
}
// find all the unique material IDs of neighbours of the Triangles list (that are not in Triangles list) and
// return (MaterialID, NbrTriCount) tuples as a pair of lists
auto CountUniqueBorderMaterialIDs = [&](const FDynamicMesh3& Mesh, const FDynamicMeshMaterialAttribute& MaterialAttrib, const TArray<int32>& Triangles, TArray<int32>& MaterialIDs, TArray<int32>& Counts)
{
MaterialIDs.Reset(); Counts.Reset();
for (int32 tid : Triangles)
{
FIndex3i TriNbrs = Mesh.GetTriNeighbourTris(tid);
for (int32 j = 0; j < 3; ++j)
{
int32 NbrTriangleID = TriNbrs[j];
if ( Mesh.IsTriangle(NbrTriangleID) == false || Triangles.Contains(NbrTriangleID) )
{
continue;
}
int MatID = MaterialAttrib.GetValue(NbrTriangleID);
int32 Index = MaterialIDs.AddUnique(MatID);
if (Counts.Num() != MaterialIDs.Num())
{
Counts.Add(0);
Counts[Index]++;
}
}
}
};
// For each bevel-vertex-polygon, pick the nbr material ID that was most frequent.
// Terminator vertices are also handled this way, which is not ideal, should probably
// ignore the new 'edge' faces for the terminator vertex
for (FBevelVertex& Vertex : Vertices)
{
TArray<int32> NbrMaterialIDs, NbrMaterialIDCounts;
CountUniqueBorderMaterialIDs(Mesh, *MaterialIDs, Vertex.NewTriangles, NbrMaterialIDs, NbrMaterialIDCounts);
int32 SetMaterialID = SetConstantMaterialID;
if (NbrMaterialIDs.Num() > 0)
{
int32 MinIndex = 0;
for (int32 k = 1; k < NbrMaterialIDs.Num(); ++k)
{
if (NbrMaterialIDCounts[k] < NbrMaterialIDCounts[MinIndex])
{
MinIndex = k;
}
}
SetMaterialID = NbrMaterialIDs[MinIndex];
}
for (int32 tid : Vertex.NewTriangles)
{
MaterialIDs->SetValue(tid, SetMaterialID);
}
}
}
}
Reference in New Issue View Git Blame Copy Permalink