OpenSG: Traversal of the Graph

What have we learned so far? We know how to create a scenegraph and we can use the simple scene manager to have a fully functional application. In the last chapter we even learned how to setup the whole stuff without the simple scene manager. You might remember that we created a render action (osg::RenderAction) which was passed to the window. The instance of this render action was called during the display function

void display(void)
{
    window->render(renderAction);
}

Building a scenegraph is only useful if you work with it. OpenSG actions are actually tools which can perform various actions on the graph. In most cases the graph is traversed and a function is called when entering a node. There are some predefined actions, like the render action, but you can also create your own of course.

Actions

    RenderAction *ra = RenderAction::create();

    myAction->apply(someNode)

Actions can be applied to any node or to a vector of nodes. In any case the action will be applied to all children as it is recursively called on every child. However, depending on the action that is being executed, not every child may be visited. For example you could define an action that traverses the graph until it encounters a specific node and then ends immediately. The following image illustrates how nodes are visited when applying an action

Assuming that the traversal will not be interrupted for some reason, a traverse starting at node C would visit the nodes C, F and G in that order. If you start the action at the root node, all Nodes will be visited in that order: A, B, C, F, G, D, E, H. When providing a vector of nodes, let's say G and E then the visited nodes would be G, E and H.

Another example: If you start with root node A and node C returns Action::Skip then the processed nodes are A, B, C, D, E, H. Node C itself is processed but not it's children.

Render Action

The render action actually does a lot of important work for you. In the background a draw tree is generated (which will minimize OpenGL state changes), geometry is culled against the view frustum and transparent objects are sorted from back to front to ensure correct rendering of multiple transparencies.

You can turn off view frustum culling via setFrustumCulling() and for debugging purposes you can turn on the rendering of bounding volumes with setVolumeDraw() as well as deactivate the update of the view frustum with setAutoFrustum().

Intersect Action

    Line ray = Line(Pnt3f(5,0,-10), Vec3f(0,-1,0));
    IntersectAction *iAct = IntersectAction::create();
    
    iAct->setLine(ray);
    iAct->apply(someNode);
    
    if (iAct->didHit())
        {
        std::cout << "Hit Point : "<< act->getHitPoint();
    }

We would sent a ray from (5,0,-10) in the opposite direction of the y axis. If we hit something the intersection point will be printed on screen.

Please notice that intersection tests are really expensive. It will be sufficient for object picking and the like, but collision detection for example would require collision models to be fast enough. I participated in a project where we used OpenSG for driving a stereo application. We first used the intersect action every frame and tested against the complete geometry to determine if the user ran into some obstacle. Well, that was not a very good idea, our framerate dropped from more than 30 down to three frames per second. We later had collision wall models with very few polygons. With that we were able to use the intersect action again.

The main reason for the slowdown is that the Geometry Nodes are not optimized for ray intersection, thus if the ray intersects the bounding every triangle of the Geometry needs to be tested, and that means a lot of calculation for every ray. If you need more efficient ray intersection ask the Users list about Genvis.

Traverse Functions

NodePtr checkName(NodePtr n){
    UInt32 children = n->getNChildren();
    
    //make sure a name existes
    if (getName(n))
        //check if it is the name we are looking for
        if (getName(n)== std::string("FACESET_Woman"))
            // We got the node!
            return n;
    
    //check all children
    for (int i = 0; i < children; i++){
        NodePtr r = checkName(n->getChild(i));
        if (r != NullFC)
            // if it is not NullFC it is the node we are looking for
            // so just pass it through
            return r;
    }
    // no children's name matches or there are no more childs
    // so return NullFC, indicating that the node was not found yet
    return NullFC;
}

It would be no big deal to replace the hard coded string with some search string variable, but still this function would not be very flexible or efficent. OpenSG offers some help, if you need to traverse the graph for any reason.

OpenSG is constantly traversing the tree. Each time an image is rendered, the graph is traversed once. You can use the same powerful functionality by using the traverse() function. This function needs a root where to start from and one or two functions which will be called whenever entering or leaving a node. The following simple example will show traversal of a graph by printing either "enter" or "leaving" when entering or leaving a node.

Action::ResultE enter(NodePtr& node)
{
    std::cout << "Enter node : " << node << std::endl;
    
    return Action::Continue;
}

The first line should be obvious, the second line returns Action::Continue, which simply means that the traversal of the graph should be continued. By returning Action::Skip you tell OpenSG to not continue with the current node and thus skipping it and all children, but continuing with all other nodes still left. This is useful if you determine that all the current Node's descendents are not interesting (e.g. they are invisible). Action::Quit finally stops the traversal, no new node is entered. This is primarily useful if you were looking for a specific Node in the graph and found it, to prevent any further search.

