Repulsive Curves
Repulsive Curves
复制标题
DOI：
10.1145/3439429
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Christopher Yu;Henrik Schumacher;Keenan Crane
中科院分区：
文献类型：
--
作者：
Christopher Yu;Henrik Schumacher;Keenan Crane
曲线在计算机图形学、物理模拟和数学可视化中发挥着基础作用，但大多数曲线设计工具无法防止交叉或自相交。本文开发了平面和空间曲线（自）排斥的有效算法，非常适合计算设计中的问题。我们的起点是所谓的切点能量，它为自相交提供了无限的障碍。与物理模拟等中使用的局部碰撞检测策略相比，这种能量考虑了所有点对之间的相互作用，因此对于全局形状优化很有用：局部最小值往往美观、物理有效，并且在空间中分布良好。基于 Sobolev-Slobodeckij 内积的梯度下降重新表述使我们能够快速实现局部最小值，而与曲线分辨率无关。我们还开发了一种分层多重网格方案，可显着降低每步优化成本。能量很容易与各种约束和惩罚（例如，不可扩展性或避障）集成，我们将其用于包括曲线打包、结解缠结、图形嵌入、非交叉样条插值、流可视化和机器人路径规划等应用。
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.