高效的多边形布尔计算方法
针对计算机图形学中应用广泛的多边形布尔计算,提出了一种新的、适用于一般多边形的并集、交集和差集算法.算法主要分为计算交点、将交点插入多边形顶点序列、遍历三个步骤.通过采用循环单链表的数据结构、避开复杂的出入点计算、及预先的一些碰撞检测以避开复杂的求交运算与链表遍历等技巧,提高了算法的执行速度、减少了存储单元.算法能够很好地处理一些奇异情形(边界情形),比如重叠边、交点为边的顶点等情形,具有很好的鲁棒性.与经典的Weiler算法、Vatti算法和Greiner-Hormann算法相比,该算法具有较低的时间复杂度O((m+n+k)log d))和空间复杂度.实验结果显示该算法在处理2222×2222个顶点、42个交点时比经典的Weiler算法速度提高了296倍.算法的主要思想对确定两个多面体的交、并、差问题亦有参考价值.
计算机图形学 多边形 布尔计算算法 优化设计
齐东洲 吴敏
上海市高可信计算重点实验室(华东师范大学),上海 200062
国内会议
湖北襄阳
中文
78-82
2014-09-27（万方平台首次上网日期，不代表论文的发表时间）