4.7 Article

To cut or to fill: a global optimization approach to topological simplification

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

Funding

  1. NSF [CCF-1614562, DBI-1759836, CCF-1907612, EF-1921728]
  2. NIH grant [CA233303-1]
  3. 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

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available