3

在处理了将 Bezier 补丁转换为三角形之后，我需要进行二进制空间分区，以便使用 Painter 算法绘制投影的三角形。

我已经实现了来自 Wikipedia 的算法，对数学有很大帮助。

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

所以我想我需要像苹果核一样排列的分区平面：所有平面都通过 y 轴的线。但我有点偏离书本，你知道吗？分割茶壶的最佳方法是什么？

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

编辑：额外的杂耍以避免 dictstackoverflow。此处提供完整程序（需要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

输出：
茶壶 3x3split +bsp-三角形

4

3 回答 3

0

BSP 是为类似 Quake 的游戏中的关卡等几何图形而发明的，它可能难以用于某些特定的几何图形集。BSP 使用现有的三角形之一来分割你的关卡，所以想象一下当你想在球体上使用它时它会如何表现......

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

如果你真的需要在这里使用 BSP 树，那么你应该仔细选择你的三角形。我不理解您的所有代码，但我在这里看不到这部分。只需遍历当前树分支中的所有三角形，并为每个三角形计算它前面和后面的三角形数量。具有相似数量的前三角形和后三角形通常是用作分割平面的最佳平面。

于 2013-02-11T13:50:21.487 回答
0

我并没有完全做一个八叉树，但我修改了 bsp-tree 构建器以使用一个明确的平面列表，我用轴对齐的平面填充了这些平面，切割空间 -4 < x,y,z < 4。

/planelist [
    0 .2 4 { /x exch def
        [ 1 0 0 x ]
        [ 1 0 0 x neg ]
        [ 0 1 0 x ]
        [ 0 1 0 x neg ]
        [ 0 0 1 x ]
        [ 0 0 1 x neg ]
    } for
] def

它是绿色的

此处提供 Postscript 程序（需要mat.ps）。

较浅的绿色工件是在构建 bsp 期间显示的“预览”的结果。构建完成后，后续页面（图像）会快速绘制，并且没有伪影，因为相机围绕茶壶旋转。

主体与喷口和把手（未从这个角度显示）的连接仍然需要工作。

随着 bsp 的表现更好，背面剔除并不是绝对必要的。但它使预览更好。

于 2013-02-23T08:02:46.463 回答
0

改进此图像的 BSP 的另一种方法是使用分层分解。茶壶不仅仅是一堆贝塞尔曲面，它有一些描述主体的表面，还有一些描述把手、壶嘴、盖子（底部？）的表面。

所以树的前几层应该是顶层部分。把手是在身体前面还是后面？喷口在身体前面吗？这些问题的答案将是画家算法的有用指南。

于 2019-05-22T20:36:05.420 回答