c++ - 几何库中的算法和数据分离(需要三重调度？)

Question

我在设计处理几何的应用程序部分时遇到问题。特别是，我希望有一个类的层次结构和用于交叉点的单独方法。

问题

层次结构是这样的:

• 几何
  • 网格
  • 参数化
    • 盒子
    • 领域

交集方法类似于:

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

这很简单。现在问题出现了，当我想将所有几何图形一起存储在一个结构中时，例如 std::vector (或 KD 树，或其他)。

为此，我需要使用 std::vector<Geometry*> .然而，从这个 vector 中读取会让我得到 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

如果我在几何对象内部实现算法，问题可以由访问者和一些非常奇怪的函数调用弹跳来解决。

但是，我想将相交算法保留在几何类之外。原因是:

• 避免决定谁应该拥有所有权(例如，在 Box 或 Sphere 中实现方框和球体之间的交集？)

• 为了避免使几何对象困惑，所有可以对几何进行的操作都很多(仅举几例:体素化、计算交点、应用构造性几何运算符...)。因此，在这里非常需要将逻辑与数据分开。

另一方面，我需要一个层次结构而不是模板，因为对于某些东西，特定的几何图形可以被抽象掉......(例如，将其存储在 std::vector 或 KD 树中，或……)。

你会如何解决这个问题？有没有适合这个的设计模式？我尝试查看一些库，但结果我更加困惑，因为我已经是...

最简单的方法(有时会使用)是使用 RTTI(或伪造它)和向下转换，但这并不是完全可维护的...(添加新几何意味着更改大量 switch 语句，尽管所有代码).

有什么想法吗？

非常感谢您。

Answer 1

我想到了另一个解决方案，如果您关心速度，这具有 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 );
}