Page 1 of 1

Statically typed scenegraph based on recursive Boost.Variant

PostPosted: Sat Jun 19, 2010 10:18 pm
by FipS
I've been playing with the idea of having statically typed Scenegraph for some time. Wouldn't it be great to have no common base class, no virtual calls, efficient / no need for RTTI, I could go on :). I've tried a few different approached to the problem but I especially like the one I'm going to show you here (see [2] for my original inspiration).

It's based on Boost.Variant [1]. The key thing here is that we can use the Variant to form recursive tree-like structures, which is exactly what we need for composing a Scenegraph. So we are able to easily define internal and leaf nodes of the Scenegraph. As a bonus we can take advantage of the value semantics of the Variant.

Finaly, we need a way of visiting the Scenegraph. We use boost::static_visitor to do this. Note that the CRTP pattern [3] is involved to retain common implementation it the visitor base class. So we are able to easily add new visitors operating only over a specific set of node types.

Here's a fully working example showing the concept:
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>

#include <boost/variant.hpp>

struct Model_t; // leaf node
struct Sound_t; // leaf node
struct Group_t; // internal node

typedef boost::variant<
 Model_t,
 Sound_t,
 boost::recursive_wrapper<Group_t>
> Node_t;

struct Model_t
{
    void Draw() const { std::cout << "Model_t::Draw()\n"; }
};

struct Sound_t
{
    void Play() const { std::cout << "Sound_t::Play()\n"; }
};

struct Group_t
{
    void Attach(const Node_t &Kid) { m_Kids.push_back(Kid); }
   
    template <typename VisT>
    void apply_visitor(const VisT &Vis) const
    {
        std::for_each(
         m_Kids.begin(), m_Kids.end(),
         boost::apply_visitor(Vis)
        );
    }
   
 private:
 
    std::vector<Node_t> m_Kids;
};

template <typename VisT>
struct SceneVisitor_T : public boost::static_visitor<void>
{
    template <typename ElemT> // generic empty handler
    void operator()(const ElemT &) const {}
   
    void operator()(const Group_t &Group) const
    {
        Group.apply_visitor(*static_cast<const VisT *>(this));
    }
};

struct RenderVisitor_t : public SceneVisitor_T<RenderVisitor_t> // CRTP
{
    typedef SceneVisitor_T<RenderVisitor_t> Base_t;
    using Base_t::operator(); // prevent operator() hiding

    void operator()(const Model_t &Model) const
    {
        Model.Draw();
    }
};

struct AudioVisitor_t : public SceneVisitor_T<AudioVisitor_t> // CRTP
{
    typedef SceneVisitor_T<AudioVisitor_t> Base_t;
    using Base_t::operator(); // prevent operator() hiding

    void operator()(const Sound_t &Sound) const
    {
        Sound.Play();
    }
};

int main()
{
    Group_t Group;
    Group.Attach(Model_t());
    Group.Attach(Sound_t());
   
    Group_t Root;
    Root.Attach(Model_t());
    Root.Attach(Sound_t());
    Root.Attach(Group);
       
    boost::apply_visitor(RenderVisitor_t(), Root);
    boost::apply_visitor(AudioVisitor_t(), Root);

    return 0;
}

// console output:
// Model_t::Draw()
// Model_t::Draw()
// Sound_t::Play()
// Sound_t::Play()


References:
[1] Boost.Variant by Eric Friedman & Itay Maman (boost.org)
[2] Scene Graph Resources by snk_kid (gamedev.net)
[3] Curiously Recurring Template Pattern (wikipedia.org)
[4] High Performance Heterogeneous Container by Alexandre Courpron (codeproject.com)

FipS