本发明涉及图像处理，具体为一种gpu并行的受约束delaunay网格划分方法。
背景技术：
1、传统的delaunay四面体生成算法一般是基于cpu的串行算法。常见的算法基本上可以分为翻转法和增量插点法两类。翻转法是首先利用所有输入顶点生成不一定满足delaunay条件的网格，之后检测不满足delaunay条件的区域并逐步调整，直到网格满足delaunay条件；增量插点法则是先生成一个可以包围所有输入顶点的大单元，之后逐步向现有网格中插入顶点，并保证每一步插入后得到的网格都满足delaunay条件，逐步插入顶点直至所有输入顶点插入完成。
2、随着计算机技术的发展，现今的计算机处理器的单核心性能逐渐饱和，处理性能的提升更多以增加并行能力的方式实现。此外，gpu等设备凭借核心数量优势在一些大规模数据处理任务上获得了远超cpu的性能。因此，传统的cpu单线程算法很难适应当今的计算需求。为此我们提出了一种gpu并行的受约束delaunay网格划分方法。
技术实现思路
1、针对现有技术的不足，本发明提供了一种充分利用gpu的多线程计算能力，在每一轮迭代中可以插入多个顶点并保证得到的网格的delaunay性质，进而大幅减少生成delaunay网格的迭代步数，提高了网格生成速度的gpu并行的受约束delaunay网格划分方法。
2、为实现上述目的，本发明提供如下技术方案：一种gpu并行的受约束de launay网格划分方法，包括如下步骤：
3、步骤一、生成无约束网格
4、生成四个顶点，即超级点，使其连成的四面体可以包含所有输入顶点，将超级点构成的四面体作为初始四面体网格；
5、在输入顶点里尚未插入网格的顶点中尽可能多地选取处在当前网格的不同四面体中的顶点作为待插入顶点；
6、对于每一个待插入点，将当前网格中所有外接球包含该待插入点的四面体作为该待插入点的空腔，当不同待插入点的空腔存在重叠或相邻时，放弃优先级较低的待插入点；
7、删除空腔中的四面体，由待插入点和空腔表面生成一系列四面体填充空腔；
8、重复以上过程直至全部顶点被添加进来，生成delaunay四面体网格。
9、步骤二、恢复线段约束
10、创建列表s1和s2，s1存储所有在网格中存在的约束线段，s2存储所有在网格中尚不存在的约束线段，并行地为s2中的每条线段找出一个参考点，对于一条线段，其参考点为当前网格顶点中对该线段张角最大的顶点；
11、根据参考点与待恢复的约束线段的关系确定插入点的位置，若参考点与约束线段的顶点间存在约束线段，则以两条约束线段的公共端点为球心，以参考点到公共端点的距离为半径做球，以球与待恢复约束线段的交点为插入点，否则以参考点在待恢复线段上的投影点为插入点；
12、采用生成无约束网格的方式进行一轮尝试插入这些顶点，直接舍弃一轮插入算法后未被插入的顶点，对于插入成功的，将对应的线段从s2中删除，并将生成的两条子线段加入s1，并行地判断s1中的线段是否存在于网格中，将不存在的线段从s1中删除并加入s2；
13、重复上述过程直至s2为空集；
14、步骤三、恢复面约束
15、1)假设输入中共有n个三角形面约束，启动n个线程，每个线程负责一个三角形，在每一个线程中，判断该三角形的约束边上是否有新插入的顶点，如果没有则退出，对于未退出的线程，调用二维delaunay三角化算法对三角形进行重新剖分，得到一组新的三角形；
16、2)对于所有不须重新剖分的三角形和1)中得到的三角形，判断这些新三角形中哪些存在于当前四面体剖分之中，并将不存在的三角形收集起来，作为待恢复的三角形面；
17、3)在所有待恢复的三角形面中，相邻且公共边不是约束线段的三角形将组合为多边形约束面进行恢复；
18、4)对于每一个三角形或多边形约束面i，首先找到穿过约束面的所有四面体ti，并将这些四面体从当前四面体网格中删除，将这些四面体的顶点和约束面上的顶点收集起来，分成三组pi+，pi-，pi0，其中pi+和pi-分别表示在约束面两侧的顶点，pi0表示在约束面上的顶点，以pi+∪pi0生成无约束delauna y剖分并去除超级点和包含超级点的四面体后得到一组四面体ti+，同样的以pi-∪pi0生成无约束剖分并去除超级点和包含超级点的四面体得到一组四面体ti-，由delaunay剖分的唯一性可知，这两组四面体共享由p0生成的三角形，之后尝试将ti+和ti-嵌入原四面体剖分，若ti+或ti-嵌入后与原剖分存在冲突，删除ti+或ti-中造成冲突的四面体，并判断是否仍旧存在冲突或存在无法填满由于删除ti造成的孔洞的情况，如果不存在则直接填入删除冲突后的ti+和ti-完成约束面恢复，否则在ti的基础上添加与ti+或ti-存在冲突的原剖分中的四面体得到新的ti，删除这些四面体后以更新后的ti中四面体的顶点重新进行上述过程，直到新生成的剖分可以完美嵌入原四面体剖分为止，完成对约束面i的恢复；
19、步骤四、清理实体外的四面体
20、当前剖分中共有n个四面体，分配n个线程，每个线程对应剖分中的一个四面体，每个线程进行判断，当对应四面体满足下面任意条件时，将该四面体标记为待删除：
21、·四面体的某个顶点是超级点
22、·四面体的某个面是约束面，且该四面体处于约束面外侧
23、·四面体与被标记为待删除的四面体相邻，且公共面不是约束面；
24、同步所有线程，直到不再有新四面体被标记，删除所有具有待删除标记的四面体。
25、优选地，所述步骤一中当n维网格中存在n+1个顶点共球时，delaunay网格不唯一时，采用了edelsbrunner和e.p.mücke提出的微扰方法，判断顶点是否在某个四面体外接球内部。
26、优选地，所述步骤一中插入点选择方法为：在每个包含未插入顶点的单元内，计算这些未插入顶点的重心，选择距离重心最近的顶点作为待插入点。
27、优选地，所述在步骤一中将包含待插入顶点的单元作为初始空腔，之后进行迭代，每一步迭代检测与当前空腔相邻的单元外接球是否包含待插入顶点，如果包含则将其加入空腔，迭代至与空腔相邻的单元都不应被加入空腔为止。当一个四面体单元应当被加入多个不同待插入点的空腔，即产生冲突时，该四面体单元加入优先级更高的待插入点的空腔，冲突中的低优先级空腔对应的待插入点不再拥有空腔，这些低优先级顶点留待后续迭代过程插入。优选地，所述步骤二中插入点选取方案为：
28、1)判断参考点和待恢复线段的端点之间是否有约束线段；
29、2)如果有约束线段，则以公共端点为球心，以过参考点的约束线段长度为半径做球，以球和待恢复线段的交点作为插入点；
30、3)参考点与待恢复线段的端点间没有约束线段，则将参考点投影到待恢复线段上，以投影点作为插入点。
31、优选地，所述步骤二中按照无约束网格生成方式将顶点插入网格完成线约束恢复。
32、优选地，所述步骤二中假设网格当前有m个顶点，当前有n条待恢复线段，启动m×n个线程，每个线程处理一对顶点和恢复边，线程内判断顶点是否在以线段为直径的球内，如果在求内，则该点可能成为参考点，求得该点对线段的张角，利用原子操作比较这一张角和当前被选择的参考点的张角，如果该点张角更大则替换被选中的参考点。
33、优选地，所述步骤三中假设输入中共有n个三角形面约束，启动n个线程，每个线程负责一个三角形，在每一个线程中，判断该三角形的约束边上是否有新插入的顶点，如果没有则退出，对于未退出的线程，调用二维dela unay三角化算法对三角形进行重新剖分。
34、优选地，所述步骤四中在剖分和约束恢复结束后，还应将不属于模型的四面体删除，这些四面体分为包含超级点的四面体和不包含超级点但在模型之外的四面体。
35、与现有技术相比，本技术的技术方案具备以下有益效果：
36、1、本发明提出了一种gpu并行的受约束的delaunay四面体网格划分算法，该算法借鉴了串行算法中的增量插点法，也是生成一个单一网格后逐步插入顶点，并保证每一步插入顶点后的网格满足delaunay条件，直至完成网格划分，该算法可以充分利用gpu的多线程计算能力，在每一轮迭代中可以插入多个顶点并保证得到的网格的delaunay性质，进而大幅减少生成delau nay网格的迭代步数，提高了网格生成速度。
37、2、本发明的gpu并行的受约束delaunay四面体网格划分算法主要分为四个步骤：无约束delaunay网格生成、线段约束恢复、面约束恢复和清理实体外的四面体，无约束网格生成部分，在bowyer-watson算法的基础上改进了插入点的选取顺序，实现了并行插入顶点的功能，得到了适合并行的插点算法；线段约束的恢复部分，相比传统的串行约束恢复算法，实现了并行的线段存在性判断、并行的拆分点选取和并行插入功能，使得多个线段约束可以并行恢复；面约束恢复部分，实现了并行的面存在性判断、并行地影响区域判定和并行的面约束恢复功能；实体外四面体清理部分，实现了并行的实体外四面体筛选。
1.一种gpu并行的受约束delaunay网格划分方法，其特征在于：包括如下步骤：
2.根据权利要求1所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤一中当k维网格中因为存在k+1个顶点共球导致dela unay网格不唯一时，采用了edelsbrunner和e.p.mücke提出的微扰方法，用微扰方法使得其中顶点在计算是否共球时稍微偏离原始位置，保证在这种计算方式下任意k+1个点不共球。
3.根据权利要求2所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤一中通过改进bowyer和watson算法，在每一个迭代步插入多个顶点，提出并行增量插点的delaunay网格生成算法：
4.根据权利要求3所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述在步骤一中将包含待插入顶点的单元作为待删除的单元，之后进行迭代，每一步迭代检测与当前空腔相邻的单元外接球是否包含待插入顶点，如果包含则将其加入空腔，迭代至与空腔相邻的单元都不应被加入空腔为止。
5.根据权利要求1所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤一中插入点选择方法为：在每个包含未插入顶点的单元内，计算这些未插入顶点的重心，选择距离重心最近的顶点尝试插入。
6.根据权利要求1所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤二中插入点选取方案为：
7.根据权利要求6所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤二中按照无约束网格生成方式将顶点插入网格完成线约束恢复。
8.根据权利要求6所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤二中假设网格当前有m个顶点，当前有n条待恢复线段，启动m×n个线程，每个线程处理一对顶点和恢复边，线程内判断顶点是否在以线段为直径的球内，如果在球内，则该点可能成为参考点，求得该点对线段的张角，利用原子操作比较这一张角和当前被选择的参考点的张角，如果该点张角更大则替换被选中的参考点。
9.根据权利要求1所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤三中假设输入中共有n个三角形面约束，启动n个线程，每个线程负责一个三角形，在每一个线程中，判断该三角形的约束边上是否有新插入的顶点，如果没有则退出，对于未退出的线程，调用二维dela unay三角化算法对三角形进行重新剖分，判断这些新三角形中哪些存在于当前四面体剖分之中，并将不存在的三角形收集起来，作为待恢复的三角形面。
10.根据权利要求1所述的一种gpu并行的受约束delaunay网格划分方法，其特征在于：所述步骤四中在剖分和约束恢复结束后，还应将不属于模型的四面体删除，这些四面体分为包含超级点的四面体和不包含超级点但在模型之外的四面体。
