static poly-morphism for multi-platform api

Suppose if we are developing games for multiple platforms with the same code base, often we need to use some amount of poly-morphism to capture the platform-generic nature of components. Let us say that we are developing for the PC and PS2 platform. It is quite natural for us to have a base class called Texture, and derived classes called PCTexture and PS2Texture. The derived classes would contain the platform specific implementation of the Texture component. But in a single build configuration, we would be having only one kind of these derived classes. If the build configuration is PS2_Debug or PS2_Release, then the compiled code would not contain any instance of the PCTexture class. In fact, at compile time, we make the decision of which of the derived class is going to be used. So, the kind of runtime poly-morphism or dynamic poly-morphism using base-derived classes and v-tables is not a necessity.

This is a simple technique to express the same kind of polymorphic behavior of platform abstraction, using static poly-morphism.

An illustrative example can be downloaded here.
Here is another viewable version of the code.

dynamic poly-morphism

The following code shows an implementation of the use of dynamic poly-morphism.

  //This is widget.h

#if defined(PC_PLATFORM)
#define KGPLATFORM_PC  1
#define KGPLATFORM_PS2 0
#elif defined(PS2_PLATFORM)
#define KGPLATFORM_PC  0
#define KGPLATFORM_PS2 1
#endif

  class Widget
  {
    public:
    Widget();
    virtual ~Widget();
    void CommonMethod();
    virtual void PlatformSpecificMethod()=0;
  };
  //This is widget.cpp
  //Which holds the implementation of
 //non-virtual methods of the base class.

  Widget::Widget()
  {
     //platform-generic widget implementation
  }

  Widget:~Widget()
 {
    //platform-generic widget implementation
 }

  void Widget::CommonMethod()
 {
   //platform generic implementation of common method
 }

Now the platform specific implementation for the PC platform would be

  //This is pc_widget.h
  class PCWidget :public Widget
  {
    public:
    PCWidget();
    ~PCWidget();
    void PlatformSpecificMethod();
  };
  //This is pc_widget.cpp
  PCWidget:: PCWidget()
 {
   //platform specific contrcuctor
 }
   PCWidget::~PCWidget()
 {
  //platform specific destructor
 }
  void PCWidget:: PlatformSpecificMethod()
 {
  //platform specific implementation
 }

The main file that would be calling widget methods would be,

//This is main.cpp or some .cpp file that uses widget

#include "widget.h"
#if KGPLATFORM_PC
#include "pc_widget.h"
#elif KGPLATFORM_PS2
#include "ps2_widget.h"
#endif
int main( int argc, char **argv)
{
   Widget *pw = NULL;
#if KGPLATFORM_PC
 pw = new PCWidget();
#elif KGPLATFORM_PS2
 pw = new  PS2Widget();
#endif

  pw->CommonMethod();
  pw->PlatformSpecificMethod();

  delete pw;
  return 0;
}
static poly-morphism

Now let us implement the same functionality using static poly-morphism.

//this is widget.h
#if defined(PC_PLATFORM)
#define KGPLATFORM_PC  1
#define KGPLATFORM_PS2 0
#elif defined(PS2_PLATFORM)
#define KGPLATFORM_PC  0
#define KGPLATFORM_PS2 1
#endif

   template< int iPlat>
   class Widget
   {
      public:
        Widget();
	~Widget();
	void CommonMethod()
       {
	 //platform generic method
       }
	void PlatformSpecificMethod();
   };

And the platform specific implementation for PC would be

  //this is  pcWidget.cpp
   template<> Widget<KGPLATFORM_PC>::Widget()
  {
    // platform specific implementation of Widget
  }

   template<> Widget<KGPLATFORM_PC>::~Widget();
  {
    //platform specific implementatin of ~Widget
  }

  template<> void Widget<KGPLATFORM_PC>::
PlatformSpecificMethod()
  {
	 //platform specific method
  }

The widget methods can be called as follows.

#include "widget.h"

int main( int argc, char **argv)
{
   //Always the current platform to which the
   //code has ben compiled for will have the
   //template parameter 1
   Widget<1> *pw = new Widget<1>();
   pw->CommonMethod();
   pw->PlatformSpecificMethod();
   delete pw;

   return 0;
}

This is much simpler and cleaner and more efficient too, since we are getting rid of runtime dispatching using v-tables.

