Matter-js: Improve collision filters

[liabru]

Currently collision filters work as they do in Box2D, which uses a bitwise implementation which supposedly should give good performance. Here is a good explanation.

This comes with some downsides:

• Limits the number of categories to just 32
• Not a particularly standard JavaScript style of implementation
• It's pretty confusing

I also doubt the approach gives much of a performance boost compared to other possible nicer alternatives. I still need to decide on exactly what though. Changing the implementation is mostly a matter of changing:

• Matter.Body.create
• Matter.Body.nextGroup and Matter.Body.nextCategory
• Matter.Detector.canCollide

Back compatibility is important here, so the old scheme should be supported but deprecated.

If anyone has any thoughts let me know.

[Swendude]

What would be the downside to using the already available collisionFilter.group and adding a field collisionFilter.collidesWith that can contain an array of collision groups the body collides with? This seems like a straightforward easy-to-use feature.

Update:
I created a working pen of this idea, I have no idea how to test performance implications. It is a monkey patched version but shows the idea. The default settings for collisionFilter.group should be 0 (maybe -1) since that makes the body accept collision with everything.

[AndrewBrownK]

TL;DR:
I got wondering about different possible approaches and made something up after a bit of musing. Here it is FWIW

Alrighty

This is what I can come up with as a goal for 'capability' and performance: For a simulation of n objects, there exists a configuration such that every unique object pair can arbitrarily be set to collide or not collide. Ideally the storage and evaluation of the configuration should perform much better than O(n^2) in average cases though.

If the category/mask system is generalized to any number of categories (not just 32), then hypothetically that is a capability solution. At the finest grain of control each object can have its own category, and then arbitrary masks control all possible pairs of collisions. Of course in most situations objects will share categories when it makes sense, but it just goes to illustrate. The problem is you have to be careful how you scale beyond 32 categories or you could pay in performance (the bitwise & is really fast, and it's no wonder it was chosen in box2d).

The nice thing about the group system is that you can say "Ok, we have this nice category system as a fallback, but this set of object I want to ALWAYS or NEVER collide NO MATTER WHAT." If the category mask system is the rules, the group system is the exceptions. If we had limitless categories, then in principle this wouldn't be necessary, but it is in fact still very convenient and very performant (just number equivalence). The nice thing about the group system is that you can have any number of distinct groups (e.g. a billion robots that don't self collide (groups) but collide with all others (category/mask)). The downside of the group system is that you can only set one group. You can't make BodyA ALWAYS collide with BodyB that ALWAYS collides with BodyC that NEVER collides with BodyA, without resorting to categories and masks.

So I'm no computer scientist, but just spitballing ideas, here's my two cents of an approach.

(If I'm not mistaken this would require new interface for the programmer. The old interface might be able to ~retrofit~ forwardfit(?) onto this new idea, but might not magically grant all the full capability. Reaping the benefits might require the programmer to adopt new interface, although the old interface would still work.)

I think the two layer approach is helpful. The base rules (categories and masks) and then overriding exceptions (groups). However I'm going to break away from the 'categories', 'masks', and 'groups' terminology now to avoid confusion in describing this different approach.

If I'm not mistaken, we should be able to achieve full configurability with 3 layers:

1. implicitly, all objects collide
2. except when explicitly specified otherwise, and they will not collide
3. except when finally specified with the ultimate override, and they do collide after all

It can also be done the other way around:

1. implicitly, all objects pass through one another
2. except when explicitly specified otherwise, and they will collide
3. except when finally specified with the ultimate override, and they pass through one another after all

I think the former makes the most sense though obviously, since it makes sense to collide by default. No matter whether two particular objects collide or do not collide, you can configure one of the overrides to ensure that object pair collides as desired or not.

Now the only question is how to implement the two 'explicit override layers'. There are probably multiple different approaches, but here is my random take on it.

Similar to the category bit or the group number, each body can be given a number to identify and/or classify it. There is no restriction on whether objects can share the same number for this purpose (effectively acting as a classifier instead of an identifier). Let's call this number the collision-class (as a choice of word distinct from 'group' or 'category').

So every body has a collision-class (or not). Every body implicitly collides. Now, how does an object know which other objects it should NOT collide (the first override layer)?

We extend upon the bitset. Bits are efficient for storage, so it works for me. But how do we get past 32 (or is it 64) bits? You just make an array of bitsets. Then, every collision-class (which is a positive integer number) literally corresponds to a single bit in the bitset. If my bitsets are one byte (instead of 32 bits) long, I might have a no-collide filter of [0001, 0000, 0011, 0000, 0100]. Then if I intersect a body with a collision-class of 11, I access filter[11/4 | 0] and then bitwise & the result just like the category check 0011 & 0010 !== 0. In this case, our objects do not collide because of the no-collide override filter. The 0010 is derived from 11 by mapping 11 % 4 (which is 3) to 0010 assuming a little-endian bitset. The array is random access, which means it should be very good performance. The cost is lots of storage if you have a very large number of collision-classes. This is a weakness, but not a fatal flaw. Bits are implicitly dense. The arrays could be lazily generated (you can have thousands of collision-classes, but never make an array longer than necessary for it's greatest set bit). And lastly, objects/maps could serve as an excellent replacement whenever the configuration is sparse. e.g. instead of [0001, 0000, 0011, 0000, 0100], only store {'0':'0001', '2':'0011', '4':'0100'}

And now that we know which collision-classes are filtered to not collide by this override configuration, we implement the final override configuration layer in the same way (which objects should collide with which collision classes no matter what). i.e. the explicit layers 2 and 3 are implemented in the same way.

There are probably a number of flaws with the whole idea but this was one of those things that infects your brain and you just gotta come up with something. So there we go. I'm now exorcised of the collision-filter demon.

As far as confusion is concerned, I think the implementation is really tedious to explain, but the interface might be really simple. Everything implicitly collides, except when you tell them not to. In case you want to preserve a no-collide rule but add an exception to even that, you can do so.

[skeddles]

Seconding. The way its setup is really confusing, especially the bitmasks, and is impossible to figure out from the docs. I had to study the demos to get it working.