Box2D-lite physics engine on Arduboy

Development
21

The inverse square root is probably more useful for physics (used for vector normalization) and is much easier to compute using Newton’s method as it requires no division. Example in ArduGolf.

Pseudocode:

inv_sqrt(a)
{
    x = 1.0; // could be something else. just a reasonable starting guess
    repeat(number of iterations) {
        x = (1.5 - 0.5 * a * x * x) * x;
    }
    return x;
}
1 Like
22

Looking at the repo now, I see that the only use of square root is to compute the collision friction between two bodies here, not for vector normalization (the vector length method is never called anywhere).

friction = sqrt(static_cast<float>(body1->friction * body2->friction));

In this case, since a body’s friction coef is typically between 0.0 and 1.0, the product of two bodies’ friction coefs will itself be in the same range, so there are only 256 domain values to account for with 8 fraction bits. You could use a 256-byte LUT instead.

// warning: untested

extern uint8_t const SQRT_LUT[256] PROGMEM;

UQ8x8 friction_sqrt(UQ8x8 x)
{
    // this function should only be called with values in the range [0,1]
    if(x >= 1) return 1;
    uint8_t fraction = x.getFraction();
    fraction = pgm_read_byte(&SQRT_LUT[fraction]);
    return UQ8x8(0, fraction);
}

// use like:
friction = friction_sqrt(body1->friction * body2->friction);
1 Like
23

Interesting discovery. I checked the original Box2D-lite repo, which retains the joints features I stripped out, and it too doesn’t seem to ever call the vector length method as well. Neat!

I just tested this with your code which works. But I think I messed up generating my LUT.

Regardless of that though, I could feel the friction in the simulation changed because of that, but since I gave every box its default 0.2 friction coefficient, I also realized I probably can just have a static global friction value and still have a capable little physics engine.

1 Like
24

I keep blowing the stack (I assume) with more than 6 boxes, or with 5 boxes after a couple minutes of runtime.

I just found this repo for another “lightweight” derivative of Box2D. I tried porting it in a similar way, but ran into some std dependency errors. I wonder if It might have some tricks to learn from regardless.