Improvements and ideas

[louis-langholtz]

From @Genbox on April 2, 2017 11:46

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?

Copied from original issue: louis-langholtz/Box2D#12

[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.

[louis-langholtz]

From @Genbox on April 6, 2017 20:38

@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?

[louis-langholtz]

From @Genbox on April 7, 2017 22:43

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.

[louis-langholtz]

From @Genbox on April 13, 2017 11:0

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.

[louis-langholtz]

From @Genbox on April 13, 2017 22:17

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.

[louis-langholtz]

From @Genbox on April 13, 2017 22:32

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).

[louis-langholtz]

From @Genbox on April 30, 2017 9:28

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?

[louis-langholtz]

From @Genbox on April 30, 2017 9:44

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.

[louis-langholtz]

From @Genbox on April 30, 2017 21:17

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.

[louis-langholtz]

From @Genbox on April 30, 2017 21:29

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.

[louis-langholtz]

From @Genbox on May 29, 2017 20:42

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).

[Alan-FGR]

Guys, I didn't read the whole discussion, but there is some awesome stuff here!

What are your opinions on multi-threading, and hardware acceleration (both on CPU and GPU)? I'm personally using Chipmunk not only because spatial hash proved to be a better optimization, but also because of the multi-threaded solver which along with the overall optimization of the engine is capable of outputting manyfold faster results compared to Box2D.

These days the 3D engines are going GPU for acceleration, neither solution is robust though, Bullet has that in the works since forever and it's still far from mature, however, Bullet got that planar 2D stuff which allows you to simulate 2D physics I assume without some terribly inefficiency or other caveats (sim quality of 3D constrained to 2D used to be terrible), so I wonder if this will still be relevant once they roll out Bullet 3 which I guess will certainly suppress Box2D a lot in the indie scene.

On a related note, it's too bad that it's not easy to point all the Box2D users here... Box2D isn't collaboration friendly and honestly is quite dead at this point. This should be much more popular :(. Even LiquidFun which is unmaintained and buggy to unusable levels is popular as heck, while PlayRho has only 7 stars so far :(.

[Alan-FGR]

Also, what about allowing access to some advanced configuration like the Baumgarte scale (and provide good defaults and examples) as you have in Unity. I don't like Unity but they got some stuff right imho... and their "2D Physics" is for some reason much better than Box2D with the same timing and iteration settings, probably because those vars are fine-tuned. Massive stacks for example are way more solid and much less 'springy'... there's way less penetration, and overall the simulation runs much faster too because since there's less penetration there's less overlapping thus less contacts.

[Alan-FGR]

Also, fluid simulation like LiquidFun maybe :P... just dropping random thoughts here :). LiquidFun is SIMD'd but has some pretty serious showstopping flaws

[NauticalMile64]

@Genbox SPH makes the most sense to me. I did a project on CFD in video games a few years back comparing the different discretizations and SPH seemed to be the most stable, and produced the most visually appealing results. As part of the project I got Intel's TBB up and running and ran the samples (I think they're included here). There's also an in-depth 19-part blog series on the physics and code which starts here. I only went through the SPH discretization for that project, so I'd need to take some time to review it.

That being said, that was 2013, and I things may have changed since then, and I'm more knowledgeable as well. As a university student, I have access to much of the literature. I can't share most papers with you (legally) but I'd be happy to do some rooting around in the literature and online (probably ~2 weeks or so) to see what the most promising methods might be. I gotta get myself familiar with the PlayRho code as well. I'll make a new thread to summarize my findings, but if you want to start one sooner with your thoughts and ideas please do.

[Genbox]

@NauticalMile64 You just ruined my evening movie in favor of some reading 👍 good stuff!

I'm not associated with PlayRho. I'm just curious about all the awesome stuff @louis-langholtz is doing, I have a Box2D port written in C# over at Velcro Physics where I play around when I'm bored.

However, I will be monitoring this thread closely as always.

[louis-langholtz]

The Manifold Class

I've looked at the Manifold class and its derivation enough that I was able to figure out solutions like to the problem of boxes getting stuck when sliding across a surface of boxes. And there's things about it that bug me.

Sometimes the collision manifold is computed to have two points of contact, sometimes one, and sometimes none. Sometimes the manifold is a circles type, sometimes a face-A type, and sometimes a face-B type. Additionally the points of contact can be vertex points or face points.

