Background

The need of removing what is not visible has been and always will be extremely high in the gaming industry, even though graphic cards evolve at gigantic rates and things that were true a couple years ago are not even remotely true these days. When a game is created a goal frame rate[*] is set. The lowest acceptable rate on a target system[*] use to be around 30 frames/second. A couple of years ago this meant putting out over 5000 textured polygons per frame could be too much. These days there are graphic cards in the market with the ability to draw hundreds of million of polygons per second during optimal conditions. Still there is a need of removing hidden parts. Why? Each hidden polygon that is drawn could be replaced by a polygon that is visible, hence increasing the detail in the scenes[*], making the game visually more attractive. The question is how far one should go to remove hidden polygons. To remove a hidden part heavy computations are needed to be done, such as view frustum[*] culling and portal[*] rendering[1]. The CPU time used to do these computations could be used to enhance other effects in the game, such as AI and collision detection. Hence there is a lot to take in to consideration when developing algorithms for removal of hidden surfaces. There are almost no games that go so far as to remove each polygon that is hidden. Most games are satisfied with the removal of whole sets of polygons, such as nodes, objects etc. They do not consider individual polygons, so it seems like the correct way to go is to accept some overdraw to limit the computations when removing hidden surfaces.

The most common technique to remove hidden surfaces when creating a FPS is portal rendering. This technique is very well suited to utilize the benefits of BSP-trees, though the use of BSP-trees is not necessary. We considered to use this but thought that a more static representation could give a speedier rendering of the BSP-tree. The portal rendering has some nice side effects such as mirrors and surveillance cameras that we cannot do with our technique, but on the other hand, our technique require much less computations during run-time.

Portal Rendering

The world can be described as several sectors that are connected to each other through portals. A sector is a convex and closed set of polygons, where closed means that there is no way for a line drawn in the sector to get out of the sector without encountering a polygon[2]. This means that each hole in each node must be filled with a portal polygon. The placement of portal polygons can either be done manually or automatically. As we described before the need of convex sectors has disappeared with hardware-accelerated Z-buffers, so many game engines skip that criteria. But we are going to describe how to do it the old fashioned way.

The basic idea with a portal engine is that when you render a scene from a viewer’s position with a viewing frustum and encounter a portal polygon, the portal clips the viewing frustum. Then the adjacent sector is rendered from the same viewer’s position but with the new viewing frustum. This is a very simple approach and is very well suited for a recursive function. Many objects that are visible can easily be culled away since the viewing frustum is limited only to be exactly what you see. Below is a picture of how a viewing frustum can be clipped in a portal engine:

Figure 1: View Frustum Clipping

In the figure above the viewer is positioned at V, the original view frustum is F1. When F1 encounters portal polygon P1 it is clipped and renamed to F2. Later on F2 encounters portals P2 and P3 and is clipped to F3 and F4. When encountering portal P4, F3 is trimmed to F5 and F4 is trimmed to F6. This process is well suited for a recursive function.

To cull away an object in a portal-rendering engine, as matter of a fact any 3D-engine, there are a series of steps that can be done to speed up the process. First, compute a bounding sphere for that object; a bounding sphere is the smallest sphere that can hold each vertex in an object. Optimally this is done once and for all during the creation of the object. Then, that sphere is tested against each plane in the viewing frustum. If it is on the completely negative side of any one of those planes the object is not visible and is not drawn. The figure below describes a situation where one object is culled, thus not drawn, while the other is drawn.

Figure 2: Culling of Objects

Object 1 in the figure is on the positive side of the right plane in the view frustum, but it is on the negative side of the left plane so it is culled. The other object (2), is completely on the positive side of the left plane while a part of it is on the positive side of the right plane so it cannot be culled.

The original idea was that portal engines would have zero overdraw by clipping the polygons so that only the visible area would be drawn. These days this is an awful waste of processor time. But since a polygon can be encountered several times in the recursive loop that draws the scene we need to know if a polygon has been drawn or not. A good way to do this is to tag the polygons with a frame counter which indicates which was the last frame the polygon was drawn. That is the case for the right wall in figure 4, which should be drawn in frustum F5 and frustum F6, polygons has to be tagged to tell if they have been drawn this frame or not. Otherwise there will be Z-buffering errors.

