CSCE 441 Lecture 22

« previous | Friday, March 7, 2014 | next »

BSP Trees

Building

• Choose splitting polygon
• Sort all polygons as:
  • front (all vertices in front)
  • behind (all vertices behind)
  • crossing (some vertices in front, some behind)
  • on (all vertices on plane)
• On polygons become root
• Add all front polygons to the front child
• Add all behind polygons to the back child
• Split crossing polygons into front and back polygons
• Recur on children

Rendering

We care only about position of the viewer

Traversing tree produces rendering order from back to front

If eye is in front of the plane

1. draw back polygons
2. draw on polygons
3. draw front polygons

If eye is behind plane

1. draw front polygons
2. draw on polygons
3. draw back polygons

If eye is on the plane (order of following doesn't matter)

• draw front polygons
• draw back polygons

Advantages

• No depth comparisons needed
• Polygons split and ordered automatically

Disadvantages

• Computationally intense pre-process stage
• Restricts algorithm to static scenes
• Splitting increases polygon count
• Redraws pixel many times (overdraw)
• Choosing a splitting plane is not an exact science

Improved Rendering

Take advantage of view direction to cull away polygons behind viewer

OpenGL

glEnable(GL_DEPTH_TEST);
glEnable(GL_CULL_FACE);
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glCullFace(GL_BACK);