[MT97]
Fast, minimum storage ray-triangle intersection. Tomas Möller and Ben Trumbore. Journal of Graphics Tools, 2(1):21--28, 1997. We present a clean algorithm for determining whether a ray intersects a triangle. The algorithm translates the origin of the ray and then changes the base to yield a vector (t u v)T, where t is the distance to the plane in which the triangle lies and (u,v) represents the co
lucille 開発日記: タイトフィット OBB
タイトフィット OBB OBB(Oriented Bounding Box, 有向バウンディングボックス)は、たぶんコンピュータグラッフィクスの世界では、 SIGGRAPH 1996 で発表された論文がその起源として有名かと思います。 OBB-Tree: A Hierarchical Structure for Rapid Interference Detection この論文を発表した UNC(ノースカロライナ大学) の Gamma(Geometric Algorithms for Modeling, Motion and Animation) 研究グループは、ジオメトリの研究で有名ですね(なんか昔は違うグループ前だった気がするけど気のせいかな...) 点群(CGの場合ではポリゴンの頂点群)から、それをタイトフィットに囲むような OBB を求めるカギは、点群の直径(Diameter of
☆PROJECT ASURA☆ [OpenGL] 『Quickhullアルゴリズム』
あるものを作りたいと思ったのですが，まずは凸包を作成する必要があったので， 今回は凸包を作成するのに使われるQuickhullアルゴリズムを実装してみました。 QuickhullアルゴリズムはQuickという名の通り，クイックソートの考え方に似ています。 今回は2次元という風に限定して説明しますが，3次元の場合は同様にしてできるそうです。 まず下の図のように点の集合があると仮定します。 最初に，これらの点の集合の中からx座標が最大と最小となる2点を求めて，稜線を引きます。 次に，線が引かれることによって，線の上側と下側の2つの領域にわけることができます。下の図の場合はうまく2つの領域に分かれますが，場合によっては線の上側に点がない場合もあり，2つの領域にわかれない場合もあります。 つぎに，各領域に関して着目し，各点から稜線に向かって垂線を下ろし，垂線の長さが最大となる点を求めます。 垂直距
3次元ベジェ曲線のバウンティボックスを求める - Pashango’s Blog
■ベジエ曲線のバウンディングボックス http://d.hatena.ne.jp/nishiohirokazu/20090616/1245104751 InkscapeのSVG解析ですね、ええわかります。 Inkscape SVGは独自拡張記法で回転中心という項があるんですよね、しかし、バウンティボックスという拡張記法は無いんです。 まったく、気の利かない！（逆切れ） 実は私もInkscapeSVGのツールを作っていまして、3次ベジェ曲線のバウンティボックスを求める関数を作っていましたので、共有できればなと・・・ さて、3次のベジェ曲線のバウンティボックス問題なんですが、 下がベジェの方程式です。 f(t) = (1-t)**3*P1 + 3*t*(1-t)**2*P2 + t**2*3*(1-t)*P3 + t**3*P4バウンティボックス問題は簡単に言ってしまうと「3次方程式の極値」を
ベジエ曲線のバウンディングボックス - 西尾泰和のはてなダイアリー
Bézier curve - Wikipedia, the free encyclopedia B(t) = (1-t)^3 * P0 + 3 * (1-t)^2 * t * P1 + 3 * (1-t) * t^2 * P2 + t^3 * P3 なので B'(t) = -3 * P0 * (1 - t)^2 + 3 * P1 * (1 - t)^2 - 6 * P1 * (1 - t) * t + 6 * P2 * (1 - t) * t - 3 * P2 * t^2 + 3 * P3 * t^2 の解t = *1(-3 P0+9 P1-9 P2+3 P3!=0)のうち0~1に収まるtの時のB(t)の値を計算して、B(0) = P0、B(1) = P3とあわせて最小値と最大値を求めればいいな。たぶん。後で実装しよう。 あってそう。 (ここにあったコードは全然あっていなかったので削除しま
もっと高速に－線分交差判定－
線分交差判定といっても、すべての与えられた線分に対して、同様な計算を 行って判定していたのでは、無駄が多いように見えます。場合によっては もっと単純な軽い判定で行えるはずです。そこで、 『場合分けによるラフチェック』を もっと簡単に－線分交差判定－のプロシージャ に追加して、次のように変更します。 '構造体 Private Type POINT x As Double y As Double End Type '座標 p1,p2 を結ぶ線分と座標 p3,p4 を結ぶ線分が交差しているかを調べる 'ただし、線分が重なっている場合(3点,4点が一直線上にある)、「交差している」、と判定します。 Private Function intersectionEX(p1 As POINT, p2 As POINT, _ p3 As POINT, p4 As POINT) As Boolean 'x座標
もっと簡単に－線分交差判定－
ここでは、線分交差判定の定石ともいえる方法を紹介しています。 線分と直線の見落としがちな大切な定義です。
その13 OBBとOBBの衝突
ホーム＜ゲームつくろー！＜衝突判定編＜ OBBとOBBの衝突 3D衝突編 その13 OBBとOBBの衝突 衝突の本丸の1つ「OBBとOBB」の衝突です。大きさの違うお互いに3次元的に回転した直方体が衝突しているかどうかを調べるというのはやはり簡単ではありませんが、これができると多種多様な方面で役に立ちます。OBB同士の衝突として主流なのは「分離軸判定」と呼ばれる方法でして、ここでもそれについて見ていきます。ちょっと深呼吸してご覧下さい(^-^; ① 「分離軸」判定とは？ OBBの衝突には「分離軸」という物が登場します。これがいったい何なのか？まずは下の図をご覧下さい。 上のOBBは明らかに衝突していません。この時、両方のOBBを分ける直線が「絶対に」存在します。この直線は、ちょっと小難しい言葉で言うと分離超平面（Separating hyperplane）と呼ばれています。直線なのに平面と
第4回 平面走査法による線分の交差検出（中編） | gihyo.jp
はじめに 今回は、平面走査法による線分交差検出のデータ構造を実装していきます。内容がかなり難しくなってきますが、説明とソースコードを納得できるまで読み返していただければと思います。 平面走査法と水平方向 前回は、多数の線分から交差を検出する方法として、平面走査法（plane sweep algorithm）の考え方を紹介しました。これは、x軸に平行な走査線を上から下へと動かしていき、走査線と交わる線分のみを計算対象とすることで、交差検出の計算量を減らすというものでした（図1）。 図1 平面走査法 実は、これだけでは考え方としてまだ不足なのです。図2を見てください。図2では図1と違い、すべての線分が同じくらいのy座標範囲にまとまって存在しています。こうした場合、走査線が多数の線分と交わる時間が大半を占めるため、計算量をほとんど削減できないことになってしまいます。 図2 走査線と多数の線分
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.graphics.cornell.edu/pubs/1997/MT97.pdf
レンダリングサンプル7 - ブレゼンハムのアルゴリズム（円） - Windows Live
レンダリングサンプル6 - 誤差の最小化を基準とする基本的なアルゴリズムで円を描く - Windows Live
レンダリングサンプル5 - 円を公式通りに描画する - Windows Live
円についての考察 - Windows Live
レンダリングサンプル3 - ブレゼンハムのアルゴリズム（直線） - Windows Live
レンダリングサンプル2 - 直線の描画を数式どおりに実装する - Windows Live
直線に関する考察 - Windows Live
http://gamma.cs.unc.edu/users/gottschalk/main.pdf
https://www.cs.princeton.edu/~chazelle/pubs/BoxtreeHierarchRepSurf3D.pdf
RAPID - Paper and Errata on OBBTrees