处理converting the Bezier Patches into triangles之后，我需要做一个二进制空间分区，以便使用Painter's Algorithm绘制投影的三角形。
我已经用很多algorithm from Wikipedia实现了help with the math。
但是，它正在制造一棵查理·布朗树！也就是说，大多数节点的一个分支完全为空。整个策略都是错误的。由于茶壶基本上是球形的，因此整个形状仅在任何特定组件三角形的“一侧”上。
所以我在想我需要更像苹果角排列的分隔平面：所有分隔平面都通过y轴的线。但是我有点不喜欢书了，你知道吗？划分茶壶的最佳方法是什么？
这是我的bsp树生成器。它使用链接的问题中发布的其他功能。
编辑：额外的杂耍，以避免dictstackoverflow。完整的程序可用here（需要mat.ps和teapot）。数值输出显示正在构造的树节点的深度。
% helper functions to insert and remove triangles in lists
/unshift { % [ e1 .. eN ] e0 . [ e0 e1 .. eN ]
exch aload length 1 add array astore
} def
/shift { % [ e0 e1 .. eN ] . [ e1 .. eN ] e0
aload length 1 sub array astore exch
} def
/makebsp { % [ triangles ] . bsptree
count =
%5 dict %This is the tree node data structure
<</P[]/PM[]/plane[]/front[]/behind[]/F<<>>/B<<>>>>
begin
dup length 1 le{ % If 0 or 1 triangles
dup length 0 eq { % If 0 triangles
pop % discard
}{ % If 1 triangle
aload pop /P exch def % put triangle in tree node
}ifelse
}{ % length>1
shift /P exch def % P: Partitioning Polygon (triangle)
P transpose aload pop
[1 1 1] 4 array astore % make column vectors of homogeneous coords
/PM exch def
[ % Compute equation of the plane defined by P
PM 0 3 getinterval det
[ PM 0 get PM 2 get PM 3 get ] det
[ PM 0 get PM 1 get PM 3 get ] det
PM 1 3 getinterval det 3 mul
] /plane exch def
% iterate through remaining triangles, testing against plane, adding to lists
/front [] def
/behind [] def
{ %forall [P4 P5 P6] = [[x4 y4 z4][x5 y5 z5][x6 y6 z6]]
/T exch def
T transpose % [[x4 x5 x6][y4 y5 y6][z4 z5 z6]]
{aload pop add add} forall % (x4+x5+x6) (y4+y5+y6) (z4+z5+z6)
plane 2 get mul 3 1 roll % z|C| (x) (y)
plane 1 get mul 3 1 roll % y|B| z|C| (x)
plane 0 get mul % y|B| z|C| x|A|
plane 3 get add add add % Ax+By+Cz+D
0 le { /front front
}{ /behind behind
} ifelse
T unshift def
} forall
%front == ()= behind == flush (%lineedit)(r)file pop
% recursively build F and B nodes from front and behind lists
%/F front makebsp def
front currentdict end exch
makebsp
exch begin /F exch def
%/B behind makebsp def
behind currentdict end exch
makebsp
exch begin /B exch def
/front [] def
/behind [] def
} ifelse
currentdict end
} def
输出：
最佳答案
BSP是针对类似于Quake的游戏中的关卡等几何图形而发明的，对于某些特定的几何图形集可能很难使用。 BSP使用现有的三角形之一来拆分您的关卡，所以请想象一下，当您想在球体上使用它时，它的行为如何……
对于茶壶，使用OCTree可以获得更好的结果，它不需要将几何图形沿现有三角形进行拆分。但是我不确定它与Painter算法的配合效果如何。
如果您确实需要在此处使用BSP树，则应谨慎选择三角形。我不理解您的所有代码，但在这里看不到这一部分。只需遍历当前树枝中的所有三角形，并为每个三角形计算其前面和后面的三角形数量。具有相似数量的前三角形和后三角形的通常是最好的分割平面。