A few notes on what most actual implementations do (from what I've been able to read), just in case anyone thought this was simple: * Solving quadratics is (probably much) slower and harder than just subdividing until you're smaller than pixels then testing against the x coordinates of the points closest in y coordinates. * Generally the letters (or, more generally, glyphs) are only rendered once per font size when needed and then that copy is stamped at all the places it's needed. * It's common to use the fact that PC monitors layout their pixels in vertical RGB stripes to get more horizontal resolution. * At small sizes, avoiding blurring as lines cross through pixels is more important than exactly representing the outline. The solution is pretty crazy: TTF fonts include programs that execute to adjust the coordinates based on size... and potentially other things like weight and surrounding characters! * This doesn't work if you're animating, as you can see the outlines jumping around (and it's slow). In this and other situations, like very large text or 3d, signed distance fields (or SDF), which are basically fancier bitmaps that are quite good at approximating the outline but still very fast to render.
Hey Simon! Thanks for the great overview on some of the more technical details of font rendering :). I didn't know about the optimization you can use to avoid solving quadratics, and I'd be interested to try that out at some point. I also saw your comment about .bmp, and I do apologize for any inaccuracies there. I always forget to check some of the finer details when I make videos like this haha
I thought something seemed fishy when a square root was being calculated for every pixel per curve. A prerendered cache would definitely help, but I'm not surprised that there was another possibility.
@@angeldude101 actually square roots aren't nearly as much of a problem as they were 25 years ago. GPU's have special hardware to do square roots directly, and graphics developers typically do at least one (possibly multiple square roots) per pixel 60 times a second in games to calculate things like lighting. This article gives an interesting overview cuda-programming.blogspot.com/2013/01/performance-of-sqrt-in-cuda.html . But font rasterizers are still CPU-based (as far as I know), so it can still become a problem if you don't use some optimization techniques :)
@@angeldude101 It would probably be faster to just directly rasterize the entire outline first and store it in memory. Then checking for horizontal crossings is just referencing a binary lookup. The problem is then reduced to that of efficiently drawing the outline. I recall that even drawing simple straight lines involves some tricky optimization tricks, so the best optimization for rasterizing a cubic Bezier might not be super simple. Your t-step has to be adjusted based on the size of the curve relative to the raster resolution so that you neither 1.) leave holes in your curve nor 2.) redundantly draw the same pixel multiple times. Is there an easy formula to calculate the optimal t-step given a cubic Bezier curve's 4 points and a specified resolution? That's what would really help. It's fun thinking about how I would go about the problem before looking up how it's actually done. I haven't really studied this stuff since the 90s when everything was much slower in terms of speed and everything had to be super optimized to be at all usable in real time.
You have a great style of explaining things and making them feel friendly. I especially loved the two blob characters 🥰 I hope you make many more maths videos!
Might be worth mentioning that there is an alternative solution for fast, real-time rendering of glyphs pioneered and patented by NVIDIA, which is based on using the stencil buffer to determine coverage per pixel. Basically, a pixel is subdivided into subpixels and a shader determines for each subpixel whether it is inside the glyph or not. This can be quickly determined if you are smart in how you create your geometry. Quadratic curves, for instance, can be evaluated by creating a triangle from points p0, p1 and p2 and using barycentric coordinates for the vertices. It then becomes trivial to determine whether the subpixel is inside or outside the curve. The "winding" path is then drawn first, adding values to the stencil buffer. Next, the "non-winding" paths are drawn, subtracting the values in the stencil buffer. You end up with a stencil buffer containing ones and zeroes for every subpixel. Finally, in the so-called coverage step, you calculate the coverage of each pixel by adding all subpixel values for that pixel; if 16 out of 16 subpixels are set to one, you have 100% coverage, but if only 8 pixels are set to one, you have 50% coverage and so on. The final color will be determined by using coverage as an alpha value, or by multiplying the red, green and blue colors by the coverage. Substantial research has gone into finding ways to generate optimized stencil and coverage meshes to render, as well as coming up with ways to efficiently store these mesh representations on the GPU. It's sad that this process has been patented, but on the other hand it's free to use if you own an NVIDIA GPU. See: developer.nvidia.com/nv-path-rendering
Could you express that in pseudocode somehow? I know the basics of pixel manipulation (RGB as a byte each) but don't know much about actual graphics related stuff
Other than implementing it with hardware assist, I'm surprised that Nvidia got such a general patent on the technique. These sampling methods were being done in the 1980s on devices that needed the resolution and had the memory, like the Quantel Paintbox and Truevision graphics card applications.
2:14 just for comparison, I had a Commodore 64 back in the '80s. it used 8x8 pixels for each character and only 1 bit per pixel. so the WHOLE ASCII table of 256 characters took 256*8*8*1bits = 2KB well it only had 64KB of memory anyway.
That's insane. I have a lot of respect for the programmers in the '80s and '90s era when memory was so limited. It's so easy to just use 100's of MB in a simple program now :)
I grew up programming in the '80s and '90s and when he went 'only 32 by 32 pixels' I was like ... BRO, ONLY?! I have handcrafted many 6x6 pixel fonts just to get some decent amount of text on a screen given de crappy amount of pixels (256x192 or 320x200) on screen. Fun fact: The standard 'high rez' VGA font is 9x14 pixels.
@@GamesWithGabe you may want to read about a memory saving trick called Bloom filter. it is still used in modern systems. imagine creating a speller using only a bit for each word. (well not exactly achievable, but it was "good enough")
I am seriously unable to comprehend why you have such a small following... Your content is amazing and super high effort! You should be in the millions!
Thanks Blu3! I put a bit more effort into this video than I normally do because I was submitting it to the 3Blue1Brown SoME haha. But I hope the channel will one day be in the millions :D
Just wow. I had to work with a small OLED display and hexfonts a while ago. Since then l have been wondering how more advanced responsive font systems work and this video was the perfect answer. Thank you for this bit of knowledge.
I'm looking for an interesting topic for my maths homework right now, and your way of explaining this concept made it tremendously easy! Thank you so much for the video and your beginner-friendly explanations!
I think a video on anti-aliasing would be interesting as well. The idea behind anti-aliasing is that if the edges contrast too much with the background you get a jagged looking texture along the edges on a (low resolution) bitmap screen. So what you do is you fill in the background near the edges with shades that transition between the shades of the letter and the background so that shades transition between the letter and the background more gradually. This gives less jagged looking edges. Thank for this video.
This is a very simplified overview to get you started, it's very good! The real world of fonts and font engines is spicy. Two examples: Winding orders aren't actually used consistently to mark regions, so you should calculate the normal of the glyph instead to find out which direction it's facing first. Some font tools or glyph operations may flip your glyph for example (I.e. your font has data for b, but represents d as a mirror of b through an affine transform). As for rasterizing bezier curves, font engines will actually linearize first based on a variety of heuristics since the test math is faster. I maintain a fast open source font engine on the weekends and love this stuff
Thanks for the comment Joe! Also, thanks for the extra info. When I started diving into the world of fontrasterization I had no idea how deep this rabbit hole goes, and I'm still very interested in how internet browsers are able to handle so many different fonts seemingly effortlessly. Do you have a link to your code if it's open source? If so I would love to take a look at it :)
I'm not up on my quadratic equations, but overall I enjoyed the video. I was a little distracted at the beginning, though, due to some errors. Not big things, but big enough to make the problem of raster fonts seem overwhelming. At 1:26 you introduce a 32 x 32 grid, but it's actually only 16 x16. At 2:10 you present the formulas for determining the size of a raster file for uppercase and lowercase English letters in a monospaced typeface. 1 pixel is certainly 8 bits of data for grayscale, but fonts weren't grayscale--they were bitmaps; thus, 1 pixel was 1 bit. 1 letter in your font would have occupied 16 x 16 bits. The final equation should have been 26 x 2 x 16 x 16, or 13,312 bits--not 425,000 bits. This font would take up about 1,664 bytes or 1.625 KB (K-bytes), not 53 Kb (K-bits). At 2:37 you bring in BMP files, but fonts weren't stored as BMPs. Also, Apple didn't invent TrueType to solve the problem. The problem was already being solved with Adobe Type 1 and Type 3 fonts, introduced in 1984, the same year as Macintosh. Apple made TrueType to avoid licensing fees for Type 1 fonts. Side-note: Too bad for consumers because TrueType fonts (quadratic B-spline) were inferior to Adobe Type 1 fonts (cubic B-spline). Anyway. At 3:23 you present a 12 px font at 53 KB, referring to the previous 32 x 32 px grid that was actually 16 x 16. The 512 px font is presented as being 13.3 MB. But using bits, not grayscale pixels, the 512 px font would only be 1.664 MB. Again, I really liked the description and animation of the Bézier splines--top notch work.
Oh, the Font Wars of the 90's. Fond memories. There was a huge battle between Apple's TrueType fonts (1991) and Adobe's proprietary PostScript Type 1 fonts (1984). There was much debate over the merits of both, such as Apple had special "hints" to display better at low resolution. Adobe responded with Adobe Type Manager which was the de facto standard for a while but was expensive. Then Apple licensed TrueType to Microsoft for WIndows 3.1. But Apple wouldn't license Apple Advanced Typography, so Microsoft joined with Adobe to create OpenType (1996).
I've always wondered why font rasterization was so difficult, and with a history like this I guess it should make sense why it's not that simple :). I read a bit about the Font Wars as I was researching for this video, but I'd be interested to look a bit deeper into the history at some point as well
I was a developer charged with implementing fonts in a paint package way back in the 80s. I remember that black and white Adobe Type 1 Font book well, reading it over and over and over. Our implementation was all in assembly on a TI34010 graphics accelerator. Even for back then, it ran really fast. Decode the font files, calculate the cardinal splines, experiment with fill methods, fix the corner cases, implement kerning, test, test, test. Glorious when all the steps start to work together. People these days don't realize how you had to build everything up from scratch back then, without off the shelf libraries you could just download with working examples.
Also this calculation is a lot easier if you notice that 1 pixel is 1 byte, and that 32*32 = 1024 = the number of bytes in a kilobyte, so each letter is exactly 1 kilobyte, and therefore the english alphabet with upper and lower cases is exactly 52 kilobytes.
@@UltraLuigi2401 I know that basically everyone on this planet still uses this wrong, so you have to be aware of the fact that uninformed people (and operating systems) mean 1024 bytes when they say 1 kilobyte. Actually that's simply wrong though. The prefix "kilo" means 1000 just like "mega" means 1000000 and that is NOT different for bytes. 1 kilometer = 1000 meters and 1 kilobyte = 1000 bytes. To deal with the confusion, a standard has been published in 1998 (accepted and enforced by many organizations) which introduced binary prefixes. The correct one in this case would be "kibi". So 1 kibibyte = 1024 bytes. The abbreviation is KiB instead of kB. Here's some more info if you care: en.wikipedia.org/wiki/Binary_prefix
@@flyingsquirrel3271 I'm already aware of the different binary prefixes, I just am also aware that the base 2 definition for the SI prefixes is acceptable in informal contexts (such as youtube comments), and so use them to avoid confusion for people who have never heard of the binary prefixes.
Wow nice video, really explained the concept well (except for the quadratic algebra stuff, but I don't think anyone can explain it well to me), and the visuals definitely helped me understand it.
I've been wondering how exactly fonts are represented, visualized and scaled for a long time. A few months ago I implemented Bezier curves for smoothing out path finding points in my game, so it was a nice surprise to find them here too! Thanks for a great video.
Amazing video. Really well explained and perfectly animated. Must watch all videos you have. Congratulations for your work, I'm going to share this to friends :)
While what you have described will allow one to render an outline, this will not render characters or strings of characters of high quality. Consider rendering outlines on a fix grid a progressively smaller and larger sizes. Consider the letter uppercase H, at large sizes the two vertical strokes are of equal width and height, buts as the size gets smaller one of the strokes will render 1 or more pixels narrower that the other (This is known as the picket fence problem) looking at the horizontal stroke as the outline gets smaller the stroke will render wider or narrower than the vertical strokes, it will also be displaced upward or downward from it’s desired location. This is the vertical variation of the picket fence problem. Now let’s consider Capital M with regard to the vertical strokes it has the same problem as Capital H, but now it has anew problem the diagonal strokes don’t have the same widths as the size gets smaller, but because of pixelization there weight becomes heavier ( fatter relative the the vertical strokes) this applies to all diagonal strokes as is most pronounced at 45%. The same artifacts apply to curves Consider the Character O, as it drops in size the left right top and bottom will not be the same width in pixels similarly the curve will render fatter and fatter as it approaches North east, south east south west and north west. Now lets consider a collection of characters. The horizontals are varying in width and move up and down in Y the Verticals are varying in width and moving Left and right of their entended position. The most obvious artifact is the bottom of the characters don’t share a common base line the is called baseline wander. There are solutions to all of these problems that involve looking at the morphology of each character individually and looking at strings as agrégate characters with features like common base lines inter character spacing and string widths as features that need to be preserved when they are rendered. As an exercise for the reader consider the case of a lowercase i it is clear that the size of the staff and dot need to be the same, but the relative position of the dot, size of white space and staff need to be treated holistically. When one moves away from Latin Alphabets to ideogram base writing systems like Kanji, Hangul, Nihongo, Cursive positional representations like that found in Arabic… al of the Latin problems exist as well as numerous features that need to be preserved that are not as simple as the examples that I gave above. Then there is a basic implementations philosophy issue to you codify the rendering rules in each character “smart characters, dumb rendering” or Dumb characters, smart rendering” The former requires more work per character/ideogram the latter requires more understanding of the underlying morphology issues. I think true type is a good rendering system (Smart Characters, dumb rendering) Adobe type 1 rendering is the first to market and mass adoption format is an example for (Dumb Characters, Smart Rendering). Good presentation of rendering outlines to pixels, but not really representative of what it takes to render high quality type. I am one of the creators of Adobe’s type technology and also had a hand in the reaction of TrueType. More please.
Thanks for this extra insight! I was amazed at the complexity that goes into rendering a single character as I was researching for a project I worked on (which is one of the reasons I made this video). One of the parts that blew my mind was the TrueType font program table and learning that fonts can embed programs to adjust the pixel placement for letters. Not only that, but like you alluded to rendering strings of characters also requires complex layout algorithms and other font metrics like kerning information or ligature conversions. Font rendering is an insanely deep rabbit hole to fall into, and it's very cool to hear from somebody that got to work on the original technology :) I am curious, do you know how much these algorithms for tweaking pixels at small/large font sizes still holds true? I was under the assumption that since almost all devices now have high-dpi or lots of pixels (not counting embedded devices), the pixel adjustments were less of a concern? But I honestly have no idea how browsers and other text heavy applications render text (whether it's just cached textures or real-time rendering or a mixture of both).
@@GamesWithGabe The tweaks are still needed. Higher pixel per inch monitors simply changes the magnitude of tweaks and the size at which artifacts start to dominate the rendering. The mathematics of the font descriptions is mostly a thing of beauty. Regarding string widths managing the inter character spacing and propagating the fractional errors that quantizing to a fixed pixel grid demands is one aspect of the problem. Serifs, descenders like g, y… add another dimension to the problem. Preserving white space within characters like a, 6, 9 all are madding I think of it as a foreground background problem where neither are allowed primacy. The first rookie mistake is quantizing the fonts. The earliest Macintoshes fonts had integer font widths and integer Inter-character spacing quantized at 144 to the inch. A direct artifact of the 144 dpi ImageWriters that shipped with the earliest machines. Not only did our team design the software architecture for the Laserwriter we invested precious resources in rewriting the rendering engines that were used within QuickDraw. Steve Jobs really got his moneys worth out of teaming up with Adobe to save the failing Macintosh launch. To build real WYSIWYG systems the rendering intent is only quantized when it is on the device on which it will be rendered.. Once you have something to display or print the rendering intent has to be bound to the limits of the physical devices not the other way around. This is why a Macintosh could generate camera ready copy off an image setter with 2470 dpi resolution or a 72 dpi display or a 300 dpi laser printer and the only thing that change is the output conformed more closely to the rendering intent. In the realm of maintaining caches at high resolutions and large point sizes we found that compression algorithms that worked at laser printer resolutions were horrible at even modest point sizes and had to create a unique algorithm the usual line by line xor encoding to bias the data towards long runs for run length coding performed poorly but we observed that to we were able to take advantage of the morphology of the characters and create a predictor that encoded characters that ran diagonally through the bitmap space with there own encoding and the compression ratios became much more tractable. There was talk up thread about anti aliasing real anti aliasing is dealt with by rendering the page in reverse paint order. The aliasing that comes with the trade offs of Color pixels being stacked side by side, top to bottom and several other less than ideal device dependent topologies is better dealt with by overlaying a field lens that brings all of the illuminants together geometrically . for my sins I dealt with all of the hardware vendors that came through our doors. Our brain and visual system is very forgiving of some things and really fussy about others. I knew it was going to be a bad day when I had to explain to yet another vendor why we couldn’t fix their broke assed hardware in software. It has been a long time since I thought about this stuff. Best
Nicely explained. Sadly, I really wanted to see subpixel rendering techniques and hardware acceleration mechanisms, like single-instrucion-multiple-data.
Adobe Type 1 vector fonts are from 1984, and the concept of vector fonts is older than that. The biggest difference between Type 1 vs. TrueType fonts is that the former used cubic Bézier curves, while the latter switched to quadratic Bézier curves (I think to work around Adobe’s patents?).
Adobe fonts were never vector fonts They were scalable outline fonts. There were no Patents. Later Products like Super ATM were Patented, but the font technology inside Postscript was not patented and the Type format and PostScript language were documented in books published by Addison Wesley. Super ATM allowed you to morph Fonts along a variety of axes Blending weights, Set widths, different typefaces together were just some of the dozens of ways that typefaces could be transformed. The best example I remember is taking text in two different languages and modifying the set width’s and character shapes so that the text matched up line for line. Apple and MicroSoft got it into their heads that they would be better off if they created their own implementation of PostScript. It was my responsibility to find a way to win Apple back as a customer. It was not an easy task, thanks to some of the more moderate business development folks at Apple we managed to resolve our differences and build a lot more great product together. Apple and Microsoft spent 100s of millions of dollars and ultimately abandoned the project. True type AKA type 42 fonts was meant to be a faster rendering implementation, in the end it was the same only different. The two type formats and underlying technology were merged together into Cleartype. Within 6 months of Apple and MicroSoft tell Adobe that they were going to put us out of business, Adobe Type Manager was released for the Mac and Windows “ATM” brought type one scaleable font technology to the desktop along with a Library of thousands of Fully Licensed type faces. ATM was installed on ~80% of Macs Apple grudging allowed as it probably wasn’t good for business if they broke all of their customers machines.
@@rustybucket2248 What is the difference between a "vector font" and a "scalable outline font"? To me those two terms are synonyms. When I say "vector font" what I mean is: “the outline is specified as a mathematical curve; the font is not a pixel-based raster image”. I didn’t mean to imply anything about the relationships between sub-categories of outline-based fonts.
Possible way to optimise it: Use the points defining a character to make a bounding box, then divide the area to be rendered into small patches with pointers to the characters whose bounding boxes lie within each patch. The rendering shader then only needs concern itself with testing its fragment coordinate against the characters within a given patch. Putting the relevant data into a format a fragment shader can work with might be a bit complicated, though. Going below the level of a character seems like it might be possible, but I have no idea how you would go about it, given it seems like it would require splitting the lines and curves and adding new boundaries for patch edges that lie inside the character.
What you describe should work, but text rendering in games actually works much easier and faster by using Signed Distance Fields. You generate (once) a Signed Distance Field texture from given vector representation, and then use it to render the text. Nice video about it: th-cam.com/video/1b5hIMqz_wM/w-d-xo.html
Yep this would definitely work, and as Awesome GameDev wrote you can use signed distance fields to do this as well. I experimented with GPU accelerated font rendering using the actual techniques described in this video, and I had to create a pretty monstrous shader for the rendering haha. It was also pretty slow, but I would be interested to see if I could speed it up using the bounding box ideas that you listed :)
Haha let's hope so! My plans are to also add a serialization system for the animations and a GUI, then it should be much easier to add new animations :D
It would be nice to look at the rasterization of cubic bezier curves after that. The ones that are used in the .otf font format and in vector graphics in general. A completely new set of problems arises there. Such as looking for self-intersections, which cannot be done analytically because of the high order of polynomials. Anti-aliasing is another interesting issue worth discussing in relation to the whole topic of rasterization.
He also didn't mention that getting the bounding rectangle of each bezier curve is the first step. The more involved calculation is only needed once you know you are inside the bounding rectangle. Only in the case of complex curlicues and other thin spaghetti-looking shapes will bounding boxes greatly overlap, requiring a lot more calculations. I think the only square root you need is in finding maxima and minima of cubic beziers (because the derivatives are quadratic). Otherwise you just draw the binary rasterized curves (wire frames) in memory ahead of time and then dig them up for cases of points inside bounding rectangles. The problem is reduced to finding the best t-step to draw the binary outlines of the curves. If the t-step is too big your curve will have gaps. If it is too small you will waste time drawing certain pixels multiple times. You need a formula to calculate the best t-step given the 4 weighting points of your curve and the given pixel resolution.
Self-intersection doesn't seem like a problem for fonts as almost no font is going to use a looping bezier. If you have a deliberate loop in your glyph, you would always use two non-looping bezier curves to construct it. If you are allowing generalized shapes where the user can place weighting points anywhere they like, like in Adobe illustrator, then you do have to test for points possibly being inside the loop of a self-intersecting bezier. I think if you're doing graphics where speed is required you simply rule out loops ahead of time though. The loop is an ugly special case that only has to be dealt with when you can't rule it out ahead of time based on the location of the weighting points.
Font rasterization makes use of the quadratic formula, which in itself is not too difficult. The real difficulty is figuring out the specific version of the quadratic formula Microsoft used in their renderer.
Your explanation and visual representation of linear interpolation and Bezier curves is very similar to what I've posted on my channel! Almost scene-for-scene, haha. Well done though!
Thanks ScriptGuider! And I just checked out your video, that is funny haha. I drew inspiration from the wikipedia article on Bezier curves, and they basically had the same thing as well lol :)
I found a way to render a path made of lines, bezier curves of any degree, arc of ellipse or any shape you can imagine. For each computed pixel, i keep trace of the vertical sign of the derivate of the curve (which i compute by simply substracting a pixel position from it's previous). If it's an edge, or two curves crossing each other, i keep trace of both values. Now, from the upper pixel to the lower, then form the more left pixel to the more right, i draw the filler pixel if the sum of the sign is more than 0. I can avoid drawing on line if i want.
7:00 in: I got this ! What ? More math ? 😂 Still High School math suffices to get this. Good job. (When you started talking about pixels and filling, I had to stop myself from making an imagemagick joke hahah)
Why is it that fonts on my windows XP computer look very blocky (more so than other non-text elements) at high resolutions? Did they just not use rasterisation?
14:01 *mom walks in* finally she walks in when I can pose as doing my online math homework instead of the weird part of the TV show mom: "I thought you finished the quadradisc last year! Go do your weird TV show research already!"
Most need not remember the quadratic formula -- only (visually) that degree 2 single-variable functions bend toward and then away from the x-axis, and (algebraically) `x * y = 0` where x and y are expressions, means either x = 0, y = 0, or both
You can write documents in a terminal. You can build a website in a terminal. No guarantee that doing these things made someone encounter rasterized text :)
The mathematical notation actually extends to any arbitrarily sized vector. So if you just imagine that P consists of two components, , then you just use the same equation for x and y. Then you can extend it to 3 dimensions by using the same equation for z, etc. Let me know if that makes sense, it's kinda late and it's hard to type this on a phone haha
Are you sure that TTF uses 3-point Bézier curves? Usually 4-point Bézier curves are used in vector programs and most other applications. That will give you 2 control points which lets you create more complex shapes, and importantly it lets you determine the slope in the start and the end points of the curve separately. I haven’t been thought about this too much but I feel like it would be really bad or even impossible to create smooth shapes but combining several Bézier curves without being able to control the slope in the start and end points
Yea I'm like 90% sure haha. You can check out this section in Microsoft's overview of the TrueType specification docs.microsoft.com/en-us/typography/opentype/spec/ttch01#outlines . The second paragraph says "Curves are defined by a series of points that describe second order Bezier-spline", and when I wrote a simple ttf font parser I didn't encounter anything greater than a second order bezier curve. Those docs are really amazing too if you're interested in more of the technical details :)
Yes, if you make sure to transform all the coordinates so that the pixel you are testing is the origin, then all you need to do is check if the x-coordinate of the root is less than 0 and that means it is to the left of the pixel :)
14:45 why would it not intersect with our curve if it's greater than 1? Also at 14:17 the solutions should be shown as "t=" not "y=". Interesting video, thanks!
If it's greater than 1, then that implies that the value would intersect after the endpoint of the bezier curve. So, technically it would still intersect with the curve, it just wouldn't hit it between the end points And you're right about the y should be t, I didn't even notice I had that messed up until now haha! Thanks for mentioning it though :)
Not in practice because programmers will typically "cache" the letter to a texture. So they'll rasterize it once, then save the pixels, and then basically stamp the letter where they need it every time they need to use it :)
![[#2024MAMA] G-DRAGON - 무제(Untitled, 2014)+POWER+HOME SWEET HOME+뱅뱅뱅+FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/Ox29z5Nf1Uk/mqdefault.jpg)
A few notes on what most actual implementations do (from what I've been able to read), just in case anyone thought this was simple:
* Solving quadratics is (probably much) slower and harder than just subdividing until you're smaller than pixels then testing against the x coordinates of the points closest in y coordinates.
* Generally the letters (or, more generally, glyphs) are only rendered once per font size when needed and then that copy is stamped at all the places it's needed.
* It's common to use the fact that PC monitors layout their pixels in vertical RGB stripes to get more horizontal resolution.
* At small sizes, avoiding blurring as lines cross through pixels is more important than exactly representing the outline. The solution is pretty crazy: TTF fonts include programs that execute to adjust the coordinates based on size... and potentially other things like weight and surrounding characters!
* This doesn't work if you're animating, as you can see the outlines jumping around (and it's slow). In this and other situations, like very large text or 3d, signed distance fields (or SDF), which are basically fancier bitmaps that are quite good at approximating the outline but still very fast to render.
Hey Simon! Thanks for the great overview on some of the more technical details of font rendering :). I didn't know about the optimization you can use to avoid solving quadratics, and I'd be interested to try that out at some point. I also saw your comment about .bmp, and I do apologize for any inaccuracies there. I always forget to check some of the finer details when I make videos like this haha
I thought something seemed fishy when a square root was being calculated for every pixel per curve. A prerendered cache would definitely help, but I'm not surprised that there was another possibility.
@@GamesWithGabe I have a renderer called TD renderer. It is based on FreeType, however, it makes use of my own rasterizer.
@@angeldude101 actually square roots aren't nearly as much of a problem as they were 25 years ago. GPU's have special hardware to do square roots directly, and graphics developers typically do at least one (possibly multiple square roots) per pixel 60 times a second in games to calculate things like lighting. This article gives an interesting overview cuda-programming.blogspot.com/2013/01/performance-of-sqrt-in-cuda.html . But font rasterizers are still CPU-based (as far as I know), so it can still become a problem if you don't use some optimization techniques :)
@@angeldude101 It would probably be faster to just directly rasterize the entire outline first and store it in memory. Then checking for horizontal crossings is just referencing a binary lookup. The problem is then reduced to that of efficiently drawing the outline. I recall that even drawing simple straight lines involves some tricky optimization tricks, so the best optimization for rasterizing a cubic Bezier might not be super simple. Your t-step has to be adjusted based on the size of the curve relative to the raster resolution so that you neither 1.) leave holes in your curve nor 2.) redundantly draw the same pixel multiple times. Is there an easy formula to calculate the optimal t-step given a cubic Bezier curve's 4 points and a specified resolution? That's what would really help.
It's fun thinking about how I would go about the problem before looking up how it's actually done. I haven't really studied this stuff since the 90s when everything was much slower in terms of speed and everything had to be super optimized to be at all usable in real time.
You have a great style of explaining things and making them feel friendly. I especially loved the two blob characters 🥰 I hope you make many more maths videos!
Thanks @LookingGlassUniverse! I do plan on making more videos like this, they just take a lot of time haha. But I really appreciate the comment :D
I couldn't agree more! When you have over 100 likes and no dislikes you know that you're doing it exceptionally well!
@@GamesWithGabe 0
@@black_TM333 uwu
Those blob characters made me remember 3blue3brown
Might be worth mentioning that there is an alternative solution for fast, real-time rendering of glyphs pioneered and patented by NVIDIA, which is based on using the stencil buffer to determine coverage per pixel.
Basically, a pixel is subdivided into subpixels and a shader determines for each subpixel whether it is inside the glyph or not. This can be quickly determined if you are smart in how you create your geometry. Quadratic curves, for instance, can be evaluated by creating a triangle from points p0, p1 and p2 and using barycentric coordinates for the vertices. It then becomes trivial to determine whether the subpixel is inside or outside the curve.
The "winding" path is then drawn first, adding values to the stencil buffer. Next, the "non-winding" paths are drawn, subtracting the values in the stencil buffer. You end up with a stencil buffer containing ones and zeroes for every subpixel.
Finally, in the so-called coverage step, you calculate the coverage of each pixel by adding all subpixel values for that pixel; if 16 out of 16 subpixels are set to one, you have 100% coverage, but if only 8 pixels are set to one, you have 50% coverage and so on. The final color will be determined by using coverage as an alpha value, or by multiplying the red, green and blue colors by the coverage.
Substantial research has gone into finding ways to generate optimized stencil and coverage meshes to render, as well as coming up with ways to efficiently store these mesh representations on the GPU. It's sad that this process has been patented, but on the other hand it's free to use if you own an NVIDIA GPU. See: developer.nvidia.com/nv-path-rendering
Could you express that in pseudocode somehow? I know the basics of pixel manipulation (RGB as a byte each) but don't know much about actual graphics related stuff
Other than implementing it with hardware assist, I'm surprised that Nvidia got such a general patent on the technique.
These sampling methods were being done in the 1980s on devices that needed the resolution and had the memory,
like the Quantel Paintbox and Truevision graphics card applications.
2:14 just for comparison, I had a Commodore 64 back in the '80s.
it used 8x8 pixels for each character and only 1 bit per pixel.
so the WHOLE ASCII table of 256 characters took 256*8*8*1bits = 2KB
well it only had 64KB of memory anyway.
That's insane. I have a lot of respect for the programmers in the '80s and '90s era when memory was so limited. It's so easy to just use 100's of MB in a simple program now :)
@@GamesWithGabe thanks for this video. I learned a lot.
In the C64 the characters were in ROM. Although you could supply a RAM location for custom fonts.
I grew up programming in the '80s and '90s and when he went 'only 32 by 32 pixels' I was like ... BRO, ONLY?!
I have handcrafted many 6x6 pixel fonts just to get some decent amount of text on a screen given de crappy amount of pixels (256x192 or 320x200) on screen.
Fun fact: The standard 'high rez' VGA font is 9x14 pixels.
@@GamesWithGabe you may want to read about a memory saving trick called Bloom filter. it is still used in modern systems. imagine creating a speller using only a bit for each word. (well not exactly achievable, but it was "good enough")
I am seriously unable to comprehend why you have such a small following... Your content is amazing and super high effort! You should be in the millions!
Thanks Blu3! I put a bit more effort into this video than I normally do because I was submitting it to the 3Blue1Brown SoME haha. But I hope the channel will one day be in the millions :D
@@GamesWithGabe hey why don't make a 1 byte = to 1 bit? Why not use something different from english letters that take 1 letter = 8 bits?
This is great. Would love to see you go to the next step and talk about anti-aliasing etc.
Anti-aliasing is doing bilevel rendering at 4×4 times the size, then using a box filter
@@groszak1 That's one type of anti-aliasing, there are more. Plus, not everyone knows what that means.
Very interesting... the more I learn about font rendering/rasterization, the less I take it for granted :D
Haha yea, I think you and I both know what a pain font rendering can be. And I'm glad you liked the video Asher!
Distance field fonts are worth a mention as well because of their awesome utility, though getting into distance fields is itself a whole other topic
Absolutely! If I have some time in the future I would love to add a part 2 about distance fields :)
Also the amount of text effects you can add almost for free, I think almost every videogame uses them this days.
I just found a gem of a channel
What an amazing video - great graphics, really informative and easy to understand. Props!
Thanks Kosmik!
This video is absolutely fantastic, such a clear and simple explanation for a thoroughly interesting topic!
Just wow. I had to work with a small OLED display and hexfonts a while ago. Since then l have been wondering how more advanced responsive font systems work and this video was the perfect answer. Thank you for this bit of knowledge.
nice video, i kind of expected the part with the raster, like how it's turned into pixels, anti aliasing and stuff like that
I'm looking for an interesting topic for my maths homework right now, and your way of explaining this concept made it tremendously easy! Thank you so much for the video and your beginner-friendly explanations!
I think a video on anti-aliasing would be interesting as well. The idea behind anti-aliasing is that if the edges contrast too much with the background you get a jagged looking texture along the edges on a (low resolution) bitmap screen. So what you do is you fill in the background near the edges with shades that transition between the shades of the letter and the background so that shades transition between the letter and the background more gradually. This gives less jagged looking edges. Thank for this video.
Future 3Brown1Blue channel.
Keep going.
Wow, that's a lot more complicated than I thought! Great video!
This is a very simplified overview to get you started, it's very good! The real world of fonts and font engines is spicy. Two examples: Winding orders aren't actually used consistently to mark regions, so you should calculate the normal of the glyph instead to find out which direction it's facing first. Some font tools or glyph operations may flip your glyph for example (I.e. your font has data for b, but represents d as a mirror of b through an affine transform). As for rasterizing bezier curves, font engines will actually linearize first based on a variety of heuristics since the test math is faster. I maintain a fast open source font engine on the weekends and love this stuff
Thanks for the comment Joe! Also, thanks for the extra info. When I started diving into the world of fontrasterization I had no idea how deep this rabbit hole goes, and I'm still very interested in how internet browsers are able to handle so many different fonts seemingly effortlessly. Do you have a link to your code if it's open source? If so I would love to take a look at it :)
this deserves so much more attention.
This was very interesting. You did a great job. Hope to see more from you in future.
I'm not up on my quadratic equations, but overall I enjoyed the video. I was a little distracted at the beginning, though, due to some errors. Not big things, but big enough to make the problem of raster fonts seem overwhelming.
At 1:26 you introduce a 32 x 32 grid, but it's actually only 16 x16.
At 2:10 you present the formulas for determining the size of a raster file for uppercase and lowercase English letters in a monospaced typeface. 1 pixel is certainly 8 bits of data for grayscale, but fonts weren't grayscale--they were bitmaps; thus, 1 pixel was 1 bit. 1 letter in your font would have occupied 16 x 16 bits. The final equation should have been 26 x 2 x 16 x 16, or 13,312 bits--not 425,000 bits. This font would take up about 1,664 bytes or 1.625 KB (K-bytes), not 53 Kb (K-bits).
At 2:37 you bring in BMP files, but fonts weren't stored as BMPs. Also, Apple didn't invent TrueType to solve the problem. The problem was already being solved with Adobe Type 1 and Type 3 fonts, introduced in 1984, the same year as Macintosh. Apple made TrueType to avoid licensing fees for Type 1 fonts. Side-note: Too bad for consumers because TrueType fonts (quadratic B-spline) were inferior to Adobe Type 1 fonts (cubic B-spline). Anyway.
At 3:23 you present a 12 px font at 53 KB, referring to the previous 32 x 32 px grid that was actually 16 x 16. The 512 px font is presented as being 13.3 MB. But using bits, not grayscale pixels, the 512 px font would only be 1.664 MB.
Again, I really liked the description and animation of the Bézier splines--top notch work.
Oh, the Font Wars of the 90's. Fond memories. There was a huge battle between Apple's TrueType fonts (1991) and Adobe's proprietary PostScript Type 1 fonts (1984). There was much debate over the merits of both, such as Apple had special "hints" to display better at low resolution. Adobe responded with Adobe Type Manager which was the de facto standard for a while but was expensive. Then Apple licensed TrueType to Microsoft for WIndows 3.1. But Apple wouldn't license Apple Advanced Typography, so Microsoft joined with Adobe to create OpenType (1996).
I've always wondered why font rasterization was so difficult, and with a history like this I guess it should make sense why it's not that simple :). I read a bit about the Font Wars as I was researching for this video, but I'd be interested to look a bit deeper into the history at some point as well
I was a developer charged with implementing fonts in a paint package way back in the 80s. I remember that black and white Adobe Type 1 Font book well, reading it over and over and over. Our implementation was all in assembly on a TI34010 graphics accelerator. Even for back then, it ran really fast. Decode the font files, calculate the cardinal splines, experiment with fill methods, fix the corner cases, implement kerning, test, test, test. Glorious when all the steps start to work together. People these days don't realize how you had to build everything up from scratch back then, without off the shelf libraries you could just download with working examples.
the size of the channel isn't representative of the production quality of this video. subbed, really good video
2:14 "~ 53 Kb" -> 53 KB. Typically, bytes are indicated with an uppercase 'B', and bits are indicated with a lowercase 'b'.
Yea, I had another person point this out as well. I must have overlooked it when I was finalizing the editing :)
And the "kilo" multiplier is indicated with a lowercase "k", so "kB".
Also this calculation is a lot easier if you notice that 1 pixel is 1 byte, and that 32*32 = 1024 = the number of bytes in a kilobyte, so each letter is exactly 1 kilobyte, and therefore the english alphabet with upper and lower cases is exactly 52 kilobytes.
@@UltraLuigi2401 I know that basically everyone on this planet still uses this wrong, so you have to be aware of the fact that uninformed people (and operating systems) mean 1024 bytes when they say 1 kilobyte. Actually that's simply wrong though. The prefix "kilo" means 1000 just like "mega" means 1000000 and that is NOT different for bytes. 1 kilometer = 1000 meters and 1 kilobyte = 1000 bytes. To deal with the confusion, a standard has been published in 1998 (accepted and enforced by many organizations) which introduced binary prefixes. The correct one in this case would be "kibi". So 1 kibibyte = 1024 bytes. The abbreviation is KiB instead of kB.
Here's some more info if you care: en.wikipedia.org/wiki/Binary_prefix
@@flyingsquirrel3271 I'm already aware of the different binary prefixes, I just am also aware that the base 2 definition for the SI prefixes is acceptable in informal contexts (such as youtube comments), and so use them to avoid confusion for people who have never heard of the binary prefixes.
Wow nice video, really explained the concept well (except for the quadratic algebra stuff, but I don't think anyone can explain it well to me), and the visuals definitely helped me understand it.
I've been wondering how exactly fonts are represented, visualized and scaled for a long time. A few months ago I implemented Bezier curves for smoothing out path finding points in my game, so it was a nice surprise to find them here too! Thanks for a great video.
This channel is underrated, and my day is r..... *made
Looking forward to part 2!
Awesome! This is so cool and interested me the whole way!
Love this video. Always wondered how font was rendered
when your math knowledge from school is seen outside of school that's the coolest feeling
Jeez, I take for granted on how I can able to change zoom and increase text size on the fly nowadays. Thanks for these amazing insights.
Amazing video. Really well explained and perfectly animated. Must watch all videos you have. Congratulations for your work, I'm going to share this to friends :)
Fascinating stuff!
While what you have described will allow one to render an outline, this will not render characters or strings of characters of high quality. Consider rendering outlines on a fix grid a progressively smaller and larger sizes. Consider the letter uppercase H, at large sizes the two vertical strokes are of equal width and height, buts as the size gets smaller one of the strokes will render 1 or more pixels narrower that the other (This is known as the picket fence problem) looking at the horizontal stroke as the outline gets smaller the stroke will render wider or narrower than the vertical strokes, it will also be displaced upward or downward from it’s desired location. This is the vertical variation of the picket fence problem. Now let’s consider Capital M with regard to the vertical strokes it has the same problem as Capital H, but now it has anew problem the diagonal strokes don’t have the same widths as the size gets smaller, but because of pixelization there weight becomes heavier ( fatter relative the the vertical strokes) this applies to all diagonal strokes as is most pronounced at 45%. The same artifacts apply to curves Consider the Character O, as it drops in size the left right top and bottom will not be the same width in pixels similarly the curve will render fatter and fatter as it approaches North east, south east south west and north west. Now lets consider a collection of characters. The horizontals are varying in width and move up and down in Y the Verticals are varying in width and moving Left and right of their entended position. The most obvious artifact is the bottom of the characters don’t share a common base line the is called baseline wander. There are solutions to all of these problems that involve looking at the morphology of each character individually and looking at strings as agrégate characters with features like common base lines inter character spacing and string widths as features that need to be preserved when they are rendered. As an exercise for the reader consider the case of a lowercase i it is clear that the size of the staff and dot need to be the same, but the relative position of the dot, size of white space and staff need to be treated holistically. When one moves away from Latin Alphabets to ideogram base writing systems like Kanji, Hangul, Nihongo, Cursive positional representations like that found in Arabic… al of the Latin problems exist as well as numerous features that need to be preserved that are not as simple as the examples that I gave above. Then there is a basic implementations philosophy issue to you codify the rendering rules in each character “smart characters, dumb rendering” or Dumb characters, smart rendering” The former requires more work per character/ideogram the latter requires more understanding of the underlying morphology issues. I think true type is a good rendering system (Smart Characters, dumb rendering) Adobe type 1 rendering is the first to market and mass adoption format is an example for (Dumb Characters, Smart Rendering). Good presentation of rendering outlines to pixels, but not really representative of what it takes to render high quality type. I am one of the creators of Adobe’s type technology and also had a hand in the reaction of TrueType. More please.
Thanks for this extra insight! I was amazed at the complexity that goes into rendering a single character as I was researching for a project I worked on (which is one of the reasons I made this video). One of the parts that blew my mind was the TrueType font program table and learning that fonts can embed programs to adjust the pixel placement for letters. Not only that, but like you alluded to rendering strings of characters also requires complex layout algorithms and other font metrics like kerning information or ligature conversions. Font rendering is an insanely deep rabbit hole to fall into, and it's very cool to hear from somebody that got to work on the original technology :)
I am curious, do you know how much these algorithms for tweaking pixels at small/large font sizes still holds true? I was under the assumption that since almost all devices now have high-dpi or lots of pixels (not counting embedded devices), the pixel adjustments were less of a concern? But I honestly have no idea how browsers and other text heavy applications render text (whether it's just cached textures or real-time rendering or a mixture of both).
@@GamesWithGabe The tweaks are still needed. Higher pixel per inch monitors simply changes the magnitude of tweaks and the size at which artifacts start to dominate the rendering. The mathematics of the font descriptions is mostly a thing of beauty. Regarding string widths managing the inter character spacing and propagating the fractional errors that quantizing to a fixed pixel grid demands is one aspect of the problem. Serifs, descenders like g, y… add another dimension to the problem. Preserving white space within characters like a, 6, 9 all are madding I think of it as a foreground background problem where neither are allowed primacy. The first rookie mistake is quantizing the fonts. The earliest Macintoshes fonts had integer font widths and integer Inter-character spacing quantized at 144 to the inch. A direct artifact of the 144 dpi ImageWriters that shipped with the earliest machines. Not only did our team design the software architecture for the Laserwriter we invested precious resources in rewriting the rendering engines that were used within QuickDraw. Steve Jobs really got his moneys worth out of teaming up with Adobe to save the failing Macintosh launch. To build real WYSIWYG systems the rendering intent is only quantized when it is on the device on which it will be rendered.. Once you have something to display or print the rendering intent has to be bound to the limits of the physical devices not the other way around. This is why a Macintosh could generate camera ready copy off an image setter with 2470 dpi resolution or a 72 dpi display or a 300 dpi laser printer and the only thing that change is the output conformed more closely to the rendering intent. In the realm of maintaining caches at high resolutions and large point sizes we found that compression algorithms that worked at laser printer resolutions were horrible at even modest point sizes and had to create a unique algorithm the usual line by line xor encoding to bias the data towards long runs for run length coding performed poorly but we observed that to we were able to take advantage of the morphology of the characters and create a predictor that encoded characters that ran diagonally through the bitmap space with there own encoding and the compression ratios became much more tractable. There was talk up thread about anti aliasing real anti aliasing is dealt with by rendering the page in reverse paint order. The aliasing that comes with the trade offs of Color pixels being stacked side by side, top to bottom and several other less than ideal device dependent topologies is better dealt with by overlaying a field lens that brings all of the illuminants together geometrically . for my sins I dealt with all of the hardware vendors that came through our doors. Our brain and visual system is very forgiving of some things and really fussy about others. I knew it was going to be a bad day when I had to explain to yet another vendor why we couldn’t fix their broke assed hardware in software. It has been a long time since I thought about this stuff. Best
Nicely explained. Sadly, I really wanted to see subpixel rendering techniques and hardware acceleration mechanisms, like single-instrucion-multiple-data.
Incredible, earned a sub
Adobe Type 1 vector fonts are from 1984, and the concept of vector fonts is older than that. The biggest difference between Type 1 vs. TrueType fonts is that the former used cubic Bézier curves, while the latter switched to quadratic Bézier curves (I think to work around Adobe’s patents?).
Adobe fonts were never vector fonts They were scalable outline fonts. There were no Patents. Later Products like Super ATM were Patented, but the font technology inside Postscript was not patented and the Type format and PostScript language were documented in books published by Addison Wesley. Super ATM allowed you to morph Fonts along a variety of axes Blending weights, Set widths, different typefaces together were just some of the dozens of ways that typefaces could be transformed. The best example I remember is taking text in two different languages and modifying the set width’s and character shapes so that the text matched up line for line. Apple and MicroSoft got it into their heads that they would be better off if they created their own implementation of PostScript. It was my responsibility to find a way to win Apple back as a customer. It was not an easy task, thanks to some of the more moderate business development folks at Apple we managed to resolve our differences and build a lot more great product together. Apple and Microsoft spent 100s of millions of dollars and ultimately abandoned the project. True type AKA type 42 fonts was meant to be a faster rendering implementation, in the end it was the same only different. The two type formats and underlying technology were merged together into Cleartype. Within 6 months of Apple and MicroSoft tell Adobe that they were going to put us out of business, Adobe Type Manager was released for the Mac and Windows “ATM” brought type one scaleable font technology to the desktop along with a Library of thousands of Fully Licensed type faces. ATM was installed on ~80% of Macs Apple grudging allowed as it probably wasn’t good for business if they broke all of their customers machines.
@@rustybucket2248 What is the difference between a "vector font" and a "scalable outline font"? To me those two terms are synonyms. When I say "vector font" what I mean is: “the outline is specified as a mathematical curve; the font is not a pixel-based raster image”. I didn’t mean to imply anything about the relationships between sub-categories of outline-based fonts.
Hey, this video is incredible! Please, keep up your work!
Possible way to optimise it: Use the points defining a character to make a bounding box, then divide the area to be rendered into small patches with pointers to the characters whose bounding boxes lie within each patch. The rendering shader then only needs concern itself with testing its fragment coordinate against the characters within a given patch. Putting the relevant data into a format a fragment shader can work with might be a bit complicated, though.
Going below the level of a character seems like it might be possible, but I have no idea how you would go about it, given it seems like it would require splitting the lines and curves and adding new boundaries for patch edges that lie inside the character.
What you describe should work, but text rendering in games actually works much easier and faster by using Signed Distance Fields.
You generate (once) a Signed Distance Field texture from given vector representation,
and then use it to render the text.
Nice video about it: th-cam.com/video/1b5hIMqz_wM/w-d-xo.html
Yep this would definitely work, and as Awesome GameDev wrote you can use signed distance fields to do this as well. I experimented with GPU accelerated font rendering using the actual techniques described in this video, and I had to create a pretty monstrous shader for the rendering haha. It was also pretty slow, but I would be interested to see if I could speed it up using the bounding box ideas that you listed :)
makes a video about font rasterisation and casually explains bezier lines better than any other tutorial I could find
I would have liked to (after doing the bezier curve stuff) explain the actual algorithm behind rasterization which is the DDA but nice work anyway!
Nice work! I bet animating'll be easier with all the refactoring you've done.
Haha let's hope so! My plans are to also add a serialization system for the animations and a GUI, then it should be much easier to add new animations :D
finally learnt how Bezier curve work after years.
Amazing Video😃
Thanks @BlenderForever :)
It would be nice to look at the rasterization of cubic bezier curves after that.
The ones that are used in the .otf font format and in vector graphics in general.
A completely new set of problems arises there. Such as looking for self-intersections, which cannot be done analytically because of the high order of polynomials.
Anti-aliasing is another interesting issue worth discussing in relation to the whole topic of rasterization.
He also didn't mention that getting the bounding rectangle of each bezier curve is the first step. The more involved calculation is only needed once you know you are inside the bounding rectangle. Only in the case of complex curlicues and other thin spaghetti-looking shapes will bounding boxes greatly overlap, requiring a lot more calculations. I think the only square root you need is in finding maxima and minima of cubic beziers (because the derivatives are quadratic). Otherwise you just draw the binary rasterized curves (wire frames) in memory ahead of time and then dig them up for cases of points inside bounding rectangles.
The problem is reduced to finding the best t-step to draw the binary outlines of the curves. If the t-step is too big your curve will have gaps. If it is too small you will waste time drawing certain pixels multiple times. You need a formula to calculate the best t-step given the 4 weighting points of your curve and the given pixel resolution.
Self-intersection doesn't seem like a problem for fonts as almost no font is going to use a looping bezier. If you have a deliberate loop in your glyph, you would always use two non-looping bezier curves to construct it. If you are allowing generalized shapes where the user can place weighting points anywhere they like, like in Adobe illustrator, then you do have to test for points possibly being inside the loop of a self-intersecting bezier. I think if you're doing graphics where speed is required you simply rule out loops ahead of time though. The loop is an ugly special case that only has to be dealt with when you can't rule it out ahead of time based on the location of the weighting points.
overwhelmed !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! the only thing i could say........
Thanks for this! I was actually making a font renderer!
stellar vid mate
10:26
My Mans really just said P I N U S 💀
Thanks, this video made my day
Do computers have to calculate the root in the quadratic equation for every pixel, every frame? Isn't that really expensive computation?
Font rasterization makes use of the quadratic formula, which in itself is not too difficult. The real difficulty is figuring out the specific version of the quadratic formula Microsoft used in their renderer.
Would it be reasonable to rasterize the outline of the curve and then floodfill the rest to avoid having to test each pixel?
Depends on the flood fill method, but filling large areas can end up reading memory way more often.
this was super interesting, thanks!
3b1b sent me
Oh nice! I hope you enjoyed the video :)
@@GamesWithGabe Yes I did very much. Thank you.
Ditto, from his playlist which I'm working through.
Makes you appreciate the amount of processing being done behind the scenes...
Same! Also, this is the first video that let me truly understand bezier curves :)
great video ! thanks
I'll take code over math notation any day.
Your explanation and visual representation of linear interpolation and Bezier curves is very similar to what I've posted on my channel! Almost scene-for-scene, haha. Well done though!
Thanks ScriptGuider! And I just checked out your video, that is funny haha. I drew inspiration from the wikipedia article on Bezier curves, and they basically had the same thing as well lol :)
12:09 The formula can be simplified nicely:
P(t) = (1-t)²P0 + 2t(1-t)P1 + t²P2
Great video
I found a way to render a path made of lines, bezier curves of any degree, arc of ellipse or any shape you can imagine.
For each computed pixel, i keep trace of the vertical sign of the derivate of the curve (which i compute by simply substracting a pixel position from it's previous). If it's an edge, or two curves crossing each other, i keep trace of both values.
Now, from the upper pixel to the lower, then form the more left pixel to the more right, i draw the filler pixel if the sum of the sign is more than 0. I can avoid drawing on line if i want.
Amazing 🤩
Great video man
really good vid.
10:26 “pinus” - I guess I should’ve paid more attention in my maths courses, never heard of that arithmetic operator before 🤣
Hnnng, now I wanna see if I can go this on my graphing calculator
This video is fire
7:00 in:
I got this !
What ? More math ? 😂
Still High School math suffices to get this.
Good job.
(When you started talking about pixels and filling, I had to stop myself from making an imagemagick joke hahah)
What an amazing video.
Wonderful!
Can you please explain what is Q(t)? because I want to know what the function Q(t) for generating Bezier Curves is if you know it/them.
great great great !!!
Doesn't it also work, for example, if a pixel's X position is equal to the Y position (x = y), place the pixel there (rotated line)?
Why is it that fonts on my windows XP computer look very blocky (more so than other non-text elements) at high resolutions? Did they just not use rasterisation?
14:01 *mom walks in*
finally she walks in when I can pose as doing my online math homework instead of the weird part of the TV show
mom: "I thought you finished the quadradisc last year! Go do your weird TV show research already!"
Most need not remember the quadratic formula -- only (visually) that degree 2 single-variable functions bend toward and then away from the x-axis, and (algebraically) `x * y = 0` where x and y are expressions, means either x = 0, y = 0, or both
You can write documents in a terminal.
You can build a website in a terminal.
No guarantee that doing these things made someone encounter rasterized text :)
One thing I don’t understand is how does the Bézier curve work on points (2 numbers), do you just apply the operations to vector2 elements?
The mathematical notation actually extends to any arbitrarily sized vector. So if you just imagine that P consists of two components, , then you just use the same equation for x and y. Then you can extend it to 3 dimensions by using the same equation for z, etc. Let me know if that makes sense, it's kinda late and it's hard to type this on a phone haha
Are you sure that TTF uses 3-point Bézier curves? Usually 4-point Bézier curves are used in vector programs and most other applications. That will give you 2 control points which lets you create more complex shapes, and importantly it lets you determine the slope in the start and the end points of the curve separately.
I haven’t been thought about this too much but I feel like it would be really bad or even impossible to create smooth shapes but combining several Bézier curves without being able to control the slope in the start and end points
Yea I'm like 90% sure haha. You can check out this section in Microsoft's overview of the TrueType specification docs.microsoft.com/en-us/typography/opentype/spec/ttch01#outlines . The second paragraph says "Curves are defined by a series of points that describe second order Bezier-spline", and when I wrote a simple ttf font parser I didn't encounter anything greater than a second order bezier curve. Those docs are really amazing too if you're interested in more of the technical details :)
15:33 well, thats why i originally came for :D
That's helpful thanks.
Your P's drove my subwoofer through the floor. :P
amazing
15:10 but don't you have to check that the crossings are to the right of the tested pixel?
Yes, if you make sure to transform all the coordinates so that the pixel you are testing is the origin, then all you need to do is check if the x-coordinate of the root is less than 0 and that means it is to the left of the pixel :)
awesome
Thanks @Anilcan!
Very interesting
10:24 so many P's in that equation so it even infected the "minus" and became "pinus"
Nice video. Just gotta watch out for those French names.
Thanks! And yea, French names are not my forte :)
"blargonay"
Not what I thought!
SVG's are calculated with purely math, that is why there file size is so small but they can be scaled to any size on a screen.
so fonts are just SVGs?
I'm sorry to leave a comment like that on a video with relatively few other comments, but: 10:25 lmao "pinus"
Here just for that
14:45 why would it not intersect with our curve if it's greater than 1? Also at 14:17 the solutions should be shown as "t=" not "y=". Interesting video, thanks!
If it's greater than 1, then that implies that the value would intersect after the endpoint of the bezier curve. So, technically it would still intersect with the curve, it just wouldn't hit it between the end points
And you're right about the y should be t, I didn't even notice I had that messed up until now haha! Thanks for mentioning it though :)
14:15 It should be noted that you shouldn't use that formula for the case where the two terms in numerator have opposite signs.
At 1:40 you wrote 32x32 pixels but the grid is actually 16x16
I always thought the F in TTF stood for "font", was I mistaken?
You are right. He skipped the word Font and then it was just pure coincidence that the next word he said (file) also started with an F
i cant pass a test yet i find this really interesting
A so good video
The really interesting stuff is so-called "font hinting". There's a Wikipedia article about it.
8:12 does that mean that rendering 1 billion 'B' letters is more costly than 1 billion 'I" letters in the ttf format?
Not in practice because programmers will typically "cache" the letter to a texture. So they'll rasterize it once, then save the pixels, and then basically stamp the letter where they need it every time they need to use it :)
@@GamesWithGabe well then, next video should be "The Code Behind Font Rasterization | How it Works" ay?