Drawing some lines

We start our journey with drawing a subset of all possible lines, as that makes the initial implementation a lot easier. We also use a very basic implementation, as it is easy to understand, but more advanced versions work very similarly, so if you know this one, there will be a smaller barrier of understanding.

From now on, we will continuously extend the class Rasterizer, which can be found in the file linked at the beginning of each section. There are two other classes that will be extended along the way:

Framebuffer: Contains the output of the pipeline. Said simply, it is just one (or multiple) output images that we are writing into in the end.

class Framebuffer {
    constructor() {
        // these are a number of named outputs,
        //  each just an image
        // we will write color into these
        this.color_buffers = {};
    }

    static new() {
        return new Framebuffer();
    }
}

Pipeline: Contains surrounding information related to input and output processing of the rasterizer, basically adjusting how data flows through it.

class Pipeline {
    constructor({
        // this specifies the current set of 
        //  outputs for our rasterizer
        framebuffer = Framebuffer.new(),
    } = {}) {
        this.framebuffer = framebuffer;
    }
}

Aside from that, there will be a couple of definitions that we use to differentiate some things, though for now they aren't super important.

// describes, what a certain attribute
//  for an object is for
// for now, we only have vertices (positions)
//  which we use to specify lines
const Attribute = {
    VERTEX: 0,
};

// the topology describes the "type" of
//  object we are dealing with
// for now, we only have lines, but in a
//  little while there will also be triangles
const Topology = {
    LINES: 0,
};

We start by characterizing a line as a function in 2D. For any given $x$ coordinate, we compute $y$ as:

$$\begin{align*} y &= mx + b &= \operatorname{f}(x) \end{align*}$$

$b$ is the $y$-intercept, that is where the line intersects the $y$-axis. $m$ is the slope, how much the $y$ coordinate changes with respect to a change in $x$: $m=\frac{\Delta y}{\Delta x}$

When we have two points $\mathbf{a}$ and $\mathbf{b}$ the change in $x$ and $y$ is just the vector from $\mathbf{a}$ to $\mathbf{b}$. Then we can find $m$ as:

$$\begin{align*} m &= \frac{\Delta y}{\Delta x}\\ &= \frac{b_y - a_y}{b_x - a_x} \end{align*}$$

From this, you can immediately see one issue.

What lines are impossible to draw with that definition?

• Horizontal
• Vertical

For vertical lines, the $x$ coordinate does not change. Thus the denominator will become $b_x - a_x = 0$. As we can't divide by zero, this line can't be defined using a slope. This will be handled later.

We already know two points on the line, $\mathbf{a}$ and $\mathbf{b}$.

The basic idea, that is found in many more efficient variants of the following algorithm is simply this: If we move a unit (a pixel) to the right ($x$-direction), how would $y$ change?

$$\begin{align*} \operatorname{f}(x+1) &= m(x +1) + b \\ &= mx + m + b \\ &= mx + b + m \\ &= \operatorname{f}(x) + m \end{align*}$$

So if we know the $y$ value at one point, we can compute the one right next to it by a simple addition.

Which brings us to our basic algorithm:

1. Compute $m = \frac{b_y - a_y}{b_x - a_x}$

2. Start at the first point $(x,y) = (a_x,a_y)$

3. Move from $x$ to $b_x$ to the right (increment $x$)

   1. Put a pixel where you currently are ($x$,$y$). This needs to be converted to integer values
   2. Increase $y$ by $m$

You may already see some issues, but let's implement it first below and see the result!

To get you started, we will show you the documented base Rasterizer class.

class Rasterizer {
    /**
     * Rasterize a line
     * @param {AbstractMat} a 
     * @param {AbstractMat} b 
     * @param {Object<Number|AbstractMat>} data_a 
     * @param {Object<Number|AbstractMat>} data_b 
     */
    rasterize_line(pipeline, a, b,
        data_a = {},
        data_b = {}) {
    }

    /**
     * Processes a single line
     * @param {Pipeline} pipeline The pipeline to use
     * @param {AbstractMat} v0 The first vertex
     * @param {AbstractMat} v1 The second vertex
     * @param {Object<Number|AbstractMat>} attribs_v0 The
     *  attributes of the first vertex
     * @param {Object<Number|AbstractMat>} attribs_v1 The
     *  attributes of the second vertex
     */
    process_line(pipeline, v0, v1,
        attribs_v0 = {},
        attribs_v1 = {}) {

        this.rasterize_line(pipeline, v0, v1);
    }

    /**
     * Draw the given geometry
     * @param {Pipeline} pipeline The pipeline to use
     * @param {Object} geom Geometry object
     *  specifying all information
     */
    draw(pipeline, geom) {
        // no vertices
        // we could also take a parameter specifying
        //  the number of vertices to be
        // drawn and not rely on vertex data
        if (!geom.attributes[Attribute.VERTEX]) {
            return;
        }

        const vertices = geom.attributes[Attribute.VERTEX];
        const n = vertices.length;

        // go through objects
        if (geom.topology === Topology.LINES) {
            // handles lines
            // handle two vertices per step
            for (let i = 0; i < n; i += 2) {
                this.process_line(
                    pipeline, vertices[i], vertices[i + 1]
                );
            }
        }
    }

    /**
     * Writes a number of output colors to the
     *  pipeline's framebuffer.
     * @param {Pipeline} pipeline The pipeline to use
     * @param {AbstractMat} frag_coord The fragment
     *  coordinate
     * @param {Object<AbstractMat>} colors A map
     *  containing the colors per output buffer
     */
    write_fragment(pipeline, frag_coord, colors) {
        const px = floor(subvec(frag_coord, 0, 2));

        const frames = pipeline.framebuffer.color_buffers;

        for (let i in colors) {
            const frame = frames[i];
            if (!frame) {
                continue;
            }

            frame.set(colors[i], px.at(0), px.at(1));
        }
    }
}

There are a few things included, that will be used later, but don't worry about them. The basic flow is as follows:

1. The user calls draw with a pipeline and geometry
2. The draw method checks, what type of geometry it is (for now, we only have lines). It will then go through the VERTEX attribute, which contains line start and endpoint positions. For each pair of these, it will call the process_line method
3. process_line currently only calls the rasterize_line method, which we will implement here
4. In the rasterize_line method shown in the code editor, the write_fragment is called. Why it's called that will be explained in the section about (Shaders)[/rasterization_course/rasterizer/05.md]. For now, it's basically just a function to write a color to the output image

This might seem a bit complicated for now, but we will expand on all these functions and won't change this structure, aside from adding to it. So this general flow of data will stay the same until the end!

Below you can see the line drawing function with some basic setup. The comments in the files will tell you a bit more about the attributes and how objects are represented.

In there you can implement the above procedure. You can change the input scene if you like by changing the code in the scene.js box. Currently, a number of lines are drawn in a circle, although this might not fully work yet... We will take care of that though!

Exercise:

• Implement the line drawing algorithm described above in the rasterizer.js file

Solution:

You should be able to see some red lines in the right half of a circle. The left half is missing. If you look closely, some of the lines have gaps, which doesn't look that nice.

In the next section, we will fix these issues, but feel free to think about what is causing them and how to solve this!