Recent content on Box2D
In a previous post SIMD Matters I discussed the big wins I got from graph coloring to make the contact solver faster. That same approach exists in Box3D. I like to call this approach “wide SIMD”. The idea is to process multiple work units at the same time. In the contact solver this means solving four contact points at the same time.
This is different from “narrow SIMD”…
I’m happy to announce the release of Box3D, an open source 3D physics engine. It is now available on GitHub.
Box3D repository
You can think of Box3D as a fork of Box2D, extended with many features needed for 3D games. Some additions:
Triangle mesh collision Height-field collision Baked compound collision The core architecture of Box3D remains almost identical to Box2D.
C API…
Replay is a new system I developed for Box2D. The main goal is to allow users to send me files I can use to reproduce bugs. Because Box2D is open source, I can rarely run a user’s game or see their code in full context. This makes it hard to track down problems. Previously in v2.4 a user could use b2World::Dump to save a text file that let me reproduce bugs.
Version 3.0 was released about 8 months ago. It was a huge update and it needed some refinement. Version 3.1 addresses most of the bugs and build problems. It also introduces some new features and refinements.
Character mover I’ve added experimental character mover support to 3.1. This uses a geometric solver. It should be useful for games that want greater control than what you get with…
Dynamic Tree Insertion Dynamic tree insertion can be expensive if you try to optimize for some metric such as the surface area heuristic (SAH). The SAH tries find a node configuration that minimizes the total surface area of all internal nodes. The idea is to create fewer node visits for ray casts on average.
Insertion affects the surface area incrementally so it is essentially a greedy…
Determinism means many things when it comes to game development and especially physics engines. Generally in game development we like things to be repeatable. This makes debugging easier. This doesn’t rule out emergent behavior though because player input can be viewed as random.
Testing Determinism Determinism is a brittle feature. It is easy to break. Code changes can break it.…
SIMD in game development Often in game development we talk about SIMD. It is the holy grail of CPU performance, often out of reach. The conventional wisdom is that it is difficult to achieve real gains from SIMD.
It is tempting to build a math library around SIMD hoping to get some performance gains. However, it often has no proven benefit. It just feels good to be using something we know can…
Over 18 months ago I announced that I was working on Box2D version 3.0 (v3 for short). And it has finally arrived! It has been a long journey and I’ve learned a lot. There is more work to do, but the library is ready to be used for game development.
I’d like to thank the Box2D users who tested v3 during the alpha and beta. Their feedback and bug reports have been super helpful!
I was recently testing the Box2D version 3.0 alpha and found a stability problem. I found a fix for the problem fairly quickly, however the experience left me thinking about the progression of v3.0 and how the engine has been getting more features and more complexity. There are several joint types now. There is island management, multithreading, SIMD, graph coloring, continuous collision, and so…
Island management is a fundamental low level feature of physics engines and can have a big impact on solver design and performance. This was one of the first problems I decided to work on for Box2D version 3 (v3).
Since I began working on v3 I’ve been comparing several algorithms for island management. My goal has been to make island building scale better with multiple CPU cores. Here…
Over the holidays I started working on version 3.0 of Box2D. I started closing out some issues for v2.4 and then moved onto a backlog task: speculative collision. Speculative collision is a technique for continuous collision that promises to remove the serial bottleneck of time of impact sub-stepping. I made good progress in my research and then I realized that this would be a major update to…
Dealing with ghost collisions is a challenging problem in game physics. The basic idea comes from motion across a flat surface. You may have several shapes joined together to make a flat surface, like a triangle mesh in 3D or a chain of edges in 2D. Convex shapes can hit the internal connections and have their motion blocked. This is undesirable, we would rather have the convex shape move smoothly…
There a several computational geometry algorithms that are relevant for preparing collision data: convex hull, mesh simplification, and convex decomposition.
Many implementations of these algorithms are developed outside the specific context of rigid body simulation. For example, qhull computes convex hulls and appears to be application agnostic. Simplygon is focused on simplifying render…
Box2D has support for continuous collision. This solves the problem of fast moving objects passing through each other due to discrete time steps. The Box2D continuous collision algorithm uses a time of impact (TOI) collision algorithm along with time sub-stepping for the response.
There are other artifacts due to discrete time steps. Joint limits can also suffer from fast movement. For…
Hello! I’m Erin Catto. I work in the video game industry. I also created Box2D, a 2D physics engine for games.
I use this blog to give updates on Box2D and write about game physics and programming.
You can find Box2D on GitHub There is a Discord Server And there is a Subreddit This site was created using Hugo and a modified version of hello friend ng.
Suppose you have a plane equation in local space and you’d like to express that plane equation in world space. The plane in local space is written as:
$$P := (n, w)$$where \(n\) is the plane normal and \(w\) is the plane offset.
A point \(x\) is on the plane if
$$n \cdot x = w$$Now define a transform \(A\) as
$$A := (R, p)$$where \(R\) is an orthonormal rotation matrix and…
I’m now a moderator on the Box2D subreddit. So I think this makes it the official!
r/box2d
I look forward to seeing Box2D discussion on reddit.
Hi All! I created a Box2D server on Discord.
Discord
On a related note, I’m considering locking the forums because I’d rather spend my limited free time working on Box2D than maintaining the forums. I’ve looked for new moderators over the last year or so unsuccessfully. Also updating phpBB and dealing with spam is not my cup of tea.
In the future I’d like to see…
I received this question on LinkedIn:
I’m working on a 3d dynamic aabb tree based on the concepts of Presson’s bullet contribution. I came across a bullet forum thread in which Dirk recommended looking at your box2d implementation. I noticed the major difference is that box2d is a balanced tree using a surface area heuristic while bullet’s is unbalanced with manhattan…
Given a normalized 3D vector, here’s an efficient method for computing a full basis. The computed basis is axis aligned if the input vector is axis aligned.
void ComputeBasis(const Vec& a, Vec* b, Vec* c) { // Suppose vector a has all equal components and is a unit vector: // a = (s, s, s) // Then 3*s*s = 1, s = sqrt(1/3) = 0.57735. This means that at // least one component of a unit vector…
I ran into a problem computing a polygon normal using Newell’s method as described in Christer Ericson’s excellent book Real-Time Collision Detection. In this case the polygon happens to a be a triangle that is close to the origin. So I would guess that Newell’s method would yield a great result. However, this is not true. I only get 2 digits of accuracy in single…
The best way to use SSE is to use the __m128 intrinsic directly. Unfortunately Visual Studio displays the values backwards (w,z,y,x). Bleh. Here is a change to autoexp.dat to correct the order.
First comment out this line:
__m128=$BUILTIN(M128) And add this line:
__m128=<m128_f32[0]>, <m128_f32[1]>, <m128_f32[2]>, <m128_f32[3]>
Keep in mind that a shape does not know about bodies and stand apart from the dynamics system. Shapes are stored in a compact form that is optimized for size and performance. As such, shapes are not easily moved around. You have to manually set the shape vertex positions to move a shape. However, when a shape is attached to a body using a fixture, the shapes move rigidly with the host body.
Box2D uses MKS (meters, kilograms, and seconds) units and radians for angles. You may have trouble working with meters because your game is expressed in terms of pixels. To deal with this in the testbed I have the whole game work in meters and just use an OpenGL viewport transformation to scale the world into screen space.
float lowerX = -25.0f, upperX = 25.0f, lowerY = -5.0f, upperY = 25.0f;…
Box2D Benchmarks Benchmarks
Box3D Benchmarks Benchmarks
Dynamic Bounding Volume Hierarchies — GDC 2019 GDC Slides Full Slides
Numerical Methods — GDC 2015 Slides
Understanding Constraints — GDC 2014 Slides Matlab Source YouTube
Continuous Collision — GDC 2013 Slides YouTube
Ragdolls — GDC 2012 Slides
Soft Constraints — GDC 2011…