Sign in to follow this  
Alkhimey

Data structure for storing polygons

Recommended Posts

Hi,

What data structures are commonly used to store polygon data? I am looking for data structure that will allow me maximize performance of drawing the whole object.
Is there a better structure than a simple array of polygons?
I have looked at polygon mesh article in Wikipedia, those structures do reduce number of total data stored, and thus increasing performance. Still, they do not seem to be cache friendly.
Any ideas?

Share this post


Link to post
Share on other sites
First question would have to be, which graphics platform do you plan on developing for? OpenGL? DirectX? Mobile game, Console, or PC? in most cases it wont really matter how you store them unless you try sticking them in an std::vector or something O_O lol

Share this post


Link to post
Share on other sites
I use OpenGL on a PC.
Why do you say it does not matter? What if I have a lot of polygons, and I need drawing to be smooth in real time?

Actually, my first attempt was with std::list :(. I never thought that iterating over the polygons can be a performance bottleneck. Until I saw the result.

Share this post


Link to post
Share on other sites
How did you get a std::list into the gfx card? The only thing you can feed it with are arrays (or possibly vertex textures).

If possible, reduce the index size to 16 bit and try to keep the vertex size small.
There used to be some alignment rules, but I don't know if they still apply.
For static geometry remember to flag the VBO accordingly (GL_STATIC_DRAW).

The triangle order can be optimized to be more cache friendly and you can generate a triangle strip with degenerate triangles to reduce the vertex processing load, but that assumes that vertices are actually your bottleneck.

Share this post


Link to post
Share on other sites
Quote:


How did you get a std::list into the gfx card? The only thing you can feed it with are arrays (or possibly vertex textures).

If possible, reduce the index size to 16 bit and try to keep the vertex size small.
There used to be some alignment rules, but I don't know if they still apply.




I didn't know you could feed OpenGL with arrays. Can you explain more about this?

What I did before is to store a list of polygons. When I want to draw the object, I iterate over each polygon and draw it using glBegin, glVertex, glEnd.

Share this post


Link to post
Share on other sites
Quote:
What I did before is to store a list of polygons. When I want to draw the object, I iterate over each polygon and draw it using glBegin, glVertex, glEnd.
Immediate mode with std::list is probably just about the slowest possible way to render anything :) (Well, that might be an exaggeration, but it's pretty inefficient.)

For OpenGL, look into vertex arrays and VBOs. You can store your data using std::vector, and then take the address of the first element in the vector to access the data in raw form (which will be needed in order to pass it to OpenGL).

Share this post


Link to post
Share on other sites
Quote:
Original post by Alkhimey
When I want to draw the object, I iterate over each polygon and draw it using glBegin, glVertex, glEnd.


Mother of god.

One of the biggest bottlenecks on current hardware is transfer between CPU and GPU. Unless your model is dynamic, you want the data to actually reside upon the graphics card.

Simple answer to question - use whatever format the graphics hardware supports and store it on the graphics hardware memory unless you really have to store it locally.

Share this post


Link to post
Share on other sites
this is from a little game I made in OpenGL ES(mobile version) but I assume there is something similar for the PC version of OpenGL:

glVertexAttribPointer(0, 3, GL_FLOAT, 0, 0, (void*)objects[i].frames[f].vertices);
glVertexAttribPointer(1, 3, GL_FLOAT, GL_TRUE, 0, (void*)objects[i].frames[f].normals);
glVertexAttribPointer(2, 2, GL_FLOAT, 0, 0, (void*)objects[i].frames[f].texcoords);

glDrawElements(GL_TRIANGLES, objects[i].frames[f].numt * 3, GL_UNSIGNED_INT, (void*)objects[i].frames[f].indices);


objects[i].frames[f].numt = number of triangles
objects[i].frames[f].indices = array of triangle indices
objects[i].frames[f].vertices = array of vertex data
objects[i].frames[f].normals = array of triangle normals
objects[i].frames[f].texcoords = array of texture coordinates

http://www.opengl.org/sdk/docs/man/xhtml/glVertexAttribPointer.xml
http://www.opengl.org/sdk/docs/man/xhtml/glDrawElements.xml

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this