Action::ResultE leave(NodePtr& node, Action::ResultE result){
    std::cout << "Leaving node: " << node << "with code: " << result << std::endl;
    
    return result;
}

Well, we now have both functions we need, but we actually still need to call the traverse fucntion. This may look a bit weird...

    traverse(scene, 
        osgTypedFunctionFunctor1CPtrRef<Action::ResultE, NodePtr>(enter), 
        osgTypedFunctionFunctor2CPtrRef<Action::ResultE, NodePtr, Action::ResultE>(leave));

This command would have started the graph traversal. Let's have a closer look at these commands. As mentioned earlier, the traverse function needs a node where to start from, which is the "scene" node in this example. Alternativly you can also provide a std::vector of nodes instead of a single node. Next we have two long parameters. The traverse function needs so-called OpenSG functors, which can be created with osgTypedFunctionFunctorXCPtrRef where X is the number of arguments. So creation rules for the functor creation is like that

    osgTypedFunctionFunctorXCPtrRef<returnType, Argument1, Argument2, ..., ArgumentX>(functionName)

It is also possible to reference a method of some object instead of a function. I will demonstrate that in the tutorial at the end of this chapter.

Anyway, what is the use of all this? Well you might need to traverse the graph more often than you think. If you want to print the number of all triangles for every geometry node for example you could create an "enter" function which checks if that node core is derived from osg::Geometry and if that is the case, calls a function that will count the polygons.

Graph Operators

Graph Operators are not available in OpenSG Version 1.2! If you want to benefit from graph operators you have to use a more current version.

Graph operators can apply complex operations on the graph, with only very little effort (on your side). Usually one or more graph operators are applied after you loaded a model from file. The problem is that a loader needs to be very flexible. Some want highly optimized geometry for high performance, where others might prefer a close as possible representation of the original model with the structure staying untouched. With the help of graph operators you can make sure the result fits your needs.

Often you want to apply more than just one operator. osg::GraphOpSeq stores a sequence of osg::GraphOp which will be applied one after another. Note that the graph is traversed once for every operator you have defined which may slow down loading of bigger files.

It is also possible to specify an exclude list of nodes which will be skipped during traversal. This can be used to keep a number of important nodes intact, while optimizing the rest of the graph.

Depending on your scene, graph operators can have a great impact on the performance of your application, but keep in mind that this is not true in general. For example, the 3D Studio Max VRML exporter is not very good, therefore you can archive great results with graph operators, where as the Cinema 4D exporter is doing a good job and there is not that much to optimize left. However, giving it a try can always be useful.

Graph Operators are very easy to use. They are not derived from field container and can be instantiated as usual c++ objects.

    SplitGraphOp* spo = new SplitGraphOp;
    spo->setMaxPolygons(50);

There are two ways how graph operators can be applied to the scenegraph. You can apply the operator direcly by calling traverse() on a node of your choice, usually the root node.

    spo->traverse(scene);

The most common way is to create a sequence of operators and pass it to the loader. The following example shows a sequence of two operators which are passed to the loader.

    GraphOpSeq *graphOperator = new GraphOpSeq;
    
    //first we verify the geometry
    graphOperator->addGraphOp(new MergeGraphOp);
    graphOperator->addGraphOp(new VerifyGeoGraphOp);
    
    
    someNode = SceneFileHandler::the().read("some_file.wrl", graphOperator);

Merge

Material Merge

This is where the material merge graph operator will help you out. If applied to the graph it will look for identical textures, that will be shared if possible afterwards. If you have a smart exporter or readily optimized data you won't need this operator, in every other case it would be wise to use it. This operator can actually cause no harm to your scenegraph so you can use it in most cases - just to make sure.

Tutorial - Graph Traversal

Again we take 00framework.cpp as a starting point. First we need to add some include files we already know from other tutorials

    #include <OpenSG/OSGSceneFileHandler.h>
    #include <OpenSG/OSGSimpleAttachments.h>

    using namespace std;

At the beginning we are going to load the VRML file mentioned above. This should look a bit familiar to you by now. Paste this block of code into the createScenegraph() function.

    NodePtr n = SceneFileHandler::the().read("data/torus_sphere_cone.wrl");
    
    //we check the result
    if (n != NullFC)
        return n;
    else
    {
        cout << "Loading the specified file was not possible!" << endl;
        return NullFC;
    }
    
    return n;

