1. B-rep Streams (สตรีม B-rep)
Producer Process นำ B-rep (Boundary Representation) จากไฟล์มาตรฐาน (Wavefront OBJ, Java3D) เข้าสู่ Input Stream ของ Geometric Pipeline Polygons และ Normals ต้อง Oriented ตรงกัน อาจต้อง Filter Non-planar Polygons และ Geometric Inaccuracies Output: Stream ของ Triangles ที่ Oriented ตรงกัน → สร้าง Twin Progressive-BSP Trees
2. B-rep to BSP Algorithm Outline
ขั้นตอนหลัก: คำนวณ Inertia ของ Triangle Subsets โดย contraction ของ Inertia แต่ละ Triangle → Eigen Decomposition ของ Inertia Tensor เพื่อ Bound Shape อย่างเหมาะสมแบบ Recursive
ใน d-Dimension: Shape Confinement = 2d Hyperplanes (2 ต่อ Eigenvector ของ Euler Matrix) Intersection = Best-fitting Hyperparallelepiped ใน 3D = 6 Planes
Initialization
- คำนวณ Affinely Extended Euler Tensors ของแต่ละ Input Triangle (Linear Time)
- รวม Triangle ทั้งหมดกับ BSP Root
- รวมทั้ง E3 Space (Convex) กับ Root
- ตั้ง Root Label = FUZZY
Recursive Case
- แบ่ง FUZZY Cell ด้วย ≤ 6 Orthogonal Hyperplanes ⟂ Eigenvectors ของ Euler Tensor ของ Triangle Subset ปัจจุบัน
- Plane คำนวณจาก Min/Max ของ Linear Function w = a·v บน Vertices v ของ Subset (a = Eigenvector)
- แต่ละ Eigenvector สร้าง ≤ 3 Convex Cells: {OUT, FUZZY, IN} หรือ {OUT, FUZZY, OUT}
- แต่ละ FUZZY Cell แบ่งต่อด้วย Principal Hyper-plane ของ Max Eigenvector
- Triangle Subset น้อยลงถูก Assign ให้แต่ละ Cell ผ่าน Containment Test ของ Vertices
- Triangles ที่ตัด Plane → Split → (Sub)triangles Assign ให้ Subtrees
Base Case
หยุด Recursion เมื่อ Cell มี Triangle น้อยพอ → Final Division ด้วย Planes ของ Boundary Triangles
สรุป
อัลกอริทึมแปลง B-rep (Polygon Soup) → BSP Tree ใช้ Inertia Tensor + Eigen Decomposition เพื่อ Partitioning ที่ Optimal เหมาะสำหรับ Geometry Processing, Rendering, Collision Detection
