PDA

View Full Version : What's the best way to organize mesh structure - for speed



BigShooter
10-30-2003, 12:19 AM
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

Zengar
10-30-2003, 06:36 AM
Look into ARB_vertex_buffer_object

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

SirKnight
10-30-2003, 09:26 AM
Originally posted by Zengar:
Look into ARB_vertex_buffer_object

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

You mean, "It's the fastest way to send vertex data to date." Nit pick I know but what can I say? http://www.opengl.org/discussion_boards/ubb/biggrin.gif


-SirKnight

Won
10-30-2003, 12:53 PM
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 (http://www.flipcode.com) for details. Look up "loose octrees" for a start.

-Won

Zengar
10-30-2003, 04:49 PM
Originally posted by SirKnight:
You mean, "It's the fastest way to send vertex data to date." Nit pick I know but what can I say? http://www.opengl.org/discussion_boards/ubb/biggrin.gif


-SirKnight

http://www.opengl.org/discussion_boards/ubb/tongue.gif Yeah, laught about my english. YOU can aford it http://www.opengl.org/discussion_boards/ubb/biggrin.gif

BigShooter
10-30-2003, 08:11 PM
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

rgpc
10-30-2003, 10:46 PM
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).]

Korval
10-31-2003, 12:23 AM
You don't even need "glInterlevedArrays". All you need to do is create interleving by using gl*Pointer commands with appropriate strides and offsets.

BigShooter
10-31-2003, 01:00 AM
Korval, you got me totally lost :-)

Won
10-31-2003, 09:20 AM
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

jwatte
10-31-2003, 11:17 AM
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).]

BigShooter
10-31-2003, 11:41 AM
Thank you so much for the help!
Is there a way to use multiple uv sets per vertex (when doing multitexturing) with those arrays?

Zengar
10-31-2003, 04:20 PM
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>

jwatte
11-01-2003, 08:59 AM
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 :-)

BigShooter
11-01-2003, 05:32 PM
Jwatte, would you have some sample code as to how this could be done with templates?
Thank you,
Luke

BigShooter
11-01-2003, 05:38 PM
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

MikeC
11-02-2003, 01:20 PM
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).]

BigShooter
11-02-2003, 07:51 PM
Thank you MikeC, your explaination helped a lot.
Luke

jwatte
11-03-2003, 08:45 PM
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 :-)

knackered
11-04-2003, 05:51 AM
Check out d3d's FVF (Flexible Vertex Format) mechanism. At the end of the day it is flexible, but very fiddly.

DJSnow
11-07-2003, 05:43 PM
@jwatte:
yes, your approach looks very nice designed; but i think it's a little bit to complicated. i use a different approach:
i have a "mappinglevel" for a mesh, this mappinglevels knows everything about rendering the mesh it belongs to with the optical desires, this means whether or not uv/color/normal; the mappinglevel is created by the developer with a function in the mesh, to pass the correct amount of vertices to the mappinglevel - i use indexed arrays (with glDrawElements). if you wnat to use colors, tell it to the mesh/mappinglevel (both provides mechanism to add this afterwards); then the array will be created, you can obtain a pointer and fill it - a flag indicates if colors/normals/uv's are used: so i have only to disable/enable the desired glPointer...(). i have a "linear" pointer to all vertexattribs, meaning a seperate array for each attribtype - and if you now decide to use multitexture, just tell it again to the mappinglevel, then the array's size will be increased, by (numberofverts*2)*numofaddedlevels; this will result in a array one/two/tree/... times as big as the vertexarray itself. now i do glTexCoordPointer(...., pUVCoords + (indexofmappinglevel*numberofvertices) ) to get the correct entry into the list.
this solutions results in a less complex construction; you don't have to write your templates, it's clear/transparent and yo don't have to bother with all your funny strides values...

ADD-ON: and of course, the mappinglevel knows of it's used textures/shaders and such stuff.

[This message has been edited by DJSnow (edited 11-07-2003).]

jwatte
11-07-2003, 06:06 PM
If that works well for you, then by all means keep doing it. I was just describing how we do it (actually, a simplified version, but isn't that always the case :-)

Regarding linear (separate) arrays, that's very nice from a geometry management point of view, and in fact our on-disk geometry formats work like that, but there's lots of hardware that works much faster with interleaved arrays.

If you're working alone, or in a very small team, the trick is to do only what needs to be done, and know when what you have is "good enough". You can always go back and improve it later. After all, for most "fancy" or "future-proof" code, YAGNI. (You Aint Gonna Need It)