What is the best data structure to use for a 3D modeller? Currently I use both dynamic array and linked list for my 3D modeller data structure. Dynamic array is used to keep track of all the objects (box, cylinder, sphere, mesh etc) and linked list is used to keep track of the vertices of the mesh and the triangles that made up the mesh. I would like to hear your opinions on whether there is a better data structure to use.

Actually, I tend to do the exact opposite of the way you have it implemented--linked lists for all the objects and dynamic arrays for vertices and indices

I used static arrays for everything in my modeller.

PS: Constructors are wicked handy when creating ''default'' objects.

Nice topic, I'm actually working on something like this and havn't decided what to use yet. But I'm also going to need to store texture data (actually just a string like "tex1.bmp") and texture coordinates...

And I'd guess you mean a static array of pointers right?

But -why- did you guys pick the data structures you did?

===========================================
As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality.

-Albert Einstein

Edited by - Tebriel on August 4, 2000 8:09:30 PM

I picked the data structures that I did (all static arrays)because I made the modeller in QBasic for QBasic, and in QBasic there are NO POINTERS, thus, no linked lists. Plus, the modeller runs like ass. Qb isn''t even fast enough to render one 10-polygon textured and lighted object in real-time. That sucks.

I use STL vectors for both vertices and indices.

ECKILLER

Oh, well you didn''t say you used Qbasic, lol... I guess that would seriously limit your choices of data structures.

Anyone else have any advice?

===========================================
As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality.

-Albert Einstein

STL data structures are nice, especially vectors and lists. For maximum efficiency, linked lists are good for large groups of objects that change a lot, but don''t need to be extremely fast in finding one particular object. Vectors are faster for smaller groupings that don''t change too much. I would recommend a linked list for objects and a vector for faces and vertices. The fact is that the speed difference between the two won''t make any difference in speed for a modeller, and the synax for the two is almost identical (iterators are cool). So you might want to just go with vectors for everything - less overhead and easy access with the [] operator.

-RWarden (roberte@maui.net)

You don''t think it''d make a big difference speed wise? Hopefully you''re right... but I''ll probably have thousands of faces and even more vertices to mess around with, so I''m not that optimistic . Guess I''ll just have to try it out and find out.

===========================================
As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality.

-Albert Einstein