The code can be seen here.

issues
  • code bloat: One of the problems with using templates in c++ language is that upon compiling, each template instantiation, tends to generate its own copy of the code. However this is not an issue here, since we don’t instantiate anything other than the code for the current platform for each build configuration. Eg: PS2_Debug configuration, when compiled wont be having any Widget<KGPLATFORM_PC> instantiations.
  • Readability: Templates often result in unreadable code. But in this case, we could use typedef for easy readable synonyms which doesnt have the template construct. typedef Widget<1> CurrentWidget
  • Link issues involving compilers: Although C++ standard doesn’t have any such requirement, some compilers require that,
    bodies of template functions or member functions must be in the header file. Otherwise the translation units (.cpp files) using the template instantiations, wont find them and cause link errors. In this case, any such generic code (Eg: Widget::CommonMethod), should indeed be completely defined in the header file. But at least for visual studio compilers, the specialization, which is were the platform specific code resides, can be defined in the .cpp files.

  • Tool Build Configurations: In game development, usually the runtime engine have platform specific build configurations (Eg: PS2_Debug) and for asset building and authoring purposes the tools are built with a different configuration, which would be mostly equivalent to PC_Debug or PC_Release. For such configurations, there maybe a need where, all of the different platform specific instantiations may occur in the same configuration. Imagine a texture utility tool, which based upon a runtime parameter makes either PS2TExture or PCTexture in runtime. We suggest using enumeration template parameters for a tool build configuration and using the platform specific instantiations, based on that.

    #if defined(TOOL_BUILD)
    #define KGPLATFORM_PC    1
    #define KGPLATFORM_PS2   2
    #define KGPLATFORM_X360 3
    #define KGPLATFORM_PSP  4
    #endif
    

Posted in c++, game development | Tagged , , , , , | Leave a comment

old and miscellaneous software

This is a collection of assorted software which I had written way back in 2003. Please note that these are 5 years old, so they may have lost some topical value now.

maya manipulator plugin

David Gould’s Complete Maya Programming , provided some insights into how to make a manipluator plugin. Here is one of my attempts.
Please find the code here, that should work for Maya8.5.

  1. After you compile the code, please load in the plugin kgManip.mll.
  2. Source the mel script kgGenerateSlabs.mel.
  3. Run ‘kgGenerateSlabs()’ in the script window. This should create a grid of slabs and kgLocators
    on top of the slabs.
  4. Select any kgLocator
  5. Modify/Transformation Tools/Show Maniplulator Tools. THis makes the corresponding manipulator visible. Trypulling the manipulator. This changes the slab height.

Environment mapping using renderman

I created the following maya scene , using NURBS modeling in Maya. For aligning them on the floor, I dropped 10 or so vases from different heights,
and let them bounce and settle on the ground, utilizing a gravity field.
I had used the u-v texture editor to texture map the sky-dome using the following spherical texture map sph_sky which I found in the web. I used the maya-rib exporter that came with my Maya Unlimited 4.5, and since it didnt export texture coordinates, I wrote a mel
script to export a selected geometry and texture coordinate as a rib file.
Next I had to generate the environment maps from the scene, so that they can be used in the environment map shaders for the balls. For this I created this mel script . With these useful mel scripts, I could create the rib files 1, and
2 . As I said before, I used the standard environment mapping shader which was already available. Here is the result.shiny_balls_final

Two things that I have used for this project have since then been discontinued.

  • BMRT renderer for renderman
  • Rib exporter, bundled with Maya 4.5

Ambient Occlusion Shader for Renderman

Here is an ambient occlusion shader for renderman. I have used stratified sampling of the hemisphere surrounding a point to get the ambient occlusion value. Here amb_occis the result of ambient occlusion. Here directional_lightingis the result of lighting the same scene with directional lighting. Here is the composited image.composited_amb_occ_dirlight

Shader evaluation using python script

This is a small set of python scripts that renders a rib file multiple times, eachtime with different shader parameters. The scripts are

First, edit the shaderParamDict in the script shaderStat.py to specify the maximum and minimum values, of the shader parameters to be tested, and a way to iterate them. These are parameters that you can specify in a declarative manner.

Then do

shaderStat.py <input rib file name> <shader name>
<sub sequence of shader parameter names that need be verified>

