   Scenegraphs, space partioning & "instancing"
  Hi,Since this is pretty much the first time that I try to integrate seamlessly into a scenegraph space partinioning schemes as just regular nodes that can be inserted/deleted, I'd like some feedback on my idea.Basically, a map in my game is build by several huge heightmaps, and several models ranging from big(like building&interiors) to smaller structures. I also have decided to go for octrees, although it might change in the future.Now, the problem is that I will want to use many copies of models at different positions in the level, with variances in size/orientation/materials/shaders. I want to be able to change at any time some properties(materials/shaders) of a particular instance and of course I don't want to have a copy of the same vertex data for each instance. Treating the whole level as a "triangle soup" would make that difficult. So, here's my ideas:1)A class Mesh, which just contains info about vertices,normals,texcoords and triangles. Could be anything, from a terrain to a building.2)A class Model. Model has a list of pointers to one or more existing meshes(multiple models can share the same mesh data), a list of textures, and a functor that renders that model using just 1 material/shader. It can render the whole model, or just a part of it using a triangle list. It also has a 4x4 transform matrix, which allows to render the mesh data in diffent positions/orientations.3)A class Entity. It's the actual game object, and contains zero(no visual representation),one or more models.4)Now, the class Octree. It contains a list of several models. If, say, I would want to add the visual representation of a terrain in the octree, I would do:map->octree->AddModel(map->heightmap[0]->model)When the octree is compiled(off-line,of course), for each model:1)Takes all the mesh data from the model.2)Makes a temporary copy of the data, and transforms them based on the model's transform matrix.3)"Place" the data in the octree, and determine which triangles belong in which octree nodes, and build the trianglelists. Each (terminal) octree node has a list of all the models it contains, along with the corresponding triangle list for each one.When we call, Octree->Draw(...), we perform the usual culling stuff and then each visible node is rendered. Now, when rendering each octree node:1)Pick a model from the model list the octree node has.2)Call model->Draw(...) by sending the triangle list.2)The model sets up the material/shader and renders the mesh data(using VBO), by setting the GL matrix to its transform matrix(.Does anyone sees any flaws in this? What could go wrong, what can't it handle well? What are your suggestions for improving it, both in terms of design and efficiency?   
  What does the entity do, is it just a group of models?  I'm thinking that you may want to have the transform matrix in the entity if they are instances of the models.Maybe also abstract the textures into a Material class along with other render properties of it (colors, blending, etc).  I'm guessing that models can share materials...   ;Quote:What does the entity do, is it just a group of models? I'm thinking that you may want to have the transform matrix in the entity if they are instances of the models.An entity is just what I said: A game object. It can be an enemy, a vehicle, a building. It has a certain semantic in the game, a certain role,behaviour, maybe AI... The model is just its visual representation. The two have a has-a, not an is-a relation(a game object is not a model, it has a model).The mesh/model/entity thing goes like this://Loading meshes: Here and only here actual geometry data is kepttorso1=new Mesh("c:\\torso1.obj");torso2=new Mesh("c:\\torso2.obj");head1=new Mesh("c:\\head1.obj");head2=new Mesh("c:\\head2.obj");legs1=new Mesh("c:\\legs1.obj");legs2=new Mesh("c:\\legs2.obj");Model alienmodel,demonmodel;alienmodel.AddMesh(torso2);//Add reference to mesh torso1alienmodel.AddMesh(head1);alienmodel.AddMesh(legs1);demonmodel.AddMesh(torso2);demonmodel.AddMesh(head2);demonmodel.AddMesh(legs2);Entity* alien=new Alien();Entity* demon=new Demon();Entity* megademon=new MegaDemon();alien->model=alienmodel;//Just a shallow copydemon->model=demonmodel;megademon->model=demonmodel;The entities will of course set the transformation matrix of their model(s) based on their position and other properties(for example, the megademon will scale its model as well). I don't want to keep the transform matrix in the entity, because then I would have to send the whole entity to the rendering parts of the engine, and there's no reason to do that. The model should have all the data that are necessary to fully describe a visual representation of the game entity.Of course, the octree as I described it will be used for static geometry, but the principles are the same.   ;Quote:2)Makes a temporary copy of the data, and transforms them based on the model's transform matrix.3)"Place" the data in the octree, and determine which triangles belong in which octree nodes, and build the trianglelists. Each (terminal) octree node has a list of all the models it contains, along with the corresponding triangle list for each one.What are you meaning by "trianglelist"?  A list of indices?  Or even vertices?  It seems like your goal of not having a copy of the vertex/index data for each instance starts to break down when you have to build these trianglelists for each node.I'm not saying that's a bad thing - I think constructing separate index lists for each instance might be a cool idea.  I'm trying to think of how to optimize static geometry myself.  It seems like breaking the mesh and constructing the triangelists would be a very difficult task, but I haven't done much in the ways of mesh decomposition.Just my ideas... haven't done any of this practically!Edit:  On second thought, you couldn't simply have a list of indices because for each node you have to create new vertex data to break it on the plane.  So you would have to create new vertex data for every instance at some point, right?   ;  In my space partition implementation I have 2 classesclass partition_nodeandclass scene_nodepartition_node represents the space partition cube for octrees ....the scene_node is the class from which I derive the objects that are added to thescene graphNow there is the problem of entities/models/static geometryI solved it as followsstatic geometry which is just a collection of static meshes is represented by a class calledclass static_geometry : public scene_node;Now lets say you have a octree and there are 5 meshes with the same material inside this node(its a leaf node) so I merge these meshes to a single mesh to reduce the function calls required to render it.In my implementation a mesh can consist of several materialsmesh->material->vertex,color,normal,binormal dataFor entities that use models as their visual representatives I just store the model reference and some info about its locatione.g.://this is the global information of that modelclass model_vertex_data;class model_bone_data;//in entities I store thisuint32 modelid;uint32 animationid;class rendering_infomation{position;rotation;animationtime[0.0,1.0];}Now you can scan the scenegraph for visible entities, sort these entities by model/materials and finally render it.With multiple materials per mesh you store an array of pointers to the mesh classesand for each material an array of indices to the mesh pointer array to minimize state changes.You also need to take care about lighting information, what lights effect which object ....   