Printable View
This is quite a trivial question (I'm just curious), so thank you if you answer.I was just wondering what would be best for handling objects with multiple faces.
A structure containing a linked list of coods for xyz,
or
A structure containing multiple multi-dimensional pointer, one for each of the axis.
If you ask what is easier/better to implement, you should be more specific. If you ask for performance, you won't know until you measure.
Storing very small objects in a linked list isn't a good idea; consider using a contiguous storage. Whether or not to put each coordinate is a separate container - it depends on the computations involved.
Thanks for the quick reply. I'm just looking for people's views on the subject.
At the moment I'm using structures with multi-dimensional pointer arrays, mainly because I'm more comfortable with them. I was wondering if I should of been using linked list because I've mostly over looked them, and thought it might be wise to get a little insight into it before I start to create any larger projects.
What are you doing most with the data? Inserting, Removing, Accessing, traversing etc.. most often/importantly?Quote:
Originally Posted by 0x47617279
As far as using a linked list (of any kind, except maybe a skip list) a good question to rule them out is "Do I need random access on this data?". Random access on an array is O(1) on a linked list it is worst case O(N) where N is the total number of items in the list.
If random access is not needed, or if you need something like a Stack, queue, dequeue, FIFO, LIFO etc.. type structure then a linked list is the best thing because you can get O(1) insert/removal from the Head/tail of the list (tail only with a double linked list).
I think you need to explain the use case of this "multi-dimensional pointer array" structure you keep mentioning more before we can make a real critique on what data structure would be better.
The reason you are getting several, vague replies is because of the question you asked.
You basically just said "What's better, a helicopter or a jet-ski?", and in actual fact if I read your answer how I last touched an OpenGL project (which was 99.9% about graphics performance), the correct answer is in fact something like "a Ferrari" (i.e. neither of your options, but something entirely different).
Clarify your question (specifically what you mean by "better") and we can help you a lot more.
Well, think about what functions like glBufferData accept. If you use a data format that can't be passed directly to such a function, then your program is obviously going to have to spend time converting from one format to another. Such performance gains aren't usually significant, though, but if there's no practical advantage to using another data format, then there's no point in sacrificing those gains.
Can you elaborate on that? I've been messing around with OpenGL and I was wondering as well what would be the best way to store what is going to turn into a large amount of data. I am extremely concerned about what collision detection and physics is going to look like when I actually know how to utilize the gpu for most of the calculations.Quote:
I read your answer how I last touched an OpenGL project (which was 99.9% about graphics performance), the correct answer is in fact something like "a Ferrari" (i.e. neither of your options, but something entirely different).
Honestly?
We could go round in circles all day without information of what you're after, and teaching you how to write an OpenGL program with collision detection and physics is beyond the scope of a forum answer.
What format does the graphics card need to be most efficient? Usually a plain, linear array in video memory (i.e. VBO or vertex array - a buffer you have to upload and then change as little as feasibly possible). If your object faces all use different textures then you need a texture vertex array too, and that has to also be linear and modified as little as possible. If you aren't drawing every single vertex every single frame, then things get more complicated - modifying or drawing lots of vertices but not lots of others probably requires you to use the indexed OpenGL functions to only change/draw the ones you need, which needs another linear list that contains indexes into the above linear arrays (and if your using indexed texture arrays, yet another array).
Above and beyond that, you probably want to access that information in an easier way - this probably involves not using direct manipulation of a pointer containing the original vertex (because then every single change would result in vertex uploads which will kill your OpenGL performance) but somehow "checkpointing" what changes have been made recently and then uploading ONLY the changes in one fell swoop at the end of all your graphics changes so they can upload and happen in a single OpenGL call. How you do that in a way compatible with your program is entirely dependent on your program.
How does that tie in with collision detection, which probably doesn't care about what format the arrays are in but might benefit from a ordered list of some kind (because you're likely to iterate through each object and compare it against every other object within a certain radius). Physics? Probably the same, but that totally depends on how you do physics - some hardware-accelerated libraries can probably use very similar formats to OpenGL.
Fact is, there are just too many variables to give you a "correct" answer, and you can only get there by trying and - I can tell you - it can get very hairy very quickly. And that's before we even consider the question of what platform you're aiming at - where copies to video RAM might be fast (e.g. desktop with GPU) or very, very slow (e.g. some embedded device), or how many threads you intend to put this code into and what will run in what order or even simultaneously (or will you serialise the physics, then the collision detection for any "new" collisions, and then draw the result, each of which is dependent on the result of all the previous ones before you can fill a single pixel on the screen?).
Long answer: linear arrays in RAM, copied to the graphics cards as VBO's / indexed vertex and texture arrays which are inherently optimised for huge linear arrays that aren't updated much (the position of world objects and their textures changes little in most games, so you won't be doing much re-uploading - but your program might be WAY different) and then YOU find out a way to make that programmable for yourself. Or you might find that even OpenGL direct-mode calls each time are more than enough for your purposes and you don't want to faff with all that other stuff.
Short answer: You tell us.