3

ベジエ パッチを三角形に変換する処理を行った後、ペインターのアルゴリズムを使用して投影された三角形を描画するために、バイナリ スペース パーティションを実行する必要があります。

ウィキペディアからアルゴリズムを実装し、数学に大いに役立ちました。

しかし、チャーリー・ブラウンの木を作っているのです! つまり、ほとんどのノードには完全に空のブランチが 1 つあります。全体の戦略はすべて間違っています。ティーポットは本質的に球形であるため、形状全体は、特定のコンポーネント三角形の 1 つの「側面」にのみ存在します。

だから私は、リンゴの芯のように配置された平面を分割する必要があると考えています:すべてが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-triangles

4

3 に答える 3

0

BSPは、Quakeのようなゲームのレベルなどのジオメトリ用に発明されたものであり、特定のジオメトリセットには使用が難しい場合があります。BSPは、既存の三角形の1つを使用してレベルを分割するため、球体で使用する場合の動作を想像してみてください...

ティーポットの場合、既存の三角形に沿ってジオメトリを分割する必要がないOCTreeを使用すると、より良い結果を得ることができます。しかし、画家のアルゴリズムでどれだけうまく機能するかはわかりません。

ここで本当にBSPツリーを使用する必要がある場合は、三角形を慎重に選択する必要があります。私はあなたのコードのすべてを理解していませんが、この部分はここにはありません。現在の木の枝にあるすべての三角形を繰り返し処理し、それぞれについて、その前と後ろにある三角形の数を計算します。通常、前面の三角形と背面の三角形の数が同じであるものが、分割平面として使用するのに最適です。

于 2013-02-11T13:50:21.487 に答える
0

私は八分木を完全にはしませんでしたが、スペース-4 <x、y、z<4をスライスする軸整列平面で埋めた平面の明示的なリストを使用するようにbsp-treeビルダーを変更しました。

/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 に答える