ต้นไม้ BSP ในโครงสร้างข้อมูล

ในวิทยาการคอมพิวเตอร์ วิธีการที่เรียกว่าการแบ่งพาร์ติชันพื้นที่ไบนารี (BSP) ถูกนำมาใช้เพื่อแบ่งแยกช่องว่างออกเป็นสองชุดนูนโดยใช้ไฮเปอร์เพลนเป็นพาร์ติชั่น กระบวนการแบ่งย่อยนี้ทำให้เกิดการเป็นตัวแทนของออบเจ็กต์ภายในภูมิภาคในรูปแบบของโครงสร้างข้อมูลทรีที่เรียกว่าทรี BSP

การแบ่งพื้นที่ไบนารีถูกประดิษฐ์ขึ้นในบริบทของคอมพิวเตอร์กราฟิก 3 มิติในปี 2512 โดยที่โครงสร้างของแผนผัง BSP อนุญาตให้มีข้อมูลเชิงพื้นที่เกี่ยวกับวัตถุในฉากที่เป็นประโยชน์ในการเรนเดอร์ เช่น วัตถุที่เรียงจากหน้าไปหลังด้วย เกี่ยวกับผู้ชมในสถานที่ที่กำหนด เพื่อให้เข้าถึงได้อย่างรวดเร็ว แอปพลิเคชันอื่นๆ ของ BSPinclude:บรรลุการดำเนินการทางเรขาคณิตด้วยรูปร่าง (เรขาคณิตทึบเชิงสร้างสรรค์) ใน CAD, การตรวจจับการชนกันในวิดีโอเกมและหุ่นยนต์ 3 มิติ, การติดตามรังสี และแอปพลิเคชันอื่นๆ ที่เกี่ยวข้องกับการจัดการฉากเชิงพื้นที่ที่ซับซ้อน

ภาพรวม

การแบ่งพาร์ติชันพื้นที่ไบนารีถือเป็นกระบวนการทั่วไปในการแบ่งฉากออกเป็นสองฉากซ้ำๆ จนกว่าการแบ่งพาร์ติชันจะเป็นไปตามข้อกำหนดตั้งแต่หนึ่งข้อขึ้นไป สามารถมองได้ว่าเป็นโครงสร้างทั่วไปของโครงสร้างต้นไม้เชิงพื้นที่อื่น ๆ เช่น k-d tree และ quadtrees ซึ่งไฮเปอร์เพลนที่แบ่งพื้นที่อาจมีการวางแนวใด ๆ แทนที่จะจัดแนวกับแกนพิกัดเหมือนกับที่อยู่ในต้นไม้ k-d หรือ quadtrees เมื่อนำมาใช้ในคอมพิวเตอร์กราฟิกเพื่อแสดงฉากที่ประกอบด้วยรูปหลายเหลี่ยมระนาบ ระนาบการแบ่งพาร์ติชันมักถูกเลือกให้ตรงกับระนาบที่กำหนดโดยรูปหลายเหลี่ยมในฉาก ตัวเลือกเฉพาะของระนาบการแบ่งพาร์ติชันและเกณฑ์สำหรับการทำกระบวนการแบ่งพาร์ติชันให้เสร็จสิ้นจะแตกต่างกันไปตามวัตถุประสงค์ของทรี BSP ตัวอย่างเช่น ในการเรนเดอร์กราฟิกคอมพิวเตอร์ ฉากจะถูกแบ่งออกจนกว่าแต่ละโหนดของแผนผัง BSP จะประกอบด้วยรูปหลายเหลี่ยมเท่านั้นที่สามารถแสดงผลในลำดับใดก็ได้ เมื่อใช้การคัดแยกด้านหลัง แต่ละโหนดจะประกอบด้วยชุดรูปหลายเหลี่ยมนูน ในขณะที่เมื่อสร้างรูปหลายเหลี่ยมสองด้าน แต่ละโหนดของทรี BSP จะประกอบด้วยรูปหลายเหลี่ยมเท่านั้นในระนาบเดียว ในการตรวจจับการชนหรือการติดตามรังสี ฉากสามารถแบ่งออกเป็นพื้นฐานบางอย่างซึ่งการทดสอบการชนกันหรือการแยกรังสีนั้นตรงไปตรงมา

รุ่น

การนำแผนผัง BSP ไปใช้ตามรูปแบบบัญญัตินั้นใช้สำหรับแสดงรูปหลายเหลี่ยม (ที่มีสองด้าน นั่นคือ ไม่มีการคัดแยกด้านหลัง) โดยใช้อัลกอริทึมของจิตรกร รูปหลายเหลี่ยมแต่ละรูปถูกกำหนดด้วยด้านหน้าและด้านหลัง ซึ่งสามารถเลือกได้ตามอำเภอใจและมีผลกับโครงสร้างของต้นไม้เท่านั้น แต่ไม่รวมถึงผลลัพธ์ที่ต้องการ ต้นไม้ดังกล่าวสร้างขึ้นจากรายการที่ไม่เรียงลำดับของรูปหลายเหลี่ยมทั้งหมดในฉาก อัลกอริธึมแบบเรียกซ้ำสำหรับการสร้างแผนผัง BSP จากรายการรูปหลายเหลี่ยมนั้นคือ

• เลือกรูปหลายเหลี่ยม A จากรายการ
• สร้างโหนด N ในแผนผัง BSP และเพิ่ม A ลงในรายการรูปหลายเหลี่ยมที่โหนดนั้น
• สำหรับรายการรูปหลายเหลี่ยมของกันและกัน
• หากรูปหลายเหลี่ยมนั้นตั้งอยู่ด้านหน้าระนาบที่มี A ทั้งหมด ให้ย้ายรูปหลายเหลี่ยมนั้นไปยังรายการโหนดที่อยู่ด้านหน้า A
• หากรูปหลายเหลี่ยมนั้นตั้งอยู่ด้านหลังระนาบที่มี A ทั้งหมด ให้ย้ายรูปหลายเหลี่ยมนั้นไปยังรายการโหนดที่อยู่ด้านหลัง P
• หากรูปหลายเหลี่ยมนั้นตัดกันโดยระนาบที่ประกอบด้วย A ให้แยกรูปหลายเหลี่ยมออกเป็นสองรูปแล้วย้ายไปยังรายการของรูปหลายเหลี่ยมที่อยู่ด้านหลังและด้านหน้าของ P
• หากรูปหลายเหลี่ยมนั้นอยู่ภายในระนาบที่มี A ให้เพิ่มลงในรายการรูปหลายเหลี่ยมที่โหนด N
• ใช้อัลกอริทึมนี้กับรายการรูปหลายเหลี่ยมที่อยู่ด้านหน้า A
• ใช้อัลกอริทึมนี้กับรายการรูปหลายเหลี่ยมที่อยู่ด้านหลัง A