a question that will make you think

This is a discussion on a question that will make you think within the Game Programming forums, part of the General Programming Boards category; Well well well....most of us have taken Computer Science classes...and in those Computer Science classes, many times they teach us ...

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738

    Lightbulb 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.
    My Website

    "Circular logic is good because it is."

  2. #2
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704
    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.
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

  4. #4
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    well, i solved the problem the best way i know how.

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

    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.
    My Website

    "Circular logic is good because it is."

  5. #5
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    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.
    It is not the spoon that bends, it is you who bends around the spoon.

  6. #6
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    thats what i already do. the problem for this thread was fixed awhile ago. do not bump this thread.
    My Website

    "Circular logic is good because it is."

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exam Question - Possible Mistake?
    By Richie T in forum C++ Programming
    Replies: 15
    Last Post: 05-08-2006, 03:44 PM
  2. I need help to compile this code...
    By wise_ron in forum C Programming
    Replies: 17
    Last Post: 05-07-2006, 12:22 PM
  3. Question about binary trees and files
    By satory in forum C Programming
    Replies: 9
    Last Post: 03-06-2006, 05:28 AM
  4. Question about atheists
    By gcn_zelda in forum A Brief History of Cprogramming.com
    Replies: 160
    Last Post: 08-11-2003, 11:50 AM
  5. assembler and linker stuff...question
    By dirkduck in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 12-16-2001, 11:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21