scene graph rendering techniques

First, some introduction. I'm working on a game engine for my virtual reality class in the short term and for general game developing in the long term. I want to build the whole thing as a tree of objects that can have scripting, geometry, communication with each other and various other optional properties. In order to maintain portability and make this useful both for right now and for later, I also want to set up the major components (windowing, input, rendering, sound, etc) as plugins with interface classes.

My first question is about the actual rendering of triangles from meshes in the scene graph. The best idea I have right now is to define a material class that has lighting, textures, etc in it and keep a list of materials in a manager class. Then, whenever an object requests to have a mesh associated with it from the model manager I have the model manager go into the model file, find all the materials and send them to the material manager (getting indices back), and then go on and load the mesh. This way I have only load each model once, and I only load each material once (now that I'm thinking about it, I should have a texture manager that the material manager sends requests to too). So now I have all these materials loaded into memory, and a bunch of meshes defined as triangles with indices into the material list.

Now I define a renderer class with several lists of triangles, organized by material. I define a max size for the number of lists and the number of triangles in each list. When a list of triangles is full or when I need room for a new list or when I flush at the end of rendering, I switch rendering states and send the list of tris to the gpu as a display list or whatever. This should run fast because it minimizes state changes, but the drawback is that I have to transform all my vertices to world-space before I start rendering. Is this a good method?

My second question is about culling for rendering and collision detection. My idea here is to have every mesh in the model manager have an associated bounding box. Each frame, I would do a preorder traversal of the graph. If the node isn't declared as static, I get the bounding boxes for all its children and determine a bounding box that contains all of the children and the current node's geometry (if it has any) and return that. If the node is static, then I assume it was preprocessed and I just get the bounding box at the top. At the end of this traversal, I have a bounding box for each node that contains all of its children. I can use this to cull my rendering and to limit my collision testing. The clever part of this, I think, is that you can define parts of the world that don't move (and things that are currently not moving) as static, and then they don't need their bounding boxes updated. You could use this to implicitly build a terrain quadtree or an octree into the scene graph. So my question is, is this going to be good compared to traditional (quadtree, bsp, octree) methods?

Quote:

---

Originally Posted by ichijoji

My first question is about the actual rendering of triangles from meshes in the scene graph. The best idea I have right now is to define a material class that has lighting, textures, etc in it and keep a list of materials in a manager class. Then, whenever an object requests to have a mesh associated with it from the model manager I have the model manager go into the model file, find all the materials and send them to the material manager (getting indices back), and then go on and load the mesh. This way I have only load each model once, and I only load each material once (now that I'm thinking about it, I should have a texture manager that the material manager sends requests to too). So now I have all these materials loaded into memory, and a bunch of meshes defined as triangles with indices into the material list.

---

So, assuming your scene graph nodes are holding the mesh data and material data for each of things you are drawing. This is what I'm getting out of what you want to do.

You want to be able to load a single model, have it use multiple materials, maybe not at the same time, but say you have a soldier model, you want to be able to paint this soldier blue, red, green, depending on what team he is on, correct?

This is something I havn't taken into consideration into my resource management program yet, really all I control is how every model (mesh+materials) is re used, not each individually. I am questioning as to whether or not implementing this would be THAT valuable. Unless you're going to have thousands of the same mesh ALL with different materials on your screen, there really isn't a need.

But if for some strange case this is the case, your idea is completely feasable and necessary, but you must remeber, that BOTH mesh data and meterial data is stored internally in whatever model file you're loading, it would require heavy modification of the loading function for these model types. You have to cart off to town the material data, give them some type of ID, as well as cart of the mesh data somewhere, and give it some type of ID, then later in the process the two can be combined for a final result.

I'd be worried about for some reason if a mesh of a soldier got a hold of a cute rubber ducky material, the strange effects that might occur could prove fatal! Well, maybe not fatal, but not desireable :).

Well, I think it's worth implementing because not only can I instance my materials at runtime however I want like you said, but I can keep my memory use to a minimum at the same time.

Thinking about this since yesterday, I've come to a couple conclusions. The first is that the whole idea of doing bucket-based rendering is to prevent pipeline stalls and keep the cpu and gpu both going, right? So as far as that goes, I'm ok because I can tune the parameters to the size of buckets and number of buckets in my renderer to prevent stalls. Now I'm thinking that if there was some way to detect the gpu going idle, I could automatically tune my renderer to balance the processing load.

*rubs chin thoughtfully* Interesting....

It's hard to say whether or not it will be good compared to other methods. This is why we have different methods like quadtree, bsp, and octree partitioning; they work well for specific situations but poorly for others.

However, your idea is not bad, and the general line of thought has proven well in the past in my experiences. My only question is this:

Quote:

---

Each frame, I would do a preorder traversal of the graph. If the node isn't declared as static, I get the bounding boxes for all its children and determine a bounding box that contains all of the children and the current node's geometry (if it has any) and return that.

---

You mentioned that box can be used to cull your rendering, but how? Just something you should think about if you already haven't.

Essentially that is the standard/traditional method. Remember as well that if the bounding box is partially inside the frustum you must continue your cull tests. If it's completely out, you can totally ignore the children and if it's totally in, you can render all children w/o doing a cull test.

A box culls rendering by checking the corners of the box to see which side of the 8 frustum planes they lie on. If all 8 points are on the wrong side of the plane, then the bounding box is completely out and whatever it is acting as a bounding volume for is also out.

There is another method which computes the P and N vertices, or the diagonal of the box closest to the direction of the normal. I have encountered signficant problems with this method in that it tends to cull too perfectly.

It should be noted that with modern hardware attempting to split the geometry across planes in real-time should be avoided. It is faster to just send the entire object down the pipeline and let the hardware cull and clip it to the screen. So if a bounding volume is partially in and you are at a leaf node, render it anyways.

As for dynamic objects I really do not have a good system for culling them. Because they move across boundaries both in BSP, Octree's and QuadTrees so rapidly and frequently I have deduced that even making them part of the tree is pointless. Trying to recurse the tree to stick the object in the right node is very time consuming. It can be done in a separate thread, but it's still using cycles. I really do not have a good answer yet for dynamic geometry and most books only cover static geometry.

Anyone have any good algos for dynamic objects?

Quote:

---

Anyone have any good algos for dynamic objects?

---

Process using the same culling algorithm as you explained. If you're worried about performing too many checks, don't calculate everything every frame (either skip frames, or do x amount 1 frame, and x the next). That can cause some problems, but if you know the fasted an object will ever move, and scale your frustum based on that expected amount, you might be able to make work.

Quote:

---

Originally Posted by skorman00

If you're worried about performing too many checks, don't calculate everything every frame (either skip frames, or do x amount 1 frame, and x the next).

---

That's a good idea. With velocity and acceleration calculated, you could extrapolate 5 or 10 frames ahead to get a pretty good position and compare that position as well as the current one to cull. It might be a little flickery with collisions at the edge of the screen or stuff like that, but I think you'd generally get pretty good results if you didn't look to far ahead.

However when they cross boundaries, major problems occur.