I have used the following python features in this script.

  • currying
  • OO design
  • iterators, generators
  • dynamic changing of the functions of a module

Here are some resulting images for a simple noise shader
on a simple vase scene.
shader_stat_result

Posted in Maya SDK, Rendering | Tagged , , , , , | Leave a comment

stl wrapper for maya container classes

In the Maya SDK array container classes which are

  • MIntArray
  • MFloatArray
  • MDoubleArray
  • MVectorArray
  • MPointArray
  • MFloatPointArray
  • MFloatVectorArray
  • MCallbackIdArray
  • MAttributeSpecArray
  • MColorArray
  • MDagPathArray
  • MMatrixArray
  • MRenderLineArray
  • MTimeArray
  • MTrimBoundaryArray
  • MUint64Array

has got an entirely different interface compared to the stl conatiner classes. They dont expose any iterator interface. Consequently we cannot use the data contained in them in stl or generic algorithms.

So we have come up with a templatized wrapper class MArray_stl. A wrapper class for MFloatVectorArray would be defined as

typedef kg::MArray_stl< float, MFloatVector, MFloatVectorArray > MArray_stl_fv;

The code can be found here which is tested to work for Maya8.5.

Since the container classes that we wrap are not light weight classes and carry heavy data, the wrapper class just maintains a pointer to the allready constructed maya container class. For example an instance of MArray_stl_fv would maintain a pointer to the MFloatVectorAray that it is pointing to.


MFloatVectorArray fa;
//populate this float vector array and use it for something.
typedef typename kg::MArray_stl kgWrapper;
kgWrapper kg_fa( fa );
//do some generic programming code with kg_fa

Here are the differences of the MArray_stl class compared with std::vector.

  • The only constructors to the wrapper class include a copy constructor, and a constructor that accepts a reference to the maya container class. We don’t allow a default constructor for MArray_stl, since it mean that the wrapper class MArray_stl would have to carry a NULL pointer to the corresponding container class. If it carries a NULL pointer, then what would begin and end iterators be?
  • since Maya container classes doesn’t expose any reserve functionality, the reserve function of the wrapper class doesn’t do anything. Also the capacity function just returns the length of the container.
  • The allocator member variable doesn’t perform any functionality and is a dummy value.
  • Also, use the copy constructor and assignment operator with caution, the use of which leads to two wrappers pointing to the same wrapee.

The core header file where this is referenced can be found at here

Posted in c++, Maya SDK | Tagged , , , , , , | Leave a comment

A generic DAG walk algorithm

This is an example of a simple walk through a dag data structure, written in the paradigm of generic programming. Since a tree is always a dag, this can be easily applied to a tree walk, with or without further simplification.

You can access this as a downloadable version here. The core generic dag walk header file is here.

Introduction

The contribution of this implementation here is two unrelated functionalities.

  • Using generic programming, split data structure and algorithm, there by promoting code re-use
  • Expose the api to preserve user defined stackable information during the walk, through program stack and recursion

We encounter these data structures in multiple occasions in our projects. In projects related to games programming, examples of tree traversal can be, traversing a bounding volume hierarchy tree of a polygon soup, or, traversing the bone hierarchy of a character. An example of a DAG traversal would be, traversing the dependency DAG of resources. When we write code for each of these cases of traversals, we usually succumb to using a separate pieces of code. This is because, the data structures corresponding to the bounding hierarchy traversal is not exactly the same as the data structures for the traversal of animation hierarchy.

One might be tempted to use object oriented programming here, and make base and derived classes, so that generic code can be hoisted to the base class. But sadly OOP, demands unrelated classes to be put into hierarchies, just for the sake of code re-use.

Generic programming doesn’t demand such hierarchies. Generic programming aims to bring re-usabilty by splitting the algorithm and the data structure. The traditional way to implement a generic tree walk or dag walk is through an iterator. But such an implementation, necessitates the iterator class to maintain a stack of where it was, so that it can find the next node to visit, which is kind of unweildy. Our implementation doesnt need an explicit stack of remembering where it is, for the purpose of traversing.

The generic dag_walk algorithm, takes a dag Node class and a Walk class as template arguments.

