一种拓扑保持的三维模型中值面的简化方法

一种拓扑保持的三维模型中值面的简化方法，包括：(1)寻找三维模型中值面上的拓扑孔洞，即亏格，将孔洞周围的面片标记为拓扑关键区域；(2)使用边折叠方法简化中值面时，对拓扑关键区域中的边在简化前进行拓扑检查，判断该待简化边简化后会否导致相关的孔洞消失，破坏拓扑结构；(3)将中值面的包围盒划分成偶数个分片，对这些分片进行奇/偶交错方式的并行简化处理；对非拓扑关键区域的边，直接折叠简化；对拓扑关键区域中的边，在简化前需要进行步骤(2)中的拓扑检查，若会破坏拓扑则不简化该边，若不会破坏拓扑则简化该边，并将新产生的面片标记为拓扑关键区域。最后将会得到一个拓扑保持的简化中值面。该方法具有拓扑保持、运算速度快、简化误差小的优点。

技术领域

本发明属于计算机图形学和计算机视觉领域，具体涉及一种拓扑保持的中值面简化方法。

背景技术

几何形状的简要表示方法在计算机图形学及几何建模技术中具有重要地位，一直都是研究领域的热点课题。中值面(Medial Surface)作为三维模型的一种简洁表示方法，在模型压缩与近似、模型动画与形变、模型检索与识别等方面具有广泛应用。

三维模型的中值面是指模型内部所有内切球的球心的集合。以这些点为球心的内切球被称为是中值球。中值面以及定义在中值面上描述中值球半径的函数一起构成了中轴变换(MAT,Medial Axis Transform)。任意三维模型都可以利用其中值面进行表示，并能从中轴变换重建恢复出原模型。但是中值面的生成对噪声敏感，易生成许多毛刺，妨碍了其表达的简洁性。因此对中值面进行化简，提高其表达的简洁性，在很多应用中都具有重要意义。

已有的中值面简化方法大致可以分为两类。一类方法将中值面视作中值点的集合，通过定义在中值点上的某种度量的阈值筛选来进行化简[1][2][3]。此类方法在去除毛刺的同时，往往会牺牲几何精度，且会破坏中值面对模型的拓扑表达。另一类方法通常将中值面表示为网格模型，并通过收缩或折叠中值面的边或者面片来进行化简[4][5][6][7]。但是此类方法要么难以保持拓扑，要么注意保持拓扑但所得结果几何误差大或者计算速度很慢。例如基于QEM边折叠框架的简化方法[5][6]，它们通常能得到较好的几何精度，但其依赖于每次简化的拓扑检查来保持拓扑，严重影响了计算效率。

中值面和原模型一致的拓扑结构是其保证很多应用的根本原因。破坏拓扑自然会影响重建模型的拓扑，也就会导致基于中值面抽象表达的应用中出现错误的拓扑改变。因此在简化中值面过程中，如何快速高效地生成一个拓扑保持、几何精度高的简化中值面具有非常重要的价值。

[1]M.Foskey,M.C.Lin,and D.Manocha,“Efficient computation of asimplified medial axis,”Journal of Computing and Information Science inEngineering,vol.3,no.4,pp.274–284,2003.

[2]F.Chazal and A.Lieuer,“Theλ-medial axis,”Graphical Models,vol.67,no.4,pp.304–331,2005.

[3]B.Miklos,J.Giesen,and M.Pauly,“Discrete scale axis representationsfor 3d geometry,”ACM Transactions on Graphics(TOG),vol.29,no.4,p.101,2010.

[4]FARAJ N.,THIERY J.-M.,BOUBEKEUR T.:Progressive medial axisfiltration.In SIGGRAPH Asia 2013Technical Briefs(2013),ACM,p.3

[5]SUN F.,CHOI Y.-K.,YU Y.,WANG W.:Medial meshes—a compact andaccurate representation of medial axis transform.IEEE transactions onvisualization and computer graphics 22,3(2016),1278–1290.

[6]LI P.,WANG B.,SUN F.,GUO X.,ZHANG C.,WANG W.:Q-MAT:Computingmedial axis transform by quadratic error minimization.ACM Transactions onGraphics(TOG)35,1(2015),8.

[7]YAN Y.,SYKES K.,CHAMBERS E.,LETSCHER D.,JU T.:Erosion thickness onmedial axes of 3d shapes.ACM Trans.Graph.35,4(July 2016),38:1–38:12.

