article/rast1.html

<!doctype html>
<html>
<head>
    <meta charset="utf8">
    <link rel="stylesheet" href="article.css">
    <link rel="shortcut icon" href="favicon.png">
    <link rel="alternate" type="application/atom+xml" href="feed.xml" />
    <title>Explanations</title>
</head>
<body id="rast1"><div class="main">
    <header>
        <a href="index.html">
            <h1><span>Explanations</span></h1>
            <span class="subtitle">Play, don't show</span>
        </a>
    </header>

    <article>
        <h2></h2>

        <section id="prologue">
        <h3>Stepping Down</h3>
        <p>
            Up until now, we've been exploring the X11 Window System from a somewhat high level.
            We've talked about Windows and Drawables and Pixmaps but we're always talking about them
            in terms of the protocol. "You draw on a Drawable with protocol extension RENDER," or
            "you can configure a window with the protocol request ConfigureWindow", but I haven't really gone
            into any detail about how that's implemented. I think it's about time we dropped from the abstract
            to the concrete. Today's article won't be about X11, or even the data structures that are inside of
            it. Today, we're going to start to unravel 2D Graphics. You can explore the things I'm going to talk
            about on any operating system, in any programming language, and even on paper.
        </p>
        <p>
            I often see comments like "oh, if only SVG was implemented with WebGL, then it would be fast",
            and realize that people do not quite understand the challenges and complications of 2D graphics
            rendering. Despite it going against your intuition, fast, good looking 2D graphics are actually
            <em>harder and more computationally expensive</em> to accomplish than 3D graphics, at least
            on traditional consumer GPUs. I hope to eventually explain <em>why</em>, but unfortunately that
            won't come today.
        </p>
        <p>
            Even though fast, good-looking 2D graphics rendering is an extremely difficult problem, the basics
            and principles behind it aren't. Today, we will be exploring the basics of 2D graphics by writing
            a software rasterizer of our very own, from the ground up. You should be able to write one of your
            very own at the end of this article! All of the code you see here was written
            for this article, from nothing more than basic principles and ideas. It's
            <a href="https://github.com/magcius/xplain/blob/gh-pages/src/article-demos/rast1.js">open source on GitHub</a>,
            and I've tried to and document it well as a source to learn from.
        </p>
        <p>
            I hope you're as excited as I am to get started! So, without further ado...
        </p>
        </section>

        <section id="pixel-grid">
        <h3>The Pixel Grid</h3>
        <p>
            The X11 articles take place in a hand-written X11 server. Regional Geometry took place, well,
            in the land of geometry. Today's article takes place...
        </p> 

        <div class="demo-canvas" data-demo="rast1-demo"></div>

        <p>
            ... on the pixel grid! If you can peel your eyes away from the absolute graphical marvel I've
            created above, we're going to dig into exactly what's going on inside those little squares,
            and how they interact. This series will go on for multiple parts. Today, we're going to start
            with the basics of 2D graphics: the graphics buffer and its layout, abstract shapes, a basic
            introduction to sampling theory, lerping and blending colors, transparency, and end it off by
            adding a bit of antialiasing!
        </p>
        <p>
            A bit of note about the interactive demos on display in here today. First, I'm presenting a
            "zoomed in" buffer so you can see the pixels easier. Specifically, each "demo pixel" here
            is 16 "real pixels" wide, and the same tall. The grid itself is composed of 46 of these
            "demo pixels" horizontally, and 10 of them vertically, which are basically a few arbitrary
            constants I chose to make it fit nicely inside these margins, which are 800 "real pixels" wide.
        </p>
        <p>
            It might hurt your head to think about "demo pixels" and "real pixels". Graphics programming
            often takes place in lots of different coordinate spaces like this. After quite a long time of
            doing it, I still get confused; it's just part of the job description. If you are having trouble,
            what helps me is to just turn off the monitor, grab some physical pen and paper, and just draw
            it out. Often times, just drawing and labelling the parts often shows me my confusion.
        </p>
        <p>
            What doesn't help is blind trial and error. If you are serious about graphics programming, you
            will eventually reach a point when things go wrong, and you'll start peppering <code>x*8</code>
            and <code>(y+15)/8</code> into your code in a vain attempt to just get everything to match up
            correctly. You will start fiddling with your plus and minus signs, wildly reversing your
            translations and rotations at random in desperation. You might find yourself even getting close,
            but later on, finding that it breaks something else. It's OK, and we've all been there. I did it
            multiple times writing this article. Just take a break, come back, and try to figure out what's
            really going on.
        </p>
        <p>
            ... To prevent any confusion like this, let's start at the beginning.
        </p>
        </section>

        <section id="coordinates">
        <h3>Coordinates</h3>
        <p>
            While I'm sure everyone here doesn't need this refresher, let's over some notation and basic math
            for how to address pixels in this grid. We often treat pixel buffers as large arrays in memory,
            and we usually leave them one-dimensional, and do the math ourselves to find a specific index
            for a given position.
        </p>
        <p>
            Buffer layouts in the real world have a lot of subtleties: stride alignment, endianness, pixel formats.
            If you don't know what any of those things are, don't worry, I'll explain them later. In this article series,
            we'll be using the convention established by HTML5's
            <a class="code-literal" href="https://developer.mozilla.org/en-US/docs/Web/API/ImageData">ImageData</a>
            API. It sees this pixel grid as a giant, one-dimensional array of bytes, with each pixel taking four
            bytes: red, green, blue, alpha, in that order.
        </p>

        <p>
            We can find the index of the first byte of a pixel, and vice versa, with some very simple math:
        </p>

