基于最近邻Marching Cubes的医学图像三维重建

在医学图像三维可视化中,移动立方体算法（Marching Cubes,MC）是面绘制的经典算法。针对MC算法计算插值点导致执行速度慢、效率不高的缺点,提出一种基于最近邻逼近的MC算法,该方法在n次等分点量化序列中寻找等值面最近邻点代替线性或非线性插值,既避免了插值的大量计算又保证了误差精度,还可改善三角面片结构。利用可视化工具开发包VTK对人体脸部和脚部CT数据集进行三维重建,实验表明改进算法明显缩短了绘制时间,提高了重建效率。     

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

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

基于自适应延迟切割的三角网格布尔运算优化

规则化的布尔运算被广泛应用在三维建模系统中.近年来,随着图形硬件的发展,基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理,表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略,使得面片在相交测试中反复被切割,并且由于面片分类在切割后的模型之间直接进行,导致算法无法在保证鲁棒性的同时实现高性能.为了避免这些问题,本文呈现了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成：自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段,算法通过仔细处理多个三角面片相交导致的各种情况使得延迟切割被扩展到整个CSG树来避免由于面片的反复切割带来的数值误差累积并利用自适应的八叉树使得相交测试能在线性时间内完成.在全局化面片分类阶段,算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度;通过结合组分类策略和自适应的八叉树来进一步优化了分类性能。实验结果表明,本文提出的算法无论是在执行单次或连续布尔运算时都能在保证鲁棒性同时性能优于其他的算法,因此本文算法可广泛应用于交互式建模系统中,如数字雕刻、计算机辅助设计和制造（CAD/CAM）等.     

虚拟装配中快速碰撞检测算法的研究与实现

针对虚拟装配中碰撞检测的特殊要求，提出了一种基于包围盒与空间剖分法的两级碰撞检测算法HSDHBB。该算法首先用空间剖分法找出潜在的相交区域，然后用包围盒求得碰撞的三角面片对和精确的碰撞点。给出了层次包围盒树的构造方法和空间网格的剖分方法，在空间剖分中采用哈希表的数据结构加快检索速度。最后，在CATIA环境中实现了该算法，结果表明该算法能够满足虚拟装配系统的实时性和精确性的要求。     

一种基于三角网格模型的阶梯剖切算法

针对三角网格模型,提出了一种基于四叉树的剖切算法。首先将三角面片投影到二维空间,并针对投影后的三角面片建立层次四叉树,然后,通过四叉树来查找第一个与切割面相交的三角形,由此三角形开始,利用三角网络的拓扑关系寻找所有被切割的三角形,最后将剖面进行三角剖分和三角网重构完成剖切。实验结果验证了该算法的可行性和有效性。     

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

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

基于八叉树的柔性体切割仿真中并行化的碰撞算法EI北大核心CSCD

为了提高柔性体切割仿真中碰撞处理的运行效率,并解决切割影响变形计算稳定性问题,提出基于八叉树的柔性体切割仿真中碰撞算法的并行化实施方法.该方法使用基于链接体素和自适应八叉树网格的柔性体模型,前者用于描述物质的连接性和构造用于碰撞和图形显示的面网格,后者用于变形计算;在粗略碰撞阶段对八叉树网格构造空间Hash表并构造潜在碰撞对;在精细碰撞阶段根据体素中心的距离场值,使用考虑拓扑关系的距离场插值方法检测碰撞并计算入侵深度;柔性体之间的碰撞和自碰撞处理使用独创的多级检测和约简方法在GPU上运行,同时在CPU上使用多线程运行切割工具与柔性体的碰撞处理;切割算法切断被切割工具扫过的链接,重构切口附近的面网格,递归细分并复制被切割工具扫过的八叉树单元,并使用快速行进法更新距离场.仿真实验结果表明,与3个CPU线程的实现相比,文中GPU加速的柔性体碰撞和自碰撞算法可以将处理速度提高76%~215%;而与单个CPU线程的实现相比,3个CPU线程实现的切割工具与柔性体的碰撞算法可以将处理速度提高132%~190%.     

基于八叉树的柔性体切割仿真中并行化的碰撞算法

为了提高柔性体切割仿真中碰撞处理的运行效率,并解决切割影响变形计算稳定性问题,提出基于八叉树的柔性体切割仿真中碰撞算法的并行化实施方法.该方法使用基于链接体素和自适应八叉树网格的柔性体模型,前者用于描述物质的连接性和构造用于碰撞和图形显示的面网格,后者用于变形计算;在粗略碰撞阶段对八叉树网格构造空间Hash表并构造潜在碰撞对;在精细碰撞阶段根据体素中心的距离场值,使用考虑拓扑关系的距离场插值方法检测碰撞并计算入侵深度;柔性体之间的碰撞和自碰撞处理使用独创的多级检测和约简方法在GPU上运行,同时在CPU上使用多线程运行切割工具与柔性体的碰撞处理;切割算法切断被切割工具扫过的链接,重构切口附近的面网格,递归细分并复制被切割工具扫过的八叉树单元,并使用快速行进法更新距离场.仿真实验结果表明,与3个CPU线程的实现相比,文中GPU加速的柔性体碰撞和自碰撞算法可以将处理速度提高76%~215%;而与单个CPU线程的实现相比,3个CPU线程实现的切割工具与柔性体的碰撞算法可以将处理速度提高132%~190%.     

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

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

智能配镜三维特征参数提取方法研究

