flipcode - Advanced Management Of Polygonal Data

Advanced Management Of Polygonal Data
by (16 April 1999)

Introduction

When I was developing my Focus rendering engine, I encountered numerous problems with the management of the polygons in the scene. A simple rendering engine doesn't have many problems with this; simple structures suffice and will rarely cause problems. But Focus had a dynamic illumination system, and frustum culling, amongst other things, and these algorithms require temporary polygons that sometimes last a single frame, sometimes longer. A polygon that is clipped to the frustum for example shouldn't affect the original polygon, and, once it is drawn, it can be released again. A polygon that represents a lit portion of an original scene polygon could last more than a single frame: If a light source is stationary, it's a waste of time to recalculate it every frame. Managing these polygons is complicated by the fact that temporary polygons may share vertices with non-temporary polygons. Theoretically, this is not neccessary: Whenever a clipped polygon is generated, it could just copy the vertices of the original polygon. This is however not optimal, and should thus be avoided.

Finally, multiple vertices may have the same position in 3D. This happens for example when the sides of a cube have different textures: While the cube can be represented by eight 3D coordinates, it requires much more vertices, as vertices also contain U/V information.

The Goal

In this document I describe the structures needed to maintain a set of polygons for a rendering engine in a flexible way. With these stuctures, polygons can be allocated and freed efficiently, and the application that uses them doesn't need to keep track of shared vertices and coordinates. The custom memory manager that is used for this also keeps track of vertices that are shared by multiple polygons and frees them automatically when they are not used anymore.

Initial Structures

A polygon class might look like this:


 class Polygon
 {
 private:
    Vertex* m_vertex[3];
 };

The vertex class:


 class Vertex
 {
 private:
    float m_U, m_V;
    Coordinate* m_coord;
 };

And finally, the coordinate class:


 class Coordinate
 {
 private:
    Vector3D m_original;
    Vector3D m_rotated;
    Vector2D m_screen;
    int m_processed;
 };

With these classes triangles can be stored. The triangles can share vertices, and the vertices can share coordinates. The vertex class can easily be extended to hold more data, for example information about a bumpmap, or a detail texture. The coordinate class contains the original coordinate, a rotated coordinate (transformed by a matrix, for example the camera matrix), 2D screen coordinates, and finally a flag to indicate whether this coordinate has been transformed in the current frame. The m_processed field is not a boolean: That would require to set it to 'false' once the frame is completed. Instead, I store a number here, for example the number of frames drawn since the application started. As this number increases, it can be used to determine whether the coordinate needs to be transformed.

More Flexible Polygons

Of course, we want to store more complex polygons. Most accelerators only display triangles, but it is best to postpone triangulation until the polygon is about to be rasterized: This keeps the number of polygons in the rendering pipeline low. Besides, every 3D API is capable of performing this triangulation.

The polygon class can easily be extended to hold more vertices. One way is to store a linked list of vertices in the polygon class. This would however require an extra pointer for each vertex in the polygon. A better way is to use an array of vertex pointers. The data in the polygon class thus becomes:


 class Polygon
 {
 private:
    int m_vertices;
    Vertex** m_vertex;
 };

Now, we can reserve some room for vertices in the constructor of the class. Note that we now have a potential problem: When a polygon is instantiated, we first allocate memory for the polygon, then for the vertex array, then for each vertex, and finally for the coordinates in the vertices. If the coordinates and vertices already existed, we still need two allocations of a very small amount of memory for each new polygon. At runtime, this is a lot of calls to the operator 'new'. Therefore, Focus did it's own memory management.

Custom Memory Management

The custom memory manager maintains a list of allocated polygons, vertices and coordinates, which is initially empty. Whenever a polygon record is released, it is appended to the list of unused records, so that it can be reused without allocating memory when another temporary polygon is needed. The same is done with vertices and coordinates. The problem is that the vertex pointer array doesn't have a fixed size: It's 12 bytes for a triangle, and 20 bytes for a 5-sided polygon. I'll talk more about that later.

Let's have a look at some code for maintaining a list of unused polygons. I use the following structures:


 class PolygonList
 {
 private:
    Polygon* m_item;
    PolygonList* m_next;
 };

 class VertexList
 {
 private:
    Polygon* m_item;
    PolygonList* m_next;
 };

 class CoordList
 {
 private:
    Coordinate* m_item;
    CoordList* m_next;
 };

 class MManager
 {
 public:
    MManager () { m_plist=0; m_vlist=0; m_clist=0; }
    newPoly ();
    freePoly ();
    newVertex ();
    freeVertex ();
    newCoordinate ();
    freeCoordinate ();
 private:
    PolygonList* m_plist;
    VertexList* m_vlist;
    CoordList* m_clist;
 };

The lists start empty. When a new polygon is requested, there are two possible cases: If the list of unused polygon records is not empty, the first unused polygon is returned. Otherwise, a new polygon is instantiated, and returned. The same happens when a vertex or a coordinate is requested.

