Advanced Management Of Polygonal Data
by (16 April 1999)
|Return to The Archives|
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.
|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.|
A polygon class might look like this:|
The vertex class:
And finally, the coordinate class:
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
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:
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:
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:
Now a polygon can be used as a linked list by itself. The data fields in the memory management class must be changed also:
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:
And for freeing the instance:
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:
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:
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:|
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 (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, 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...
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"