2026
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2006年08月の記事
全31件 (31件中 1-31件目)
1
-
Real-Time Collision Detection 8.3.2 Evaluating Dividing Planes
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/8.3.2 Evaluating Dividing Planes分割平面の評価。さまざまな手法が提案されています。大部分は節点ノード保存ツリーの仮定に基づいたもので平行な面の数が最大な面か大きな面積を持つ面のサポート平面を選択するといったものです。衝突判定向きの戦略としては、幾何形状の分割を最小になるようにし、なおかつ幾何形状が分割平面の両側においてバランスが取れるように平面を選択するものです。前者の最小分割(least-crossed) 戦略は、分割によって幾何形状が複製される部分を最小限にします。効率のためこの2つの方法を重みつけて線形に組み合わせる方法が実際にはよく用いられます。本文ではソースで例が示されています。またより洗練された手法として衝突最小化法(confict minimization)および衝突中立化法(conflict neutralization)があります。これらの方法は一度に２つ以上の連続した分割平面を考えることによりツリーの現在のレベルにおける平面の｢衝突｣をできるだけ少なくするように選択します。
2006年08月31日
コメント(0)
-
Real-Time Collision Detection 8.3.1 Selecting Dividing Planes
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/8.3.1 Selecting Dividing Planes分割平面の選択。ツリーの構築の間に分割平面が選択される順序は結果としてできるツリーの形と大きさ、さらにはツリーをクエリする際の効率性に多大な影響を与えます。あり得る順序付けは幾通りもあるので候補の中から評価関数に従って絞り込みます。問題に制約条件を与えるための1つの方法は幾何形状を構成している面のサポート平面だけを探索するという手法もあります。自動分割だけだと理想的とはよべず葉ノード保存のツリーに対してなど、場合によっては望ましい数より多くの分割が行われてしまうことがあります。ポリゴンの球からBSPツリーを構築する問題を考えてみましょう。球は凸なので平面の片側だけにあります。そのため得られるツリーはある意味最悪のバランスになってしまいます。対象的に平面で球を切断することを可能にすれば面のうち半分を各平面に対する判定において無視することができ最悪の場合のクエリでもO(logn)の操作で済ませることができます。Naylor によって提案される手法としては、まず最初に自動分割平面の集合を球をその周りの空の空間から分離するために選択します。球を取り囲む正四面体を構成します。ソリッドな正四面体に一致する領域が１つでき残りの4つの領域はすべての面が処理されるまで同じ分割の処理が再帰的に行われるようにします。これで得られるツリーは徐々に正確になっていきます。また自動選択に頼るだけでなくヒント平面(hinting planes)を手動で置いていく手法もあるようです。また任意の平面を単純な山登り法で評価していく手法もあるようです。
2006年08月30日
コメント(0)
-
Real-Time Collision Detection 8.3 Building the BSP Tree
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/8.3 Building the BSP TreeBSPツリーの構築。構築の段階として3つの段階が示されています。１．分割平面を選択。２．入力幾何形状を平面の表と裏に分割３．ツリーの形成本文ではここまでのコード例が示されています。ただ良い分割平面を選ぶのは実際には難しい問題ですね。また再帰をどこまでやるのかといったところはアルゴリズムに応じて考えないといけないですね。ここではツリーの構築時と実行時におけるＢＳＰツリーは同じものですが高品質なプロダクションではまったく異なる記述方を利用するのもよさそうです。
2006年08月29日
コメント(0)
-
Real-Time Collision Detection 8.2.3 Solid-Leaf BSP Trees
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/8.2.3 Solid-Leaf BSP Treesソリッド葉ノードBSPツリー。これまでと異なりソリッド葉ノードBSPツリーは入力幾何形状の中を占めているソリッドなボリュームを表現するために構築されます。分割平面は最終的にはオブジェクトの外部からソリッドなボリュームを分離するために選択されます。入力幾何形状におけるすべてのポリゴンのサポート平面は分割平面として選択されなければなりません。とりわけ葉ノードの直前の分割平面はサポート平面と一致することになります。ツリーの他の内部ノードは常に任意の分割平面を使用することができ、バランスをより良くすることが可能です。ツリーには幾何形状が保存されておらず葉ノードは分割平面の表側または裏側にある残りの部分が空きなのかソリッドなのかを示しているだけです。つまり入力ボリュームを凸多面体の集合に分割していると見なすことができます。ソリッド葉ノードBSPツリーは衝突判定に関して有益です。オブジェクトがソリッドな空間上にあるのか空き空間にあるのかどうかを交差判定によって直接調べることだできます。QuakeII および QuakeIII に使用されたブラシ保存(brush-storing)ツリーと呼ばれる手法がありソリッド葉ノードと葉ノード保存BSPツリーの折衷案となっています。
2006年08月28日
コメント(0)
-
Real-Time Collision Detection 8.2.2 Leaf-Storing BSP Trees
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/8.2.2 Leaf-Storing BSP Trees葉ノード保存BSPツリー。この用語はBSPツリーが内部の節点ノードではなくツリーの葉ノードに幾何形状を保存することからこう呼ばれています。内部のツリーの節点ノードは分割平面とノードの子となる部分木への参照のみを含んでいます。葉ノードへの衝突のクエリは葉ノードに含まれるすべてのポリゴンに対して判定を実行します。ツリーに対する判定は衝突が検知された場合には早期に終了することが可能です。分割平面は一般的なものか自動分割であるかのどちらかです。自動分割の場合は選択されている分割平面に平行なすべての面がマークされ、その後分割平面が選択される際に考慮されるべき平面から除外するためにマークをつけておきます。ここで図示されている例は最初の分割平面を半分ずつ分割しているようです。衝突用の幾何形状のデータ構造としては一般的なものになっていると思います。
2006年08月27日
コメント(0)
-
Real-Time Collision Detection 8.2 Types of BSP Trees
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/8.2 Types of BSP TreesBSPツリーの種類。ここでは節点ノード保存(node-storing)、葉ノード保存(leaf-storing)、ソリッド葉ノード(solid-leaf)(あるいは単にソリッド(solid))BSPツリーなどの例が挙げられています。8.2.1 Node-Storing BSP Trees節点ノード保存BSPツリー。これは自動分割のため構築時に幾何形状の各面のサポート平面を分割平面として選択します。名前の通りある面のサポート平面が分割平面として選択され同一平面上にある他のすべての面が節点ノードに保存されます。残りの面は平面の適切な側に渡されて、ノードの部分木を再起的に構築するために使用されます。最終的にはツリーのかなり下の方のノードに保存されます。分割平面をまたいでいる面は分割されて分割の結果として得られる小片が下の方に渡されます。このアルゴリズムは３Ｄのソフトウェアレンダリングで主に利用されてきました。他の種類のＢＳＰに比べてより少ない分割で節点ノードに面を保存しておくことができ、より少ない面をレンダリングするだけで済みます。ただ節点ノードに保存されている面はクエリのオブジェクトとは何の位置関係も持っていないので衝突判定に向いているとは言えません。
2006年08月26日
コメント(0)
-
Real-Time Collision Detection 8 BSP Tree Hierarchies
今日からまた Real-Time Collision Detection を読むことにします。http://www.realtimecollisiondetection.net/8 BSP Tree HierarchiesBSPツリー構造。kd-ツリーや4,8分木と同じ用途に適用することが可能ですが逆はできません。空間分割意外にも任意の多面体で構成されるシーンにおける境界やソリッドを記述するのに利用できます。8.1 BSP TreesBSPツリー。2分空間分割ツリー(binary space-partitioning tree)あるいは略してBSPツリーは2分木の構造で位置および方向を持っている分割平面に基づいて空間を分割し再帰的に分割空間のペアを作るように空間を分割することで得られます。2つの区間あるいは半空間に分割された領域は正(positive)負(negative)の半空間と呼ばれます。元々BSPツリーは隠面処理の問題に対処するために開発されました。BSPツリーはこの問題を前処理の段階で視点に依存せずにシーンを分割することで解決します。オブジェクトのボリュームを表現する手法で分割平面と幾何形状の面が一致するように選ばれている場合には自動分割(autopartitoning)やポリゴン平面(polygon aligned)と呼ばれます。xy,xz,yz平面に平行な分割平面は軸平行(axis aligned)と呼ばれています。BSPツリーが軸平行の分割平面のみ用いられている場合にはkdツリーと呼ばれます。
2006年08月25日
コメント(0)
-
Real-Time Rendering 6.12.2 Shadows on Curved Surfaces
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.12.2 Shadows on Curved Surfaces曲面上の影。今までの平面上の影の考え方を曲面上の影に拡張する方法の1つは生成した影の画像を投影テクスチャとして利用することです。受影体に投影することで任意の形状に適用できます。ここではシャドウテクスチャ(shadow texture)テクニックと呼んでいるようです。またライトマップと対になる単語としてシャドウマップ(shadow map)といういい方もしていますがこれはデプス比較を使う影でよく使われている単語なので紛らわしいかもしれないですね。あっちの方はシャドウデプスマッピングとでも呼んだ方がいいかもしれないですね。この手法の欠点としては事前にどのオブジェクトが遮光体でどのオブジェクトが受影体なのかをデザイナがいちいち指定しないといけないことです。まあ、それをランタイムでやらない分だけ高速だとも言えるのですが。またセルフシャドウがちゃんとできないのも今時困るかもしれません。
2006年08月24日
コメント(0)
-
Real-Time Rendering 6.12.1 Planar Shadows その２
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.12.1 Planar Shadowsソフトシャドウ。投影シャドウを様々なテクニックを使ってソフトにすることができます。光源が面積を持つ場合は常にソフトシャドウが現れます。面光源の効果を近似するために多数の点光源をその面上に配置してサンプリングする手法があります。点光源ごとに画像をレンダリングしてアキュムレーションバッファに加算して平均値を求めればソフトシャドウを作ることができます。また Heckbert と Herf は視錐台を基にした手法を提案しています。点光源ごとに点光源と受影体の平行四辺形から形成される四角錐内部にある遮光体を平行六面体に座標変換します。本質的には光源から受影体を見て遠近投影を行います。ここで用いられるマトリックスを用いることで四角錐の外側をカリングして正しく遮光体だけが受影体に影を生成させることができます。面光源をサンプリングする手法の問題として重なり合う点光源からの多くの影に見えがちなことです。光源面上のサンプリング位置を変化させる代わりに Ｇｏｏｃｈ らは受影平面の位置を上下させてそこにおける投影を平均させております。またこの方法ですと作成した影を入れ子テクスチャに格納することもできます。問題点としてはオブジェクトが受影体に触れていようとオブジェクトの下から漏れだすように見えてしまいます。どちらの手法にせよ影が限られた数のグレースケール陰影に量子化されてしまうことです。テクスチャはこの量子化を隠してくれるので受影体にテクスチャを使うのがよさそうです。影は接している部分で影が鋭くなり距離が増えるにつれて柔らかくなります。Haines の手法では中心が暗く周囲が白くなる輪郭線を描く例が挙げられています。
2006年08月23日
コメント(0)
-
Real-Time Rendering 6.12.1 Planar Shadows
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.12.1 Planar Shadows平面上の影。ここでは平らなサーフェィスにオブジェクトが影を落とすアルゴリズムが2つ紹介されています。投影シャドウ。この方法では影を作成するためにシーンを2回レンダリングします。ここではまずオブジェクトの頂点を平面に投影する行列の算出方法が記述されています。このあたりの説明を省略する書籍も多いのですがこの本はさすがにしっかりしていますね。y=0平面での相似三角形の例を示しその後任意の平面へと一般化して説明してあります。きちんと証明されたこの式を用いて投影マトリックスを作り影モデルを変形(変換?)させてレンダリングすれば影の描画を行うことが出来るというわけです。理屈としてはここまでで十分なのですが影ポリゴンと投影される地形モデルとの間に適切なバイアスを加えないと精度の誤差もあるので綺麗に影が落ちません。またバイアスは視点とサーフェィス法線と角度に応じて適切に調整を行う必要があります。より安全な手法としては最初に地面を描画してからZバッファを無効にして投影後のポリゴン描画を行うことで必ず描画させるという手法も紹介されています。後は影が落ちてはいけない部分をステンシルでマスクする方法やZ深度を利用して矛盾を回避する定番の方法が紹介されています。また光源が投影されるオブジェクトより下にある場合（床と天井などがある場合）は床だけでなく天井のほうにも陰がレンダリングされてしまう逆影(anitishadow)問題が生じることもあります。同様に影の投影される裏側(たとえば壁の反対側)にも影が投影されてしまう偽影(false shadow)と呼ばれる問題が起こることもあります。これらはクリップ平面などで回避するようにここではまとめられています。
2006年08月22日
コメント(0)
-
Real-Time Rendering 6.12 Shadows
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.12 Shadows影はユーザーにオブジェクト配置の視覚的手がかりを提供する重要な要素です。ここで使う用語として遮光体(occluder)は受影体(receiver)上に影を落とすオブジェクトとします。点光源はハードシャドウと呼ばれる完全に影になる領域だけを生成します。面光源(エリアライト)やボリューム光源(ボリュームライト)を使うとソフトシャドウを生成できます。そのとき影はそれぞれ本影(umbra)と呼ばれる影の領域と半影(penumbra)と呼ばれる部分的な影の部分を持ちます。ハードシャドウの影の淵をローパスフィルタでぼかすだけでは正確ではなく影を落とすジオメトリが受影体に近いほどくっきりするようにするのが望ましいです。ソフトシャドウの本影領域は光源が大きいほどサイズが縮小し実際に十分大きな光源を与えると本影領域が消えることさえあります。
2006年08月21日
コメント(0)
-
Real-Time Rendering 6.11 Refractions
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.11 Refractions屈折。物理的な効果としてフレネル、スネルの法則などがあります。屈折は反射と似ています。ここではＥＭＢＭやキューブ環境マップやピクセルシェーダーで補正ベクトルを作る方法などが示されています。私の経験からも屈折は物理的に正確でなくてもボロが出にくいところだと思います。水の表現としてはコースティクスや海洋面の細かい動的法線マップあるいは光の筋の疑似ボリュームレンダリング、泡やパーティクルのしぶきなどが挙げられています。まあ細かいテクニックの組み合わせが大切なのでしょうね。
2006年08月20日
コメント(0)
-
Real-Time Rendering 6.10.3 Reflections from Curved Reflectors
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.10.3 Reflections from Curved Reflectors曲面反射体からの反射。レイトレーシングを使って反射を作るのに対して Ofek と Reppoport の提案する方法では凸面と凹面の反射からを大幅に高速化できるようです。これはなかなか面白そうですので論文を読んでみようかと思います。
2006年08月19日
コメント(0)
-
Real-Time Rendering 6.10.2 Glossy ERects
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.10.2 Glossy ERectsツヤツヤした反射効果。前の説ではくっきり反射するだけでしたがここではその応用を扱います。まずはフォグを使って適当にぼかす方法、あるいは反射面からの距離に応じて黒くフェードさせたりとか。これは影のぼかしなんかでもやりますかね。アキュムレーションバッファを使えばぼかすこともできますしステンシルバッファと併用することでぼやけた反射ときれいな反射との併用もできるでしょうか。反射には黒のフォグを使い屈折には白いフォグを使うそうです。なるほどなるほどローテクですがそんなものかも。
2006年08月18日
コメント(0)
-
Real-Time Rendering 6.10.1 Planar Refleections
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.10.1 Planar Refleections平面反射。これは平らなサーフェィス専用の反射です。ゲームでは結構よく見かけるかも。基本的にはｙ軸方向に-1スケールかけるだけでよいのですがそれだとライティングが不正確なのでカメラひっくり返してテクスチャ作って張ったりもしますかね。これだとバンプやらなんやらやりたい放題です。ひっくり返すだけの場合は移りこみ先の形状次第ではボロが出るのでステンシルやユーザ定義クリップ平面で切ってあげればよいでしょうか。応用としてはテクスチャに反射絵を作って平面に張る際に uv を揺らして波打たせたりでしょうか。水の表現なんかはこんなのをよく見かけます。まあこれだけだと水銀みたいになるのでフレネルとかも入れないといけないでしょうけど。後は反射画像にローパスフィルタをかけたりですか。高速化のためには1フレーム前の環境マップを際利用する例がここには挙げられています。
2006年08月17日
コメント(0)
-
Real-Time Rendering 6.10 Reflections
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.10 Refleections反射。反射と屈折と影の処理はシーン内の1つのオブジェクトが別のオブジェクトのレンダリングに影響を与えるグローバルイルミネーション効果です。影なんかは空間的な認識を判断する重要な手掛かりとなります。反射に関しては環境マップなんかが原始的なところでしょうか。
2006年08月16日
コメント(0)
-
Real-Time Rendering 6.9 Depth of Field
RealtimeRendering という本を読んでいます。http://www.realtimerendering.com/6.9 Depth of Field被写界深度。これは写真の焦点効果をまねたものです。手法としては・アキュムレーションバッファにカメラを動かした映像を累積・レイヤベースにテクスチャにレンダリングした絵をＺ深度に応じてアルファブレンドなどの方法がありますか。2番目の手法はやっぱテクスチャ3枚あったほうが良いのかも。ただコストが高いのでゲームなんかだとまだ難しいのかも。
2006年08月15日
コメント(0)
-
Real-Time Rendering 6.8 Motion Blur
本日からまた Real-Time Rendering を読みます。http://www.realtimerendering.com/6.8 Motion Blurモーションブラー。これは映画などの効果をまねたもので動いているものをぼかします。移動の感覚を加えるためにモーションブラーを強調することもあります。アプローチとしては・ブラー自身をモデリングしてレンダリングする方法・アキュムレーションバッファを使って一連の画像を平均する方法・頂点シェーダーで移動方向の後ろ向きのポリゴンを引き延ばす方法などがあります。3番目の方法は試したことないのですが綺麗にいくものなのですかね？
2006年08月14日
コメント(0)
-
Real-Time Collision Detection 7.8 Summary
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.8 Summaryまとめ。空間分割はつまるところペアの数を必要最小限に絞り込むことで最適化を狙っています。ここでは格子、ツリー、空間分割ソートによる方法を扱いました。格子はハッシュで必要メモリを最適化しました。ツリー表現の1つの8分木を扱い。線形に展開することでポインタを使わずに表現する方法を学びました。またkdツリーは8分木の一般化であり1つの次元に沿って空間を分割します。これはクエリを単純にします。空間ソートは1つ以上の軸に対してソートされている構造の中で管理する必要がありました。これはソートされているので隣のオブジェクトを探索を用いずに検出することが可能になります。そして次のショウではkdツリーの一般化された手法を扱います。
2006年08月13日
コメント(0)
-
Real-Time Collision Detection 7.7.3 Amortized Time Stamp Clearing
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.7.3 Amortized Time Stamp Clearingタイムスタンプを少しずつリセットする。タイムスタンプのカウンタを一度にリセットする際のオーバーヘッドは、少しずつリセットしていくことで軽減できます。グローバルなカウンタがオーバーフローする場合にすべてのタイムスタンプのカウンタの集合をより小さなブロックに再分割して各フレームでブロックを1つずつリセットすることが可能です。本文ではそれぞれ3個3個4個のオブジェクトが入るような3つのブロックへの分割を考えています。カウンタも３つ用意しそれぞれをずらしたタイミングでクリアすることでフレームごとの処理付加を分散しているようです。また実装例のソースもついていますのでこれを参考にするのがよさそうです。
2006年08月12日
コメント(0)
-
Real-Time Collision Detection 7.7.2 Time Stamping
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.7.2 Time Stampingタイムスタンプ。光線を使用する場合うまくいくのが各光線のクエリに対して加算されるカウンタを実行し続けて判定の終わった各オブジェクトに通常タイムスタンプと呼ばれるカウンタを割り当てる方法です。これはオブジェクトが判定される前にタイムスタンプを調べてオブジェクトが判定されているかどうかを調べるものです。複数のオブジェクトが光線によって交差される場合はこのタイムスタンプを利用して最も手前で交差するオブジェクトを検出することが可能でこの例が本文に挙げられています。タイムカウンタがオーバーフローしないように注意する必要があります。レイトレーシングの世界ではメールボックス(mailbox)として説明されています。また複数回の交差を除去し冗長な計算を省く別の方法であるレジデンシーマスク(residency masks)という手法もあるようです。
2006年08月11日
コメント(0)
-
Real-Time Collision Detection 7.7 Avoiding Retesting
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.7 Avoiding Retesting再判定を防ぐ。空間分割の仕組みを用いる場合に1つのオブジェクトが複数の分割された部分に重なる可能性があります。同じ２つのオブジェクトを複数回判定しないようにいくつかの解決方法を利用することができます。7.7.1 Bit Flagsビットフラグ。これは交差判定がすでに行われたかどうかを示すビットフラグを用いることです。ビットがすでにセットされている場合はすでに判定済みでそれ以上の判定を行う必要はありません。オブジェクトとオブジェクトの衝突判定を行うにはビットフラグをオブジェクトのインデックスを利用することで少ない配列に格納することが可能です。本文ではインデックスの例がコードつきで示されています。
2006年08月10日
コメント(0)
-
Real-Time Collision Detection 7.6 Cells and Portals
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.6 Cells and Portalsセルとポータル。衝突判定のためだけに空間分割の枠組を持つ必要はなくシーングラフのような階層的なレンダリング方法だけで十分です。このような構造のなかで衝突判定向きなのはセルとポータルです。この方法は建築物をウォークスルーするシステムをレンダリングするために開発されました。深さ方向に対して非常に複雑なのですが視垂台に入ってはいるが見えないものが多くあります。ワールドを領域(セル)とそれらを連結する境界(ポータル)に分割していくことで無駄を省くことができます。部屋がセルに対応し戸口や窓がポータルに対応します。セルとポータルに分かれているシーンをレンダリングするためにはカメラを含んでいるセルに対する幾何形状を描くことから始めます。そして隣接するセルを再帰的にレンダリングしていきます。新しいポータルは現在のポータルに対してクリップされ見える範囲は徐々に狭くなっていきます。ポータルは自己交差のないポリゴンとして実装されます。セル自体は慣習的に凸多面体として定義されます、これは凸であればセルの中にあるポリゴンはどんな順序であっても重なることなしにレンダリングすることができるからです。最適化のためにオブジェクトはそれらの中心点を含むセルに関連付けられます。オブジェクトが動くに従って光線の判定がオブジェクトが現在のセルから動いて光線の判定がオブジェクトが現在のセルから動いて外に出てしまったかどうかを決定します。そうであれば接続するポータルに対して判定すればよいわけです。
2006年08月09日
コメント(0)
-
Real-Time Collision Detection 7.6 Cells and Portals
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.6 Cells and Portalsセルとポータル。衝突判定のためだけに空間分割の枠組を持つ必要はなくシーングラフのような階層的なレンダリング方法だけで十分です。このような構造のなかで衝突判定向きなのはセルとポータルです。この方法は建築物をウォークスルーするシステムをレンダリングするために開発されました。深さ方向に対して非常に複雑なのですが視垂台に入ってはいるが見えないものが多くあります。ワールドを領域(セル)とそれらを連結する境界(ポータル)に分割していくことで無駄を省くことができます。部屋がセルに対応し戸口や窓がポータルに対応します。セルとポータルに分かれているシーンをレンダリングするためにはカメラを含んでいるセルに対する幾何形状を描くことから始めます。そして隣接するセルを再帰的にレンダリングしていきます。新しいポータルは現在のポータルに対してクリップされ見える範囲は徐々に狭くなっていきます。ポータルは自己交差のないポリゴンとして実装されます。セル自体は慣習的に凸多面体として定義されます、これは凸であればセルの中にあるポリゴンはどんな順序であっても重なることなしにレンダリングすることができるからです。最適化のためにオブジェクトはそれらの中心点を含むセルに関連付けられます。オブジェクトが動くに従って光線の判定がオブジェクトが現在のセルから動いて光線の判定がオブジェクトが現在のセルから動いて外に出てしまったかどうかを決定します。そうであれば接続するポータルに対して判定すればよいわけです。
2006年08月08日
コメント(0)
-
Real-Time Collision Detection 7.5.2 Array-Based Sorting
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.5.2 Array-Based Sorting配列を基にしたソート。リンクリストはメモリの許す限り多数のオブジェクトを取り扱うことが可能なこととオブジェクトがほとんど動かない時に高速なところがよいのですが各オブジェクトのAABBのメモリの重いオーバーヘッドが欠点となります。代替案として配列を用いて軸上の範囲のソートを実装するという方法があります。多くのオブジェクトを動かす場合には柔軟ではないのですがメモリの消費量を減らすことが可能です。配列を用いると完全なソートのパスが必要になります。ここの例では qsort をそのまま使っているようですね。ソートに関しては座標軸の中から1つを選びその軸に沿ってソートします。スウィープのパスの間に3つの軸それぞれに沿ったAABBの分数が計算されますこのパスにおける計算が終わった後では、最も大きな分散を持っている軸が次にルーチンが呼び出される時に利用されるために選択されます。
2006年08月07日
コメント(0)
-
Real-Time Collision Detection 7.5.1 Sorted Linked List Implementation
7.5.1 Sorted Linked List Implementationソートされているリンクリストの実装。2つの構造体が必要です。最小もしくは最大の間隔を保持するためのものとstruct AABB{Elem* pMin[3], // 最小の射影間隔Elem* pMax[3], // 最大の射影感覚Object* pObj,},そのエントリをリンクするものです。struct Elem{AABB* pAABB, // Elem* pLeft, // Elem* pRight, // float value,int minmax:1,},minmax はフラグとして使いメモリを節約するのに役立ちます。ポインタを16ビットのインデックスに変えるのも手だと思われます。本文では具体的な実装がソースコードで解説されています。よく最適化されていると思われます。
2006年08月06日
コメント(0)
-
Real-Time Collision Detection 7.5 Sort and Sweep Methods
7.5 Sort and Sweep Methodsソートとスウィープの方法。固定の分割空間にオブジェクトを挿入するのは複数の分割空間にまたがっているオブジェクトによって格子と8分木の記述方法に加わる複雑さに対処しなければならないことです。代わりに何らかのソートされた空間を考えることができます。ソートとスウィープと呼ばれる方法があります。(sort and sweep)最初に1次元から考えるとソートされているリストに登録する場合はリストをスウィープすることでアクティブな間隔を記録することができます。リストがソートされた後にオブジェクトが一般的にフレームとフレームの間でかなり離れたところまで動くことはないためリストはあるフレームから次のフレームまでソートされているままで残ります。この性質を利用して単純な挿入ソートを用いて順番を管理します。ソートの高速化のために双方向のリストを用意する必要があります。オブジェクトが集合してしまいやすい一般的な状況における解決方法の1つとしてｙ軸はｘｚのみリストに保存する方法があります。ゲームなどではｙは比較的近い値で密集するからです。
2006年08月05日
コメント(0)
-
Real-Time Collision Detection 7.4.2 Uniform Grid Intersection Test
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.4.2 Uniform Grid Intersection Test均一格子の交差判定。均一な格子を通る光線を発射するのは Bresenham のライン描画アルゴリズムによって実行されるらスター化に非常によく似ています。ただ重要な違いもありラスター化では直線は埋められていないセルと交差する可能性があります。探索方法は直線に沿って訪問するセルが6接続で行われている必要があります。Bresenhamのような手法は主軸に沿って段階的に分類化を行います。エラーの項が出ればもう一方の軸に沿って段階的に行います。ここではセルが正方形であることを仮定していています。鍵となる考え方としては光線はセルを通過して離れる際にセルの境界を貫通します。どの軸を先に計算するかは光線の向きにより決まります。本文では２Ｄおよび３Ｄのコード例が示されています。最適化手法としてはいくつかの異なる向きの格子を用意して光線を追跡するのに最も近い方向に沿っているものを選びます。別の最適化としてはセルの中にあるオブジェクトが全面に動いていくような発見的な手法を適用することです。
2006年08月04日
コメント(0)
-
Real-Time Collision Detection 7.4.1 k-d Tree Intersection Test
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.4.1 k-d Tree Intersection Testkdツリーの交差判定。光線や方向のある線分とkdツリーとの交差の背後にある考え方は直線的です。線分 S(t) = A + td はノードが分割する平面に対して交差し交差における t の値を計算することができます。0 < t < tmax の範囲内にあれば線分は平面をまたいでいるのでツリーの両方の子を再帰的に降下していきます。そうでないならば線分の原点側を再帰的に降下していきます。最初に線分の原点側を降下することにすれば重なっている kd ツリーのノードが近い方から遠い方の順に探索していくことが保証されます。本文では疑似コードの例が示されています。この処理は明示的な再帰処理を用いない方法で記述可能です。
2006年08月03日
コメント(0)
-
Real-Time Collision Detection 7.4 Ray and Directed Line Segment Traversals
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.4 Ray and Directed Line Segment Traversals光線と方向のある線分の探索。ゲームでよくある判定が直線選択(line pick)判定です。これは光線か方向のある線分についてのクエリになります。典型的な使用方法には視野直線(line-of-sight)の判定や発射された弾丸が敵に当たったかどうかの判定があります。最初の衝突クエリとしても利用できます。これらのクエリを高速化するために階層構造を作り光線あるいは線分により交差するオブジェクトの数を最小化します。鍵となる考え方は最初にワールドを無数のセルに分割し次にそれらのセルを通りセルが含んでいるオブジェクトを貫通し交差しながら追跡していきます。
2006年08月02日
コメント(0)
-
Real-Time Collision Detection 7.3.8 Hybrid Schemes
Real-Time Collision Detection という本を読んでいます。http://www.realtimecollisiondetection.net/7.3.8 Hybrid Schemes戦略の混合。これまでの方法を組み合わせて使用することも可能です。例えば最初に均一格子への割り当てを行った後に格子の空ではない各セルにおけるデーターをさらにツリー構造に組織化することも可能です。こうすることで格子はツリーのある森の中から適切なツリーを高速に探し出す手段として機能します。また格子を1つのツリーの階層となる｢加速化のための構造｣としても利用可能です。ツリーのノードのポインタで構成されている均一な格子を考えます。各ポインタがツリーのノードを参照していて、ツリーのノードのボリュームは対応する格子のセルにできるだけ密着しているようにします。この方法で格子を用いることでクエリの間にツリーの大部分をバイパスすることができます。緩い8分木のノードと同様に格子のセルを緩く作成することも可能です。
2006年08月01日
コメント(0)
全31件 (31件中 1-31件目)
1
-
-
- ハンドメイドが好き
- 幅広レースを入れました２
- (2026-07-26 18:28:11)
-
-
-
- どんな写真を撮ってるの??（*^-^*）
- ではこれはタイタンビカス？モミジア…
- (2026-07-29 05:30:04)
-
-
-
- 機動戦士ガンダム
- 『機動戦士ガンダム』RX-78ー２ ガ…
- (2026-07-22 20:36:15)
-
