From 9648d32182a16b2b90dc0e090376e939aa750730 Mon Sep 17 00:00:00 2001 From: Emmett Lalish Date: Mon, 16 May 2022 23:46:08 -0700 Subject: [PATCH 1/6] testing --- manifold/src/edge_op.cpp | 23 +++++++++++++++-------- test/mesh_test.cpp | 4 ++-- test/test_main.cpp | 2 -- 3 files changed, 17 insertions(+), 12 deletions(-) diff --git a/manifold/src/edge_op.cpp b/manifold/src/edge_op.cpp index eecf01568..eac8c4e88 100644 --- a/manifold/src/edge_op.cpp +++ b/manifold/src/edge_op.cpp @@ -121,7 +121,8 @@ void Manifold::Impl::SimplifyTopology() { VecDH flaggedEdges(halfedge_.size()); int numFlagged = thrust::copy_if( - thrust::device, countAt(0), countAt(halfedge_.size()), flaggedEdges.begin(), + thrust::device, countAt(0), countAt(halfedge_.size()), + flaggedEdges.begin(), ShortEdge({halfedge_.cptrD(), vertPos_.cptrD(), precision_})) - flaggedEdges.begin(); flaggedEdges.resize(numFlagged); @@ -131,7 +132,8 @@ void Manifold::Impl::SimplifyTopology() { flaggedEdges.resize(halfedge_.size()); numFlagged = thrust::copy_if( - thrust::device, countAt(0), countAt(halfedge_.size()), flaggedEdges.begin(), + thrust::device, countAt(0), countAt(halfedge_.size()), + flaggedEdges.begin(), FlagEdge({halfedge_.cptrD(), meshRelation_.triBary.cptrD()})) - flaggedEdges.begin(); flaggedEdges.resize(numFlagged); @@ -139,11 +141,12 @@ void Manifold::Impl::SimplifyTopology() { for (const int edge : flaggedEdges) CollapseEdge(edge); flaggedEdges.resize(halfedge_.size()); - numFlagged = thrust::copy_if( - thrust::device, countAt(0), countAt(halfedge_.size()), flaggedEdges.begin(), - SwappableEdge({halfedge_.cptrD(), vertPos_.cptrD(), - faceNormal_.cptrD(), precision_})) - - flaggedEdges.begin(); + numFlagged = + thrust::copy_if(thrust::device, countAt(0), countAt(halfedge_.size()), + flaggedEdges.begin(), + SwappableEdge({halfedge_.cptrD(), vertPos_.cptrD(), + faceNormal_.cptrD(), precision_})) - + flaggedEdges.begin(); flaggedEdges.resize(numFlagged); for (const int edge : flaggedEdges) { @@ -202,10 +205,14 @@ void Manifold::Impl::CollapseTri(const glm::ivec3& triEdge) { } void Manifold::Impl::RemoveIfFolded(int edge) { + const int pair = halfedge_[edge].pairedHalfedge; + if (pair < 0) return; + const glm::ivec3 tri0edge = TriOf(edge); - const glm::ivec3 tri1edge = TriOf(halfedge_[edge].pairedHalfedge); + const glm::ivec3 tri1edge = TriOf(pair); if (halfedge_[tri0edge[1]].endVert == halfedge_[tri1edge[1]].endVert) { for (int i : {0, 1, 2}) { + if (halfedge_[tri0edge[i]].startVert < 0) continue; vertPos_[halfedge_[tri0edge[i]].startVert] = glm::vec3(NAN); halfedge_[tri0edge[i]] = {-1, -1, -1, -1}; halfedge_[tri1edge[i]] = {-1, -1, -1, -1}; diff --git a/test/mesh_test.cpp b/test/mesh_test.cpp index ef0db72ac..61aa348a5 100644 --- a/test/mesh_test.cpp +++ b/test/mesh_test.cpp @@ -751,7 +751,7 @@ TEST(Boolean, Gyroid) { Related(result, input, meshID2idx); } -TEST(Boolean, DISABLED_Cylinders) { +TEST(Boolean, Cylinders) { Manifold rod = Manifold::Cylinder(1.0, 0.4, -1.0, 20); float arrays1[][12] = { {0, 0, 1, 1, // @@ -830,7 +830,7 @@ TEST(Boolean, DISABLED_Cylinders) { } m2 += Manifold(rod).Transform(mat); } - + std::cout << "union 3" << std::endl; m1 += m2; EXPECT_TRUE(m1.IsManifold()); diff --git a/test/test_main.cpp b/test/test_main.cpp index 2a570f528..bb12a9541 100644 --- a/test/test_main.cpp +++ b/test/test_main.cpp @@ -27,8 +27,6 @@ void print_usage() { int main(int argc, char **argv) { ::testing::InitGoogleTest(&argc, argv); - int c; - for (int i = 1; i < argc; i++) { if (argv[i][0] != '-') { fprintf(stderr, "Unknown option: %s\n", argv[i]); From 6f89c5974cacebf931b82120f04ee20180f90335 Mon Sep 17 00:00:00 2001 From: Emmett Lalish Date: Wed, 1 Jun 2022 22:26:33 -0700 Subject: [PATCH 2/6] updated cylinder test --- test/mesh_test.cpp | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) diff --git a/test/mesh_test.cpp b/test/mesh_test.cpp index a0c6944ff..59d215e41 100644 --- a/test/mesh_test.cpp +++ b/test/mesh_test.cpp @@ -785,23 +785,24 @@ TEST(Boolean, Gyroid) { } TEST(Boolean, Cylinders) { - Manifold rod = Manifold::Cylinder(1.0, 0.4, -1.0, 20); + Manifold rod = Manifold::Cylinder(1.0, 0.4, -1.0, 12); float arrays1[][12] = { + {0, 0, 1, 3, // + -1, 0, 0, 3, // + 0, -1, 0, 6}, // + {0, 0, 1, 2, // + -1, 0, 0, 3, // + 0, -1, 0, 8}, // + {0, 0, 1, 1, // -1, 0, 0, 2, // 0, -1, 0, 7}, // {1, 0, 0, 3, // 0, 1, 0, 2, // 0, 0, 1, 6}, // - {0, 0, 1, 3, // - -1, 0, 0, 3, // - 0, -1, 0, 6}, // {0, 0, 1, 3, // -1, 0, 0, 3, // 0, -1, 0, 7}, // - {0, 0, 1, 2, // - -1, 0, 0, 3, // - 0, -1, 0, 8}, // {0, 0, 1, 1, // -1, 0, 0, 3, // 0, -1, 0, 7}, // @@ -813,15 +814,16 @@ TEST(Boolean, Cylinders) { 0, -1, 0, 6}, // }; float arrays2[][12] = { - {0, 0, 1, 2, // - -1, 0, 0, 2, // - 0, -1, 0, 7}, // {1, 0, 0, 3, // 0, 0, 1, 2, // 0, -1, 0, 6}, // {1, 0, 0, 4, // 0, 1, 0, 3, // 0, 0, 1, 6}, // + + {0, 0, 1, 2, // + -1, 0, 0, 2, // + 0, -1, 0, 7}, // {1, 0, 0, 3, // 0, 1, 0, 3, // 0, 0, 1, 7}, // @@ -863,6 +865,7 @@ TEST(Boolean, Cylinders) { } m2 += Manifold(rod).Transform(mat); } + // ExportMesh("m2a.glb", m2.GetMesh(), {}); std::cout << "union 3" << std::endl; m1 += m2; From 359774115a1168fa57bde611d22d5e622a44f26e Mon Sep 17 00:00:00 2001 From: Emmett Lalish Date: Thu, 2 Jun 2022 22:38:19 -0700 Subject: [PATCH 3/6] removed CreateAndFixHalfedges --- manifold/src/edge_op.cpp | 35 ++++++++++++ manifold/src/face_op.cpp | 17 +++--- manifold/src/impl.cpp | 112 +++++++++++---------------------------- manifold/src/impl.h | 9 ++-- 4 files changed, 79 insertions(+), 94 deletions(-) diff --git a/manifold/src/edge_op.cpp b/manifold/src/edge_op.cpp index eac8c4e88..34bf01164 100644 --- a/manifold/src/edge_op.cpp +++ b/manifold/src/edge_op.cpp @@ -32,6 +32,17 @@ __host__ __device__ bool Is01Longest(glm::vec2 v0, glm::vec2 v1, glm::vec2 v2) { return l[0] > l[1] && l[0] > l[2]; } +struct DuplicateEdge { + const Halfedge* sortedHalfedge; + + __host__ __device__ bool operator()(int edge) { + const Halfedge& halfedge = sortedHalfedge[edge]; + const Halfedge& nextHalfedge = sortedHalfedge[edge + 1]; + return halfedge.startVert == nextHalfedge.startVert && + halfedge.endVert == nextHalfedge.endVert; + } +}; + struct ShortEdge { const Halfedge* halfedge; const glm::vec3* vertPos; @@ -118,8 +129,20 @@ namespace manifold { * removal, by setting vertPos to NaN and halfedge to {-1, -1, -1, -1}. */ void Manifold::Impl::SimplifyTopology() { + VecDH halfedge(halfedge_); + thrust::sort(thrust::device, halfedge.begin(), halfedge.end()); + // FIX: copy halfedge index, not sorted index. VecDH flaggedEdges(halfedge_.size()); int numFlagged = + thrust::copy_if(thrust::device, countAt(0), countAt(halfedge_.size() - 1), + flaggedEdges.begin(), DuplicateEdge({halfedge.cptrD()})) - + flaggedEdges.begin(); + flaggedEdges.resize(numFlagged); + + for (const int edge : flaggedEdges) SplitEdge(edge); + + flaggedEdges.resize(halfedge_.size()); + numFlagged = thrust::copy_if( thrust::device, countAt(0), countAt(halfedge_.size()), flaggedEdges.begin(), @@ -220,6 +243,18 @@ void Manifold::Impl::RemoveIfFolded(int edge) { } } +void Manifold::Impl::SplitEdge(const int current) { + int startVert = vertPos_.size(); + vertPos_.push_back(vertPos_[halfedge_[current].startVert]); + int endVert = vertPos_.size(); + vertPos_.push_back(vertPos_[halfedge_[current].endVert]); + + int pair = halfedge_[current].pairedHalfedge; + + UpdateVert(startVert, pair, NextHalfedge(NextHalfedge(current))); + UpdateVert(endVert, current, NextHalfedge(NextHalfedge(pair))); +} + void Manifold::Impl::CollapseEdge(const int edge) { VecDH& triBary = meshRelation_.triBary; diff --git a/manifold/src/face_op.cpp b/manifold/src/face_op.cpp index d90ea6492..bef2ae9fc 100644 --- a/manifold/src/face_op.cpp +++ b/manifold/src/face_op.cpp @@ -34,11 +34,11 @@ void Manifold::Impl::Face2Tri(const VecDH& faceEdge, const VecDH& halfedgeBary) { VecDH triVerts; VecDH triNormal; - VecDH &triBary = meshRelation_.triBary; + VecDH& triBary = meshRelation_.triBary; triBary.resize(0); triVerts.reserve(faceEdge.size()); triNormal.reserve(faceEdge.size()); - triBary.reserve(faceEdge.size()*3); + triBary.reserve(faceEdge.size() * 3); for (int face = 0; face < faceEdge.size() - 1; ++face) { const int firstEdge = faceEdge[face]; @@ -49,8 +49,7 @@ void Manifold::Impl::Face2Tri(const VecDH& faceEdge, auto linearSearch = [](const int* mapping, int value) { int i = 0; - while (mapping[i] != value) - ++i; + while (mapping[i] != value) ++i; return i; }; @@ -85,7 +84,8 @@ void Manifold::Impl::Face2Tri(const VecDH& faceEdge, halfedge_[firstEdge + 3].startVert}; const glm::mat3x2 projection = GetAxisAlignedProjection(normal); auto triCCW = [&projection, this](const glm::ivec3 tri) { - return CCW(projection * this->vertPos_[tri[0]], projection * this->vertPos_[tri[1]], + return CCW(projection * this->vertPos_[tri[0]], + projection * this->vertPos_[tri[1]], projection * this->vertPos_[tri[2]], precision_) >= 0; }; @@ -122,7 +122,7 @@ void Manifold::Impl::Face2Tri(const VecDH& faceEdge, } } - for (auto tri : { tri0, tri1 }) { + for (auto tri : {tri0, tri1}) { triVerts.push_back(tri); triNormal.push_back(normal); triBary.push_back(faceRef[face]); @@ -156,14 +156,13 @@ void Manifold::Impl::Face2Tri(const VecDH& faceEdge, triNormal.push_back(normal); triBary.push_back(faceRef[face]); for (int k : {0, 1, 2}) { - triBary.back().vertBary[k] = - vertBary[tri[k]]; + triBary.back().vertBary[k] = vertBary[tri[k]]; } } } } faceNormal_ = std::move(triNormal); - CreateAndFixHalfedges(triVerts); + CreateHalfedges(triVerts); } /** diff --git a/manifold/src/impl.cpp b/manifold/src/impl.cpp index 3ffd4e11c..be4e5f156 100644 --- a/manifold/src/impl.cpp +++ b/manifold/src/impl.cpp @@ -12,14 +12,15 @@ // See the License for the specific language governing permissions and // limitations under the License. +#include "impl.h" + #include #include -#include #include +#include #include "graph.h" -#include "impl.h" namespace { using namespace manifold; @@ -30,9 +31,10 @@ __host__ __device__ void AtomicAddVec3(glm::vec3& target, #ifdef __CUDA_ARCH__ atomicAdd(&target[i], add[i]); #else - std::atomic &tar = reinterpret_cast&>(target[i]); + std::atomic& tar = reinterpret_cast&>(target[i]); float old_val = tar.load(); - while (!tar.compare_exchange_weak(old_val, old_val + add[i])); + while (!tar.compare_exchange_weak(old_val, old_val + add[i])) + ; #endif } } @@ -129,41 +131,6 @@ struct LinkHalfedges { } }; -struct SwapHalfedges { - Halfedge* halfedges; - const TmpEdge* edges; - - __host__ void operator()(int k) { - const int i = 2 * k; - const int j = i - 2; - const TmpEdge thisEdge = edges[i]; - const TmpEdge lastEdge = edges[j]; - if (thisEdge.first == lastEdge.first && - thisEdge.second == lastEdge.second) { - const int swap0idx = thisEdge.halfedgeIdx; - Halfedge& swap0 = halfedges[swap0idx]; - const int swap1idx = swap0.pairedHalfedge; - Halfedge& swap1 = halfedges[swap1idx]; - - const int next0idx = swap0idx + ((swap0idx + 1) % 3 == 0 ? -2 : 1); - const int next1idx = swap1idx + ((swap1idx + 1) % 3 == 0 ? -2 : 1); - Halfedge& next0 = halfedges[next0idx]; - Halfedge& next1 = halfedges[next1idx]; - - next0.startVert = swap0.endVert = next1.endVert; - swap0.pairedHalfedge = next1.pairedHalfedge; - halfedges[swap0.pairedHalfedge].pairedHalfedge = swap0idx; - - next1.startVert = swap1.endVert = next0.endVert; - swap1.pairedHalfedge = next0.pairedHalfedge; - halfedges[swap1.pairedHalfedge].pairedHalfedge = swap1idx; - - next0.pairedHalfedge = next1idx; - next1.pairedHalfedge = next0idx; - } - } -}; - struct InitializeBaryRef { const int meshID; const Halfedge* halfedge; @@ -294,7 +261,7 @@ Manifold::Impl::Impl(const Mesh& mesh, CheckDevice(); CalculateBBox(); SetPrecision(); - CreateAndFixHalfedges(mesh.triVerts); + CreateHalfedges(mesh.triVerts); ALWAYS_ASSERT(IsManifold(), topologyErr, "Input mesh is not manifold!"); CalculateNormals(); InitializeNewReference(triProperties, properties, propertyTolerance); @@ -357,7 +324,8 @@ Manifold::Impl::Impl(Shape shape) { void Manifold::Impl::ReinitializeReference(int meshID) { // instead of storing the meshID, we store 0 and set the mapping to // 0 -> meshID, because the meshID after boolean operation also starts from 0. - thrust::for_each_n(thrust::device, zip(meshRelation_.triBary.begin(), countAt(0)), NumTri(), + thrust::for_each_n(thrust::device, + zip(meshRelation_.triBary.begin(), countAt(0)), NumTri(), InitializeBaryRef({0, halfedge_.cptrD()})); meshRelation_.originalID.clear(); meshRelation_.originalID[0] = meshID; @@ -386,10 +354,10 @@ int Manifold::Impl::InitializeNewReference( "propertyTolerance."); const int numSets = properties.size() / numProps; - ALWAYS_ASSERT(thrust::all_of(thrust::device, triPropertiesD.begin(), triPropertiesD.end(), - CheckProperties({numSets})), - userErr, - "triProperties value is outside the properties range."); + ALWAYS_ASSERT( + thrust::all_of(thrust::device, triPropertiesD.begin(), + triPropertiesD.end(), CheckProperties({numSets})), + userErr, "triProperties value is outside the properties range."); } VecDH> face2face(halfedge_.size(), {-1, -1}); @@ -474,22 +442,6 @@ int Manifold::Impl::InitializeNewReference( * Create the halfedge_ data structure from an input triVerts array like Mesh. */ void Manifold::Impl::CreateHalfedges(const VecDH& triVerts) { - const int numTri = triVerts.size(); - halfedge_.resize(3 * numTri); - VecDH edge(3 * numTri); - thrust::for_each_n(thrust::device, zip(countAt(0), triVerts.begin()), numTri, - Tri2Halfedges({halfedge_.ptrD(), edge.ptrD()})); - thrust::sort(thrust::device, edge.begin(), edge.end()); - thrust::for_each_n(thrust::device, countAt(0), halfedge_.size() / 2, - LinkHalfedges({halfedge_.ptrD(), edge.cptrD()})); -} - -/** - * Create the halfedge_ data structure from an input triVerts array like Mesh. - * Check that the input is an even-manifold, and if it is not 2-manifold, - * perform edge swaps until it is. This is a host function. - */ -void Manifold::Impl::CreateAndFixHalfedges(const VecDH& triVerts) { const int numTri = triVerts.size(); // drop the old value first to avoid copy halfedge_.resize(0); @@ -500,14 +452,11 @@ void Manifold::Impl::CreateAndFixHalfedges(const VecDH& triVerts) { // Stable sort is required here so that halfedges from the same face are // paired together (the triangles were created in face order). In some // degenerate situations the triangulator can add the same internal edge in - // two different faces, causing this edge to not be 2-manifold. We detect this - // and fix it by swapping one of the identical edges, so it is important that - // we have the edges paired according to their face. + // two different faces, causing this edge to not be 2-manifold. These are + // fixed by duplicating verts in SimplifyTopology. thrust::stable_sort(thrust::device, edge.begin(), edge.end()); thrust::for_each_n(thrust::host, countAt(0), halfedge_.size() / 2, LinkHalfedges({halfedge_.ptrH(), edge.cptrH()})); - thrust::for_each(thrust::host, countAt(1), countAt(halfedge_.size() / 2), - SwapHalfedges({halfedge_.ptrH(), edge.cptrH()})); } /** @@ -585,7 +534,8 @@ void Manifold::Impl::SetPrecision(float minPrecision) { */ void Manifold::Impl::CalculateNormals() { vertNormal_.resize(NumVert()); - thrust::fill(thrust::device, vertNormal_.begin(), vertNormal_.end(), glm::vec3(0)); + thrust::fill(thrust::device, vertNormal_.begin(), vertNormal_.end(), + glm::vec3(0)); bool calculateTriNormal = false; if (faceNormal_.size() != NumTri()) { faceNormal_.resize(NumTri()); @@ -595,7 +545,8 @@ void Manifold::Impl::CalculateNormals() { thrust::device, zip(faceNormal_.begin(), countAt(0)), NumTri(), AssignNormals({vertNormal_.ptrD(), vertPos_.cptrD(), halfedge_.cptrD(), precision_, calculateTriNormal})); - thrust::for_each(thrust::device, vertNormal_.begin(), vertNormal_.end(), Normalize()); + thrust::for_each(thrust::device, vertNormal_.begin(), vertNormal_.end(), + Normalize()); } /** @@ -605,28 +556,26 @@ void Manifold::Impl::CalculateNormals() { * Will raise an exception if meshRelation_.triBary[startTri..startTri+n] * contains a meshID not in meshIDs. * - * We remap them into indices starting from startID. The exact value value is not - * important as long as + * We remap them into indices starting from startID. The exact value value is + * not important as long as * 1. They are distinct * 2. `originalID[meshID]` is the original mesh ID of the triangle * * Use this when the mesh is a combination of several meshes or a subset of a * larger mesh, e.g. after performing boolean operations, compose or decompose. */ -void Manifold::Impl::UpdateMeshIDs(VecDH &meshIDs, VecDH &originalIDs, +void Manifold::Impl::UpdateMeshIDs(VecDH& meshIDs, VecDH& originalIDs, int startTri, int n, int startID) { - if (n == -1) - n = meshRelation_.triBary.size(); + if (n == -1) n = meshRelation_.triBary.size(); thrust::sort_by_key(thrust::host, meshIDs.begin(), meshIDs.end(), originalIDs.begin()); constexpr int kOccurred = 1 << 30; VecDH error(1, -1); const int numMesh = meshIDs.size(); - const int *meshIDsPtr = meshIDs.cptrD(); - int *originalPtr = originalIDs.ptrD(); - int *errorPtr = error.ptrD(); - thrust::for_each(thrust::device, - meshRelation_.triBary.begin() + startTri, + const int* meshIDsPtr = meshIDs.cptrD(); + int* originalPtr = originalIDs.ptrD(); + int* errorPtr = error.ptrD(); + thrust::for_each(thrust::device, meshRelation_.triBary.begin() + startTri, meshRelation_.triBary.begin() + startTri + n, [=] __host__ __device__(BaryRef & b) { int index = @@ -663,12 +612,13 @@ SparseIndices Manifold::Impl::EdgeCollisions(const Impl& Q) const { VecDH edges = CreateTmpEdges(Q.halfedge_); const int numEdge = edges.size(); VecDH QedgeBB(numEdge); - thrust::for_each_n(thrust::device, zip(QedgeBB.begin(), edges.cbegin()), numEdge, - EdgeBox({Q.vertPos_.cptrD()})); + thrust::for_each_n(thrust::device, zip(QedgeBB.begin(), edges.cbegin()), + numEdge, EdgeBox({Q.vertPos_.cptrD()})); SparseIndices q1p2 = collider_.Collisions(QedgeBB); - thrust::for_each(thrust::device, q1p2.begin(0), q1p2.end(0), ReindexEdge({edges.cptrD()})); + thrust::for_each(thrust::device, q1p2.begin(0), q1p2.end(0), + ReindexEdge({edges.cptrD()})); return q1p2; } diff --git a/manifold/src/impl.h b/manifold/src/impl.h index 1cb674ab6..e42fb07d7 100644 --- a/manifold/src/impl.h +++ b/manifold/src/impl.h @@ -32,8 +32,8 @@ struct Manifold::Impl { /// - In `MeshRelationD`: The original mesh triangle index = /// `originalID[meshID]` /// - /// @note Triangles coming from different manifolds should have different mesh - /// ID, otherwise `SimplifyTopology` will not work properly. + /// @note Triangles coming from different manifolds should have different + /// mesh ID, otherwise `SimplifyTopology` will not work properly. VecDH triBary; /// meshID to originalID mapping. std::unordered_map originalID; @@ -68,9 +68,9 @@ struct Manifold::Impl { void ReinitializeReference(int meshID); void CreateHalfedges(const VecDH& triVerts); - void CreateAndFixHalfedges(const VecDH& triVerts); void CalculateNormals(); - void UpdateMeshIDs(VecDH &meshIDs, VecDH &originalIDs, int startTri=0, int n=-1, int startID=0); + void UpdateMeshIDs(VecDH& meshIDs, VecDH& originalIDs, + int startTri = 0, int n = -1, int startID = 0); void Update(); void ApplyTransform() const; @@ -108,6 +108,7 @@ struct Manifold::Impl { // edge_op.cu void SimplifyTopology(); + void SplitEdge(int edge); void CollapseEdge(int edge); void RecursiveEdgeSwap(int edge); void RemoveIfFolded(int edge); From b7a5d532e2fb9c9c96b964808a4bea6c2aed9ba0 Mon Sep 17 00:00:00 2001 From: Emmett Lalish Date: Sun, 5 Jun 2022 12:20:25 -0700 Subject: [PATCH 4/6] Added DedupeEdge --- .vscode/settings.json | 8 ++++- manifold/src/edge_op.cpp | 67 +++++++++++++++++++++++++++---------- manifold/src/impl.h | 2 +- manifold/src/properties.cpp | 8 +++-- test/mesh_test.cpp | 2 -- 5 files changed, 63 insertions(+), 24 deletions(-) diff --git a/.vscode/settings.json b/.vscode/settings.json index 9144fda17..723cd2708 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -86,7 +86,13 @@ "set": "cpp", "memory_resource": "cpp", "random": "cpp", - "variant": "cpp" + "variant": "cpp", + "hash_map": "cpp", + "hash_set": "cpp", + "codecvt": "cpp", + "regex": "cpp", + "future": "cpp", + "shared_mutex": "cpp" }, "C_Cpp.clang_format_fallbackStyle": "google", "editor.formatOnSave": true, diff --git a/manifold/src/edge_op.cpp b/manifold/src/edge_op.cpp index eb5f6f7d0..f70e508d8 100644 --- a/manifold/src/edge_op.cpp +++ b/manifold/src/edge_op.cpp @@ -130,19 +130,23 @@ namespace manifold { * removal, by setting vertPos to NaN and halfedge to {-1, -1, -1, -1}. */ void Manifold::Impl::SimplifyTopology() { + auto policy = autoPolicy(halfedge_.size()); + VecDH halfedge(halfedge_); - thrust::sort(thrust::device, halfedge.begin(), halfedge.end()); - // FIX: copy halfedge index, not sorted index. + VecDH idx(halfedge_.size()); + sequence(policy, idx.begin(), idx.end()); + sort_by_key(policy, halfedge.begin(), halfedge.end(), idx.begin()); + VecDH flaggedEdges(halfedge_.size()); - auto policy = autoPolicy(halfedge_.size()); + int numFlagged = copy_if( - policy, countAt(0), countAt(halfedge_.size()), flaggedEdges.begin(), + policy, idx.begin(), idx.end() - 1, countAt(0), flaggedEdges.begin(), DuplicateEdge({halfedge.cptrD()})) - flaggedEdges.begin(); flaggedEdges.resize(numFlagged); - for (const int edge : flaggedEdges) SplitEdge(edge); + for (const int edge : flaggedEdges) DedupeEdge(edge); flaggedEdges.resize(halfedge_.size()); numFlagged = @@ -178,6 +182,47 @@ void Manifold::Impl::SimplifyTopology() { } } +void Manifold::Impl::DedupeEdge(const int edge) { + // Orbit endVert + const int startVert = halfedge_[edge].startVert; + const int endVert = halfedge_[edge].endVert; + int current = halfedge_[NextHalfedge(edge)].pairedHalfedge; + while (current != edge) { + const int vert = halfedge_[current].startVert; + if (vert == startVert) { + int newVert = vertPos_.size(); + vertPos_.push_back(vertPos_[endVert]); + current = halfedge_[NextHalfedge(current)].pairedHalfedge; + int opposite = halfedge_[NextHalfedge(edge)].pairedHalfedge; + + UpdateVert(newVert, current, opposite); + + int newHalfedge = halfedge_.size(); + int newFace = newHalfedge / 3; + int outsideVert = halfedge_[current].startVert; + halfedge_.push_back({endVert, newVert, -1, newFace}); + halfedge_.push_back({newVert, outsideVert, -1, newFace}); + halfedge_.push_back({outsideVert, endVert, -1, newFace}); + PairUp(newHalfedge + 2, halfedge_[current].pairedHalfedge); + PairUp(newHalfedge + 1, current); + + newHalfedge += 3; + ++newFace; + outsideVert = halfedge_[opposite].startVert; + halfedge_.push_back({newVert, endVert, -1, newFace}); + halfedge_.push_back({endVert, outsideVert, -1, newFace}); + halfedge_.push_back({outsideVert, newVert, -1, newFace}); + PairUp(newHalfedge + 2, halfedge_[opposite].pairedHalfedge); + PairUp(newHalfedge + 1, opposite); + PairUp(newHalfedge, newHalfedge - 3); + + break; + } + + current = halfedge_[NextHalfedge(current)].pairedHalfedge; + } +} + void Manifold::Impl::PairUp(int edge0, int edge1) { halfedge_[edge0].pairedHalfedge = edge1; halfedge_[edge1].pairedHalfedge = edge0; @@ -244,18 +289,6 @@ void Manifold::Impl::RemoveIfFolded(int edge) { } } -void Manifold::Impl::SplitEdge(const int current) { - int startVert = vertPos_.size(); - vertPos_.push_back(vertPos_[halfedge_[current].startVert]); - int endVert = vertPos_.size(); - vertPos_.push_back(vertPos_[halfedge_[current].endVert]); - - int pair = halfedge_[current].pairedHalfedge; - - UpdateVert(startVert, pair, NextHalfedge(NextHalfedge(current))); - UpdateVert(endVert, current, NextHalfedge(NextHalfedge(pair))); -} - void Manifold::Impl::CollapseEdge(const int edge) { VecDH& triBary = meshRelation_.triBary; diff --git a/manifold/src/impl.h b/manifold/src/impl.h index e42fb07d7..a2e9ad395 100644 --- a/manifold/src/impl.h +++ b/manifold/src/impl.h @@ -108,7 +108,7 @@ struct Manifold::Impl { // edge_op.cu void SimplifyTopology(); - void SplitEdge(int edge); + void DedupeEdge(int edge); void CollapseEdge(int edge); void RecursiveEdgeSwap(int edge); void RemoveIfFolded(int edge); diff --git a/manifold/src/properties.cpp b/manifold/src/properties.cpp index e33155fe9..9377ae07f 100644 --- a/manifold/src/properties.cpp +++ b/manifold/src/properties.cpp @@ -219,12 +219,14 @@ bool Manifold::Impl::IsManifold() const { auto policy = autoPolicy(halfedge_.size()); bool isManifold = all_of(policy, countAt(0), countAt(halfedge_.size()), CheckManifold({halfedge_.cptrD()})); + // std::cout << (isManifold ? "" : "Not ") << "Manifold" << std::endl; VecDH halfedge(halfedge_); sort(policy, halfedge.begin(), halfedge.end()); - isManifold &= all_of(policy, countAt(0), countAt(2 * NumEdge() - 1), - NoDuplicates({halfedge.cptrD()})); - return isManifold; + bool noDupes = all_of(policy, countAt(0), countAt(2 * NumEdge() - 1), + NoDuplicates({halfedge.cptrD()})); + // std::cout << (noDupes ? "" : "Not ") << "2-Manifold" << std::endl; + return isManifold && noDupes; } /** diff --git a/test/mesh_test.cpp b/test/mesh_test.cpp index 29f6b4beb..29041c309 100644 --- a/test/mesh_test.cpp +++ b/test/mesh_test.cpp @@ -862,8 +862,6 @@ TEST(Boolean, Cylinders) { } m2 += Manifold(rod).Transform(mat); } - // ExportMesh("m2a.glb", m2.GetMesh(), {}); - std::cout << "union 3" << std::endl; m1 += m2; EXPECT_TRUE(m1.IsManifold()); From 1da7f6a75bed57430482186c4b3a14adbc44c941 Mon Sep 17 00:00:00 2001 From: Emmett Lalish Date: Sun, 5 Jun 2022 12:36:34 -0700 Subject: [PATCH 5/6] added another test --- manifold/src/edge_op.cpp | 5 +++++ test/mesh_test.cpp | 15 +++++++++++++++ 2 files changed, 20 insertions(+) diff --git a/manifold/src/edge_op.cpp b/manifold/src/edge_op.cpp index f70e508d8..bd1b44e80 100644 --- a/manifold/src/edge_op.cpp +++ b/manifold/src/edge_op.cpp @@ -121,6 +121,11 @@ namespace manifold { * It also performs edge swaps on the long edges of degenerate triangles, though * there are some configurations of degenerates that cannot be removed this way. * + * Before collapsing edges, the mesh is checked for duplicate edges (more than + * one pair of triangles sharing the same edge), which are removed by + * duplicating one vert and adding two triangles. These degenerate triangles are + * likely to be collapsed again in the subsequent simplification. + * * Note when an edge collapse would result in something non-manifold, the * vertices are duplicated in such a way as to remove handles or separate * meshes, thus decreasing the Genus(). It only increases when meshes that have diff --git a/test/mesh_test.cpp b/test/mesh_test.cpp index 29041c309..218257ee4 100644 --- a/test/mesh_test.cpp +++ b/test/mesh_test.cpp @@ -868,3 +868,18 @@ TEST(Boolean, Cylinders) { EXPECT_TRUE(m1.MatchesTriNormals()); EXPECT_LE(m1.NumDegenerateTris(), 12); } + +TEST(Boolean, Cubes) { + Manifold result = Manifold::Cube({1.2, 1, 1}, true).Translate({0, -0.5, 0.5}); + result += Manifold::Cube({1, 0.8, 0.5}).Translate({-0.5, 0, 0.5}); + result += Manifold::Cube({1.2, 0.1, 0.5}).Translate({-0.6, -0.1, 0}); + + EXPECT_TRUE(result.IsManifold()); + EXPECT_TRUE(result.MatchesTriNormals()); + EXPECT_LE(result.NumDegenerateTris(), 0); + auto prop = result.GetProperties(); + EXPECT_NEAR(prop.volume, 1.6, 0.001); + EXPECT_NEAR(prop.surfaceArea, 9.2, 0.01); + + if (options.exportModels) ExportMesh("cubes.glb", result.GetMesh(), {}); +} \ No newline at end of file From 7023d2b1b7315e143f720ab6eb1f846f0329eee9 Mon Sep 17 00:00:00 2001 From: Emmett Lalish Date: Sun, 5 Jun 2022 13:03:09 -0700 Subject: [PATCH 6/6] revert early attempt --- manifold/src/edge_op.cpp | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) diff --git a/manifold/src/edge_op.cpp b/manifold/src/edge_op.cpp index bd1b44e80..12b12741c 100644 --- a/manifold/src/edge_op.cpp +++ b/manifold/src/edge_op.cpp @@ -279,14 +279,10 @@ void Manifold::Impl::CollapseTri(const glm::ivec3& triEdge) { } void Manifold::Impl::RemoveIfFolded(int edge) { - const int pair = halfedge_[edge].pairedHalfedge; - if (pair < 0) return; - const glm::ivec3 tri0edge = TriOf(edge); - const glm::ivec3 tri1edge = TriOf(pair); + const glm::ivec3 tri1edge = TriOf(halfedge_[edge].pairedHalfedge); if (halfedge_[tri0edge[1]].endVert == halfedge_[tri1edge[1]].endVert) { for (int i : {0, 1, 2}) { - if (halfedge_[tri0edge[i]].startVert < 0) continue; vertPos_[halfedge_[tri0edge[i]].startVert] = glm::vec3(NAN); halfedge_[tri0edge[i]] = {-1, -1, -1, -1}; halfedge_[tri1edge[i]] = {-1, -1, -1, -1};