发明内容

本发明技术解决问题：模型的近似与压缩、动画与形变、检索与识别等多个应用场景，都需要一个简洁且准确的中值面。因此，本发明旨在解决现有方法在简化中值面的过程中破坏拓扑和计算效率不高的问题。

本发明提出了一种拓扑保持的三维模型中值面的简化方法。该方法通过最小化几何近似误差的边折叠操作来化简中值面，确保化简结果具有良好的几何精度。同时该方法将拓扑检查步骤限制在可能发生拓扑改变的拓扑关键区域(即一次简化处理可能导致拓扑结构发生变化的区域，具体地，在本发明中指一条边的折叠简化处理可能导致其相关的拓扑孔洞消失)，减少了大量不必要的运算，并通过一个并行的处理框架进一步提高化简的效率。

本发明的技术方案如下：一种基于拓扑保持的三维模型中值面的简化方法，包括如下步骤：

(1)寻找三维模型的中值面上的孔洞，即亏格，将中值面上的孔洞周围的面片标记为拓扑关键区域；这些面片的边为关键边，即在简化计算中需要进行拓扑检查的边；

(2)使用边折叠方法简化三维模型的中值面时对拓扑关键区域中的边在简化前进行拓扑检查，如果该待简化边简化后会导致相关的孔洞消失，则该边不进行简化，否则简化该边；

(3)将三维模型的中值面的包围盒划分成偶数个分片，对这些分片进行交错方式的并行简化处理；并在简化拓扑关键区域中的边时，进行步骤(2)中的拓扑检查，得到一个拓扑保持的简化中值面。简化中值面能作为三维模型的简要表达应用于模型压缩与近似、模型动画与形变、模型检索与识别等多个应用场景。

所述步骤(1)中，寻找三维模型中值面上的孔洞，即亏格，将中值面上的孔洞周围的面片标记为拓扑关键区域，具体步骤为：

(11)从三维模型的中值面数据所在坐标系的±x,±y,±z共6个正交方向对中值面进行正投影，得到6个深度图像和6个对应的面片序号图像，面片序号图像记录深度图像中每一个像素在中值面上对应的面片序号；

(12)对深度图像的每一个像素判断该像素与周边像素的深度差；若该差值大于某一阈值则标记该像素为关键像素；

(13)找到每一个关键像素所对应的面片序号，由这些面片构成拓扑关键区域，这些面片的边为关键边，即在简化计算中将需要进行拓扑检查的边。

所述步骤(12)中的某一阈值为中值面上最长边的长度。该阈值设定方法能有效地筛选出深度图像中所属于的中值面面片不相邻的两个相邻像素。也就意味着该位置发生了深度的跃迁，有可能是孔洞的边界。

所述步骤(2)中，对拓扑关键区域中的边在简化前进行拓扑检查的具体步骤为：

(21)遍历该边两个顶点的相邻顶点集合，找到它们的共同相邻顶点；

(22)遍历该边两个顶点的相邻面片集合，找到它们的共同相邻面片；

(23)对每一个共同相邻顶点，判断是否存在一个共同相邻面片包含了该顶点。若所有的共同相邻顶点都存在这样的共同相邻面片，则折叠该边不会破坏拓扑结构；否则，折叠该边会破坏拓扑结构。

所述步骤(3)中，将模型包围盒划分成偶数个分片，对这些分片进行交错方式的并行简化处理的具体步骤为：

(31)将三维模型的包围盒划分成偶数个分片；要求满足分片的宽度大于中值面最大边长的四倍长度；

(32)交错地选择所有奇数序号和所有偶数序号的分片进行并行的简化处理，直至达到简化目标；

(33)在(32)中对一个分片中的中值面进行简化处理时，以边折叠的方式进行，每次找到分片中简化代价最小的边；检查该边是否是关键边，若不是则简化该边，反之则需进行拓扑检查，判断该边的简化会否导致相关孔洞消失；如果会导致相关孔洞消失则不简化该边，若不会导致相关孔洞消失，则简化该边，并将新产生的面片标记为拓扑关键区域，对应的边标记为关键边。

本发明与现有技术相比的优点在于：本发明将边折叠化简过程中的拓扑检查限制在了拓扑关键区域，避免了对所有边折叠进行拓扑检查，大大减少了运算量，加快了简化中值面的速度；同时本发明采用了更为简单直接的拓扑检查方法，并利用并行框架进一步提高化简的效率，能快速地生成拓扑保持、几何精度高的简化中值面，能有效地应用于模型的压缩与近似、动画与形变、检索与识别。

