From 6db130eca7f114d364d94ba7b245d4f26addd165 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Fri, 21 Feb 2025 17:16:50 +0800 Subject: [PATCH 1/8] kdtree --- src/polygon.cpp | 78 ++++++++--------------- src/twodtree.h | 166 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 194 insertions(+), 50 deletions(-) create mode 100644 src/twodtree.h diff --git a/src/polygon.cpp b/src/polygon.cpp index f092785b8..85e19fcaf 100644 --- a/src/polygon.cpp +++ b/src/polygon.cpp @@ -20,6 +20,7 @@ #include "./collider.h" #include "./parallel.h" +#include "./twodtree.h" #include "./utils.h" #include "manifold/optional_assert.h" @@ -218,6 +219,11 @@ std::vector TriangulateConvex(const PolygonsIdx &polys) { return triangles; } +struct PointWrapper { + vec2 pt; + size_t idx; +}; + /** * Ear-clipping triangulator based on David Eberly's approach from Geometric * Tools, but adjusted to handle epsilon-valid polygons, and including a @@ -306,9 +312,8 @@ class EarClip { double epsilon_; struct IdxCollider { - Collider collider; + Vec points; std::vector itr; - SparseIndices ind; }; // A circularly-linked list representing the polygon(s) that still need to be @@ -502,32 +507,24 @@ class EarClip { return totalCost; } - Box earBox = Box{vec3(center.x - radius, center.y - radius, 0), - vec3(center.x + radius, center.y + radius, 0)}; - earBox.Union(vec3(pos, 0)); - collider.collider.Collisions(VecView(&earBox, 1), - collider.ind); + Rect earBox = Rect(vec2(center.x - radius, center.y - radius), + vec2(center.x + radius, center.y + radius)); + earBox.Union(pos); const int lid = left->mesh_idx; const int rid = right->mesh_idx; - - totalCost = transform_reduce( - countAt(0), countAt(collider.ind.size()), totalCost, - [](double a, double b) { return std::max(a, b); }, - [&](size_t i) { - const VertItr test = collider.itr[collider.ind.Get(i, true)]; - if (!Clipped(test) && test->mesh_idx != mesh_idx && - test->mesh_idx != lid && - test->mesh_idx != rid) { // Skip duplicated verts - double cost = Cost(test, openSide, epsilon); - if (cost < -epsilon) { - cost = DelaunayCost(test->pos - center, scale, epsilon); - } - return cost; - } - return std::numeric_limits::lowest(); - }); - collider.ind.Clear(); + QueryTwoDTree(collider.points, earBox, [&](PointWrapper point) { + const VertItr test = collider.itr[point.idx]; + if (!Clipped(test) && test->mesh_idx != mesh_idx && + test->mesh_idx != lid && + test->mesh_idx != rid) { // Skip duplicated verts + double cost = Cost(test, openSide, epsilon); + if (cost < -epsilon) { + cost = DelaunayCost(test->pos - center, scale, epsilon); + } + if (cost > totalCost) totalCost = cost; + } + }); return totalCost; } @@ -836,35 +833,16 @@ class EarClip { // epsilon_. Each ear uses this BVH to quickly find a subset of vertices to // check for cost. IdxCollider VertCollider(VertItr start) const { - Vec vertBox; - Vec vertMorton; + ZoneScoped; std::vector itr; - const Box box(vec3(bBox_.min, 0), vec3(bBox_.max, 0)); - - Loop(start, [&vertBox, &vertMorton, &itr, &box, this](VertItr v) { + Vec points; + Loop(start, [&itr, &points, this](VertItr v) { + points.push_back({v->pos, itr.size()}); itr.push_back(v); - const vec3 pos(v->pos, 0); - vertBox.push_back({pos - epsilon_, pos + epsilon_}); - vertMorton.push_back(Collider::MortonCode(pos, box)); }); - if (itr.empty()) { - return {Collider(), itr, {}}; - } - - const int numVert = itr.size(); - Vec vertNew2Old(numVert); - sequence(vertNew2Old.begin(), vertNew2Old.end()); - - stable_sort(vertNew2Old.begin(), vertNew2Old.end(), - [&vertMorton](const int a, const int b) { - return vertMorton[a] < vertMorton[b]; - }); - Permute(vertMorton, vertNew2Old); - Permute(vertBox, vertNew2Old); - Permute(itr, vertNew2Old); - - return {Collider(vertBox, vertMorton), itr, {}}; + BuildTwoDTree(points); + return {std::move(points), std::move(itr)}; } // The main ear-clipping loop. This is called once for each simple polygon - diff --git a/src/twodtree.h b/src/twodtree.h new file mode 100644 index 000000000..9b05d2596 --- /dev/null +++ b/src/twodtree.h @@ -0,0 +1,166 @@ +// Copyright 2025 The Manifold Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#pragma once + +#include + +#include "./utils.h" +#include "manifold/common.h" +#include "manifold/optional_assert.h" +#include "manifold/vec_view.h" + +namespace manifold { + +template +void BuildTwoDTreeImpl(VecView