Eventhough our algorithm doesnt need a stack to keep track of where the current position is, for utility purposes, we expose the abilty to preserve stackable information in the program stack. Many times when you walk a tree or dag, you often feel the necessity to maintain a stack for storing Walk related data. For eg: suppose if you are traversing a scene graph, you may need to store the cumulative transformation matrix. This implementation of the dag_walk, in adition to splitting the algorithm and data structure, allows the walk-implementer to designate an explicit stack_type and a stack variable. The dag walk is done in a recursive way, which means that the program stack can be used to store the stack variable designated by the Walk class.

User’s point of view

  • The user has to supply a dag Node class and a Walk class as template arguments.
  • Additionally the user has to specialize a node_traits struct and walk_traits struct with the Node and Walk classes that he is supplying.

The folowing requirements need be met for the DAG Node class.

Absolute requirements are requirements necessary for the dag_walk to compile.
Functional requirements are requirements necessary for the dag_walk to function.

Absolute requirements of Node class:

  • None

Functional Requirements of the Node class:

  • The Node should have the provision of setting and unsetting a visit flag, which signifies whether the Node has already been visited or not.
  • The requirement can be relaxed, if we anticipate only tree traversals on a dag (ie visiting many times a Node with multiple parents) , or if the dag is guaranteed to be a tree.

Here is an example for a typical user supplied Node

  struct Node {
      Node( int data):_data(data),_visited(false){}
      int _data;
      list< Node *> _children;
      bool _visited;
  };

For the second template argument, the Walk class embodies the work done on the Node. Often the Node class is a rigid, predetermined class supplied by a thrid party, where as the second template argument, the Walk class is a glue class written by the person who uses the Node class. The Walk class must meet the following requirements.

Absolute rquirements of the Walk class:

  • The Walk class must define a stack_type, which should be copy_constructible and assignable.
  • The Walk class should have a member variable of the type stack_type.

If the walk doesnt need to use stackable information, then a dummy stack_type, and a dummy stack_type variable should be defined.

Functional requirements of the Walk class:

  • The Walk class should store the stackable information during the dag traversal in the stack variable.Eg: If the dag was a scene graph, the stack_type of the Walk could contain the current cumulative matrix, at each Node. This trick, enables us to use the program stack to store the stack_type variable while we do recursive traversal of the DAG. Even though the existance of the stack_type and the stack_tpe variable are a compilation necessity, if we dont need them, you can just use dummy values here.
  • The Walk class should have a pre( Node *) and a post (Node *) function which does the main work on the Node, before and after traversing the children of the Node.

Here is an example of the Walk data structure, which prints the dag depth at each Node.

struct Walk {
  Walk():_level(0){}
  typedef int stack_type;
  stack_type _level;
  stack_type & get_stack() { return _level;}
  const stack_type & get_stack() const { return _level;}
  void print( Node * pNode ) {
      cout << pNode->_data << endl;             }
  bool pre( Node * p){
      inc_level();
      print(p);
      return true;
 }
 bool post( Node *) {
      dec_level();
      return true;
 }
 void inc_level() {
      ++_level;
 }
 void dec_level() {
      --_level;
 }
}; 

We have defined the following return values for the algorithm to return.

  typedef enum { eOK, ePrune, eStop, eError } walk_result;

In order to facilitate generic access of the Node and Walk classes, one should specialize the node_traits and walk_traits structs with the Node and the Walk classes.

The node_traits struct which takes the Node as a template parameter should define

  • the set and get functions to access the visit flag of the Node
  • get the begin and end iterators of the container that hold references to the children of a Node. ( If the child container of the Node deosnt have an iterator class,
    one should define one )

Here is a specialization of the node_traits struct.

template < >
struct node_traits < Node > {
  typedef Node N;

  //get the visit tag from the node
  static bool get_visit_tag(const N * pNode ) { return pNode->_visited;}
  //set the visit flag
  static void set_visit_tag( N *pNode, bool b ) { pNode->_visited= b; }

  //how the children of the nodes are defined
  typedef list<Node*> node_container;
  typedef list::iterator node_iterator;
  typedef list::const_iterator node_const_iterator;

  //get the begin and end iterators for the children
  static node_iterator get_node_container_begin( N *pNode ) { return pNode->_children.begin();}
  static node_const_iterator get_node_container_begin(const  N *pNode ) { return pNode->_children.begin();}
  static node_iterator get_node_container_end( N *pNode ) { return pNode->_children.end();}
  static node_const_iterator get_node_container_end(const N *pNode ) { return pNode->_children.end();}

};

