7 replies to this topic

[altreality]

Hi,

I want to create complex scenes in my 3D application. Like a house with rooms in it and stuff inside the rooms. I want to remove rooms which are not visible in the camera. I know opengl will clip stuff that are not visible, but I am talking about not sending the data about rooms and objects which are blocked, at all.

So I have heard that for complex scenes a scene grah can help. But most implementation of scene graphs seem to take a hierarchical view of the scene. Say we have a city which is the root node, then the buildings would be its children and the rooms in the buildings would be lower level chidlren etc. This structure does not help in knowing which rooms are adjacent to each other(all adjacent rooms are children of the same parent node).

I came up with this idea for a scene graph where the links between nodes represent the "is adjacent" relationship and the nodes are objects :



The lower part of this picture was added later, please ignore it.for now.

So here we have irregularly shaped rooms. The camera is at the position shown by the red dot. The bounding box(BB) of D is the red border square. As long as the camera is in the red square, the 3D and physics data for B, C & A is loaded. Of course D is there also. But when it moves out of the box to say A, then B & C is unloaded. Also the camera is marked to be "in" A right now.

This saves on texture memory and mesh calls to the graphics API. However a tricky issue is, in a huge graph with many rooms, if I am given a camera position, then I would need to find its owning room by going through all the nodes in the graph which may be prohibitive.

Any objects inside the room D is considered to be adjacent to it as well.If an object is carried outside the room, well then the links are changed to reflect the object's new spatial position with respect to the rooms.

Has anyone got a better suggestion on how to solve this ? Are there open source libraries out there which can do it faster. Especially if I have a camera position and I want to get to the node to which it belongs(is closest to) ?

----------------

The other option as shown in the lower part of the picture, is to combine a hierarchical volume graph and an adjacency graph into one. So we start with a hierarchical graph as shown in the lower part of the image where the root is A and A's children are inside the volume of A. Now if I want to find in which volume the camera is located I can do so in logarithmic time.

However each node(like C) also maintains links to volumes adjacent to it. So I can find and load only adjacent rooms and not the whole darn house !

what do you guys think ?

Edited by altreality, 18 May 2012 - 09:01 PM.

[L. Spiro]

Every time someone says “scene graph” an angel loses its wings.

What you want is called “portals” and “potentially visible sets”, or PVS.
As it just so happens I am in the middle of a multi-part tutorial on exactly how to generate this data for the exact purpose your are describing.
Part 1: http://lspiroengine.com/?p=400

I plan to take readers through the entire process—with additional notes on stability and speed—and ultimately leave readers with a fully functional .MAP loader (meaning you can make all your levels using Valve Hammer Editor), PVS system for efficient rendering, and a bit of ad-hoc physics for the delight of those who want to see little balls and boxes bouncing around their maps.

If you don’t want to wait that long, I have already given you the Google terms you need: Portals, PVS, Potentially Visible Sets.
But I don’t think it will take too long to finish my tutorials; I am pretty into this right now and have even cancelled a date just to stay home and work on it.


L. Spiro

Edited by L. Spiro, 19 May 2012 - 02:35 AM.

[altreality]

Good going L. Spriro. Looking forward to your tutorial on BSP trees. Since you seem to have done similar stuff, I am wondering if my approach is in any way close to an efficent solution

[L. Spiro]

The concept of finding out only what rooms are visible from any other given room is of course the most efficient solution, although you would not want to unload textures etc.
Typically the wall paper in a house will be in many rooms, so a generalized scheme for dropping resources—rather than one specialized for this type of situation—would be more appropriate.


It is the implementation that matters most in terms of efficiency, not the concept. Implementing portals/PVS’s is not so trivial, but you have the search terms if you want to take a peak at how it is done and decide if you are up to it.


L. Spiro

[altreality]

ok , well here is some more info about my specfic case. I am developing a plugin for a space flight simulator called as Orbiter : http://orbit.medphys.ucl.ac.uk/

It allows creation of spacecraft, bases etc and has an extensive API.

It already provides a directx based viewer, functions for loading meshes etc. A lot of the low level stuff is already automated such as texture loading which happens along with the meshes, occlusions culling etc. So I would probably not need to go down to the polygon level. Any help to the CPU in terms of unloading meshes which are not visible to the camera would help while exploring the inside of large vessels.

I have decided to integrate Bullet Physics with Orbiter and it actually works quite well. I have got a rover traversing Lunar terrain now : http://code.google.com/p/surface-physics/

What I will be doing with the PVS is tracking large sections of a base or vessel and loading and unloading the sections based on the distance of the camera from a section.I ll need to load the graphics stuff and the physics stuff together of course so collisions happen based on whats visible.

