Ambassador

In the past, I hated nearly everything in std namespace. Today this sounds ridiculous and childish. I have had groundless reasons to believe so and I think I have debunked (almost) all those. One, however, sometimes make me think... use of STL function function adapters and mem_fun for algorithms.

I have started using OpenSceneGraph some time ago and it didn't take too much time to realize it's a very powerful "thing" (I think it's more than a scene graph and that could be the problem). It also didn't take too much time to realize it has some problems and limitations, much like any other software, as well. But overall, OpenSceneGraph is, in my opinion, a serious project. I am also moderator in OpenSceneGraph forum.

So, I thought about "what about a scene graph that is not as powerful as OpenSceneGraph, but can run on multiple backends/graphics APIs (i.e. not OpenGL only), which also is more scalable (parallel?) than OpenSceneGraph is today". This is a tough job for me, primarily because computer graphics isn't really my expertise. Therefore, I had to read more OpenGL code and even more DirectX code. ...And I did exactly that! I have 4 DirectX books now (because I already have some OpenGL experience) and 2 math books; more on the way!

For me, scene graph is a scene graph; it does not render anything at all. It's a DAG (Directed Acyclic Graph), representing the structure of the entire scene hierarchically and enables traversals to operate on nodes, period. Rendering is done by the back-end (e.g. D3DXRenderBackend, OpenGLRenderBackend, SoftwareRenderBackend), each has its own traversal "tasks" (as in Intel Threading Building Blocks tasks), traversing scene graph and ending up with a drawable tree. Some of those traversals are running in parallel. I also have read-only and read-write traversals. To store and handle events, one may need to derive from EventHandler class, which will subscribe event handler for some event categories (e.g. InputEventCategory, or MouseInputEventCategory to be more specific, or FrameEventCategory).

Back to our story... When I store objects in std::vector, I use a reference counting intrusive smart pointer class as parameter to std::vector template, and privately derive from an ObjectContainer<T> then expose some methods I like. But when I want to traverse, I don't want to deal with reference counting, because I have to traverse fast. I also didn't want to write for loops myself, so I used std::for_each. It took 2-3 hours to write one single, small function adapter class that converts pointer-to-T from a reference counted intrusive smart pointer of T. Here is how everything looks like, briefly...

template<typename T>
class ObjectContainer<T>
{
  std::vector<T> m_arItems;
public:
  void AddChild(T& t) throw(std::bad_alloc);
  void AddChild(T& t) throw(std::bad_alloc);
  void AddChild(typename T::pointer val) throw(std::bad_alloc);
  void RemoveChild(T& t) throw(std::out_of_range);
  void RemoveChild(typename T::pointer p) throw(std::out_of_range);
  T& GetChild(size_t nIndex) throw() // crashes, since it can't throw;
  const T& GetChild(size_t nIndex) const throw(); // crashes, since it can't throw
  const T& GetChildSafe(size_t nIndex) const throw(std::out_of_range);
...
};
typedef RefObj<NodeState> sp_nodestate; // state for a node.

class RenderPass : ObjectContainer<sp_nodestate> // render pass, including all states, for a node
{
...
};
typedef RefObj<RenderPass> sp_renderpass;
typedef std::vector<sp_renderpass> RenderPassCollection;
class Node
{
public:
  const RenderPassCollection& GetRenderPasses() const;
};
typedef RefObj<Node> sp_node;
class Group : public Node, ObjectContainer<sp_node>
...
typedef RefObj<Group> sp_node;
...
void D3DXTranslator::TranslateRenderPass(const Node* pNode)
{
  std::for_each(pNode->GetRenderPassCollection().begin(), 
      pNode->GetRenderPassCollection().end(), now_what);
}

now_what part was longest part.
I need a function adapter that will adapt a "const sp_renderpass& to a const RenderPass* on a non-const this pointer" (member function shouldn't be const qualified). I wrote something that didn't compile for 3-4 times. Why did it take that long to figure out what's wrong? Compiler error message... Compiler spits out an error message that is way too long to read and usually contains very little information, as far as such complicated templates are concerned. Note that type that goes as template argument is also a template class. At the end, function adapter looks something like:

template<typename R, typename T, typename A>
class FuncAdapter
{
  R(T::*m_pfunc)(const A*);
  T* m_pThis;
public:
  explicit FuncAdapter(T* pThis, R(T::*p)(const A*) : m_pThis(pThis), m_pFunc(p) { }
  R operator()(const RefObj<A>& r) const { return (m_pThis->*m_pFunc)(r.get()); }
};

(Also, there is a const version of this which has a const T* instead of T*).
The problem with this was one character; star (*) after const A* in member function type declaration. It took 2-3 hours to find an answer to the question of "what did I miss here?"; a star. Because what compiler spit out was pushing me to operator(); it said "can't convert from const RefObj to const RefObj&". This made me think about const-ness, copy constructor of RefObj and everything else but that star. Then I opened notepad and started to write down which type is what and what does this dude expect. It didn't take too long to figure out a star was missing there. Well, it took 2 hours to start notepad!

With the assistance of this adapter, I can iterate through all RenderPasses by saving some CPU cycles. I can't (safely) escape from calling get() method, but that's fine. Then, for each of those render passes, I iterate through all NodeStates and each node state gets translated into graphics API's render state (e.g. alpha blending will be translated to GL_BLEND for OpenGL and D3DRS_ALPHATESTENABLE, and its related render states, etc.). Hence:

NodeStateTranslator* D3DXRenderPassTranslator::TranslateRenderPass(const RenderPass* pPass) const
{
  std::for_each(pPass->begin(), pPass->end(), mem_fun_refobj_arg_binder(pNodeStateTranslator, &D3DXNodeStateTranslator::TranslateNodeState));
}

bool D3DXNodeStateTranslator::TranslateNodeState(const NodeState* pState) const
{
  // translate my scene graph's node state into API's renderstate.
}

Organizing where to and where not to modify reference count improved performance. Because tree traversal could scale very good on multicore, I consider using a tbb:arallel_for-like construct instead in some cases. I should instrument performance before and after modifying code to have empirical results. I also make multiple traversals to organize and optimize the scene graph. After analysis, I create a NodePath - a linked list of nodes to visit - and that acts like the final tree to render, after being processed multiple times. I don't know whether this is a good idea, I am just experimenting (since it isn't my expertise). This NodePath is passed to render traversal, which walks through the graph and just performs all renderstate change operations, transforms and drawing and shader stuff, etc.

One of my developers said "it takes longer to write function adapters or functors instead of using regular for loops" and I think he is almost right, particularly when it comes to complicated types. Boost::bind is widely used, but I think it took shorter for me to craft my own adapter instead of using Boost+std constructs. While writing this function adapter, I wrote couple of more to enable calling member functions of a RefObj<T> (over pointer-to-T) and similar things. This has again shown that finding correct combination of std constructs to pass STL algorithms is difficult.

Compilers are like women when it comes to express wrongdoings of other party, I think. If I make an analogy; women don't mean what they say, but they imply something else is not right. It means "something else" is wrong but she complains about something utterly different. It's like; "you didn't put dishes into dishwasher" in fact means "it's Friday evening but we are home, why didn't we go out?" - although, you actually *do* place dirty dishes into dishwasher every time but just wanted to drink some water before doing so in that Friday evening. It's all about experience and knowing your partner!