In order to be able to render in portal engine we need to define what a view frustum consist of. A view frustum is a structure that holds n number of planes, each of these planes’ normals faces inwards the view frustum, thus enclosing a volume referred to as inside the frustum. Below there is an algorithm on how to calculate whether a polygon is inside a frustum or not, in this algorithm we use the function CLASSIFY-POINT as if it takes a plane and a point as parameters.

► INSIDE-FRUSTUM
* Indata:
*   Frustum – The frustum to check whether the polygon is inside or not.
*   Polygon – The polygon to check.
* Outdata:
*   Whether the polygon was inside the frustum or not.
* Effect:
*   Checks each point in the polygon versus each plane in the view
*   frustum. If any point is on the positive side of all planes the
*   polygon is counted as inside.

INSIDE-FRUSTUM (Frustum, Polygon)
1 for each point Pt in Polygon
2    Inside = true
3    for each plane Pl in Frustum
4       if (CLASSIFY-POINT (Pl, Pt) <> INFRONT)
5           Inside = false
6 if (Inside)
7     return true
8 return false

The main rendering function in a portal engine would look something like this:

► RENDER-PORTAL-ENGINE
* Indata:
*   Sector – The sector the viewer is in.
*   ViewFrustum – The current viewing frustum.
* Outdata:
*   None
* Effect:
*   Renders the polygons in a portal engine. Where the world is
*   represented as sectors connected by portals.

RENDER-PORTAL-ENGINE (Sector, ViewFrustum)
1 for each polygon P1 in Sector
2     if (P1 is a portal and INSIDE-FRUSTUM (ViewFrustum, P1))
3         NewFrustum = CLIP-FRUSTUM (ViewFrustum, P1)
4         NewSector = get the sector that is connected with the current sector through portal P1
5         RENDER-PORTAL-ENGINE (NewSector, NewFrustum)
6     else if (P1 has not been drawn yet)
7         draw P1
8 return

Placing the Portals

As we mentioned before, one of the big problems in a portal engine is the placement of the portals. It is a very time consuming process to manually place the portals, not to mention the skill required of the map designer. As with many other things, that time could be better used in other places. So a good algorithm for automatic portal placement is needed. A colleague of mine, Andreas Brinck, has come up with a good solution to this problem. To use his solution a BSP-tree will have to be used.

The general idea is that each portal in the tree must be coinciding with a plane defined by a dividing polygon in the tree. Out of each of these planes a portal polygon is created, that portal polygon is initially a four-sided polygon that exceeds the bounding box[*] of the node it is located in. Then each portal polygon is pushed down the sub trees of the node it is in. When a portal polygon passes through a node in one of its sub trees the plane defined by the dividing polygon in that node clips it, it is also clipped by the polygons in that node if the node is a leaf. If a polygon is clipped, the two resulting parts are sent down from the top of the tree. When a portal polygon is not in need of any clipping, it is sent down to the sub trees of the node currently visiting. This means that if it is on the positive side of the plane it will be sent down the right sub tree, and if it is on the negative side it will be sent down the left sub tree. But if it is coinciding with the plane defined by the dividing polygon in the current node it will be sent down both sub trees.

In order to be able to define the algorithm that places all the portals in the tree we need to define how to clip a polygon, for this we need to assume there is a function called INTERSECTION-POINT that returns a intersection point between a plane and a line between two 3D points.

► CLIP-POLYGON
* Indata:
*   Clipper – The plane/polygon to clip the other polygon versus.
*   Polygon – The polygon to clip.
* Outdata:
*   The two resulting pieces after the clipping.
* Effect:
*   Clips the polygon by the plane defined by the clipper polygon. If
*   the polygon isn’t spanning the clipper one of the resulting parts
*   will be an empty polygon

CLIP-POLYGON (Clipper, Polygon)
1  RightPart = {}
2  LeftPart = {}
3  for each point edge E in Polygon
4      Side1 = CLASSIFY-POINT (Clipper, E.Point1)
5      Side2 = CLASSIFY-POINT (Clipper, E.Point2)
6      if (Side1 <> Side2 and Side1 <> COINCIDING and Side2 <> COINCIDING)
7          Ip = INTERSECTION-POINT (Clipper, E)
8          if (Side1 = INFRONT)
9              RightPart = RightPart U E.Point1
10             RightPart = RightPart U Ip
11             LeftPart = LeftPart U Ip
12             LeftPart = LeftPart U E.Point2
13         if (Side1 = BEHIND)
14             LeftPart = LeftPart U E.Point1
15             LeftPart = LeftPart U Ip
16             RightPart = RightPart U Ip
17             RightPart = RightPart U E.Point2
18     else
19         if (Side1 = INFRONT or Side2 = INFRONT or Side1 = COINCIDING and Side2 = COINCIDING)
20             RightPart = RightPart U E.Point1
21             RightPart = RightPart U E.Point2
22         if (Side1 = BEHIND or Side2 = BEHIND)
23             LeftPart = LeftPart U E.Point1
24             LeftPart = LeftPart U E.Point2
25 return (RightPart, LeftPart)