Let us start with something simple: When the 'p' button is pressed, our application should print a list of the names of every node found in the scenegraph. We first need a functor, which will print the node's name on entering during traversal of the graph.

//This is the function that will be called when a node
//is entered during traversal.
Action::ResultE enter(NodePtr& node)
{   
    if (getName(node))
    {
        cout << getName(node) << endl;
    }
    else
        cout << "No name was set!" << endl;

    return Action::Continue; 
}

Now add a keyboard callback function like you know it from other tutorials. The following code should be executed when the 'p' key is pressed

    cout << endl << endl;
    cout << "Printing all node names";
    cout << "---------------------------------------";
    cout << endl << endl;
            
    // now we invoke the traversal
    traverse(scene, 
                osgTypedFunctionFunctor1CPtrRef
                    <Action::ResultE, NodePtr>(enter));

Now compile and execute the application. After the window appears push 'p' and watch for output in the terminal. If nothing happens, make sure that the window and not the terminal is active. The result should look like this

As you can see there are three nodes, whose name contain the prefix "FACESET_" which we encountered previously, when we were implementing a search for the geometry core of the woman model in section Big Tutorial. Some nodes have no name set at all but three other have exactly the same name as it was provided in the modeling package (torus, sphere and cone).

It seems that the FACESET_* nodes were created automatically when exporting a scene to VRML. Maybe nodes named FACESET_* always contain the geometry cores? We can proof the assumption by implementing another traversal action. Instead of the most enter() function we used above, we now will have a functor that checks if the current node's core is derived from osg::Geometry and if that is true it will print the name of that node. If our assumption is correct we will have only node names that will beginn with FACESET_ . Of course this will only be correct if you have not created your own geometry or loaded some other files.

//This function will test if the core is of type
//geometry and if it is, it will print the node's
//name
Action::ResultE isGeometry(NodePtr& node)
{
    // this tests if the core is derived from geometry
    if (node->getCore()->getType().isDerivedFrom(Geometry::getClassType()))
        if (getName(node))
            cout << "Found a geometry core stored in " << getName(node) << endl;
        else
            cout << "Found a geometry core but node has no name" << endl;
    
    return Action::Continue;
}

Extend the keyboard() function in that way, it will react to the 'g' key and start a traversal using the isGeometry() functor. The code is nearly identical to the other case. After you have finished that, compile and execute the application.

After you have pushed the 'g' key you will know that our assumption was correct! If you have problems compiling it you can have a look at the complete program here : progs/12traversal.cpp

Now either take that file or the one you just created. We are now going to improve our program a bit and use some graph operators. First we extend our program to load files from the command line. This is actually no big deal. In the main() function locate the line where we call createScenegraph() and replace it with

    if (argc > 1)
        scene = createScenegraph(argv[1]);
    else
        scene = createScenegraph("data/brick_quads.wrl");

This either loads a file passed in the command line (i.e. the first parameter), or if none is given, it load's a default scene. Now alter the line that actually loads the file in the createScenegraph() method. The new correct command is

    NodePtr n = SceneFileHandler::the().read(filename);

Before we begin implementing optimizations with graph operators, you have to add new include files

#include <OpenSG/OSGGraphOpSeq.h>
#include <OpenSG/OSGSplitGraphOp.h>
#include <OpenSG/OSGVerifyGeoGraphOp.h>
#include <OpenSG/OSGMergeGraphOp.h>
#include <OpenSG/OSGSharePtrGraphOp.h>

Now we are going to apply a little sequence of graph operators right when loading the file. In the createScenegraph() function add the following code just before the command you edited last.

    // define the Graph Op Sequence here
    GraphOpSeq *graphOperator = new GraphOpSeq;
    
    //first we verify the geometry
    graphOperator->addGraphOp(new VerifyGeoGraphOp);
    //merge geometry and transformations
    graphOperator->addGraphOp(new MergeGraphOp);
    //merge identical field containers
    graphOperator->addGraphOp(new SharePtrGraphOp);
    //verify again
    graphOperator->addGraphOp(new VerifyGeoGraphOp);

now we need to pass the sequence object to the loader. Once again change the line that loads the file

    NodePtr n = SceneFileHandler::the().read(filename, graphOperator);

After loading, the resulting graph will be modified by the graph operator sequence. In this specific case the geometry will first be verified, then the geometry will be optimized by merging reusable parts, as well as applying transformations to the vertices directly, where possible. Next all field containers with identical content are shared and finally the geometry is verified again.

Again, please note, that this does not always result in better graphs! If you try it with the scene from "brick_quads.wrl" you will not notice any significant changes at all.

