如何对犹他茶壶进行空间分区? [英] How to do a space-partitioning of the Utah Teapot?

问题描述

已经处理了将贝塞尔补丁转换为三角形，我需要做一个二元空间分区，以便使用画家算法绘制投影的三角形.

Having dealt with converting the Bezier Patches into triangles, I need to do a Binary Space Partition in order to draw the projected triangles using the Painter's Algorithm.

我已经用很多数学帮助.

但它正在制作一棵查理布朗树！也就是说，大多数节点都有一个完全空的分支.整个策略都是错误的.由于茶壶基本上是球形的，因此整个形状仅位于任何特定组件三角形的一侧".

But it's making a Charlie Brown tree! That is most of the nodes have one branch completely empty. The whole strategy is all wrong. Since the teapot is essentially spherical, the entire shape is only on one "side" of any particular component triangle.

所以我想我需要更像苹果核的分区平面:所有平面都通过 y 轴的线.但我有点离开书本，你知道吗?茶壶的最佳分区方式是什么?

So I'm thinking I need partitioning planes arranged more like an apple-corer: all passing through the line of the y-axis. But I'm kind of going off book, you know? What's the best way to partition the teapot?

这是我的 bsp 树生成器.它使用链接问题中发布的其他功能.

Here's my bsp-tree generator. It uses other functions posted in the linked question.

额外的杂耍以避免dictstackoverflow.完整的程序可用此处(需要mat.ps 和 茶壶).数值输出显示了正在构建的树节点的深度.

Extra juggling to avoid dictstackoverflow. Complete program available here (requires mat.ps and teapot). The numerical output shows the depth of the tree node under construction.

% 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 使用现有的三角形之一来分割你的关卡，所以想象一下当你想在一个球体上使用它时它的行为......

BSP was invented for geometries like levels in Quake-like games and it may be hard to use for some specific geometry sets. BSP uses one of the existing triangles to split your level, so just imagine how it would behave when you want to use it on a sphere...

对于茶壶，您可以使用 OCTree 获得更好的结果，它不需要沿现有三角形拆分几何图形.但我不确定它与 Painter 算法的配合效果如何.

For the teapot you could get better results using OCTree, which doesn't need to split your geometry along existing triangles. But I'm not sure how well does it work with the Painter Algorithm.

如果你真的需要在这里使用 BSP 树，那么你应该仔细选择你的三角形.我不明白你的所有代码，但我在这里没有看到这部分.只需迭代当前树分支中的所有三角形，并为每个三角形计算它前面和后面的三角形数.前三角形和后三角形的数量相近的那个通常是最好的一个用作分割平面.

If you really need to use BSP tree here, then you should pick your triangles carefully. I don't understand all of your code but I don't see this part here. Just iterate over all triangles in your current tree branch and for each of them compute the number of triangles in front of it and at the back. The one that has similar number of front-triangles and back-triangles is usually the best one to be used as a split plane.

这篇关于如何对犹他茶壶进行空间分区?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！