The Math Behind Font Rasterization | How it Works

[Music] if you have ever written a document read a book made a powerpoint presentation built a website or even worked with text in general then you have used font rasterization font rasterization is the process of converting a vector description to a raster or bitmap description in other words font rasterization is converting mathematical formulas to pixels on the screen that you're using we use this process every day when we use our phones but have you ever wondered how it really works [Music] computers display graphics to us by using pixels on a screen in the 80s and 90s we had very limited resolutions because computing power was not sufficient enough to support a lot of pixels on the screen now we have resolutions that can contain upwards of 33 million pixels on a screen compared to a nintendo game boy which only has around 23 000 pixels on the screen this is insane now why are we talking about pixels and screen resolutions because in order to understand the evolution of font rasterization you must understand where we came from and where we are now if i asked you how to represent text using a limited number of pixels how would you do it well the easiest way i can think of would be to simply plot the pixels in the shape of letters this is simple and straightforward and it's very easy to communicate to a computer that deals with pixels so plotting the letter a would look something like this i could also plot the letter b and so on and so forth we can very easily calculate how much computer memory this would take up per character set if we assume each pixel is represented by 8 bits allowing a grayscale image to add some variety and each letter is only 32x32 pixels then storing the english alphabet would only take up around 425 000 bits we know that eight bits is one byte so this would take up 53 000 bytes or around 53 kilobytes this is great we can store an alphabet in a way that's easy to communicate to the computer and it also takes up very little space on the computer but there's one problem what if we want a different font size unfortunately our whole technique breaks down here the process i just described is how the bitmap file format works which was created around 1986. around 1991 apple decided to add support for a new font file format that would solve our problem the truetype file format so we must revisit our original question if i asked you how to represent text using an unknown number of pixels how would you do it before we assumed you knew how many pixels you could use and it was limited but now let's assume that the user could use a 12 pixel font size or a 512 pixel font size how do you represent the letter a for both of those well you could create a bitmap file for both pixel sizes and switch the file for different sizes but this is very inefficient and costly a 512 pixel font size for the english alphabet would take around 109 million bits or 13.3 megabytes we are now wasting a lot of memory for the different font sizes and we are multiplying the amount of work for ourselves by having to recreate the font for every different font size instead let's use math to solve this problem [Music] we know that you can represent curves in math using an equation there are different kinds of curves that you can create for example a quadratic curve looks like this [Music] a cubic curve looks like this a logarithmic curve looks like this and there are many more we can also translate these curves by simply adding offsets to our equation we can offset any curve vertically by adding a number outside the equation and horizontally by adding a number inside the equation we can do all sorts of transformations to our curve by modifying it slightly to get different results now we know two things one we can represent any curve using an equation two a letter is just a combination of several different types of curves now that we know this we can set out to represent a font as a series of mathematical curves that describe each letter but how do we do this we could define a set of points that we want our curve to pass through then we could connect each of these points with a straight line but for letters like c this won't work very well because of the curvature [Music] we could create a polynomial to pass through each of these points and there are entire procedures to do this one of these procedures is known as lagrange interpolation which will create a polynomial that will pass through all of your points but this doesn't give sharp edges that are expected in a letter like capital a so we have two techniques that work for different types of letters why don't we combine them that's exactly the process that the true type file format takes it combines straight lines and simple second order bezier curves to describe a set of letters a bezier curve is special because it can represent a curve using a set of control points p0 through pn where p0 and pn are the end points and all the in between points are control points these control points describe how the curve should bend and if we keep it simple with second order bezier curves then we only ever have three points to describe a curve that only bends in one direction now we have a solution we can represent the outline of a letter using a series of points and a description that tells us whether the next two points are a line or the next three points or a bezier curve we have another problem though sure we can draw the outline of the shape but this does not help us draw solid letters remember computers are made of discrete pixels and all we have is a way to describe a series of curves that describes the outline of the letter so how do we fill the letter in well the simplest way we could do this is by drawing the outline first this will give us a closed set of pixels which outline the letter once we have the outline drawn we can simply pick a pixel inside the letter and fill the shape from there this will work fairly well however when we get to a complex letter like capital b we run into another problem what is the inside of the letter we intuitively know that it's these pixels but how does the computer know it's these pixels and not the pixels inside the holes as well well some clever mathematicians have already solved this for us let's look at this problem from another angle instead of drawing the outline why don't we test each pixel to determine whether it is inside the outline or outside the outline if we think about it this way we can come up with a solution that should work notice that with the letter capital b we can look at a pixel over here and if we draw a line to the right how many times do we hit a line well we run into four lines what about when we start inside here we run into three lines and what about in here two lines and here we run into one line there's a pattern every time a pixel is inside the outline of b we run into an odd number of lines going to the right but if the pixel is outside the outline of b we run into an even number of lines the truetype file format simplifies this concept even more by introducing a winding contour which is a curve that goes clockwise and a non-winding contour which is a curve that goes counterclockwise whenever we test a pixel we can simply add one every time we hit a winding contour and subtract one every time we hit a non-winding contour when we add it all up we will get zero if the pixel is outside the curve and a non-zero value when the pixel is inside the curve [Music] this brings up the question of how do we test if a pixel is going to hit a curve in order to understand how we can check if a pixel is going to hit a curve we first have to understand how a bezier curve works let's start with the simplest bezier curve which happens to be a straight line imagine we have two points p0 and p1 what if we want to represent the line between these two points using one function when we input 0 to this function we should get p0 and when we input 1 to this function we should get p1 we will call this parameter t if p0 is located at 10 0 and p1 is at 20 0 and i asked you what p of 0.5 is what would you say if you said 15 you guessed correctly what about p of 0.75 well if you guess 17.5 you guess correctly this makes a lot of sense to us intuitively but what is our brain doing behind the scenes we can abstract this into an equation pretty easily we're simply doing 20 minus 10 times t plus 10. if we abstract this one more time we can say more generally that p of t equals p1 minus p0 times t plus p0 now we have one equation that can give us any line based off of two points let's rearrange this equation to look like p of t equals p1 times t minus p0 times t plus p0 we can factor out p0 and we get an equation that looks like this p of t equals p1 times t plus 1 minus t times p0 now that the equation looks like this we can actually intuit what is happening behind the scenes we're actually taking a weighted average between p0 and p1 which gives us our result it will be helpful to think of a bezier curve as a weighted average between all the control points this is great but this still doesn't help us figure out how to find a curve where a third point is the control point well imagine that we now have a third point and we want to draw a curve that bends towards that control point when we define a bezier curve we want points p0 and p2 to have equal weight and how it bends towards p1 how can we do this well let's draw two straight lines one from p0 to p1 and the other from p1 to p2 we know that we can create an equation p of t for p0 to p1 and for p1 to p2 let's call these lines q0 and q1 what if we just draw a third line from q0 to q1 and we create an equation to interpolate between them well we can use the same equation as before p of t equals p1 times t plus p0 times 1 minus t we can rewrite this though in terms of q0 and q1 this would give us p of t equals q one times t plus q zero times one minus t and if we plug it all in we get this this will give us a nice bezier curve from zero to one that goes through p0 and p2 and is bent towards p1 we can graphically visualize this as an interpolation between q0 and q1 like this now that we can generate any equation for a bezier curve using three points we can find a way to see if a pixel is located at some position x y intersects with this line p of t going to the right how do we check if a pixel will hit the curve well let's imagine that the point x y is actually the origin we can achieve this mathematically by simply translating each of our points p0 p1 and p2 by subtracting the position xy now if we look at p of t in relation to the origin how can we tell if this point will intersect with p of t well this is now just a simple question of finding the roots of this equation we know that the equation is simply a quadratic function and we should remember from pre-algebra that we can solve for the roots of the quadratic function using the quadratic equation but our formula does not look like a quadratic function so how can we find the roots well let's rearrange our formula p of t if we multiply all of the terms together we get this this still doesn't look like a quadratic function so let's expand the multiplication next now p of t looks like this next we'll distribute p0 and combine like terms ah do you see it there's now a quadratic function hiding in there let's factor out all the like terms and see what we get remember a quadratic equation in standard form looks like y equals ax squared plus bx plus c looking at our equation p of t we can clearly see what a b and c are now to find the roots it's a simple matter of setting the equation equal to zero and plugging in the y-coordinates of each point and solving using the quadratic equation the quadratic equation will give us one two or no roots depending on how many roots the function has we can check each real root and see if the value t is less than zero or greater than one if it's less than zero or greater than one it will not intersect with our bezier curve if one or both of the roots is between zero and one then we will intersect with the bezier curve now we can test every pixel and see whether it will hit any of our curves simply by plugging in a few values using all of the combined techniques we can now use a collection of points to define how a letter should be drawn we can then connect these points using bezier curves and determine whether a pixel should be on or off by testing it and seeing how many curves it hits there are a myriad of other problems that you will encounter using this technique some problems to consider are what happens when a pixel hits the junction between two curves what happens when a pixel hits a horizontal line what happens when a pixel is on a curve the true type format sets out to solve all these issues with a complicated set of instructions that are defined to handle all of these edge cases which i will not be covering i hope that this video has showed you how something as simple as displaying text through a computer screen is not as simple as it may appear if we take a deep dive into the mathematics behind it all though we can see how you could create a procedure to transform a series of curves into the text that you look at on a daily basis thanks for watching

Channel: GamesWithGabe

Views: 76,205

Keywords: gameswithgabe, games with gabe, font rasterization, how does font rasterization work, bezier curves, how do bezier curves work, how do fonts work, how to rasterize fonts, the math of fonts, how does truetype work, truetype, truetype font, how do font files work, fonts, font, bezier, lines, some, SoME

Id: LaYPoMPRSlk

Length: 16min 7sec (967 seconds)

Published: Fri Aug 20 2021