Increase usability of broadphases

[mtsamis]

I'm working on some improvements for the CCD which give huge performance gains. I need to use a broadphase detector that acts just on bodies, but all broadphases currently only work with <Body, Fixture> pairs. I was thinking that broadphases are useful in a wide range of scenarios, not just for <Body, Fixture> pairs.

It would be useful (maybe?) to make them more general, that is they should work for any 'object' with a corresponding 'createAABB' method.
@wnbittle I'm searching for some design ideas on how to achieve this while not changing much the current interface of broadphase detectors (Maybe a more general broadphase class which has a subclass that provides the exact functionality they currently have?).
The CCD improvement is huge, so this is overall quite useful.

Any help/discussion apreciated

[wnbittle]

A more general broadphase definition would be the right approach. If it were me, I wouldn't hesitate to break compatibility a bit if it makes for a better or clearer design (similar to our getRotation discussion earlier).

I would have it operate on Shape objects, since any shape should be able to produce an AABB. In addition, if we ever wanted to try out a Circle-Circle detector or OBB detector we could add more methods (createBoundingCircle, createOBB).

[mtsamis]

Good to know that you support the idea. I'm going for something more general that the Shape class; For my own use case with the CCD improvement, what I need is to support broadphase detection once per body (so could be multiple shapes) with AABBs for detection being created by createSweptAABB (that is I need support for creating AABBs with an arbitrary method).

I'm currently thinking that the most general approach is

interface BroadphaseObject {
   public AABB createAABB();
   public boolean equals(Object o);
   public int hashCode();
}

and

BroadphaseDetector<E extends BroadphaseObject>

Then we'll have all broadphases work just with BroadphaseObjects.
I intentionally added equals and hashCode; with this setup we can support out of the box the use of hashtables in broadphases without the extra BroadphasePair stuff (as well detect can return simply List<BroadphaseObject>).

One question with this setup is: for the current use case of broadphases, should BodyFixtures implement this interface directly or should another class exist that stores a Fixture and Body?
I think it would be very cool to have fixtures implement it because then we can just work with fixtures on the broadphase, but that requires an extra Body field in the fixture to know which body owns each fixture.
On the other hand we can have extra class but adding and getting those from the broadphase will incur some syntactic and mental (and performance?) overhead.

How do all these sound to you? I'm interested about your opinion about whether we can add that extra Body field in fixtures for the added convenience and a clean interface.

[wnbittle]

I'd was thinking something like this:

package geometry;
public interface Bounded {
    public AABB createAABB();
    public AABB createAABB(Transform transform);
    public Circle createBoundingCircle();
    public Rectangle createOBB();
    ...
}

package dynamics;
public interface TemporallyBounded {
    public AABB createSweptAABB();
    public Capsule createSweptCircle();
    ...
}

public Shape implements Bounded ...
public Fixture implements Bounded ...
public Body implements Bounded, TemporallyBounded ...
...

My thought is that a bounded "object" is a more general concept than an object being useful for a Broadphase collision detection algorithm. Instead its a geometric concept. Naturally, all we need right now is createAABB, but this would allow us to expand to use other bounding types in the future. This also allows us to define the Bounded contract where it belongs in the geometry package without a (at least by name) coupling to the broadphase package.

The only downside of operating at the Body level in the Broadphase is with multi-fixture bodies. Once you detect via the Broadphase that two bodies are potentially intersecting, you now have to use a Narrowphase against every pair of fixtures (n*m tests).

The downside of having it Fixture based is the requirement of the body field. I've done this before, but always internal only - it shouldn't be exposed externally. I don't think we'll be able to keep the field internal because the broadphase code is in another package.

I would just keep the current design of a BroadphaseItem for now - I'm totally ok with some overhead in favor of a cleaner API.

[mtsamis]

An additional interface describing geometric primitives is fine with me, but this does not solve my needs for a general broadphase. How will a broadphase work with either Bounded or TemporarilyBounded? How will it work with anything else than these?
By the way, I did not suggest to use broadphase only for bodies and not for fixtures in general. I need this functionality just for the new CCD.
Lastly I don’t think we should ‘require’ shapes to be able create bounding circles and other shapes.
This can be difficult for current or future shapes with not much gains in my opinion.
I have experimented in the past with a circle based or mixed shape broadphase but the overhead of shape operations was to big to bring any benefits.

I think I’ll try an implementation based on the notion of BroadphaseObject and see how I can reduce code duplication and keep the interface same or similar.
I’ll follow your comment and won’t add a Body field on the Fixture or other class. Also won’t make existing objects implement new interfaces.

The reason I need this change is because with the new CCD changes I’m making the performance gain is insane.
On my current simulation, with CCD.ALL mode simulation time goes from 12 seconds to 5.

If you want to provide any additional guidance feel free to comment here. I’ll add a link to my branch here as soon as I have some first working code.

[wnbittle]

An additional interface describing geometric primitives is fine with me, but this does not solve my needs for a general broadphase. How will a broadphase work with either Bounded or TemporarilyBounded? How will it work with anything else than these?

In my view, the interface BroadphaseObject is no different than the interface Bounded apart from the name. What am I missing?

The interface TemporarilyBounded was just an example of how I would split out the concept of "swept bounds" if that was something that you had in mind. If not - ignore it.

By the way, I did not suggest to use broadphase only for bodies and not for fixtures in general. I need this functionality just for the new CCD.

Not a problem, I must have misunderstood what you were saying.

Lastly I don’t think we should ‘require’ shapes to be able create bounding circles and other shapes.
This can be difficult for current or future shapes with not much gains in my opinion.

If you don't need it at the shape level - ignore it. The point I was trying to make was that the interface that describes the idea of "being bounded" could be applied/useful in many scenarios other than the Broadphase. For example, knowing the bounding shape (circle, AABB, OBB, etc) for a given Body - while not useful internally - could be useful to user code.

I have experimented in the past with a circle based or mixed shape broadphase but the overhead of shape operations was to big to bring any benefits.

Again, I'm not suggesting that we do any of these, but trying to drive home the idea that "being bounded" was a more general concept.

The reason I need this change is because with the new CCD changes I’m making the performance gain is insane.
On my current simulation, with CCD.ALL mode simulation time goes from 12 seconds to 5.

I appreciate all the contributions and I'm truly looking forward to it.

[mtsamis]

An additional interface describing geometric primitives is fine with me, but this does not solve my needs for a general broadphase. How will a broadphase work with either Bounded or TemporarilyBounded? How will it work with anything else than these?

In my view, the interface BroadphaseObject is no different than the interface Bounded apart from the name. What am I missing?

Thanks for the reply and further notes. They’re indeed functionally the same, I was actually confused because I had a different use case in my mind.
I wanted to make broadphases work just on a single object, that would be a BroadphaseObject. Making fixture Bounded here does not mean it can be added on a broadphase because it’s missing the information of which Body is the owner.
I would actually make a separate class that would hold a Body and Fixture and implement the BroadphaseObject interface, not have any existing classes implement it.

Your approach is better imo, but I somehow need to have broadphases work on a single Bounded object and not require extra information. It would be nice at that point to have a Body field in fixtures, but that requires even more changes in the library.

I’m not really sure what’s the desired solution at this point. I’ll give it some extra thought.

[wnbittle]

@mtsamis Are the changes you were thinking about implementing here still valid? Should we close this issue?

[mtsamis]

Hey, yeah we can close this. The discussion was good back then. I think the successor to this concept is your newer issue #122