Robin's Thoughts

Lines, circles and quadratic bezier curves

(3448 words)

It feels like it has not been a very productive week this week. Mostly due to things happening in real life and not having the time or energy to do much work on fourth. This can be seen in the number of lines added this week:

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Zig                             31           1787           1568          14164
-------------------------------------------------------------------------------

Last week we were at 13912 lines of code. This week we’ve added only 252 lines of code. If we consider a standard five day week for working, this is only 50 lines of code a day. This code isn’t even that spectacular. But, next week, I hope to have a car that works, and a fridge/freezer that freezes and fridges things. Until then, life is a little less civilized at home.

Anyway, back to the project… What has been added? Firstly, we’ve added a whole graphics library rendering system. Well, at least the start of it. This is basically a module that can draw lines, and curves, and logically any complex shape. We have two main arrays:

var gl_vertexes: std.ArrayList(gl_shader_source.Vertex) = undefined;
var gl_indexes: std.ArrayList(Index) = undefined;

These collect a set of vertexes and indexes that allows things to be drawn. To draw something we have to call set_color, that saves the current color being drawn.

pub fn set_color(col: ng.Color) void {
    current_color = col;
}

We can then add a vertexes as needed. We always return the index of the currently added vertex so that we can then reference this index later.

pub fn add_vertex(pos: ng.Vec2) !Index {
    const index: Index = @intCast(gl_vertexes.items.len);
    try gl_vertexes.append(.{ .pos = pos, .col = current_color });
    return index;
}

To actually render something, we use the add_triangle function. This is the function that adds three vertex indexes to the the indexes array.

pub fn add_triangle(p0: Index, p1: Index, p2: Index) !void {
    try gl_indexes.append(p0);
    try gl_indexes.append(p1);
    try gl_indexes.append(p2);
}

It is all very simple. So how do we use this to draw a line?

pub fn draw_line(start: ng.Vec2, end: ng.Vec2, width: f32, color: ng.Color) !void {
    const delta = end - start;
    const dist = @sqrt(delta[0] * delta[0] + delta[1] * delta[1]);
    if (dist > 0) {
        const tangent = ng.Vec2{ delta[1], -delta[0] } *
            @as(ng.Vec2, @splat(width / 2 / dist));

        set_color(color);
        const p0 = try add_vertex(start - tangent);
        const p1 = try add_vertex(start + tangent);
        const p2 = try add_vertex(end - tangent);
        const p3 = try add_vertex(end + tangent);

        try add_triangle(p0, p1, p2);
        try add_triangle(p2, p1, p3);
    }
}

The draw_line function takes in a start and end positions, the width of the line, and the color of the line. We first determine the length of the line. If the line is longer than zero, we determine the tangent of the line and multiple that by the half the width divided by the distance. This gives us a simple vector that can be added to the start and end points for this line.

We then use set_color to set the color of the next few vertexes. We add four vertexes, two for each end with plus or minus the tangent vector. We then just add two triangles based off those points.

Let’s look at another function to get an idea why we use vertex indexes. The fill_circle function is also very simple.

pub fn fill_circle(pos: ng.Vec2, radius: f32, color: ng.Color) !void {
    const num: f32 = @min(256, @max(9, @sqrt(detail * radius) * quality));
    const a: f32 = std.math.tau / @floor(num);
    const r: ng.Vec2 = @splat(radius);

    set_color(color);

    var angle: f32 = 0;

    const first = ng.Vec2{ @cos(angle), @sin(angle) } * r;
    angle += a;

    const p0 = try add_vertex(pos);
    var p1 = try add_vertex(pos + first);
    const first_p1 = p1;

    const segments: usize = @as(usize, @intFromFloat(num)) - 1;

    for (0..segments) |_| {
        const cur = ng.Vec2{ @cos(angle), @sin(angle) } * r;
        const p2 = try add_vertex(pos + cur);
        try add_triangle(p0, p1, p2);
        p1 = p2;
        angle += a;
    }

    try add_triangle(p0, p1, first_p1);
}

We first have to determine how many triangles we want to approximate the circle using. To do this, we use detail and quality variables along with the radius. The detail value is computed from the model-view-projection matrix used, whereas quality is a value that can be tweaked by the user, eventually, in some sort of settings menu.

Once we have the number of segments, we determine the angle of each triangle in that wedge. We also @splat the radius f32 value into a Vec2 vector.

After setting the set_color, we calculate the first point from an angle. We then add two vertexes of the first wedge, the center point p0 and the first point p1. We then iterate through each of the segments, calculating the next point based on the angle, adding a vertex for that, p2, and then adding a triangle from the center point, the last point on the edge and the newly computed point on the edge. The new p2 becomes p1 ready for the next iteration.

