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

Dan Zeng, Erin Chambers, David Letscher, Tao Ju

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish
Article number201
JournalACM Transactions on Graphics
Issue number6
StatePublished - Nov 26 2020


  • cell complexes
  • global optimization
  • graph labelling
  • steiner tree
  • topology simplification


Dive into the research topics of 'To cut or to fill: A global optimization approach to topological simplification'. Together they form a unique fingerprint.

Cite this