Signed Distance Functions (SDF's) for the Playdate

SDK Development Discussion
, ,
1

I thought I'd make a Lua and C library of Signed Distance Functions (SDF's) available.

It's a Lua and C port of the GLSL shader SDF's from Inigo Quilez :: computer graphics, mathematics, shaders, fractals, demoscene and more to start.

I'm not sure how useful they'll be for others, but essentially these allow you to efficiently determine distance from a shape. eg Point to Polygon, Point to Rhombus, Point to Arc, etc. They are fast. In Lua, you can do hundreds of checks per 1/50s. In C, tens of thousands.

This can be used for collision detection, among other things. I've only started playing with Lua since I received my Playdate last month so the code is probably fairly ugly :slight_smile: and I suspect creates more garbage to be collected than needed.

collisions
sprites
raymarch

15 Likes
2

Benchmarks

I ran extensive distance checks on device (rev B, firmware 2.4.2) for each function to establish how many distance checks can be made for each within 1/50th second.

SDF C Lua Lua Old
sdCircle 49k 877 306.7
sdSegment 28k 757 77.7
sdSegmentLinf 37k 851 na
sdBox 42k 781 74.8
sdBoxLinf 104k 1056 na
sdOrientedBox 17k 583 21.7
sdRoundedBox 29k 810 69.0
sdRoundSquare 39k 760 na
sdRhombus 21k 599 32.3
sdRhombusLinf 42k 794 na
sdTrapezoid 23k 629 41.0
sdParallelogram 19k 515 28.1
sdEquilateralTriangle 23k 693 61.4
sdTriangleIsosceles 19k 563 34.8
sdTriangle 12k 409 15.7
sdQuad 11k 378 12.3
sdUnevenCapsule 23k 677 124.3
sdEgg 31k 818 na
sdPie 23k 591 70.5
sdCutDisk 25k 652 108.1
sdMoon 17k 513 81.1
sdVesica 28k 675 86.7
sdOrientedVesica 15k 555 24.3
sdTunnel 24k 624 58.6
sdArc 37k 902 116.8
sdRing 22k 588 48.2
sdHorseshoe 22k 628 33.0
sdParabola 7k 391 67.4
sdCross 32k 726 53.3
sdRoundedX 39k 811 88.0
sdEllipse 4k 195 6.6
sdEllipseLinf 28k 740 na
sdStar5 20k 515 23.8
sdHexagram 25k 562 32.4
sdPentagon 26x 586 33.3
sdRegularPolygon (5) 4k 325 52.6
sdHexagon 30k 629 48.1
sdRegularPolygon (6) 4k 325 52.3
sdOctagon 26k 577 32.2
sdRegularPolygon (8) 4k 325 52.1
sdPolygon (4) 8k 242 13.9

2024-03-07: baseline
2024-03-09: better bench marking (6x runs, better timing); better local variables in SDFs
2024-04-26: 10-30x Lua speed increase; add C version 100x orig

Lua/C binding versions generally run 1-2k per 1/50th frame.

2 Likes
3

Sped things up a bit and added a better benchmark.

1 Like
4

Just trying this and couldn't run some of the bundled examples. Have filed some github issues.

That said, I'm really excited to make a game using these.

Cheers!

5

Thanks, Ive fixed these problems caused by the last push.

I should also add a module of draw functions to make it more consumable since it takes some noodling to find the drawing commands for the shapes (e.g. use of apothem for n-gons). I'll get to that at some point.

I was intrigued by your peggle idea. Here's a quick sketch.

peggle

4 Likes
6

Nice! Is that 100% SDFs?

7

Added complex bezier example source to repo

1 Like
8

Experimenting.

koatari

koatari2

4 Likes
9

distances

I've pushed a major performance update to the Library of 2D SDF functions.

I've updated the benchmarks speed table in the post above.

The new Lua functions are appox 10-15x the speed of previous. I've also ported the library to C functions which are approx 500x the speed of previous. For example, distance to rhombus could be called 30 times per 1/50 second frame, but now it is 600 times in Lua, and the C function is 21000 times in the same frame. I have created an example showing C bindings with Lua. Lua bindings to C functions generally run at 1000-2000 per 1/50th second which seems to be constrained simply by the C/Lua interface.

What was the Lua performance bottlneck?

a) Playdate SDK Vector2D operations. Every time we address a vector or create new ones we create unnecessary overhead. Instead, we can operate on the x,y natively and compute our own dot products and vector add/sub/mult/div componentwise without the vector2D structure or helper functions. Might this mean you can speed up your vector work elsewhere in your game? Maybe, probably, possibly, hopefully? If you're into shaving time off your game loop, give it some thought.

b) Overhead to call math abs, min, max, clamp, etc, even when localised. I've removed all of these. Instead, we can use boolean operations: abs(x) becomes (x >= 0) and x or -x and max(x,y) becomes ((x > y) and x or y). Again, your game loop elsewhere may be optimised in this way.

This means the SDF functions are now generic Lua and C and not playdate specific. They could be used in other microcontroller realms (esp32? pi zero?) or software frameworks (love2d etc).

The performance improvements opens new possibilities:

  • many more objects on screen
  • continuous collision detection. It should now be possible to run any collision loop much much faster, removing the likelihood of object tunneling, and to perform precalculation of trajectory totally separate to and in advance of the UI rendering of object movement.
  • on device rendering, potentially including lighting etc
  • less/no need for broad phase AABB collision checking before sdf check
  • 3d opportunities? I'll port 3D SDFs soon.

I've put the creation of basic samples/tutorials on the todo list since there is a learning curve.

4 Likes
10

Wonderful! For me this is one of the best things to happen for SDK developers. Thanks

11

In some cases we can calculate distance in the L-infinity norm metric space (i.e. Chebyshev distance) much faster than in Euclidean space. The actual distance isn't much use unless your game moves in "chess directions" in which case its very useful. But the sign of the distance tells you if you outside or on/in the shape, and thus is perfectly fine for collision detection.

So I've added/ported sdf's for Ellipse (C:7x, Lua:4x), Box (C:2.5x, Lua:1.4x), Segment (C:1.3x, Lua:1.1x), Rhombus (C:2x, Lua:1.3x).

4 Likes
12

Not directly SDFs, but I added generalised functions with a demo for calculating the intersection of a Ray or LineSegment with an Ellipse or Circle, and the normals at the point of intersection.

circleintersects

7 Likes