Improvements and ideas

[Genbox]

Hi Louis,

I've seen you active around the Box2D project, and it seems like you are keen to improve it and add features. I'm working on Velcro Physics, which is a Box2D port in C#, but extended with many new features such as path generators, better performance, concave polygons etc.

I'm interested in your port as it seems like you made some improvements and new features, but I have a hard time going through hundreds of files and look for them, so could we have a discussion here on what improvements you have made?

[louis-langholtz]

@Genbox Thank you for contacting me and expressing your interest in my fork of Box2D!

I've been using the top-level REAME.md file to provide an overview of the changes that I've made in my fork. I believe it should be the file that GitHub presents at the top-level of the fork. Sounds like this information isn't as easy to find however as I'd like it to be.

Here's the "run-down" that I've mentioned in that file:

• Exported symbols are now within the library namespace of box2d and are no longer preficed by b2.
• Mutable global variables in the library have been removed or replaced with runtime-time parameters.
• Preprocessor defines, except those used for include guards, have been replaced with C++ solutions or removed from the API.
• Rounded corner collisions.
• Capsule shapes (using 2-vertex PolygonShape instances).
• More stable polygon stacking.
• Shared shapes with friction, density, and restitution moved into them (from Fixture class) for reduced memory usage.
• Support for C++11's range-based loops and constant expressions.
• Unit tested via Google Test and over 400 tests.
• Compile-time support for double and long double floating-point types and 32-bit and 64-bit fixed-point types (in addition to float).
• Fully per-step run-time configurable (via StepConf).
• In-depth per-step return value statistics (via StepStats).
• Increased construction-time configurability of world instances (via World::Def).
• Various methods have been rewritten to be non-member non-friend functions.
• Various functions and procedures have been rewritten to be "pure functions".
• Testbed enhancements: per-step configurability, per-step statistics, ability to manipulate bodies while paused, and more.
• Testbed test additions: Half Pipe, iforce2d's Topdown Car, Orbiter, Newton's Cradle, and Spinning Circles.

I've been considering putting this information into a CHANGES file in the hopes of making it easier to find. Please let me know if you have any suggestions to this effect. Another place on GitHub where I've been documenting this kind of info is in the Projects tab. Hmm... maybe the Wiki would be even better for this.

[Genbox]

@louis-langholtz I should have clarified. I read the list of changes you made in the readme, but I just expect there to be more hidden in the ~1400 commits you have made. There always are :)

Your list is a place to start. Velcro Physics is written in C# where many of the changes you have made (namespaces, solution, global variables, non-member function etc.) is best practices, so I already did them way back in 2007 when I first ported Box2D. However, I'm very interested in rounded corner collisions, stable stacking and the physics stuff, as I think it can really improve the physics experience.

I'd also be very interested in the unit tests you wrote (wow - 400 seems like a lot). I am a big fan of formal verification, and I always planned to have code contacts implemented, but since Microsoft pretty much killed it along with XNA (the framework I used for drawing in Farseer Physics Engine), I have to fall back to comprehensive unit tests instead.

[louis-langholtz]

Thank you for the clarification.

Eric Cato wrote about the mathematics he used in publications that I've read which have impressed me. I'd like to do the caliber of formal mathematical analysis that he's done but I'm afraid my math skills right now aren't up to his level (particularly in regards to differential equations - ODEs and PDEs). If they were, I'd love to relate what I did regarding rounded corner collisions and other physics stuff that way.

I have made some posts in which I discussed the physics changes in what I suppose could be called more like "layman's terms". My posts haven't been comprehensive either as really I've been having a blast working on evolving the C++ library into my own vision for it and haven't paid much attention to documenting about it; perhaps at least not as much as I should.

What do you see a conversation about the physics changes looking like or what would you like that to look like?

[Genbox]

I guess I will have a better idea once I dive into the code and dig up some of the changes. For now, I have to go though ALL of Box2D and synchronize my port with changes made the past 4 years. After I'm done with that, I'll come back here and take a deeper look into what changes you made.

As for the formal verification, I'm much like you. Eric is on a level I can only dream of, so most of the formal verification will be against a specification based on behavior rather than the math. It is more setting up some constraints on what input/output a method works with, and then have a static analysis tool sit in the background and analyse if you break those rules at any point in time, while developing.

[louis-langholtz]

Just an FYI update to this thread: I just added compile-time support for strongly-typed physical units. So no more needing to guess what the units are supposed to be for any given functions (unless they required unit-less, a.k.a. dimensionless, value like ratios). So for example, if the function or method took a length, it now takes that parameter as a Length type where Meter defines the unit of that parameter.

[Genbox]

Are those some sort of type constraints in newer versions of C++? I mean, like functional languages where you can define an integer to have only the numbers from 5 to 10?

[louis-langholtz]

This new units interface places no restrictions on the range of the values; only on the types of the values.

