c++ - 在几何库中分离算法和数据（需要三次调度？）

Question

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

问题

层次结构将是这样的：

几何学
- 网
- 参数
  - 盒子
  - 领域

相交方法类似于：

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

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

为此，我需要使用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

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

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

避免决定哪个应该拥有所有权（例如，你在哪里实现盒子和球体之间的交集，在Box还是在Sphere？）
为了避免使几何对象混乱，可以对几何做所有的事情，这是相当多的（仅举几例：体素化它，计算交叉点，应用构造几何运算符......）。因此，在这里将逻辑与数据分离是非常可取的。

另一方面，我需要有一个层次结构而不是模板，因为对于某些事情，可以抽象出特定的几何图形......（例如，将其存储在 astd::vector或 KD-Tree 或......）。

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

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

有什么想法吗？

非常感谢你提前。

score 2 · Accepted Answer

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

score 1 · Accepted Answer

这个问题与此类似。

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

编辑：

如果您将问题减少到双重调度，则可以使用此技术。

对于交集，将层次结构视为：

几何学

网

盒子

领域

以及其他操作：

几何学

网

参数

盒子

领域

score 0 · Accepted Answer

您如何将您的相交算法表示为可以决定的类，它们是否可以处理他们获得的几何图形集，并且您提供具有原始接口的相交代理。这看起来像这样：

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

c++ - 在几何库中分离算法和数据（需要三次调度？）

3 回答 3

Related

Reference