Now we can define how to distribute the portals in a BSP-tree. The algorithm is initially called with a portal polygon that is larger than the bounding box of root node of the tree. We got the design to this function from a fellow game programmer, Andreas Brinck, currently employed at DICE, Sweden.

► PLACE-PORTALS
* Indata:
*   PortalPolygon – Polygon to push down the tree
*   Node – The node that we are currently visiting.
* Outdata:
*   None
* Effect:
*   Pushes a portal polygon down through the tree clipping when it
*   needs it. The output of this function will be that each node
*   contains a list of portal polygons where each portal connects
*   exactly two nodes.

PLACE-PORTALS (PortalPolygon, Node)
1  if (IS-LEAF (Node))
       // The portal is checked against every polygon in the node. When the
       // portal polygon is spanning the plane defined by a polygon it will
       // be clipped against that plane. The two resulting parts will be
       // sent down from the top of the tree again.
2      for (each polygon P2 in Node)
3          IsClipped = false
4          if (CALCULATE-SIDE (P2, PortalPolygon) = SPANNING)
5              IsClipped = true
6             (RightPart, LeftPart) = CLIP-POLYGON (P2, PortalPolygon)
7             PLACE-PORTALS (RightPart, RootNode)
8             PLACE-PORTALS (LeftPart, RootNode)
9      if (not IsClipped)
10         Remove the parts of the portal polygon that coincide with
           other polygons in this node.  //see description below
11         Add this node to the set of connected nodes in this portal polygon.
12 else
13     if (the dividing polygon of this node hasn’t been pushed down the tree)
14         Create a polygon P that is larger than the bounding box that
           contains all polygons in the sub trees of this node that
           lies in the same plane as the dividing polygon.
15         PLACE-PORTALS (P, Node.LeftChild)
16         PLACE-PORTALS (P, Node.RightChild)
17     Side = CALCULATE-SIDE (Node.Divider, PortalPolygon)
18     if (Side = POSITIVE)
19         (RightPart, LeftPart) = CLIP-POLYGON(P2, PortalPolygon)
20         PLACE-PORTALS (RightPart, RootNode)
21         PLACE-PORTALS (LeftPart, RootNode)
22     if (Side = POSITIVE or COINCIDING)
23         PLACE-PORTALS (PortalPolygon, Node.RightChild)
24     if (Side = NEGATIVE or COINCIDING)
25         PLACE-PORTALS (PortalPolygon, Node.LeftChild)

Complexity Analysis

This function is extremely complex to analyze and since it is not our design we will not analyze it. To clarify line 10 we need to show what happens when we remove the coinciding parts between the portal polygon and other polygons in the node. See the image below:

Figure 3: Removing coinciding parts

In Figure 3 a portal polygon has reached a leaf. The dark gray areas marked as 1 is removed during the pushing down the tree. Parts 2, 3 and 4 which is painted in light gray is coinciding with polygons in the end node thus they are removed. The only remaining part is the part marked as 5; this is going to be used as a portal. The previous algorithm might look very complex at first sight but it is in fact very simple and intuitive. In the end every portal polygon will end up in exactly two nodes. These are the two portals that will be visible from each other. The following is an example of the algorithm implemented:

Figure 4: An example map for automatic portal placement

1. Portal polygon 1 (s1) enters node n1.

In n1 the splitting polygon will be clipped to fit and one part will be removed since it coincides with one of the polygons in the pillar. This leaves us with two polygons, namely p1 and p2. These two polygons replace s1.

2. p1 and p2 enters node s2

In node s2 p1 since it is on the positive side of s2 together with splitting polygon s2 will be sent to node n2. p2 (because it is on the negative side of s2) together with s2 will be sent further down to s3, none of them will be clipped since they do not cross splitting polygon s2.

