Repulsive Curves

ACM Transactions on Graphics, vol. 40, pp. 1–21

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 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 3

1. Chris Yu

   Carnegie Mellon University

   Affiliation as printed

   Carnegie Mellon University, Pittsburgh, PA

2. H. Ralph Schumacher Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

3. Keenan Crane

   Carnegie Mellon University

   Affiliation as printed

   Carnegie Mellon University, Pittsburgh, PA