5

我正在尝试为学术目的制作一个自定义碰撞引擎，但我陷入了一个一般的 c++ 编程问题，我已经拥有所有正常工作的几何图形，并且对于问题的范围，我有这个功能：

template<typename lhs_geometry, typename rhs_geometry>
bool intersects( const lhs_geometry& lhs, const rhs_geometry& rhs )
{
    //returns true if does objects intersects 
    //(assume this functions works perfectly with every geometry type)
}

我还有以下课程需要完成实施

template<typename geometry_type>
class collidable_object
{
public:
    explicit collidable_object( geometry_type& geometry ) :
        m_geometry( geometry )
    {

    }

    ~collidable_object()
    {

    }

private:
    geometry_type& m_geometry;
};

我的问题出现的地方是当我想创建一个列表collidable_object并测试它们的交叉点 2 by 2。

我对谷歌做了一些研究，发现有一个基类collidable_object可以让我将对象存储到列表中。但在那之后，我如何根据对象的特定几何形状测试对象？

我曾尝试实现访问者模式，但每次都卡住了，因为我不想硬编码所有可能的几何类型，因为我总是会调用intersetcs().

我还发现了一篇关于合作访客的文章，但这似乎很复杂。

有没有人有一个简单有效的解决方案？

编辑：我想避免列出几何图形的原因是因为我希望添加新几何图形相对容易，而不必在树状结构中查找文件。

EDIT2：这里是有关该intersetcs方法的更多信息：intersects 方法基于标签调度以找到正确的几何图形，但几乎所有凸形都使用 GJK 算法，该算法只要求对象可以返回给定方向上最远的点。对于非凸形状，这些形状被分割成凸子形状，并且该过程重新开始。

没有统一的标准来查看是否intersects能够处理最常用的给定形状furthest_along，但球对球不能，而且球体聚合也不需要使用furthest_along

附加信息：我使用 VS2012 和 C++11

4

2 回答 2

3

如果不将所有可能的几何图形列表存储在某个地方，您将无法逃脱。否则编译器将不知道要生成哪些模板实例。但我想出了一些代码，你必须在一个位置声明该列表，即GeometryTypes. 其他一切都建立在此之上。我在这里没有使用 vistor 模式，它的好处是您不必将样板代码添加到不同的几何类实现中。实现intersects所有组合就足够了。

首先包括：我稍后将使用shared_ptr，打印东西，并在未知几何类型的情况下中止。

#include <memory>
#include <iostream>
#include <cstdlib>

现在使用可用于多态指针的通用基类定义一些几何图形。你必须至少包含一个虚函数，这样你才能得到一个可以在dynamic_cast以后使用的虚函数表。使析构函数具有多态性可确保即使通过多态指针删除派生类也将被正确清理。

struct Geometry {
  virtual ~Geometry() { }
};
struct Circle : public Geometry { };
struct Rectangle : public Geometry { };

现在是您的intersects模板。我只为此演示编写了一个包罗万象的实现。

template<typename lhs_geometry, typename rhs_geometry>
bool intersects(const lhs_geometry& lhs, const rhs_geometry& rhs) {
  std::cout << __PRETTY_FUNCTION__ << " called\n"; // gcc-specific?
  return false;
}

这是我们声明所有几何图形列表的地方。如果您有相互衍生的几何图形，请确保首先拥有最具体的几何图形，因为将尝试这些几何图形以进行动态转换。

template<typename... Ts> class TypeList { };
typedef TypeList<Circle, Rectangle> GeometryTypes;

现在一堆帮助代码。基本思想是迭代一个这样TypeList的，并为每种类型尝试动态转换。第一个助手迭代 lhs 参数，第二个助手迭代 rhs 参数。如果未找到匹配项，则您的列表不完整，这将导致应用程序中止并显示一个希望有用的错误消息。

template<typename TL1, typename TL2> struct IntersectHelper1;
template<typename T1, typename TL2> struct IntersectHelper2;

template<typename TL2, typename T1, typename... Ts>
struct IntersectHelper1<TypeList<T1, Ts...>, TL2> {
  static bool isects(Geometry* lhs, Geometry* rhs) {
    T1* t1 = dynamic_cast<T1*>(lhs);
    if (!t1)
      return IntersectHelper1<TypeList<Ts...>, TL2>::isects(lhs, rhs);
    else
      return IntersectHelper2<T1, TL2>::isects(t1, rhs);
  }
};

template<typename T1, typename T2, typename... Ts>
struct IntersectHelper2<T1, TypeList<T2, Ts...>> {
  static bool isects(T1* lhs, Geometry* rhs) {
    T2* t2 = dynamic_cast<T2*>(rhs);
    if (!t2)
      return IntersectHelper2<T1, TypeList<Ts...>>::isects(lhs, rhs);
    else
      return intersects(*lhs, *t2);
  }
};