附图说明null实施方式

下面结合附图及实例对本发明进行详细说明。

本发明主要涉及3个步骤：

(1)寻找拓扑孔洞，标记拓扑关键区域：在已有的基于边折叠的中值面简化算法中，对每一条边在折叠时进行拓扑检查是导致算法效率低下的主要原因。而事实上，只有在折叠孔洞周围的边时，才有可能导致孔洞消失，进而改变拓扑。所以，这一步骤旨在标记那些孔洞周围关键区域，并在后续简化过程中只对这些关建区域内的关键边进行拓扑检查，避免大量不必要的运算。

(2)边折叠拓扑检查：细究孔洞消失的原因，可以发现如果一条边不是三角形孔洞的三条边之一，那么折叠它就不会破坏拓扑。因此，在这一模块主要目的就是，通过一条边的局部连接信息，判断其是否构成了一个三角形孔洞。若是，则折叠该边会破坏拓扑结构；若不是，则折叠该边不会改变拓扑。

(3)并行边折叠简化：本发明通过并行化边折叠简化过程进一步提高算法效率。一条边的折叠会影响该边相邻区域的连接关系。因此，并行化需要保障并行处理的边折叠互不影响。本发明通过将模型包围盒划分成偶数个分片，每次只在间隔开的奇数或偶数序号分片内同时进行边折叠操作。只要间隔长度满足一定条件，就可以保障并行折叠互不影响。

下面，对本发明的各个步骤进行分别介绍。

1.寻找拓扑孔洞，标记拓扑关键区域

拓扑性质在拉伸、压缩、弯曲等连续变换下是保持不变的，只有造成撕裂和粘合才会改变拓扑性质。边折叠操作除了造成孔洞消失的情况，始终是一个保持拓扑的连续变换。因此对边折叠化简而言，保持拓扑可以归结为确保边折叠不会导致孔洞的消失。边折叠是一个只影响折叠边邻域内连接关系的操作，只有在折叠孔洞周围的边时，才有可能导致拓扑改变。所以对边折叠是否会破坏拓扑的检查只在孔洞周围才有必要。本发明先找到孔洞周围的拓扑关键区域，将拓扑检查限制在这一区域，因而可以显著提高计算效率。

初始中值面往往是非流形的网格，而在非流形的网格模型上提取孔洞周围区域是一个很困难的问题。但是，在网格模型的投影所得的二维图像中提取孔洞周围的像素则要容易很多。而中值面的深度投影在可见的孔洞周围必然会有深度值的明显变化。所以本发明首先在中值面的二维深度投影上进行孔洞检测，即找出与周围像素的深度值差别很大的像素，作为孔洞周围的关键像素。然后找到这些关键像素在中值面网格模型上对应的面片序号，将这些面片的边标记为关键边，从而标记出中值面上的拓扑关键区域。

由于关键边被折叠后产生的新的边依旧在孔洞周围，因此也会被标记为关键边。这种传递性意味着只要一个孔洞周围的部分区域被标记为关键区域，那么在后续简化过程中该孔洞附近边总有一部分需要进行拓扑检查，也就保障了该孔洞结构不会被破坏。而一个孔洞只要在一个投影图像中可见，其周边区域至少有一部分会被标记为关键区域。因此，投影方向的选择只要确保每一个孔洞都有部分在投影图像中可见即可。如图3左图所示，无遮挡时的一个孔洞，当且仅当其所在平面和投影方向y平行时，它在投影方向y相关的投影中是不可见的。因此，如果加上另外两个正交的投影方向x,z，就可以保证每一个未被遮挡的孔洞都可找到。图3右图展示了中值面上常见的遮挡情况，孔洞只在一侧可见。因此，在三个正交方向的基础上加上相反的-x,-y,-z方向，就可以基本解决遮挡问题。

具体实施步骤如下：

(1)如图2(a)所示，从±x,±y,±z共6个正交方向对中值面进行正投影，得到图2(b)显示的6个深度图像和6个对应的面片序号图像，此处面片序号图像记录了深度图像中每一个像素在中值面上对应的面片序号；

