Thread: Data Structure to store unlimited dynamic vectors

  1. #1
    Registered User
    Join Date
    Dec 2008
    Location
    California
    Posts
    37

    Data Structure to store unlimited dynamic vectors

    I'm creating a 3d engine right now using OpenGL and I want to make it very object oriented and easy for the developers to use. I don't know how to store thousands of dynamic vector on my engine like 3D models.

    Should I use an array or linked list to store it or is there any data structure out there? I want to make it fast as possible because frame rate is the important in 3d games.

    Thanks

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Standard containers (vector, list, etc) will support what you want ... at least, in terms of storing an arbitary number of elements.

    A fact of life is that a large vector, list, or other container implies a performance hit if you access elements at random (with different trade-offs for different containers). You need to be smart in terms of how you use them (eg using smart algorithms to access the particular subsets of the data you need). Problem is .... the nature of a suitable algorithm depends on needs of your application: no general-purpose, incredibly efficient, solution is possible. You therefore need to do some analysis, to find a good technique, based on needs of your application.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by m3rk View Post
    I want to make it fast as possible because frame rate is the important in 3d games.
    That's not entirely true - the CONTENT of the frame is probably a whole lot more important. I'm sure there are thousands of games with 300 fps that no one would want to play at all - because the game itself is rubbish.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Dec 2008
    Location
    California
    Posts
    37
    I have this.

    Code:
    class VertexBuffer
    {
    
    private:
    core::vector3df vertexData; // <--- This is it.
    
    }
    
    template <class T>
    class vector3d
    		{
    			public:
    				T x, y, z;
    				vector3d() : x(0), y(0),z(0) {}
    				vector3d(T x, T y, T z)
    				{
    					this->x = x;
    					this->y = y;
    					this->z = z;
    				}
    
    				vector3d(vector3d& copy)
    				{
    					this->x = copy.x;
    					this->y = copy.y;
    					this->z = copy.z;
    				}
    
    				void set(T nx, T ny, T nz)
    				{
    					this->x = nx;
    					this->y = ny;
    					this->z = nz;
    				}
    
    .
    .
    .
    .
    .
    .
    .
    
    		};
    	typedef vector3d<float> vector3df;
    }
    By the way, I'm not accessing it at random. I'll just store all the vertices and pass it into the buffer and draw everything stored on the vector3d.

    Do you think creating a vector3d class that can insert just like the <vector.h> is good? How can I do that? Can you give me some examples? I didn't experience this problem when I was creating 2D game because most of the variables I created there are all static. What I'm creating right now is an engine meaning I don't know how many vertices the developer will create. Did I make any sense? BTW, I'm sorry for my noobness.

  5. #5
    Registered User
    Join Date
    Dec 2008
    Location
    California
    Posts
    37
    Quote Originally Posted by matsp View Post
    That's not entirely true - the CONTENT of the frame is probably a whole lot more important. I'm sure there are thousands of games with 300 fps that no one would want to play at all - because the game itself is rubbish.

    --
    Mats
    What I mean there is, my top priority on my engine is to squeeze more performance for now. I'm creating an engine not game!

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by m3rk View Post
    Please don't change the topic.

    What I mean there is, my top priority on my engine is to squeeze more performance for now. I'm creating an engine not game!
    That wasn't entirely clear from the original post.

    And whilst performance is important, there are lots of other considerations to take into account.

    The vector3d design you have seem adequate. Since x, y, z are public, I'm not sure you need so much of the copy/set functionality - why not simply do
    Code:
    vector3df v;
      ...
      v[n].x = somex;
      v[n].y = somey;
      v[n].z = somez;
    There is no need to have a separate function to set those values. [Not that I'm saying you can't have one!]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The copy function does exactly the same that the operator= already does. The set function could be convenient, but basically this is already available as:

    Code:
    x = vector3d<T>(a, b, c);
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Myself, I am a fan of having a vector like this:

    Code:
    template<int N, typename T> class Vector;
    
    typedef Vector<2, double> Vector2d;
    typedef Vector<3, double> Vector3d;
    typedef Vector<4, double> Vector4d;
    Etc, where one would access X, Y and Z as:
    Code:
    vector3d_object[0] = x;
    vector3d_object[1] = y;
    The upside of this is easy calculating with any dimensions. No need to recode anything for other dimensions. No need to use the .x, .y or .z to multiply matrixes (which, in this case, can be of any size). One simply for loop is enough to do anything.

    Just some advice.

  9. #9
    Registered User
    Join Date
    May 2007
    Posts
    147
    m3rk:

    You've touched upon a classic study in this area of design.

    It's time to crack some books on the subject. Boards like this are excellent resources, but you're approaching a topic that could fill several texts.

    It's called scene management.

    I highly suggest considering David Eberly and one of his books on game engine design.

    Google Eberly WildMagic.

    Wild Magic is an open source game engine, including physics and special effects, for which Eberly has written several books on the subject. Eberly is a mathematician, and a professional game developer/consultant.

    Your questions are valid, but like others have hinted, you're a bit overfocused on one micro-part of a larger field of study that is simply way to involved for anyone to simply say "here's the way to do it" - because there are several ways, and ultimately in a real engine, there are competing interests for CPU power, which is why several have said the simple truth - it depends on factors of your design goals.

    That's why you need a book like Eberly's, and a few others on game physics (I'd suggest Ian Millington's book on physics from the same publisher) - which will lead you into perhaps a few specialty studies on contacts/collisions.

    In fact, you'll discover (slowly if you try to stumble on all of this on your own, experimenting) that more CPU cycles can be consumed in the contact/collision phase of the physics engine than in the rendering engine.

    In the rendering side of the engine, where you're currently focused, the CPU is generally not as busy as the graphics system, and the primary wasted time is in overhead calling the underlying graphics library (OpenGL or DirectX). Choosing the better, more efficient means of delivering data to the graphics card is more important than overfocus on containers.

    Eberly notes that professional game developers (in the closed rooms of the high end) tend to avoid the STL for several reasons he details in his book. This is less true of PC based games, though. One of his more powerful arguments against the STL is the lack of support for it in certain target platforms, and a few examples of speed problems. They can be overcome, and the STL IS applicable, despite Eberly's warning, but he's correct in pointing out examples where the STL can end up fighting you, and when it does, drop it. (However, Eberly's solution for smart pointers is, IMO, abysmal - they're based on the derivation from a common "Object" class - pre-Template style).

    The WildMagic engine can be downloaded for free, even used under a GPL like license, but it's not entirely commercial-ready code. It's used in commercial or research work, but it's primary purpose is to illustrate the tenets of game engine design. However, the code is too dense to study without the books; at least it's going to be a LOT more efficient and illuminating to read the book as you study the engine.

    His discussion of scene management is exactly where you need to be right now - scene management is a discussion of data structures and engine function, and how they relate to speed, from a practiced and mature viewpoint that takes into account all of the competing issues. In 3 months you'll have covered what would take you years to discover working in isolation.

    For example - have you yet considered object culling?
    Have you discovered the subjects of BSP tree's, OctTree's and other data structures?

    These are used to do something more important than the raw speed design of feeding the graphics engine data. They're focused on figuring out what NOT to draw (skipping things that can't be seen turns out to be more important that raw speed in a loop of objects).

    Have you discovered bounding volumes? They're related to object culling. If not, there's an often un-discussed subject of a second set of object data, sometimes convex hulls, that surround the objects, but are never drawn, used by the culling engine and/or the physics engine. They also require efficient management, in the context of the overall engine, and may even turn out to be more important to performance than where your attention is currently focused.

    What about textures and how they relate to performance? Did you know that on some hardware it's more important to sort the list of objects to draw by the texture(s) they use, than by their Z order?

    ...and transparencies. Did you know you have to draw them after everything else?

    These subjects through a wrench in the works where you're studying now. The conclusions you'll draw from the experiments you're currently working on will convince of the wrong conclusions, because you're working in isolation.

    Eberly covers 98% of this in one book.

    I'm not selling it (well, I guess I am in a way - just not making any money), it's just that I can see you have a number of posts around here, and I can tell you're focused on figuring this stuff out. I know what's going to happen - you'll burn out after a few months unless you undergo a study that reveals just about everything that's been discovered by a few decades of engineering, and I've not found a single text with a more complete coverage of the subject, even though I disagree with a few of the design techniques he uses in his engine. He's not a programmer, per se, he's a math PhD - but his code is illustrative to this study, his treatment serious and his advice is correct.

    Your current line of questions indicate you're ready to head in such a direction.
    Last edited by JVene; 04-22-2009 at 06:33 AM. Reason: Not enough coffee, stumbling fingers

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Data structure for storing serial port data in firmware
    By james457 in forum C Programming
    Replies: 4
    Last Post: 06-15-2009, 09:28 AM
  2. Creating Dynamic Structure in C
    By SomeNath in forum C Programming
    Replies: 1
    Last Post: 03-19-2005, 09:11 AM
  3. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM
  4. gcc problem
    By bjdea1 in forum Linux Programming
    Replies: 13
    Last Post: 04-29-2002, 06:51 PM
  5. vector static abstract data structure in C?
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 11-05-2001, 05:02 PM