Journal
ACM TRANSACTIONS ON GRAPHICS
Volume 40, Issue 2, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3439429
Keywords
Computational design; shape optimization; curves; knots
Categories
Funding
- Packard Fellowship
- NSF [DMS-1439786, 1717320, 1943123]
- German Academic Exchange Service (DAAD)
- German Research Foundation (DFG) [282535003]
- Sloan award [G-2019-11406]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1717320] Funding Source: National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [1943123] Funding Source: National Science Foundation
Ask authors/readers for more resources
The article introduces efficient algorithms for repulsion of plane and space curves, preventing crossings and self-intersections. By utilizing tangent-point energy and gradient descent, rapid progress towards shape optimization and cost reduction can be achieved.
Curves play a fundamental role across computer graphics, physical simulation, and mathematical visualization, yet most tools for curve design do nothing to prevent crossings or self-intersections. This article develops efficient algorithms for (self-)repulsion of plane and space curves that are well-suited to problems in computational design. Our starting point is the so-called tangent-point energy, which provides an infinite barrier to self-intersection. In contrast to local collision detection strategies used in, e.g., physical simulation, this energy considers interactions between all pairs of points, and is hence useful for global shape optimization: local minima tend to be aesthetically pleasing, physically valid, and nicely distributed in space. A reformulation of gradient descent based on a Sobolev-Slobodeckij inner product enables us to make rapid progress toward local minima- independent of curve resolution. We also develop a hierarchical multigrid scheme that significantly reduces the per-step cost of optimization. The energy is easily integrated with a variety of constraints and penalties (e.g., inextensibility, or obstacle avoidance), which we use for applications including curve packing, knot untangling, graph embedding, non-crossing spline interpolation, flow visualization, and robotic path planning.
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