Topological Simplification of Nested Shapes
Topological Simplification of Nested Shapes
复制标题
DOI：
10.1111/cgf.14611
复制
发表时间：
2022-08
影响因子：
2.5
通讯作者：
Dan Zeng;E. Chambers;D. Letscher;T. Ju
中科院分区：
文献类型：
--
作者：
Dan Zeng;E. Chambers;D. Letscher;T. Ju
我们提出了一种用于去除不需要的拓扑特征（例如，岛、手柄、腔），其中每个形状嵌套在下一个形状中。这样的序列可以在自然界中找到，例如多层材料或生长的植物根。现有的拓扑简化方法是针对单个形状设计的，将它们单独应用于序列中的形状可能会失去嵌套属性。我们将嵌套约束简化任务制定为一组候选形状删除（"切割"）和添加（"填充"）的最优标记问题。我们探索了几种优化策略，包括顺序传播标签的贪婪启发式，可证明最优的状态空间搜索算法，以及具有可控复杂度的波束搜索变体。对合成和真实的世界数据的评估表明，我们的方法在降低拓扑复杂性和最小化几何变化方面与单一形状简化方法一样有效，并且还确保了嵌套。此外，波束搜索策略被发现在最优性和效率之间取得了最佳平衡。
We present a method for removing unwanted topological features (e.g., islands, handles, cavities) from a sequence of shapes where each shape is nested in the next. Such sequences can be found in nature, such as a multi‐layered material or a growing plant root. Existing topology simplification methods are designed for single shapes, and applying them independently to shapes in a sequence may lose the nesting property. We formulate the nesting‐constrained simplification task as an optimal labelling problem on a set of candidate shape deletions (“cuts”) and additions (“fills”). We explored several optimization strategies, including a greedy heuristic that sequentially propagates labels, a state‐space search algorithm that is provably optimal, and a beam‐search variant with controllable complexity. Evaluation on synthetic and real‐world data shows that our method is as effective as single‐shape simplification methods in reducing topological complexity and minimizing geometric changes, and it additionally ensures nesting. Also, the beam‐search strategy is found to strike the best balance between optimality and efficiency.