<pre><code class="javascript">var BYTES_PER_PIXEL = 4;

function indexForPixelLocation(imageData, x, y) {
    return (y * imageData.width + x) * BYTES_PER_PIXEL;   
}

function pixelLocationForIndex(imageData, idx) {
    var pixelIdx = Math.floor(idx / BYTES_PER_PIXEL);
    var y = Math.floor(pixelIdx / imageData.width);
    var x = pixelIdx % imageData.width;
    return { x: x, y: y };
}
</code></pre>

        <p>
            Familiarize yourselves with what these functions do &mdash; they convert from the x and y
            coordinates of pixels on the grid to their index into the array of pixels. Pixels go from
            top left to bottom right, first in the X direction, then in the Y direction. The top left of
            the pixel grid is at <span class="definition">0, 0</span> at index 0. The next pixel in the
            array, which starts at index 4, is located directly to the right.
        </p>
        </section>

        <section id="draw-rectangle">
        <h3>Let's Draw a Rectangle</h3>
        <p>
            Now that we've established ourselves with the format of the pixel grid, let's try drawing
            a rectangle. For simplicity's sake, let's just fill it with black for now.
        </p>

<pre><code class="javascript">function fillPixel(imageData, x, y) {
    var idx = indexForPixelLocation(imageData, x, y);
    imageData.data[idx + 0] = 0; // Red
    imageData.data[idx + 1] = 0; // Green
    imageData.data[idx + 2] = 0; // Blue
    imageData.data[idx + 3] = 255; // Alpha
}

function fillRectangle(imageData, x1, y1, width, height) {
    for (var y = y1; y < y1 + height; y++)
        for (var x = x1; x < x1 + width; x++)
            fillPixel(imageData, x, y);
}
</code></pre>

        <p>
            And let's try it out!
        </p>

        <div class="demo-canvas" data-demo="rast1-fillrect-basic"></div>

        <p>
            This should be pretty straightforward, but there are a few peculiarities I do want to go over.
            First, it may strike some of you as odd to iterate over the "y" first. Graphics programmers
            often think about things in rows. This is a holdover from early computer graphics, and it's
            for performance reasons &mdash; if you think about the memory layout of our pixel grid, you'll
            notice that I'm iterating over the indexes in order. While RAM does stand for "random access memory",
            CPUs cheat and have things called "caches". Just know that it is cheaper to write to indexes
            in order than it is to actually access randomly.
        </p>
        <p>
            You will often see this pattern, iterating over the rows, rather than the columns, come up in
            graphics algorithms, even for things that aren't pixel grids or such. This will become more
            apparent when we start going over more complex topics.
        </p>
        <p>
            It should also hopefully be pretty clear how to replace this "black" with another color, so I
            won't bother explaining that. I will, however, up the ante. Let's try filling this rectangle
            with something a bit more fancy. ... Let's try a gradient.
        </p>
        </section>

        <section id="lerp">
        <h3>Space and Time</h3>
        <p>
            Gradients aren't actually that tricky, but we do need some basic grounding in one of the most
            fundamental concepts of computer graphics: <span class="definition">linear interpolation</span>,
            or, the "lerp" for short. Yes, lerping is that important that we give it a special abbreviation,
            which can even be used as a verb.
        </p>
        <p>
            It's actually a simple concept. A lerp takes two values, a position parameter, often called
            <span class="definition">time</span>, and returns something in between. A time of 0 gives you
            the first value. 1 gives you the second value. 0.5 gives you the value halfway in between both.
        </p>