You can try to load the first example file "torus_sphere_cone.wrl". The system will inform you that five cores where shared. Furthermore if you now push 'p', you can see that there are only four nodes left: a node without name (that has to be the root node) and three futher nodes, we previously have identified as the nodes storing the geometry cores. All other nodes have not survived the optimization - the transformations are gone as they have been computed into the vertex positions. Well, that's 11 nodes have been reduced to 4 nodes, which is more than 50!

As next we want to apply another graph operator manually during runtime. This time we will use the split graph operator. In order to have some feedback we will create another traversal action that counts nodes beforehand. However I mentioned before, that you can use an object instead of a function for traversal. This is especially useful if you need to store data during traversal (like the number of encountered nodes) which could only be stored globally if you would use a function.

// A simple class that counts the number of entered nodes
class counter{
    public:
        //constructor 
        counter(void){
            mCount = 0;
        }
        
        //method that will be called when entering
        //a new node
        Action::ResultE enter(NodePtr& node){
            mCount++;
            return Action::Continue;
        }
        
        UInt16 getCount(void){
            return mCount;
        }
        
        void reset(){
            mCount = 0;
        }
    
    private:
        UInt16 mCount;
};

So what next? We want to split the graph into many small nodes with 50 polygons each when the user presses the 's' key. So edit your keyboard callback function and add the following code

    case 's':
            cout << "Splitting Graph now...";
            
            counter c;
            
            traverse(scene,
                    osgTypedMethodFunctor1ObjPtrCPtrRef
                    <Action::ResultE, counter, NodePtr>(&c, &counter::enter));
                    
            cout << "Number of nodes before splitting: " << c.getCount() << endl;
            
            SplitGraphOp* spo = new SplitGraphOp;
            spo->setMaxPolygons(50);
            spo->traverse(scene);
            delete spo;
            
            cout << "done" << endl;
            
            c.reset();
            
            traverse(scene,
                    osgTypedMethodFunctor1ObjPtrCPtrRef
                    <Action::ResultE, counter, NodePtr>(&c, &counter::enter));
                                        
            cout << "Number of nodes after splitting: " << c.getCount() << endl;
            
        break;

If you have less than 512 MB of memory, you should choose more than 50 polygons as max polygon value - maybe 400 or 1000.

If you have a look at the traverse function call, you will notice that it is quite similar. osgTypedFunctionFunctor1CPtrRef changed to osgTypedMethodFunctor1ObjPtrCPtrRef and additionally you also specifiy the class type that will be used.

Try to rotate the guy. If you have a moderate PC you might notice that the performance is not that great, as there are 60.000 polygons in one node. Memory consumtion lies by about 23 MB. Now split the graph up by pushing 's' - this may take some time. Memory consumption goes up to about 307 MB, but performance increases significantly as now the view frustum culling can work better. The number of nodes increases from 2 to 1190 nodes if you used 50 polygons as maximum!

Of course, this one is just for demonstartion - I would not recommend this for usage in real live...

Hit it

First remove the code that created the graph operator sequence during createScenegraph(). Do not forget to adjust the load command by removing the operator sequence parameter. We do not want these optimizations for this example, because the individual boxes would be merged into a single one. You see - as we want to preserve the structure this time, graph optimizers are not always a solution to all problems.

void mouse(int button, int state, int x, int y)
{
    if (!state)
        mgr->mouseButtonRelease(button, x, y);
    else{
        // this is the case when the mouse button 
        // is released
        
        //just to inform the simple scene manager
        mgr->mouseButtonPress(button, x, y);

        //calculates a ray from the camera trough
        //the clicked pixel
        Line ray = mgr->calcViewRay(x, y);
    
        IntersectAction *iAct = IntersectAction::create();
    
        iAct->setLine(ray);
        iAct->apply(scene);
    
        //see if anything was hit
        if (iAct->didHit()){
            // get the hit point
            Pnt3f p = iAct->getHitPoint();
        
            cout << "Hit point : " << p[0] << " " << p[1] << " " << p[2] << endl;
            
            //and the node that was hit
            NodePtr n = iAct->getHitObject();

            //remove the node from the scene
            NodePtr parent = n->getParent();
            beginEditCP(parent, Node::ChildrenFieldMask);
                parent->subChild(n);
            endEditCP(parent, Node::ChildrenFieldMask);
        }
    }
        
    glutPostRedisplay();
}

and then compile and execute the application. You can now click away boxes... with some more features this one could evolve into a game! ;) You see, using intersect actions is not difficult at all.