Computing Dynamic Changes to BSP Trees

Created: 2022-03-07T17:19:59-06:00

Return to the Index

This card pertains to a resource available on the internet.

Basically takes BSP trees and:

• Incrementally adds geometry, building up the tree for each polygon
• Incrementally removes geometry when the object is moved, rebalancing the tree after removal
• Moves items by removing and re-adding them to the tree

BSP Trees

• A binary tree holding planes (and faces that belong to them)
• Each node in the tree represents a plane
• Each node (plane) has the polygons along that plane
• The left is the 'front' of the plane and the right is the 'back'
• Provides efficient removal of faces based on view orientation but must be computed ahead of time

Some variations of the trees exist where objects are added in a dynamic fashion. Doing so requires choosing separation planes that cut up the space between where objects are.