I am currently goin through the concept of PVS as discussed here : https://docs.google.com/viewer?a=v&q=cache:sH7_Z8XIlzAJ:www.cs.ucl.ac.uk/staff/ucacajs/frontiers_shortlow.pdf+example+Potentially+Visible+Sets&hl=en&gl=us&pid=bl&srcid=ADGEEShcyvQ2_8sLXFH9WrbNtvvbXp-Ef4MF6OPc6lBtx6Nh3yROUwk0pNqTjn7cVASl9erVOxoljp5zuZysG9OTFfXNXUJWf-wuwvy3qDb1NPQG153Y-tgVLEQ9I0Lft2xOjGbMb4es&sig=AHIEtbSjGYnyXDdAO19JNnM7LkOGC2h2Sg

[altreality]

Hmmm, in the above paper they seems to have used adjacency graphs with the cells being the nodes and the links between cells being the portals(or openings/doors). See section 3. Creating Frontier Sets

Has some pseudo code to generate the PVS. It will probably be a good starting point.

[altreality]

So till something better comes up, I ll continue to flesh out my idea here for my limited simple purposes. If anyone has got suggestions please do let me know.

My Lunar base will be set up something like as follows:


So it will be in 3D but lets stick to a 2d view for now. The entire area is divided up into sections. Each sections can have rooms. The sections S2 has 4 rooms. The remaining area is outside.

I would store this as an adjacency graph as follows :



This is basically space partitioning though not like a BSP. Each node stores its bounding box in space and there is an out node always for the "rest" of the area in a section that is not covered by rooms. We can get which room the camera is located in , at the start of the game, in O(log N) time as its a tree.

However we also need to store adjacency information, so we add links to adjacent rooms :



This helps us decide which rooms to load when the camera position has been found in the tree. We simply load all adjacent rooms for now.

But how about using the graph to support level of detail as well. We dont want hi-res textures and meshes for rooms to be loaded if they are really far away from the camera.

To support it we have each node maintain its distance from camera. Now suppose the user is in R3 and decides to go left to section S1(so he is not only changing rooms but sections as well), then we have the :
leaving node R3 and the
entering node S1

Operations initiated for the leaving node :
For every leaving node, we tell all adjacent nodes to update their camera distances. R1 may find its quite far away from the camera now, so it loads a lower detail mesh for itself.
R2 and R4 are no longer visible as they are not in the visible set of rooms/sections for S1. They decide to unload themselves. Whenever a rooms unloads itself it tells its parent that its unloaded itself. A bitmask in the parent is updated to reflect the fact(as shown below S4). 1 means loaded, 0 means unloaded. After all adjacent nodes are updated we go to the parent node of the leaving node(in this case S2 and repeat). The parent may find that its bit mask == 0, so it can unload itself. Or some additional conditions can be set. If the camera has moved out of the base and far from it, then all meshes for the base are removed !.
If some rooms are in the visible set of the entering node then they can still check the camera positions and load lower res textures/meshes if needed.
R3 also updates its own meshes based on the camera distance.

Operations for the entering node:
Here it may be possible to go lower down the node S1 to decide which room the camera is in(if S1 has rooms). I decided that if S1 has rooms then the pointer from R3 will directly point to the adjacent rooms instead of to the parent section S1 (for speed).
We simply check all nodes adjacent to S1 and all children of S1(if any) and load them. When the nodes load they will check the camera position and load approporiate low res/high res meshes. We skip the node we just came from i.e. R3 as its already updated itself and any nodes adjacent to it.

What each node must contain :
All this means the nodes have to track their own meshes and loaded state. Camera distance need only be updated when the node is told to update itself. The node must also maintain a pointer to its only parent and a list of pointers to its adjacent rooms/sections. It must maintain a bitmap to track which of its children are loaded and if it can unload itself.

Bounds checking:
Bounds checking will probably be a bottleneck here especially due to irregularly shaped rooms, Each node can maintain a list of shapes which overlap in some places, to define the room. So all the shapes are checked against. to decide if the camera is in the room...kind of like clipping shapes.

Also I havent gone down to the level of loading/unloading objects inside the room yet, but this can probably be added by adding another level to the tree.

I will construct the graph while the objects in the rooms ..and the rooms themselves are being laid out in blender or max or whatever.

Edited by altreality, 19 May 2012 - 03:24 PM.

[L. Spiro]

As far as I can see you are still just explaining your concept, but simplifying the points where implementations become abstract.
Implementation is everything, frankly, in this situation.

My next tutorial is available already, and gives you insight into what a computer does when it tries to perform this task.
The result is not yet optimal but I will be presenting more tutorials that will ultimately allow you to create the most optimal solution possible for your given situations.
If you are willing to wait.


L. Spiro

Edited by L. Spiro, 20 May 2012 - 07:51 AM.