By my calculations a manifold is 58-bytes large (with 4-byte float) with 20 bytes unused for single collision point manifolds. The type, #-points-of-contact, and vertex-vs-face contact feature types combinations require multiple levels of branching.

Is there a more efficient way to express the collision manifold? I'd really like a more efficient way to get what we need out of the manifold and I'd like that way to be easier to describe any invariants than what we have now with the current Manifold.

In 3-D in real-life, I'd say one needs at least 3 legs to get a table to stand up stable. In 2-D, just 2 legs suffice. Is that the logic behind why Box2D manifolds can have up to 2 points of contact? I've come across some literature somewhere that suggested that indeed that's why there needs to be up to 2 points of contact in 2D (and up to 3 in 3-D) for physics engines to deliver the stability expected like with things like stacking boxes.

Is that really true for the mathematical model that a physics engine is doing however? Anybody know?

I'd much rather a manifold be just a world point paired with a surface normal. Two fields with no invariants between them and just 16-bytes. Move the impulses into the Contact data structure. I haven't tried this yet though; only gotten to the point of considering whether it's conceptually equivalent. If it can work, it should simplify significant portions of some of the more computationally involved code and provide some speedup.

[Genbox]

The manifold solver is indeed made to support 1 & 2 points to support stacking. I remember a presentation Erin did 10 years back where he discussed how solving 2 points was basically the same as 1 point due to the algorithm used, but provided a lot more stability for stacking.

I don't remember the nitty gritty about how manifolds are created, and don't have the code in front of me - are you sure they are created when there are no contacts? Seems like a waste.

[Genbox]

I found the presentation. The part about determining contacts and manifolds is not in the slides though.

[louis-langholtz]

@Genbox Looking at the Box2D sources, specifically collide functions like b2CollideCircles, we can see that they can return with the manifold's point count set to 0. That's what I meant by saying they can be computed with no points of contact. Sorry if I wrote that poorly before.

I don't know if single points of contact can be made to be as stable as two points but I want to eliminate as much branching as possible that goes on with manifold usage and I want to shrink its memory usage too. Secondarily, I want the manifold class (a struct-class) to have clearer and more easily expressed invariants (if it has to have any). As it is in Box2D, it's a struct class but its usage has invariants even though those aren't encapsulated in an OO sense.

I'd love discussion about this. For examples...

There's really no need to have the contact point count for instance be its own 4-byte int32 variable. The value can only be 0, 1, or 2 and can be encoded into the type field or the points field (using a sentinel like NaN in a field in b2ManifoldPoint).

We could also just use zero values in a 2nd manifold point in cases where there's only 1 actual point of contact. That would save on needing to branch based on the point count. Not sure if this would foul up the block-solver though but it's something I've been thinking about.

[louis-langholtz]

In terms of improvements and ideas, while perhaps ancillary to physics engine/library ideas/improvements, but still important in terms of giving users increased understanding of what's possible, I've just yesterday added a new Entity Editor to the Testbed (via pull request #188). Here's a screen shot of it in action on the Joints Overview Test:

Please note that this editing capability doesn't allow for creating or destroying physical entities; at least not presently. Also the new interface is not tuned yet to prevent or handle illegal settings which could cause exceptions or crashes.

[Alan-FGR]

Hello. I've been following the discussion here but I honestly feel they're a bit beyond my understanding, I don't fully understand that manifold talk, but regarding stability, I use the Nvidia PhysX library for 3D physics and there are some flags to enable some tricks for stability and sim quality, most notably "adaptive force", "stabilization" and "average point" may substantially improve the results depending on the use case. Not sure whether that means anything to you but just wanted to point that out in case you're wondering if any of these methods yield usable results for real-life applications.
Keep up the good work! :)

[louis-langholtz]

Latest improvement: blowing away the between 0.1 to 10 meter rule... now supporting literally 1 to 1 Solar System scales for movement and collision handling. I feel very excited about that! Build with Real set to double and see the Testbed "Solar System" Test. Not the pretties graphics but I love seeing what giant bombs do when hurtling through our system! 😃

[Alan-FGR]

So is it possible to have scenes the size of our solar system while still having precision for human-sized characters just by using doubles? I could be wrong but last I checked it wasn't possible to do that naively not even with double precision.

