Skip to content
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.

Already on GitHub? Sign in to your account

Jump to bottom

Triangulation algorithm can eliminate segments that are part of the face's boundary #60

Closed
hannobraun opened this issue Jan 20, 2022 · 0 comments · Fixed by #81
Closed

Triangulation algorithm can eliminate segments that are part of the face's boundary #60

hannobraun opened this issue Jan 20, 2022 · 0 comments · Fixed by #81
Assignees
@hannobraun
Labels
topic: core Issues relating to core geometry, operations, algorithms type: bug Something isn't working
Milestone
Straight edges, f...

Comments

@hannobraun
Copy link
Owner

The triangulation algorithm first runs a Delaunay triangulation, then filters out triangles that are not part of the face. It does this by running a point-in-polygon check of triangle edges, but it should never run this check for triangle edges that were generated directly from the face's edges.

triangulation-failure

This is debug output from a 2D version of the star model. It shows checks for face edges (marked blue), as well as one where there shouldn't even be a triangle edge (marked yellow).

I'm looking into it.
@hannobraun hannobraun added type: bug Something isn't working topic: core Issues relating to core geometry, operations, algorithms labels Jan 20, 2022
@hannobraun hannobraun self-assigned this Jan 20, 2022
@hannobraun hannobraun mentioned this issue Jan 20, 2022
Merged
@hannobraun hannobraun changed the title Triangulation algorithm can eliminate segments that are part of the model's edge Triangulation algorithm can eliminate segments that are part of the model's boundary Jan 21, 2022
@hannobraun hannobraun changed the title Triangulation algorithm can eliminate segments that are part of the model's boundary Triangulation algorithm can eliminate segments that are part of the face's boundary Jan 21, 2022
hannobraun added a commit that referenced this issue Jan 21, 2022
@hannobraun
Fix deduplication of approximate vertices
1e64e80 
This is a fix for one weird effect that was observed in #60 (a
point-in-polygon test being made for a vertex it shouldn't be made for),
but leaves the main issue unfixed.
@hannobraun hannobraun mentioned this issue Jan 21, 2022
Merged
hannobraun added a commit that referenced this issue Jan 25, 2022
@hannobraun
Fix floating point accuracy issue in triangulation
5dcbdfc 
Close #60
@hannobraun hannobraun mentioned this issue Jan 25, 2022
Merged
hannobraun added a commit that referenced this issue Jan 25, 2022
@hannobraun
Fix floating point accuracy issue in triangulation
7b81aa1 
Close #60
hannobraun added a commit that referenced this issue Feb 4, 2022
@hannobraun
Remove workaround in triangulation code
58c9f8d 
I'm not sure what made this workaround unnecessary, but one of the
recent clean-ups must have done it. All I know is, I can't tell why it
would be necessary with the current code, and the star model, which
previously exposed the bug this workaround fixes (#60) works without any
problems now.
@hannobraun hannobraun mentioned this issue Feb 4, 2022
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@hannobraun hannobraun

Labels
topic: core Issues relating to core geometry, operations, algorithms type: bug Something isn't working
Projects
None yet
Milestone
Straight edges, flat faces, simple sk...
Development

Successfully merging a pull request may close this issue.

Fix floating point accuracy issue in triangulation hannobraun/fornjot
1 participant
@hannobraun