4

三角形のセットが与えられます。各三角形は点のトリプレットです。各点は実数の 3 要素です。各三角形の表面法線を計算できます。ただし、グーロー シェーディングの場合は、頂点法線が必要です。したがって、各頂点にアクセスして、その頂点を共有する三角形を調べ、それらの表面法線を平均して、頂点法線を取得する必要があります。

これを達成するための最も効率的なアルゴリズムとデータ構造は何ですか?

素朴なアプローチはこれです（疑似pythonコード）：

MAP = dict()
for T in triangles:
  for V in T.vertices:
    key = hash(V)
    if MAP.has(key):
      MAP[key].append(T)
    else:
      MAP[key] = []
      MAP[key].append(T)

VNORMALS = dict()
for key in MAP.keys():
  VNORMALS[key] = avg([T.surface_normal for T in MAP[key]])

より効率的なアプローチはありますか？

4

2 に答える 2

4

各三角形にアクセスし、各三角形の法線を計算し、それらを各コーナー頂点の頂点法線に追加します。
最後に、各頂点の法線を正規化します。

次に、少なくとも三角形を 1 回トラバースするだけでよく、法線/頂点を 1 つだけ保存します。

于 2012-11-03T02:39:28.657 に答える
3

各頂点は 1 つ以上の面に属します (通常は三角形、場合によっては四角形です。この回答では三角形を使用します)。

他の三角形に接続されていない三角形は「平滑化」できません。平らです。面に隣接面がある場合にのみ、面を一緒にスムージングする必要があります。

複数の面が接する頂点の場合、これらの各面の法線を計算します。2 つのベクトルの外積は、必要な直交 (法線) ベクトルを返します。

A --- B
  \ /
   C

v1 = B - A
v2 = C - A
normal = v1 cross v2

これらのベクトルをすべての面で一貫して計算するように注意してください。そうしないと、法線が必要な方向に対して負の方向になる可能性があります。

したがって、複数の面が交わる頂点で、面の法線を合計し、結果のベクトルを正規化し、それを頂点に適用します。

メッシュの一部をスムージングし、他の部分をスムージングしない場合があります。わかりやすい例は、三角形でできた円柱です。円柱の丸い面は滑らかになりますが、鋭い尾根の周りの頂点で平らな端から三角形を考えると、奇妙に見えます。これを回避するには、計算対象の面の法線から大きく外れている面の法線を無視するルールを導入できます。

編集実際のアルゴリズムについては説明していませんが、Gourad shading を計算するためのテクニックを示す非常に優れたビデオがあります。

Three.js のソースを見てみたいと思うかもしれません。具体的にはcomputeVertexNormals機能。シャープ エッジの維持はサポートされません。アルゴリズムの効率は、プリミティブをモデル化する方法に大きく依存します。

于 2013-02-07T23:29:32.273 に答える