Dynamic updates to AABB tree; intersection-blocking mesh decimation#2301
Merged
alecjacobson merged 45 commits intomainfrom Oct 14, 2023
Merged
Dynamic updates to AABB tree; intersection-blocking mesh decimation#2301alecjacobson merged 45 commits intomainfrom
alecjacobson merged 45 commits intomainfrom
Conversation
…hts in right ballpark
Merged
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This adds a couple features and bug fixes in pursuit of adding a feature to high-jack the callbacks of
decimateto prevent (new) self-intersections to be made during edge collapses. To do this efficiently, I modified the AABB tree so that leaves could be dynamically updated (roughly following Eric Catto's notes).Along the way I also found some bugs in the
fast_find*functions (intersections with neighbors were ignored). I've added some routines to detect these intersections (approximately! using floating point ; i.e., not exactly like CGAL or with fancy igl::predicate*). The logic in these functions should be reusable so could benefit from abstracting over fancy types/predicates.Added tests and tutorials.
I made this nasty "balloon inflation" mesh to create a high-res input that has no self-intersections but would cause a ton during decimation. The new feature successfully avoids all self-intersections.
-hb.mp4
Since it wraps existing callbacks it can be used with qslim metrics:

Would be cool to extend to a nested cages/progressive hulls type of constraint for cage / level of detail hierarchies. For now, you can at least go all the way down to super coarse with no self intersections:
Using the trivial decimate callbacks, you can kind of use this for self-intersection-free remeshing. Though it'd be much better to just use the dynamic AABB in the same way for a real remesher like Silvia's port of https://github.com/sgsellan/botsch-kobbelt-remesher-libigl