points) { + std::sort(points.begin(), points.end(), [](const P& a, const P& b) { + return sortX ? a.pt.x < b.pt.x : a.pt.y < b.pt.y; + }); + if (points.size() < 2) return; + BuildTwoDTreeImpl(points.view(0, points.size() / 2)); + BuildTwoDTreeImpl(points.view(points.size() / 2 + 1)); +} + +// Not really a proper KD-tree, but a kd tree with k = 2 and alternating x/y +// partition. +// Recursive sorting is not the most efficient, but simple and guaranteed to +// result in a balanced tree. +// +// Make it multiway... +template +void BuildTwoDTree(VecView

points) { + ZoneScoped; + // don't even bother... + if (points.size() <= 8) return; + BuildTwoDTreeImpl(points); +} + +template +void QueryTwoDTree(VecView

points, Rect r, F f) { + ZoneScoped; + if (points.size() <= 8) { + for (const auto& p : points) + if (r.Contains(p.pt)) f(p); + return; + } + Rect current; + current.min = vec2(-std::numeric_limits::infinity()); + current.max = vec2(std::numeric_limits::infinity()); + + int level = 0; + VecView

currentView = points; + std::array rectStack; + std::array, 64> viewStack; + std::array levelStack; + int stackPointer = 0; + + while (1) { + if (currentView.size() <= 2) { + for (const auto& p : currentView) + if (r.Contains(p.pt)) f(p); + if (--stackPointer < 0) break; + level = levelStack[stackPointer]; + currentView = viewStack[stackPointer]; + current = rectStack[stackPointer]; + continue; + } + + // these are conceptual left/right trees + Rect left = current; + Rect right = current; + const P middle = currentView[currentView.size() / 2]; + if (level % 2 == 0) + left.max.x = right.min.x = middle.pt.x; + else + left.max.y = right.min.y = middle.pt.y; + + if (r.Contains(middle.pt)) f(middle); + if (left.DoesOverlap(r)) { + if (right.DoesOverlap(r)) { + DEBUG_ASSERT(stackPointer < 64, logicErr, "Stack overflow"); + rectStack[stackPointer] = right; + viewStack[stackPointer] = currentView.view(currentView.size() / 2 + 1); + levelStack[stackPointer] = level + 1; + stackPointer++; + } + current = left; + currentView = currentView.view(0, currentView.size() / 2); + level++; + } else { + current = right; + currentView = currentView.view(currentView.size() / 2 + 1); + level++; + } + } +} + +template +void VerifyTwoDTree(VecView

points) { + Rect current; + current.min = vec2(-std::numeric_limits::infinity()); + current.max = vec2(std::numeric_limits::infinity()); + + int level = 0; + VecView

currentView = points; + std::array rectStack; + std::array, 64> viewStack; + std::array levelStack; + int stackPointer = 0; + + while (1) { + if (currentView.size() <= 2) { + if (--stackPointer < 0) break; + level = levelStack[stackPointer]; + currentView = viewStack[stackPointer]; + current = rectStack[stackPointer]; + continue; + } + + Rect left = current; + Rect right = current; + const P middle = currentView[currentView.size() / 2]; + if (level % 2 == 0) + left.max.x = right.min.x = middle.pt.x; + else + left.max.y = right.min.y = middle.pt.y; + + DEBUG_ASSERT(stackPointer < 64, logicErr, "Stack overflow"); + + DEBUG_ASSERT( + std::all_of(currentView.begin(), + currentView.begin() + (currentView.size() / 2), + [&left](const P& p) { return left.Contains(p.pt); }), + logicErr, "Left tree contains invalid point"); + if (!std::all_of(currentView.begin() + (currentView.size() / 2 + 1), + currentView.end(), + [&right](const P& p) { return right.Contains(p.pt); })) { + printf("level = %d, length = %ld\n", level, currentView.size()); + } + DEBUG_ASSERT( + std::all_of(currentView.begin() + (currentView.size() / 2 + 1), + currentView.end(), + [&right](const P& p) { return right.Contains(p.pt); }), + logicErr, "Right tree contains invalid point"); + + rectStack[stackPointer] = right; + viewStack[stackPointer] = currentView.view(currentView.size() / 2 + 1); + levelStack[stackPointer] = level + 1; + stackPointer++; + current = left; + currentView = currentView.view(0, currentView.size() / 2); + level++; + } +} +} // namespace manifold From 8d046ba27900992dc7f8eca96c324eb6fb04d261 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 00:56:52 +0800 Subject: [PATCH 2/8] remove verify code --- src/twodtree.h | 58 -------------------------------------------------- 1 file changed, 58 deletions(-) diff --git a/src/twodtree.h b/src/twodtree.h index 9b05d2596..6203e942d 100644 --- a/src/twodtree.h +++ b/src/twodtree.h @@ -105,62 +105,4 @@ void QueryTwoDTree(VecView

