a question that will make you think

Well well well....most of us have taken Computer Science classes...and in those Computer Science classes, many times they teach us of such things as Big-O, sorting algorithms, and searching algorithms.

Many times you question when you will ever use Big-O, however, I am here to tell you, I have used it several times in my computer programming experiences, and it has come upon me yet again today.

I am unsure, however, which road I should take in programming a certain function of mine, each road has a seperate BigO.

Here is my problem:

I have a 3D model. Each model is composed of several hundred meshes.

Now, in my program, I would like to be able to rotate the entire model and also to be able to rotate a single mesh IN the model.

This is not necessarily difficuly. I have the means to do so. The question is, which road to take?

Using deductive reasoning, I have narrowed my options down to two different methods of doing this.

Here is how rotations work:

I might want to rotate the model more than once in a single frame. I also might want to rotate more than one mesh in a single frame. In fact, I might want to rotate a single mesh more than once in a single frame.

This posed a problem for me under my current method of rotating my models. So I rewrote my model-rotating code.

I use a stack. If the RotateModel() or RotateMesh() functions are ever called, they simply set flags to tell my program what needs to be rotated before we do any drawing of that model again.

So lets say I do this in one frame:

Rotate the model
Rotate mesh #5
Rotate the model
Rotate mesh #8
Rotate mesh #5

I would push all of those actions that needed to be done onto my stack, so my stack would look somewhat like this:

mesh 5 <-top of stack
mesh 8
model
mesh 5
model <- bottom of stack

Now I have a stack containing rotations that need to be done before I ever draw the model again.

So I call the DrawModel() function.

The DrawModel() function handles all the rotations that need to be done, and then draws the model.

Here is where my problem comes in. Consider this code in my DrawModel() function:

Code:

for (uint i= 0; i<UnitModel.GetMeshCount(); i++) { glBindTexture ( GL_TEXTURE_2D, texture [MECH_METAL] ); LMesh &mesh = UnitModel.GetMesh(i); // Texturing Contour Anchored To The Object glTexGeni(GL_S, GL_TEXTURE_GEN_MODE, GL_OBJECT_LINEAR ); // Texturing Contour Anchored To The Object glTexGeni(GL_T, GL_TEXTURE_GEN_MODE, GL_OBJECT_LINEAR ); glEnable(GL_TEXTURE_GEN_S); // Auto Texture Generation glEnable(GL_TEXTURE_GEN_T); // Auto Texture Generation glVertexPointer(4, GL_FLOAT, 0, &mesh.GetVertex(0)); glNormalPointer(GL_FLOAT, 0, &mesh.GetNormal(0)); glColorPointer(3, GL_FLOAT, 0, &mesh.GetBinormal(0)); glDrawElements(GL_TRIANGLES, mesh.GetTriangleCount()*3, GL_UNSIGNED_SHORT, &mesh.GetTriangle(0)); } glDisable ( GL_TEXTURE_GEN_S ); glDisable ( GL_TEXTURE_GEN_T );

Some of you do not know OpenGL, so I will tell you what it is doing.

It is simply iterating through every mesh in the model and drawing that mesh. In the end, every mesh in the model will be drawn, and so (obviously) the entire model will be shown on the screen.

Now, in order to do rotations correctly (so as I do not rotate anything I do not want to rotate) I need to use glPushMatrix() and glPopMatrix().

So if I was just doing a simple rotation of the entire model, I would:

1. push matrix
2. glRotatef a certain number of degrees
3. iterate through the meshes and draw all meshes
4. pop matrix

The process is different however, if I want to rotate only a single mesh. In this case, I would:

1. iterate through the meshes and draw them until I reach the mesh I want to rotate
2. push matrix
3. glRotatef that mesh
4. draw that mesh
5. pop matrix
6. continue iteration of the rest of the meshes

This in itself is not that much of a problem. The problem arises because my rotations are not necessarily sorted.

Take my earlier example of my rotation stack:

mesh 5 <-top of stack
mesh 8
model
mesh 5
model <- bottom of stack

Mesh 5 needs to be rotated TWICE in a single frame. In order for this to be done under my current construct, I would have to iterate through every single mesh more than once in order to rotate.

THESE ARE MY TWO OPTIONS:

Option 1: Create a queue. Every time I pop a "mesh" off the stack (signaling that a mesh needs to be rotated), push/enqueue it onto the queue.

Do all the model rotations.

Then dequeue all the mesh rotations that need to be done, sort them using a quick sort or merge sort (so we do not have to iterate through every single mesh more than once) and then do the iteration of the meshes, and rotate as we iterate.

This would yield the following BigO:

Sort Time: O ( n log n )
Draw Time: O ( n )

Option 2:

In this option, I handle rotations as they come off the stack, but I do it in such a manner, that I do not have to iterate through every mesh more than once.

I would pop an item off the stack.

If it was a mesh was popped off the stack, I would simply index right to that mesh, rotate it, draw it, and go to the next thing on the stack.

If a model was popped, I would simply do a glRotatef().

After all of that, I would then iterate through all the meshes and draw all of them.

This would yield some extra draw time, but not as much.

The BigO of this is:

Extra Draw Time: O ( n ) <- worst case
Extra Draw Time: O ( 1 ) <- best case
Draw Time: O ( n )

So those are my two options.

First off, if you see an error in my logic anywhere, please correct me.

Second off, which method do you think is better/

Drawing to video memory is slower than swapping objects, even though the BigO is better.

Let's say "x" is equal to how many MESHES i want to rotate.

So, Option 1:

BigO = (x log x) + (n) <- best case
BigO = (x^2) + (n) <- worst case

Option 2:

BigO = (n) + (n) <- worst case
BigO = (x) + (n) <- best case

The BigO for Option 2 is better, however, drawing on the screen is slower in runtime than swapping variables is. That is why I do not know which one to use. Even though the BigO for doing the extra drawing is a better BigO, think about it's worst case scenario.

If Option 2 hit it's worst case scenario, I would basically be drawing each model on the screen twice. Each model consists of about 15000 triangles. I don't think I want to do that.

So the BigO's in this case can be deceiving.

Which option should I take?

Is one of my options flawed?

Do you see a better option I could take?

Thanks.

Why not write a model class that handles an array of meshes (for direct indexing) that has there own rotation values of xyz.

when ever you want to rotate a mesh(say 5) in a model do say:

Code:

model.mesh[5].rotate(val,x,y,z);

Then rotating the entire model

Code:

model.rotate(val,x,y,z);

Which would send all the values to the meshes. additive rotating.

Then when you actually draw the model, check to see if a meshs x,y,z axis has been rotated, pushmatrix if necessary and do rotation appropriatly.

Perhaps this is already one of your options, and i didn't understand, but i think this owuld be best.

Not sure if this helps but:

Any mesh that needs to be rotated should have its own matrix. It sounds like your meshes are related to one another in one way or another. The way to do complex rotations is to link all of them and then concatenate each mesh's matrix with the mesh prior to it.

There is an article on www.gamedev.net about this.

well, i solved the problem the best way i know how.

I used a bucket sort! The only O(n) sort known to man :cool:

This what I do:

I handle the model rotations immediately as they come off the stack.

If I pop a mesh rotation, I throw it into my bucket sorted array.

I then handle all mesh rotations in my iterative drawing loop.

Works great.

anytime a mesh is rotated more than once in a frame, instead merge all the rotations in a matrix and perform a single rotation on the mesh.

thats what i already do. the problem for this thread was fixed awhile ago. do not bump this thread.