Finally, we have to close the circle. We could just complete the circle using math, but floating point math could introduce some errors and we already have the first point that we can connect with. So we just add one more triangle.

This means that if we have a circle for say 12 segments, we’ll have 12 triangles being drawn, but only 13 vertexes being created. This also meant that I had to implement element arrays in the platform layer, adding an IndexType into the pipeline descriptor.

A draw_circle function was also created. This does pretty much the same work as fill_circle, except it has two points per segment because the drawn circle has a width to it, and therefore two triangles per segment.

pub fn draw_circle(pos: ng.Vec2, radius: f32, width: f32, color: ng.Color) !void {
    const num: f32 = @min(256, @max(9, @sqrt(detail * radius) * quality));
    const a: f32 = std.math.tau / @floor(num);
    const r: ng.Vec2 = @splat(radius);
    const w: ng.Vec2 = @splat(width);

    set_color(color);

    var angle: f32 = 0;

    const inner = ng.Vec2{ @cos(angle), @sin(angle) } * (r - w);
    const outer = ng.Vec2{ @cos(angle), @sin(angle) } * r;
    var last_inner = try add_vertex(pos + inner);
    var last_outer = try add_vertex(pos + outer);
    const first_inner = last_inner;
    const first_outer = last_outer;
    angle += a;

    const segments: usize = @as(usize, @intFromFloat(num)) - 1;

    for (0..segments) |_| {
        const cur_inner = ng.Vec2{ @cos(angle), @sin(angle) } * (r - w);
        const cur_outer = ng.Vec2{ @cos(angle), @sin(angle) } * r;
        const p0 = try add_vertex(pos + cur_inner);
        const p1 = try add_vertex(pos + cur_outer);
        try add_triangle(last_inner, last_outer, p0);
        try add_triangle(last_outer, p0, p1);
        last_inner = p0;
        last_outer = p1;
        angle += a;
    }

    try add_triangle(last_inner, last_outer, first_inner);
    try add_triangle(last_outer, first_inner, first_outer);
}

How are these triangles actually rendered?

Well, there is a function called start_render that takes the model-view-projection matrix to be used for all the operations. This calculates the detail variable used in the various drawing functions.

pub fn start_render(mvp: ng.Mat4) void {
    current_mvp = mvp;

    detail = @sqrt(@abs(mvp[0] * mvp[5] - mvp[1] * mvp[4]));
}

As you can see, this just uses the 2D parts of the mvp to determine the detail level.

Then once all the drawing is complete, the render function is called, that just updates the buffer data for the vertexes and indexes. It then applys the state for the pipeline, binding, uniform, and then draws the correct number of indexes.

pub fn render(render_pass: ng.RenderPass) void {
    gl_buffer.update(ng.as_bytes(gl_vertexes.items));
    gl_index.update(ng.as_bytes(gl_indexes.items));

    render_pass.apply_pipeline(gl_pipeline);
    render_pass.apply_bindings(gl_binding);
    render_pass.apply_uniform_mat4(GL_Uniforms.mvp, current_mvp);
    render_pass.draw(gl_indexes.items.len);

    gl_vertexes.clearRetainingCapacity();
    gl_indexes.clearRetainingCapacity();
}

This does an indexed draw, because we initialised the gl_pipeline with an index type:

gl_pipeline = try ng.create_pipeline(.{
    .label = "gl pipeline",
    .shader = gl_shader,
    .primitive = .triangle_list,
    .index_type = .u32,
});

And bound the gl_index buffer along with the gl_buffer.

gl_buffer = try ng.create_buffer(.{
    .label = "gl vertex buffer",
    .kind = .vertex,
    .size = 1024 * 1024 * @sizeOf(gl_shader_source.Vertex),
    .update = .stream,
});

gl_index = try ng.create_buffer(.{
    .label = "gl index buffer",
    .kind = .index,
    .size = 1024 * 1024 * @sizeOf(Index),
    .update = .stream,
});

gl_binding = try ng.create_binding(.{
    .label = "gl binding",
    .vertex_buffers = &.{gl_buffer},
    .index_buffers = &.{gl_index},
});

You’ll notice that the last thing we do in the render function is clearRetainingCapacity. This resets the length of the gl_vertexes and gl_indexes arrays back to zero but does not free any memory allocated for this. First, this means that the next frame we are going to have to draw the same things, or mostly the same things, again, so freeing this memory to then immediately having to reallocate them is just a waste of good CPU cycles. So we retain the capacity and reuse this memory again in the next frame.

How do we use all these functions?