3. p1 and s2 enters node n2

In n2 p1 is accepted as a portal, so it is not changed in node n1 either, and a part of p3 is removed since it coincides with a polygon in the pillar. Polygon s2 that was sent down to s3 in the previous step is now called p3.

4. p3 and s3 enters node n3.

Since neither of p2 or p3 is clipped they are pushed downwards together with s3. p3 and s3 goes down to node n3 and p2 and s3 is pushed down to node s4.

5. p3 and s3 enters node n3

In n2 p3 is accepted as a portal and a part of s3 is removed by the same reasons as before. s3 is now named p4.

6. p2 and p4 enters node s4

None of the polygons need clipping, both p2 and p4 are sent down to n4 together with s4. Only s4 is sent to n5.

7. p2, p4 and s4 enters node n4

Neither of p2 or p4 need clipping, except for that to fit the node. But s4 is completely coinciding with a polygon in the pillar so it is removed.

8. Nothing enters node n5.

This node will have no portals, since it is not visible from any node and cannot see any other node.

9. The result

Portal p1 is in both n1 and n2.
Portal p2 is in both n1 and n4.
Portal p3 is in both n2 and n3.
Portal p4 is in both n3 and n4.

This is everything we need for building a simple portal engine that will give a relatively good frame rate.

Our Solution

A portal engine has a very flexible structure that provides some nice features. When we started designing our system we considered doing it as a portal engine, but there are some problems with portal engines, especially all the clipping that occurs when you are drawing the scene. So we decided to do a more static solution to avoid expensive calculations during run-time. The idea is somewhat similar to a portal engine but instead of calculating what needs to be drawn during run-time it is done in the pre-rendering of the map. For each leaf in the BSP-tree a Potentially Visible Set (PVS[*]) is created. This PVS is the set of leaves that is visible from the first leaf; it is not only of use during the drawing phase. It can also be used when radiosity[*] is calculated and networking is optimized for example.

The PVS is calculated during the pre-rendering of the map. In each leaf a set of visible leaves is stored. When a scene should be drawn, first the leaf where the camera is in is drawn, and then each leaf in the PVS is drawn. This requires that you have some kind of algorithm that takes care of overdraw. As we have mentioned before, graphic cards of today has hardware accelerated Z-buffers, which is enough.

Calculating the PVS

To calculate the PVS we need to do standard ray tracing between the leaves, to see if any point in a leaf is visible from another leaf. Each leaf has to have some sample points, between which visibility can be traced. These sample points have to be as few as possible to avoid massive calculations. The problem is how to distribute them.

As with the portals in a portal engine the sample points can be distributed along the splitting planes in the tree, because only the openings between the leaves have to be checked for visibility. If a point that lies in the center of a leaf is considered visible by a ray that came from another leaf, the ray must have passed through an opening in the leaf. Look at the following for a clarifying picture.

Figure 5: Visibility between nodes

In the figure above we clearly see that for a point to be visible from another node the visibility line must pass through an opening in the node. This is very obvious since if the passed somewhere else the line would be obstructed, thus there would be no visibility between the two points. Hence distributing the sample points in the openings of the nodes is adequate. Below we have described an algorithm on how to distribute sample points in a BSP-tree. For this function we need a couple of helper function that distributes points in a node. These are:

• DISTRIBUTE-POINTS (Node): This function distributes points with a certain interval along the splitting plane of the incoming node, within the boundaries of the bounding box of the node[*]. It returns a set of points. Complexity: O(xy), where x is the width of the dividing plane in the bounding box and y is the height.
• CLEANUP-POINTS (Node, PointSet): Removes points from the point set that are either coinciding with a polygon in the node or outside the bounding box of the node. Complexity: O(np), where n is the number of polygons in the node and p is the number of points in the set.

► Function: DISTRIBUTE-SAMPLE-POINTS
* Indata:
*   Node - The current we are visiting.
*   PointSet – A set of points to distribute in the sub tree of the node.
* Outdata:
*   None
* Effect:
*   Distributes points along the splitting plane of this node. Then it
*   divides the incoming points according to the splitting plane and
*   removes the points that are coinciding with a polygon in this node
*   or is outside the bounding box of this node. The newly created
*   points will be added to both the positive and negative set. When
*   a set of points reaches a leaf node the points are the sample
*   points of this leaf.

