Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
101 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Vertex Structures and Lists

Before going on, we need to make some structural decisions. If you look at the description for d3dVertex3f again, you'll notice that it adds a vertex to the vertex list. Before we can decide how to create a vertex list, we need to determine what exactly a vertex is. We'll use a standard D3D vertex structure, since there is actually no other way to do it. Looking back at the function calls, we see that our vertex structure must support a position, normals, diffuse color, and texture coordinates. That gives us the following structure:

struct ListVertex
{
  float x, y, z;
  float nx, ny, nz;
  D3DCOLOR Diffuse;
  float tu, tv;
}

And its corresponding FVF definition:

#define FVF_LISTVERTEX   D3DFVF_XYZ | D3DFVF_NORMAL | D3DFVF_DIFFUSE | D3DFVF_TEX0

Now that we've got our vertex structure, we can decide how to make a list for it. There are two major ways to structure the list: as an array or as a singly linked non-cyclic list.

The Array Method

Remember that we don't know how many vertices we're going to get ahead of time. This means that our array will have to be dynamic, and will also have to be resized occasionally. We get the following performance from the array:

          Adding a vertex to the list:
Resizing the list
Copying the list to a vertex buffer:  
O(1)
O(n)
O(1)

I've assumed memcpy() to be O(1) for the above times (don't worry if you don't understand these notations; it's an analysis of the time required for the operations). I can assume this because on modern systems, moving data around really doesn't take too much time. I'm guessing that at most, this code will need to shift ~1MB of data. Resizing the list involves creating a larger memory space, copying the old data to the new list, and changing the array pointer to the new memory location. That will have to be done approximately every few thousand vertices. Copying the list involves a single memcpy(), since the vertices are all in a contiguous memory block. Adding a vertex (assuming there is still space in the array) simply involves changing the data for the vertex involved. The main drawback here is that depending on how much the array is expanded at each resize, we could waste quite a lot of memory.

The Linked List Method

The advantage to the linked list is that we do not need to resize the list at any point. It's not difficult to implement, and not too hard to traverse.

          Adding a vertex to the list:
Resizing the list:
Copying the list to a vertex buffer:  
O(1)
O(0) (no time required because we never resize)
O(n)

The serious drawback here is that moving the vertices into the buffer is O(n), not O(1)! Because we cannot guarantee that any vertices are next to each other in memory, we have to memcpy() the vertices one at a time, not all at once. This is a serious performance hit!

We'll use the array method.

The O(n) time for copying the linked list is too high, and array resizing does not take so much time that it justifies using the linked list(the time for the array resize is O(n/ExpandAmount), whereas the linked list copy time is just O(n) ). A single static pointer represents our list:

static ListVertex *pVertList = NULL;

At this point we need to make a decision about the size to start the list at and how much to expand it at each resize. We could hard code it in, but that wouldn't be good coding practice. Instead, we'll put a #define statement in the header. Also, we'll encase it in an #ifndef...#endif block. This way, you can define it as something else before you include the header and easily change the value. To simplify things, there will be just one #define which will be used both as the start array size and as the amount to expand at each time:

#ifndef MIN_VERTEX_LIST_SIZE
#define MIN_VERTEX_LIST_SIZE 2048
#endif

We'll access this define during d3dBegin() and d3dVertex3f().

The Static Variables

We've already seen one variable: the vertex list. If you go back through the function descriptions, you'll notice that I mention several other variables, but that I have not actually specified what they are. I'll do that here:

static IDirect3DDevice8 *pD3DDevice = NULL;
A pointer to the Direct3D device. We'll hold this between the d3dBegin() and d3dEnd calls, and access it during d3dEnd().

static BOOL bRenderBegun = FALSE;
We need to make sure that we have begun before d3dVertex3f() or d3dEnd() is called. This variable will become true at d3dBegin() and false at d3dEnd().

static float CurNX = 0.0, CurNY = 0.0, CurNZ = 0.0;
The normals need to be held in-between calls to d3dVertex3f(). In addition, we need to be able to set the normal before d3dBegin is called (not so common with normals and texture coordinates, but OpenGL coders do it frequently with glColor*).

static D3DCOLOR CurDiffuse = 0xff000000;
As with the normals, we need to hold on to the diffuse color. We'll put the color in this variable in between calls. Also notice that while the default color is black, we still set the alpha channel to 0xff so that we draw opaque polygons.

static float CurTU = 0.0, CurTV = 0.0;
And of course, we need to keep the current texture coordinates.

static ListVertex *pVertList = NULL;
Like I've explained before, this is a pointer to a dynamic array of vertices.

static long MaxArraySize;
This holds the current maximum size of the array. We'll check NumVerts against this at every call to d3dVertex3f() to make sure that there is enough array space. If not, we'll expand the array.

static long NumVerts = 0;
This holds how many vertices have actually been created by calls to d3dVertex3f(). It's also the logical size of the array, and the index of the next vertex to be added.

static D3DPRIMITIVETYPE PrimitiveType;
When it comes time to actually draw the vertices, we will need to know what kind of primitives to draw. Since this is passed in as a parameter to d3dBegin() but not used until d3dEnd(), we need to keep track of its value.



Page 3

Contents
  Page 1
  Page 2
  Page 3

  Source code
  Printable version
  Discuss this article