hello everyone and welcome to another episode of coding Adventures today I'd like to try and render some text since it's one of those things that I always just take for granted to begin with we're going to need a font and I've just grabbed the first one I found on my hard drive which happens to be jet brains mono bold so let me open that up in a text editor just to see what's inside and not unexpectedly the raw contents is highly unilluminating so we're going to need to find some kind of guide for decoding it this is a ttf or true type font file which is a format I'm told developed by Apple in the late 1980s and so I had a look on their developer website and located this reference manual hopefully it's nice and simple to [Music] understand okay I've been skimming through it a little and I'm becoming increasingly baffled and bewildered by all the mysterious diagrams the long lists of Arcane bite code instructions not to mention the strange terminology such as Freedom vectors ploop values and Twilight zones what is the Twilight Zone it is the middle ground between light and Shadow you're not helping anyway after slowing down a bit and reading more carefully I realize that most of this complexity is focused on a single problem which is making sure the text is displayed or printed clearly at low resolutions where unlucky scaling could cause one part of a letter to appear twice as thick as another for example sample making the letters difficult to read so I don't think it's actually something we need to worry about for our little experiment today at least which is definitely a relief let's move on then to the next section of the manual which gives us this list of mandatory tables that all fants need to include and I'm most excited about this glyph table since that sounds like where the shapes are stored so our first goal is simply to locate that table and this looks promising the font directory is a guide to the contents of the font file music to my ears so this is the very first block of data we'll encounter in the file and I don't think we really care about any of it except for the number of tables so we're going to want to skip over one 32-bit integer and then read in this 16bit integer and just some quick cop code for doing exactly that I'm printing out the number of tables here by the way just to make sure it's a plausible value which from the tables listed in the manual I'm thinking would be somewhere between the mandatory 9 and around 50 at a maximum maybe so let's run this quickly and we can see the number of tables is 4,352 how am I doing something wrong already okay I finally found the answer on this OS Dev Wiki entry which is that the file format is Big Indian which just means that the individual bytes of each value are stored back to front from what my little Indian computer is expecting so I've quickly made this simple font reader class which lets us read in a 16bit value and have this conversion to little endian happen behind the scenes so we don't need to worry about it every time all right so using that let's try running the program again and now the number of tables comes out as 17 which is much more believable that means we can proceed to the table directory and what this gives us is a four-letter identifying tag for each table and we've briefly seen what those look like already and along with that there's also the table's location in the file in the form of a bite offset so in the code I've just added this little Loop over the total number of tables and in there it's simply reading in the metadata for each of them of course I've also had to expand our reader class in the process with these two new functions for actually reading a tag and a 32-bit integer so hopefully this is good work let's try running it and these tags look a little strange for example we seem to have a tiny head over here with a big question mark next to it which does incidentally sum up how I'm feeling right now oh I just realized that I forgot to skip over all that other stuff in the first table that we didn't really care about so let me just do that quickly I think it was three 16bit values so that's six bytes we want to hop over here all right and now we've got the tables I've spotted the glyph table entry over here which is pointing us to bite location 35,43 so that's where we're headed next let's take a quick look at the manual first though and it looks like the first bit of information will be given is the number of Contours that make up the first glyph in the table interestingly that value can be negative which would indicate that this is a compound glyph made up of other glyphs but let's worry about that later we then have a bunch of 16bit fword which tell us the B in box of the glyph and following that comes the actual data such as these X and Y coordinates here I'm eager to get my hands on those although we should take note that these coordinates are relative to the previous coordinate so they're more like offsets I guess we could say and they can also be in either an 8bit or 16bit format which I assume these flags here are hopefully going to tell us then there's also an array of instructions which I believe is the scary bite code stuff we're skipping over and ually or I guess firstly I'm not sure why I read this table backwards we have indices for the end points of each Contour so if I'm understanding this correctly we're going to read in a bunch of offsets from which we can construct the actual points and then say we get two contour and indices such as 3 and six for example that just means that the first Contour connects points 0 1 2 3 and back to zero while the second Contour connects points 4 5 6 and back to four that seems easy enough so the other thing to look at is that 8bit flag value although only six of the bits are actually used it seems so we're going to have one of these flag values for each point and according to the manual bits one and two tell us whether the offsets for that point are stored in an unsigned one by format or a signed 2 by format then getting just slightly convoluted here bits four and five have two different meanings depending on whether the one bite or two bite representation is being used in the first case it tells us whether that bite should be considered positive or negative and in the second case that's not necessary since the sign is included in the offset itself and so it instead tells us whether or not we should skip the offset that way if the offset is zero it doesn't have to actually be stored in the file so we can see there's some basic compression Happening Here on that note let's take a look at bit three if this is on it tells us to read the next bite in the file to find out how many times this flag should be repeated so that it doesn't have to waste space storing repeated copies of the same flag finally Bit Zero tells us whether a point is on the curve or off the curve and I'm not entirely certain what that means right now but we can worry about it later let's first just get these points loaded in by the way to actually test if a particular bit in the flag is on or off I'm using this tiny function here which simply shifts all the bits over so that the bit we're interested in is in the first spot then masks it out meaning all the other bits get set to zero and finally checks if the resulting value is equal to one all right and then here's a function I've been working on for actually loading one of these simple glyphs and this does exactly what we just talked about it reads in the Contour end indices then reads in all of the flag values of course checking each of them to see if they should be repeated some number of times and reading in the X and Y coordinates before simply returning all of that data and for reading in the coordinates I have another function here where each coordinate starts out with the value of the previous coordinate and then we grab the flag for this point and depending on that we either read in a single bite for the offset and add or subtract it based on what the flag tells us to do or we read in a 16bit offset but only if the flag isn't telling us to skip this one all right I'm excited to see what comes out of this so back over here I've just made a dictionary for mapping table tags to locations which we can use to set the reader's position to the start of the glyph table and then simply read in the first glyph and print out its data so let's see what that looks like quickly okay that seems promising but we won't really know if it's nonsense or not until we draw it so in the unity engine I've just quickly plotted these points and I don't know what this is supposed to supposed to be but I'm sure it will become clear once we draw in the Contours okay it's looking a little disheveled but I do believe it's the missing character glyph and I actually remember now reading that it's required to be at the very start of the glyph table so that makes sense I just need to iron out some bugs clearly so I've been fiddling with the code a bit and here's how it's working now we simply Loop over all the end indices and then create this little window into the array which which allows us to access only the points in the current Contour since evidently I can't be trusted and then we draw lines between those looping back to the first point in the Contour to close the Contour at the end all right let's try it out and that's looking much better one glyph is not enough though I want all the glyphs and to get them we just hop over to the max P table where we can look up the total number of glyphs in the front and then we head over to the Head table leaping over several entries we don't care about right now to find out whether the locations of the glyphs are stored in a 2 by or 4 byte format and finally we can dive into the loc table from which we can extract the locations of all of the glyphs in the glyph table and then we can just read them in I must admit even though pausing a font file must be pretty low on the list of thrilling things one could do with one's day I'm quite excited to see all these letters appearing here anyway let's zoom in on one of these clips such as the Big B for instance and we can see that while the glyphs obviously very beautiful they are perhaps a bit blocky so I believe our next step should be to bezier these bad boys I've babbled about beziers a bunch before on this channel but briefly if we have two points and want to draw a curve between them we need at least one extra control point to control how the curve should curve now to visualize this curve let's imagine a point starting out at the start point and moving at a constant speed towards this intermediate control point from which a second Point moves simultaneously towards the end point in the same amount of time that it takes the first point to complete its Journey like this that's not terribly interesting but like many things in life it can be made more exciting with the addition of lasers so let's draw a laser beam between our two moving points and that's a bit better already but for some added flare let's then also leave a ghost Trail of the old beams behind and now we're really getting somewhere so the curve that these beams Trace out is our bezier curve and all we need now is a way to describe this curve mathematically which is surprisingly easy to do we just need to imagine one last traveling point this one moving between the first two Travelers and also completing its journey in the same amount of time observing the path of this third point we can see how it travels perfectly along our curve so here's a little function to help calculate the positions of these points it takes in both the start position and the destination as well as a sort of Time Value which can be anywhere between 0 and one as a measure of the progress of the journey the point's position at the given time is then calculated as the start point plus the offset that takes us from the start to the end point multiplied by the time value then from this linear interpolation we can build our bezier interpolation which just calculates these Intermediate A and B points like we saw and then interpolates between those to get the actual point along the curve at the current time so if we want to draw one of these curves one way to do it would be like this simply chopping the curve up into a bunch of discrete points based on this resolution value and then drawing straight lines between them so just testing this out quickly we can see that with a resolution of one we of course just have a straight line two gives us the faintest idea of a curve and from there it quickly starts to look pretty smooth anyway let's go back to our blocky B now that we have bezier working and I'll just quickly jump into the Cod here and modify it so that every set of three points in the Contour now gets drawn as a curve and let's take a moment to to admire how that looks wait what this is not quite what I had in mind but it looks kind of interesting so let's try writing some text with it and we can come back and fix it in a minute so I've created a string here that says hello world and we simply go through each character in that string and of course to the computer each of these characters is just a number defined by the unic code standard and I'm using that number as an index into the array of glyphs that we've loaded in we then draw each of these and add some hardcoded spacing between them because I still need to figure out where they've hidden the actual spacing information all right let's take a look at the result the letter spacing is too small so I'll just increase that quickly but unfortunately the text is still not particularly comprehensible clearly the glyphs in the font are not in the same order as Unicode which makes total sense actually since different fonts support different subsets of characters so there's never going to be a onetoone mapping instead the font file needs to include a character map to tell us which GPH indices map to which Unicode values this part seems like a bit of a pain because there are nine different formats in which this mapping information can be stored although I then read to my great relief that many of these are either obsolete or were designed to meet anticipated needs which never materialized and reading a little further it seems that 4 and 12 are the most important important ones to cover so I'm going to get cracking on those okay here's the code I've written to handle those formats and I'm not going to boy you with the details as we talked about all it's doing is looking up in a slightly convoluted way the Unicode value that corresponds to each glyph index with that mapping information we can now finally retrieve the correct glyphs to display our little hello world message I really like how stylish some of these buggy beziers look perhaps this is the fun of the future oh and by the way if you'd like to learn more about the beauty of bezier cures I highly recommend a video called the beauty of bezier cures and it's equal to the continuity of splines right now though let's see if we can fix this mistake that I've made so first of all we can see that here where there's supposed to be a straight line this point is actually just controlling how the curve bends as it moves towards this next Point here so it looks like the glyphs aren't made entirely out of beziers as I was kind of assuming but rather have some ordinary line segments mixed in also taking another look at the manual it shows this example where we have a spline made up of two consecutive bezier curves and what it's pointing out is that this shared point between the two curves is exactly at the midpoint between these two control points this is typically where you'd want it to be simply because if it's not at the midpoint we can see that we no longer get a nice smooth joint between the two curves meaning this Spain becomes discontinuous and so what the manual recommends doing for these points that lie right in the middle is to save space by simply deleting them as it puts it the existence of that Middle Point is implied so we're going to need to infer these implied points when we load the font and I believe that that's where this on curve flag that we saw earlier is going to come in handy so in this example points one and two would be flagged as off the Curve whereas points 0 and three would be on the curve what we can do then is say that if we find two consecutive off curve points we'll insert a new uncurve point in between them also just to turn everything into Bas for consistency sake let's also say that if we find a straight line segment which would be two consecutive uncurve points then we'll also insert an extra point in between them all right so I've just been writing code to handle that quickly which as we just talked about simply checks if we have two consecutive on or off curve points and if so it inserts a new point in the middle here's a quick test to see if that's working as expected so these are the on and off curve points that actually stored within the font file for our letter b and then here are the implied on curve points that we've now inserted into the Contours as well as these extra points between the straight line segments to turn them into valid bezier curves with that our code for drawing these curves finally works as expected and just for fun I made it so that we can grab these points and move them around to edit the glyphs if we want anyway let's put this to the test quickly by drawing all the letters of the English alphabet and these all seem to have come out correctly so let's then also try the lowercase letters and these are looking good too except I noticed that we're missing the I and the J I guess they must be compound Cliffs since we haven't handled those yet and I think the idea is just that the dot would be stored as a separate glyph and then the I and the J would both reference that instead of each having to store their own copy of it so I've just spent some time implementing compound glyphs over here and since these are made up of multiple component glyphs essentially all we need to do is keep reading in each component glyph until we receive word that we've reached the last one and all the point and Contour end indices from those are simply squished together into a single glyph which is returned at the end here then here's the function for actually reading in a component glyph and this essentially just gives us the index to go and look up the data of a simple glyph although I'm wondering now if a compound glyph can contain other compound glyphs I'll need to tweak this later if that's the case but anyway the simple glyph we've just read in can then be moved around scaled or even rotated if I had implemented that yet that is to oriented correctly relative to the other components and we can see that transformation being applied to the points over here so with that bit of code we can at Last Read in our missing inj and this has also unlocked a whole world of diacritics since of course these all make use of compound glyphs as well to save having loads of duplicate data okay we're making good progress I think so I'd like to start trying out some different fonts just to to see if they're working properly let's write a little test sentence here such as the classic one about the fox and the lazy dog or this one I came across concerning discotex and jukeboxes These are nice test sentences because of course they contain all the letters of the alphabet which I learned today is called a pangram anyway this is jet brains monel that we've been using and I'm going to try switching now to maybe open sense all right there's an issue with the size of the glit clearly but I found this helpful scaling factor in the head table which should take care of that and that's looking much better but obviously the spacing is a little off the problem is that this isn't a monospaced font like the one we had before so our hardcoded spacing value is no longer good to cut at after some rooting around though I uneed this horizontal metric table which tells us how much space we need to leave after each glyph which is known as the glyphs Advance width so here's some code for just reading in that information and if we use those values our text obviously looks a lot more sensible okay I've just spent a little while refactoring and cleaning up the project because things were getting slightly out of hand let's quickly make sure that I haven't messed anything up in the process and of course I have all right I've tracked on the issue so we're back on track and now that we're able to write some words and display the outlines let's finally figure out how to properly render the text I guess the simplest solution would be to just increase the thickness of the lines until they turn into a solid shape all right thanks for watching well wait a minute this is perhaps not the most legible approach so we should maybe take some time to explore our options for example some years ago I wrote this little polygon triangulation script using an algorithm called ear clipping and one idea might be to Simply feed the points that we're currently using to draw the outlines into that and get out a mesh for the computer to draw this doesn't seem ideal though because if we want the letters to be nice and smooth we'll have to have lots of little triangles on the screen which the computer might not particularly appreciate so a much smarter mesh-based approach is presented in this paper on resolution independent curve rendering basically we triangulate a mesh of just the sort of straight line inner part of the glyph and then render a single extra triangle for each of the curvy bits so to be clear for each bezier curve on the Contour a triangle is simply being drawn like this the trick now is to find some way to display only the section of the triangle that is inside of the curve so that we can get a smooth result without having to add loads more triangles to do this we're going to need to think about what the shape of our beur actually is and just eyeballing it you might think it looks kind of parabolic but let's have a look at our equation to be sure currently we have this defined as three separate linear interpolations which paints a nice geometric picture but it's a little clunky mathematically so I've quickly just written out these interpolations as one giant equation and then simplified it a bit to arrive at this which we can of course recognize as a quadratic equation it's just this coefficient a * T ^2 plus the coefficient B * t plus a constant C for that reason this particular type of Bia curve we're working with is called a quadratic buia curve which confirms our parabolic suspicions and we can maybe see this even better if we allow the lines to extend out past this 0 to1 time interval now it is a little bit fancier than your standard Parabola though in that we can actually rotate it around and that's just because our equation of course is outputting two dimensional points rather than a single value we could break it down if we wanted into separate equations for the X and Y components and if we were to graph those they would just be regular old non-rotated parabas like this so nothing mysterious here if we move a point on the x-axis we can see how that's reflected in the X graph and if we move a point on the y-axis we can see how that's reflected in the Y graph all right so I reckon we're ready now to think about this problem of how to fill in the region inside of the curve that's kind of confusing when the curve is all rotated like this though so let's just position the point so that it looks like a perfectly normal y = x^2 Parabola one way to do this is to put P1 at coordinates half comma 0 p 0 at coordinates 0 comma 0 and P2 at coordinates 1 comma 1 and that indeed has given us this nice simplified case where the Y values of the Curve are equal to the square of the X values so if we want to fill in this region inside the curve that's very easy in this case because if the points on the curve are where Y is equal to x^2 then obviously inside is just where Y is greater than x squ to actually draw this region though we'll need a mesh and a Shader for the mesh we can simply construct a triangle like we saw earlier out of the three beia points and I'll give those points texture coordinates corresponding to the positions that we put the points in to get that simple y = x^2 Parabola then in a Shader we can get the interpolated X and Y texture coordinates for the current pixel and let's visualize the x value for now as red which looks like this and here's the Y value as green then here's them both together I actually find it a bit easier to see what's going on if we chop the values up into discrete bands by multiplying by 10 for example then taking the integer part of that and then dividing by 10 and now we can see our X and Y values as a little gridge here instead of a continuous gradient of course we can move our points around and we can see how this grid gets transformed along with them since again the Shader automatically interpolates the texture coordinates to give us the value for the current pixel in texture space though things always just look like this since these are the texture coordinates that we defined so back in the Shader Let's test for y being greater than x^2 and draw the results of that into the blue channel here as hoped that now fills in the curve and what's more of course it will also be transformed along as we move our points around so we only really had to think about the simplest possible case and by taking advantage of the way that shaders work we get the rest for free I thought that was a cool idea so with that we can now go back to our mesh of just the straight lines of the glyph then add in those triangles for all the curves and then use this clever little idea to shade in just the parts inside the curve hang on that's not quite right though it looks like along the outside edge of the glyph where the points go in a clockwise order everything is correct but along the inside here where the points are now going counterclockwise we actually want to fill in the opposite region of the curve so in the Shader I've just quickly added this little parameter which will tell us the direction of the triangle and we can flip the fill flag based on that then just testing that here we can see that when the points are clockwise we have the inside of the curve being filled and when counterclockwise the outside is now filled and that seems to have fixed our problem here so this is a pretty interesting way to render text I think but one potential problem with the approach is that Microsoft has a patent on the research skimming through it it does seem though that it only covers the more complicated case of cubic Basia curves which is when the curves are defined by four points instead of the three that we're working with so quite possibly it is actually okay to use but I'm anyway curious to experiment with different ideas today so let's put this one to the side for now what if we instead simply took our old glyph meeses made out of ridiculous numbers of triangles but say that we don't actually care about the triangle count because instead of rendering them to the screen we pre-render all of them to a texture file that way we ultimately only need to render a single quad for each letter and use a Shader that just crops out the appropriate part of that texture Atlas to display the letter we want this would be nice and fast but it does of course have some issues with scaling we'd need to make our Atlas truly gigantic if we want to be able to display large text for example or alternatively we could try using signed distance fields in one of my old videos we took this map of the Earth and wrote a little function to calculate the distance of every pixel to the Shoreline which could then be used for making a simple wave effect so we could use that same coat here to turn our image of glyphs into an image of glyph distances a simple Shader could then sample the distance and output a color if that distance is within some threshold we looks like [Music] this this scale is better than before because now the Shader is blending between distances rather than hard on off values the outlines are a little lumpy but I'm sure we could improve that with some refinements to the technique these texture-based approaches are slightly annoying though in the sense that it's not really practical to support all the characters in a font because then the texture would be too large so we always have to compromise on some sub subset in order to get good quality and even still the edges tend to have some obvious imperfections at least if you're resuming unreasonably close to the text and we tend to lose our nice crisp Corners with that said I have seen some interesting looking research about using multiple color channels to store additional information that can help to increase the quality quite a bit so I would like to experiment with this at some point because it's definitely an interesting technique but for today prefer to render the text directly from the beia data without any textures compromising the quality in between so focusing on a single letter for a moment let's imagine a grid of pixels behind it and our goal is obviously to light up the pixels that are inside of the L therefore we need a way to detect whether a point is inside or not and happily there's a very intuitive way to do this so we're interested in this point over here all we need to do is pick any direction and imagine a ray going out until it hits one of the Contours of the shape when it hits that Contour it must either be entering or exiting the shape and if it's entering it then of course it's bound to exit it at some point but in this case the ray doesn't hit any other Contours along its Journey which means it must have been exiting the shape and so obviously it must have started out inside of it now moving our point of Interest back a bit into the B hole here for want of a better term the ray now intersects with two Contours along its path from that we can deduce it must have first entered the shape and then exited it and so clearly the starting point this time was on the outside the simple rule we can gather from this is that if the number of intersections is even we're outside the glyph while if it's odd we're inside of it so all we really need to do is figure out the Maths for calculating the intersection of a horizontal Ray with a beia curve for example say we have this curve over here and we want to figure out where this Ray at a height of 0.5 intersects with it since the ray is horizontal we only need to care about the Y values of the curve so we're basically just asking where this function is equal to 0.5 or equivalently we could shift the whole curve down by 0.5 and then ask where the function is equal to zero conveniently that's exactly the question question that the quadratic formula is there to answer so if we just take our equation for the Y component of the Bia curve and plug the values for a b and c into the quadratic formula we're going to get back the values of T where the corresponding y value is 0 in this case the T values come out as 0.3 and 1.2 and since values outside of the range 0 to one are not on the curve segment that means that we count one intersection in this case all right so here's some code implementing the quadratic formula and one small detail here is that if a is zero we get a division error this is the case where the curve is actually a straight line and so we can then solve it like this instead okay now I've also written this little test just to see that this is working properly and all it does is calculate the a b and c values from the positions of the Bia points and then it asks what the roots of that quadratic equation are so where it's equal to zero but but first the height of our horizontal Ray is of course subtracted over here like we saw earlier to take its position into account then assuming a solution exists we just draw a point at that time value along the curve to visualize it using this little function over here so let's see how it goes I'm just going to grab some points and move them around a bit to see whether the intersection points look correct or not it's maybe not the most rigorous testing methodology in the world but we should catch anything obvious at least so far so good though and let me also try changing the height of the Ray and that seems to be working as well so using this horizontal intersection test we can now Implement that simple algorithm we're talking about where an even number of intersections means that the point is on the outside of the glyph while an odd number means that it's inside so I've basically just copy pasted our little test code here only after calculating the roots instead of visualizing them we now increment a counter if the root is valid and by valid I mean it needs to lie between Zer and one to be on the curve segment and we're also only interested in intersections to the right of the race starting point since that's the arbitary direction I picked for the ray to be traveling okay we now just need this tiny function here to Loop over all the Curves in the glyph count the total number of intersections and return whether that value is even or odd all right let's try it out and isn't that beautiful from here I guess we basically just need to increase the number of dots and we're done but hang on a second what are these weird artifacts that keep appearing and also I'm a bit concerned that my computer is about to burst into flames okay no need to panic let's just start with the most serious issue first getting rid of this weird line here so let's take another look at our [Music] visualization all right it just needed a good oldfashioned restart it appears and we're back in business so let me set the resolution to 100 here which is where that issue was occurring and I believe what's happening is just that there's obviously a meeting point of two curves over here and this row of pixels just happens to line up precisely for both of them to be counted in this case so in the code I'll just change the condition for being a valid intersection to Discount the very end of the curve meaning that where one curve ends and another begins we'll only count one of them and running this again we can see problem solved with that fixed let's now tackle the performance problems and I want to try simply moving all of our calculations into a Shader so that we can compute loads of pixels in parallel firstly I'm just going to try get the bounding boxes of each Cliff showing up so basically we have this buffer of instance data which just contains each Cliff's position and size at the moment and that gets sent to the Shader then we're requesting that a quad mesh be drawn for however many glyphs there are in the input string so when the Shader is processing the vertices of the cord mesh it'll be told which copy or instance of the mesh it's currently working with meaning that we can get the data for that instance and use it to position each vertex here's how it's looking at the moment this says coding Adventures by the way in case you can't tell to improve the readability we'll need to get the rest of the dat data over to the Shader so I've been working on this little function here which creates a big list of all the bezier points that we need along with a list of integers for storing some metadata about each unique gliph in the text in particular each gliph needs to know at what index it can find its bezier data as well as the number of Contours that it has and also the number of points in each of those Contours obviously we also need to record the index at which each Cliff's metadata begins so that we know where to find dir not very exciting stuff but it needs to be done and all of this ultimately gets packed up and sent to the Shader to live in these buffers over [Music] here another slightly tedious thing I've been doing is translating all our C code into Shader language for things like the quadratic formula intersection counting and the point inside of a glyph chest okay with that done let's try it out [Music] and it's working well mostly anyway I don't know why the Bitcoin logo has showed up that's just supposed to be a space and also the eye has gone missing but I'm sure these will be easy enough to fix I'm more concerned about whatever is happening over here so I'm just going to step through the different segments of the glyph to see what values we're getting for a b and [Music] c and I might have known if it isn't my old nemesis this floating point in precision and as you can see everything is jiggling like there's no tomorrow so computers tragically represent numbers with a finite number of bits meaning that Precision is limited on this segment for example when we calculate the coefficient a by taking p 0 adding P2 and subtracting twice P1 we should get precisely zero on the y- AIS except the computer begs to differ it says it's extremely close but not quite equal to zero this means that when we apply the quadratic formula we're dividing by this tiny incorrect value and getting incorrect results so we need to get a little dirty I suppose and just say that we'll consider our curve to be a straight line if a is very close to zero and now those horrible little lines have disappeared by the way we should check if we've managed to actually improve the performance with all of this and indeed the computer is running a lot more happily now okay after a few Misadventures I've managed to fix that missing eye and uninvited Bitcoin and so at last we're able to properly render some text to the screen with our Shader since we're doing this directly from the curve data we can also zoom in pretty much to our hearts content and it remains perfectly smooth well I say perfectly smooth but of course there are still not enough pixels in most modern displays to prevent edges from looking unpleasantly Jagged so we'll definitely need to implement some kind of anti-aliasing to improve that I also spotted a weird flicker when I was zooming in I'm struggling to see it again now but here's a freeze frame from the recording so I've been zooming in and out and panning around trying to see how common these flickers are and where they're occurring there's another one did you see that this is a bit frustrating because it only happens when the pixels perfectly line up in some way so it's hard to capture the exact moment in fact it's right in The Sweet Spot I'd say of being rare enough to be a nightmare to debug but not quite rare enough to just pretend it doesn't exist so I really want to have some way of quantifying how many of these artifacts are occurring so that I don't have to spend multiple minutes after each tweak to the code trying desperately to define whether I've made things better or worse so I've decided to build an evil artifact detector what I've done is simply taken a glyph and written some code to randomly generate these little test Windows the windows in Black are entirely outside of the glyph while the windows in white are entirely inside of it and I've run this across a bunch of different gphs from several different fonts the idea then is that each of these windows gets fed one by one to a comput trator which looks at all the texels which is to say all the pixels inside the the window texture and runs our algorithm for each of them to figure out whether they're inside the glyph or not it then draws the result to the window texture and also Flags the test as a failure if it doesn't match the expected value by the way a small detail here is that I'm am offsetting the Y position by an increasing fraction of a Texel as we go from the left to right edge of the window because that way we're not just running the same test over and over but rather covering a whole extra range of values which will hopefully help us catch more artifacts in total it's running just over 74,000 tests which takes about 10 seconds to complete and our current algorithm is failing 7,166 of them so roughly 10% to help hunt down the issues I've also set up this little debug view where we can see a list of the failed cases down the S side here and each case is defined by three numbers there's the glyph index which we can set over here then the resolution index which determines how many pixels are tested inside of the window and finally the window index of course tells us which window we're looking at so let's go to one of the failed cases such as 0219 and zooming in on the window we can see this little spot over here where it mistakenly thought that it was inside of the glyph now I'm going to draw in a quick debik line so that we can then zoom out and see where exactly this issue is arising and it appears to be this Troublesome meeting point of two curves again where the intersection is being double counted I thought I had fixed that earlier when we told it to ignore time values exactly equal to one but clearly that was overly optimistic it makes sense in theory but as we saw recently with every bit of maths we do numerical imprecision has an opportunity to creep in and so we can't exactly trust the values that we're getting so I've been working on a dirty little fix for the double counting where we simply record the positions of the intersections that occur on each segment and then when we're examining the next segment we ignore any intersection points that are extremely close to those previous ones all right let's try this out and we get a failure count of over 30,000 okay I see what went wrong though we're recording the positions regardless of whether they were actually on the curve segment or not so let me fix that quickly and then redo the test and this time 4,943 and with some trial and error just tweaking the value of the distance threshold I was able to get the failure count down to 3,647 all right now I've been taking a look at some of these remaining failures such as this one over here and in this case we have a few spots that falsely believe they're outside of the gliph meaning the intersection count is even even when it should be odd and looking at this we can see we have 1 2 three simple intersections and then we avoid the double counting over here giving us a total of four the count is supposed to be OD though so I guess in this particular case we actually do need to count both of these I think because they're forming this kind of vertical wedge so in a sense the ray is both exiting and entering the glyph at that point meaning they cancel each other out I'm not sure if I'm making any sense but regardless this whole double counting business is becoming quite annoying so I've been brainstorming a bit how we could approach the problem slightly differently to get around it the new plan is to forget about counting the number of intersections but rather look for the closest intersection the idea is that regular Contours are defined in a clockwise Direction while the Contours of holes go anticlockwise and this means that if the closest curve crosses our Ray in an upwards direction we must be outside the glyph or inside a hole but that's the same thing really whereas if the closest curve crosses our Ray in a downwards Direction then we know that we're inside the glyph now to determine which direction the curve crosses the ray we can take our equation and just apply the power rule from calculus to figure out the gradient which comes out as 2 a t + B calculating that for any value T along our curve gives us this vector here which tells us how the X and Y positions along the curve are changing with respect to T for example over here the Y position of the curve is increasing as T increases so the gradient has a positive y value whereas over here Y is decreasing as T increases so the gradient has a negative y value that means we can simply check the sign of that value to find out whether the curve crosses our Ray in an upwards or downwards Direction so here's the new implementation as you can see we're simply searching for the closest point that our Ray intersects then calculating the gradient of the curve at that point and saying we're inside the glyph if that closest curve crosses the ray in a downwards Direction okay let's run the test now to see how this Compares and we're getting a failure count of 1,126 so not a bad Improvement there are some downsides to this approach though for instance here's a font I was experimenting with and we can see that the J is looking a little strange that's due to a small mistake in the font where the Contour has been wound anticlockwise like a hole if we were just counting the intersections it would give the correct result regardless but this new approach fails catastrophically also over here the Contour contains a slight self-intersection which again causes an issue so that's definitely a weakness to keep in mind but I'm going to run with this anyway since it seems promising in terms of eliminating those pesky artifacts at least with that said the same case we had before is actually still failing but now it's because right at the end point these two curves have the same position so it doesn't know which one is closer I think it makes sense then to favor the curve that's most on the left since our rightwards Ray should hit that first so in the code I've just added a quick test to see if two points are the same or at least very near to being the same and then if that's the case we skip the curve that has its P1 Point further to the right and running this now we've eliminated a few more problems down to 10,24 all right here is our next problem and I'm just trying to spot the artifact here it's quite Tiny But there it is okay I'm not sure what's going on in this case I don't even know which of these curves the ray is intersecting so I've quickly added a way to highlight the curves of each Contour by their index and we can see here the possibilities are curves 2 3 or four now shaders can be a little tricky to debug but we can get creative and do something like output a color based on the index of the closest curve we found so red if index 2 green of index 3 and blue of index 4 and now we can zoom in on our debug texture again to see which it is and it must be our lucky day two different problems for the price of one so from the one spot it's hitting curve two and from the other it's hitting curve four let's think first of all about the ray that's hitting curve number two I think it's odd that our re is able to hit that curve but evidently miss the closer curve over here since these end points are at exactly the same height I think what might help in at least some situations like this is to test whether all the points of a curve are below our Ray and simply skip the curve in that case and same story if all the points are above the ray that's because these raw position values are really the only reliable thing we have as we've seen once we start doing maths with them all bets are off and so by skipping curves early on based on the positions we can avoid accidentally hitting them due to numerical issues it would really be wise to use these positions directly as much as possible for example at one point I read a bit about the slug algorithm which has this interesting way of classifying different curves based solely on the positions of their control points this technique is patented though so I'm just going to forge ahead with my own hacky approach instead all right so running the test again with our curve skipping enabled now we get a failure count of 882 and looking at our case from before we can see that only the intersection with curve 4 remains this is actually the curve that we wanted to intersect with but since it complet completely flattens out over here we must be getting a gradient of zero which is ambiguous as to whether the curve is going up or down however from the fact that p 0 and P1 l in a straight line here and P2 is below them I think we could reasonably consider this curve is going purely downwards so in general let's say that a curve is decreasing for its entire duration if P2 is below p 0 and increasing if it's the other way around although this is only true of course if P1 is somewhere in between them on the y- AIS as soon as P1 becomes the lowest or highest point the curve starts curving in both directions and this is kind of troublesome actually because let's say we have a ray which should theoretically intersect precisely at the turning point over here where the Y gradient is zero even the tiniest imprecision might cause the program to actually think it intersected a little bit behind or ahead of that point so we could very easily end up with the wrong value most fonts I've come across so far actually seem to avoid using this kind of curve but if we encounter one maybe we could simply split it into two segments one where it's going purely upwards with respect to T and one where it's going purely downwards doing that should be reasonably straightforward first of all we can figure out the Turning Point simply by setting the Y gradient to zero and then solving for T from which we can of course compute the actual point then say we want to construct this segment here that goes from p 0 to the Turning Point obviously we're going to place the two end points of the new curve at p 0 and the turning point but the big question is where does the new P1 Point go well we need the gradient at p 0 to Still Point towards the P1 point of the original curve in order to maintain the same shape which means that our new P1 point is constrained to be somewhere along this line here and where exactly is where it forms a horizontal line with the Turning Point since of course the gradient there by definition is zero on the y- AIS so I've been writing some code to do these calculations for us automatically and it's such a great feeling to figure out the Maths for something and then just have it work perfectly the first time which is why I was a bit disappointed when this happened anyway it turns out I just forgot some important parentheses and while we're here let's take a quick look at the maths which is super simple we just say that if we start at p 0 and move along the gradient Vector of the original curve at p 0 for some unknown distance we're eventually going to hit a point with a Y value equal to the turning point we can then rearrange that to solve for the unknown distance which then lets us calculate our new P1 point and the exact same goes for the other segment of course and now we we can see that this is working so this can be done as a pre-processing step on the glyph Contours though like I said most the fonts I've tried actually keep the P1 points strictly between p 0 and P2 so it's usually not necessary in any case in the Shader we can now determine if the curve is going up or down simply based on the relative y positions of p 0 and P2 hopefully this will improve the accuracy somewhat and running the test on this we now have a failure count of 755 I'm slightly underwhelmed but it's progress nonetheless okay let's keep going the next error on our list is this one here where this Ray is managing somehow to dodge both of the segments at their meeting point I believe what's happening is that the roots we're calculating there are just ever so slightly outside of the valid bounds due to Precision errors of course so I've simply added in a little fudge Factor to catch those cases and running the tests again we're now down to just 404 remaining failers okay here's the next case on the list and in this one the ray should be hitting segment six but after some debugging I discovered it's actually just missing it due to you won't believe this Precision errors again and instead hitting only segment 7 so in our quadratic formula missing the curve means that the descript discriminant is negative so let's try actually allowing it to be a tiny bit negative to catch those cases and then just clamp it to zero in our actual calculation this might seem pretty dodgy but remember we are skipping curves that are entirely above or below the ray so I don't think it will actually introduce many false positives I am hoping it will cut down on the false negatives though so let's run the test once again and that's actually brought us all the way down to just 10 fail cases which is very exciting be careful not to fall off the edge of your seat so let's have a look at what [Music] remains all right our array is hitting the tip of these two segments here and this looks very similar to a problem we dealt with earlier actually remember this one where the ray was also hitting the tip of two segments and we told it to prefer the one that had its P1 Point further on the left the idea being that a ray traveling rightwards should hit that segment first but now we have a bit of an edge case here where the P1 point of the segment we want the ray to hit is actually not further to the left than the other segment so I've set up this little test area with different configurations of Curves to try and come up with a more robust approach and after playing around a bit I think I have something that will do the trick to be clear about what we're trying to achieve in case I wasn't making sense earlier the problem is that if our Ray is coming in and hitting the tip of these two segments we're not getting a clear answer as to which curve it hit first but intuitively it should be the blue curve since if the ray was just a tiny bit lower down then it would very clearly be hitting the blue curve first so my thinking now is that we'll consider the gradients of the two curves at our point of intersection and then imagine kind of winding in a clockwise direction from the Ray and seeing which gradient Vector we run into first which of curve that gradient belongs to is the curve we want by the way if the curves originate from above the ray instead of below it like this case here the idea still works the same only we imagine winding in a counterclockwise Direction instead and here's that idea expressed in code so running the test again we're now at long last down to zero errors which I'm very happy to see obviously scoring perf ly on the test does not mean it's perfect in fact I'd be shocked if there are not still plenty of edge cases Ling in the shadows but we've definitely come a long way in destroying those artifacts that were quite prevalent before at least I've been zooming and panning around this text for quite a while and not yet noticed a single one I did come across a more fundamental issue while testing some new fonts though and this arises when we have overlapping shapes like with this particular letter K over here we're using the closest segment to determine whether were inside or outside of the glyph but from over here for example the Ray would hit into this as the closest segment which incorrectly tells us that we're outside of the glyph and so if we try rendering it it looks like this thankfully though after some contemplation I realized that we can tweak the algorithm slightly to keep track of the closest distance to the exit of any shape that we're inside of as well as to the exit of any hole that we might be inside of and then by comparing those distances we can determine whether our point is inside the glyph or not so with that it seems like our rendering is now working okay however it is definitely in need of some anti-aliasing as I mentioned before so that it doesn't look so unpleasantly jaggedy currently each pixel decides what color to display based on whether a single point at its Center is inside of the glyph or Notch so the easiest Improvement I can think of would be to go from a single point deciding the fate of the pixel to perhaps a grid of nine points each contributing a little to the final color of the pixel we could even get fancy and consider the fact that each pixel is of course made up of a red green and blue component so over here for example instead of just dimming all three colors uniformly because only six of the nine points are inside of the glyph we could say that since red and green are within the glyph we'll just light those two up fully by outputting yellow and leave Blue turned off this is a a technique called subpixel anti-aliasing and we can see it in action if we take a very close look at the text in my code editor for example where along the left edge of the H for instance we can notice how mainly just the green and blue parts of the pixel are lit up while along the right edge here it looks like mainly just the red part of the pixel is lit up so this is a clever way of essentially tripling the horizontal resolution of the display there are some subtleties to this though in terms of filtering the results so that the color fringes aren't overly harsh and I guess detecting and handling the possibility of different pixel layouts on different displays so I'm actually going to leave this sub pixel idea for future experiments but here's our super simple anti-aliasing for today we just Loop over a 3X3 grid and calculate the different sample points within the pixel this is possible by the way thanks to this derivative function which tells us how much the position value changes between the current pixel we're working on and its next door neighbor in other words it's the size of the pixel in our glyphs coordinate space so we're just adding one for each of these points that is inside of the glyph and then dividing by nine to get the average of those samples and now instead of being all jaggedy our edges become nicely smoothed out this is at a very high magnification of course just to show the effect better it's obviously a lot more subtle in reality and while I'm not sure how well it'll show up in the video it definitely does make a big difference to how smooth the text feels nevertheless running our algorithm nine times for each pixel feels a bit exorbitant so I've been experimenting with a little Improvement where we actually only run it three times along the vertical axis and sum up now this horizontal coverage value basically instead of simply returning a Bool for whether the point is inside the glyph or not I've slightly modified our function to return a coverage value between 0 and 1 this is calculated by adding together the distance to the nearest curve segment on either side of the input Point both of which have been clamped to half the width of a pixel and then dividing by the width of the pixel this means that if the pixel is far away from any Edge then it will get a value of one meaning it's completely inside of the glyph or inverted to zero if we're actually outside of the glyph and for pixels closer and closer to an edge that value will get closer and closer to 0.5 so that we get a smooth transition between 0 and one across the edge here that is in action with our test text from earlier and if we magnify this a bit we can see the anti-aliasing is looking pretty decent I think it's maybe a slightly strange implementation though I later came across this write up which talks about sending out the Rays in different directions to estimate what fraction of this little circle is covered by the glyph which sounds a bit more flexible and accurate so I might use that instead in the future in any case what I'd like to do now is run a super quick performance test so I'll paste in the entire 12,000w script that I have for this video so far as the input and try running [Music] it all right taking a look at the statistics it seems to be running happily enough at around 800 frames per second and I tried comparing the average frame duration here to that of a blank project and it seems like the text is taking roughly 0.2 milliseconds to render although I'm honestly not sure how to properly profile these sorts of things the performance does fall off a cliff ands surprisingly though for very complex fonts here's a random font I found with lots of little Wiggly details in the glyphs this G for instance contains 440 bezier curves which has taken us from roughly 800 frames per second crashing down to about 150 there are ways we could optimize this though the obvious idea that to mind being splitting each glyph up into multiple bands so that each pixel only has to test the beia segments inside of the band that it's in additionally each glyph is currently rendered as a quad which is nice and simple but in a lot of cases can leave quite a bit of empty space that the Shader still needs to Crunch the numbers for with a bit of pre-processing though we could construct much tighter fitting meshes tailed specifically for each individual glyph far more challenging than improving the performance I suspect is improving the legibility of the text at small sizes right now it's very easy to read on my screen at least but if I just zoom out a little more it really starts to go downhill quite fast let me magnify this view so we can see the problem better and take this word here for example we can see how some parts of it show up nice and bright while other parts are much dimmer because maybe they fall awkwardly between two pixels for example so both pixels end up just being kind of great if I Pan the camera slightly we can see how the legibility of each letter actually changes as its alignment with the pixels changes and that seems like kind of a tough thing to fix I believe we'd need to delve into that scary bite code interpreter stuff that I was so happy to skip in the beginning so definitely a problem for some other day what's still bugging me a bit though is those downsides I showed earlier to our closest curve rendering approach namely failing if the Contour has the wrong winding Direction and being very sensitive to self intersections so I decided to take everything I learned from that artifact hunting process and basically start over from scratch with the counting method again I won't bore you with another blow-by-blow account but armed with a much better understanding of the problem now I was able to quickly get it working with zero issues on the test search a bunch of these same ideas are still in there and the main new addition is a super simple one it's really just a small detail in the way that curves are skipped which actually helped immensely with the double counting issues that were plaguing us previously basically when we're testing if all the points of a curve are above or below the ray we need to decide whether we want to include zero in the test which means skipping the curve even if one of the points is precisely at the same height as the ray if we don't skip those cases we get issues with double counting at the meeting point of two curves as we've seen while if we do skip them then we essentially create tiny holes that the ray can sneak through at those meeting points of course we could try to solve that issue by only including zero for the P2 points perhaps since then if we imagine a contour like this a ray that perfectly lines up at the meeting point will only intersect one of the curves the problem though is that if the Contour looks like this instead then suddenly the ray isn't really crossing the Contour anymore it's just kind of scraping past it so we wanted to hit either neither of the curves or both of them so that it doesn't affect the end result I believe it was this kind of issue that drove me to abandon the counting method originally but now that we've processed the curves to ensure they can only go strictly upwards or strictly downwards it suddenly doesn't seem like such a big deal anymore the problem simply occurs when the curves are going in opposite directions one up and one down and so the way we can handle this in the code is to just check the direction of the current curve and for One Direction we include zero only for the p 0 points and for the other direction we include zero only for the P2 points and that seems to work very nicely all right so now that we're using the counting method again we can see that the incorrectly wound J renders correctly and the tiny self intersection is no longer causing any visible issues I was quite happy about this but victory was shortlived because I then realized that this approach actually fails in the case of overlapping shapes again now we can fix this with a slight tweak where we say that whenever the ray crosses a downwards curve which means that it's exiting the current shape we add one to this counter and otherwise subtract one if it's entering the shape then if the ray exited more shapes than it entered it must have started out inside of a shape this is essentially the same idea as the original counting method but should be able to handle overlapping shapes by the way this can also be extended nicely to work with our current anti-aliasing approach like this it's still just adding or subtracting one like before unless the distance to the intersection becomes extremely small like within the current pixel and in that case we're now adding or subtracting some fractional amount meaning that in the end we again get our nice smooth blend from 0 to one across the edge of the glyph this idea comes from that right up I mentioned earlier when we were first implementing the anti-aliasing anyway as we can see this little tweak has indeed resolved the overlapping shape issue while unfortunately breaking the problematic J again which is quite annoying on the other hand the self intersection is looking better than ever so I'd say we can count this as a half victory at least I did try a couple different things to get the wonky J to render correctly since it is a recurring issue that I've seen in a handful of fonts at this point but none of my attempts came particularly close to working this one perhaps least close of all so maybe we could try to automatically detect faulty Contours and correct them when importing the font instead but I need to stop worrying about these little details for now this was just supposed to be a quick experiment after all and I may have got a little lost in the weeds along the way sorry about that anyhow after all this I definitely feel like I've gained a much greater appreciation for the intricacies of rendering text here is one last test with our latest approach on a big wall of text with several different fonts and I think I'm happy enough with how it's looking to call it a day for now at least so to end things off I've just been having some fun in the vertex Shader here making the letters wave and spin around to say farewell and thanks for watching I hope you've enjoyed following this little journey into the surprisingly deep Rabbit Hole of rendering text and if you have any thoughts as to how the current implementation could be improved I'd of course love to hear them all right that's all for now though so until next time cheers