DISTRIBUTE-SAMPLE-POINTS (Node, PointSet)
1  CLEANUP-POINTS (Node, PointSet)
2  if (IS-LEAF (Node))
3      Set the point set to be the sample points of this node
4  else
5      RightPart = NewPoints
6      NewPoints = DISTRIBUTE-POINTS (Node)
7      RightPart = NewPoints
8      LeftPart = NewPoints
9  for each point P in PointSet
10     Side = CLASSIFY-POINT (Node.Divider, P)
11     if (Side = COINCIDING)
12         RightPart = RightPart U P
13         LeftPart = LeftPart U P
14     if (Side = INFRONT)
15         RightPart = RightPart U P
16     if (Side = BEHIND)
17         LeftPart = LeftPart U P
18     DISTRIBUTE-SAMPLE-POINTS (Node.LeftChild, LeftPart)
19     DISTRIBUTE-SAMPLE-POINTS (Node.RightChild, RightPart)

Complexity Analysis

Each call to this function is of order O(np + xy) (see CLEANUP-POINTS and DISTRIBUTE-POINTS). To calculate the full complexity we can formulate the following function (we will assume that the set of points are evenly distributed in the both sets):

    T(n) = 2T(n/2) + O(np + xy)

Using Masters Theorem[3] we get that the order of complexity is Θ(np + xy).

The function is first called with the root node of the tree and an empty set as parameters. In other words, the function does the following. It starts by distributing points in the plane defined by the splitting polygon in the root node of the BSP-tree. Since a plane is an infinite shape this would generate an infinite number of sample points, so there has to be some boundaries in which the points are distributed. These boundaries are the bounding box of the root node.

After the points have been distributed all of them are sent down to both sub trees. When a set of sample points enter a node, they are divided into two sets, one set for the points on the positive side of the dividing plane in the node and one set for the points on the negative side. The points that are exactly on the plane are put in both sets. Then points are distributed along this nodes dividing plane with this nodes bounding box as boundaries. The newly distributed points are put in both sets. Now the positive set is sent down the right sub tree and the negative set is sent down the left sub tree. The process is repeated until a set of points enters a leaf. After these operations each leaf contains a set of sample points that are distributed in the openings of the node.

If we would ray trace between each node at this stage it would take quite long time. But if we knew which leaves are connected to each other it would be much easier, since this could be used to skip tracing between some leaves. It is very simple to find out which leaves that are connected to each other; just check the sample points in each leaf against each other leaf’s sample points. If two nodes share one sample point these two nodes are connected to each other, because during the distribution of the sample points through the tree every point will end in zero or two leaves. When we know which leaves are connected, the algorithm for tracing visibility can be defined. But first we need to define some helper functions.

In order to trace visibility some basic ray tracing is needed. BSP-trees is a very good structure to ray trace in, since you can discard huge parts of the world, at a very little cost. The set of functions needed for our solution is:

• POLYGON-IS-HIT (Polygon, Ray) returns whether the ray interests the polygon or not.[4]
• RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray) returns whether the ray intersects something in the sub tree of the node or not.
• INTERSECTS-SPHERE (Sphere, Ray) returns whether the ray interests the sphere or not.[5]
• CREATE-RAY (Point1, Point2) returns the ray between the two points.

RAY-INTERSECTS-SOMETHING-IN-TREE is the most interesting function of those above, since it shows some of the advantages with BSP-trees, and how BSP-trees can be used to optimize ordinary ray tracing. This is a recursive function that first is applied to the root node of the tree. The algorithm is formulated as follows:

► RAY-INTERSECTS-SOMETHING-IN-TREE
* Indata:
*   Node – The node to trace through
*   Ray – The ray to test for intersection.
* Outdata:
*   Whether the ray intersected something or not.
* Effect:
*   Checks if the ray intersects something in this node or any of this node’s sub trees.

RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray)
1  for each polygon P in Node
2      POLYGON-IS-HIT (P, Ray)
3  startSide = CLASSIFY-POINT (Ray.StartPoint, Node.Divider)
4  endSide = CLASSIFY-POINT (Node.EndPoint, Node.Divider)
   // If the ray spans the splitting plane of this node or if the ray is
   // coinciding with the plane, send it down to both children
5  if ((startSide = COINCIDING and endSide = COINCIDING) or
        startSide <> endSide and startSide <> COINCIDING and endSide <> COINCIDING)