摘 要：针对智能配镜中三维面部特征点提取算法复杂度较高的问题,提出一种将三维点 云转换为映射图像定位特征点的方法。采用 Voronoi 方法计算面部三角网格各顶点处的高斯曲 率、平均曲率。选取鼻尖、眼角等曲率特征明显的区域估计面部点云姿态。根据曲率旋转不变 性,使用初选的点云方向向量简化旋转矩阵的计算,使面部点云正面朝向视点。将点云映射转 换为图像,三维网格模型中三角面片一对一映射到图像中的三角形。搭建卷积神经网络,使用 Texas 3DFRD 数据集进行模型训练。进行人脸对齐,预测所得各面部特征点分别限制在图像某 三角形中。根据图像中三角形映射查找三维网格模型中对应三角面片,通过三角面片顶点坐标 计算配镜所需的面部特征点位置坐标,实现配镜特征参数的提取。     

基于动态OBB层次结构的曲面相交算法*

为提高大曲面相交算法的效率,提出一种基于新的碰撞检测的曲面相交算法。该算法采用动态OBB层次结构碰撞算法获取相交区域,准确计算交点并构成交线;再利用分治三角化算法重构相交区域,以基于交线平均长度的方法去除窄小三角形,同时对空间闭合交线进行三角化,更新相交区域的三角形,并以闭合交线区分不同的区域。通过分析和实验结果证明,该算法能够对由大量三角形组成且相交情况比较复杂的曲面进行较快的处理。     

基于骨骼的3D角色的碰撞检测

基于骨骼的角色实现快速碰撞检测。该算法以层次包围盒（OBB）为基础,通过为每个骨骼模型建立包围盒,运用分离轴理论计算包围盒的相交测试。该方法能有效地用于3D游戏引擎中碰撞检测的实现。     

蒙皮骨骼动画的碰撞检测研究

提出了一种利用蒙皮骨骼的特点改进的碰撞检测算法,该算法使用层次包围体为基础,改进了OBB树的生成和更新。实验证明,该算法提高了碰撞检测的效率,能满足复杂3D人物的碰撞检测需求。     

基于包围盒的碰撞检测算法研究

基于包围盒的碰撞检测算法是一类重要的碰撞检测算法。文章比较了几种常用的包围盒碰撞检测算法;给出了OBB包围盒的计算算法及其改进和修正算法;包围盒树的建立算法;包围盒的重叠测试和基于包围盒的碰撞检测算法;最后以OBB验证了该类算法的有效性,正确性和鲁棒性。     

Efficient triangle–triangle intersection test for OBB-based collision detection

We present an efficient algorithm for triangle–triangle intersection test in oriented bounding box (OBB)-based collision detection. In testing two OBB leaf nodes (i.e., rectangles), many intermediate computation results can be reused for the intersection test of two triangles they contain. It is considerably easier to detect redundant operations when we work in the local coordinate of the bounding rectangle rather than in the global coordinate of the object. The performance improvement of our algorithm is based on this observation that eliminates redundant computations. Compared with conventional algorithms, we have observed 15–79% improvement in computing time. We demonstrate the effectiveness of our approach using several experimental results.     

实时碰撞检测算法分析与比较

随着计算机硬件的升级,3D虚拟游戏产业早已出现在电脑的客户端,而碰撞检测是影响3D虚拟环境的一个重要因素,如何快速而精确地进行碰撞检测成为研究的热点。本文主要介绍碰撞检测的几种常用的算法,根据球和OBB包围盒的特性,提出一种球包围与OBB包围盒相结合的算法。针对众多的改进算法的局限性,应根据具体情况及碰撞检测精度选择不同的算法以实现较好的碰撞效率。     

基于空间散列法的虚拟植物碰撞检测算法

根据虚拟植物模型复杂的特点,采用在精细的三角形网格模型上所创建的较粗糙的四面体网格模型,在虚拟植物模型上实现基于空间散列法的碰撞和自碰撞检测.该算法具有高效快速、无需复杂的数据结构等特点.实验结果表明,该算法能够有效地解决群体中植株的碰撞和自碰撞问题,并能够达到实时的处理要求.可同时适用于其它复杂的三维模型的碰撞检测问题.     

导弹飞行视景仿真中的碰撞检测算法

针对导弹飞行视景仿真中碰撞检测实时性与精确性的不足,提出了一种优化的混合包围盒碰撞检测算法.该算法在包围盒树的上层使用Sphere,下层使用OBB;将该算法在导弹飞行视景仿真系统中实现后,分别与相交矢量碰撞检测算法、OBB包围盒算法进行对比试验和分析.结果表明,这种混合包围盒算法能够有效地提高导弹飞行视景仿真中碰撞检测的实时性与精确性.     

CPU–GPU Parallel Framework for Real‐Time Interactive Cutting of Adaptive Octree‐Based Deformable Objects

A software framework taking advantage of parallel processing capabilities of CPUs and GPUs is designed for the real‐time interactive cutting simulation of deformable objects. Deformable objects are modelled as voxels connected by links. The voxels are embedded in an octree mesh used for deformation. Cutting is performed by disconnecting links swept by the cutting tool and then adaptively refining octree elements near the cutting tool trajectory. A surface mesh used for visual display is reconstructed from disconnected links using the dual contour method. Spatial hashing of the octree mesh and topology‐aware interpolation of distance field are used for collision. Our framework uses a novel GPU implementation for inter‐object collision and object self collision, while tool‐object collision, cutting and deformation are assigned to CPU, using multiple threads whenever possible. A novel method that splits cutting operations into four independent tasks running in parallel is designed. Our framework also performs data transfers between CPU and GPU simultaneously with other tasks to reduce their impact on performances. Simulation tests show that when compared to three‐threaded CPU implementations, our GPU accelerated collision is 53–160% faster; and the overall simulation frame rate is 47–98% faster.