What's the best way to organize mesh structure - for speed

I started working on a small game engine and I’m about to start coding the polygon/mesh class. Right from the beginning, I’d like to use a method that will be the fastest to display. All my objects will be loaded from dotXSI file (can output triangles, triangle strips, and polygons). All of my objects will be textured (most likely multitextured) and will have normal data per vertices…
Now, I realize that doing glBegin() send a few vertices glEnd() is not the fastest thing to do… So how do you structure your meshes? What do you send? Vertex arrays?
Finally, how do you organize your data… do you keep multiple points or points/face indices array ? Do you keep plane approximation (i.e. each trangle has a plane equation) for collision detection?
I’m very interested in how you would organize the mesh structure to allow for fast rendering and collision detection.

Kind regards,
Luke

Look into ARB_vertex_buffer_object

It’s the fastest way to send vertex data to time.

Originally posted by Zengar:
[b] Look into ARB_vertex_buffer_object

It’s the fastest way to send vertex data to time.[/b]

You mean, “It’s the fastest way to send vertex data to date.” Nit pick I know but what can I say?

-SirKnight

Use indexed arrays and sort your index accesses so that the video card vertex caches work well. I think interleaved formats are sometimes a good idea. They never hurt and sometimes help.

As far as collision detection goes: this is a pretty hard problem that has nothing to do with OpenGL. While the actual face-vertex/edge-edge collision checks need to be reasonably good, the real speed comes from having some kind of hierarchical organization that lets you perform cheap, gross culling. Also, there are some annoying corner cases to iron out. Check out www.flipcode.com for details. Look up “loose octrees” for a start.

-Won

Originally posted by SirKnight:
[b] You mean, “It’s the fastest way to send vertex data to date.” Nit pick I know but what can I say?

-SirKnight[/b]

Yeah, laught about my english. YOU can aford it

Won, what interleaved formats? I didn’t know that Opengl had inteleaved structures like the vertex strucures in DirectX, where you can specify the way the uvs/normals/points interleave in the array…?
Thank you,
Luke

glInterleavedArrays(GLenum format, GLsizei stride, void *pointer)

Format is one of…

GL_V2F
GL_T2F_C4F_N3F_V3F
(etc. - search for the definitions of the above in your headers and you’ll find the others)

Given the above names the following symbols mean the following…

V = Vertex
T = Texture
C = Colour
N = Normal
3 = 3 components
F = Float (there is also UBYTE)

So GL_V3F means your interleaved array has a 3 component Vertex in each element and each component is of type float (why you’d bother is beyond me).

As you pointed out this is not an advanced topic but I thought I’d give you a starter at least because if you don’t have the red book (go buy it) info on Interleaved arrays seems hard to come by (maybe someone knows of some links?).

[EDIT] - If you have MSVC then open MSDN and you’ll find all the info you need - so presumably it’s available on the MSDN web site…

[This message has been edited by rgpc (edited 10-30-2003).]

You don’t even need “glInterlevedArrays”. All you need to do is create interleving by using gl*Pointer commands with appropriate strides and offsets.

Korval, you got me totally lost

Vertex arrays don’t have to be contiguous: all they need is a constant stride. A stride is the distance between two members of an array.

You can interleave your arrays without using the call to glInterleavedArrays because you have control over the stride (size of the entire struct) and the offset (offset within struct).

-Won

InterleavedArrays() is an anachronism, and isn’t actually a good idea. Instead, do what Korval said:

enum {
kPos = 1, kColor = 2, kNormal = 4, kUV = 8
};
struct MyVertexPosNormUV {
float x, y, z;
float nx, ny, nz;
float u, v;
};

struct MyVertexPosColor {
float x, y, z;
uchar r, g, b, a;
};

struct MyVertexType {
virtual uint specify( char const * ) = 0;
};

struct MyVertexTypePosNormUV : public MyVertexType {
typedef MyVertexPosNormUV MyType;
uint specify( char const * base ) {
assert( sizeof( float ) == 4 );
glVertexPointer( 3, GL_FLOAT, sizeof( MyType ), base );
glNormalPointer( GL_FLOAT, sizeof( MyType ), base+12 );
glTexCoordPointer( 2, GL_FLOAT, sizeof( MyType ), base+24 );
return kPos | kNormal | kUV;
}
};

struct MyVertexTypePosColor : public MyVertexType {
typedef MyVertexPosColor MyType;
uint specify( char const * base ) {
assert( sizeof( float ) == 4 );
glVertexPointer( 3, GL_FLOAT, sizeof( MyType ), base );
glColorPointer( 4, GL_UNSIGNED_BYTE, sizeof( MyType ), base+12 );
return kPos | kColor;
}
};