6      if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
7          return true
8      if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
9          return true
       // If the ray is only on the positive side of the splitting plane
       // send the ray down the right child. The or in the if statement is
       // because one of the points might be coinciding with the plane.
10     if (startSide = INFRONT or endSide = INFRONT)
11         if(RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
12             return true
       // If the ray is only on the positive side of the splitting plane
       // send the ray down the right child. The or in the if statement is
       // because one of the points might be coinciding with the plane.
13     if (startSide = BEHIND or endSide = BEHIND)
14         if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
15             return true
   // There was no intersection anywhere, pass that upwards
16 return false

Complexity Analysis

Worst case is that the ray passes through exactly every node in the tree in which case it has to be tested against every single polygon. Giving us an order of O(n), where n is the number of polygons in the tree. Typically a ray will not pass through every node in the tree, thus reducing the number of polygons to check versus. The best case is if the ray is limited to only one node, in which case the order of the function will be somewhere around O(lg n), depending on the structure of the tree.

► CHECK-VISIBILITY
* Indata:
*   Node1 – The starting node
*   Node2 – The end node.
* Outdata:
*   Whether Node2 is visible from node 1 or not.
* Effect:
*   Traces between the sample points in the both leaves to see if
*   there is visibility between the two nodes.

CHECK-VISIBILITY (Node1, Node2)
1 Visible = false
2 for each sample point P1 in Node1
3     for each sample point P2 in Node2
4         Ray = CREATE-RAY (P1, P2)
5         if(not RAY-INTERSECTS-SOMETHING-IN-TREE(Node1.Tree.RootNode, Ray)
6             Visible = true
7 return Visible

Complexity Analysis

The function CHECK-VISIBILITY is computationally extremely expensive. When we trace between to leaves between which there is no visibility, a trace from every sample point in node 1 to every sample point in node 2 has to be done. In worst case each of these traces has to be checked towards every polygon in the tree, hence the function would be O(s1 s2 p), where s1 is the number of sample points in node 1, s2 is the number of sample points in node 2 and p is the number of polygons in the tree. Generally the behaviour is much better, closer to O(s1 s2 lg p) because of the reduction of polygons that are needed to check versus in the ray tracing through the tree.

► TRACE-VISIBILITY
* Indata:
*   Tree – The BSP-tree to trace visibility in.
* Outdata:
*   None
* Effect:
*   For each leaf in the tree it traces visibility to that leaf’s
*   connected nodes. Every node that is found visible is added to the
*   PVS of that node. When a visible leaf is found we have to trace
*   for visibility to the visible nodes connected nodes.

TRACE-VISIBILITY (Tree)
1 for (each leaf L in Tree)
2     for (each leaf C that is connected to L)
3         Add C to L’s PVS
4 for (each leaf L1 in Tree)
5     while (there exist a leaf L2 in L’s PVS which’s connected nodes hasn’t been checked for visibility yet)
5         for (each leaf C that is connected to L2)
6             if (C isn’t in L1’s PVS already and CHECK-VISIBILITY (L1, C))
7                 Add C to L1’s PVS
7                 Add L1 to C’s PVS

Complexity Analysis

If we would not draw usage of the optimization that the connected leaves strategy gives us we would need to trace visibility between each leaf hence O(n²), where n is the number of leaves in the tree. It is very hard to give an approximation of how much the strategy speeds up the process since it is very much dependent of how the level is constructed. In a level where each leaf is visible from every other leaf it wouldn’t optimize anything, while a level where only one or two leaves is visible from every other leaf it would optimize a great deal, almost down to O(n).

The structure that is generated now will discard large amounts of polygons each frame in a good map. A good map is built considering the visibility aspect, meaning that sight-blocking objects should be inserted, such as walls that prevent sight. If a map contains large room with enormous amounts of detail there is nothing our engine (or for that matter a portal engine) can do to remove hidden surfaces. In those bad cases there is another technique can be used to remove polygons; it is called level of detail (LOD[*]).

Static Objects

Consider a map that consists of a sphere that lies in the middle of a box. When we try to render a BSP-tree from this map we would end up with a terrible amount of nodes, and great number of splitted polygons, since each of the polygons in the sphere would end up in separate leaves. So if the sphere consists of 200 polygons, a simple scene as this would render a BSP-tree of 200 leaves. A tree with such depth (in the mentioned case the depth would be as much as 200) would be very cumbersome during run time, not to mention all the extra polygons created because of the splitting. Certainly there is a need of taking care of such cases.

To solve this problem the map designer chooses which objects are defining the geometry of the map, in the example above the box would be such an object. The rest of the objects are classified as static objects, these are objects that will not be used to render the BSP-tree or during the visibility testing, but they will cast shadows during the lightning phase of the map. Each of the static objects will be added to the BSP-tree when the visibility calculations are done. This is done by taking each polygon in a static object and pushing it down the tree. The algorithm that pushes a polygon down the tree will need further description. It looks like this:

► PUSH-POLYGON
* Indata:
*   Node – The node the polygon is currently in
*   Polygon – The polygon to push down
* Outdata:
*   None
* Effect:
*   Pushes the polygon down through the tree. If the polygon at some
*   point spans the dividing plane of a node it must be
*   clipped. The resulting parts will be pushed downwards in the tree.
*   When a polygon enters a leaf it will be added to the set of
*   polygons in that leaf.

PUSH-POLYGON (Node, Polygon)
1  if (IS-LEAF (Node))
2      Node.PolygonSet = Node.PolygonSet U Polygon
3  else
4      Value = CALCULATE-SIDE (Node.Divider, Polygon)
5      if (Value = INFRONT or Value = SPANNING)
6          PUSH-POLYGON (Node.RightChild, Polygon)
7      else if (Value = BEHIND)
8          PUSH-POLYGON (Node.LeftChild, Polygon)
9      else if (Value = SPANNING)
10         Split_Polygon (P1, Divider, Front, Back)
11         PUSH-POLYGON (Node.RightChild, Front)
12         PUSH-POLYGON (Node.LeftChild, Front)

PUSH-POLYGON is a neat recursive function that adds a polygon to the tree. The function will be called once for every polygon in every static object together with the root node of the tree to add the object to.

After this process our leaves are no longer convex sets, this will render some problems when doing collision detection, which will be described in the upcoming series Physics in BSPtrees.

Related Readings

• Hoff III, Kenneth E. Faster 3D Game Graphics by Not Drawing What Is Not Seen
• Tyberghein, Jorrit. The Portal Technique for Real-time 3D Engines
• Bikker, Jacco. Building a 3D Portal Engine
• Nuydens, Tom. 3D Engine Column, Delphi3D
• Chalfin, Alex. Cells and Portals
• Hoff, Kenny. The Warnock Area Subdivision Algorithm for Hidden Surface Removal

References

1. Hoff III, Kenneth E. Faster 3D Game Graphics by Not Drawing What Is Not Seen
2. Tyberghein, Jorrit. The Portal Technique for Real-time 3D Engines
3. Cormen, Thomas H. Leiserson, Charles E. and Rivest, Ronald L.: Introduction to Algorithms
4. Åhs, Cons T and Bevemyr, Johan. Inlämningsuppgift I Programmeringsmetodik 2
5. Silicon Graphics. BSP Tree Frequently Asked Questions (FAQ)

Glossary

PVS Potentially Visible Set; given a position this is the set of objects/polygons/nodes that are potentially visible from that location.

Portal A hole through which two nodes are connected or a mirror on which a scene can be rendered.

Frame rate The number of times the screen is updated per second. This has nothing to do with the refresh rate of the monitor. It is the number of times the world is drawn per second. Usually this should be above 30 times/sec to give a continuous feeling.

Target system The minimum system that a game should be able to run on. LOD Level of Detail, when this technique is used objects is drawn with different amount of detail depending on distance from the viewer. The reason is to reduce the polygon count in the scene. The closer an object is to the viewer the more detailed it will be.

Node A part of a tree. Each node consists of a left- and a right sub tree.

Viewing frustum The field of view for the camera. Often shaped as a pyramid with the top in the camera.

Scene A set of objects with attribute from which one can render an image from any viewing position and angle.

Bounding box Generally this is defined as the least box that encapsulates some set of objects, for example points, polygons, other bounding boxes etc. When we use the term as the bounding box of a BSP-node, we mean that this is the least box that encapsulates all polygons in the sub trees of this node.

Radiosity A lightning model commonly used in game engines. Main feature is so called color bleeding, where walls “bleed” its color to neighbor walls.