Bezier Patches如何在犹他州茶壶中工作？

Question

我过早地发布了一个代码高尔夫挑战来使用这个数据集(只是茶壶)绘制犹他茶壶.(经过修订和发布的茶壶挑战)但是当我深入研究数据以便掀起一个小例子时,我意识到我不知道这些数据是怎么回事.我对2D中的Bezier曲线有很好的理解,实现了deCasteljau.但对于3D它的工作原理是否相同？

是! 它确实!

数据包含每个包含16个顶点的补丁.这些是如何布局的标准顺序？如果它们对应于2D曲线,则四个角点实际接触表面,其余12个是控制,对吧？

是!

我的"原始计划"是将形状简化为矩形,将它们投影到画布上,然后绘制灰色的填充形状,通过与光矢量垂直的贴片的点积计算.如果我将它简化到那么远,它甚至会看起来像茶壶吗？是否必须使用光线追踪来获得可识别的图像？

这是主观的.:-(

虽然这可能看起来像几个问题,但它们都是这一个问题的所有方面:"请,请好的Guru,在一些Bezier Patches上学习我？我需要知道什么才能画出茶壶？"

---

这是我到目前为止编写的代码.(使用此矩阵库:mat.ps)

%!
%%BoundingBox: 115 243 493 487
%-115 -243 translate

(mat.ps)run  %include matrix library

/tok{ token pop exch pop }def
/s{(,){search{ tok 3 1 roll }{ tok exit }ifelse }loop }def
/f(teapot)(r)file def
/patch[ f token pop { [ f 100 string readline pop s ] } repeat ]def
/vert[ f token pop { [ f 100 string readline pop s ] } repeat ]def
%vert == patch == %test data input

/I3 3 ident def      % 3D identity matrix
/Cam [ 0 0 10 ] def  % world coords of camera center viewpoint
/Theta [ 0 0 0 ] def % y-rotation x-rotation z-rotation
/Eye [ 0 0 15 ] def  % eye relative to camera vp
/Rot I3 def          % initial rotation seq

/makerot {
    Theta 0 get roty        % pan
    Theta 1 get rotx matmul % tilt
    Theta 2 get rotz matmul % twist
} def

/proj {
    Cam {sub} vop  % translate to camera coords
    Rot matmul  % perform camera rotation
    0 get aload pop Eye aload pop  % extract dot x,y,z and eye xyz
    4 3 roll div exch neg          % perform perspective projection
    4 3 roll add 1 index mul
    4 1 roll 3 1 roll sub mul exch % (ez/dz)(dx-ex) (ez/dz)(dy-ey)
} def


/R 20 def
/H -3 def
/ang 0 def
{
    300 700 translate
    1 70 dup dup scale div setlinewidth

    /Cam [ ang sin R mul  H  ang cos R mul ] def % camera revolves around Y axis at height H, dist R
    /Theta [ ang  H R atan  0 ] def % rotate camera back to origin
    /Rot makerot def % squash rotation sequence into a matrix

    patch {
        % Four corners
        %[ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]

        % Boundary curves
        [ exch
            dup 8 get exch dup 4 get exch dup 0 get exch %curveto4

            dup 14 get exch dup 13 get exch dup 12 get exch %curveto3

            dup 7 get exch dup 11 get exch dup 15 get exch %curveto2

            dup 1 get exch dup 2 get exch dup 3 get exch %curveto1

            dup 0 get exch %moveto
        pop ]

        { 1 sub vert exch get proj } forall

        moveto
            curveto curveto curveto curveto

        stroke
        %flushpage flush (%lineedit)(r)file pop
    } forall
    pstack
    showpage

    %exit
    /ang ang 10 add def
} loop

这是最初的Newell Teapot数据集.

这是我非常糟糕的形象:

更新:bugfix.也许他们毕竟是'正常'.选择正确的角至少会形成对称的形状:

更新:边界曲线看起来更好.

Answer 1

Bi-Cubic Bezier曲面贴片是一个4x4的3D点阵列.是的,四个角落接触表面; 行是贝塞尔曲线,列也是贝塞尔曲线.但deCasteljau算法基于计算两点之间的中值,并且在3D中与2D中一样有意义.

完成上述代码的下一步是细分补丁以覆盖较小的部分.然后,上面的简单边界曲线提取成为合适的多边形网格.

首先展平补丁,直接插入顶点数据,而不是使用单独的缓存.此代码遍历补丁,查找顶点数组中的点并构造一个新的补丁数组,然后使用相同的名称重新定义.

 /patch[ patch{ [exch { 1 sub vert exch get }forall ] }forall ]def

然后我们需要deCasteljau算法来分割Bezier曲线.vop来自矩阵库,并对矢量的相应元素应用二元运算,并生成一个新的矢量作为结果.

/median { % [x0 y0 z0] [x1 y1 z1]
    {add 2 div} vop % [ (x0+x1)/2 (y0+y1)/2 (z0+z1)/2 ]
} def   

/decasteljau { % [P0] P1 P2 P3  .  P0 P1' P2' P3'  P3' P4' P5' P3
    {p3 p2 p1 p0}{exch def}forall
    /p01 p0 p1 median def
    /p12 p1 p2 median def
    /p23 p2 p3 median def
    /p012 p01 p12 median def
    /p123 p12 p23 median def
    /p0123 p012 p123 median def
    p0 p01 p012 p0123  % first half-curve
    p0123 p123 p23 p3  % second half-curve
} def   

然后进行一些堆栈操作以应用于补丁的每一行,并将结果组合成2个新补丁.

/splitrows { % [b0 .. b15]  .  [c0 .. c15] [d0 .. d15] 
    aload pop % b0 .. b15
    4 {                          % on each of 4 rows
        16 12 roll decasteljau   % roll the first 4 to the top
        8 4 roll                 % exch left and right halves (probably unnecessary)
        20 4 roll                % roll new curve to below the patch (pushing earlier ones lower)
    } repeat
    16 array astore              % pack the left patch
    17 1 roll 16 array astore    % roll, pack the right patch
} def

丑陋的实用程序允许我们重用列的行代码.编写此过程需要堆栈注释,因此可能需要读取它.n j roll滚动n个元素(向左),j次; ==第n个元素上方的前j个元素(从1开始计算).因此n稳步下降,选择在那里把元素,和j选择把哪一个元素有(拖动其他一切与它).如果bind应用,则此过程将比基于字典的过程快得多.

% [ 0  1  2  3
%   4  5  6  7
%   8  9 10 11
%  12 13 14 15 ]
/xpose {
    aload pop % 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    15 12 roll % 0 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3
    14 11 roll % 0 4 8 9 10 11 12 13 14 15 1 2 3 5 6 7
    13 10 roll % 0 4 8 12 13 14 15 1 2 3 5 6 7 9 10 11

    12 9 roll % 0 4 8 12 1 2 3 5 6 7 9 10 11 13 14 15
    11 9 roll % 0 4 8 12 1 5 6 7 9 10 11 13 14 15 2 3
    10 8 roll % 0 4 8 12 1 5 9 10 11 13 14 15 2 3 6 7
    9 7 roll % 0 4 8 12 1 5 9 13 14 15 2 3 6 7 10 11

    8 6 roll % 0 4 8 12 1 5 9 13 2 3 6 7 10 11 14 15
    7 6 roll % 0 4 8 12 1 5 9 13 2 6 7 10 11 14 15 3
    6 5 roll % 0 4 8 12 1 5 9 13 2 6 10 11 14 15 3 7
    5 4 roll % 0 4 8 12 1 5 9 13 2 6 10 14 15 3 7 11
    4 3 roll % 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15
    16 array astore
} def
% [ 0 4  8 12
%   1 5  9 13
%   2 6 10 14
%   3 7 11 15 ]

/splitcols {
    xpose
    splitrows
    xpose
} def

然后将这些函数应用于补丁数据.再次,每次重新定义补丁.

/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitcols }forall ]def
/patch[ patch{ splitcols }forall ]def

