I've run Doom 3 through GL Intercept and every single draw call in it is glDrawElements - it's index buffers all the way. Admittedly it is an old game, but it should suffice as one possible real world example.

It might be the case that the model you used was already heavily optimized and as such would not benefit. It might also be the case that you may need to double-check your vertex elimination code ( ;) ), but either way there are plenty of other cases where index buffers are needed and/or useful. Even at quite a mundane level - take the classic example of a particle system; assuming that we're on D3D (or an OpenGL core context) and that we don't want to use point sprites or a geometry shader, an index buffer is the best way of grouping multiple particles into a single draw call. That's just one example; a less contrived one may be GUI elements.

I just spent a good 10 minutes waiting for my engine's new OBJ model loader ... the time was spent trying to go through every listing in the "faces" section of the file looking for duplicates, and substituting that vertex with an index in the index buffer where appropriate

Don't do this at run-time. The model file is static -- you make it once and ship it to the user -- so don't make the user run an optimization algorithm over that data each time they load the game. Instead, you should run that algorithm once when you're creating the data.

i.e. don't distribute OBJ files with your game. Export to OBJ from your art program, and then convert these OBJ files into an engine-specific format.

Just to be sure I am reading your post right.
You start with X vertices and you end with the same number of indices?
[font="arial, verdana, tahoma, sans-serif"]

there isn't a single damn difference between the "raw" vertex count in the OBJ and the produced index buffer's size after compilation.

[/font][font="arial, verdana, tahoma, sans-serif"]There should’t be. Assuming triangle lists, you should end up with around half the number of vertices[/font][font="arial, verdana, tahoma, sans-serif"], and the same number of indices as there originally was vertices.[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]Also, even though you plan to move this conversion offline, you can speed up the process by using a map to store scanned vertices. That is, for each vertex you check, you should be able to perform a binary search for its duplicate, if any. By your time, I can guess you are just searching from the start of the list every time.[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]Also, since the map will be resized frequently, you actually don’t want to copy the vertices into it. Instead, keep a vector of the copied vertices that only accept vertices at its end, and use the map to sort indices[/font][font="arial, verdana, tahoma, sans-serif"] into that vector. This way the map only contains integers that are fairly trivial to move around as objects are inserted into the map.[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]When you have done this process correctly, you should see a heavy gain in performance over using vertex buffers alone. Remember to chop the unused vertices off the end of the vertex buffer.[/font][font="arial, verdana, tahoma, sans-serif"] [/font]


[font="arial, verdana, tahoma, sans-serif"] [/font][font="arial, verdana, tahoma, sans-serif"] [/font][font="arial, verdana, tahoma, sans-serif"]L. Spiro[/font]

The way I have done it is to unpack the vertices into a vertex buffer in triangle-list format. The vertex buffer could be used in this form to render, but of course we want to eliminate duplicates so I add an index buffer.
I believe you also reach this point.


From here I want to search for duplicates but of course I want the search to be binary, so I suggested a map above.
The naive way to implement this would be to store a copy of each vertex in the map itself (vertex = key, value = that vertex’s index in the no-duplicate list). This is naive because the map will constantly be shuffling data around, and the larger the keys the more memory it has to copy/move.


In order to minimize the amount of data needed to move each time the map has a value inserted into it, we want to use references to vertices, rather than vertices themselves, for the keys.

My structure looks like this:

/**
* A unique element in a vertex buffer.
*/
typedef struct LSG_UNIQUE_VB_ELEMENT {
/**
* Pointer to the element.
*/
LSVOID * pvElement;

/**
* Size of the element.
*/
LSUINT32 ui32Size;


// == Operators.
/**
* Less-than operator.
*
* \param _uveOther The object against which to check for being less than.
* \return Returns true if this element is less than the given element.
*/
LSBOOL LSE_CALL operator < ( const LSG_UNIQUE_VB_ELEMENT &_uveOther ) const;

/**
* Equality check.
*
* \param _uveOther The object against which to check for being equal to.
* \return Returns true if this element is equal to the given element.
*/
LSBOOL LSE_CALL operator == ( const LSG_UNIQUE_VB_ELEMENT &_uveOther ) const;
} * LPLSG_UNIQUE_VB_ELEMENT, * const LPCLSG_UNIQUE_VB_ELEMENT;

A simple memcmp() is all that is needed to check if a key is less than or equal to another key.


Notice that I have a pointer to the vertex rather than the vertex itself. This acts as a smaller key and sorts much faster.

Now as you add vertices to your no-duplicates buffer, you can store a pointer to the vertex within that buffer (assuming the buffer has been pre-allocated so that the data within it never moves) as the key and the index of the vertex as the value.

Your original vertex buffer and your no-duplicate vertex buffer can be the same thing.


L. Spiro