I have just introduced a new problem. Polygons are stored in an instance of the class PolygonList. When a polygon is added to the list, a new instance of PolygonList is created. When a polygon is retrieved from the list, this instance is not needed anymore. Of course, we could also manage a list of unused PolygonList instances, but that would require a PolygonListList, and so on, unless we think of something better.

There is something better: The information in an unused Polygon instance is irrelevant. It can be filled with random information, as long as it is unused. This means that we don't need a PolygonList class, at least not for the memory manager. Instead, we can alter the Polygon class a bit:


 class Polygon
 {
 private:
    int m_vertices;
    union
    {  Vertex** m_vertex;
       Polygon* next;
    }
 };

Now a polygon can be used as a linked list by itself. The data fields in the memory management class must be changed also:


   Polygon* m_plist;
   Vertex* m_vlist;
   Coordinate* m_clist;

Note that I assume that the vertex and coordinate classes now also contain a 'next' pointer.

Here is the code to allocate a Polygon instance:


 Polygon* MManager::newPoly ()
 {  if (!m_plist) return new Polygon ();
    Polygon* retVal=m_plist;
    m_plist=m_plist->next ();
    return retVal;
 }

And for freeing the instance:


 void MManager::freePoly (Polygon* p)
 {  p->next (m_plist);
    m_plist=p;
 }

Now polygons, vertices and coordinates can be allocated and freed very efficiently. Maybe a good C++ compiler can do it just as good as this, but I doubt it: The newPoly and freePoly methods can now be highly efficient because they know things that a C++ compiler can't know: The size of the classes that are freed and allocated. Besides, we now know for sure that the code is optimal.

Vertices Used By Multiple Polygons

There's one problem left now: Vertices that are used by multiple polygons, and coordinates that are used by multiple vertices. This may not seem to be a huge problem, but it is: When a polygon is freed, it's hard to determine whether it's vertices can be freed also. Likewise, when a vertex is freed, it's hard to determine whether it's coordinates can be released safely also. In Focus, this means that I have to maintain a list of temporary vertices, so that I can free them up once the frame is drawn. This is not such a big problem for polygons that are clipped against the frustum, but it's much more of a problem for polygons that last more than a single frame. In that case, the list of temporary vertices must be maintained for example in the light source class, and even then it's rather tricky. In the case of Focus, this means that I spend lots of time developing clever ways to free up all unused instances of vertices and coordinates, and often I forget something or free up something that is still being used. Both types of bug are hard to track down, since the instances still live, in the memory manager. There is a way to work around this in a way that is transparent to the application, however, and that is the main reason for writing this document.

Have a look at this Vertex class:


 class Vertex
 {
 private:
    float m_U, m_V;
    Coordinate* m_coord;
    int m_instances;
 };

Note that I have added another field: The m_instances counter. This field is used to keep track of the number of polygons that still use this vertex. Which polygons use this vertex is not important, just the fact that it is still being used is. When a polygon is freed, we thus decrease the instance counter for it's vertices. Whenever a vertex is known to be unused, it can be freed safely.

The same can be applied to the Coordinate class:

 
 class Coordinate
 {
 private:
    Vector3D m_original;
    Vector3D m_rotated;
    Vector2D m_screen;
    int m_processed;
    int m_instances;
 };

And it might even be useful to add an instance counter to the polygon class.

Note that a polygon with four vertices now takes 32 bytes of memory more than the original version, but only if it's vertices and coordinates are not shared by any other polygon. In practice, each coordinate is shared by at least three polygons, so the extra space goes down to 20 bytes. Vertices are often unique. Twenty bytes may not seem too much, but it is quite a lot: If you have a set of 500.000 polygons, you have just increased memory usage by 10Mb.

Managing The Vertex Pointer Arrays

I promised to deal with one more thing: The variable sized vertex pointer arrays. I have no idea what the best way would be to cope with this, but this is what I intend to do: Usually, a polygon consists of 3-6 vertices, even after clipping. In a portal engine, this might be more, but no polygon will get more complex than about 20 vertices. Using this information, we could solve the problem like this: For each possible size of the vertex pointer array, we use a separate list. Thus, the memory management class is extended with the following data fields:


void* m_array[17]

This requires some tricky code, of course. When we free a vertex pointer array for three vertices (12 bytes), we store this bit of memory in m_array[0] (since three vertices is the minimum). The first pointer in this piece of memory is considered to be the 'next' pointer. Likewise, arrays of four vertices are appended to the list that is stored in m_array[1], and so on. To ensure correct behaviour for really odd polygons (with more than 20 vertices), those polygons are freed and allocated using the standard 'new' and 'delete' operators. If this happens too often, we can extend the array. I know this is a hack, and I would appreciate it if someone knows a better solution...

Conclusion

Data management for a 3D scene is now considerably simpler, meaning that coding a rendering engine doesn't require the extensive tracking of loose ends any more. The memory manager is highly reusable, although this might require some minor changes to the polygon/vertex/coordinate classes. These modifications shouldn't affect the memory manager itself, though. The memory manager can easily be extended to handle s-buffer spans, sprites, 3D objects and so on.

Written by Jacco Bikker, a.k.a. "THE PHANTOM"