Bsp

Split the world in half

A BSP tree splits up space into half-spaces along a hyperplane. A hyperplane is in 2D is a line and in 3D its a plane. One of the half-spaces is the front half-space and the other is the back. Each node in the tree contain the hyperplane used to split the space and then links to the front node and the back node.

Node based vs leaf based

solid trees

Buidling

Rendering

Collision

Reference

• 3D Rendering with Binary Space Partitions - 2014
• DOOM port and BSP visualization - 2014. Video
• Object-Environment Collision Detection using Onion BSPs - 2013
• Divide and Conquer: Partition Trees and Their Uses - 2008
• BSP Collision Detection As Used In MDK2 and NeverWinter Nights - 2001 . Video
• Binary Space Partitioning Tutorial - 2001
• I: Creating a Solid Node Based BSP Tree Compiler & Renderer
• II: Creating a Solid Leaf Tree , Portal Generation , Precalculating a PVS and Adding Frustum Rejection
• Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering - 2001
• Dynamic Plane Shifting BSP Traversal - 2001
• Ramblings in Realtime - 2000
• BSP Tree FAQ - 1999
• Intro to 3D Graphics Programming: Volume V - 1999
• Practical Collision Detection - 1999
• BSP Tree Frequently Asked Questions - 1998
• Binary Space Partition Trees by Carl Shimer - 1997
• A Tutorial on Binary Space Partitioning Trees - 1996
• Binary Space Partitions for 3D Subdivisions
• Bsp Tutorial by Steven Cento

How to Use BSP Trees to Generate Game Maps - 2013

Binary Space Partitioning Tutorial

https://www.cs.utah.edu/~jsnider/SeniorProj/BSP1/default.html

Binary Space Partitioning Tutorial Part II

http://www.cs.utah.edu/~jsnider/SeniorProj/BSP/default.htm