use strict inequalities in AABB::intersects

[bfops]

This is definitely a nit, but I've stubbed my toe several times on the fact that AABB::intersects uses non-strict inequalities. When things are placed perfectly next to one another, my intuition thinks that they shouldn't count as intersecting. If two objects overlap, the intuitive solution is to bump them apart so that they're touching, but not overlapping anymore. AABB::intersects will still treat them as intersecting after that bump!

[sebcrozet]

This actually has a lot of tricky implications. My current (strong) position is to keep the non-strict inequalities because, long story short, making the inequalities strict means that ncollide should not support hollow ray-casting and boundary representations (Bézier surfaces, Triangle meshs, etc.) any longer.

I think the core issue here is that AABB are bounding volumes, nothing more, but you are using them as collision shapes (but I understand you have very good reasons to do this, especially in the performance side).

So first, I will explain why we should keep non-strict inequalities, then I would like to understand exactly your use-case (sorry I did not read your code with enough attention to understand it; but if you give me some pointers on where to look, I will) so that we can find an alternative.

Why non-strict inequalities ?

The question here is whether or not bounding volumes should be (topologically) closed objects or (topologically) open − in other words, whether they should include their borders as solid things or not. As they are volumes that bound collision shapes (Cuboid, Sphere, etc.), making them open implies that the bounded shape must also be open (otherwise, we would not be able to compute the exact bounding volume of those shapes: it is impossible to design a borderless box that exactly encloses another box with a border).

But making the collision shapes open has two very bad consequences:

1. Ray casting on open geometries is not very well defined as there is no way to compute the exact time of impact (i-e the exact time the ray touches the object). The only information we could compute is the "least time of non-impact", which is a very unusual concept.
2. Some shape cannot, by definition, be open. For example the triangle mesh is the union of a set of triangles which will just vanish if we open them in a 3D space. The idea is simple: a triangle is a 2-manifold in a 3-dimensional space, so it has no interior because it is its own border. If you remove this border, you remove the whole mesh altogether. On the other hand, we cannot just make a "special case" here and assume triangle meshes are closed because even if you try to find the exact (open) bounding box of a (closed) triangle, you will fail because this bounding box is not the limit of a converging series of slightly smaller bounding boxes (it is the one "just before" this limit).

To recapitulate, we cannot open every geometrical shapes (e.g. 2-manifolds), therefore we cannot open their bounding volumes, implying that we cannot use strict inequality for AABB intersection test as this would make many things inconsistent.

If you do not agree with this position, I am open do discuss this.

About your use-case.

If I understand correctly, you want to represent your objects with AABB because, in your application, everything live in an axis-aligned world (rotations are forbidden). Using a Cuboid instead would be overkill and less performent because the collision detection algorithm assume they can be rotated.

What I do not understand is why you have more than one or two box-shaped collision objects (for the user and the mob), in which case the performance overhead of using a Cuboid is negligible? Also, assuming you are using lots of AABBs to represent the solid ground, why would you need to test them for intersection with each other?

My feeling here is that you did something unusual because ncollide lacks some crucial feature.

[bfops]

Thanks for the detailed explanation! That helps clarify a lot of things for me. The non-strict case also makes sense for AABBs that have 0 width in at least one dimension.

It's always an option to simply add an AABB::overlaps function that differs from intersects in the boundary case (and it doesn't necessarily need to go in ncollide either - I can write that on my end). But you're probably right that I'm using ncollide a little weirdly.

It's my impression that it's not-uncommon in games with simpler physics to just treat things as their AABBs, and check for overlaps to determine whether things are colliding. If they are, they are bumped outwards by some minimal amount so that they're not intersecting anymore. Much as finding a minimal TOI with a ray is impossible without the boundary included, finding a minimal bump with another AABB is impossible with the boundary included.

