Journal
ACM TRANSACTIONS ON GRAPHICS
Volume 39, Issue 6, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3414685.3417854
Keywords
Topology simplification; graph labelling; Steiner tree; cell complexes; global optimization
Categories
Funding
- NSF [CCF-1614562, DBI-1759836, CCF-1907612, EF-1921728]
- NIH grant [CA233303-1]
- Imaging Science Pathway fellowship at Washington University in St. Louis
Ask authors/readers for more resources
We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available