// Catch unknown types, where all dynamic casts failed:

bool unknownIntersects(Geometry* g) {
  std::cerr << "Intersection with unknown type: "
            << typeid(*g).name() << std::endl;
  std::abort();
  return false; // should be irrelevant due to abort
}

template<typename TL2>
struct IntersectHelper1<TypeList<>, TL2> {
  static bool isects(Geometry* lhs, Geometry* rhs) {
    return unknownIntersects(lhs);
  }
};

template<typename T1>
struct IntersectHelper2<T1, TypeList<>> {
  static bool isects(T1* lhs, Geometry* rhs) {
    return unknownIntersects(rhs);
  }
};

有了所有这些助手，您现在可以进行多态交叉测试。我正在介绍一个shared_ptr来存储这样的多态指针，我建议你在你的collidable_object类中做同样的事情。否则，只要可碰撞对象还活着，您就必须负责确保所引用的几何图形仍然存在，但最终会被清理掉。你想要这样的责任吗？

typedef std::shared_ptr<Geometry> GeomPtr;

bool intersects(GeomPtr lhs, GeomPtr rhs) {
  return IntersectHelper1<GeometryTypes, GeometryTypes>::
    isects(lhs.get(), rhs.get());
}

最后是一些 main ，这样您就可以在一个小示例中实际运行上述所有代码。

int main() {
  GeomPtr g1(new Rectangle), g2(new Circle);
  std::cout << intersects(g1, g2) << std::endl;
  return 0;
}
于 2013-06-19T07:31:09.243 回答
1

您的第二次编辑表明基本的交叉点例程将使用一些furthest_along代码进行操作。您可以利用它，使正常的交集检查在一个公共基类上运行，该基类furthest_along在其接口中包含它。您只需要针对特殊情况的特殊功能，您需要其他算法。

以下示例避免了所有动态转换，而是执行两个虚拟方法调用（也称为“<a href="http://en.wikipedia.org/wiki/Double_dispatch#Double_dispatch_in_C.2B.2B" rel="nofollow">双分派”，顺便说一句，它也可用作标签，因此将其添加到您的问题中可能会有用）。

struct Geometry {
  virtual ~Geometry() { }
  virtual Point furthest_along(Vector& v) const = 0;
  virtual bool intersects(const Geometry& other) const {
    return other.intersects_impl(*this);
  }
  virtual bool intersects_impl(const Geometry& other) const { // default impl
    // compute intersection using furthest_along
  }
  virtual bool intersects_impl(const Circle& other) const {
    return intersects_impl(static_cast<const Geometry&>(other)); // use default
  }
};

struct Circle : public Geometry {
  bool intersects(const Geometry& other) const {
    return other.intersects_impl(*this); // call intersects_impl(const Circle&)
  }
  bool intersects_impl(const Circle& other) const {
    // do circle-circle intersection
  }
  Point furthest_along(Vector& v) const {
    // implement for default intersection
  }
};
struct Rectangle : public Geometry {
  Point furthest_along(Vector& v) const {
    // implement for default intersection
  }
};

如果你调用a.intersects(b)，那么intersects方法将从虚函数表中选择a，而intersects_impl方法将从中选择b。如果要为类型组合添加特殊情况A和B，则必须添加

  1. 一个虚拟方法Geometry::intersects_impl(const A&)，委托给默认值
  2. 一个覆盖方法A::intersects委托给intersects_impl(const A&)
  3. B::intersects_impl(const A&)具有实际自定义代码的覆盖方法

如果您必须使用许多特殊情况算法添加许多类型，这可能相当于在各个地方进行大量修改。但是，如果您添加的大多数形状都将使用默认实现，那么您所要做的就是furthest_along为每个形状正确实现。

你当然可以做比这更聪明的事情。ConvexGeometry您可以创建一个使用该furthest_along方法的中间类，以及一个NonConvexGeometry可以提供一些方法来分割成凸块的类。你可以intersects在这两个中实现，并在Geometry纯抽象（= 0）中实现。然后，您可以避免intersects_impl(const Geometry&)使用intersects_impl(const ConvexGeometry&)andintersects_impl(const NonConvexGeometry&)作为默认机制，这两种机制都可以= 0在Geometryand 中适当地实现和ConvexGeometry实现NonConvexGeometry。但是如果你理解了上面代码背后的想法，那么添加这些扩展应该很简单。如果没有，请问。

于 2013-06-19T17:04:05.100 回答