In playform, in part as a remnant of its more voxely heritage, the terrain is represented using lots of little AABBs, along with the player and the mob. These AABBs are all stored in an octree (misnamed - it's a BSP tree), and movement in the world is checked against the "tree" for collisions. Inserting new chunks of terrain also checks that same tree, which makes sense for a few reasons, mainly "don't place terrain into a mob", but also so that newly-created terrain doesn't accidentally cut through existing terrain in some strange way (not a problem yet, but I plan to let the player add and remove terrain at will).

I'm not committed to AABBs for everything - I'll want more advanced physics eventually. But I actually couldn't figure out how to use Cuboids for collisions! I also need to think a little bit about how they'll play with the BSP tree - a nice thing about turning everything into AABBs is that they're very easy to split up and insert.

[bfops]

A bit of a derailment, but I'm also interested in your thoughts on a feature I have planned for playform: I want to give the player an OBB as a cursor, and let them remove parts of the terrain. The first iteration will use an AABB and simply remove any triangles it touches, but I'll eventually be looking to use an OBB and add triangles to fill in some of the space left behind so that it appears that precisely that cube was cut from the terrain (e.g. like an eraser tool). I'm not entirely sure whether this will be feasible (I may need to switch back to something more voxely), but I'm interested in your thoughts as to how much support ncollide can give me here.

[sebcrozet]

About your first answer.

It's always an option to simply add an AABB::overlaps function that differs from intersects in the boundary case

It would be definitely useful to add a method that returns a three-variants-enum that tells if the bounding volumes are penetrating, touching, or separated. However I have no idea how to name such method !

It's my impression that it's not-uncommon in games with simpler physics to just treat things as their AABBs, and check for overlaps to determine whether things are colliding. If they are, they are bumped outwards by some minimal amount so that they're not intersecting anymore. [...] finding a minimal bump with another AABB is impossible with the boundary included.

To be honest, I do not have much experience in actually using a physics engine for things like games, so I can only give you an impression too (but this time more as a physics engine writer than as a collision detection specialist).

There are two concepts here: interference detection (overlaps check) and then contact resolution (bumping outward). What I think people do is to perform a distance computation and interpret the 0-distance case as "just touching". In this case, what you call "minimal bump" actually has a more scientific denomination which is the "minimal translational distance" (or "penetration depth"). With this concept in hand, the sound thing to do is to move the objects such that their distance is equal to zero. In this case it makes sense to have closed objects as the overlap of their boundaries (and only their boundaries) corresponds exactly to this zero-distance.

Then, using an AABB or not does not mater, except for the semantics. An AABB is equivalent to a rotationless Cuboid after all. People will pick whatever is simpler for them to use depending on their tools I guess.

These AABBs are all stored in an octree (misnamed - it's a BSP tree), and movement in the world is checked against the "tree" for collisions. Inserting new chunks of terrain also checks that same tree, which makes sense for a few reasons, mainly "don't place terrain into a mob", but also so that newly-created terrain doesn't accidentally cut through existing terrain in some strange way (not a problem yet, but I plan to let the player add and remove terrain at will).

So if I understand correctly there won't be a lot of distance queries between the objects after all. I don't think using AABBs instead of Cuboids is very necessary. Especially because if you need more advanced physics AABBs will not give you enough tools to work with.

But I actually couldn't figure out how to use Cuboids for collisions!

I must admit I can't blame you for that! What you need to test two cuboids for collisions (without using persistent collision detection structure) is there: http://ncollide.org/doc/ncollide3df32/narrow/collide/fn.implicit_implicit.html As you can see, this is very, very, very well hidden, and horribly rendered by rustdoc. Also the return type is quite obscure, and the simplex argument hardly understandable by non-specialists. I really have to clean this up to make it actually usable (I just created an issue for this #28).

Correctly used, this function will return the penetration depth between the two objects, or their distance if they are close enough.

I also need to think a little bit about how they'll play with the BSP tree

Well, almost nothing should change with the BSP tree. Usually, the BSP tree will use AABBs (of the cuboids) to find collision pairs. Then those collision pairs should have their exact distance computed using a dedicated algorithm. Of course, since the AABBs and the cuboids will coincide, you do not have to represent them both explicitly: just pass a dynamically created Cuboid to the relevant distance computation function. This is what I would do.

---

About your other answer.

use an AABB and simply remove any triangles it touches

This means that to dermine where the AABB touches the terrain, your current ray-cast will have to be an "AABB-cast" or "OBB-cast" instead. I just created an issue for this: #29. This is not implemented in ncollide, yet, but should be easy enough to add as all the hard work is already done (this can be done with a ray cast on their Minkowski Sum which is already implemented). Also, it does not matter if this you are casting against a triangle mesh or a voxel grid, the algorithms it uses remain the same, and are already implemented.

This is part of the "basic, high level, features" ncollide do not have yet.

fill in some of the space left behind so that it appears that precisely that cube was cut from the terrain

Depending on what kind of "cut" you want this may be quite difficult, especially with OBB. If you want an exact cut (i-e the exact geometry of the intersection), you will need to compute the exact intersection of the involved objects. This is not easy and there is (today) nothing in ncollide related to exact intersection geometry computation.

Also, if some day you end up extracting the surface of the ground as a triangle mesh instead of keeping thousands of boxes, ncollide does not have modifiable triangle meshes yet. Though this should be easy enough to add: #30.

[bfops]

Thanks so much for being so thorough! That all sounds very cogent to me. I think given our discussion, we can close this issue.