三维网格模型的布尔运算方法

提出了一种基于三维网格模型的布尔运算方法。首先通过基于方向包围盒（OBB）层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果。实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性。     

基于空间多边形三角剖分的曲面分割求交算法

针对传统曲面分割求交方法存在的平面片的选取、遗漏部分交线段以及交线间断 的问题,提出一种基于空间多边形三角剖分的曲面分割求交算法。以等深度分割方法为基础, 避免了交线不连续的问题,当分割达到一定层次时以空间多边形近似曲面片,并对空间多边形 进行三角剖分,以三角形对的交线近似空间多边形之间的交线,进而以空间多边形的交线近似 曲面片的交线,最终得到相交曲面之间的交线。利用曲面片轮廓构造出的空间多边形更加接近 曲面片的真实形状,提高了逼近精度,同时对空间多边形进行三角剖分,提高了求交精度,进 而降低了丢失交线的可能性。实验验证了该算法比传统的分割法更加精确。     

三维网格模型的稳定布尔运算算法

给出一种稳定、高效的三维网格模型的布尔运算算法。该算法首先,基于网格模型原始的拓扑关系,结合层次包围盒相交检测实现网格模型相交区域快速定位;然后,采用改进的空间三角形求交算法求解离散交线段数据,并对单个三角形重新进行Delaunay三角剖分;最后,通过建立交线段与相交三角形间的拓扑关系对交线快速跟踪提取,通过局部区域快速分类组合,实现三角网格模型的精确布尔运算。该算法能有效地处理各种特殊情况且运行稳定;程序实现简单,实例证明符合工程需求。     

基于平均单元格的三角网格曲面快速求交算法

在地质建模中,当待处理的曲面包含大量三角形时,求交速度成为了瓶颈。该文提出基于平均单元格的三角网格曲面快速求交算法,采用平均单元格技术对求交曲面进行预处理,以加快相交元素对的获取。实验结果表明,与同类求交算法相比,该算法能够有效提升求交速度,并已成功应用于某地质建模软件中。     

基于八叉树和混合搜索树的地质曲面快速求交方法

为处理地质界面之间的空间相交关系,提出一种新的针对三角地质曲面的快速求交方法。该方法融合优化八叉树法和OBB搜索树方法,可以更快速准确地剔除远离交线的其他三角形。求交剩余的三角形得到交线,应用三角网局部重构和网格优化算法修正交线附近的三角网,最终分割交线两侧的地质曲面,完成2个地质曲面的离散化求交过程。与AABB、OBB和空间分解法相比,该方法在大数据量三角曲面求交中效率优势明显,可以快速准确处理地质模型构建和分析中的曲面求交问题,为三维地质模型自动化构建的实现提供有效支撑。     

分片驱动的特征敏感曲面重建

为健壮处理包含尖锐特征或欠采样的数据点集,通过对基于边界推进曲面重建技术的扩展,提出一种分片驱动的、特征敏感的对无方向散乱数据点集进行曲面重建的算法.在一个光滑阈值的控制下,将曲面重建过程分成分片重建和特征缝合2个阶段.在分片重建中,从光滑的种子三角化区域开始进行边界推进三角化,并通过拓扑元素分类与特征检测对边界光顺和特征重定位,以进一步扩展该分片,重复该过程,得到对光滑区域三角化的一系列光滑分片;特征缝合阶段,在边界推进过程中将所有分离的分片或分片中的缝隙缝合在特征区域.这种两阶段的三角化策略可有效地处理含尖锐特征或不规则采样如不充分采样的点集,无需保证拓扑完整性的复杂数学测试,如协变分析和三角形相交检测等,基于局部光滑曲面的求交,可有效地恢复采样点集丢失的特征信息.实验结果表明,采用文中算法能健壮处理不规则采样点集,并生成特征敏感的高质量网格.     

细分曲面求交交线计算方法的研究

主要针对三角网格的细分曲面求交提出了一种有效的交线计算的方法,该方法适用于任意三角网格的细分曲面中.在利用AABB和二部图进行初始控制网格相交性检测后,利用该方法快速有效地求出细分曲面的交线.     

多边形网格的非流形封闭三角形网格正则化

为了提高基于网格模型的算法与应用的效率和稳定性,提出一种将任意多边形网格模型转化为正则三角网格模型的算法.首先对输入多边形网格模型中非三角形的面片进行三角剖分,然后查找并移除模型中的重合或重叠元素,再通过模型内部三角形求交对模型进行边和面的分割,从而修正模型的拓扑结构;在求交的过程中,根据边和三角形的位置关系对共面求交进行细致的分类处理,减少了求交次数,提高了算法的稳定性;最后循环搜索在网格模型中可以确定法向的种子三角形,通过拓扑结构调整与之相邻的三角形的法向,最终构成一个或多个法向确定的闭合曲面.实验结果表明,该算法能够将多边形网格转化为正则三角形网格模型.     

基于"结式法"的二次曲面求交算法

提出了一种新的基于“结式法”的二次曲面求交算法，该算法首先利用结式法计算出两二次曲面相交时交线的投影方程,再对投影方程进行分解等处理，通过循环计算从而得到投影交线的分支数及其上的一系列的点,然后回代入两二次曲面中的一个即可得到二次曲面的交线，该算法实现简单且符合求交算法的稳定、准确和快速等要求。     

一种通用的trimmed曲面三角化算法

本文提出一种既可用于进行trimmed曲面求交,也可用于进行trimmed曲面显示的快速trimmed曲面三角化算法。算法主要基于本文首次提出的对trimmed曲面的空间及参数trimmed边界进行相关离散的思想和入边、出边、跨边三角形等新概念。算法已经成功地应用于雕塑立体造型系统MESSAGE中,进行trimmed曲面的求交与显示。     

Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Möller’s algorithm, Devillers’ and Guigue’s algorithm, and Shen’s algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers’ and Guigue’s algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers’ and Guigue’s triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models.

     

