[舊帖] UVa 11275 3D Triangles

Old Post in Xanga on 2010-02-18

---

Problem Statement:
Given 2 triangles in R³, check whether they share at least 1 common point.

---

今日 Research 有 3D 野要搞...
Google... 無意間見到 一個 theorem - SAT (?)
原 來 SAT = Separating Axis Theorem

發覺 ACM 可能有用喎!

應 用落呢題之後... Runtime 快過以前 Ray / Plane Intersection !
而且對比之下, 呢個方法更加 mechanical, 貌似好多地方都用得著

---

呢題用到既係 SAT 既特例 (亦即係 reference 份 Paper 講既野)

大意係咁：
Given 兩個 Polyhedra (A, B)
[general case 係 convex set, 但呢度只討論 polyhedra]
問佢地可唔可以俾一塊平面分開

其實咁等價於問你：
存唔存在 一條線, 佢地既projection係 disjoint (見下圖)



呢條咁既 線, 叫做 Separating Axis

Turns out, SAT 話你知
只要試 O(N^2) 咁多支 Axes
[where, # Vertices = # Faces = # Edges = O(N)]
就可以知道 Separating Axis 是否存在

要試既 Axes 包括：
1) 每一塊面既 Normal
2) CROSS_PRODUCT(A.edge[i], B.edge[j]) [A.edge[i] = A 既 第 i 條 edge]

如果試曬, 都發覺佢地既 projection 唔係 disjoint
咁 可以conclude 佢地兩個 set 有 intersection

---

Source:
* SAT wiki
* Fast 3D Triangle-Box Overlap Testing - Tomas Akenine-Möller*. Department of Computer Engineering,. Chalmers University of Technology

---

註:
唔 好將 Separating Line (2D) / Plane (3D) 同 Separating Axis 撈亂
後者係 用黎 project object 落去果支 axis
前者係 physcially 將兩個 set 分開既東西

---

Also:
ICPC 4639 - Separate Points
[= UVa 10256 - The Great Divide]