dr_*_*_rk 14 c++ graphics visualization mesh computational-geometry
切片3D网格的正确方法是什么？网格都是闭合曲面,切片需要是网格内部的二进制图像.因此,例如,表示球体和切片图像的网格是实心圆的网格.
我正在寻找一个可以集成到我当前的C++项目中的软件库或算法.
Den*_*nis 21
我的开源游戏库包含网格切片的实现.它适用于Irrlicht api,但可以通过适度的努力重写为使用不同的API.您可以使用BSD许可条款下的代码,或从中学习您自己的工具.
请参阅此文件中的 MeshTools :: splitMeshZ以获取网格切片的实现.
如果您只是想知道算法,这里是我所做的高级描述:
我最初想过使用轴对齐的边界框来指定切割网格的位置.这是有问题的,因为它引入了许多特殊情况.例如,穿过盒子角落的边缘可以分成三块而不是两块.
使用平面将网格切割成左侧网格和右侧网格可减少特殊情况的数量,因为边缘位于平面的一侧或另一侧,或者它与平面交叉,因此切入正好两个件.
可以简单地通过切割一次,取出所得到的网格之一并在另一个位置再次切割它来进行任何所需的切割配置,等等.特别是在您在该部分中描述的情况下,可以通过将球体的一半切掉,将平面移动少量并切掉另一半而仅留下一个薄带来从球体切割圆圈.(您不能使用我编写的代码将网格切割到几乎没有深度,但您可以将网格切割为您设置浮点平等阈值的任何内容.我认为我在代码中任意选择了0.001.)
使用类似的逻辑,可以使用固定平面实现切割平面的任何期望角度; 您只需要转换网格以相对于固定切割平面旋转它,然后将结果转换回来.(对于我的游戏,我只需要垂直于XY平面的切割,所以为了简单起见,我只允许设置切割的Z值,并假设切割位于Z位置.)
好了,既然我们已经简化了问题,那么算法并不是那么糟糕:
开始条件:你有一个切割平面.你有一组源三角形.您有两组目标多边形(不是三角形;可以通过切割三角形生成四边形).两个目标集称为左和右.
过程:迭代三角形的三个点.计算小于切割平面的点数.我会称那些小于切割平面左侧的那些和那些大于切割平面右侧的那些.只有少数案例:
剩下两点,一点是右.如果你握住一个三角形的边缘并将其切割到另外两个边缘,那么你将保持一个梯形.将一个四边形放在由手中的两个点组成的左侧组中,加上两个穿过切口的点.在右侧设置一个三角形(上面的镜像图像).
完成后,通过在最短的部分添加链接将四边形转换为三角形.
而已.这是基本的算法.实际代码处理一些更多的情况,例如,如果边缘与切割完全相等,如果三角形正好在边缘上,不添加退化多边形(例如,没有主体的点),等等.
杂项.问题(所有内容都包含在链接代码中):
LERP的边缘越过切割平面的位置不要过于复杂.它不需要完全线性插值,它实际上只是Highschool代数II:上升超过运行,乘以比率
有利的是,缓存生成的(LERP)点,使得在未切割网格中共享顶点的三角形将共享切割网格中的相应新顶点.
如果要保留顶点共享,并且使用三角形索引缓冲区,那么在第一次生成要放入"左"和"右"集的形状时,遗憾的是您还不知道索引.我使用一个名为"PossibleVertex"的类来表示未来的三角形索引号.
如果要显示网格,缠绕顺序很重要.仔细考虑如何对其进行编码可以确保生成的多边形使用与它们来自的三角形相同的绕线顺序.在对四边形进行三角测量时,这尤其棘手.我不记得细节,但它们都是在链接代码中处理的.
对于我的游戏,我想制作一个连接两个切割网格的扁平带子.这就是为什么splitMeshZ会产生3个网格,而不仅仅是两个网格.您可以使用中间网格,或者只是忽略它.