(2)对深度图像的每一个像素判断其与周边像素的深度差；若该差值大于某一阈值则标记该像素为关键像素(如图2中的(c)中黑点标记的像素)；设定该阈值为中值面上最长边的长度，这是因为一旦某个像素和周围邻域像素的深度差大于这一阈值，就意味着这两个像素对应着两个不相邻的面片。这表明该像素邻域发生了深度值较大的跃迁，也就意味着该像素可能位于孔洞周围区域。

(3)如图2(d)利用面片序号图像可以找到每一个关键像素所对应的面片序号，这些面片构成了拓扑关键区域，这些面片的边即为关键边，将在简化计算中需要进行拓扑检查；

2.边折叠拓扑检查

当一个孔洞由三条以上的边组成时，折叠任何一条边都不会导致该孔洞的消失。只有在折叠三角形孔洞的构成边时，才会导致孔洞的消失。而要判断一条边是否是三角形孔洞的边，只需要判断是否存在一个顶点与该边的两个顶点都相邻，且这三个顶点不构成一个面片，而构成了三角形孔洞。具体的实施步骤如下：

(1)遍历该边两个顶点的相邻顶点集合，找到它们的共同相邻顶点；

(2)遍历该边两个顶点的相邻面片集合，找到它们的共同相邻面片；

(3)对每一个共同相邻顶点，判断是否存在一个共同相邻面片包含了该顶点。若所有的共同相邻顶点都存在这样的共同相邻面片，则折叠该边不会破坏拓扑结构；否则，折叠该边会破坏拓扑结构。

3.并行边折叠简化

并行化可以进一步加快简化算法的速度，但是由于边折叠将会影响被折叠边邻域内的连接关系，要同时折叠数条边就需要保证折叠这些边所改变的连接关系不会产生冲突。如图4所示，本发明将模型包围盒划分成偶数个分片，每次同时折叠间隔开的分片内具有最小折叠简化代价的边。图中Ls是包围盒的最长边的长度，O,E分别表示奇数序号分片和偶数序号分片。并行折叠时，只要间隔的距离充分大，就可以保证边折叠操作互不影响，可以同时进行。在处理中，一条边只要有一个顶点位于某个分片中，就被算为该分片中的成员。图5展示了并行折叠两条边时不会发生冲突的情况，图中虚线圆圈表示边折叠操作的最大可能影响范围。当分片宽度W设定为大于四倍的中值面最大边长r时，间隔开的分片中的边进行折叠简化必然不会相互影响，也就可以同时进行简化。

具体实施步骤为：

(1)将模型的包围盒划分成偶数个分片；要求满足分片的宽度大于中值面最大边长的四倍；

(2)交错地选择所有奇数序号和所有偶数序号的分片进行并行的简化处理，直至达到简化目标；

(3)对一个分片中的中值面的面片进行简化处理时，以边折叠的方式进行。每次找到其中简化代价最小的边；检查该边是否是关键边，若不是则简化该边，反之则需进行拓扑检查，判断其简化会否导致相关孔洞消失；如果会则不简化该边，否则简化该边，并将新产生的面片标记为拓扑关键区域，对应的边标记为关键边；

下面是本发明的一些实验数据：

实验在一台微机上进行，该微机配备了一个Intel i7-8700(3.2GHz)CPU、16G RAM和一个NVIDIA GeForce GTX 1080Ti GPU。实验所用模型均来自学界常用的PrincetonShape Benchmark和Aim@Shape模型库。

与另一个代表性的边折叠中值面简化方法——Q-MAT[6]方法进行比较，图7是本发明和Q-MAT对比实验的结果，其中#v表示顶点数目，#genus表示模型亏格的数目，也就是孔洞的数目。Q-MAT方法为了避免拓扑检查在效率上的拖累，只在简化到一定顶点数目之后才开始进行拓扑检查。这就导致了该方法在开始拓扑检查之前可能有些拓扑结果已经破坏了。如图7中的(a)所示，初始模型和中值面亏格数目为8，但图7(b)显示，Q-MAT方法会导致亏格数目发生变化，孔洞消失，破坏了拓扑结构；而图7中的(c)则显示，本发明在同样的简化程度之下依旧能保持拓扑不变。

下表统计了本发明和Q-MAT方法对多个模型的中值面简化至2000个顶点的表示后的几何误差与所需时间。实验表明，本发明不仅能始终保持拓扑，且有和Q-MAT相近的几何精度，和更快的计算速度。