A faster triangle‐to‐triangle intersection test algorithm

The triangle‐to‐triangle intersection test is the most basic component of collision detection. And our algorithm, which firstly computes the line segment between triangle A and the plane of triangle B and uses a new method to detect the intersection between this line and triangle B, can reduce about 10% of time on average, compared with the previous fastest algorithm. Our new method divides the plane of triangle B into four quarter planes by two edges of B, and detects intersection depending on the location of the two endpoints of the segment. After using some techniques like avoiding division and projecting the segment and triangle B on XY, YZ, or ZX plane, the total number of arithmetic operations is reduced to at most 87, which is less than any existing algorithms. Copyright © 2013 John Wiley & Sons, Ltd.     

A fast triangle to triangle intersection test for collision detection

The triangle‐to‐triangle intersection test is a basic component of all collision detection data structures and algorithms. This paper presents a fast method for testing whether two triangles embedded in three dimensions intersect. Our technique solves the basic sets of linear equations associated with the problem and exploits the strong relations between these sets to speed up their solution. Moreover, unlike previous techniques, with very little additional cost, the exact intersection coordinates can be determined. Finally, our technique uses general principles that can be applied to similar problems such as rectangle‐to‐rectangle intersection tests, and generally to problems where several equation sets are strongly related. We show that our algorithm saves about 20% of the mathematical operations used by the best previous triangle‐to‐triangle intersection algorithm. Our experiments also show that it runs 18.9% faster than the fastest previous algorithm on average for typical scenarios of collision detection (on Pentium 4). Copyright © 2006 John Wiley & Sons, Ltd.     

三角形对的快速相交测试

为提高碰撞检测的响应速度,提出了一种基于Ayellet算法的改进算法.该算法从代数的角度出发,首先快速排除掉三角形对不相交或共面的两种情况,然后分别计算一个三角形与另一个三角形所在平面的相交线段,最后检测这两条线段是否有公共点.如果有公共点则三角形对相交,反之则不相交.该算法也可以应用于类似的问题,如矩形对的相交测试,多边形对的相交测试.实验结果表明,该算法的速度优于改进前的算法.     

结合轴对齐包围盒和空间划分的碰撞检测算法

目的 碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法 本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果 本文算法与AABB层次包围盒二叉树算法、k-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和k-Dops算法的距离差超过阈值0.02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和k-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论 结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。     

一种优化的机器人碰撞检测算法研究

提出了一种基于Vclip的优化碰撞检测算法,利用Vclip算法对AABB包围盒进行底层碰撞检测计算,用GPU的遮挡查询等特性进行三角形相交测试,以提高对虚拟物体进行碰撞检测的精确性与实时性。算法已成功应用于课题组自行研制的6自由度小型工业机器人的仿真控制系统中,实验结果表明,其算法具有高效、精确、实时性高等特点,能使控制系统对工业机器人的控制更为流畅。     

三角形和三角形相交测试技术研究

高效率的“三角形和三角形相交测试”对于提高碰撞检测算法效率,增强虚拟场景的真实感和沉浸感起着至关重要的作用。该文深入研究了“三角形和三角形相交测试”的基本原理和典型算法,根据算法思想提出两个概念：标量判别法和矢量判别法,并对两种算法进行验证,对仿真计算结果进行分析、比较得出：矢量判别算法是对标量判别算法的改进和优化,条件相同时检测效率提高约7％,算法更加简单快捷,具有较高的理论意义和实际工程应用价值。     

基于八叉树精确划分型值点的碰撞检测算法

针对虚拟现实中碰撞检测的快速计算问题,提出一种新的粗略碰撞检测与精确碰撞检测相结合的检测算法。首先利用AABB包围盒法排除不可能相交的物体,然后对可能发生碰撞的包围盒采用八叉树算法进行空间分割,在包围盒内找到由型值点形成的三角形面片,利用三角形面片的碰撞检测算法精确地判断物体是否碰撞。通过与OBB包围盒算法的碰撞检测数据对比,验证了该方法的有效性。     

基于OBB树层次关系的相交体特征计算

针对不同复杂情况的网格模型在运动过程中发生的接触问题，提出了一个有效、准确的相交体特征计算算法，这里的特征包括相交三角形求交线，相交体求轮廓线，相交体求轮廓体。该算法以OBB（Oriented Bounding Boxes）树的数据结构为基础，借助AABB（Axis-Aligned Bounding Boxes）包围盒，通过分析线段、三角面、包围盒的位置关系情况，得到了相交线段、相交三角面以及包围三角面，并在此基础上计算出相应的相交体特征。该算法在CAD模型分割、建造、几何特征提取、生产车间以及机器人运动轨迹规划等方面都有很高的应用价值。     

SQ-Map: efficient layered collision detection and haptic rendering

This paper presents a novel layered and fast framework for real-time collision detection and haptic interaction in virtual environments based on superquadric virtual object modeling. An efficient algorithm is initially proposed for decomposing the complex objects into subobjects suitable for superquadric modeling, based on visual salience and curvature constraints. The distance between the superquadrics and the mesh is then projected onto the superquadric surface, thus generating a distance map (SQ-Map). Approximate collision detection is then performed by computing the analytical equations and distance maps instead of triangle per triangle intersection tests. Collision response is then calculated directly from the superquadric models and realistic smooth force feedback is obtained using analytical formulae and local smoothing on the distance map. Experimental evaluation demonstrates that SQ-Map reduces significantly the computational cost when compared to accurate collision detection methods and does not require the huge amounts of memory demanded by distance field-based methods. Finally, force feedback is calculated directly from the distance map and the superquadric formulae