Separation of algorithms and data in the geometry library (do you need triple scheduling?)

Question

I had a problem developing a part of my application that deals with geometry. In particular, I would like to have a class hierarchy and separate methods for intersections.

Problem

The hierarchy will be something like this:

• Geometry
  • Mesh
  • Parametric
    • Box
    • Sphere

And the intersection methods are something like:

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

It is pretty simple. The problem now arises when I want to store all the geometries together in one structure, say, for example, std::vector (or a KD tree or something else).

For this I need to use std::vector<Geometry*> . However, reading from this vector would make it possible to obtain Geometry* objects, and therefore I have no way to call the corresponding intersection function.

Example 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 the visitor and some rather strange call of the call function.

However, I would like to keep intersection algorithms outside of the Geometry classes. causes:

• to avoid deciding which one should have ownership (for example, where do you intersect between a field and a sphere, in Box or in Sphere ?)

• to avoid cluttering geometry objects, all this can be done for geometry, which is quite a lot (just to name a few: voxelize it, calculate intersections, apply constructive geometry operators ...). Thus, it is highly desirable to separate the logic from the data.

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

How would you solve this? Is there any design template suitable for this? I tried to look at some libraries, but in the end I was more embarrassed that I was already ...

The easiest way (which is sometimes used) is to use RTTI (or fake it) and downcastings, but this is not completely repaired ... (adding new geometry implies changing a large number of switch statements, although all the code).

Any thoughts?

Thank you very much in advance.

Answer 1

I mean another solution, if you are concerned about speed, this is O (1) complexity, but you may need a program to automatically generate C ++ code for mode geometry types. You can create an array of intersection functions (pseudo code, I don't have any compiler):

 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 an 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 are not using 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 the type of one geometry, you can use the template function:

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

NOTE2: you can write 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 the problem to double sending, you can use this method.

For the intersection processing hierarchy as:

• Geometry
  • Mesh
  • Box
  • Sphere

and for other actions:

• Geometry
  • Mesh
  • Parametric
    • Box
    • Sphere

Answer 3

How do you present your intersection algorithms as classes that can decide if they can handle the set of geometries that they receive, and you provide an intersection proxy that has an original interface. It will 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) }