wiki:Tutorial/OpenSG1/Traversal
close Warning:

Previous Chapter: Windows and Viewports

Tutorial Overview

Next Chapter: Multithreading


Traversal

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

#!cpp

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

osg::Action objects are created just like nodes and cores via ::create() but as these are not derived from osg::FieldContainer simple pointers will do. A render action is therefore simply created by

#!cpp

    RenderAction *ra = RenderAction::create();

Any action can be executed by calling a single command

#!cpp

    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

Sample graph

Assuming that the traversal will not be interrupted for some reason, it is starting at node C and visits 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

This action was used by the simple scene manager right from the beginning. Needless to say that its primary task is to transform the scene graph into a two dimensional image that can be displayed on the screen. If you do not use the simple scene manager you need to tell the window of your application what render action to use. If you have not something really fancy in mind, the osg::RenderAction is all you need to do the job.

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

osg::IntersectAction might be very useful for some problems, but it may also cause some new performance problems, as ray intersection tests are not that optimized right now. This action enables you to send a ray from a position into a direction of your choice. Afterwards you can gain detailed information about the first object that was hit. Here is a little example on how you would typically use the intersect action.

#!cpp

    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 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 osg::Geometry is not optimized for ray intersection, but for rendering speed, thus if the ray intersects the bounding volume 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

Traversal of a graph is very important and used by many important features like the two actions I presented above. Previously we could have used such an action: Please remember the Big Tutorial from Chapter Node cores, where we tried to find a node with a specific name in the graph. We implemented a little helper function that started at the root node, checked if the name matches the search string (which was hardcoded at that point) and if not, recursivly calling that function with all children. Here is the code of that function again

#!cpp

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.

First we need a function that will be called when we enter a node

#!cpp

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.

Here is the function that will be called when leaving a node

#!cpp

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...

#!cpp

    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

#!cpp

    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

Attention:

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.

#!cpp

    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.

#!cpp

    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.

#!cpp

    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);

Here is an overview of the predefined graph operators

Merge

osg::MergeGraphOp tries to combine geometry that has the same attributes. Remember the section about Indexing? This operator will change some indices and deletes the attribute values that become obsolete. In addition to that the graph will be flattened as transformations are applied to the vertices thus there is only one transformation per vertex. This operator is smart enough to handle LODs correctly, so it should work with any model.

Material Merge

This one is extremly useful under certain circumstances. I had the following situation during a recent project: Someone modeled a few different buildings and someone else build a little city from these with copy and paste. The buildings were textured, of course. Well, we exported that to VRML with Studio Max and after loading with OpenSG our RAM was all but gone... 1 GB of memory wasted. What happened? The texture that was assigned to the buildings was loaded once for each object and was not reused properly... and we had lots of buildings.

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.

Prune

Very small objects (relative to the whole scene) are automatically deleted by osg::PruneGraphOp. Of course, it is possible that you may loose important data, but on the other side if you have a file created by some architect you might not be happy about the scews he modeled throughout the skyscaper object. The prune operator might be able to remove these small objects automatically. However, in most cases you have to check if the result is good for your needs.

Stripe

This one simply stripes geometry. The result is the same as if you were using QUAD_STRIP or TRIANGLE_STRIP in OpenGL. Since striped geometry can usually be rendered much faster this can make a big difference especially for very complex models with large numbers of polygons.

SharePtr

The osg::SharePtrGraphOp tries to share field containers which are identical. Geometry exported from a modelling package may often contain redundant information. The share pointer operator helps you to delete the field containers that are useless.

Verify

Simply checks if the geometries are consitent and outputs a warning if they're not.

Split Graph Operator

With this operator you can split a scenegraph into several parts which will contain a predefined number of polygons. This is very useful if you, for example, are loading a single very large mesh. Usually this will not be very performant as this object is stored in one single node and the view frustum culling can not

work efficiently. By splitting it up into several nodes you can improve performance remarkably. But be careful, splitting up a 100.000 polygon geometry core into single nodes with 50 polygons each won't be speedy at all... As a rule of thumb I'd recommend splitting into nodes with about 1000 polygons each.

Tutorial - Graph Traversal

In this tutorial we are going to load a VRML file from disk (you already know that from Tutorial - loading and saving) containing a simple scene with just three objects - a torus, a sphere and a cone. This file was created using a 3D modeling package. All three objects are named after what they are. No additional features, like textures or geometry modifiers from a modeling package were used. I will demonstrate some different approaches on how to use traverse() and osg::GraphOps

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

#!cpp

#include <OpenSG/OSGSceneFileHandler.h>

#include <OpenSG/OSGSimpleAttachments.h>

You also should activate the standard namespace.

#!cpp

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.

#!cpp

    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.

#!cpp

//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

#!cpp

    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

Terminal results

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 others 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 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.

#!cpp

//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

#!cpp

    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

#!cpp

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

Give it a try by calling the program by

    ./12traversel2 data/beethoven.wrl

assuming that you called your file that way and that it is located in the "progs" folder.

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

#!cpp

#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.

#!cpp

    // 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

#!cpp

    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%!

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.

First we need the class that will store the number of nodes we found so far.

#!cpp

// 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

#!cpp

    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;

Important:

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.

After compiling execute the application with

./12traversal3 data/beethoven.wrl

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 is at 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...

The code so far can be found in progs/12traversal2.cpp

Hit it

Finally we add a last feature for this tutorial. We are going to add the possibility to click into the window to select objects which will then be deleted.

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.

Anyway, replace the mouse() function with the following code

#!cpp

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.


Previous Chapter: Windows and Viewports

Tutorial Overview

Next Chapter: Multithreading

Last modified 7 years ago Last modified on 01/17/10 01:11:44

Attachments (2)

Download all attachments as: .zip