Sunday, September 7, 2025

I don’t remember exactly where I saw it first, but I think it was a car commercial where they had some kind of high-tech looking CGI effect in the background, that is maybe best described as “interacting, floating lines”. How do they do that, I asked myself, and came up with what I now call the “code weaving” demo. The end result looks different, but my version is kind of fascinating in its own right, enough to write about it here.

Floating in space

The basic idea is pretty simple. Starting off, we are just going to have a bunch of points that randomly float about in 2D space. Floating around means the point moves in a direction, and then it’s direction vector is slowly adjusted, and it starts to drift off.

On top of that, we let the points bounce off the walls (ie. the screen edges) so we don’t have to deal with points flying offscreen.

typedef struct {
    Vec2f pos;
    Vec2f direction;
} DriftPoint;

DriftPoint all_points[NUM_POINTS];

The direction vector is normalized, and then we slowly rotate it by a fraction of an angle. When the angle is negative, it rotates anti-clockwise.

Vec2f rotate_Vec2f(Vec2f v, float a) {
    Vec2f d;
    d.x = v.x * cosf(a) - v.y * sinf(a);
    d.y = v.x * sinf(a) + v.y * cosf(a);
    return d;
}

Connecting the dots

Dots close to each other connect to a line. Dots further away have weaker connections (a fading line), while dots that are too far away do not connect at all. This creates a web-like structure between points. Since we connect to at most only four points, visually flying triangles start to appear. This is kind of an illusion, in the sense that we never explicitly code or draw any triangles.

typedef struct {
    size_t a, b;    // index into `all_points`
    float intensity;
} LineDef;

The line intensity is a measure of how far the other point is. We can use it as the alpha blend value when drawing the line.

float intensity = MAX_DISTANCE / distance;
intensity = clamp_float32(0.1f, intensity, 1.0f);

Calculating the distance involves taking a square root, which does ouch to performance, but luckily we don’t have to compute the square root—we can keep the distance squared and work with that. Sort by shortest distance, we’re actually only interested in drawing lines to the four closest points.

I hope you can already smell that we’re still doing a lot of computations that are actually wasted effort.

High-performance weaving by space partioning

Connecting the dots quickly becomes incredibly slow at high point counts, because it is an N×N or O(n²) algorithm. We can do a lot better; a point only needs to interact with its direct neighbors, and has nothing to do with points that are far away. The ideal data structure for doing just that is the collision grid. [Note: A quadtree also does the trick. A collision grid is much easier to implement, and its performance is better too].

A collision grid divides the (screen) space up into cells, which makes it easy to consider only points that are in a cell, or in adjacent cells.

It’s funny how a bunch of randomly drifting points can give rise to a living and breathing mass of electrified web, or something. A static image just wouldn’t do it any justice, so we have an animated GIF showing off the effect. This is a (headache inducing) low-fps rendering; it looks much smoother at 60 fps.

Now, wouldn’t it be nice if we could click the mouse, creating a splash + ripple effect in the weaving points …