The walk_traits class, which takes both the Node and the Walk class as template arguments should

define

  • whether multiple visits to the Node are allowed (ie: it can behave like a tree or is it
    strictly a dag)
  • call the appropriate delegataion codes in the Walk class for the pre and post calls
  • access functions for get-ing and set-ing the current stack

template < >
struct walk_traits<> : public walk_traits_base {
  typedef Walk W;
  typedef Node N;
  typedef W::stack_type stack_type;

  //does this walk allows multiple visits for
  //the dag node. generally during a dag walk, the nodes
  // visisted once are not visited again
  static const bool is_multiple_visits_allowed = false;

  //main operation that need be performed on the node
  //This is called in dag_walk, for each node,
  //before we recurse into the dscendents
  static walk_result pre(  N *pNode, W & w )
      { return (w.pre( pNode )) ? eOK : eStop; }

  //get the curent stack variable of W
  static stack_type & get_stack( W & w){ return w.get_stack(); }
  static const stack_type &get_stack( const W & w) { return w.get_stack();}

  //set the curent stack on W
  static void set_stack( W &w, stack_type &s ){ w._level = s; }

  //main operatrion that will be called after visiting the descendants
  //this function is called after visiting the children
  static walk_result post( N * pNode, W &w, const walk_result &res )
      { return (w.post( pNode) ) ?  eOk : eStop;}
};

Core algorithm

Finally here is the data structure indpendent algorithm code for dag_walk.

/**
*    Generic dag_walk procedure
*
*   - do the pre operation on the node
*   - visit the children and call dag_walk recursively
*   - restore the stack variable after each child visit.
*   - do the post operation on the node
*   @param pNode[in, out] pointer to node.
*          Note that pNode is a not a const pointer and is mutable
*
*   @param w [in, out] the walk operation on the node
*   @return walk_result
**/

template <typename N, typename W>
walk_traits_base::walk_result dag_walk( N *pNode, W &w)
{
  typedef typename walk_traits<W> wtraits;
  typedef typename node_traits<N> ntraits;
  typedef walk_traits_base::walk_result walk_result;
  using walk_traits_base::eOK;
  using walk_traits_base::ePrune;
  using walk_traits_base::eStop;
  using walk_traits_base::eError;

  walk_result res = eOK;
  bool b_visit_children = true;

  //there is no need to visit this node
  //if multiple visits are not allowed and it has already been visited earlier
  bool b_should_do_main_operations = wtraits::is_multiple_visits_allowed || !ntraits::get_visit_tag( pNode);
  if( b_should_do_main_operations)
  {
      res = wtraits::pre( pNode, w );

      //set the visit flag for this node
      ntraits::set_visit_tag( pNode, true );
      //if the result of the main operation
      //is prune, stop or error, the not visit children
      if ( res > eOK)
      {
          b_visit_children = false;
      }
  } else {
      //there is no need to continue
      //this  node has been visited once
      return res;
  }
  //if the children ought to be visited
  if ( b_visit_children )
  {
      //copy the current stack
      //we need to rstore it after visiting chilren
      wtraits::stack_type s_copy( wtraits::get_stack( w) );
      ntraits::node_iterator nit, nbegin, nend;
      nbegin = ntraits::get_node_container_begin( pNode );
      nend = ntraits::get_node_container_end( pNode );
      for( nit = nbegin; nit != nend; ++ nit )
      {
          N * pChild = *nit;
          assert( pChild );

              res = dag_walk( pChild, w );

          //restore the stack on w
          //so that the next child gets the same context
          wtraits::set_stack( w, s_copy);

          //if the rsult of this walk is more serious
          //than ePrune, let us quit
          if ( res >= wtraits::eStop )
          {
              break;
          }
      }
  }
  //finally do the post operation
  //The post operation is the one done after vsisting the children.
  //It is passed the previous value of res.
  //So the first step in post, has to check the result so far,
  //and treat it accordingly
  if( res <= ePrune )     {
      res = wtraits::post( pNode, w,  res );
 }
return res;
}  

Here is the version of the above stored at code/google .

Posted in c++ | Tagged , , , , , , , | Leave a comment