First, we split the drawing of the world into a start_draw_world and end_draw_world. The start calls gl.start_render passing it the mvp for the world drawing, allowing detail to be calculated. Then later the end calls the gl.render function to actually do the binding and applying of pipelines to draw the triangles necessary.

Why did we do this split?

Because the nodes and links that we want to draw are stored in the entity component system, and we therefore want to draw these things while we are progressing the ECS state.

start_draw_world(render_pass) catch {};
ng.progress(state.dt);
process_events();
draw_ui();
end_draw_world(render_pass) catch {};
ng.ui_render(render_pass);

We start drawing the world, then we progress the ecs, process any events, draw the user interface, then end drawing the world which actually draws the triangles for the world, before finally rendering the user interface on top of the world.

The progressing of the ecs basically means calling the various systems with the various entities that match those systems.

What do the systems look like?

We have two systems, draw_links_system and draw_nodes_system. The links system operates only on entites that have a Link component. The nodes system operates only on entities that have a Node component.

fn draw_nodes_system(iter: *const ng.SystemIterator) void {
    for (iter.entities) |entity| {
        if (entity.get(com.Node)) |node| {
            gl.draw_circle(node.pos, 5, 0.5, .purple) catch {};
        }
    }
}

As you can see, the nodes system is really simple. We iterate through all the entities that have Node, get the node data for each entity, and then draw_circle for that node. It will be easy to add different colors depending on whether a node is ‘selected’ - a task for next week.

The links system is also simple.

fn draw_links_system(iter: *const ng.SystemIterator) void {
    for (iter.entities) |entity| {
        if (entity.get(com.Link)) |link| {
            const start = link.start;
            const mid = link.mid;
            const end = link.end;
            const width = @as(f32, @floatFromInt(link.width)) * 0.1;

            const start_node = start.get(com.Node);
            const mid_node = mid.get(com.Node);
            const end_node = end.get(com.Node);

            if (start_node) |n0| {
                if (mid_node) |n1| {
                    if (end_node) |n2| {
                        gl.draw_bezier(n0.pos, n1.pos, n2.pos, width, .black) catch {};
                    }
                }
            }
        }
    }
}

This again just iterates though the entities that have Link. From that link we can get the start, mid and end nodes, along with the width of the link. We then draw a bezier curve for the link based on these values. Note how we can get data from other entities, in this system, but we can’t modify those values.

We have a bezier drawing function?

Yes, we do. This was written whilst sat in the customer waiting area of a car repair place. Yes, you can work anywhere, although their internet speed wasn’t the best.

set_color(color);

const delta = end - start;
const dist = @sqrt(delta[0] * delta[0] + delta[1] * delta[1]);

const w2: ng.Vec2 = @splat(width / 2);

const num_segments: f32 =
    @floor(@min(256, @max(9, @sqrt(detail * dist) * quality)));

The draw bezier function is a significantly more complex function compared to drawing a line or circle but it starts the same way, calculating the distance, the half width vector, and the number of segments to draw.

const dt: ng.Vec2 = @splat(1 / num_segments);
const two = ng.Vec2{ 2, 2 };
const ddt = two * dt * dt;

We then calculate the vector for dt being one over the num_segments splatted over the Vec2. This is then repeated for ddt being the square of dt multiplied by two.

const dd = (end - two * mid + start) * ddt;
var d = (two * (mid - start)) * dt + dd / two;
var tan = ng.normalize(ng.Vec2{ -d[1], d[0] }) * w2;

We can then calculate the dd value, which is derivative of the curve. You’ll have noticed that we only have one control point and therefore we only need a single derivative. From that we can calculate the first d, or delta values based on two times the mid minus start value multipled by dt and adding the derivative over two. We can then calculate the tangent for the width by normalizing the normal to the derivative and multipling it by half the width. This sounds complex, but mathematically it is relatively simple.

const segments: usize = @intFromFloat(num_segments);

var pos = start;
var last_inner = try add_vertex(pos - tan);
var last_outer = try add_vertex(pos + tan);

Finally, we can add two vertexes for the starting line of the curve.

for (0..segments - 1) |_| {
    pos += d;
    d += dd;
    // try fill_circle(pos, 0.25, .white);
    tan = ng.normalize(ng.Vec2{ -d[1] + dd[1] / 2, d[0] - dd[0] / 2 }) * w2;
    const inner = try add_vertex(pos - tan);
    const outer = try add_vertex(pos + tan);
    try add_triangle(last_inner, inner, last_outer);
    try add_triangle(last_outer, inner, outer);
    last_inner = inner;
    last_outer = outer;
}