[Hexlord]

Yep, the fanciness ends when the relative scaling applies. The problem of meter rule is that ratio of smallest 1 to biggest 100 works okay, but objects exceeding this range disrupt stability of the simulation (performance problems, staggering, etc). So scaling linear slop and stuff to match the size of planet is okay, but that is not the solution to the root of the problem.

Yet double precision seems to help a bit.

I think some code could be integrated to solver so that big objects ignore small ones (act as kinematic) while small objects are blown away by big objects, this could help with artifacts during such interactions. And together with that you could try resolving small object collisions with lower slopping and stuff, so that double configuration is applied. But that probably leads to a size-relative configuration model of slopping (k*S + c). Probably need to experiment with this.

__

Also wanted to note that an option (#define or smth) to disable vertex radius collision would be priceless in scenarios where performance is extremely important as it is the only extra functionality of playrho that you pay for with your very blood.

[louis-langholtz]

@Alan-FGR

So is it possible to have scenes the size of our solar system while still having precision for human-sized characters just by using doubles?

I love this question!

Please correct me if/where I'm wrong...

I believe the answer ultimately comes from what's possible in terms of numerical fidelity of whatever type is being used for the Real type alias. I have been experimenting and making changes to the PlayRho code to be more robust in the face of potential range issues with this underlying type. I think you're correct however in that things still are problematic for floating point types dealing with two values where one is much larger in magnitude than the other.

In the scenario you're asking about we have some 2 meters at one end of the size spectrum and 696342000 meters on the other. Roughly 8-orders of magnitude difference in decimal digits. IEEE 754 single precision binary floating point format has as little as 6 significant decimal digits precision. Meanwhile IEEE 754 double precision format has at least 15 significant decimal digits precision. So looking at these types, I believe the answer — at least theoretically — is a solid no for float and a possible yes for double.

In practice however, I suspect many interactions between human sizes and Sun sizes even with double for Real won't work well-enough especially as speeds and masses relevant to these kinds of objects are used.

As I believe Hexlord is pointing out, using alternate notions of collisions or alternative solutions for collisions is another avenue to pursue for handling such situations. Right now, I see collisions as being dealt with from a third party perspective; that of the viewer. Depth of penetration for TOI calculations or the linear slop value for instance are absolute values that make the most sense to me when a viewer is viewing a scene at a scale relevant to those values. I can imagine using relative values instead like a percentage value for depth of penetration (vs. the total radius) that would have more robust handling characteristics in perhaps more dynamic collision scenarios however.

[Alan-FGR]

I love this question!

😄 and I loved your answer!

I agree with you and @Hexlord. Although it would be nice to be able to simulate such huge spaces and high scale/mass ratios, perhaps there are few use cases for that, especially considering that you'll probably need a high number of the smaller objects to populate such large areas in an interesting way, so having all of that running simultaneously probably is a going to be a problem bigger than precision, it's probably going to take some time until we can have those scenes naively without tricks/hacks. Perhaps at that time 128bit floats will be commonplace, I guess even these days one could achieve decent performance using SIMD 128bit registers (could be 100% wrong here), but then again, it doesn't sound something very practical, although it could surely be interesting and useful for some edge cases.

[ninnghazad]

dynamic/relative penetration/slop sounds nice. maximum usable scale differences are of importance to me at least - and proper interaction between something human-sized and possibly moon-sized (or at least multiple magnitudes larger) sounds awesome. i'd gladly trade performance for possibility in that case.
as @Alan-FGR said, it might be an edge-case. then again - as long as it isn't easily possible, of course it is.
think kerbal-space-program in 2d, surely would be fun. they use some heavy tricks to simulate at largely different scales - would be nice to be able to do something like that with an out-of-the-box physics lib and without rescaling the whole world or the like. but yeah, space-stuff mainly i guess.
a dynamic approach to penetration/slop however i'd image to be beneficial aside from the whole stellar-scales thing. maybe i am imagining it wrong, but having TOI-overlap relative to colliders' size seems like a good idea.

[Hexlord]

I've seen some interesting idea in gpu-physics.js by schteppe: gif maybe interpreting small objects as radius-vertex geometry instead of volume geometry when interacting with big objects can ease resolving the conflict, maybe even consider a group of small objects as an area-rectangle interacting with big object, but that for sure will require lots of nancy stuff, just the extra thoughts.

Relative slop & penetration may help, but the performance hit is still tremendous for TOI when huge asteroid of 500 fixture-triangle geometry flies upon 100 tiny triangles. I know very few how this stuff works, but the TOI not being optimized for multiple contacts incoming is an experimental observation as it lags all the way since small stuff is radius-close to the big object, that's when TOI starts to predict solving equation or something. That is not a very common scenario yet it happens.

[ninnghazad]

@Hexlord performance hit: huge astroid could be represented by single/few chain shapes or chained boxed just representing it's surface. worked way faster for me when doing some tests with box2d a while ago. and the 100 tiny triangles, should they all be of equal size, could be done using particlesystem like in liquidfun. if it's 100 unique objects, i guess that'll be slow(er) even without any astroids around.
EDIT: well, the triangles would have to be round triangles also ;)

