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.

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

Validate that coincident HalfEdges refer to same GlobalEdge #1594

Closed
hannobraun opened this issue Feb 16, 2023 · 2 comments · Fixed by #1695
Closed

Validate that coincident HalfEdges refer to same GlobalEdge #1594

hannobraun opened this issue Feb 16, 2023 · 2 comments · Fixed by #1695
Labels
topic: core Issues relating to core geometry, operations, algorithms type: development Work to ease development or maintenance, without direct effect on features or bugs

Comments

@hannobraun
Copy link
Owner

If two HalfEdges are coincident (which happens where two neighboring faces touch), they need to refer to the same GlobalEdge. If they don't, code working with the object graph (like the approximation code) won't know that they are supposed to be the same edge. In the case of the approximation code, this might lead to an invalid triangle mesh being generated. This has been the cause of bugs in the past (#494, #1162).

To make sure that all instances of this bug have been fixed, and that it stays fixed, we need a validation check for this.

@hannobraun hannobraun added type: development Work to ease development or maintenance, without direct effect on features or bugs topic: core Issues relating to core geometry, operations, algorithms labels Feb 16, 2023
@A-Walrus
Copy link
Contributor

How would we check that HalfEdges are coincident? For lines, it seem simple enough, find start and end values (in 3D) and make sure that they are equal up to some epsilon (possibly with the start and end flipped). However this is not enough for more complicated curves, which may meet at the start and end but diverge in the middle.

A simple (but possibly not very elegant) solution would be to sample the curves at various points along them and ensure that they are all within our configurable epsilon.
This sampling rate could also be part of the ValidationConfig. This solution would be very general and work with everything from lines, to circles, to whatever else we have in the future (beziers...)

A-Walrus added a commit to A-Walrus/Fornjot that referenced this issue Mar 19, 2023
Validate whether coincident HalfEdges refer to the same GlobalEdge.
This should resolve: hannobraun#1594. Checks whether they coincide by sampling.
@hannobraun
Copy link
Owner Author

Hey @A-Walrus, I think you're on to something with your idea of sampling, but we can simplify that a bit: Right now, the only kinds of curve that exist are lines and circles, which means that sampling exactly 3 points will always be enough to determine whether two half-edges are coincident.

I suggest not complicating it further, for now. When we get more complicated curves, we need to revisit this, but I think the following will always be true: There will always be a definite number of sampling points that will be enough to determine coincidence of two half-edges, and that number of points will be defined by the curve/surface of the half-edges we compare.

A-Walrus added a commit to A-Walrus/Fornjot that referenced this issue Mar 20, 2023
Validate whether coincident HalfEdges refer to the same GlobalEdge.
This should resolve: hannobraun#1594. Checks whether they coincide by sampling.
A-Walrus added a commit to A-Walrus/Fornjot that referenced this issue Mar 21, 2023
Validate whether coincident HalfEdges refer to the same GlobalEdge.
This should resolve: hannobraun#1594. Checks whether they coincide by sampling.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
topic: core Issues relating to core geometry, operations, algorithms type: development Work to ease development or maintenance, without direct effect on features or bugs
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants