Separation of algorithms and data in a geometry library (triple-dispatching needed?)

Question

I am having trouble designing the part of my application that deals with geometry. In particular, I would like to have a hierarchy of classes and separate methods for intersections.

The problem

The hierarchy would be something like this:

• Geometry
  • Mesh
  • Parametric
    • Box
    • Sphere

And the intersection methods something like:

namespace intersections
{
  bool intersection( const Box &, const Box &);
  bool intersection( const Box &, const Sphere &);
}

This is quite simple. The problem arises now, when I want to store all geometries together in a single structure, say for example a std::vector (or a KD-Tree, or whatever).

To do that, I need to use a std::vector<Geometry*>. However, reading from this vector would get me Geometry* objects and thus I have no way of calling the appropriate intersection function.

Example of the problem:

std::vector<Geometry*> arrGeometry;

// add the elements
arrGeometry.push( new Box() );
arrGeometry.push( new Sphere() );

// ... some more code

// try to intersect them?
Geometry* g1 = arrGeometry[0];
Geometry* g2 = arrGeometry[1];
bool intersecting = intersections::intersection( g1, g2 ); //< As expected, this does
                                                          // not work

If I implemented the algorithms inside the geometry objects the problem could be solved by a visitor and some pretty weird function call bouncing.

However, I would like to keep the intersection algorithms outside the Geometry classes. the reasons are:

• to avoid deciding which should have the ownership (eg. where do you implement the intersection between box and sphere, in Box or in Sphere?)

• to avoid cluttering the geometry objects will all that can be done to geometry, which is quite a lot (just to name a few: voxelize it, compute intersections, applying constructive geometry operators...). Thus, separating logic from data is quite desirable here.

On the other hand, I need to have a hierarchy instead of templates because for some things the specific geometry can be abstracted away... (eg. for storing it in a std::vector, or a KD-Tree, or... ).

How would you solve this? Is there any design pattern appropriate for this? I tried looking at some libraries but I ended up more confused that I already was...

The easiest way (which is sometimes used) is to use RTTI (or to fake it) and downcastings, but that is not exactly maintainable... (adding a new geometry implies change a lot of switch statement though all the code).

Any thoughts?

Thanks you very much in advance.

Answer 1

