Index

Home Page

OpenGL Tutorials

Template
Cameras
Timing
Lighting
Collision Detection & Response
Culling
Dialogs, Text & FPS
Templated Linked Lists
Billboards / Sprites
Splines / Bezier Curves
Binary Space Partitioning
Lightmapping
Portals
Potentially Visible Sets
3D Sound
Decals
Particles
Video
Skybox & Lens Flare
Constructive Solid Geometry
Polygon Selection
Polygon Removal
OpenGL MDI
Basic ODE Physics

Ported Demos

Ports of some of the above examples to SDL, ClanLib and GLFW are Here

Old News

OpenGL Old News

OpenGL Links

OpenGL links for Beginners through to Advanced
Free Q2 Map Viewer
Click here to go to the Q2View program

Polygon Removal Tutorial


By Alan Baylis 27/08/2003



If you are writing a map editor using brushes and constructive solid geometry (CSG) it can be difficult to remove the exterior/outfacing polygons from the final map file during compilation, especially if you are dealing with a true polygon soup where each polygon is unconnected to any other polygon. The following tutorial discusses one possible solution to the problem by using the BSP process to organize the data. There may be other solutions or it may be simpler to use a more advanced data format that includes vertex/edge sharing or change to a B-Rep method. The diagrams used in the tutorial are 2D representations of the actual 3D process to help describe the method. I'm not much of an artist but I know from experience that any diagrams are a bonus when learning new techniques.

After you have constructed your world using the CSG method, in which convex brushes are added and subtracted from one another, you will end up with a world that contains polygons that face out from the interior of the world, these polygons become a problem if you intend to BSP the world data after it has been created. The BSP process will fail if these polygons are not removed from the final map. Figure 1 shows a very small map with a yellow interior and the normals of the polygons colored blue. The polygons we want to remove are the ones on the outside of the walls.

Figure 1.


The first step is to tag all the polygons in the map as valid, using a member of the polygon class/structure. Then find the bounding box of all the polygons in the data set, but extend this bounding box outwards so that it totally encloses all the polygons with a bit of space in-between as shown in figure 2.

Figure 2.


The next step is to create six new polygons that are coplanar with the faces of the extended bounding box and face inwards as shown in figure 3. As you create these new polygons tag them as invalid.

Figure 3.


We now have a map that we can use the BSP method on; this isn't a final compilation but a necessary step towards determining which polygons are to be removed. Once the BSP and portal creation has been done you would have something like figure 4. The leaves of the BSP (sectors) are colored blue and the portals are colored red. Each sector contains at least one portal and each portal contains a pointer or reference to the sector behind it. As you will notice, there are no portals that lead from the outer region of the map into the interior region. This is important because a hole in the original walls of the map will cause this method to fail.

Figure 4.


The idea now is to find a sector that contains an invalid polygon, marked with a number 1 in figure 5. Because it contains an invalid polygon we know that this sector is in the outer region and we can use it as a starting sector. By setting all the polygons in this sector as invalid and recursively traveling to the connecting sectors via the portals, setting all the polygons of these sectors as invalid too, you will only be setting the exterior polygons of the original map as invalid. To stop the recursive function from going into an infinite loop it is also necessary to tag any sector that has been processed as visited and not revisit those sectors again.

Figure 5.


Once the sectors have been processed you then collect all the valid polygons from the sectors into a final data file and you will have a final map that you can use the BSP method on, as shown below.

Figure 6.


Below are a collection of functions that may help you when it comes to writing your own code. You can find the full source code for this method of exterior polygon removal in the new.cpp file of the FreeWorld editor source code, the function is called RemoveOuterPolygons.

MarkAllLeavesAsUnvisited is a small function that I call after creating the BSP tree but before calling any other functions. 
void MarkAllLeavesAsUnvisited(BSP_node* node)
{
    if (node->leaf)
    {
         node->visited = false;
         return;
    }
    MarkAllLeavesAsUnvisited(node->frontnode);
    MarkAllLeavesAsUnvisited(node->backnode);
}
GetFirstLeafNode walks the BSP tree and returns the first sector that contains a invalid/suspect polygon. 
BSP_node* GetFirstLeafNode(BSP_node* node)
{
    BSP_node* tempNode;
    if (node->leaf)
    {
        for (int i = 0; i < node->polylist.size(); i++)
        {
              if (node->polylist[i].suspect)
                return node;
        }
        return NULL;
    }
     tempNode = GetFirstLeafNode(node->frontnode);
    if (!tempNode)
        tempNode = GetFirstLeafNode(node->backnode);
    return tempNode;
}
MarkOuterPolygonsAsSuspect sets the polygons of the sector passed to it as invalid/suspect and then recursively travels to any unvisited sectors that lead from it. 
void MarkOuterPolygonsAsSuspect(BSP_node* node)
{
    for (int i = 0; i < node->polylist.size(); i++)
        node->polylist[i].suspect = true;
    node->visited = true;
    for (int i = 0; i < node->portallist.size(); i++)
    {
        if (!node->portallist[i].backleaf->visited)
            MarkOuterPolygonsAsSuspect(node->portallist[i].backleaf);
    }
    return;
}
GetValidPolygons recusively walks the BSP tree and collects all valid/non-suspect polygons into a final list before returning. 
void GetValidPolygons(vector<POLYGON>& InputPolygons, BSP_node* node)
{
    if (node->leaf)
    {
        for (int i = 0; i < node->polylist.size(); i++)
            if (!node->polylist[i].suspect)
                InputPolygons.push_back(node->polylist[i]);
        return;
    }
    GetValidPolygons(InputPolygons, node->frontnode);
    GetValidPolygons(InputPolygons, node->backnode);
}
As far as I can tell, this method will work on any type of world as long as there are no holes or leaks from the interior to the exterior. It should work well for you if you are dealing with a true polygon soup and have been looking for a solution to the problem of removing outfacing polygons. This method will split the polygons during the BSP process so a more optimized method would be to give each polygon a unique number at the start and use the number of any surviving polygons to determine which of the original polygons should be kept. It would be nice to find a simpler solution though, so if you know of one then I'd like to hear it.

Above Content Copyright © 1998 - 2005 Alan Baylis, All Rights Reserved