基于Delaunay三角剖分的球体Voronoi图采样方法

《Computers & Graphics》：Delaunay triangulation-based sampling approach for the Voronoi diagram of spheres

　　•一种基于四球接触模型的新方法，用于计算球体的Voronoi图。•一种新的自适应采样策略，用于确定球体的邻域。•一种能够捕捉Voronoi图拓扑结构的定向面数据结构。•一个能够处理非常规球体配置及相交球体的框架。

引言
给定一组几何对象O={oi∣i=1,2,…,n}，对象oi的Voronoi单元（VC）是指所有距离oi比距离集合中其他任何对象oj（j≠i）都更近的点的集合。Voronoi图（VD）则是集合中所有对象的Voronoi单元的集合。为便于解释，在本文的其余部分，我们将VD视为Voronoi单元的边界元素的集合。VD在多个领域都有应用，包括模型降维、碰撞避免、传感器部署、运动规划、分割、搜索与检索等。球体的VD在结构生物学中也有应用，比如蛋白质路径分析[1]、[2]以及蛋白质空间结构研究[3]，此外还应用于几何建模领域，如隐式表面网络[4]。

一组点的VD由垂直平分线构成。对于一组半径不同且不相交、不重叠的圆，其VD则由双曲线构成（见图1(a)）。在R2空间中，VD由Voronoi顶点（VV）和Voronoi边（VE）组成。显然，“平分线”（即到两个对象距离相等的点的轨迹）在计算VD过程中起着关键作用。实际上，在VD中只有一部分两对象之间的平分线起作用，因此需要大量处理来消除平分线上不必要的部分。例如，对于图1(b)中所示的两个圆之间的平分线，只有绿色的那部分会成为Voronoi图的一部分，因为切线圆T1是空的（仅与圆c1和c2相切，既不包含它们也不与它们相交，见图1(c)）[5]。图中用红色标出的平分线部分则不会被使用。此外，当有更多输入圆时（如图1(d)所示），绿色平分线（图1(c)）中只有一小部分会成为该圆组中的Voronoi边（见图1(d)中的绿色边）。因此，直接使用平分线来计算VD在计算上非常耗费资源。

当两个对象是半径不同的（不相交的）球体时，它们之间的平分线被证明是双叶双曲面（证明见[6]，另见[7]中的表1），如图2所示。对于一组球体，可以利用平分面下的包络来计算Voronoi单元（见图3）[7]、[8]。或者，也可以通过三等分线交点来获得Voronoi顶点，即到三个几何对象距离相等的点的轨迹。不过，这两种方法都计算成本很高。即使获得了Voronoi顶点，还需要进一步处理才能构建图的边和面拓扑结构。这里的边拓扑指的是沿三等分线连接的Voronoi顶点，而面拓扑则指的是平分面及其边界边的排列方式。

除了在R3空间中存在的计算复杂性之外，孤立Voronoi边的存在也带来了进一步挑战[8]。孤立Voronoi边是Voronoi边集中断开的组成部分。几乎所有现有算法都假设不存在这样的孤立边。一种计算球体Voronoi顶点的简单方法会耗费大量时间，因此并不实用。

因此，为数不多的用于计算球体VD的方法大多存在以下一个或多个缺点：(a)无法处理退化情况（强制要求处于一般位置）[3]；(b)需要平分线这种高阶曲面来计算下包络[5]、[8]；(c)无法处理孤立边[3]、[9]。

已有研究表明，无需计算平分线的交点，就可以计算一组曲线的VD[10]。然后可以在识别出的曲线段对之间计算Voronoi边。不过，这种方法仅限于二维空间。我们提出了一种基于接触球的 方法来计算球体的VD。同时，我们还引入了一种基于Delaunay三角剖分的采样策略用于计算邻域信息，以及一种新颖的定向面数据结构。像球心位于平面上的退化情况以及孤立边这类特殊情形仅存在于三维空间中，而我们能够处理这些情况。

因此，在本文中，我们提出了一种算法，通过捕捉Voronoi顶点的拓扑结构来计算一组球体的VD，而不需要使用平分线或三等分线。该方法利用三个接触球的概念，随后通过定向面数据结构形成四个接触球。这种方法也避免了边缘拓扑的识别，但需要面拓扑信息。Voronoi面仅在局部范围内进行计算。所提出的框架能够处理多种非常规和相交的球体配置，包括孤立Voronoi边。不过，某些高度对称的配置以及球体包含关系仍不在当前实现的范围内。本文的主要贡献如下：
•一种基于四球接触模型的新方法，用于计算球体的Voronoi图。
•一种新的自适应采样策略，用于确定球体的邻域。
•一种能够捕捉Voronoi图拓扑结构的定向面数据结构。
•一个能够处理非常规球体配置及相交球体的框架。