points, Rect r, F f) { } } } - -template -void VerifyTwoDTree(VecView

points) { - Rect current; - current.min = vec2(-std::numeric_limits::infinity()); - current.max = vec2(std::numeric_limits::infinity()); - - int level = 0; - VecView

currentView = points; - std::array rectStack; - std::array, 64> viewStack; - std::array levelStack; - int stackPointer = 0; - - while (1) { - if (currentView.size() <= 2) { - if (--stackPointer < 0) break; - level = levelStack[stackPointer]; - currentView = viewStack[stackPointer]; - current = rectStack[stackPointer]; - continue; - } - - Rect left = current; - Rect right = current; - const P middle = currentView[currentView.size() / 2]; - if (level % 2 == 0) - left.max.x = right.min.x = middle.pt.x; - else - left.max.y = right.min.y = middle.pt.y; - - DEBUG_ASSERT(stackPointer < 64, logicErr, "Stack overflow"); - - DEBUG_ASSERT( - std::all_of(currentView.begin(), - currentView.begin() + (currentView.size() / 2), - [&left](const P& p) { return left.Contains(p.pt); }), - logicErr, "Left tree contains invalid point"); - if (!std::all_of(currentView.begin() + (currentView.size() / 2 + 1), - currentView.end(), - [&right](const P& p) { return right.Contains(p.pt); })) { - printf("level = %d, length = %ld\n", level, currentView.size()); - } - DEBUG_ASSERT( - std::all_of(currentView.begin() + (currentView.size() / 2 + 1), - currentView.end(), - [&right](const P& p) { return right.Contains(p.pt); }), - logicErr, "Right tree contains invalid point"); - - rectStack[stackPointer] = right; - viewStack[stackPointer] = currentView.view(currentView.size() / 2 + 1); - levelStack[stackPointer] = level + 1; - stackPointer++; - current = left; - currentView = currentView.view(0, currentView.size() / 2); - level++; - } -} } // namespace manifold From 1b511bd146868cfef7e62918f49742b1bea6a745 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 23:19:25 +0800 Subject: [PATCH 3/8] address comments --- src/CMakeLists.txt | 2 ++ src/polygon.cpp | 15 ++++------- src/tree2d.cpp | 45 +++++++++++++++++++++++++++++++++ src/{twodtree.h => tree2d.h} | 49 ++++++++++-------------------------- 4 files changed, 65 insertions(+), 46 deletions(-) create mode 100644 src/tree2d.cpp rename src/{twodtree.h => tree2d.h} (61%) diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 2dff72d90..131b56336 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -29,6 +29,7 @@ set( smoothing.cpp sort.cpp subdivision.cpp + tree2d.cpp # optional source files $<$:cross_section/cross_section.cpp> $<$:meshIO/meshIO.cpp> @@ -48,6 +49,7 @@ set( shared.h sparse.h svd.h + tree2d.h tri_dist.h utils.h vec.h diff --git a/src/polygon.cpp b/src/polygon.cpp index 85e19fcaf..226883898 100644 --- a/src/polygon.cpp +++ b/src/polygon.cpp @@ -20,7 +20,7 @@ #include "./collider.h" #include "./parallel.h" -#include "./twodtree.h" +#include "./tree2d.h" #include "./utils.h" #include "manifold/optional_assert.h" @@ -219,11 +219,6 @@ std::vector TriangulateConvex(const PolygonsIdx &polys) { return triangles; } -struct PointWrapper { - vec2 pt; - size_t idx; -}; - /** * Ear-clipping triangulator based on David Eberly's approach from Geometric * Tools, but adjusted to handle epsilon-valid polygons, and including a @@ -312,7 +307,7 @@ class EarClip { double epsilon_; struct IdxCollider { - Vec points; + Vec points; std::vector itr; }; @@ -513,7 +508,7 @@ class EarClip { const int lid = left->mesh_idx; const int rid = right->mesh_idx; - QueryTwoDTree(collider.points, earBox, [&](PointWrapper point) { + QueryTwoDTree(collider.points, earBox, [&](PolyVert point) { const VertItr test = collider.itr[point.idx]; if (!Clipped(test) && test->mesh_idx != mesh_idx && test->mesh_idx != lid && @@ -835,9 +830,9 @@ class EarClip { IdxCollider VertCollider(VertItr start) const { ZoneScoped; std::vector itr; - Vec points; + Vec points; Loop(start, [&itr, &points, this](VertItr v) { - points.push_back({v->pos, itr.size()}); + points.push_back({v->pos, static_cast(itr.size())}); itr.push_back(v); }); diff --git a/src/tree2d.cpp b/src/tree2d.cpp new file mode 100644 index 000000000..9ba97dbf4 --- /dev/null +++ b/src/tree2d.cpp @@ -0,0 +1,45 @@ +// Copyright 2025 The Manifold Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "tree2d.h" + +#include "./parallel.h" +#include "./utils.h" + +namespace manifold { + +// Not really a proper KD-tree, but a kd tree with k = 2 and alternating x/y +// partition. +// Recursive sorting is not the most efficient, but simple and guaranteed to +// result in a balanced tree. +void BuildTwoDTreeImpl(VecView points, bool sortX) { + auto cmpx = [](const PolyVert& a, const PolyVert& b) { + return a.pos.x < b.pos.x; + }; + auto cmpy = [](const PolyVert& a, const PolyVert& b) { + return a.pos.y < b.pos.y; + }; + stable_sort(points.begin(), points.end(), sortX ? cmpx : cmpy); + if (points.size() < 2) return; + BuildTwoDTreeImpl(points.view(0, points.size() / 2), !sortX); + BuildTwoDTreeImpl(points.view(points.size() / 2 + 1), !sortX); +} + +void BuildTwoDTree(VecView points) { + ZoneScoped; + // don't even bother... + if (points.size() <= 8) return; + BuildTwoDTreeImpl(points, true); +} +} // namespace manifold diff --git a/src/twodtree.h b/src/tree2d.h similarity index 61% rename from src/twodtree.h rename to src/tree2d.h index 6203e942d..d16b2ab3e 100644 --- a/src/twodtree.h +++ b/src/tree2d.h @@ -14,45 +14,22 @@ #pragma once -#include - -#include "./utils.h" #include "manifold/common.h" #include "manifold/optional_assert.h" +#include "manifold/polygon.h" #include "manifold/vec_view.h" namespace manifold { -template -void BuildTwoDTreeImpl(VecView

