Главная » C++ » Разделение алгоритмов и данных в геометрической библиотеке (необходима тройная диспетчеризация?)

Разделение алгоритмов и данных в геометрической библиотеке (необходима тройная диспетчеризация?)

У меня возникают проблемы при разработке части моего приложения, которая имеет дело с геометрией. В частности, я хотел бы иметь иерархию классов и отдельные методы для пересечений.

Эта проблема

Иерархия будет примерно такой:

  • Геометрия
    • меш
    • параметрический
      • коробка
      • сфера

И методы пересечения что-то вроде:

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

Это довольно просто. Проблема возникает сейчас, когда я хочу сохранить все геометрии вместе в одной структуре, скажем, например, std::vector (или KD-дерево, или что угодно).

Для этого мне нужно использовать std::vector<Geometry*>, Тем не менее, чтение из этого вектора получит меня Geometry* объекты и, таким образом, я не могу вызвать соответствующую функцию пересечения.

Пример проблемы:

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

Если бы я реализовал алгоритмы внутри геометрических объектов, проблему мог бы решить посетитель и довольно странный отскок вызова функции.

Однако я хотел бы оставить алгоритмы пересечения вне классов Geometry. Причины:

  • чтобы избежать принятия решения о том, кто должен владеть (например, где вы реализуете пересечение между коробкой и сферой, в Box или в Sphere?)

  • чтобы не загромождать объекты геометрии, все, что можно сделать с геометрией, — это довольно много (и это лишь некоторые из них: вокселизация, вычисление пересечений, применение конструктивных операторов геометрии …). Таким образом, отделение логики от данных здесь весьма желательно.

С другой стороны, мне нужно иметь иерархию вместо шаблонов, потому что для некоторых вещей конкретная геометрия может быть абстрагирована … (например, для хранения ее в std::vectorили KD-дерево, или …).

Как бы вы решили это? Есть какой-то шаблон дизайна, подходящий для этого? Я пытался посмотреть на некоторые библиотеки, но в итоге я был более смущен тем, что уже был …

Самый простой способ (который иногда используется) состоит в том, чтобы использовать RTTI (или имитировать его) и даункастинг, но это не совсем поддерживаемо … (добавление новой геометрии подразумевает изменение большого количества операторов switch через весь код).

Какие-нибудь мысли?

Большое спасибо заранее.

4

Решение

Я имею в виду другое решение, если вы беспокоитесь о скорости, это имеет сложность O (1), но вам может понадобиться программа для автоматической генерации кода c ++ для типов геометрии режима. Вы можете создать массив функций пересечения (псевдокод, у меня под рукой нет компилятора):

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 );
}

Или альтернатива:

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 );
}
2

Другие решения

Эта проблема похожа на этот.

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;
}
}

Или, если вы не используете наследование:

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;
}
}

ПРИМЕЧАНИЕ: если вы знаете тип одной геометрии, вы можете использовать шаблонную функцию:

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

ПРИМЕЧАНИЕ 2: вы можете написать одинаковые функции, например:

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

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

РЕДАКТИРОВАТЬ:

Если вы уменьшите проблему до двойной отправки, вы можете использовать этот техника.

Для пересечения трактуйте иерархию как:

  • Геометрия
    • меш
    • коробка
    • сфера

и для других действий:

  • Геометрия
    • меш
    • параметрический
      • коробка
      • сфера
1

Как насчет того, чтобы вы представляли свои алгоритмы пересечения как классы, которые могут решать, могут ли они обрабатывать набор геометрий, которые они получают, и вы предоставляете прокси пересечения, который имеет оригинальный интерфейс. Это будет выглядеть так:

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)
}
0
Источник
По вопросам рекламы [email protected]
Web-Answers © 2024 Наверх