2026
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2006年11月の記事
全30件 (30件中 1-30件目)
1
-
Real-Time Collision Detection 13.6.1 Type-Based Alias Analysis
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.6.1 Type-Based Alias Analysis型に基づいたエイリアスの分析。いくつかの C/C++ コンパイラは型に基づいたエイリアスの分析を利用しています。言語規格上、同じ互換性のある型を持っている2つのオブジェクトに限りお互いにエイリアスになる可能性があり、メモリには1つの型のみが関連づけられているという性質を利用します。この機能はvoid foo( float* v, int* n){ for(int i =0; i
2006年11月30日
コメント(0)
-
Real-Time Collision Detection 13.6 Aliasing
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.6 Aliasingエイリアシング。int n;int*p1 = &n;int*p2 = &n;のようなとき p1, p2 の両方が変数 n のエイリアスとなります。コンパイラが2つのポインタがお互いにエイリアスであることを推論できなかった場合に最適化を妨げる可能性があります。コードの中に不必要なロード命令が残りコードと関数のスタックフレームの両方が膨張してしまいます。ここではポインタを2つ渡してマトリックス演算を行うような例が挙げられています。引数をそのまま使う場合はエイリアスの可能性があるのでロード命令を複数回行うことになります。回避例として入力引数を関数内の自動変数にコピーして使う例が挙げられています。これでエイリアシングの問題を避けることができてレジスタの多いプロセッサの場合はすべてがレジスタに乗り高速に演算できます。エイリアスに関して最適化に悪い影響を及ぼすような抽象化は抽象化ペナルティ問題(abstraction penalty problem)として知られています。
2006年11月29日
コメント(0)
-
Real-Time Collision Detection 13.5.2 Amortized Predictive Linearization Caching
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.5.2 Amortized Predictive Linearization Caching予測される線形化キャッシングの償却。ここではより高度なキャッシュの仕組みとしてワールドの幾何形状を表現している静的なツリー構造を考えてみます。衝突のクエリがプレイヤーに隣接している球状のボリュームに対して発行されるとすると、このボリュームの範囲内にあるすべてのポリゴンデーターを線形化されている形式の中にキャッシングすることでプレイヤーが球から離れない限りキャッシュのデータのみを判定すれば良いということになります。ただ、高速に移動する場合はあまり効果的ではないですね。
2006年11月28日
コメント(0)
-
Real-Time Collision Detection 13.5.1 Cached Linearization Example
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.5.1 Cached Linearization Exampleキャッシュされている線形化の例。ここでは葉ノードが多数の三角形を含んでいるツリー型のデータ構造を例にあげて説明しています。ソースコードでの具体例を示しながらソフトウェアキャッシュの例を示しています。すでにキャッシュにあるかどうかを調べてなければキャッシュするような単純な例ですね。
2006年11月27日
コメント(0)
-
Real-Time Collision Detection 13.5 Software Caching
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.5 Software Cachingソフトウェアキャッシング。データーの線形化のためにアプリケーション側にソフトウェアキャッシュを実装することは有益です。ここでいう線形化とは隣接している複数のブロックに分散しているデーターにアクセスする際にデーターの再配置を行い空間的な局所性を高めることで性能を向上させることを意味しています。衝突用データーを圧縮しておき必要に応じて展開してキャッシュに入れ識別番号(id)をキーにして引けるようにしておくというわけです。ソフトウェアキャッシュの別の利点としてキャッシュで使用されるデーターの形式が統一化された形式としてすべてのコードにとって処理の対象とすることができることです。
2006年11月26日
コメント(0)
-
Real-Time Collision Detection 13.4.3 Cache-Obliviousness
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.4.3 Cache-Obliviousnessキャッシュを記憶しない方法。あるアーキテクチャに対して最適化するのではなく任意の様々なキャッシュ設定を対象にうまく実行できるように構築されています。ファンネルソート(funnelsort)や van Emde Boas の配置といった手法があるようです。
2006年11月25日
コメント(0)
-
Real-Time Collision Detection 13.4.2 A Compact AABB Tree
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.4.2 A Compact AABB Tree緻密なAABBツリー。親AABBの境界を2つの子のAABBから再構築するために6つの追加面情報に加えて親の側面がどの子に継承されているかの情報が必要になります。また6つの追加の面の1つによって決定される側面がどの子なのか示すためにも6ビットは必要になります。ここでは新しい面の値を浮動少数点にするのをやめて親の側面の比率を定義することで8ビットで量子化する例が示されています。残りのビットもノードが葉ノード化節点ノードかを示すために使用したり子ノードのポインタもインデックスで示したりします。
2006年11月24日
コメント(0)
-
Real-Time Collision Detection 13.4.1 A Compact Static k-d Tree
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.4.1 A Compact Static k-d Tree緻密で静的な kd ツリー。kd ツリーのノードは節点ノードか葉ノードかを特定するための情報を持つ必要がありさらに節点の場合は分割軸と分割する点の座標値です。またはノードの場合はデーターの配列に対するポインタあるいはインデックスなどが必要です。ここでは分割の値は浮動少数点として与えられていると考えます。23ビットの浮動少数点の可数部における位の低いビットの変更はそれほど影響ありません。したがって下位2ビットにノードの種類の情報を格納することができます。キャッシュラインが64バイト幅を持っていることを仮定して幅優先で扱う例が本文でソースコードを含めて開設されています。
2006年11月23日
コメント(0)
-
Real-Time Collision Detection 13.4 Cache-Aware Data Structures and Algorithms
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.4 Cache-Aware Data Structures and Algorithmsキャッシュを考慮したデータ構造とアルゴリズム。アルゴリズムおよびデータ構造をある固有のプラットフォームに向けて設計することでキャッシュを考慮した設計を行うことができます。この章で、量子化による容量削減あるいは緻密でキャッシュ効率の良い kd ツリーの例を挙げその後緻密な AABB の例を示しているようです。いくつかの異なるアーキテクチャで動作させるためにキャッシュを記録しない(cache oblivious)なコードを実装します。
2006年11月22日
コメント(0)
-
Real-Time Collision Detection 13.3.3 Prefetching and Preloading
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.3.3 Prefetching and Preloadingプリフェッチとプリロード。キャッシュされていないメモリにアクセスすることで失速するのを防ぐためにプリフェッチと呼ばれる仕組みがあります。これはあるキャッシュラインをキャッシュにロードするようにCPUに指示を出すことができます。線形の構造体の場合プリフェッチの命令は効果的です。非線形の場合の対処法としては可能な分岐をこまめにプリフェッチすることです。本文ではこのあたり簡単なコード例を示しながら解説されています。メモリからのフェッチの長い時間に対処する別の仕組みとしてノンブロッキングロード(nonblocking loads)を利用することができます。これでCPUはキャッシュミスの後で命令の実行を続けることができるようになります。メモリがロードされるレジスタにデーターが準備できる前にアクセスした際だけ失速することになります。
2006年11月21日
コメント(0)
-
Real-Time Collision Detection 13.3.2 Quantized and Compressed Vertex Data
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.3.2 Quantized and Compressed Vertex Data頂点データの量子化と圧縮。衝突判定のコードの場合頂点を浮動小数点ではなく16ビットの整数値に量子化することも有効です。さらにはx,yを11ビットで表しzを10ビットで表現することで１頂点を32ビットに収める方法も可能です。また頂点を表現するために１つ前からの頂点からの変位を利用し記憶容量を減らす手法もあります。これは頂点のAABBを計算しその中心を固定された原点とみなしその原点からの頂点の変位を数ビットで記録するというわけです。これは原点からの変位に応じて良い圧縮比を計算するようなものです。本文では具体例を示しわかりやすく開設されています。また空間分割との組み合わせでデータを量子化した形式で葉ノードに保存することも可能です。葉ノードは一般的にはワールドのごく小さな部分の範囲を網羅するだけで良いからです。展開にかかるコストはデータ容量の節約だけでなくキャッシュ効率の面からみても効果的です。
2006年11月20日
コメント(0)
-
Real-Time Collision Detection 13.3.1 Structure Optimizations
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.3.1 Structure Optimizations構造体の最適化。３つの最適化が考えれます。・構造体全体のサイズを小さくする。・アクセスの多いものなどフィールドの順序を変える。・構造体を熱い部分と冷めた部分に分割する。多くのプラットフォームでは大抵そのフィールドの中で大きさが最も大きいフィールドのバイト数の倍数になるようにパディングされます。したがってメンバ変数を大きさの小さい順にソートすることでパディングのためのメモリを余分に消費されるのを防ぐことができます。構造体のサイズを減らすためには以下のような手法もあります。・すでに保存されている値から容易に計算できる値を保存しない。・可能ならより小さい整数を使用。・ブール値からビットフィールドに変更。・インデックスのあるデータ構造はオフセットをポインタの代わりに使用する。構造体を熱い部分と冷めた部分とに分割する方法は効果的です。どこが熱いメンバなのかは後続体へのアクセス関数を作りそこで統計的なデーターをとるのが良さそうです。コンパイラーとリンカーはコードの順序を変更するのに似た原理を利用しています。
2006年11月19日
コメント(0)
-
Real-Time Collision Detection 13.3 Data Cache Optimizations
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.3 Data Cache Optimizationsデータキャッシュの最適化。データキャッシュの利用としては圧縮ではなくデータ自体の大きさを縮小させて空間的あるいは時間的な局所性を高めることによって改善が可能です。具体的にはアルゴリズムとデータ構造を再設計することによって改良されます。データーをより予測しやすい順序で線形にアクセスできるようにします。局所性を向上させるためにブロッキングと呼ばれる処理が行われることもあります。できるだけ少ないキャッシュラインに触れるようにたとえば衝突判定用のデーターをレンダリング用のデーターと分離して処理するようにします。
2006年11月18日
コメント(0)
-
Real-Time Collision Detection 13.2 Instruction Cache Optimizations
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.2 Instruction Cache Optimizations命令キャッシュの最適化。２つのキーポイントがあります。・データーの大きさをキャッシュが保持できるように小さくする。・同時にアクセスするデーターを一緒に保存することができるようにデーターの局所性を増やす。ある程度はコンパイラが最適化してくれるのですが以下のような工夫を行うことがより効果的。・コードのインライン化に注意する・繰り返し処理を行うループをキャッシュの大きさに収まるように分解する。・ループを不必要に展開しない・速度ではなく、コードサイズに配慮した最適化オプションでコンパイルします。・何でもかんでも盛り込むのはやめる。・アセンブリ言語が有益なところで利用。多くのアーキテクチャでキャッシュをコントロールする命令を持っており、命令キャッシュの利用を効率化します。前もって関数のアドレスに対する呼び出しを行うキャッシュ命令を発行することで関数を呼び出される前にキャッシュに入れておくことが可能です。
2006年11月17日
コメント(0)
-
Real-Time Collision Detection 13.1 CPU Caches
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13.1 CPU CachesCPUキャッシュ。ここ最近のCPUだと命令やデーターをメインメモリからフェッチする分には高速に実行が可能です。命令を保持するのはインストラクションキャッシュでデータキャッシュはデーターを保持します。キャッシュにデーターがあればキャッシュから読みます。キャッシュにない場合はメインメモリを参照してデーターをフェッチします。その際にデーターが読み出されるまでストールしますので計算を遅らせるようにスケジュールするのがよさそうです。各キャッシュは32あるいは64バイトの多数のキャッシュラインと呼ばれるセクションに分割され、このセクション単位でデータ転送を行います。したがってバイト数よりもこのキャッシュラインのサイズ単位でデータ転送コストがかかると考えなくてはいけません。メインメモリは通常直接写像の方法によってキャッシュメモリに写像されます。直接写像の方法はキャッシュとメインメモリを一対一で写像します。キャッシュサイズと同じだけはなれているアドレスはキャッシュメモリ上で連続している位置に写像されます。キャッシュラインごとにデータ区別用のタグ識別子を持っています。タグは元データーのアドレスを持っています。キャッシュラインのスラッシング(thrashing)として知られる問題を軽減するためにセットアソシエイティブ(set associative)になっており、nウェイのアソシエイティブなキャッシュメモリに対して各論理キャッシュラインはn個の物理キャッシュラインに一致しております。これらすべてをタグを用いてチェックするわけです。
2006年11月16日
コメント(0)
-
Real-Time Collision Detection 13 Optimization
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/13 Optimization最適化。ここでは対象としているアーキテクチャに対してチューニングを扱います。今日では・メモリ最適化・並列処理の最適化が効果が大きいです。ここ数世代においてはメモリのアクセスを減らすことが最適化のキーになっています。このため高速なメモリを階層的に用意しています。コンパイラはメモリの階層構造を知らないので・ハードウェアキャッシング・ソフトウェアキャッシングの２つの手法を考えることができます。次に並列処理が考えられます。ほとんどのCPUはスーパースカラ(superscalar)で複数の命令をフェッチして発行することができます。
2006年11月15日
コメント(0)
-
Real-Time Collision Detection 12.7 Summary
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.7 Summaryまとめ。衝突判定では適格な幾何形状を入力として与えることが重要です。適格でない場合は、・重複頂点・平面でないポリゴン・T結合などの問題を生じます。構造化されていないポリゴンの集合(ポリゴンスープ)を入力とし、適格なメッシュに変換する方法について紹介しました。また、重複されている頂点をどのように結合するかについても解説してきました。隣接する面の間にできる割れ目やT結合の修復を可能にするために・頂点・辺・面の接続情報を計算する方法について学びました。同一平面上にある複数の面を１つの面に結合する方法や最初の位置において同一平面上にあるか、あるいはそれに近い状態にあるかどうかを判定する方法についても学びました。凹オブジェクトや凹面を凸あるいは三角形の切片に分解する方法についても学びました。分解不可能な凹オブジェクトの対処法も考えました。さらに正当性を判定する方法としてオイラーの公式を学びました。
2006年11月14日
コメント(0)
-
Real-Time Collision Detection 12.6 Consistency Testing using Euler's Formula
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.6 Consistency Testing using Euler's Formulaオイラーの公式による一貫性の判定。幾何形状の接続形態(トポロジー)を判定することで適切でない幾何形状であるかどうかを検知できます。最初は２つのソリッドな物体がお互いにトポロジー的には等価、あるいは同相(homeomorphic)であると見なせる状態を考えます。球に対して同相な多面体は単純な多面体(simple polyhedron) と呼ばれます。四面体や立方体が単純な凸多面体です。単純な多面体における頂点の数V、面の数F、辺の数E、の間にはオイラーの公式が成り立ちます。V+F-E=2多面体に１つ以上の穴がある場合は非単純な多面体(nonsimple polyhedron)に分類されます。穴の数を種数(genus)と呼んでいます。種数が０の任意の多面体はトポロジー的に球と等価になります。種数が１の場合はトーラスと２の場合はソリッドな８の字と等価になるといった具合です。種数(G)を加えたオイラーポアンカレの公式(Euler-Poincare formula)が成立します。V+F-E=2(1-G)この公式を適用するにはすべての多面体の面の境界において、その接続している頂点が１つの環を形成している必要があります。すなわち円盤に対して同相となります。さらに多様体の幾何形状のみに適用できます。すなわち各辺は２つの面によって共有され各辺は２つの頂点に対して接続し少なくとも３つの辺が各頂点で結合していることを仮定します。いくつかの有用な式をオイラーの公式から導出することができます。閉じている（多様体）メッシュが以下の図形の多数の集合により構成される場合に次の関係が成り立ちます。・三角形(T): 2E=3T、T=2V-4、E=3V-6・四辺形(Q):2E=4Q、Q=V-2、E=2V-4・三角形(T)および四辺形(Q):2E=3T+4Q,T=2V-2Q-4・任意の凸面(F):2E>=3F、F
2006年11月13日
コメント(0)
-
Real-Time Collision Detection 12.5.4 Dealing with "Nondecomposable" Concave Geometry
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.5.4 Dealing with "Nondecomposable" Concave Geometry｢分解不可能な｣凹幾何形状の取り扱い。半球状のお椀形状を考えてみます。内側は凹面だらけなので、幾何形状をポリゴンスープとして扱い面の集合として扱います。ただしこれでボリューム情報は失われます。別の解決方法はCSGオブジェクトとして扱う方法でAABBと球２つで簡単に表現できます。
2006年11月12日
コメント(0)
-
Real-Time Collision Detection 12.5.3 Convex Decomposition of Polyhedra
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.5.3 Convex Decomposition of Polyhedra多面体の凸分解。多面体を凸面に分割するのは難しく、まったくできないケースもあります。たとえばお椀の内部やトーラス形状などは難しいでしょう。分解手法としては多面体を四面体に分割する四面体分割(tetrahedralization)が良いでしょう。ただし三角形分割はすべてのポリゴンで可能ですが四面体はそうではありません。Schnhardtの多面体と呼ばれるものが有名です。三角柱における３つの長方形の各面をくぼんだ辺(concave edge)を持つ２つの三角形に｢谷折る｣されるようにひねることで構築されます。こうするとどの４頂点でも四面体を形成できません。しかし Schonhardt の多面体は内部にシュタイナー点を追加することで分割が可能です。また凸分解の現実的な手法として１つ以上のくぼんだ辺を通る切断平面によって多面体を２つに分解していくことです。くぼんだ辺を１つづつ減らしていくので最終的には凸切片の集合を返します・辺がくぼんでいるかどうかは内積で計算できるようです。
2006年11月11日
コメント(0)
-
Real-Time Collision Detection 12.5.2 Convex Decomposition of Polygons
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.5.2 Convex Decomposition of Polygonsポリゴンの凸分割。先に示された通り光線および四辺形の間の交差判定は三角形に対するものより高価になりません。したがって衝突用幾何形状は四辺形あるいは凸多面体によって構成されることもあります。単純なポリゴンの三角形分割は直接的ですが凸ポリゴンの集合へ分解することはより複雑になります。最小の凸切片に分解しようとした場合には追加の頂点(シュタイナー点(Steiner points))が必要かもしれません。凸分解のための単純なアルゴリズムが Hertel と Mehlhorn によって作成されていてこれは三角形分割から開始し各対角線を一回につき一度考慮します。対角線が凹頂点を生成することなしに除去できる場合は除去され、そうでない場合は次の対角線の処理を行います。本文では疑似コードの例が示されています。三角形分割のアルゴリズムは、より良い分割を生成するように2つの凸頂点に接続している対角線よりも優先して少なくとも1つの凹頂点につながるようにアルゴリズムを改善します。
2006年11月10日
コメント(0)
-
Real-Time Collision Detection 12.5.1.1 Triangulating Polygons with Holes
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.5.1.1 Triangulating Polygons with Holes穴のあるポリゴンの三角形分割。穴のあるポリゴンを三角形分割するために、外側のポリゴンを反時計周りで、内側にある１つ以上の穴の境界を時計周りで記述することにします。ポリゴンの三角形分割を可能にするために、外側および内側の境界は一連の繋がっている辺によってできる鎖として結合する必要があります。このため外側から内側の境界まで水路のような境界を作ることにします。具体的には内側と外側でループしている点をそれぞれ分けて反対方向へ対応する辺を作りつなぐ形になります。これは本文に図がありますのでそれを参考にするのが良いと思います。また任意の方向で与えられた場合はそこが穴なのか外側なのかがわからないのですが、この場合は最も大きな面積の方を外側の境界とします。外側が確定すれば頂点の順番を逆にすることもできるでしょう。
2006年11月09日
コメント(0)
-
Real-Time Collision Detection 12.5.1 Triangulation by Ear Cutting
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.5.1 Triangulation by Ear Cutting耳切断による三角形分割。ポリゴンの頂点 Vi, Vi-1, Vi+1 で形成される三角形が耳であるとは Vi-1 と Vi+1 の間の対角線がそのポリゴン全体を含んでいる場合に言います。また頂点 Vi は穂先(ear tip)と言います。耳は穂先によってのみ参照されるのが一般的です。すべての単純な三角形でないポリゴンは少なくとも2つの重ならない耳を持っています。このため、繰り返し耳を識別して除去することにより三角形分割できます。頂点nのポリゴンの三角形分割はちょうど n - 2 個の三角形から構成されることになります。単純なポリゴンに対して3つの連続している頂点 Vi-1, Vi, Vi+1 が耳Eを形成しているかどうかを判定するのに等しいことはViが凸で他のポリゴンがEの内側にないことを確かめればよいです。ポリゴンは境界の周りを反時計回りに反復処理することによって三角形分割することが可能です。耳を切断したあと両方の頂点を確実に再巡回するように穂先の頂点に対してその直前の頂点が、切断の後に巡回される次の頂点として設定されます。本文ではここまでの説明を図とソースコードでわかりやすく説明しています。
2006年11月08日
コメント(0)
-
Real-Time Collision Detection 12.5 Triangulation and Convex Partitioning
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.5 Triangulation and Convex Partitioning三角形分割と凸面分割。凸面だけの判定ならば単純に高速に頑健に行えるので凸でない面を凸切面分割(convex partitioning)することは有意義です。単純な方法としては三角形分割(triangulate)する方法です。本文では三角形分割と小さな凸面に分割する手法が提案されています。
2006年11月07日
コメント(0)
-
Real-Time Collision Detection 12.4.2 Testing Polygon Planarity
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.4.2 Testing Polygon Planarityポリゴンの平面性を判定する。ポリゴンが平面になっているかどうかの判定には頂点がサポート平面上にあるかどうかを確認すればよいです。サポート平面はポリゴンの法線とポリゴンの頂点から計算できます。しかしポリゴンの法線を求めるために外積を用いると2辺が同一かそれに近い場合にゼロベクトルになるか精度に問題が出てきます。2辺の間の角度が大きい場合も共有頂点が平面からの距離わずかだけ離れている場合などにポリゴンが拡大されると平面性が変わらないので問題になります。したがって2辺というよりはすべての頂点をもとめそれらの平均を求めるのがよさそうです。しかしこれは凹の場合にうまくいきません。法線が反対方向に向いてしまうからです。ずっと優れている方法として Newell の方法として知られている方法があります。www.graphicsgems.comこれはポリゴンの法線の成分が yz, xz, xy 平面に射影した符号付き面積にそれぞれ比例しているという事実を利用して計算するものです。本文ではソースコードつきで説明されています。見方によってはすべての頂点が最も密着する平面を求めているともいえそうです。となるとポリゴンの頂点に対して平面を最小２乗法を用いてフィッティングさせる方法も良さそうです。四辺形に限定すれば Newell の方法を簡略化した方法も提案されています。また、さらなる簡略化方法もあるようでなかなか興味深いテーマです。
2006年11月06日
コメント(0)
-
Real-Time Collision Detection 12.4.1 Testing Coplanarity of Two Polygons
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.4.1 Testing Coplanarity of Two Polygons2つのポリゴンが同一平面上にあるかどうか判定する。同一平面かどうかの判定には、平面の法線の間にできる角度を計算する方法が良さそうです。ただしこの手法は衝突判定用には向きません。なぜなら角度が近くても面が大きい場合は厚みが大きく変わってしまうからです。したがって厚みを別途確認するのが良さそうです。ここでは平面を結合したあとにすべての頂点を含む平面を代理平面(representative plane)と呼ぶことにしその代理平面にスナップする際にさらに三角形分割する手法が提案されています。
2006年11月05日
コメント(0)
-
Real-Time Collision Detection 12.4 Merging Coplanar Faces
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.4 Merging Coplanar Faces同一平面上にある面の結合。面の数を減らすことで衝突判定を最適化することができます。多くの手法がありますが衝突判定用には形とボリュームの両方を保存しておき視覚的に表現される形状よりも｢縮む｣のを避けるのが良さそうです。衝突判定用の幾何形状に適しているのは同一平面(co-planner)に近い面を結合する方法です。面の条件としては以下のようなものが挙げられます。・結合する面は両面(double sided)か同じ法線方向を向いていること・同じ曲面属性であること。（足音、摩擦係数、似たような属性）・境界となる辺を共有していること接続情報が利用できるなら接続情報のリンクにより与えられる隣接している面を巡回して隣接している面を接続していくのが素直な方法です。また各法線をキューブマップとしてみて投影した立方体の近いセル同士を結合する手法も良さそうです。
2006年11月04日
コメント(0)
-
Real-Time Collision Detection 12.3 Holes, Cracks, Gaps and T-Junctions
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.3 Holes, Cracks, Gaps and T-Junctions穴、割れ目、すき間、T結合。メッシュにおける穴は繋がって閉じた辺によって接続されている頂点の集合に対して、これらすべての頂点と辺に関してそれらを接続する面が定義されていないことを意味します。意図的にあけていない穴は割れ目(crack)や継ぎ目(seam)とも呼ばれます。２つの完全には接続されていない状態の幾何形状の間にある狭い空洞になっている部分はすき間(gap)と呼びます。こちらは局所的に発見して対処することが可能なのですがすき間は大域的な意味によってしか検知することができません。多くの割れ目は複製された頂点によって生じ、これらの割れ目はメッシュの頂点を結合することによって消滅させることができます。ある辺の1つの端点が別の辺の内部にある状態をT結合(t-junctions あるいは t-joint)と呼ばれます。またその頂点をT頂点と呼びます。T結合を検知するにはすべての頂点について繰り返しの処理を行い各頂点に対して接続している辺について辺のペアに対する共線(同一直線上にある)性を判定します。共線的な(同一直線上にある)辺が発見された場合、そのペアは割れ目の一部です。これは辺の端点を他方の端点に結合することで解決できます。しかしすき間に関してはより大域的な方法が必要です。ある辺に対してその近傍にあるすべての頂点のメッシュの頂点を見つけることができなければなりません。h格子や緩い8分木のような階層構造に挿入すると良さそうです。T結合が発見された場合3つの解決法があります。・頂点を1つにする(vertex collapse)・辺を分割(edge cracking)・頂点をスナップ(vertex snapping)非多様体の場合は面を分割(face cracking)しなくてはいけないケースもあるようです。
2006年11月03日
コメント(0)
-
Real-Time Collision Detection 12.2.3 Testing Connectedness
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.2.3 Testing Connectedness接続性のテスト。接続情報を用いて面の表の中にあるすべての面がある辺によって別の面に接続しているかどうかを決定する問題について考えてみます。どの接続要素が三角形の一部の要素なのか知るために label フィールドを各三角形のデータ構造に要素の番号を保持するために追加されています。開始時にはどの要素の一部としてもラベル付けされてはおらず、すべての三角形を巡回しマーク付けされていない三角形に遭遇するたびに要素の番号を1つずつ増やしこの要素の番号でタグ付けしていきます。こうしてすべての要素を接続し終わると再帰的に最初の要素番号のついている三角形をすべて巡回してマークしていきます。ここまでの例が本文ではソースコード込みの例で示されています。再帰の処理が深すぎると問題になるでしょうから明示的にスタックをとるような処理が良さそうですね。
2006年11月02日
コメント(0)
-
Real-Time Collision Detection 12.2.2 Computing an Edge-to-Face Table
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/12.2.2 Computing an Edge-to-Face Table辺から面への変換表を計算する。前回と同様に辺に対して辺に接続している面を関連づけている表の計算を行います。ここでも三角形のみを扱います。また三角形は一貫して面上からみて反時計回りになっているとします。頂点はインデックス化されているので小さいインデックスの値を持つ頂点を最初に記すことで辺の記述の1つを選んでリスト化することができます。インデックスの代わりに３つの座標の組として頂点が与えられている場合はx,y,z成分について辞書順(lexicographic ordering)に並べる順序付けで一貫した順番にすることが可能です。辺は頂点インデックスのペアによって表現されているのでこのペアは表に対するインデックスを用いていなければなりません。ここでハッシュを用いる例が本文では示されています。ここまでの例が本文で示されています。
2006年11月01日
コメント(0)
全30件 (30件中 1-30件目)
1
