网站建设费用 计入什么科目,搜索网站做淘宝客,温州优化售后,培训学做网站要多久目录 三维布尔运算概述三角网格布尔运算效率提升思考BSPTree方式优化 参考 三维布尔运算概述
三维布尔运算根据三维实体数据结构表达分为CSG布尔运算、Brep布尔运算、三角网格布尔运算等类型。这几种类型算法在不同情境下有不同的优势#xff0c;根据情况进行选择。但这也不能… 目录 三维布尔运算概述三角网格布尔运算效率提升思考BSPTree方式优化 参考 三维布尔运算概述
三维布尔运算根据三维实体数据结构表达分为CSG布尔运算、Brep布尔运算、三角网格布尔运算等类型。这几种类型算法在不同情境下有不同的优势根据情况进行选择。但这也不能作为随意选择方案的借口在不分析实际情况下。
CSG和BRep布尔运算能够保留原始几何拓扑信息适用于各类设计编辑场景如建模设计软件中。而三角网格布尔运算也是常见和常用的由于一些因素当前实体的表达方式就是三角面网格方式也需要对这些实体进行编辑这时候三角网格布尔运算是最佳选择方案。当然也有其他方案如将三角网格实体拟合为Brep实体然后使用BRep布尔运算方法进行计算至于有没有必要还是上述表达的那样根据实际情况分析进行选择取舍。
本文就三角网格布尔运算几点思考进行简单记录。
三角网格布尔运算
三维布尔运算的一个核心思想是得到运算两实体彼此相对内外部分然后根据布尔运算类型对这些部分进行组合。如实体A与实体B进行计算得到A in B、A out B、B in A、B out A四部分实体A与实体B求交运算即为A in B B in A求并、求差运算类似求差会涉及到组合前对对应部分进行取反这里不再赘述。 那么问题来了如何提高运算得到两实体彼此相对内外部分的效率 效率提升思考
关于该问题有不少论文、文章、开源库、商业库进行过思考并形成各自提出的方案思路主线是怎样降低判断一个三角面与实体的包含关系的运算时间。
目前有空间分区二叉树BSPTree和其它搜索树如八叉树、球体空间位置树等方案。
BSPTree方式基于实体本身的几何拓扑数据构造树三角面所在超平面对实体空间进行分割
优势是在搜索时即可以得到精确的结果劣势是会产生较多的碎三角面、构造的BSPTree可能不太平衡当然这两个问题都有方案去应对
八叉树方式根据实体空间分布进行八叉树的构造得到的搜索树比较平衡搜索得到相关三角面子集后由三角面子集对目标三角面进行切割根据切割线有向和目标三角面本身的轮廓线有向进行路径搜索得到目标三角面在实体内外部分。当然可能没有切割到这时就需要判断目标三角面是在实体内部还是外部同样可以利用实体八叉树降低此判断复杂度。
优势是根据实体空间分布进行八叉树的构造得到的搜索树比较平衡同时不会产生多余的三角面劣势是计算实现复杂
如果不进行优化判断一个三角面与实体的包含关系的时间复杂度为O(N)而上述两种优化方案复杂度均为O(logN)但并不意味着效率一样只是效率的级数一致但毕竟N和6N还是有倍数差距的。
BSPTree方式优化
在构建实体BSPTree时产生零散的三角面是合理的也是为了计算精确。目标三角面在BSPTree中进行搜寻过程中由于切割产生了很多零碎的三角面这个问题可以通过记录新产生的零碎三角面对应的原始三角ID的方式进行针对性的拟合达到消除冗余三角面的目的。
至于怎么尽可能保持BSPTree平衡可以选择与所在超平面与三角面集质心距离最近或较近的三角面作为拆分左右子树的参照三角面
参考
1.三维模型的布尔运算研究 2.几何算法学习实践三维 3.3D网格布尔运算开源库
