2006年11月10日
カテゴリ： カテゴリ未分類
Real-Time Collision Detection という本を読んでいます。
http://www.realtimecollisiondetection.net/
12.5.2 Convex Decomposition of Polygons
ポリゴンの凸分割。先に示された通り光線および四辺形の間の交差判定は三角形に対するものより高価になりません。したがって衝突用幾何形状は四辺形あるいは凸多面体によって構成されることもあります。
単純なポリゴンの三角形分割は直接的ですが凸ポリゴンの集合へ分解することはより複雑になります。最小の凸切片に分解しようとした場合には追加の頂点(シュタイナー点(Steiner points))が必要かもしれません。
凸分解のための単純なアルゴリズムが Hertel と Mehlhorn によって作成されていてこれは三角形分割から開始し各対角線を一回につき一度考慮します。対角線が凹頂点を生成することなしに除去できる場合は除去され、そうでない場合は次の対角線の処理を行います。本文では疑似コードの例が示されています。
三角形分割のアルゴリズムは、より良い分割を生成するように2つの凸頂点に接続している対角線よりも優先して少なくとも1つの凹頂点につながるようにアルゴリズムを改善します。
http://www.realtimecollisiondetection.net/
12.5.2 Convex Decomposition of Polygons
ポリゴンの凸分割。先に示された通り光線および四辺形の間の交差判定は三角形に対するものより高価になりません。したがって衝突用幾何形状は四辺形あるいは凸多面体によって構成されることもあります。
単純なポリゴンの三角形分割は直接的ですが凸ポリゴンの集合へ分解することはより複雑になります。最小の凸切片に分解しようとした場合には追加の頂点(シュタイナー点(Steiner points))が必要かもしれません。
凸分解のための単純なアルゴリズムが Hertel と Mehlhorn によって作成されていてこれは三角形分割から開始し各対角線を一回につき一度考慮します。対角線が凹頂点を生成することなしに除去できる場合は除去され、そうでない場合は次の対角線の処理を行います。本文では疑似コードの例が示されています。
三角形分割のアルゴリズムは、より良い分割を生成するように2つの凸頂点に接続している対角線よりも優先して少なくとも1つの凹頂点につながるようにアルゴリズムを改善します。
お気に入りの記事を「いいね！」で応援しよう
【毎日開催】
15記事にいいね！で1ポイント
PR
キーワードサーチ
▼キーワード検索
大鳥居.
人生ゲーム
コメント新着
© Rakuten Group, Inc.