That said, I've also been working on ideas and code for doing range restrictions. Some of which is already in place. Like for iteration count types such as ts_iters_t which is for time step iterations and restricts the range to positive integers between 0 and 255. That just trivially uses an underlying unsigned 1-byte data type (std::uint8_t) however.

[Genbox]

I've just stumbled upon one of the things I made this issue for.
I ported over some of your unit tests for AABB and noticed it failed. However, my code was right and it failed in Box2D as well, so I looked other places where you had differences, and finally found that you do some reordering in the AABB constructor.

Since the engine itself would never give an AABB in the wrong order, I think it would be for the better to implement it only for user supplied data for performance reasons.

[Genbox]

I only now notices that Box2D never uses the constructor itself, only user supplied data goes in the constructor.

[louis-langholtz]

Is there an improvement you have in mind for the AABB class then? I'm not sure that I understand your last two comments about the AABB implementation/design but would like to be sure. :)

[louis-langholtz]

Just looked at the use of the AABB class more. Yes, there are places in the code where the AABB gets initialized with already minimized and maximized points only to have the constructor recheck that to ensure it's invariant about that.

I am updating the AABB interface to avoid this recheck while still being able to enforce the invariant.

[louis-langholtz]

Update: with commit d361c51, I've just introduced what I consider a major change to the Manifold calculation mechanism.

By design, this change does away with need of "ghost-vertices" at least for level surfaces. For a tutorial on what "ghost-vertices" are and why they were necessary see iforce2d's Box2D C++ tutorials - Ghost vertices.

A shortcoming with the "ghost-vertices" solution was that it only solves the polygon getting stuck while being dragged across chained edge-shapes problem. It doesn't apply to dragging a polygon across a level floor made of rectangles for instance. The new manifold calculation mechanism though solves this problem for any shapes forming a level surface.

[louis-langholtz]

Commit a952a62 introduces vertex-radius respecting RayCast functionality for all shapes now (not just for circle shapes anymore).

[Genbox]

Wow Louis.

I have a couple of questions:

1. I'd love to get rid of ghost vertices. They create confusion for the users and should really be an internal thing. I've gotten rid of most of the confusion by creating a factory that assembles chainshapes and hook up vertex0/3 automatically. I'm sure Erin is very interested in your solution.

2. What does vertex-radius respecting raycast mean? I thought radius (in Box2D) was mainly used for the CCD.

3. It seems DistanceProxy etc. exist to create a clean separation between algorithms. It seems you are removing them in your refactorings - is there a reason for that?

[Genbox]

I tested the performance of different line intersection algorithms, I found that it is sometimes faster to do a quick AABB check before the intersection code. The AABB check is just a couple of range comparisons compared to at least 2 div instructions and sometimes sqrt. It might be different with C/C++ compilers though which are usually more aggressive in their optimizations compared to C#.

[louis-langholtz]

I'm sure Erin is very interested in your solution.

I'd love it if he was/is interested in this!

I don't know how to contact him about my solution. Should I just post something about this on his Box2D Forum pages? I'd started a thread a while ago related to this but it was an open question and got no responses.

What does vertex-radius respecting raycast mean? I thought radius (in Box2D) was mainly used for the CCD.

Glad you asked! Yes, radius had been used mainly for the "CCD". Inconsistently.

Some shape-shape collision handling (like in b2EPCollider::Collide) ignored the shape radius and instead just used a hard-coded multiple of b2_linearSlop. Some shape-shape collision handling essentially treated the radius as a linear amount to translate and scale edges out by (in the direction of their normals) such that the edges still intersected and created a "skin" buffer. I opened issues (428 and 429) for these things on Erin's Box2D GitHub web pages.

I'd changed how radius was handled so that it's always treated as a circular concept for CCD and collision manifold calculations in terms of separation distances. The "vertex-radius respecting RayCast" now adds that circular interpretation to ray-casting as well.

I think this is easier to understand when the radius is in the visible size range. Imagine an EdgeShape whose length (between its vertices) is 1 meter and whose radius is also 1 meter. When its "skin" is drawn, this edge looks like a capsule now.

Here's an image of a triangle (PolygonShape) and an edge (also implemented using a PolygonShape but it could have also be constructed from an EdgeShape and treated the same way) where both have visibly large radius's:

The commit that introduces vertex radius respecting RayCast makes the casted ray also recognize this "skin" and it's rounding. This extends to ray-casting the concept of all objects having area now (beyond how distance calculations and overlap resolution handled it). I'd already added code to take the radius into account in calculating mass but hadn't extended the handling of the radius to the ray-casting before.

More generally speaking...

An admitted potential downside of this, is more calculations getting done per world step. I've also changed the internal algorithms however and intend to make more optimizations that should in the end be faster at least in some ways.

The upside, though, for me, is really exciting!

One of these upsides, is like you've recognized, the handling of bodies getting dragged across composite surfaces without getting stuck and without the use of "ghost-vertices".

