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 走査線と多数の線分
第3回 平面走査法による線分の交差検出（前編） | gihyo.jp
今回から平面走査法という手法による、線分の交差検出について解説します。この手法を使うことで、多数の線分の中から交点を高速に見つけ出すことができます。 はじめに 計算幾何学では、巨大な入力データを扱う可能性を想定して、計算量の少ない効率的なアルゴリズムの追求が行われます。今回からは、線分の集合から交差を検出する問題を取り上げます。平面走査法と呼ばれるアルゴリズムを使用することで、総当たり式の実装に比べ、計算量を大きく削減できることを見ていきます。 多数の線分から交差を見つける 前回、線分を表すLineSegmentクラスを作成し、2つの線分が交差するかどうかを調べるintersects()メソッドや、交点座標を求めるgetIntersectionPoint()メソッドを実装しました。 さて今後、プログラムの扱う線分が100個、1,000個、あるいはそれ以上に増えたときのことを考えてみましょう
第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
2D衝突編その5 円と線分から多角形と円へ
ホーム < ゲームつくろー！< 衝突判定編 2D衝突編 その５ 円と線分から多角形と円へ 多角形は線で構成された閉じた図形です。多角形と円が衝突しているかどうかを判定できれば、複雑な形状をしたものと球とを正しく衝突判定させる事ができるようになります。効率はあまり良くありませんが、知って損はありません。 ひとつ注意。ここでの多角形は「凸多角形（多角形のどの内側の角度も180度以下である多角形）」です。凹多角形だとうまくいきません。 ① 多角形の定義 まず多角形を定義します。記号化がちょっと面倒なのですが、配列のような書き方にしておきます： 多角形 ： 頂点P[n](x[n], y[n]) 円は言わずもがなですが、中心点の座標と半径で定義できます： 円 ： 中心点C(xc, yc)、半径r では下の図を御覧ください： この図は多角形の一部と幾つかの衝突を起こしている円の状態を示しています。C1
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
レンダリングサンプル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
線分と円が交差する条件