我将3D三角形夹在3D轴对齐边界框(AABB)上,以获得AABB中包含的三角形的最大平面多边形。我的裁剪算法是C.Ericson的实时碰撞检测中所述的鲁棒(例如,裁剪平面的厚度有限)Sutherland-Hodgman算法的(略有修改)版本。我将三角形裁剪成AABB的6个平面中的每个平面。

为了避免堆(取消)分配,我预先为堆栈的所有顶点在堆栈上分配了固定大小的点缓冲区。获得平面多边形。我现在的问题是:将三角形相对于AABB修剪后,一个顶点可以获得的最大顶点数是多少?

基于控制流,在多边形平面修剪期间,每个检查的顶点都可以产生两个顶点。因此$ 3 * 2 ^ 6 $个顶点。由于对称,这变成$ 3 * 2 ^ 3 = 24 $个顶点。但是,在实践中,我总是获得较少的顶点。

#1 楼

有趣的是,几年前,我在Math.SE上问了这个确切的问题:三角形与盒子相交的顶点的最大数量。

答案是9个顶点,因为6个平面中的每一个框可以切掉多边形的一个角,将一个顶点替换为两个顶点。所以3个顶点+ 6个因修剪而增加的顶点= 9个。