%0 Generic %1 yu2020repulsive %A Yu, Christopher %A Schumacher, Henrik %A Crane, Keenan %D 2020 %K 2020 cmu curve geometry graphics siggraph %T Repulsive Curves %U http://arxiv.org/abs/2006.07859 %X 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 paper 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.

@misc{yu2020repulsive, abstract = {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 paper 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.}, added-at = {2021-03-25T02:36:53.000+0100}, author = {Yu, Christopher and Schumacher, Henrik and Crane, Keenan}, biburl = {https://www.bibsonomy.org/bibtex/2be7b8595c17abdeffd5d9f18e45f4a50/analyst}, description = {[2006.07859] Repulsive Curves}, interhash = {73ff0b5d4172fae7c507f912af3fc375}, intrahash = {be7b8595c17abdeffd5d9f18e45f4a50}, keywords = {2020 cmu curve geometry graphics siggraph}, note = {cite arxiv:2006.07859Comment: 20 pages}, timestamp = {2021-03-25T02:36:53.000+0100}, title = {Repulsive Curves}, url = {http://arxiv.org/abs/2006.07859}, year = 2020 }