<pre><code class="javascript">function lerp(a, b, t) {
    return (a * (1.0 - t)) + (b * t);

    // It's also sometimes written as:
    // return a + ((b - a) * t);
    // ... which might be easier to read for some people.
    // The two are mathematically equivalent.
}

function draw(imageData, secs) {
    var startX = 1;
    var endX = 38;
    var x = Math.floor(lerp(startX, endX, secs));
    var y = 1;
    fillRectangle(imageData, x, y, 8, 8);
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-fillrect-lerp"></div>
        <p>
            A few more notes. This time variable is often called "t", but I've also seen "position" or "pos",
            and "alpha". I don't like "position" because I use that to mean a point on our pixel grid,
            and I don't like "alpha" since it's confusing when we already have an "alpha channel", which is
            completely unrelated to the lerp here.
        </p>
        <p>
            The time parameter, "t", is between 0 and 1. In this case, we derive it from the number of seconds
            that have passed in the animation, so it is quite literally "time". One obvious thing we can do is
            to warp time. We can multiply to speed it up, divide it to slow it down, but we can also warp it 
            in more fancy ways. For instance, to make it slow down near the ends, we can warp "t" by passing it
            through a famous easing curve known as "<a href="https://en.wikipedia.org/wiki/Smoothstep">smoothstep</a>":
        </p>

<pre><code class="javascript">function lerp(a, b, t) {
    return (a * (1.0 - t)) + (b * t);
}

function smoothstep(t) {
    return t*t*(3 - t*2);
}

function draw(imageData, secs) {
    var startX = 1;
    var endX = 38;
    var smoothSecs = smoothstep(secs);
    var x = Math.floor(lerp(startX, endX, smoothSecs));
    var y = 1;
    fillRectangle(imageData, x, y, 8, 8);
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-fillrect-lerp-smoothstep"></div>

        <p>
            ... which looks a bit easier on the eyes. The etymology behind the time "t" parameter is derived
            from the math-y "f(t)" sense of the word "time". We don't have to use an input that corresponds
            to time passing in the real world: we can use any value between 0 and 1 as the input. We also can
            choose to lerp things other than position. For instance, we can lerp between two colors with just
            a bit more code.
        </p>
<pre><code class="javascript">function newRGB(r, g, b) {
    return { r: r, g: g, b: b };
}

// Lerp between colors "color1" and "color2".
function lerpRGB(color1, color2, t) {
    var newR = lerp(color1.r, color2.r, t);
    var newG = lerp(color1.g, color2.g, t);
    var newB = lerp(color1.b, color2.b, t);
    return newRGB(newR, newG, newB);
}
</code></pre>
        <p>
            This isn't doing anything more fancy than just doing a lerp across all three components in a
            color, and if we draw a ton of 1px-wide rectangles that all use this:
        </p>
<pre><code class="javascript">function fillPixel(imageData, x, y, rgb) {
    var idx = indexForPixelLocation(imageData, x, y);
    imageData.data[idx + 0] = rgb.r;
    imageData.data[idx + 1] = rgb.g;
    imageData.data[idx + 2] = rgb.b;
    imageData.data[idx + 3] = 255; // Alpha
}

function fillRectangle(imageData, rgb, x1, y1, width, height) {
    for (var y = y1; y &lt; y1 + height; y++)
        for (var x = x1; x &lt; x1 + width; x++)
            fillPixel(imageData, x, y, rgb);
}

function draw(imageData) {
    var startX = 1;
    var endX = 45;
    var y = 1, width = 1, height = 8;

    var red = newRGB(255, 0, 0);
    var blue = newRGB(0, 0, 255);
    for (var x = startX; x &lt; endX; x++) {
        var t = (x - startX) / (endX - startX);
        var rgb = lerpRGB(red, blue, t);
        fillRectangle(imageData, rgb, x, y, width, height);
    }
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-lerp-gradient"></div>
        <p>
            ... we end up with a smooth transition between the colors, also known as a "linear gradient".
        </p>
        </section>

        <section id="gradients">
        <h3>Styling our Rectangle</h3>
        <p></p>
        <p>
            Let's try applying this knowledge to our rectangle drawing code. The biggest change here is that
            we'll need to modify what colors we draw based on the position in the image. To help us out, let's
            introduce a new concept, known as the "fill style". This is a function that takes a position, and
            returns a color for that position. The simplest possible fill style is a radial gradient, whose
            color depends on the position from the center.
        </p>
<pre><code class="javascript">// Basic fill style.
function newSolidFill(rgb) {
    return function(x, y) {
        // A solid fill returns the same color, no matter the position.
        return rgb;
    };
}

function newRadialGradient(centerX, centerY, radius, centerRGB, edgeRGB) {
    return function(x, y) {
        // Calculate distance from the center point. Basic Pythagoras.
        var distX = x - centerX, distY = y - centerY;
        var distance = Math.sqrt(distX*distX + distY*distY);

        // If we're outside the circle, then just return the color at the edge.
        // This is a choice -- we could instead choose to repeat or ping-pong
        // between the colors.
        if (distance >= radius)
            return edgeRGB;

        // Translate the [0, radius] ranged value to a [0, 1] ranged value
        // so we can lerp the colors.
        var t = distance / radius;
        return lerpRGB(centerRGB, edgeRGB, t);
    };
}

// The same code as above, but slightly adapted to handle fill styles
// and custom colors.

function fillRectangle(imageData, fillStyle, x1, y1, width, height) {
    for (var y = y1; y &lt; y1 + height; y++) {
        for (var x = x1; x &lt; x1 + width; x++) {
            var rgb = fillStyle(x, y);
            fillPixel(imageData, x, y, rgb);
        }
    }
}

function draw(imageData) {
    var x = 19;
    var y = 1;
    var red = newRGB(255, 0, 0), blue = newRGB(0, 0, 255);
    var gradient = newRadialGradient(x + 4, y + 4, 6, red, blue);
    fillRectangle(imageData, gradient, x, y, 8, 8);
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-gradients"></div>
        <p>
            The biggest complexity here is figuring out which "t" to use. In the case of a radial gradient,
            it's actually just the distance from the center point, normalized against the radius.
        </p>
        <p>
            As an exercise, try working out, using this base, how to have arbitrary gradient stops at different
            time values, rather than just two colors at the starts and ends.
        </p>
        </section>

        <section id="circles">
        <h3>Drawing Other Shapes</h3>
        <p>
            Now that we've become familiarized with the concepts of rendering boxes and fills, let's try our
            hand at something a tad bit more fancy &mdash; rendering other shapes. To start with, let's try
            a circle. We just learned above how to calculate the distance of a point x, y against the center
            of a circle with any radius. Once we have that, we can just run over our pixel grid, test when
            we're "inside" the circle, and if so, choose to fill in the pixel.
        </p>
        <p>
            The only complication here is that we have to pick some start and end bounds for where we start
            iterating. We could use our <em>entire</em> pixel grid, but we know a bunch of pixels will never be
            filled in. We need a tight set of pixels. Thankfully, for a circle, it's quite easy to compute.
            By definition, the left edge ("x1", since it is the left X coordinate) is the X coordinate of the
            circle's center minus the radius, and the right edge ("x2") is the center plus the radius. The same
            thing happens for the top and bottom edges.
        </p>
<pre><code class="javascript">function fillCircle(imageData, fillStyle, centerX, centerY, radius) {
    var x1 = centerX - radius, y1 = centerY - radius;
    var x2 = centerX + radius, y2 = centerY + radius;
    for (var y = y1; y &lt; y2; y++) {
        for (var x = x1; x &lt; x2; x++) {
            var distX = (x - centerX), distY = (y - centerY);
            var distance = Math.sqrt(distX*distX + distY*distY);
            if (distance &lt;= radius) {
                var rgb = fillStyle(x, y);
                fillPixel(imageData, x, y, rgb);
            }
        }
    }
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-circle"></div>
        <p>
            Oof. What happened here? This doesn't look very... circular. Is it an off-by-one error? It looks like it might be.
            It's tempting to brute force your way to a possible fix: changing the <span class="code-literal">&lt;=</span>
            above to a single <span class="code-literal">&lt;</span>, peppering various <span class="code-literal">+ 1</span>
            and <span class="code-literal">-1</span>s throughout. But, trust me on this, this approach won't net you anything.
            It's actually not an off-by-one error, it's an off-by-0.5 error.
        </p>
        <p>
            "Wha?" I hear some of you cry.
        </p>
        <p>
            There is actually nothing wrong with the above code in the abstract. Instead of this being a simple implementation
            detail change, the issue with this algorithm is actually a more fundamental and conceptual one, one that causes us
            to rethink a bit about how we're imagining the pixel grid. You might also have spotted it above in the radial
            gradient example: the gradient isn't centered, it's sort of down and to the right. These are both related problems.
        </p>
        <p>
        </section>

        <section id="sampling">
        <h3>Sample Location</h3>
        <p>
            When we do something like the algorithm above &mdash; iterate over a bunch of pixels, and then test whether a pixel
            should be in or out, we're making use of a concept known as <span class="definition">sampling</span>.
            Basically, we have some functional concept of a shape, like a circle, and we can give it different x and y
            points and it tells us whether they are inside or outside of the circle. But what do these points actually mean?
        </p>
        <p>
            Well, we know that in our pixel grid, each one of these numbers corresponds to a pixel. But have we thought
            about the <em>abstract space</em> where these circle descriptions live? We're talking about a circle
            centered at, let's say, 5, 5, with a radius of 10. We have to have some concept of mapping this abstract
            space to the pixel grid. Up until now, we haven't thought about this and have been hacking it together
            based on what makes sense. But to get this right, we need to think more closely about the relationship
            between the two.
        </p>
        <p>
            I'm going to cheat, and for my next figure, show you what this abstract space circle looks like we've been
            using so far, laid on top of the pixel grid.
        </p>
        <div class="demo-canvas" data-demo="rast1-circle-overlay"></div>
        <p>
            Maybe the revelation is clear now about what's actually going on. If not, don't worry. Right now, when
            we test each pixel against the abstract space circle, we've been testing whether the <em>top left</em>
            of each pixel's square is inside the abstract circle. When you think about it, though, that doesn't
            quite make sense. Really, what we're trying to ask is "is more than 50% of the pixel square inside the
            circle". Using something like the pixel's center would more accurately answer that question.
        </p>
        <div class="demo-canvas" data-demo="rast1-circle-overlay-fixed"></div>
        <pre><code class="javascript">function fillCircle(imageData, fillStyle, centerX, centerY, radius) {
    var x1 = centerX - radius, y1 = centerY - radius;
    var x2 = centerX + radius, y2 = centerY + radius;
    for (var y = y1; y < y2; y++) {
        for (var x = x1; x < x2; x++) {
            var distX = (x - centerX<strong> + 0.5</strong>), distY = (y - centerY<strong> + 0.5</strong>);
            var distance = Math.sqrt(distX*distX + distY*distY);
            if (distance <= radius) {
                var rgb = fillStyle(x, y);
                fillPixel(imageData, x, y, rgb);
            }
        }
    }
}
</code></pre>
        <p>
            And indeed it does! By adjusting our <span class="code-literal">fillCircle</span> function to test distance
            against the pixel's <em>center</em> in the abstract space, we get something that looks a lot more circular.
            Since pixel centers are halfway between pixels, all we need to do is add 0.5 to both dimensions before
            calculating the distance.
        </p>
        <p>
            This also explains the bizarre gradient bug we were seeing earlier. When we were comparing distances in the
            gradients, we were also comparing distances with the top left of the pixel, rather than the pixel's center.
            I'll leave it as an exercise to the reader to add the necessary <span class="code-literal">+ 0.5</span>s to
            fix that one.
        </p>
        <p>
            If you've worked with graphics APIs before like HTML5 &lt;canvas&gt;, you might have had to add these 0.5
            increments yourselves, e.g. to lines, to make the resulting line look sharp. This is because a line is basically
            a "thin" rectangle which is <em>lineWidth</em> wide, and <em>centered</em> upon the position you give it.
            HTML5 &lt;canvas&gt; also uses this "pixel center" sampling strategy. Giving it a bit of thought (imagine a tall,
            skinny rectangle "growing" in width from a pixel's center until it becomes two pixels wide), and it should be
            obvious why you need to add 0.5 offsets yourself.
        </p>
        </section>

        <section id="transparency-and-blending">
        <h3>Transparency and Blending</h3>
        <p>
            OK, so now we have basic shapes, and basic fills. What would be really cool is to try to add
            transparency, and to blend multiple shapes together. This is actually easier than you think, at least
            for a toy implementation. But first, the theory. As a term stolen from
            <a href="https://en.wikipedia.org/wiki/Compositing">the visual effects industry</a>, blending multiple
            transparent shapes together is formally called
            "<a href="https://en.wikipedia.org/wiki/Alpha_compositing">alpha compositing</a>", though I don't like
            that term very much, for reasons that will become clearer as the rest of the article goes on.
            I prefer "blending".
        </p>
        <p>
            For our toy implementation, we'll make some simplifications. Our resulting pixel grid is designed
            to be displayed directly on my monitor. Since my monitor isn't transparent (at least <a href="https://www.theverge.com/2016/1/7/10733626/panasonic-transparent-screen-display-ces-2016">isn't yet!</a>),
            we won't bother changing its storage, and just assume it's full opaque. However, we'll add a new
            parameter to our fill color: <span class="definition">alpha</span>, or the "A" in "RGBA".
            Alpha is commonly taken to be identical with "transparency", though this isn't fully accurate,
            as we'll see later (and one of my personal pet peeves)! If we wanted to take an image we rendered
            and then reuse it, transparency and all, it would definitely be appropriate to retain the alpha
            channel. This makes the math a bit too complicated for this basic introduction though, so I'll cheat
            and omit it for now.
        </p>
        <p>
            We'll also be a bit more formal about our fill parameters. We'll call the fill pattern the
            "source image", and we'll call the pixel grid that's being filled the "destination image". To blend
            an RGBA "source image" into the opaque "destination image", instead of just setting the values like
            the old <code>fillPixel</code> did... we lerp them!
        </p>
        <pre><code class="javascript">function newRGBA(r, g, b, a) {
    return { r: r, g: g, b: b, a: a };
}

function getPixel(imageData, x, y) {
    var idx = indexForPixelLocation(imageData, x, y);
    // Reminder: ImageData stores things as a giant array with bytes
    // in "RGBA" order.  So index 0 = R, index 1 = G, and index 2 = B.
    return newRGB(imageData.data[idx + 0],
                  imageData.data[idx + 1],
                  imageData.data[idx + 2]);
}

function blendPixel(imageData, x, y, src) {
    // Retrieve the existing pixel in the destination image.
    var dst = getPixel(imageData, x, y);
    // Lerp using the src's alpha to blend.
    var blended = lerpRGBA(dst, src, src.a);
    fillPixel(imageData, x, y, blended);
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-circle-simple-alpha"></div>
        <p>
            It's a bit clunky, but it works fine. If you think about it, it makes sense too: at 0% alpha, you
            want the untouched pixel grid (the destination), and at 100% alpha, you want the source fully filled
            in between, and at 50%, you want half of one, half of the other.
        </p>
        </section>

        <section id="antialiasing">
        <h3>Anti-aliasing</h3>
        <p>
            So, this is looking a lot better. We have shapes, we have colors and gradients. But it still doesn't
            look great. The edges are all "jaggies", like you might see out of something made entirely in MS Paint.
            Looking at the zoomed in pixel grid vs. the abstract one, it should be obvious what the problem is:
            the pixel grid is much, much coarser than the abstract grid! In signal processing terms, we're
            <a href="https://en.wikipedia.org/wiki/Aliasing" class="definition">aliased</a>: to construct our pixel
            grid, we're sampling from a much <span definition="definition">higher frequency</span> space, the
            abstract grid, and that results in aliasing artifacts.
        </p>
        <p>
            ... OK. If that was a bit too technical, here's a quick signal processing intro:
            the word "frequency" just means "how fast things change". In our case, these "changes" are basically
            "how fast" our circle is changing, in the abstract grid case, and how fast our pixels
            are allowed to change, in the concrete grid case. Our abstract circle changes from "being inside" to
            "being outside" much faster than how often the grid can change, or, at a "higher frequency".
        </p>
        <p>
            ... Erm, that might also be too technical. Imagine a striped rectangle in our abstract grid that changes rapidly
            from black to white over and over again. Sampling this in our extremely course pixel grid will have a
            seemingly random pattern of sometimes white pixels and sometimes black pixels. This is known as a
            <a href="https://en.wikipedia.org/wiki/Moir%C3%A9_pattern" class="definition">moire pattern</a>,
            and it happens when we can't sample fast enough or fine enough for the source.
        </p>

        <p>
            Signal processing theory tells us that in order to prevent artifacts like this, we have two options:
            sample faster, or just remove the high frequencies altogether. Computer graphics implementations,
            conceptually, do the former, and <em>then</em> downsample using a special filter that blends the pixels
            to avoid artifacts.
        </p>

        <p>
            If that was a bit too abstract for you, let's try writing this in code. The easiest way to sample at a high
            frequency is to literally just sample more. This is an approach known as <a href="https://en.wikipedia.org/wiki/Supersampling">supersampling</a>,
            since we're sampling at a higher, or "more super", frequency. In order to do that, we're going to need to
            refactor our code a bit and introduce a bit of infrastructure so we can sample at arbitrary positions.
            The first thing we're going to do is take that if statement testing if the point is inside the circle,
            and move it out into a new function.
        </p>
        <pre><code class="javascript">function insideCircle(centerX, centerY, radius, sampleX, sampleY) {
    var distX = (sampleX - centerX), distY = (sampleY - centerY);
    var distance = Math.sqrt(distX*distX + distY*distY);
    return (distance &lt;= radius);
}
</code></pre>
        <p>
            We also remove the "center pixel" 0.5 bias now, because this will be part of our passed in sample
            point. This gives us a nice functional sampling test. Now, for each pixel, we're going to sample
            it 16 different times, and collect the results. Watch closely. The code below might be a bit dense,
            but read it line-by-line and it should make sense.
        </p>
        <pre><code class="javascript">function fillCircle(imageData, fillStyle, centerX, centerY, radius) {
    // Sample the shape 16 times in a 4x4 grid.
    var nSubpixelsX = 4;
    var nSubpixelsY = 4;

    var x1 = Math.floor(centerX - radius), y1 = Math.floor(centerY - radius);
    var x2 = Math.ceil(centerX + radius), y2 = Math.ceil(centerY + radius);
    for (var y = y1; y &lt; y2; y++) {
        for (var x = x1; x &lt; x2; x++) {
            // Compute the coverage by sampling the circle at "subpixel"
            // locations and counting the number of subpixels turned on.
            var coverage = 0;
            for (var subpixelY = 0; subpixelY &lt; nSubpixelsY; subpixelY++) {
                for (var subpixelX = 0; subpixelX &lt; nSubpixelsX; subpixelX++) {
                    // Sample the center of the subpixel.
                    var sampX = x + ((subpixelX + 0.5) / nSubpixelsX);
                    var sampY = y + ((subpixelY + 0.5) / nSubpixelsY);
                    if (insideCircle(centerX, centerY, radius, sampX, sampY))
                        coverage += 1;
                }
            }
            // Take the average of all subpixels.
            coverage /= nSubpixelsX * nSubpixelsY;

            // Quick optimization: if we're fully outside the circle,
            // we don't need to compute the fill.
            if (coverage === 0)
                continue;

            var rgba = fillStyle(x, y);
            // Apply coverage to the alpha.
            rgba = newRGBA(rgba.r, rgba.g, rgba.b, rgba.a * coverage);
            blendPixel(imageData, x, y, rgba);
        }
    }
}
</code></pre>
        <div class="demo-canvas" data-demo="rast1-circle-aa"></div>
        <p>
            There's quite a lot to go through here, but the core important idea is that for each pixel,
            we're sampling the abstract grid 16 times, and figuring out how much of the abstract circle this
            square pixel contains. Once we know this, we compensate by making the pixel more transparent.
            This makes some intuitive sense: if a circle only covers half of a pixel, the other half should be
            occupied by what's underneath it, so the two colors get merged into one. This, unfortunately, has
            a cost: we still only have 8 bits per channel to work with. We are trading color depth for the
            appearance of more space. This is why it's hard to "un-anti-alias" pictures in Photoshop if
            you've ever tried to remove a background or similar: because some of the original color was lost!
        </p>
        <p>
            Secondly, note the use of the word <span class="definition">coverage</span>, which tells
            you how much of the concrete pixel was covered by the abstract shape. Note that we also put this
            coverage value into the alpha of our source, even though it's conceptually <em>not</em> a
            transparent image. This is important: the alpha channel of an image isn't only just for
            transparency, it's also used for pixel coverage, though they do end up blending the same, and so
            we tend to combine the two into one channel.
        </p>
        <p>
            One other thing: You might notice that I'm not computing the fill style at every subsample,
            only the shape's coverage. This is an optimization known in the 3D graphics world as
            <a href="https://www.khronos.org/opengl/wiki/Multisampling">multisampling</a>. The hope is that
            the fill color of just the pixel's center really doesn't change from an average of all possible
            sample points, but the coverage does. When you go into a game's advanced settings and turn on
            "MSAAx16", this is exactly the algorithm that runs there.
        </p>
        <p>
            You might also notice that the animation still seems a bit "jerky". This is because I'm drawing
            the circle locked to the pixel grid with a <code>Math.floor</code>. But now we can represent
            arbitrary sample points thanks to proper antialiasing. Taking the <code>Math.floor</code> out lets
            us draw something like <code>drawCircle(3.5, 2.32, 6.7);</code>, to pull some numbers out of a hat.
            Our abstract grid can represent fractions of pixels just perfectly, and, with us taking multiple
            samples, our circle should look a lot more... well... circular, with fractional sample positions.
        </p>
        <div class="demo-canvas" data-demo="rast1-circle-aa-smooth"></div>
        <p>
            I've also slowed down time and given you a visualizer tool to see the subpixel sampling in action.
            Just hover over a pixel to see the details of it.
        </p>
        <p>
            Also, now that we can draw shapes starting at any pixel, we have to be a bit more careful computing
            the bounding box to help accommodate this. Note the additions of <code>Math.floor</code> and
            <code>Math.ceil</code> above; I sneakily put those in there, but they are required for this to work
            correctly. Otherwise, the X and Y values we pass to <code>blendImage</code> would be fractional,
            and our attempts at setting the ImageData array would fail on fractional indexes.
        </p>
        <p>
            And last, I should mention. Super- or multisampling are not the only approaches to doing antialiasing.
            Another approach here is to use analytic methods to figure out how much area the shape actually covers.
            The common algorithm for this is commonly attributed to Raph Levien in the
            <a href="http://www.levien.com/libart/">libart rendering library</a>. I might do an interactive article
            for this some other day, but for now, I'll link to Sean Barrett, who has
            <a href="http://nothings.org/gamedev/rasterize/">an excellent whiteboard explanation</a> up on his website.
            The sampling approaches are easier to understand, much more visualizable and obvious to the theory, and
            give us pretty great results.
        </p>
        </section>

        <section id="next-time">
        <h3>Coming up next...</h3>
        <p>
            This was probably already a huge article to read through. Thank you for making it to the bottom! You're
            a real trooper! As always, this is only the starting point of a much deeper subject. I welcome all
            comments and questions, including ideas for additional demos to help make hard-to-understand concepts
            either. Email me, open a GitHub issue, play around with the code and see what you can make happen. The
            code for every single demo seen today is open-source, with extra comments about what's going on. It's
            also a bit more complete and refactored than what you see in the article itself. Perhaps you can take
            some inspiration from that!
        </p>
        <p>
            My plan is that next time, we'll expand on graphics further with fun things like linear transformations,
            more shapes, like complex filled polygons, Bezier curves, and maybe a bit of extra fun stuff with
            perspective-textured triangles. That said, these plans aren't finalized, and if you would like me to
            cover something extra, ideas are always welcome!
        </p>
        <p>
            Thank you to everyone that left comments on the last article I made. This article has been a long time
            coming. Since my last one was written, I've made a personal decision to leave the Linux, X11, and
            Wayland worlds mostly behind. However, I'm still at a job where I interact with graphics every day,
            and I, of course, will never tire of teaching people stuff. Even if it takes me a year to actually
            finish an article. I'm hoping the expanded focus will help a lot with my motivation, though.
        </p>
        </section>

        <a class="comments-link" href="https://github.com/magcius/xplain/issues/28">Comments</a>
        <div class="nav-bottom"></div>
    </article>

    <script src="article.js"></script>

    <script src="../src/region.js"></script>
    <script src="../src/canvas-util.js"></script>
    <script src="../src/article-demos/demos.js"></script>
    <script src="../src/article-demos/rast1.js"></script>

    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/8.9.1/styles/railscasts.min.css">
    <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/8.9.1/highlight.min.js"></script>
    <script>hljs.initHighlightingOnLoad();</script>

    <script>
      (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
      (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
      m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
      })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
      ga('create', 'UA-35480078-2', 'magcius.github.io');
      ga('send', 'pageview');
    </script>
</div></body>
</html>