Features

A Real-Time Procedural Universe, Part Two: Rendering Planetary Bodies

Looking at the Code

I want to go over the classes I wrote for this ROAM algorithm so you can get a good idea of how they work. To keep it concise, I will only list and explain key classes, members, and methods here. This is just to explain some of the finer points of what I did to make it easier for you to go through the demo source and modify it or come up with your own implementation based on it.

CROAMVertex:
class CVertex
{
public:
static CVertexArray Array;
     CVector m_vPosition;      // The vertex position
     CVector m_vNormal;        // The vertex normal
     float m_fTexCoord[4];      // 2 sets of texture coordinates
};

The CVertex class doesn't have any ROAM-specific members or methods in it, it's just a regular vertex with space for 2 sets of texture coordinates for multi-texturing. Note the static CVertexArray object, which is currently used as a global OpenGL vertex array shared by all ROAM instances. This needs to be global because I'm only allocating room for 65536 vertices in video memory (NVidia-specific), and I need to make sure one ROAM object doesn't step on another. If necessary I could make a second global array, perhaps to share non-ROAM vertices, and it would allocate its own block of video memory and work in a similar fashion.

CVertexArray

#define VERTEX_ARRAY_SIZE 65535
class CVertexArray
{
protected:
     // Members for the vertex array
     unsigned short m_nStackPosition;   // Index into the stack
     unsigned short *m_pStack;               // A stack of free elements
     unsigned char *m_pUpdated;           // An array of updated flags
     CVertex *m_pBuffer;                           // Contains the actual vertices

     // Members for GL_NV_vertex_array_range and GL_NV_fence extensions
     bool m_bFence;                         // true if extensions are enabled
     CVertex *m_pArray;                 // pointer to allocated video memory
     GLuint m_nFence;                    // utilize fence synchronization

     // Members for GL_ARB_multitexture extension
     int m_nMaxTextureUnits;        // Is multi-texturing allowed?

public:
     // Init and Cleanup methods
     void Init();                      // Initializes extensions, allocates video memory
     void Cleanup();             // Frees video memory

     unsigned short GetElement();                               // Call to get a new array index
     void UpdateElement(unsigned short);                // Call after updating a vertex
     void ReleaseElement(unsigned short);                // Call to release a vertex

     // OpenGL vertex array methods
     void InitRender();                     // Call before rendering each frame
     void FinishRender();                // Call after rendering each frame
     int GetMaxTextureUnits();
     void EnableVertexArray();
     void DisableVertexArray();
     void EnableNormalArray();
     void DisableNormalArray();
     void EnableTextureCoordArray(int, int);
     void DisableTextureCoordArray(int);
};

The CVertexArray class implements the OpenGL vertex array I use for my ROAM algorithm. To properly encapsulate an OpenGL vertex array, it must handle the GL_NV_vertex_array_range and GL_NV_fence extensions, and it must contain wrappers to call functions like glVertexPointer(), glNormalPointer(), and glTexCoordPointer(). As you can see here, it keeps a stack of free array indexes into the vertex array. When the ROAM split function needs to add a new vertex to its mesh, it calls GetElement() to get a new index into the array. When the ROAM merge function needs to remove a vertex from its mesh, it calls ReleaseElement() to put that index back on the free stack.

CROAMTriangle

class CROAMTriangle : public CListNode<CROAMTriangle>
{
public:
     // Triangle members
     unsigned short m_nVertex[3];                // Indices into CVertex::Array
     CROAMTriangle *m_pEdge[3];            // Pointers to edge neighbors
     CROAMTriangle *m_pParent;              // Pointer to the parent triangle
     CROAMDiamond *m_pDiamond;        // Set if this triangle is in a diamond

     // Split priority members
     CVector m_vMidpoint;           // The midpoint of the longest edge
     float m_fOffset;                        // The offset in height
     float m_fLength;                      // The length of the longest edge
     unsigned char m_nFlags;

     float GetPriority(CVector &vPosition, CVector &vHeading, float fHorizon);
     void Draw(GLenum nMode, unsigned short *nArray, unsigned short &nIndex);
};

This class requires a little more explanation. As I mentioned above, my ROAM implementation uses a linked list of triangles instead of a binary tree. The list is initialized with the 12 top-level triangles, each with its parent pointer set to NULL. When a square is split I create two new triangles and set their parent pointers to the two existing triangles in the square, then I rearrange the vertices and edges of all four triangles. This means that the true parent triangle doesn't really exist in the list anymore. But as long as I have a pointer linking a triangle with the triangle it was split from, rebuilding the parent is easy when it needs to be merged.

Every time I create a new triangle during a split operation, I cache the midpoint and length of its longest edge (the edge to be split). I also cache the offset from that midpoint to the vertex's correct location (i.e. the error). If the new triangle is completing a square, then the values are copied from its neighbor. Otherwise, the values are calculated. All three values are used in the priority calculation, which also takes into account the camera position and heading and the distance to the horizon.

