如何做一个空间分区犹他州茶壶的？ [英] How to do a space-partitioning of the Utah Teapot?

问题描述

经处理的<一个href="http://stackoverflow.com/questions/14558814/how-do-bezier-patches-work-in-the-utah-teapot">converting贝塞尔补丁成三角形的，我需要做的二进制空间分割，以便使用画家算法得出的预测三角形。

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。这里完整的程序提供（需要<一个HREF =HTTP：//$c$c.google.com/p/xpost/downloads/detail名= mat.ps相对=nofollow> 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

输出：

Output:

推荐答案

BSP被发明了像地震般的游戏水平的几何形状和它可能很难用于一些特定的几何图形集。 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...

有关紫砂壶你可以得到使用八叉树，它不需要沿着现有的三角形分割你的几何更好的结果。但我不知道它是如何与画家算法的工作。

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树在这里，那么你应该仔细选择你的三角形。我不明白你的所有code，但我不认为这部分在这里。只是遍历所有的三角形在当前的树枝，并为每个计算在它的前面和后面的三角形数量。一个具有类似数目的前三角形和后端三角形通常是最好的一个被用来作为一个分割面

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屋！