Uppsala Master's Theses in Computing Science
Examensarbete 179
2001-01-19
ISSN 1100-1836
Binary Space Partioning Trees and Polygon
Removal in Real Time 3D Rendering
Samuel Ranta-Eskola
Information Technology
Computing Science Department
Uppsala University
Box 311
S-751 05 Uppsala
Sweden
Supervisor: Erik Olofsson
Examiner:
Passed:
BSP-TREES AND POLYGON
REMOVAL IN REAL TIME 3D
RENDERING
By Samuel Ranta-Eskola
Uppsala University
Abstract
When the original design of the algorithm for Binary Space Partitioning
(BSP)-trees was formulated the idea was to use it to sort the polygons in the
world. The reason for this was there did not exist hardware accelerated Z-
buffers, and software Z-buffering was too slow. Today that area of usage is
obsolete, since hardware accelerated Z-buffers exist. Instead the usage is to
optimise a wide variety of areas, such as radiosity calculations, drawing of the
world, collision detection and networking.
We set out to examine the areas where one can draw advantages of the
structure supplied and study the generating process.
As conclusion a BSP-tree is a very useful structure in most game engines.
Although there are some drawbacks with it, such as that it is static and it is
very expensive to modify during run-time. Hopefully some ideas can be taken
from the BSP-tree algorithm to develop a more dynamic structure that has
the same advantages as the BSP-tree.
TABLE OF CONTENTS
Number Page
1. Introduction ......................................................................................................1
• Background..............................................................................................1
• Problem Statement.................................................................................1
2. BSP-Trees.........................................................................................................3
• Background..............................................................................................3
• The BSP algorithm .................................................................................4
o CLASSIFY-POINT ....................................................................4
o POLYGON-INFRONT..................................................................5
o IS-CONVEX-SET ......................................................................5
o CALCULATE-SIDE.....................................................................7
o CHOOSE-DIVIDING-POLYGON................................................8
o GENERATE-BSP-TREE............................................................11
• Drawing the BSP-tree...........................................................................15
o DRAW-BSP-TREE ....................................................................15
3. Hidden Surface Removal..............................................................................16
• Background............................................................................................16
• Portal Rendering...................................................................................17
o INSIDE-FRUSTUM...................................................................19
o RENDER-PORTAL-ENGINE.....................................................19
• Placing the Portals ................................................................................20
o CLIP-POLYGON.......................................................................21
o PLACE-PORTALS.....................................................................22
• Our Solution..........................................................................................26
• Calculating the PVS..............................................................................26
ii
o DISTRIBUTE-SAMPLE-POINTS............................................28
o RAY-INTERSECTS-SOMETHING-IN-TREE.........................30
o CHECK-VISIBILITY..............................................................31
o TRACE-VISIBILITY..............................................................32
• Static Objects.........................................................................................33
o PUSH-POLYGON.......................................................................33
4. Radiosity ..........................................................................................................35
• Background............................................................................................35
• Radiosity in BSP-trees..........................................................................36
o RADIOSITY ..............................................................................37
5. Summary of BSP-Tree Rendering ...............................................................39
• RENDER-SCENE.....................................................................................39
6. Physics In BSP-Trees.....................................................................................41
• Future Position Calculation.................................................................33
• Collision Detection and Collision Handling......................................44
o CALCULATE-COLLISIONRADIUS..........................................47
o PRE-CHECK-COLLISION.......................................................48
o GET-COLLIDING-POLYGON...................................................52
o OBJECTS-COLLIDE ................................................................53
o GET-COLLIDING-POLYGON (RE-WRITTEN) ....................55
o COLLISION-HANDLING..........................................................57
7. Network Optimization Using BSP-Trees....................................................59
8. Future Work....................................................................................................60
9. Conclusions.....................................................................................................61
10. Appendix .........................................................................................................63
iii
LIST OF FIGURES
Figure Page
Cyclic overlap 3
The difference between a convex set and a non-convex set. 4
The non-symmetric nature of the comparison POLYGON-INFRONT 5
Splitting a polygon 7
Problems when choosing dividing polygon. 10
Example structure 12
The result of a split at polygon 16 13
The second step. 14
The final tree. 14
View frustum clipping 17
Culling of objects 18
Removing coinciding parts. 23
An example map for automatic portal placement. 24
Visibility between nodes. 26
Sample of Radiosity. 38
A human encapsulated in an ellipsoid. 41
Prohibited and allowed move. 42
Object move. 45
Incorrect collision. 45
Correct collision 45
Side value. 46
Collision radius. 47
Testing if a object passes through a polygon. 49
Perpendicular planes for a triangle. 49
Moved perpendicular planes. 50
The effective collision area of a triangle. 51
The correct collision area of a triangle. 51