The main loop comes next. Each segment of the curve addes two more vertexes and then adds two triangles to create the line segment for this section. We add the delta to the position, and the deriviative to the delta. This creates the curve center points. We can then calculate the tangent at each point, normalize it, multiply it by the half width, and then add that to the current point to create the inner and outer points. We can then add the next two triangles to create the curve segments.

d = end - mid;
tan = ng.normalize(ng.Vec2{ -d[1], d[0] }) * w2;
const inner = try add_vertex(end - tan);
const outer = try add_vertex(end + tan);

try add_triangle(last_inner, inner, last_outer);
try add_triangle(last_outer, inner, outer);

At the end of the loop, we add the final two vertexes and add the final two triangles. Again, we don’t rely on potentially poor floating point accumulated errors but base this on the angle from mid to end.

This actually took a bit of time to get right. I validated this again the slow but accurate de Casteljau method, writing a separate function for this and drawing it behind the actual end function to enable visual validation.

There should probably be a couple of questions being raised at this point. Why are you using quadratic bezier curves and not cubic bezier curves, and why are you redrawing everything every frame?

The use of quadratic (single control point) and not cubic (two control points) is really to keep things simple in the user interface. We will be drawing roads, paths, railways, and the like with these curves. I’d like the user interface to be:

And not:

Or:

Personally, I find drawing curves by just using quadratic bezier curves so much easier to understand than cubic curves where you have to fiddle with the control points to get things right. We just want people to click curved roads into existance as easily as possible.

We are redrawing everything every frame because we are not prematurely optimising things. We’ll probably have to consider splitting the world into a set of areas (probably 1km on each side) that would then have a generated model for that area being created. These can then be rendered as necessary depending on what part of the world is visible. However, we’d still need to have whatever the user is creating at the moment be fully dynamic, fully redrawn every frame, and therefore this optimisation can happen at a later date. At the moment, the complexity of any map will be tiny and therefore we should move forward quickly getting the user interaction feeling right rather than making everything really complex now just to make it really fast to render huge cities.

What are the plans for next week? Well, obviously we need to create new roads, placing nodes, drawing links. We probably want to have straight roads as well are curves, so being able to draw a link that has no mid point might still be useful, although we could just compute the mid point as the mathematical mid point between the start and end nodes.

Once this user interaction is implemented, we probably need to think about how we do junctions. This requires some thinking of the best way to do this. Junctions are just nodes, but I’m assuming we have some components that expand on that. I’m assuming we’ll have a PriorityJunction component, and a SignalizedJunction component. We’ll probably need a Roundabout junction component, and perhaps other components for other types of junctions.

Do we need a way to move the rendered links back from the junction node and allow the junction node itself to render everything from that point into and through the junction. This is the fun part of these projects, doing something complex that we haven’t done before.

Once that is done, we should create some vehicles and move them around the network of roads. This probably requires us to have multiple lanes on these links, and therefore being able to update a texture for these lanes and then set the correct u,v coordinates for this texture when drawing roads. This would need extensions to the new gl module above, but that shouldn’t be too difficult.

And we need to get the vehicles moving correctly. One of my biggest bugbears for simulation programs is that vehicles don’t move correctly along roads. Vehicles should rotate around the rear axle of the vehicle, not the center of the vehicle. So many programs get this wrong. It looks wrong. It looks like the vehicle is sliding around the corner. I really want to get this right. The interesting thing about this is that when do you it correctly, it automatically causes longer vehicles to swing wide to navigate around a sharp corner, just like in real life. We can also calculate this ‘swing’ and potentially cause vehicles to wait until there is enough space to swing around before continuing along. Also, if we do this right, we can make the steering wheels rotate the correct amount for how much the vehicle is turning.

One other thing that I really want to get right is how bicycles move around. Ignoring that bicycles rotate around the rear wheel, bicycles can also filter past vehicles and in some places have their own dedicated lanes. I’d like to implement advanced bike boxes, advanced traffic lights for bikes, bike specific traffic signals, and similar. Note, I’m not trying to create a full traffic simulation, this is meant to be a game, but this is something that nobody else is doing right in my humble opinion, and I really want to get this right. Get this right for bicycles, and we should be able to get it right for mopeds. I’ve been to Vietnam and the number of mopeds on their roads is ‘high’. We should enable such flows.

The final bugbear that I really want to implement is two-way traffic along narrow roads. In many places, we have roads that can move traffic in two directions but there are parked vehicles on both sides, or the road is literally a single track road. This needs to be solved. I think this should also allow for vehicles to overtake slower vehicles on two-lane roads, for example cars overtaking slow farm tractors or slow bikes.

Hopefully next week will be more productive with less life getting in the way.

Fourth, Game, Bezier