论文部分内容阅读
空间分割算法在计算机图形学中占据重要地位。本文分别针对层次划分结构中的八叉树和非层次划分结构中的Voronoi图在GPU上进行了高效的实现。并且将GPU端的八叉树建立方法应用于高分辨率三角形网格求交。针对模型编辑问题,本文提出了一种新的基于近似刚度(ARAP)算法的模型编辑算法,提高了ARAP算法的细节保持能力。
在高分辨率三角形网格模型间的几何布尔运算中,求解两网格模型间的相交区域是很多求解算法中核心的一步。本文使用了自适应高度的八叉树作为空间分割结构,降低了算法的时间复杂度。同时将主要算法在GPU端进行实现,利用GPU的并行计算能力对八叉树建立及三角形间的求交过程进行并行化,提高了算法的效率。针对以往GPU端层次空间划分结构需要在建立过程中分割三角形,造成大量退化三角形,并降低了数值精度的情况,本文中的算法尽量避免了在空间分割过程中对三角形进行的分割,从而提高了最终三角形求交区域计算的精度。同时,在三角形求交阶段使用更精确的求解方式。通过与GTS软件的整合,最终实现了高效的几何布尔运算。
提出了一种GPU端的鲁棒的二维Voronoi图构建算法。本算法有着较好的平均性能,并在种子节点分布较稠密和均匀的情况下取得最优性能。同时在GPU上实现了鲁棒Voronoi图的构建算法中的BFA算法以及非鲁棒算法中的JFA算法。经验证,此算法能够在种子数一定的情况下获得比BFA好的平均性能,并在种子较多的情况下获得接近JFA的性能。
作为几何建模的重要手段,曲面变形有着广泛的应用。传统的近似刚性(ARAP)曲面编辑算法存在局部塌陷的问题,并在变形过程中可能产生退化三角形,影响了曲面的质量。本文提出了一种新的基于ARAP曲面编辑算法框架与三角形局部能量的三角形网格编辑算法,通过对每个三角形定义其允许的变换集合,在细节丰富的区域得到了更好的保形效果。通过限制三角形缩放因子的比例,减少了ARAP算法在变形过程中产生退化三角形的情况。本算法提高了ARAP变形算法的鲁棒性,增强了变形过程中对网格局部细节的保持能力。
提出的空间分割算法和模型编辑算法分别在性能上和数学模型上对计算几何中相关的算法做出了改进,对今后在这方面的工作提供了技术支持。