这使得能够处理较小的片段.

添加可见性测试.

/visible { % patch  .  patch boolean 
    dup % p p
    dup 3 get exch dup 0 get exch 12 get % p p3 p0 p12
    1 index {sub} vop % p p3 p0 v0->12
    3 1 roll {sub} vop % p v0->12 v0->3
    cross /normal exch def
    dup
    [ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]
    { Cam {sub} vop normal dot 0 ge } forall
    %add add add 4 div 0 lt
    or or or
} def

生产

更新:测试是倒退.

更新:测试没用!您可以从图像中看到底部部件没有朝外,当然,背面剔除不会阻止手柄穿过底部.这需要隐藏表面移除.由于Postscript不支持Z缓冲区,我想它必须是一个二进制空间分区.所以它又回到了我的书中.

更新:添加模型 - >世界变换以使事物直立.

/Model -90 rotx def % model->world transform

/proj {
    Model matmul 0 get             % perform model->world transform
    Cam {sub} vop                  % translate to camera coords
    ...

制作这个.

到目前为止完成计划.(使用矩阵库:mat.ps.)在ghostscript中,您可以通过按住来查看动画旋转[enter].

    %!
    %%BoundingBox: 109 246 492 487
    %-109 -246 translate

    (mat.ps)run  %include matrix library
    (det.ps)run  %supplementary determinant function

    /tok{ token pop exch pop }def
    /s{(,){search{ tok 3 1 roll }{ tok exit }ifelse }loop }def
    /f(teapot)(r)file def
    /patch[ f token pop { [ f 100 string readline pop s ] } repeat ]def
    /vert[ f token pop { [ f 100 string readline pop s ] } repeat ]def
    /patch[ patch{ [exch { 1 sub vert exch get }forall ] }forall ]def
    %vert == patch == %test data input flush quit

    /I3 3 ident def      % 3D identity matrix
    /Cam [ 0 0 10 ] def  % world coords of camera center viewpoint
    /Theta [ 0 0 0 ] def % y-rotation x-rotation z-rotation
    /Eye [ 0 0 15 ] def  % eye relative to camera vp
    /Rot I3 def          % initial rotation seq

    /Model -90 rotx def % model->world transform

    /makerot {
            Theta 0 get roty        % pan
            Theta 1 get rotx matmul % tilt
            Theta 2 get rotz matmul % twist
    } def

    /proj {
            Model matmul 0 get             % perform model->world transform
            Cam {sub} vop  % translate to camera coords
            Rot matmul  % perform camera rotation
            0 get aload pop Eye aload pop  % extract dot x,y,z and eye xyz
            4 3 roll div exch neg          % perform perspective projection
            4 3 roll add 1 index mul
            4 1 roll 3 1 roll sub mul exch % (ez/dz)(dx-ex) (ez/dz)(dy-ey)
    } def

    /median { % [x0 y0 z0] [x1 y1 z1]
            {add 2 div} vop % [ (x0+x1)/2 (y0+y1)/2 (z0+z1)/2 ]
    } def

    /decasteljau { % [P0] P1 P2 P3  .  P0 P1' P2' P3'  P3' P4' P5' P3
            {p3 p2 p1 p0}{exch def}forall
            /p01 p0 p1 median def
            /p12 p1 p2 median def
            /p23 p2 p3 median def
            /p012 p01 p12 median def
            /p123 p12 p23 median def
            /p0123 p012 p123 median def
            p0 p01 p012 p0123
            p0123 p123 p23 p3
    } def

    /splitrows { % [b0 .. b15]  .  [c0 .. c15] [d0 .. d15]
            aload pop % b0 .. b15
            4 {
                    16 12 roll decasteljau
                    %8 4 roll
                    20 4 roll
            } repeat
            16 array astore
            17 1 roll 16 array astore
    } def

    /xpose {
            aload pop % 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
            15 12 roll % 0 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3
            14 11 roll % 0 4 8 9 10 11 12 13 14 15 1 2 3 5 6 7
            13 10 roll % 0 4 8 12 13 14 15 1 2 3 5 6 7 9 10 11

            12 9 roll % 0 4 8 12 1 2 3 5 6 7 9 10 11 13 14 15
            11 9 roll % 0 4 8 12 1 5 6 7 9 10 11 13 14 15 2 3
            10 8 roll % 0 4 8 12 1 5 9 10 11 13 14 15 2 3 6 7
            9 7 roll % 0 4 8 12 1 5 9 13 14 15 2 3 6 7 10 11

            8 6 roll % 0 4 8 12 1 5 9 13 2 3 6 7 10 11 14 15
            7 6 roll % 0 4 8 12 1 5 9 13 2 6 7 10 11 14 15 3
            6 5 roll % 0 4 8 12 1 5 9 13 2 6 10 11 14 15 3 7
            5 4 roll % 0 4 8 12 1 5 9 13 2 6 10 14 15 3 7 11
            4 3 roll % 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 14
            16 array astore
    } def

    /splitcols {
            xpose
            splitrows
            xpose exch xpose
    } def

    /patch[ patch{ splitrows }forall ]def
    /patch[ patch{ splitrows }forall ]def
    /patch[ patch{ splitrows }forall ]def
    /patch[ patch{ splitrows }forall ]def
    /patch[ patch{ splitcols }forall ]def
    /patch[ patch{ splitcols }forall ]def

    /color {normal light dot 1 add 4 div
%1 exch sub
setgray} def

    /visible { % patch  .  patch boolean
            dup % p p
            dup 3 get exch dup 0 get exch 12 get % p p3 p0 p12
            1 index {sub} vop % p p3 p0 v0->12
            3 1 roll {sub} vop % p v0->12 v0->3
            cross /normal exch def
            dup
            [ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]
            { Cam {sub} vop normal dot 0 ge } forall
            %add add add 4 div 0 lt
            or or or
    } def

    /drawpatch {

            % Four corners
            %[ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]

            visible {

                    [ exch
                            % control rows
                            %dup 4 get exch dup 5 get exch dup 6 get exch dup 7 get exch
                            %dup 11 get exch dup 10 get exch dup 9 get exch dup 8 get exch

                            % control columns
                            %dup 1 get exch dup 5 get exch dup 9 get exch dup 13 get exch
                            %dup 14 get exch dup 10 get exch dup 6 get exch dup 2 get exch

                            % Boundary curves
                            dup 8 get exch dup 4 get exch dup 0 get exch %curveto4
                            dup 14 get exch dup 13 get exch dup 12 get exch %curveto3
                            dup 7 get exch dup 11 get exch dup 15 get exch %curveto2
                            dup 1 get exch dup 2 get exch dup 3 get exch %curveto1
                            dup 0 get exch %moveto
                    pop ]

                    { proj } forall

                    moveto curveto curveto curveto curveto
                    %moveto lineto lineto lineto lineto lineto lineto lineto closepath
                    %moveto lineto lineto lineto lineto lineto lineto lineto closepath

                    stroke
                    %flushpage flush (%lineedit)(r)file pop

            }{
                    pop
            }ifelse

    } def

    /R 20 def
    /H -3 def
    /ang 10 def
    {
            300 700 translate
            1 70 dup dup scale div setlinewidth

            % camera revolves around Y axis at height H, dist R
            /Cam [ ang sin R mul  H  ang cos R mul ] def
            /Theta [ ang  H R atan  0 ] def   % rotate camera back to origin
            /Rot makerot def        % squash rotation sequence into a matrix

            patch {
                    drawpatch
            } forall
            pstack
            showpage

            %exit
            /ang ang 10 add def
    } loop