Scenegraph performance improvements

OpenGL Development JOGL Development
#1

First, since i’m new to this board: hi @ everyone

I’d like to ask you for some advice how to solve some scenegraph performance issues.
About two years i wrote a small visualisation plugin during an internship. It had to be written in java so i decided to code a very simple (and crude) scenegraph using jogl. Each inner node of the graph used a vector to store child nodes and Iterators to traverse them.
While i knew that wasn’t a very elegant solution it was enough to do the job since it was only going to be used for very small scenegraphs without any changes at the graph during rendertime.
Recently i got a call from the company about some performance problems with my plugin.
Looking into it i found that they started to use it for a lot bigger scenegraphs (20000+ nodes) and changed node parameters during the rendering process. I figured out two major problems:

  1. Changes at the scenegraph during rendering cause multiple ConcurrentModificationExceptions due to the Iterator usage.
    (As a quick fix i replaced all Iterators with regular loops)
  2. While node parameters like Color are changed often the node hierarchy of the graph stays the same at all time, therefore my original approach of using a different vector for each inner node is probably not the most efficient solution.

I’m now thinking of using a single list datastructure to store the scenegraph nodes preorder-sorted for a more efficient traversal.
Does anyone of you have experience with problems like this and can give me a few tips to further increase the performance?

TIA

#2

IMHO: Scene-graphs should be avoided. This issue however is like language/OS fights.

#3
  1. When you’re rendering, you shouldn’t be altering the scenegraph. If you need to concurrently render and modify a scenegraph, then you need to double-buffer the scenegraph (easiest solution anyway).
  2. Not sure what you’re saying here: if a change is made that has no impact on child nodes then there’s no need to do anything about it, right? Also: allow loads of changes but calculate no state. Lazily evaluate state changes just once, at render time.

Cas :slight_smile:

#4

Scene graphs are best suited for organizing things spatially and defining transform hierarchies. When you start throwing in state descriptions and materials, the concept of the scene graph becomes bloated. IMO its much better to separate it, and since its also more programmer friendly to automate the spatial organization for culling you might as well do away with that altogether and focus on specifying material descriptions as conveniently as possible.

#5

You shouldn’t make your own general scengraph. It’s too complex. It’s like building your own compiler or editor. Use an existing one instead, like Aviatrix3D

http://aviatrix3d.j3d.org/index.html

Or JMonkey,

http://www.jmonkeyengine.com/index.php

#6

Or Ardor3D (it works really fine with JOGL):
www.ardor3d.com

#7

To give you some more information, my new visualisation task is to show the occupancy of racks in a small warehouse.
The picture shows a test case where each L-shaped model is one storage unit.
http://img690.imageshack.us/img690/8348/warehouse1.gif

Naturally the geometric data i get from the client software is strongly hierarchical.
(warehouse -> corridor -> corridorside -> rack -> shelf height -> storage unit).
To me a scenegraph seemed like the best way to render this.
@ Roquen:
Which renderingmethod would you suggest instead of a scenegraph?
@ princec:

  1. depending on the frequency of single modifications CopyOnWriteArrayLists might help, thanks for the tip
  2. this was more about the performance influence of using one Nodelist per inner node compared to encoding the whole scenegraph in a single List
    @ lhkbob:
    in the warehouse usecase i found that in most cases 2 subsequent nodes differ mainly in translation and color thats why i inculded these attributes (+ rotation and scaling with a flag since they are rarely used) into the the general object node. As a result my scenegraph now consists only of one camera node and thousands of object nodes.
    @ api suggestions:
    the scenegraph is already coded, it just has performance issues :wink:
    also since my plugin might be sold as part of the companies client i’m not sure about licensing problems…
#8

Okay, your follow-up changes things. (Again all of this is IMHO) Scenegraphs are okay for pure visualization/mock-up purposes, but not so great if there is any simulation. If you need to speed things up, it might help if you posted some timing info.

To answer your question to me: spatial partition (of some kind, or hybrid of multiple kinds). If I were coding up something from scratch to cover your example picture, I’d probably do “cells and portals” as the main database.

#9

I will never understad such advice “dont do it ?” there isn’t and there will never be one scenegraph that do the best job for every possible project… and everything can always be improved

some possible ways depending on your project/target :

  • add some kind of compilation => for some static branches when all childrens wont change you can cache a compiled/precomputed/snapshot version of the wole branches ans its childrens (for example the use of a static native array instead of vector or the collapse of all childrens (like as flattering an image in PSP or modifiers in 3ds) inded many others thing can be “pre-compiled”).
  • an easy/fast to implement improvment can be done in addition of pre-compilation using a surrounding sphere for each node including childrens (inded in case of precompiled/static branches), camera frustrum culling become then very fast as when a sphere is outside the camera frustrum you remove all the branchess and its children from the rendering process. you can also perform an occlusion culling test using that surrounding sphere (will remove every high poly object / caracter hidden behind a door/wall/etc… if you render for example scene wall before object)

those two things are very-generic stuff, but once again there are hundreds of different improvment depending on your need ? very dynamic / lot of change in structure ? indoor only ?

EDIT : after looking at your image it seems that an octree space partitioning may help in this case

#10

After looking at that image, I’d say: bruteforce it!

Rendering this with one VBO in one OpenGL call, would probably be fastest.

#11

It is not true on very low end graphics cards.

#12

Low end graphics cards are surprisingly rare in business situations. As in, you say, it requires this card to work, and don’t come running to us if you don’t use it. Very rarely does a business have a problem spending the £30 to buy a decent graphics card.

Cas :slight_smile:

#13

hehe, in fact I did not really undestood where could be the botlneck in such simple scene with a decent hardware but I did not dare to advice to use bruteforce :slight_smile:

#14

These days you can bruteforce textured and lit 1024x1024 terrains at decent framerates, which means 2 million triangles @ >60fps. I do not advice anybody to bruteforce 1024x1024 terrains, because that’d leave no room for everything else, but looking at that ‘datacenter scene’ I’m fairly sure it’s less than 2 million triangles, not even textured, and probably you don’t even have to light it, using hardcoded color shades.