It seems DistanceProxy etc. exist to create a clean separation between algorithms. It seems you are removing them in your refactorings - is there a reason for that?

That's really cool to me that you're looking at my changes in terms of the refactorings they're doing!!

Regarding DistanceProxy, they're actually seeing a more important/prominent role for me. This is another upside. Code that had been shape plus child-index based, has now - with the ray casting code change - been entirely refactored to be based on the decomposition of:

1. Get the "child" of the shape based on the "child's" index: shape.GetChild(childIndex).
2. Do with the "child" now what formerly would have been done by methods of the shape.

So instead of calling something like:

const auto result = shape.RayCast(input, childIndex, transform);

The code now calls:

const auto child = shape.GetChild(childIndex);
const auto result = RayCast(child, input, transform);

Or potentially:

const auto result = RayCast(shape.GetChild(childIndex), input, transform);

Where this child is actually the DistanceProxy.

The advantage to me, is greater re-use of code and looser coupling. I was able to toss away the shape specific RayCast and ComputeAABB methods and code and replace these with a single RayCast function and a single ComputeAABB function where these just take this child primitive.

This looser coupling, extends also to the manifold calculating code. Instead of dealing with contacts as contacts between a chain and circle or edge and polygon, my code more simply just deals with contacts between the two children as DistanceProxy objects. I got rid of all the subclasses of Contact since these aren't needed now.

With contacts all being handled as between children (instead of being between shape types), down fell the need for the shape types enum. So that's gone now too with a Visitor interface to replace it for stuff like serialization (the dump code), and the Testbed's shape drawing.

[Genbox]

I don't know how to contact him about my solution.
GitHub is the best way it seems. He is not active in the sense that he is maintaining Box2D, it serves more as a PoC for guys like you and me to improve and distribute. if you managed to wrap up your changes into some nice pull requests (more on this further down) at least people would be able to apply it to their forks.

As I see it, what you have going here is a nice testbed for experimentation and you can make the code to your taste. I've done the same thing with Velcro Physics, but mostly outside the engine (utilities, micro-optimizations, etc.), It is not interesting to backport into Box2D. However, what you have here are improvements to the engine itself and could solve some of the issues people are having out there.

As you know, with engines like this, performance is everything. As long as the algorithms (SAT, dynamic tree, newton integration etc.) are the same speed or better, then people don't really care. All they see is a black box with some knobs and switches they can play with.

I love that you have made an alternative solution to the ghost vertices problem - it might be slower and have problems on its own, but it is worth doing in a testbed like your to see what potential it has, and once you have tested and benchmarked it, it would be a really nice thing to backport into Box2D. You literally have hundreds of changeset, and users don't care about most of them, so I think the best course of action here, is to do some test/benchmarks, and then fork a clean Box2D, to which you port the changes. That way, people can easily checkout your version, compile it like they are used to and just copy&paste the new DLL into their game.

[Genbox]

As for the refactorings and cleaner code, I'm all for it. I love good separation with clean boundaries that can still be fast and flexible. The stuff you have done with simplifying shapes, manifolds, and raycast is the same thing I'm currently doing, I'm just waaaay behind you since I barely just started again.

That being said, I don't pretend to understand many of the changes you have made, which is exactly why I created this issue. I like your explanations and level of detail - it really helps.

[louis-langholtz]

Another new improvement: commit 04f9188 adds "early out" processing to velocity constraints resolution.

[louis-langholtz]

Commit 2fe4135 brings support for any/all shapes:

1. to be used with dynamic bodies,
2. to be identified (via TestPoint), and
3. to collide with any/all other shapes.

I.e. I've added support for selectable and dynamic, chain and edge shapes.

[Genbox]

Selectable and dynamic? What kind of sorcery is this?

[louis-langholtz]

@Genbox Not sure what you mean but hope the new changes are exciting! ;)

In case, what I meant by selectable isn't clear for everyone... it's whether the TestPoint function is supported for a given shape type. I'd refactored TestPoint to work based on DistanceProxy objects instead of being a virtual method of Shape (which hadn't been implemented before for all shape types). So now the bool TestPoint(const Shape& shape, const Length2D pLocal) noexcept convenience function can be called to test whether a point is within any shape type, including chain and edge shapes (that have a larger than zero vertex radius sizes).

As for "collide with any/all other shapes"... I had also added MassData calculation support for chain and edge shapes so that now all shapes support having mass. That paired with changes I'd made previously that provide for manifold calculations for any pair of shape types, means all shape types should now be able to be used in dynamic bodies and all should have collision processing done for them. Think chain-chain collisions - they're supported now. Or "hula" hooping with looped ChainShape shapes.

[louis-langholtz]

With commit 1988b9e I've added full deep copy construction and copy assignment support for World instances. This represents a snapshotting capability which includes all state (even bodies' time remaining till sleep, the broad phase state data, and contact warm start data).

[louis-langholtz]

This issue was moved to louis-langholtz/PlayRho#12