Ray-Box Testすげえ

今日もこの本から。
箱と線分の交差判定という問題があります。問題がプリミティブなだけに、昔から随分研究がなされています。特に２Ｄの矩形と線分の交差判定はかなり研究されているみたいで、ポリゴンの射影変換後のクリッピングにも応用されています。
この分野の有名な研究にCohen-Sutherland(CH)とLiang-Barsky(LB)というものがあります。CHの方は、矩形境界線(境界面)とポイントとの位置関係をビット表現するもので、LHは、矩形表現と直線の表現があるときに、境界線(境界面)が無限の長さを持つときの交点を瞬時に計算する手法です。
実はこのCHとLBの研究のあわせ技で、開始点s,終了点tの２点を結ぶ線分が箱を通過するかどうかを高速に計算できるようなのです。というのが今日読んだ話です。CHのビット情報にとある解釈をする事で、その解釈情報とLBの考え方を引っ付ける事で(存在するなら)高速に線分が矩形にどう切り取られるかの情報を計算していました。既存の研究が導き出すパラメータに新しい解釈を与えて別の研究と引っ付ける事で何か新しいものを生み出すというのが格好いいですね。正直アルゴリズムを理解したときにはかなり感動しました。
CH,LBの研究についてはググったらすぐに出てきますが一応リンクを貼っておきます。図入りなのでかなり分かりやすいです。
http://www.den.rcast.u-tokyo.ac.jp/~suzuki/class/cad/ohp/6scanconv.pdf