Initially the GetPriority() method returned 0 if the distance to the vertex was greater than the horizon or it was out of the current angle of view, but this caused problems. Essentially, if you turned the camera away from a planet while close to it, all polygons would be merged and the sphere would be turned into a cube. When you turned the camera back to face the planet, the cube would not always be split because the vertices checked were so far away from the camera that they were either beyond the horizon or outside the angle of view. So now a priority is always calculated if the camera is closer to the vertex than the length of the edge to be split.

The Draw() method simply fills in an array of indices for a future call to glDrawElements(). I've toyed with adding a check to skip drawing triangles that aren't in the current view, but I've got that commented out right now so I can turn off updates from a specific viewpoint, then fly around the planet in wire-frame mode to see how well the mesh is optimized. You may get a small improvement in performance by un-commenting the lines dealing with the TriangleDrawMask flag.

CROAMDiamond

class CROAMDiamond : public CListNode<CROAMDiamond>
{
public:
     // Triangles that make up the diamond
     CROAMTriangle *m_pParent[2];
     CROAMTriangle *m_pChild[2];

     // Merge priority members
     CVector m_vMidpoint;       // The midpoint of the longest edge
     float m_fOffset;                    // The offset in height
     float m_fLength;                  // The length of the longest edge
     unsigned char m_nFlags;

     float GetPriority(CVector &vPosition, CVector &vHeading, float fHorizon);
};

This class is a good bit simpler than CROAMTriangle, but it is just as important. A diamond is made up of four triangles. Because two of them are always parents of the other two, the parent and child pointers are kept separately to make the merge routine simpler. Note how the priority members stored in CROAMTriangle are duplicated in this class. These values are what would've been cached in the original parent triangle that gets destroyed during a split. Caching them in CROAMDiamond allows us to calculate a merge priority that matches the parent's split priority exactly.

Note that the diamonds are in a linked list, each contains a pointer to its 4 triangles, and a triangle contains a pointer to the diamond its currently in. This is pretty redundant, but it is necessary to get good performance. When splitting a triangle, you need to be able to find and destroy the diamond it's in (if any) very quickly. I used to scan the list of diamonds, thinking that the list would stay rather small, but this killed my performance when a lot of splits needed to be done each frame.

CROAMSphere

class CROAMSphere : public C3DObject
{
protected:
     CROAMTriangleList m_llTriangle;           // List of triangles in the mesh
     CROAMDiamondList m_llDiamond;        // List of diamonds in the mesh
     CROAMAlgorithm *m_pAlgorithm;        // A planet algorithm
     int m_nTriangles;                                        // The current triangle count

     void Init(CROAMAlgorithm *pAlgorithm);
     bool CollisionCheck(C3DBase *pCamera);
     void Split(CROAMTriangle *pTriangle);
     void Merge(CROAMDiamond *pDiamond);
     bool Update(C3DBase *pCamera, float fMaxError);
     void Draw(C3DBase *pCamera, bool bTexture=true);
};
We finally get to the main ROAM class. The key member variables should be about what you expected at this point: a triangle list, a diamond list, and an algorithm object for retrieving the height and texture coordinates of new vertices. The Init() method takes an initialized algorithm object, and builds the 12 top-level triangles of the cube. The CollisionCheck() method calls the fractal function to determine whether the camera's position is inside the planet or not. This is a faster and more accurate way to do collision detection than to check against the current mesh.

The Split() method looks messy right now and could probably be cleaned up a bit, but it is fairly easy to explain with some pseudo-code:

void CROAMSphere::Split(CROAMTriangle *pTriangle)
{

if(pTriangle->neighbor does not make a square with pTriangle)
     Split(pTriangle->neighbor)
pOpposite = pTriangle->neighbor

pVertex = CVertex::Array.GetNewElement()
Initialize pVertex's position, normal, and texture coordinates

Create a new triangle and add it to the triangle list
Split pTriangle into the new triangle
Create a new triangle and add it to the triangle list
Split pOpposite into the new triangle

Update the pVertex's normal based on the new triangles

if(pTriangle was part of a diamond)
      delete pTriangle->m_pDiamond;
if(pOpposite was part of a diamond)
      delete pOpposite->m_pDiamond;
Add the new diamond created by the new split

Final Notes

Now that you've seen how to generate and render a full-size planet at real-time speed with dynamic level of detail, I encourage you to play around with the source code and see what you can come up with. It should run pretty well on most systems with OpenGL-accelerated drivers, and it should fly on NVidia GeForce cards. Because it only generates and uses memory for vertices the camera is close to, it should be fairly easy to expand this demo to generate and render an entire solar system, or an entire galaxy of star systems, without a significant impact on memory or the CPU. The next article in the series will focus on doing that and will explain how to fix some of the problems you will run into working with such a large game world.

Discuss this article in Gamasutra's discussion forum.

______________________________________________________

[Back to] Introduction

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service