BSP Trees (Binary Space Partitioning) ในโครงสร้างข้อมูล

แนวคิดพื้นฐาน

Binary Space Partitioning (BSP) = วิธีแบ่ง Space แบบ Recursive เป็น 2 Convex Sets ด้วย Hyperplanes สร้าง Tree Data Structure = BSP Tree แสดงวัตถุในพื้นที่

ประดิษฐ์ 1969 สำหรับ 3D Computer Graphics: BSP Tree ให้ Spatial Info (Front-to-back Ordering) สำหรับ Rendering เร็ว ใช้เพิ่มใน: CAD (CSG), Collision Detection (Games/Robotics), Ray Tracing, Complex Spatial Scenes

Overview

BSP = Generic Process: Recursive Divide จนกว่า Partition จะตรงตามเงื่อนไข Generalization ของ k-d Trees และ Quadtrees: Hyperplanes มี Orientation ใดก็ได้ (ไม่ผูก Axes)

Computer Graphics Rendering: แบ่งจนแต่ละ Node มี Polygons ที่ Render ได้ในลำดับไหนก็ได้ Back-face Culling → Convex Set ต่อ Node Double-sided → Single Plane ต่อ Node

Generation Algorithm (Canonical - Painter's Algorithm)

1. เลือก Polygon A จาก List
2. สร้าง Node N ใน BSP Tree, เพิ่ม A ใน Polygon List ของ Node นั้น
3. สำหรับ Polygon อื่นๆ ใน List:
   • อยู่หน้า Plane ของ A ทั้งหมด → ย้ายไป List "หน้า A"
   • อยู่หลัง Plane ของ A ทั้งหมด → ย้ายไป List "หลัง A"
   • ถูก Plane ของ A ตัด → Split เป็น 2 Polygons → ย้ายไป List "หน้า" และ "หลัง" ตามลำดับ
   • อยู่ใน Plane ของ A → เพิ่มใน List ของ Node N
4. Apply Algorithm ซ้ำกับ List "หน้า A"
5. Apply Algorithm ซ้ำกับ List "หลัง A"

หมายเหตุ

Polygon แต่ละตัวมี Front/Back Side (เลือกได้อิสระ) ส่งผลต่อ Tree Structure แต่ไม่ส่งผลต่อ Rendering Result