points) { - std::sort(points.begin(), points.end(), [](const P& a, const P& b) { - return sortX ? a.pt.x < b.pt.x : a.pt.y < b.pt.y; - }); - if (points.size() < 2) return; - BuildTwoDTreeImpl(points.view(0, points.size() / 2)); - BuildTwoDTreeImpl(points.view(points.size() / 2 + 1)); -} +void BuildTwoDTreeImpl(VecView points, bool sortX); -// Not really a proper KD-tree, but a kd tree with k = 2 and alternating x/y -// partition. -// Recursive sorting is not the most efficient, but simple and guaranteed to -// result in a balanced tree. -// -// Make it multiway... -template -void BuildTwoDTree(VecView

points) { - ZoneScoped; - // don't even bother... - if (points.size() <= 8) return; - BuildTwoDTreeImpl(points); -} +void BuildTwoDTree(VecView points); -template -void QueryTwoDTree(VecView

points, Rect r, F f) { - ZoneScoped; +template +void QueryTwoDTree(VecView points, Rect r, F f) { if (points.size() <= 8) { for (const auto& p : points) - if (r.Contains(p.pt)) f(p); + if (r.Contains(p.pos)) f(p); return; } Rect current; @@ -60,16 +37,16 @@ void QueryTwoDTree(VecView

points, Rect r, F f) { current.max = vec2(std::numeric_limits::infinity()); int level = 0; - VecView

currentView = points; + VecView currentView = points; std::array rectStack; - std::array, 64> viewStack; + std::array, 64> viewStack; std::array levelStack; int stackPointer = 0; while (1) { if (currentView.size() <= 2) { for (const auto& p : currentView) - if (r.Contains(p.pt)) f(p); + if (r.Contains(p.pos)) f(p); if (--stackPointer < 0) break; level = levelStack[stackPointer]; currentView = viewStack[stackPointer]; @@ -80,13 +57,13 @@ void QueryTwoDTree(VecView

points, Rect r, F f) { // these are conceptual left/right trees Rect left = current; Rect right = current; - const P middle = currentView[currentView.size() / 2]; + const PolyVert middle = currentView[currentView.size() / 2]; if (level % 2 == 0) - left.max.x = right.min.x = middle.pt.x; + left.max.x = right.min.x = middle.pos.x; else - left.max.y = right.min.y = middle.pt.y; + left.max.y = right.min.y = middle.pos.y; - if (r.Contains(middle.pt)) f(middle); + if (r.Contains(middle.pos)) f(middle); if (left.DoesOverlap(r)) { if (right.DoesOverlap(r)) { DEBUG_ASSERT(stackPointer < 64, logicErr, "Stack overflow"); From b66e1d6ad0bba5d55cbc8da96dbcbc78e2c36571 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 23:19:40 +0800 Subject: [PATCH 4/8] try to add the CI failing case --- test/polygons/polygon_corpus.txt | 25 ++++++++++++++++++++++++- 1 file changed, 24 insertions(+), 1 deletion(-) diff --git a/test/polygons/polygon_corpus.txt b/test/polygons/polygon_corpus.txt index a11a637e1..9d7fac881 100644 --- a/test/polygons/polygon_corpus.txt +++ b/test/polygons/polygon_corpus.txt @@ -1670,4 +1670,27 @@ Very_Branchy_With_hole 35 -1.0 2 3 -61.065936 242.624693 -59.65022 241.08199 --61.482003 240.77002 \ No newline at end of file +-61.482003 240.77002 +CondensedMatter64 19 2.30642e-11 1 +21 +-0.068422 9.67994 +0.0112535 9.6809 +0.00513979 9.69041 +0.00513979 9.69041 +0.00513979 9.69041 +0.00782256 9.68428 +-0.068422 9.67994 +-0.0120512 9.69438 +-0.0120512 9.69438 +-0.0120512 9.69438 +-0.0246183 9.69901 +-0.0246183 9.69901 +-0.0366197 9.70488 +-0.0366197 9.70488 +-0.0441664 9.70959 +-0.068422 9.67994 +-0.0493803 9.71306 +-0.053702 9.71642 +-0.068422 9.67994 +-0.068422 9.67994 +-0.068422 9.67994 From 9cd9933c394d1650c558ebfd15148d77da4b2108 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 23:29:40 +0800 Subject: [PATCH 5/8] fix build --- src/tree2d.cpp | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/src/tree2d.cpp b/src/tree2d.cpp index 9ba97dbf4..04a500505 100644 --- a/src/tree2d.cpp +++ b/src/tree2d.cpp @@ -24,13 +24,14 @@ namespace manifold { // Recursive sorting is not the most efficient, but simple and guaranteed to // result in a balanced tree. void BuildTwoDTreeImpl(VecView points, bool sortX) { - auto cmpx = [](const PolyVert& a, const PolyVert& b) { + using CmpFn = std::function; + CmpFn cmpx = [](const PolyVert& a, const PolyVert& b) { return a.pos.x < b.pos.x; }; - auto cmpy = [](const PolyVert& a, const PolyVert& b) { + CmpFn cmpy = [](const PolyVert& a, const PolyVert& b) { return a.pos.y < b.pos.y; }; - stable_sort(points.begin(), points.end(), sortX ? cmpx : cmpy); + manifold::stable_sort(points.begin(), points.end(), sortX ? cmpx : cmpy); if (points.size() < 2) return; BuildTwoDTreeImpl(points.view(0, points.size() / 2), !sortX); BuildTwoDTreeImpl(points.view(points.size() / 2 + 1), !sortX); From 61523f10a75746427ab23f19a2fe636795cd46b7 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 23:31:02 +0800 Subject: [PATCH 6/8] set precision --- src/polygon.cpp | 1 + 1 file changed, 1 insertion(+) diff --git a/src/polygon.cpp b/src/polygon.cpp index 226883898..9584c1cbb 100644 --- a/src/polygon.cpp +++ b/src/polygon.cpp @@ -144,6 +144,7 @@ void Dump(const PolygonsIdx &polys, double epsilon) { void PrintFailure(const std::exception &e, const PolygonsIdx &polys, std::vector &triangles, double epsilon) { + std::cout << std::setprecision(16);; std::cout << "-----------------------------------" << std::endl; std::cout << "Triangulation failed! Precision = " << epsilon << std::endl; std::cout << e.what() << std::endl; From d621cb522a6ff3737078b305fa36e538b32f7bcd Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 23:31:47 +0800 Subject: [PATCH 7/8] format --- src/polygon.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/polygon.cpp b/src/polygon.cpp index 9584c1cbb..57b9eaddd 100644 --- a/src/polygon.cpp +++ b/src/polygon.cpp @@ -144,7 +144,8 @@ void Dump(const PolygonsIdx &polys, double epsilon) { void PrintFailure(const std::exception &e, const PolygonsIdx &polys, std::vector &triangles, double epsilon) { - std::cout << std::setprecision(16);; + std::cout << std::setprecision(16); + ; std::cout << "-----------------------------------" << std::endl; std::cout << "Triangulation failed! Precision = " << epsilon << std::endl; std::cout << e.what() << std::endl; From fc20d1f17f77c8f0cecf34d7072d8bf708504b80 Mon Sep 17 00:00:00 2001 From: pca006132 Date: Sat, 22 Feb 2025 23:40:13 +0800 Subject: [PATCH 8/8] fix --- src/polygon.cpp | 4 +-- test/polygons/polygon_corpus.txt | 42 ++++++++++++++++---------------- 2 files changed, 23 insertions(+), 23 deletions(-) diff --git a/src/polygon.cpp b/src/polygon.cpp index 57b9eaddd..ea7e1077e 100644 --- a/src/polygon.cpp +++ b/src/polygon.cpp @@ -18,7 +18,6 @@ #include #include -#include "./collider.h" #include "./parallel.h" #include "./tree2d.h" #include "./utils.h" @@ -145,7 +144,6 @@ void Dump(const PolygonsIdx &polys, double epsilon) { void PrintFailure(const std::exception &e, const PolygonsIdx &polys, std::vector &triangles, double epsilon) { std::cout << std::setprecision(16); - ; std::cout << "-----------------------------------" << std::endl; std::cout << "Triangulation failed! Precision = " << epsilon << std::endl; std::cout << e.what() << std::endl; @@ -507,6 +505,8 @@ class EarClip { Rect earBox = Rect(vec2(center.x - radius, center.y - radius), vec2(center.x + radius, center.y + radius)); earBox.Union(pos); + earBox.min -= epsilon; + earBox.max += epsilon; const int lid = left->mesh_idx; const int rid = right->mesh_idx; diff --git a/test/polygons/polygon_corpus.txt b/test/polygons/polygon_corpus.txt index 9d7fac881..377e00238 100644 --- a/test/polygons/polygon_corpus.txt +++ b/test/polygons/polygon_corpus.txt @@ -1673,24 +1673,24 @@ Very_Branchy_With_hole 35 -1.0 2 -61.482003 240.77002 CondensedMatter64 19 2.30642e-11 1 21 --0.068422 9.67994 -0.0112535 9.6809 -0.00513979 9.69041 -0.00513979 9.69041 -0.00513979 9.69041 -0.00782256 9.68428 --0.068422 9.67994 --0.0120512 9.69438 --0.0120512 9.69438 --0.0120512 9.69438 --0.0246183 9.69901 --0.0246183 9.69901 --0.0366197 9.70488 --0.0366197 9.70488 --0.0441664 9.70959 --0.068422 9.67994 --0.0493803 9.71306 --0.053702 9.71642 --0.068422 9.67994 --0.068422 9.67994 --0.068422 9.67994 +-0.06842195833766856 9.679939633804798 +0.01125349940133374 9.680903111806934 +0.005139787287448156 9.690408106108382 +0.005139787287445186 9.690408106108382 +0.005139787287445186 9.690408106108382 +0.007822556637645924 9.684282094785807 +-0.06842195833766818 9.679939633804798 +-0.01205120016400146 9.694378352997491 +-0.01205120016400146 9.694378352997491 +-0.01205120016400146 9.694378352997491 +-0.02461833537677266 9.699006865448419 +-0.02461833537677267 9.699006865448419 +-0.03661970614604192 9.704881022991231 +-0.03661970614604192 9.704881022991231 +-0.04416639052247019 9.709589843848839 +-0.06842195833766818 9.679939633804798 +-0.04938028753596506 9.713063939287069 +-0.05370195201180676 9.716422994315348 +-0.06842195833766776 9.6799396338048 +-0.06842195833766818 9.679939633804798 +-0.06842195833766825 9.679939633804798