I have in mind another solution, if you are concerned about speed, this have O(1) complexity, but you may need program for auto generation of c++ code for mode geometry types. You can make array of intersection functions (pseudocode, i don't have any compiler at hand):

enum GeometryType
{
    TypeMesh,
    TypeParamBox,
    TypeParamSphere,
    MaxType,
};

bool intersection( const Mesh*, const Mesh* );
bool intersection( const Mesh*, const Box* );
bool intersection( const Mesh*, const Sphere* );

bool intersection( const Box*, const Mesh* );
bool intersection( const Box*, const Box* );
bool intersection( const Box*, const Sphere* );

bool intersection( const Sphere*, const Mesh* );
bool intersection( const Sphere*, const Box* );
bool intersection( const Sphere*, const Sphere* );

template<class T1,class T2>
bool t_intersection( const Geometry* first, const Geometry* second )
{
    return intersection( static_cast<const T1*>( first ), static_cast<const T1*>( second ) );
}

typedef bool (*uni_intersect)( const Geometry*, const Geometry* );

const uni_intersect IntersectionArray[] = // 2D array all possible combinations
{
    t_intersection<Mesh,Mesh>,
    t_intersection<Mesh,Box>,
    t_intersection<Mesh,Sphere>,

    t_intersection<Box,Mesh>,
    t_intersection<Box,Box>,
    t_intersection<Box,Sphere>,

    t_intersection<Sphere,Mesh>,
    t_intersection<Sphere,Box>,
    t_intersection<Sphere,Sphere>,
};

bool main_intersection( const Geometry* first, const Geometry* second )
{
    const unsigned index = (unsigned)(first->Type) * (unsigned)MaxType + (unsigned)(second->Type);
    return IntersectionArray[ index ]( first, second );
}

Or alternative:

const uni_intersect IntersectionArray[] = // 2D array all possible combinations
{
    t_intersection<Mesh,Mesh>,
    t_intersection<Mesh,Box>,
    t_intersection<Mesh,Sphere>,

    nullptr, // skip mirrored functions
    t_intersection<Box,Box>,
    t_intersection<Box,Sphere>,

    nullptr,
    nullptr,
    t_intersection<Sphere,Sphere>,
};

bool main_intersection( const Geometry* first, const Geometry* second )
{
    const unsigned Type1 = unsigned(first->Type);
    const unsigned Type2 = unsigned(second->Type);
    unsigned index;
    if( Type1 < Type2 )
        index = Type1 * (unsigned)MaxType + Type2;
    else
        index = Type1 + Type2 * (unsigned)MaxType;

    return IntersectionArray[ index ]( first, second );
}

Answer 2

This problem is similar to this.

class Geometry
{
public:
    enum eType
    {
        TypeMesh,
        TypeParamBox,
        TypeParamSphere,
    };

    Geometry( eType t ): Type( t ) { }
    ~Geometry() { }

    const eType Type;
};


class Mesh : public Geometry
{
public:
    Mesh(): Geometry( TypeMesh ) { }
};


class Parametric : public Geometry
{
public:
    Parametric( eType t ): Geometry( TypeMesh ) { }
};


class Box : public Parametric
{
public:
    Box(): Parametric( TypeParamBox ) { }
};


class Sphere : public Parametric
{
public:
    Sphere(): Parametric( TypeParamSphere ) { }
};


namespace intersections
{
    bool intersection( const Geometry* first, const Geometry* second );
    template <typename T>
    bool t_intersection( const T* first, const Geometry* second );

    bool intersection( const Box*, const Box* );
    bool intersection( const Box*, const Sphere* );
    bool intersection( const Sphere*, const Box* );
    bool intersection( const Sphere*, const Sphere* );
}


void foo_test()
{
    std::vector<Geometry*> arrGeometry;

    // add the elements
    arrGeometry.push_back( new Box() );
    arrGeometry.push_back( new Sphere() );

    // ... some more code

    // try to intersect them?
    Geometry* g1 = arrGeometry[0];
    Geometry* g2 = arrGeometry[1];
    bool intersecting = intersections::intersection( g1, g2 );
}


bool intersections::intersection( const Geometry* first, const Geometry* second )
{
    switch( first->Type )
    {
    case Geometry::TypeParamBox: return t_intersection( static_cast<const Box*>( first ), second );
    case Geometry::TypeParamSphere: return t_intersection( static_cast<const Sphere*>( first ), second );
    default: return false;
    }
}


template <typename T>
bool intersections::t_intersection( const T* first, const Geometry* second )
{
    switch( second->Type )
    {
    case Geometry::TypeParamBox: return intersection( first, static_cast<const Box*>( second ) );
    case Geometry::TypeParamSphere: return intersection( first, static_cast<const Sphere*>( second ) );
    default: return false;
    }
}

Or if you don't use inheritance:

struct Mesh{};

struct Box{};

struct Sphere{};


enum GeometryType
{
    TypeMesh,
    TypeParamBox,
    TypeParamSphere
};


struct Geometry
{
    GeometryType Type;

    union
    {
        Mesh* pMesh;
        Box* pBox;
        Sphere* pSphere;
    } Ptr;
};



namespace intersections
{
    bool intersection( const Geometry* first, const Geometry* second );
    template <typename T>
    bool t_intersection( const T* first, const Geometry* second );

    bool intersection( const Box*, const Box* );
    bool intersection( const Box*, const Sphere* );
    bool intersection( const Sphere*, const Box* );
    bool intersection( const Sphere*, const Sphere* );
}



void foo_test()
{
    std::vector<Geometry*> arrGeometry;

    // add the elements
//  arrGeometry.push_back( new Box() );
//  arrGeometry.push_back( new Sphere() );

    // ... some more code

    // try to intersect them?
    Geometry* g1 = arrGeometry[0];
    Geometry* g2 = arrGeometry[1];
    bool intersecting = intersections::intersection( g1, g2 );
}


bool intersections::intersection( const Geometry* first, const Geometry* second )
{
    switch( first->Type )
    {
    case TypeParamBox: return t_intersection( first->Ptr.pBox, second );
    case TypeParamSphere: return t_intersection( first->Ptr.pSphere, second );
    default: return false;
    }
}


template <typename T>
bool intersections::t_intersection( const T* first, const Geometry* second )
{
    switch( second->Type )
    {
    case TypeParamBox: return intersection( first, second->Ptr.pBox );
    case TypeParamSphere: return intersection( first, second->Ptr.pSphere );
    default: return false;
    }
}

NOTE: if you know type of one geometry, you can use templated function:

Box* pBox;
Geometry* pUnknownGeometry;
bool intersecting = intersections::t_intersection( pBox, pUnknownGeometry );

NOTE2: you can write identical functions like this:

bool intersection( const Box* first, const Sphere* second );

bool intersection( const Sphere* first, const Box* second )
{
    return intersection( second, first );
}

EDIT:

If you reduce problem to double dispatch, you can use this technique.

For intersection treat hierarchy as:

• Geometry
  • Mesh
  • Box
  • Sphere

and for other actions:

• Geometry
  • Mesh
  • Parametric
    • Box
    • Sphere

Answer 3

How about you represent your intersection algorithms as classes which can decide, if they can process the set of geometries they are getting, and you provide an intersection proxy which has the original interface. This would look like this:

class IIntersection
{
   public:
     bool intersection( const Geometry &, const Geometry &);
     bool accept( const Geometry &, const Geometry &);
}

class IntersectionBoxSphere : public IIntersection
{
public:
   bool intersection( const Geometry &, const Geometry &);
   bool accept( const Geometry & a, const Geometry &b)
   {
      return ((dynamic_cast<Box>(a) != NULL || dynamic_cast<Box>(b) != NULL)
              (dynamic_cast<Sphere>(a) != NULL || dynamic_cast<Sphere>(b) != NULL))
   }
}

class IntersectionBoxbox  : public IIntersection
...
    /**collect some where all algorithms*/
    IIntersection* myintersections[2];
    myintersections[0] = new IntersectionBoxSphere()
    myintersections[1] = new IntersectionBoxbox()
...
/**decide here which to use */
bool intersection( const Geometry &a, const Geometry &b)
{
    for ( i ... )
     if (myintersections[i]->appect(a,b))
       return myintersections[i]->intersection(a,b)
}