void SpecifyVertexArray( char const * array, MyVertexType * type ) {
uint flags = type->specify( array );
((flags & kPos) ? glEnable : glDisable)( GL_VERTEX_ARRAY );
((flags & kColor) ? glEnable : glDisable)( GL_COLOR_ARRAY );
((flags & kNormal) ? glEnable : glDisable)( GL_NORMAL_ARRAY );
((flags & kUV) ? glEnable : glDisable)( GL_TEXTURE_COORD_ARRAY );
}

Hope the C++ doesn’t scare you. Also, with a little bit of template magic, you can make this deal with differing vertex formats quite elegantly, without having to write each vertex/type class explicitly.

It’s likely that keeping data interleaved (and using stride) will transfer faster than using separate arrays, at least compared to keeping each component in a separate array. It’s also possible that aligning your vertices on power-of-2 boundaries (16, 32, etc) may make some hardware transfer it faster, if the amount of padding isn’t obscene.

Edit: an obvious naming typo.

[This message has been edited by jwatte (edited 10-31-2003).]

Thank you so much for the help!
Is there a way to use multiple uv sets per vertex (when doing multitexturing) with those arrays?

Look into glActiveClientTexture(Was that the right name?) + the same striding-shifting mechanism. I don’t know how it would affect performance thought. <speculation> I don’t think multiply tex coord arrays are well accelerated. </speculation>

Multiple texture coordinates are well accelerated. You call glClientActiveTexture() before calling glTextureCoordPointer() and your’e done.

In the C++ code above, you’d support that by just defining bits for kUV0, kUV1, kUV2 etc, as well as structs contaning the appropriate data.

I highly recommend going either the template route, or a data-driven format description approach, in order to not have to write 168 different struct kinds, although defining 3 or 4 structs is easier to get things up and running, and worry about scaling it when you get to the 5th format

Jwatte, would you have some sample code as to how this could be done with templates?
Thank you,
Luke

One more thing Jwatte (I’m kind of beginner in game programming
With regards to your above code, just wanted to ask you a few questions:

enum {
kPos = 1, kColor = 2, kNormal = 4, kUV = 8
};

whhat is this enumeration specifying? For instance, why is kNormal 4 and kUV = 8?

glTexCoordPointer( 2, GL_FLOAT, sizeof( MyType ), base+24 );

With this part, not sure why there’s base+ 24, that is why 24?

return kPos | kNormal | kUV;

Not sure how is this part working…

Sorry about the basic questions, I’m still in school. only had 2 courses on C++

Thanks a lot for your great help.

Luke

Originally posted by BigShooter:
One more thing Jwatte (I’m kind of beginner in game programming With regards to your above code, just wanted to ask you a few questions:

IANAJW, but since he doesn’t seem to be around I’ll take a stab at this.

enum {
kPos = 1, kColor = 2, kNormal = 4, kUV = 8
};

whhat is this enumeration specifying? For instance, why is kNormal 4 and kUV = 8?

The enum defines flags that specify what kind of data is contained in the vertex array; vertex positions, colours, normals, texcoords etc. The values chosen correspond to particular bits (1 = bit0, 2 = bit1, 4 = bit3 etc), so they can be ORed together with the ‘|’ operator .

glTexCoordPointer( 2, GL_FLOAT, sizeof( MyType ), base+24 );

With this part, not sure why there’s base+ 24, that is why 24?

The +12 and +24 are offsets from the start of the interleaved data. A MyVertexTypePosNormUV contains positions, normals and texcoords. Positions come first and so start at base+0. Normals come right after that and so start at the base address plus the size of the position data; a position is 3 floats, hence 12 bytes. Similarly, texcoords come after normals and so start at the base address, plus the size of the position, plus the size of the normal. (Writing this as base+(sizeof(GLfloat)*3) etc would have been just as efficient and might make the intent clearer.)

return kPos | kNormal | kUV;

Not sure how is this part working…

This just tells the caller of specify() what kinds of data the vertex array contains, so that it (“it” being the SpecifyVertexArray function here) knows which arrays to enable. It’s necessary because SpecifyVertexArray doesn’t know exactly what it’s dealing with; it gets passed a pointer to the base class, MyVertexType. Read up on virtual functions and polymorphism if this bit is confusing you. I’d probably make the flags-accessor a separate method, but that’s just me.

HTH,
Mike

(I’ve also got some templated vertex format deduction code kicking about, but IIRC I’d been overdosing on Alexandrescu when I wrote it, and probably shouldn’t inflict it on an unsuspecting world…)

{EDIT:typo}

[This message has been edited by MikeC (edited 11-02-2003).]

Thank you MikeC, your explaination helped a lot.
Luke

What Mike said.

Btw: Contrary to popular belief, I don’t get to read these boards every day; I have some actual code to write, too

Check out d3d’s FVF (Flexible Vertex Format) mechanism. At the end of the day it is flexible, but very fiddly.