Browsing by Author "Ju, Tao"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Topological Simplification of Nested Shapes
    (The Eurographics Association and John Wiley & Sons Ltd., 2022) Zeng, Dan; Chambers, Erin; Letscher, David; Ju, Tao; Campen, Marcel; Spagnuolo, Michela
    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.
  • Thumbnail Image
    Item
    Variational Pruning of Medial Axes of Planar Shapes
    (The Eurographics Association and John Wiley & Sons Ltd., 2023) Rong, Peter; Ju, Tao; Memari, Pooran; Solomon, Justin
    Medial axis (MA) is a classical shape descriptor in graphics and vision. The practical utility of MA, however, is hampered by its sensitivity to boundary noise. To prune unwanted branches from MA, many definitions of significance measures over MA have been proposed. However, pruning MA using these measures often comes at the cost of shrinking desirable MA branches and losing shape features at fine scales. We propose a novel significance measure that addresses these shortcomings. Our measure is derived from a variational pruning process, where the goal is to find a connected subset of MA that includes as many points that are as parallel to the shape boundary as possible. We formulate our measure both in the continuous and discrete settings, and present an efficient algorithm on a discrete MA. We demonstrate on many examples that our measure is not only resistant to boundary noise but also excels over existing measures in preventing MA shrinking and recovering features across scales.