3D scene data structure

satchmo

I'm doing a VR 3D modeller (with dataglove input and a HMD) for my final year project, and I'm trying to decide on how to store my scene.

I guess I can always go for a linked list to store the objects, but I was wondering if anyone (Void I'm looking in your direction!) has any other suggestions, or any reasons why a linked list would be a bad choice (like for searching the scene, or collision detection maybe)?

Hobbes

Sorry for stating the obvious, but why don't you build on what already exists?

Use a VRML engine or something. That way there are loads of editors out there already and you can claim that the software be customised easier.

Void

Sounds like a nice project Jazz.

These days, you don't code a "3d-engine", you code a "scene graph api". In Void, I basically have a hierarchy of objects. The root node is "space". Every object can contain other objects. There are problems with this approach, but I won't delve into that. All objects have an "id" and a "type" (typeplanet, typeship etc). This lets you convert pointers on the fly (if you know it's of typeship, then you can cast - blah = (cShip *) pointer). The "id" is used for searching the scene, they are stored in a global hash table. I'm debating whether to use the STL hash table implementation or write my own, they aren't that complicated (Java actually has better support for them). Also, in the game, ids are passed around, not pointers. If an AI has a pointer to it's target, and the target is destroyed (unallocated), then the pointer is invalid, crashometrics etc. But if it does a lookup on the id, it'll get 0 back.

Basically, every object has Draw() and Update() methods. Draw() also calls the Draw() method on any stuff that object contains, this lets you do heirarchical modeling (turrets, engines etc). The Update() function applies the objects velocity for that time slice and also moves it's collision template (I use an external collision detection engine).

I started off with just a linked list, but my code has mutated since then. A "Tree" structure is probably what you'll end up with. The hash table bit is essential though, you will need to search the scene, as you said.

Hope some of that helped.

satchmo

Right, like a tree of nodes where each node contains a linked list of other nodes, and then store pointers to these nodes in a hashtable? That hashtable is a good idea, I hadn't though of that. Thanks a lot, that's a great help.

Hobbes, I'm using position & orientation sensors for the glove and headset, and VRML most likely wouldn't let me anywhere near the COM ports (OpenGL is so much nicer to code too). And besides, this is exactly the sort of stuff I wanted to do myself. It's the best way to learn, and gets me one step closer to writing that game I've always wanted to do

Greenbean

Working slowly on a basic 3d "tree" of my own. Just started looking at it - trying to get my head around the ideas of flexible vertex formats and vertice index streams. Anyway its for a small project due to be finished (slowly) by next christmas.