[Hexlord]

@ninnghazad yep, but chain shapes do not support holes. triangles are just the result of triangulation of geometry with holes, so liquidfun solution sadly won't work. 100 small objects work just fine if they meet small objects like eachother... Well that seems to be quite another problem as one mentioned before, yet still.
Thank you for the note, I'll try to optimize it by splitting geometry to be hole-less with multiple chain shapes connected, maybe this will actually help in a way.

[louis-langholtz]

Incidentally, I've been considering what it'd take to implement a "negative" of a shape for implementing holes. I'd like that very much as we could for example have an inner disk (circle) shape be the negative of an outer one and have fully round rolling without jagged approximations.

I believe that the plausibility of negative shapes has some corroboration in the implementation of the false condition of the joint collide connected property. It may be a while to implement negative shapes though since I first want to refactor contacts and joints into being subclasses of a constraint base class and then develop a better understanding of how ordering effects simulations. Ordering I can see then begetting constraint hierarchy which seems necessary for negative shapes.

[louis-langholtz]

@Hexlord Help me understand what you're describing in:

Also wanted to note that an option (#define or smth) to disable vertex radius collision would be priceless in scenarios where performance is extremely important as it is the only extra functionality of playrho that you pay for with your very blood.

Do you mean simulating only velocity and acceleration and not simulating collisions? If you could reference specific code perhaps, that'd help me a bunch!

Also, it's absolutely critical to make sure that we're using a release build of the library — i.e. with compiler optimization enabled to the fullest (-O3) and assert's disabled with the NDEBUG pre-processor macro defined — when looking into any speed related performance issues.

[Hexlord]

@louis-langholtz Sorry for my puzzling description of what I mean. I did not inspect the new code very precisely, but it seems like some checks are unavoidable even if all vertices of all the bodies have 0 radius, slowing the performance. They seem relatively cheap for 0-radius case, but still that is the only misstep from max-performance way, so that probably should be optional (#ifdef PLAYRHO_VERTEX_RADIUS or smth).

I support run-time configuration, but this functionality is high-load and four if-s can really mess the cpu performance...

[louis-langholtz]

@Hexlord I agree that four if's looks concerning but how concerning is it on a given hardware architecture in terms of reliably measurable performance loss? I ask because I don't know.

My hope is that the Benchmark application will be increasingly used to measure these places (by calling the existing routines) and also to measure alternative coding strategies. Alternative functions can be added directly within the Benchmark itself to start with and possibly get migrated into the library as they prove useful.

In terms of preprocessing out some of the GetFaceManifold code like you're suggesting, I believe that could change the operational semantics in ways that become less consistent. The TOI code for instance needs to be in sync with the concept of the skin. If the skin shape changes, then the TOI calculating code also needs to be updated to reflect this shape. Part of what got me to do the rounded corner skin shapes to begin with was a concern that was growing for me that the TOI calculating code in Box2D was measuring as though the skin was rounded while the manifold generating code wasn't returning manifolds that reflected similarly rounded corners. This reminds me that I've been meaning to revisit the PlayRho unit test code to ensure this kind of consistency.

Incidentally, what I'm more sure of is that I really dislike the length and complexity of the GetFaceManifold function starting with its parameters (8 of them and I blame myself in part for its length and complexity). I want to believe that the whole way it's doing its stuff could be done more simply and that refactoring it can improve execution speed too.

As another related side note, the alternative method for detecting almost equal that you'd provided for instance showed itself to be faster (which I saw after I increased the sensitivity of many of the tests in the benchmark application). It or the almost equal related unit tests however need some tweaks worked on since they don't match up exactly and can only be used on platforms where float and double are is_iec559 compliant I believe (in case you're interested in that 😄 ).

[Hexlord]

@louis-langholtz
I would reference Migdalskiy' talk, slide 46 proves it to be a maximum of ~60 extra ticks due to misprediction (4 connected if branches), which is, given random Radius distribution between being zero and non-zero would give aprxly 30 * num_vertex extra ticks per frame, given 3 GHz cpu and 10000 vertices processed that is an extra 0.1 ms.

Actually if you always use zero radius that would be just one tick thanks to prediction, so not a problem at all...

Cool stuff! Could be an experimental feature, but probably its win is not considerable in the whole simulation.

[NauticalMile64]

Just for reference, I'll note that Algodoo gives the ability to use shapes to clip one another, kind of like Snipperclips. Closed source code though :(

[Alan-FGR]

@NauticalMile64 yes but it converts those clipped shapes into polygon shapes, so basically it's just a way to edit polygon shapes; internally it doesn't support a colliders described by booleans I think (I'm pretty sure).

[iderik]

Hi, it seems flipping (vertically) bodies in Box2D is an obstacle for many users, since its quite common for 2D games with a side perspective.

I did recently came into this problem, which feels like a dead end for my project. Imagine I have an excavator with multiple joints (wheels and a boom, which has a bucket jointed to it). If its facing a direction and then wants to move the other way, it has to flip/mirror/reflect vertically.

Currently, the only solutions are quite complex. Recreating all the bodies, shapes, fixtures and joints, plus all the joints' bodies. Or having pre-created bodies of both directions and "hide" one of the direction from the Box2D and switch when a flip needs to happen.

I was wondering what do you think about this and if a feature to simplify this would have a chance to be implemented. It would really help us less experienced users and may be migrate more Box2D users over to PlayRho.

[louis-langholtz]

@iderik Hello and thanks for your suggestion!

Here's some thoughts that come to me at the moment regarding your proposal.

The flipping that you're asking about sounds in part like a reflection transformation matrix applied to the coordinates of the shapes in order to derive reflected shapes. A free function operating over an iterable range of shapes that mutated those shapes per the transformation sounds doable and appealing to provide.

This could probably benefit from extending the Shape concept to include a transform operation. I've created issue #283 now to add this extended functionality to the Shape class. Such work may also help with issue #276. I've also created issue #285 for adding code that produces the reflection matrices needed for transforming shapes against a given direction through the origin.

Reflecting joints sounds like another part to what you're asking for. I think it'd be a more involved than the former part of this and probably has to be done on a joint type by joint type basis. I've been considering a redesign of joints to replace the use of public inheritance with the same kind of on-use polymorphic design that Shape now uses. I mention that because it may be worth waiting till that gets done to tackle this other part of what you're asking for.

I suspect the overall functionality would still need to effectively do the complex solution. I like the idea of providing free function code that takes care of those details however so to the user this at least looks simpler.

[louis-langholtz]

From @Genbox on April 2, 2017 11:46
...
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?

I've just merged in pull request #346. This introduces some new changes that I'm very excited about and greatly improve this library in my opinion. Here's a partial list of these improvements:

• Switched to value semantics. User code no longer deals with pointers to bodies, fixtures, contacts, nor joints. The API instead uses strong-typed indexes to reference them. Besides value-semantics being easier to reason about, this has opened the doors to more contiguous - i.e. cache friendly - memory accesses.
• Moved the implementation behind a compilation firewall. The World class is now just a PIMPL holding wrapper. This will facilitate future optimization work with less need to change the binary interface to user applications.
• Extended the use of polymorphic values to joints. The Shape class design was already providing a polymorphic value type and now the Joint class does as well. Derived classes of Joint - like RevoluteJoint - have been replaced with the instantiation of the Joint type with the value of any type supporting the Joint concept. So, for example, now creating a RevoluteJoint is instead done by creating a joint with a RevoluteJointConf value.
• Behind the scenes, low level implementation details have moved to the WorldImpl class and there are no longer any friend classes that co-mingle in the implementation.