前期工作
本节将探讨涉及球体时的VD/平分线相关研究。在[11]中，人们对构造实体几何学中的基本图形的平分线进行了分析。他们指出，球体与CSG基本图形（圆锥、圆柱、球体等）的平分线总是有理曲线。Will [12]则表明，三个球体的三等分线是一条圆锥曲线。这是因为与三个固定球体相切的球体的包络是一个Dupin环面，而三等分线则是这些球心所在的轨迹。

预备知识
设S={si|i=1,2,…,n}表示R3空间中n个处于一般位置、半径各异且互不相交的输入球体，其中si=(ci,ri)，ci为球心坐标(xi,yi,zi)，ri≥0。之后，为了研究处于非一般位置和相交配置下的球体VD，我们将放宽关于一般位置和球体互不相交的假设。

定义1
对于S中的每个球体si，其Voronoi单元VCi定义为：
VCi={p∈R3∣‖p?ci‖?ri<‖p?cj‖?rj,?j≠i}。

定义2
Voronoi图VD(S)是……

算法的基本思路
图4展示了如何利用对应于半径函数局部极值的Voronoi球来定义Voronoi边段。为了计算一组球体的VD，需要按照半径从小到大的顺序找出所有这样的Voronoi球，并在此过程中为每条Voronoi边段配对半径最小的球体和半径最大的球体。

处理非一般位置和相交的球体
对于处于非一般位置和相交情况的输入，无需对输入数据进行特殊处理即可应对。图11展示了在退化情况下生成的定向面。在这种情况下，单个接触球与四个球体si、sj、sk和sl相切，从而产生了四个对应的定向面，分别对应于TTBijk、TTBikl、TTBijl和TTBjkl。相比之下，处于一般位置的接触球只对应一个定向面。在非一般位置下，不同的球体组合会形成多个四球接触球；例如，FTBijkl。

Voronoi拓扑的几何实现
一旦完全构建出Voronoi图的拓扑结构——包括所有的Voronoi顶点以及由定向面编码的连接关系——最后的步骤就是在3D空间中计算出相应的几何嵌入。在这一阶段，仅利用从接触球和四球接触球得到的局部信息，为Voronoi边和面分配坐标和网格表示。与通过平分面交点来重建几何形状的传统方法不同，我们的方法……

算法的工作原理
本节通过一个典型配置，说明了算法如何处理四球接触球并确定Voronoi顶点。该示例基于之前关于定向面、接触球和四球接触球的定义。为便于理解，所有输入球体（s1、s2、s3、s4）都被赋予相同的半径，因此形成了平面状的Voronoi面和直线形的Voronoi边。接触球是利用邻域信息计算出来的，然后被插入到列表L中。在示意图中，定向面被表示为三角形，箭头从……延伸出来。

结果与讨论
我们的算法是用C++实现的，同时使用了CGAL[26]来查找中心点和样本点的最近距离。还采用了[27]提出的方法来计算切线圆和切球。通过多种不同的输入配置，展示了该算法处理各种复杂情况的能力，比如非一般位置的情况（图14、图15）、孤立边的情况（图16）、相交球体的情况（图17）、包含5000个球体的情况（图18）等等。

结论
在本文中，我们提出了一种基于自适应采样的新型接触球方法，用于计算球体的Voronoi图。所提出的算法能够在不需要显式计算平分面交点的情况下确定Voronoi顶点和边，从而简化了底层计算过程。该方法无需特殊处理即可处理处于非一般位置和相交配置的输入数据。据我们所知，结合已评估的数据集[28]来看……

CRediT作者贡献说明
Sasinas Alias Haritha Z.A.：概念设计、数据整理、形式分析、研究、方法论、软件开发、验证、可视化、初稿撰写、审稿与编辑。Manoj Kumar Mukundan：概念设计、数据整理、形式分析、方法论、指导监督、验证、可视化、审稿与编辑。Amrisha Srivastava：软件开发。Pradyumnan Raghuveeran：概念设计、软件开发、可视化。Yegneswaran R.V.：软件开发、可视化。

利益冲突声明
作者声明自己没有已知的可能影响本文研究结果的财务利益或个人关系。该作者为本期刊的编委会成员/主编/副主编/特邀编辑，且未参与本文的编辑评审或发表决策过程。

Sasinas Alias Haritha Z.A.|Manoj Kumar Mukundan|Amrisha Srivastava|Pradyumnan Raghuveeran|Yegneswaran R.V.|Ramanathan Muthuganapathy