8000 Fixed backward zebra polygon by elalish · Pull Request #834 · elalish/manifold · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Fixed backward zebra polygon #834

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

8000

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jun 9, 2024
Merged

Fixed backward zebra polygon #834

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
19 changes: 10 additions & 9 deletions src/polygon/src/polygon.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -354,6 +354,13 @@ class EarClip {
return left->InsideEdge(left->right, precision, true);
}

// Subtly different from !IsConvex because IsConvex will return true for
// colinear non-folded verts, while IsReflex will always check until actual
// certainty is determined.
bool IsReflex(float precision) const {
return !left->InsideEdge(left->right, precision, true);
}

// This function is the core of finding a proper place to keyhole. It runs
// on this Vert, which represents the edge from this to right. It returns
// an iterator to the vert to connect to (either this or right) and a bool
Expand All @@ -368,7 +375,8 @@ class EarClip {
std::pair<VertItr, bool> InterpY2X(glm::vec2 start, int onTop,
float precision) const {
const auto none = std::make_pair(left, false);
if (pos.y < start.y && right->pos.y >= start.y) {
if (pos.y < start.y && right->pos.y >= start.y &&
(pos.x > start.x - precision || right->pos.x > start.x - precision)) {
return std::make_pair(left->right, true);
} else if (onTop != 0 && pos.x > start.x - precision &&
pos.y > start.y - precision && pos.y < start.y + precision &&
Expand Down Expand Up @@ -532,13 +540,6 @@ class EarClip {
// triangulations of polygons with holes, due to vert duplication.
triangles_.push_back(
{ear->left->mesh_idx, ear->mesh_idx, ear->right->mesh_idx});
#ifdef MANIFOLD_DEBUG
if (params.verbose) {
std::cout << "output tri: " << ear->mesh_idx << ", "
<< ear->right->mesh_idx << ", " << ear->left->mesh_idx
<< std::endl;
}
#endif
} else {
PRINT("Topological degenerate!");
}
Expand Down Expand Up @@ -704,7 +705,7 @@ class EarClip {
vert->pos.y * above > start->pos.y * above - precision_ &&
(inside > 0 || (inside == 0 && vert->pos.x < best->pos.x)) &&
vert->InsideEdge(edge, precision_, true) &&
!vert->IsConvex(precision_)) {
vert->IsReflex(precision_)) {
if (vert->pos.y > start->pos.y - precision_ &&
vert->pos.y < start->pos.y + precision_) {
if (onTop > 0 && vert->left->pos.x < vert->pos.x &&
Expand Down
12 changes: 5 additions & 7 deletions test/polygon_test.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -56,20 +56,18 @@ Polygons Duplicate(Polygons polys) {
}

void TestPoly(const Polygons &polys, int expectedNumTri,
float precision = -1.0f, bool >) {
float precision = -1.0f) {
PolygonParams().verbose = options.params.verbose;

std::vector<glm::ivec3> triangles;
EXPECT_NO_THROW(triangles = Triangulate(polys, precision));
EXPECT_EQ(triangles.size(), expectedNumTri) << "Basic";

if (!onlyBasic) {
EXPECT_NO_THROW(triangles = Triangulate(Turn180(polys), precision));
EXPECT_EQ(triangles.size(), expectedNumTri) << "Turn 180";
EXPECT_NO_THROW(triangles = Triangulate(Turn180(polys), precision));
EXPECT_EQ(triangles.size(), expectedNumTri) << "Turn 180";

EXPECT_NO_THROW(triangles = Triangulate(Duplicate(polys), precision));
EXPECT_EQ(triangles.size(), 2 * expectedNumTri) << "Duplicate";
}
EXPECT_NO_THROW(triangles = Triangulate(Duplicate(polys), precision));
EXPECT_EQ(triangles.size(), 2 * expectedNumTri) << "Duplicate";

PolygonParams().verbose = false;
}
Expand Down
2 changes: 1 addition & 1 deletion test/zebra.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -62639,7 +62639,7 @@ TEST(Polygon, Zebra) {
{5.59076977, 14.00315}, //
{5.59097004, 14.00315}, //
});
TestPoly(polys, 62597, -1, true);
TestPoly(polys, 62597);
}

TEST(Polygon, Zebra1) {
Expand Down
Loading
0