Collision shapes rework

[mosra]

Why?

• Make the core algorithms reusable without all this inheritance, virtual functions and cached values, for example:
  • Be able to create plain old array of AABBs and do mad cache-aware SIMD operations on them
  • Use them in e.g. AABB trees
  • Batched frustum culling (possibly uploaded to GPU buffer)
  • Tools for creating bounding volumes (mesh as input, array of AABBs as output...)
• On the other hand be able to do everything what was possible now:
  • Store original shape, put reference to it into ObjectShape feature and be able to get (cached) transformed values back from it (manual collision handling)
  • BVHs with all those nice boolean operators
  • Run-time double dispatching for collision detection

    Current reimplementation state

• All shapes are now PODs (no virtual functions, constexpr constructors), they have all the needed data only once (i.e. no transformation caching) and they have no base classes, just static polymorphism (i.e. common interface for all). Result: 60% code removed.

• ShapeGroup stores the shapes in flat array, making it easy for user to query the contents and possibly save a reference to particular shape. It also saves some allocations compared to previous solution, but the internals more complicated. Nothing for user to worry about, the API is the the same as before:

  auto group = Physics::Point2D(1.0f, -0.5f) || Physics::Sphere2D({}, 1.5f);
  bool collides = group % Physics::Point2D(0.5f, 0.5f);

  Adding shapes as references to original objects is not possible though, they need to be extracted back after creating the group:

  Physics::Sphere2D& sphere = group.get<Physics::Sphere2D>(1);

• ObjectShape is now templated on shape, stores two instances of it (original and transformed one) and common functionality is in abstract base AbstractObjectShape. It is now actually usable, compare previous, where ObjectShape wasn't useful for anything:

  ObjectShapeGroup2D* group;
  Object2D* o;
  Physics::Point2D point({1.0f, -0.5f});
  (new Physics::ObjectShape2D(o, shapes))->setShape(&point);
  Vector2 transformedPosition = point.transformedPosition();

  With current:

  auto shape = new Physics::ObjectShape<Physics::Point2D>(o, {{1.0f, -0.5f}}, shapes);
  Vector2 transformedPosition = shape->transformedShape().position();

• Shape polymorphism, collision dispatching etc. is hidden from the user and done internally with wrapper classes inside ShapeGroup and ObjectShape. It is good because it doesn't add confusing wrappers to the user (except one additional "internal" header file with no public documentation and no need for user to include it). Has it any downsides? Will the user need the polymorphism anywhere?

  Issue 1

Physics::Point2D a;
Physics::Sphere2D b;
auto shape = new Physics::ObjectShape<Physics::ShapeGroup2D>(o, a || b, shapes);

The above code is not intuitive, becasuse the user might not immediately know that result of a || b is ShapeGroup. Even if he would, this is a lot of unnecessary typing, because the shape type is known from the arguments (unlike in above examples). Two considered (but unsufficient) solutions:

• Merge ShapeGroup into specialized ObjectShape, e.g. ObjectShapeHierarchy? Will result in having the internal polymorphic wrappers in only one place (hopefully), which is good, but removes the possibility to operate on ShapeGroup alone without scene graph. Has ShapeGroup any use without scene graph?

• Provide some convenience function similar to std::make_tuple which removes the need for explicit type specification, e.g.:

  auto shape = Physics::makeObjectShape(o, a || b, shapes);

  It would save typing also in some other cases, but what should this function return? Pointer to object created on heap? Object by value? Both have valid use cases and having both makeObjectShape() and makeObjectShapePtr() is ugly.

  Issue 2

The user can't intuitively tell what's the difference between ObjectShapeGroup and ShapeGroup, thus they should be renamed to something more meaningful. Also why not to move everything to different namespace so Physics can be saved for other things like rigid bodies and particle systems? Linking Physics library just because one needs to click menus seems like overkill. But on the other hand, will collision detection be large enough to be in separate library?

• Rename Physics namespace to Shapes (CollisionDetection is too long?)
• Rename ShapeGroup to Hierarchy. Because it will always be written as Shapes::Hierarchy it will be obvious what is going on. Better name?
• Rename ObjectShape to Shape and ObjectShapeGroup to ShapeGroup (Object was redundant). Is it descriptive enough for scene graph feature (Collidable sounds to Java-ish)? Physics itself will contain RigidBody.

[JanDupal]

From user's point of view I'd appreciate more solution 1.1. I find differentiating between general shapes and physics shapes bit confusing. Ideally user should be able to pass general shape and let framework decide (at compile time) whether it is related to debug drawing, collision detection, physics computation etc. depending on context. But I have no idea about implementation.

Could you please describe issue with ShapeGroup in 1.1?

[JanDupal]

Thoughts:

1. Algebraic structure like Monoids for shapes
   • encapsulate single shape or shape group
   • provide % and composition operators
   • result: no specific (at least public) type to differentiate "primitive" from "composition of primitives"
   • issues: how to specify position of components in composition
2. I like the idea with splitting Physics namespace
   • maybe Shapes and Physics
   • Where does "I'd like to render a box!" fit? Is it a primitive or a shape? What about "I'd like to render a box and make it collidable as fast as possible to see if my game idea works."?

[mosra]

1. this is how it is currently - ShapeGroup which can contain one or more shapes, but the only advantage is the "universal" type, querying the contents is almost impossible. The shapes actually behave like monoids and you have to specify the type only during creation of single shapes, not for the result:

   auto shape = Physics::Point2D({}) || Physics::Sphere2D({3.0f, 1.0f}, 0.5f);

   Nice thing would be to have something like the following to avoid specifying the resulting type altogether to follow the monoids idea, maybe C++17 will be able to do it?:

   new Shapes::Shape<auto>(object, shape);

   Otherwise, to avoid explicit type specification, we must resort to some makeShape() function as described above.

2. Shapes and Physics, sure.

In current "terminology", primitive is mesh data (vertices, faces, normals...) of some basic object (circle, line, arrow, crosshair, monkey...) to ease up prototyping, shape is (simplified) description of some subspace (which doesn't even need to encapsulate any mesh, e.g. trigger volumes) used for collision detection (primarily not for rendering). User's line of thoughs should be like this:

• I'd like to have a box object:

  auto box = new Object3D(scene);

• I'd like to have it collidable, thus I need to assign Shape feature to it and somehow describe its erm... shape, possibly using Shapes::Box3D:

  auto shape = new Shapes::Shape<???>(box, Shapes::Box3D(...));

• I'd like to visualize the box somehow. I have two options, assign Drawable feature to it and render a mesh (possibly created from pre-made Primitives::Cube) using some shader (possibly with stock Shaders::Phong). Or, because I have assigned the collision shape already, I can use DebugTools::ShapeRenderer, which will visualize just the shape with wireframe, it will look ugly, but I can do it better later:

  new DebugTools::ShapeRenderer3D(shape, ...);

[mosra]

Done in 06d707f25c517a237d301ae7422309e7a4a81c0e.