Coding Adventure: Rendering Text

Hello everyone and welcome to another episode of today's Programming Adventures. I'd like to try

rendering

some

text

, as it's one of those things I always take for granted. To start, we're going to need a font and I just grabbed the first one I found on my hard drive, which happens to be Jet Brains mono bold, so let me open it up in a

text

editor just to see what's inside and as expected , the raw content is very unrevealing, so we are going to need to find some kind of guide to decode it. This is a ttf or true type font file, which is a format I'm told was developed by Apple in the late 1980s, so I took a look at its developer's website and located this reference manual , hopefully it's good. and simple to understand, okay, I've been skimming through it a bit and I'm increasingly baffled and bewildered by all the mysterious diagrams, the long lists of arcane bite code instructions, not to mention the strange terminology like ploop values ​​of the vectors of freedom 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 closely, I realize that most of this complexity centers around a single issue which is making sure text is displayed or printed clearly at low resolutions where unfortunate scaling could make one part of a letter appearing twice as thick as another, for example, a swatch that makes the letters difficult to read, so I don't think it's something we need to worry about for our little one. experiment at least today, which is definitely a relief, let's move on to the next section of the manual which gives us this list of mandatory tables that all fans must include and I am very excited about this glyph table since it sounds like where the shapes are store, so our first goal is to simply 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 first block of data that we will find in the file. and I don't think we really care about any of that except the number of tables, so we're going to want to skip a 32-bit integer and then read this 16-bit integer and just some quick police code to do exactly By the way, I'm printing the number of tables here just to make sure it's a plausible value which based on the tables listed in the manual I think would be between the required 9 and around 50 at most maybe so run this quickly and we can see that the number of tables is 4352, how am I doing something wrong?

Well, I finally found the answer in 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 the opposite of what my little Indian computer expects, so I quickly created this simple font reader class that allows us to read in a 16 bit value and do this conversion to little endian behind the scenes so we don't need to worry about it every time, okay so let's try running the program again and now the number of tables comes out as 17, which is much more believable, it means that we can proceed to the tables directory and what this gives us is a four-letter identification tag for each table and we have briefly seen how it is come and along with that there is also the location of the table in the file in bite offset form so in the code I just added this little loop over the total number of tables and there it just reads the metadata from each of them, of course, I also had to expand our reader class in the process with these two new functions to read a tag and a 32-bit integer, so I hope this is a good job, let's try to run it and these tags will be They look a little strange, for example, it looks like we have a little head here with a big question mark next to it, which, by the way, sums up how I feel right now.

Oh, I just realized. that I forgot to leave out all those other things in the first table that we didn't really care about, so let me do that quickly. I think it was three 16-bit values, so that's six bytes that we want to jump over here, right and now. we have the tables. I've seen the glyph table entry here that tells us bite location 35.43, so that's where we're heading next. Let's first take a quick look at the manual and it looks like the first one. One bit of information that will be given is the number of contours that make up the first glyph of the table.

Interestingly, that value can be negative, which would indicate that it is a composite glyph made up of other glyphs, but let's worry about that later we will have a bunch of 16-bit keywords that tell us the B in the glyph box and then comes the actual data, like these X and Y coordinates here. I'm looking forward to getting my hands on them, although we should keep in mind that these coordinates are relative to the previous coordinate, so they're more like offsets, I guess you could say, and they can also be in 8 or 16 bit format, which I guess these flags here will tell us, then there's also a series of instructions that I think are the scary bit code things that we're skipping and generally or I guess I'm not sure why I read this table backwards in the first place, we have indices for the end points of each contour, so if I understand this correctly, let's read a bunch of offsets from which we can construct the actual points and then say we get two contours and indices like 3 and six, for example , that just means that the first contour connects the points 0 1 2 3 and goes back to zero, while the second contour connects the points 4 5 6 and goes back to four, which seems easy enough, so the other thing to keep in mind is the 8-bit flag value, although it appears that only six of the bits are used, so we are going to have one of these flag values ​​for each point and according to the manual, bits one and two tell us they say whether the offsets for that point are stored in an unsigned format one or a signed format 2 and then they get a little complicated here.

Bits four and five have two different meanings depending on whether the representation of one bite or two bites is used. In the first case, it tells us whether that bite should be considered positive or negative and in the second case that is not necessary since the sign is included in the offset itself and therefore tells us whether or not we should skip the offset that way, if the offset is zero it doesn't need to be stored in the file so we can see that something is happening. basic compression. Here on that note, let's take a look at bit three if it's on. tells us to read the following fragment of the file to find out how many times this flag should be repeated so that we don't have to waste space storing repeated copies of the same flag.

Finally, Bit Zero tells us if a point is on the curve or off the curve and I'm not entirely sure what that means right now, but we can worry about that later, let's load these points first to actually test if a particular bit in the flag is on or off. I'm using this little function here that simply shifts all the bits so that the bit we're interested in is in the first place, then masks it, meaning all the other bits are set to zero, and finally checks to see if the resulting value is equal . to one, okay and then here's a function I've been working on to load one of these simple glyphs and this does exactly what we just talked about: it reads in the end indices of the outline and then reads all the values ​​of the flags, of course, checking. each of them to see if they should be repeated a number of times and read the flag for this point and depending on that, we read in one bite the offset and add or subtract it depending on what the flag tells us to do or we read in a 16-bit offset, but only if the flag doesn't tell us to do Let's skip this.

I'm excited to see what comes of this, so here I just created a dictionary to map table labels to locations that we can use to set the reader's position. the start of the glyph table and then just read the first glyph and print its data, so let's quickly see what it looks like. Well, that looks promising, but we won't really know if it's nonsense or not until we draw it like that on the table. unity engine. I just quickly traced these points and I don't know what it's supposed to be, but I'm sure it will be clear once we draw the outlines.

Okay, it looks a little scruffy, but I think it's the missing character glyph and I actually remember reading that it needs to be at the beginning of the glyph table, so it makes sense. I just need to fix some bugs clearly so I've been playing around with the code a bit and this is how it's working now we just loop through all the final indexes and then create this little window in the array that allows us to access just the points on the Contour current since I obviously can't be trusted and then we draw lines between those loops backwards. to the first point on the Contour to close the Contour at the end, okay, let's try it and it looks much better.

One glyph is not enough, although I want all the glyphs and to get them we simply jump to the maximum P table where we can look up the total number of glyphs in front and then we go to the main table jumping over several entries that we are not interested in in this moment to find out if the glyph locations 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 the glyphs in the glyph table and then we can simply read them.

I must admit though pausing a font file must be pretty low on the list of exciting things one could do during the day. I'm really excited to see all of these letters appear here anyway, let's zoom in on one of these clips, like the Big B, for example, and we can see that while the glyphs are obviously very beautiful, they're maybe a little bit blocked, so I think our next step should be to bezier these bad boys. I've talked a lot about beziers before on this channel, but briefly, if we have two points and we want to draw a curve between them, we need at least one. additional control point to control how the curve should be curved now to display this curve let's imagine a point that starts at the initial point and moves at a constant speed towards this intermediate control point from which a second point simultaneously moves towards the point end in it The amount of time it takes for the first point to complete its journey in this way is not very 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 It's a little better, but for an extra touch, let's also leave a ghost trail of the old beams behind and now we're really getting somewhere, so the curve that these beams is our Bezier curve and all we need now is a way to describe it.

This curve is mathematically surprisingly easy to make, we just need to imagine one last travel point, it moves between the first two Travelers and also completes its journey in the same amount of time by 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 that it takes in both the start and destination positions, as well as a sort of Time Value that can be between 0 and one as a measure of the progress of The Journey, the position of the point at the given time, is calculated as the start point plus the displacement that takes us from the start point to the end point multiplied by the time value.

Then from this linear interpolation we can construct our Bézier interpolation which only calculates these intermediates. Points A and B as we saw and then interpolate between them 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, just cutting the curve on a set of discrete points based on this resolution value and then drawing straight lines between them, so quickly testing this we can see that with a resolution of one of course we only have one straight line, two gives us the idea vaguest of a curve and from there it quickly starts to look pretty smooth anyway, let's go back to our block B now that we have Bézier working and I'll quickly jump into the Cod here and modify it so that each set of three points on the Contour is now drawn like a curve and let's take a moment to admire how it looks, wait, this isn't exactly what I had in mind, but it looks interesting, so let's try writing some text with it and we can come back and fix it in a minute.

I have created a string here that says hello world andwe just go through each character in that string and of course on the computer each of these characters is just a number defined by the standard unic code and I'm using that number as a we index the glyph array that we've loaded then we draw each one of them and we add a hardcoded space between them because I still need to find out where they have hidden the actual spacing information. Well, let's take a look at the result. the letter spacing is too small, so I'll quickly increase it, but unfortunately the text is still not particularly understandable.

Clearly the glyphs in the font are not in the same order as Unicode, which actually makes a lot of sense since different fonts support different subsets of characters. so there will never be a one-to-one mapping; instead, the source file must include a character map to tell us which GPH indices correspond to which Unicode values. This part seems a bit annoying because there are nine different formats in which this mapping information can be stored, although I later read to my great relief that many of them are obsolete or were designed to meet anticipated needs that never materialized and upon reading a little more, it seems that 4 and 12 are the most important to cover, so I'm going to start unpacking them.

Here's the code I wrote to handle those formats and I'm not going to mislead you with the details. since we talked about all it does is look up in a slightly complicated way for the Unicode value that corresponds to each glyph index with that mapping information, now we can finally retrieve the correct glyphs to display our little hello world message. I really like how stylish some of these buggy beziers are look maybe this is the fun of the future oh and by the way if you want to learn more about the beauty of bezier cures I highly recommend a video called the beauty of bezier cures and it's equals continuity of splines Now, let's see if we can correct this mistake I made.

First of all, we can see that here, where there is supposed to be a straight line, this point actually just controls how the curve bends as it goes to the next point. here, then it seems that the glyphs are not made entirely of Beziers as I was assuming, but rather have some ordinary line segments mixed in. Also take another look at the manual and show this example where we have a spline made up of two. consecutive Bézier curves and what it points out is that this shared point between the two curves is exactly at the midpoint between these two control points, this is normally the place where you would want it to be simply because if it is not at the midpoint we can see We no longer get a smooth and nice union between the two curves, which means that this Spain becomes discontinuous and that is why what the manual recommends doing for these points that are right in the middle is to save space by simply eliminating them, as it says the existence of that Medium.

The point is implicit, so we will need to infer these implicit points when we load the source and I think that's where this curved flag that we saw earlier will be useful, so in this example points one and two would be marked as outside the curve, while points 0 and three would be on the curve, what we can do then is say that if we find two consecutive points outside the curve, we will insert a new point without curve between them as well just to convert everything to Bas for For the sake For consistency, let's also say that if we find a straight line segment that would be two consecutive non-curved points, we'll also insert an additional point between them, so I've been writing code to handle that quickly, which as we just did.

What we are talking about simply checks if we have two consecutive entry or exit points of the curve and, if so, inserts a new point in the middle. Here's a quick test to see if it works as expected, so these are the curve entry and exit points that were actually stored inside the curve. source file for our letter b and then here are the implicit curve points that we have now inserted into the Contours, as well as these additional points between the straight line segments to convert them into valid Bezier curves with our code to draw these curves. finally it works as expected and just for fun I made it so we can take these points and move them around to edit the glyphs if we want anyway lets put this to the test quickly by drawing all the letters of the english alphabet and they all seem to have come out correctly so let's also try the lowercase letters and these look good too except I noticed we are missing the I and the J.

I guess they must be compound Cliffs since we haven't handled them yet and I think the idea is simply that the point is would store as a separate glyph and then the I and J would reference that instead of each having to store their own copy, so I've spent some time implementing composite glyphs here and since These are made up of multiple component glyphs. Basically, all we have to do is keep reading into each component glyph until we get the word that we've reached the last one and all the point indices and contour endpoints of those are simply grouped into one. glyph that is returned at the end here, so here is the function to actually read a component glyph and this essentially just gives us the index to look up the data for a simple glyph, although now I'm wondering if a compound glyph can contain other compound glyphs I will have You'll have to modify them later if that's the case, but anyway the simple glyph we just read can be moved, scaled, or even rotated if you'd implemented it yet, making it oriented correctly in relation to each other. components and we can see that the transformation is applied to the points here, so with that piece of code we can do the last read on our missing inj and this has also unlocked a whole world of diacritics since of course all of these do using compound glyphs like Well, to avoid having a bunch of duplicate data, okay, we're making good progress.

I think I'd like to start testing a few different fonts to see if they work correctly. Let's write a little test sentence here, like the classic one. one about the fox and the lazy dog ​​or this one I found about discotex and jukeboxes. These are good test sentences because of course they contain all the letters of the alphabet which I learned today is called a pangram anyway this is the jet brain monel we use. I've been using it and I'm going to try to switch now to maybe the open sense. Okay, there's clearly an issue with the brightness size, but I found this useful scaling factor in the main table that should take care of that and it looks a lot. better, but obviously the spacing is a little off.

The problem is that this is not a monospaced font like we had before, so our hardcoded spacing value is no longer good for cutting after some searching, although I don't need this horizontal metric table that tells us how much space we need to leave after each glyph, which is known as the glyph advance width, so here's some code to read that information and if we use those values, our text obviously looks a lot more sensible. Well, I just spent. a little time refactoring and cleaning up the project because things were getting a little out of hand, let's quickly make sure we haven't messed anything up in the process and of course I'm fine.

I've tracked down the issue, so we're back on track and now that we can type some words and display the outlines, let's finally figure out how to properly render the text. I guess the easiest solution would be to simply increase the thickness of the lines until they become a solid shape. alright, thanks for looking, wait a minute, this might not be the most readable approach, so maybe we should take some time to explore our options, for example a few years ago I wrote this little polygon triangulation script using a algorithm called ear cropping and one idea could be to simply feed in the points we are currently using to draw the contours and get a mesh for the computer to draw.

However, this doesn't seem ideal because if we want the letters to be nice and smooth, we will have to have a lot of little triangles on the screen that the computer may not particularly appreciate, so this article presents a much smarter approach based on mesh over the representation of resolution-independent curves. Basically, we will triangulate a straight line type mesh on the inside of the screen. glyph and then render a single additional triangle for each of the curved parts so that it is clear for each Bézier curve in the Outline, 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 the curve so we can get a smooth result without having to add many more triangles.

To do this, we're going to need to think about what the shape of our beur actually is and just by looking at it you might think it looks good. parabolic, but let's take a look at our equation to make sure we currently have it defined as three separate linear interpolations, which paints a nice geometric picture, but it's a little clunky mathematically, so I quickly wrote these interpolations as one giant equation and then he simplified it a little bit to get to this which of course we can 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 curve Bia that we are working with is called a quadratic buia curve which confirms our parabolic suspicions and perhaps we can see this even better if we allow the lines to extend beyond this time interval from 0 to 1.

Now it is a little more elegant than the standard parabola, although in that we can actually rotate it and that's only because our equation of course generates two-dimensional points instead of a single value, we could split it if we wanted into separate equations for the X and Y components and if we had to graph them, just be regular old unrotated bars like this, so there's nothing mysterious here, if we move a point on the x axis we can see how it reflects on the x graph and if we move a point on the y axis we can see how it reflects . on the Y graph, so I think now we're ready to think about this problem of how to fill the region inside the curve, which is a little confusing when the entire curve is rotated like this, so let's just position the point of so that it looks like a perfectly normal parabola y = x^2, one way to do this is to put P1 at coordinates half point 0 p 0 at coordinates 0 point 0 and P2 at coordinates 1 point 1 and that in fact has given this nice simplification case where the Y values ​​of the curve are equal to the square of the are where Y is equal to x^ 2, so obviously the interior is just where Y is greater than x squ to draw this region, although we will need a mesh and a shader for the mesh.

We can simply construct a triangle as we saw before from the three points beia and I. We will give those points the texture coordinates corresponding to the positions in which we placed the points to obtain that simple parabola y = x^2, then in a Shader we can obtain the interpolated X and Y texture coordinates for the current pixel and let's visualize the value of x. for now in red it looks like this and here is the Y value in green, then here they are both together. In fact, I find it a little easier to see what's going on if we divide the values ​​into discrete bands by multiplying by 10, for example, and 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 grid here instead of a continuous gradient, of course, we can move our points and we can see how this grid transforms along with them from Again, the Shader automatically interpolates the texture coordinates to give us the value of the current pixel in space of texture, although things always look like this, since these are the texture coordinates that we define in the Shader.

Let's test if y is greater than that we only had to think of the simplest possible case and By taking advantage of the way shaders work, we get the rest for free. I thought that was a good idea, so now we can go back to our mesh of just the straight glyph lines and then add those triangles for all the curves. and then use this clever little idea to shade only the parts inside the curve - wait, that's not quite right - although it looks like along the outer edge of the glyph, where the points go clockwise , everything is correct, but here inside, where the points now go counterclockwise, we actually want to fill the opposite regionof the curve, so in the Shader I quickly added this little parameter that 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 looks like We've solved our problem here, so this is a pretty interesting way to represent text.

I think a potential problem with this approach is that Microsoft has a patent on the research that skims it, although it appears to only cover the more complicated case of Basia cubic curves, which is when the curves are defined by four points instead of We're working with three, so it's possibly okay to use them, but I'm still curious to experiment with different ideas today, so let's leave this aside for now. What if we just took our old glyphs made in meeses? of ridiculous amounts of triangles, but let's say we don't actually care about the triangle count because instead of

rendering

them to the screen, we pre-render them all to a texture file that way we ultimately only need to render a single quad for each one. letter and use a shader that simply cuts out the appropriate part of that Atlas texture to display the letter we want.

This would be nice and fast, but of course has some issues with scaling. We would need to make our Atlas really 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 small function to calculate the distance of each pixel to the coast, which could then be used to make a simple wave effect, so we could use that same layer here to convert our glyph image to an image of glyph distances.

A simple shader could then sample the distance and output a color if so. The distance is within some threshold, we look like this, this scaling is better than before because now the Shader is mixing distances instead of adjusting to the values, the Contours are a little jagged, but I'm sure we could improve that with some improvements in technique. However, these texture-based approaches are a bit annoying in the sense that it's not really practical to support all characters in a font because then the texture would be too large, so we always have to commit to some subset to get Good quality and Still, the edges tend to have some obvious imperfections, at least if you resume excessively close to the text and we tend to lose our nice, sharp corners.

That said, I've seen some interesting research on using multiple color channels to store additional information. that can help increase the quality quite a bit, so I'd like to experiment with this at some point because it's definitely an interesting technique, but for today I prefer to render the text directly from the beia data without any textures that compromise the intermediate quality, so that I focused. on a single letter for a moment let's imagine a grid of pixels behind it and our goal is obviously to illuminate the pixels that are inside the L, therefore we need a way to detect if a dot is inside it or not and happily there is a way very intuitive way to do this, so we are interested in this point here, all we have to do is choose any direction and imagine a ray going out until it reaches one of the contours of the shape, when it reaches that contour, it must be entering. or exiting the form and if it is entering it, then of course it will surely exit it at some point, but in this case the ray does not touch any other contours along its journey, which means that it must have been exiting the shape and therefore obviously must We have started inside it and have now moved our point of interest a little towards hole B.

Here, for lack of a better term, the ray now intersects two contours a along its trajectory, from which we can deduce that it must have first entered the form and then. We got out of it and clearly the starting point this time was outside. The simple rule we can deduce from this is that if the number of intersections is even, we are outside the glyph, while if it is odd, we are inside it, so all I really need to do is figure out the math to calculate the intersection of a horizontal ray with a beia curve, for example, let's say we have this curve here and we want to find out where this ray intersects at a height of 0.5 from the ray. is horizontal, we only need to worry 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 entire curve down by 0.5 and then ask where the function is conveniently equal to zero. that is exactly the question the quadratic formula is meant to answer, so if we simply take our equation for the Y component of the Bia curve and plug the values ​​of a b and c into the quadratic formula, we will get the values ​​of T where the value of and corresponding is 0, in this case the values ​​of T come out as 0.3 and 1.2 and since the values ​​outside the range of 0 to one are not in the curve segment, that means that in this case we count a intersection, so here is some code that implements the quadratic formula and a little 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 then we can solve for it so, okay, now too I wrote this little test just to see that it works correctly and all it does is calculate the values ​​a, b and c from the positions of the points Bia and then asks what the roots of that quadratic equation are, where is equal to zero, but but.

First, of course, the height of our Horizontal Ray is subtracted here as we saw before to account for its position. Then, assuming there is a solution, we simply draw a point at that time value along the curve to visualize it using this little function here, so let's see how it goes. I'm going to take some points and move them around a bit to see if the intersection points look correct or not. It may not be the most rigorous testing methodology in the world, but we should at least grasp the obvious. So far so good and let me try changing the height of the ray and that seems to be working too so using this horizontal intersection test we can now implement that simple algorithm we are talking about where an even number of intersections means that the point is at the outside of the glyph, while an odd number means it's inside, so I basically copied and pasted our little test code here only after calculating the roots instead of displaying them, now we increment a counter if the root is valid and for valid , I mean it must be between Zer and one to be on the curve segment and also we are only interested in the intersections to the right of the race start point since that is the arbitrary direction I chose so that lightning travels Okay, now I just need this little function here to loop through all the curves in the glyph, count the total number of intersections, and return whether that value is even or odd, okay, let's try it and it's not so pretty from here.

I guess we basically just need to increase the amount of points and that's it, but wait a second, what are these strange artifacts that keep appearing and I'm also a little worried that my computer is about to burst into flames? Okay, don't panic, let's start with The most serious problem is first getting rid of this strange line here, so let's take another look at our visualization. It's okay, just needed an old fashioned reboot. Looks like we're back to business, so let me set the resolution to 100 here, which is where. that problem was occurring and I think what's happening is that there's obviously a meeting point of two curves here and this row of pixels align precisely so that they're both counted in this case, so in the code I'll do that. just change the condition to be a valid intersection to discount the end of the curve meaning that where one curve ends and another begins we will only count one of them and by running this again we can see the problem solved with that fixed, now let's address the performance issues and I want to try to simply move all of our calculations to a Shader so we can calculate a large number of pixels in parallel.

First of all, I'm going to try to get the bounding boxes for each Cliff to appear, so basically we have this buffer of instance data that just contains the position and size of each Cliff right now and that's being sent to the Shader, so we request that it be drawn a quad mesh for all the glyphs in the input chain, so that when the Shader is processing the vertices of the string mesh it will be told which copy or instance of the mesh it is currently working with, which means that we can get the data for that instance and use it to position each vertex.

This is what it looks like right now. This says

coding

. Adventures indeed. in case you can't tell, to improve readability we'll need to send the rest of the data data to the Shader, so I've been working on this little function here that creates a big list of all the Bezier points it needs along with a list of integers to store some metadata about each unique glyph in the text, in particular each glyph needs to know in which index it can find its Bezier data, as well as the number of outlines it has and also the number of points.

On each of those Contours we obviously also need to record the index where each Cliff's metadata starts so we know where to find not-so-interesting stuff, but it needs to be done and ultimately all of this gets packaged up and sent to the Shader. living in these buffers around here another slightly tedious thing I've been doing is translating all of our C code into the Shader language for things like counting intersections of quadratic formulas and point inside a glyph chest, well done, let's try it and De Anyway, it's working fine for the most part. I don't know why the Bitcoin logo appeared, which is supposed to be a space, and the eye is also gone, but I'm sure it will be pretty easy to fix.

I'm more worried about whatever. is happening here, so I'm going to loop through the different segments of the glyph to see what values ​​we're getting for a b and c and I might have known if it wasn't my old enemy this floating point in precision and As you can see, everything moves like there's no one tomorrow, so computers tragically represent numbers with a finite number of bits, which means that precision is limited in this segment, for example, when we calculate the coefficient a by taking p 0 by adding P2 and subtracting twice P1, we should getting exactly zero on the y-AIS, except the computer disagrees, it says it is extremely close but not exactly equal to zero, this means that when we apply the quadratic formula we are dividing by this small incorrect value and getting incorrect results , so we need to guess to get a little dirty and just say that we will 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 have actually managed to improve performance with all this and in fact the computer is working much better now.

Well, after some mis

adventure

s, I managed to fix that missing eye and uninvited Bitcoin and we can finally properly render some text on the screen with our Shader, since we are doing this directly from the curve data, we can also get pretty close to the to our heart's content and it remains perfectly smooth, well I say perfectly smooth, but of course there still aren't enough pixels on most modern displays to prevent the edges from looking unpleasantly jagged, so we'll definitely need to implement some sort of smoothing to improve that. I also saw a strange flicker when I was zooming.

I'm struggling to see it again now, but here's a freeze frame of it recording, so I've been zooming in and out and panning around trying to see how common these flickers are and where they occur. There is another. Dresses? This is a little frustrating because it only happens when the pixels line up perfectly. somehow, making it difficult to capture the exact moment, in fact, it's right in The Sweet Spot. I'd say it's weird enough to be a nightmare to debug, but not weird enough to just pretend it doesn't exist, so I really want to have some way to quantify how many of these artifacts are occurring so I don't have to spend several minutes after each adjustment in the code desperately trying to define if I have improved orIt made things worse so I've decided to build an evil artifact detector, what I did was just take a glyph and write some code to randomly generate these little test windows.

The black windows are completely outside the glyph, while the white windows are completely inside it and I ran this. through a bunch of different gphs from several different sources, the idea then is that each of these windows is fed one by one to a computer that looks at all the texels, that is, all the pixels within the window texture and run our algorithm. so that each of them finds out if it is inside the glyph or not, then draws the result on the window texture and also marks the test as failed if it doesn't match the expected value, by the way, here's a little detail. that I'm offsetting the Y position by an increasing fraction of a Texel as we move from the left to the right edge of the window because that way we're not just running the same test over and over again, but we're covering a whole additional range. of values ​​that will hopefully help us detect more artifacts in total.

It's running just over 74,000 tests that take about 10 seconds to complete and our current algorithm fails on 7,166 of them, about 10% to help catch the problems I also configured. this little debug view where we can see a list of the failed cases on the S side here and each case is defined by three numbers, there's the glyph index which we can set here and then the resolution index which determines how many pixels are tested within of the window and finally the window index of course tells us which window we are looking at so let's go to one of the failed cases like 0219 and as we zoom in on the window we can see this little dot here where it mistakenly thought it was inside of the glyph, now I'm going to draw a quick debik line so that we can then zoom out and see where exactly this problem arises and it appears to be again this problematic meeting point of two curves where the intersection is taking place. double counting I thought we had fixed that before when we told it to ignore time values ​​exactly equal to one, but clearly that was too optimistic, it makes sense in theory, but as we saw recently with every bit of math we do, numerical inaccuracy has a chance to sneak in and so we can't exactly trust the values ​​we're getting, so I've been working on a dirty little solution for double counting where we simply record the positions of the intersections that occur in each segment and then When we are examining the next segment, we ignore any intersection points that are extremely close to the previous ones.

Ok, let's try this and get a failure count of over 30,000. Ok, I see what went wrong, although we are recording the positions regardless of whether they were actually in the curve segment or not, so let me quickly fix that and then redo the test and this time 4.943 and with some trial and error By simply adjusting the distance threshold value I was able to get the failure countdown to 3,647 in total. Right now I've been looking at some of these remaining glitches, like this one here and in this case we have some points that falsely believe they are outside the glyph. which means the intersection count is even when it should be odd and by looking at this we can see that we have 1 2 three simple intersections and then we avoid double counting here, which gives us a total of four, although the count is assumed to be OD.

I guess in this particular case we need to count both, I think because they're forming this kind of vertical wedge, so in a sense the ray exits and enters the glyph at that point, which means they cancel each other out. I'm not sure if I'm making any sense, but regardless this whole double counting thing is getting pretty annoying, so I've been thinking a bit about how we could approach the problem slightly differently to fix it, the new plan is to forget about count. the number of intersections but to look for the closest intersection the idea is that the regular Contours are defined in a clockwise direction while the Hole Contours go counterclockwise and this means that if the nearest curve crosses our Ray in an upward direction we must be outside the glyph or inside a hole, but that is the same thing really, while if the nearest curve crosses our Ray in a downward direction, then we know we are inside of the glyph Now to determine which direction the curve crosses the ray, we can take our equation and simply apply the power rule of calculus to calculate the gradient which results as 2 a t + B by calculating that for any value T along our curve gives us this vector that tells us how the X and Y positions along the curve are changing with respect to T, for example here the Y position of the curve increases as T increases, so the gradient has a positive y value, while here Y decreases as T increases, so the gradient has a negative y value, which means we can simply check the sign of that value to know if the curve crosses our Ray in a direction towards up or down so here is the new implementation as you can see we are simply looking for the closest point that our Ray crosses and then calculating the gradient of the curve at that point and saying we are inside the glyph if the curve further nearby crosses the ray in the downward direction, well let's run the test now to see how it compares and we get a miss count of 1,126, so not a bad improvement, there are some downsides to this. approach, although for example here is a font I was experimenting with and we can see that the J looks a little strange, this is due to a small error in the font where the outline has been rolled counterclockwise like a hole if only we were counting the intersections. would give the correct result anyway, but this new approach fails catastrophically.

Also, here the Contour contains a slight self-intersection which again causes a problem, so it's definitely a weakness to be aware of, but I'm going to go ahead with this anyway as it looks promising in terms of removing those annoying artifacts, at least That said, the same case we had before actually still fails, 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 is furthest to the left, since our rightward Ray should arrive first, so in the code I just added a quick test to see if two points are equal or at least very close of being the Same and then if that is the case we skip the curve that has its rightmost point P1 and by running this we have now eliminated some more problems up to 10.24.

Here's our next problem and I'm just trying it. detect the artifact here is quite small. But there it is fine. I'm not sure what's going on in this case. I don't even know which of these curves the ray is crossing, so I quickly added a way to highlight the curves. of each contour by its index and we can see here that the possibilities are curves 2, 3 or four. Now shaders can be a little difficult to debug, but we can be creative and do something like generate a color based on the index of the closest curve we find. so red if index 2 is green from index 3 and blue from index 4 and now we can zoom back in on our debug texture to see what our lucky day is and should be, two different problems for the price of one, from one point is reaching turn two and from the other it is reaching turn four, let's think first of all about the ray that is reaching turn number two.

I think it's strange that our fire can reach that curve, but it evidently misses the closest curve here from these end points. They are at exactly the same height. I think what might help at least in some situations like this is to test if all the points on a curve are below our Ray and just skip the curve in that case and the same story if all the points are above the This is Because these raw position values ​​are really the only reliable thing we have, as we have seen, once we start doing calculations with them, all bets are off and therefore by skipping the curves from the beginning according to the positions, we can avoid accidentally touching them due to numerical issues, it would be really 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 proprietary so I'm going to go ahead with my own hacky approach okay so running the test again with our curve jump enabled we now get a failure count of 882 and looking at our case above we can see that only The intersection with curve 4 remains, this is actually the curve we wanted to intersect, but since it completely flattens out here, we should get a gradient of zero which is ambiguous as to whether the curve goes up or down. below, however, by the fact that p 0 and P1 l are in a straight line here and P2 is below them.

I think we could reasonably consider this curve to be purely downward, so in general let's say that a curve decreases over its entire duration if P2 is below p 0 and increases. if it is the other way around, although this is only true of course, if P1 is somewhere in between in the AIS and as soon as P1 becomes the lowest or highest point, the curve starts curving in both directions and this is a bit problematic actually because let's say we have a ray that should theoretically intersect precisely at the inflection point here where the Y gradient is zero, even the smallest inaccuracy could make the program actually think it intersected a little behind or ahead of that point, so we could very easily end up with the wrong value, most sources I've found so far seem to avoid using this type of curve, but if we find one, maybe we could just split it into two segments, one where it goes purely upward with respect to T and the other. where it goes purely downwards, doing so should be reasonably straightforward.

First of all, we can calculate the inflection point by simply setting the gradient Y to zero and then solving for T from which we can, of course, calculate the actual point and then say we want to build. This segment here that goes from p 0 to the inflection point obviously we are going to place the two end points of the new curve at p 0 and the inflection point, but the big question is where does the new point P1 go well? We need the gradient at p 0 to Still Point towards point P1 of the original curve to maintain the same shape, which means that our new point P1 is bound to be somewhere along this line here and where exactly is where forms a horizontal line with the Inflection point since of course the gradient there by definition is zero in the y-AIS so I've been writing some code to do these calculations automatically and it's a great feeling figuring out the math of something and then just have it.

It worked perfectly the first time and that's why I was a little disappointed when this happened anyway turns out I just forgot some important parentheses and while we're here let's take a quick look at the math which is super simple we just say that if you start at p 0 and move along the gradient vector of the original curve at p 0 for an unknown distance. Eventually we will reach a point with a Y value equal to the inflection point. Then we can rearrange it to solve for the unknown distance. which then allows us to calculate our new point P1 and exactly the same thing happens with the other segment of course, and now we can see that this is working, so it can be done as a preprocessing step on the glyph outlines, although as I said plus the sources I've tried actually keep the P1 points strictly between p 0 and P2, so it's generally 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 positions of p 0. and P2, hopefully this will improve accuracy a bit and running the test we now have a miss count of 755. I'm a little disappointed, but anyway progress is good, let's move on. The next bug on our list is this one where this Ray is. somehow managing to avoid both segments at their meeting point. I think what is happening is that the roots we are calculating there are slightly outside the valid limits due to precision errors of course, so I just added a little fudge factor to catch those cases and run the tests again, now just There are 404 remaining failures.

Well, here is the next case on the list and in this one the lightning should reach thesegment six, but after some debugging I discovered that it's actually just missing. This is because it will not believe these precision errors again and will instead only reach segment 7, so in our quadratic formula, missing the curve means that the descriptive discriminant is negative, so let's try to allow it to be a tiny bit negative to catch those cases and then just clamp it to zero in our actual calculation, this may seem pretty dodgy, but remember we're jumping curves that are completely above or below the ray, so I don't think it actually introduces many false positives.

I hope they reduce. However, there are false negatives, so let's do the test one more time and that brought us to only 10 failed cases, which is very exciting. Be careful not to fall off your seat, so let's take a look at what's next right. our array is hitting the tip of these two segments here and this looks a lot like a problem we covered earlier. In fact, remember this one where the beam also hit the tip of two segments and we told you to prefer the one with your P1. Point further to the left, the idea is that a ray traveling to the right should hit that segment first, but now we have a limiting case where point P1 of the segment we want the ray to hit is actually no further left than the other segment, so I set up this little test area with different Curves settings to try to find a more solid approach and after playing around a bit I think I have something that will work to get clear on what we want.

We are trying to achieve this in case it didn't make sense before, the problem is that if our Ray comes in and hits the tip of these two segments, we don't get a clear answer as to which curve it hit first, but intuitively it does. should be the blue curve, since if the ray was a little bit lower then it would clearly hit the blue curve first, so my thinking now is that we will consider the gradients of the two curves at our point of intersection and then Imagine a type of curvature clockwise from the Ray and seeing which Gradient Vector we run into first, which of the curves that gradient belongs to is the curve we want, by the way, if the curves originate from above the ray instead from beneath it, as in this case.

Here the idea still works the same, only we imagine that we turn counterclockwise and here is that idea expressed in code, so when we run the test again, we finally reach zero errors, which makes me very happy see that you obviously get performance. Just because it's in testing doesn't mean it's perfect, in fact I'd be surprised if there weren't still plenty of edge cases of Ling in the shadows, but we've definitely come a long way in destroying those artifacts that were quite prevalent before, at least , from my. I've been zooming and scrolling through this text for quite some time and haven't noticed any yet.

However, I ran into a more fundamental problem while trying out some new fonts and this arises when we have overlapping shapes like this particular letter K here. We are using the closest segment to determine if we are inside or outside the glyph, but from here, for example, the Lightning Bolt would hit this segment as the closest segment, which incorrectly tells us that we are outside the glyph, so if we tried. Fortunately, rendering it looks like this, although after some reflection I realized that we can modify the algorithm slightly to keep track of the closest distance to the exit of whatever shape we are in, as well as to the exit of any hole we are in. could be inside and then by comparing those distances we can determine if our point is inside the glyph or not, so it looks like our rendering now works fine, however it definitely needs some anti-aliasing as I mentioned before.

Currently, each pixel decides what color to display based on whether a single point at its center is inside the glyph or the notch, so the easiest improvement I can think of would be to go from a single point to decide the pixel's fate. to perhaps a grid of nine points, each of which contributes a little to the final color of the pixel, we could even get sophisticated and consider the fact that each pixel is, of course, made up of a red, green and blue component, so here for example, instead of just dimming all three colors evenly because only six of the nine dots are inside the glyph, we could say that since red and green are inside the glyph, we'll just brighten those two completely emitting yellow and leaving blue off.

This is a technique called subpixel smoothing and we can see it in action if we look very closely at the text in my code editor, for example, where along the left edge of the H, for example, we can notice how Mainly just the parts green and blue of the pixel are illuminated, while along the right edge here it appears that only the red part of the pixel is illuminated, so this is a clever way to essentially triple the horizontal resolution of the display. However, there are some subtleties in terms of filtering the results so that the color fringing isn't too harsh and I suppose detecting and handling the possibility of different pixel layouts on different displays, so I'm going to leave this idea of ​​subpixels to the future. experiments, but here's our super simple anti-aliasing today: we simply loop through a 3X3 grid and calculate the different sample points within the pixel.

By the way, this is possible thanks to this derived function that tells us how much the position value changes between the current one. pixel we are working on and its next door neighbor; in other words, it's the size of the pixel in our glyph coordinate space, so we simply add one for each of these points that is inside the glyph and then divide by nine to get the average of those samples and now, in Instead of being all jagged, our edges smooth out nicely. This is at very high magnification of course, just to better show the effect, it's obviously much more subtle in reality and although I'm not sure how well. will appear in the video, it definitely makes a big difference in the flow of the text;

However, running our algorithm nine times for each pixel seems a bit exorbitant, so I've been experimenting with a small improvement where we actually just run it. three times along the vertical axis and now add this horizontal coverage value basically instead of just returning a Bool to determine if the point is inside the glyph or not. I slightly modified our function to return a coverage value between 0 and 1, this is calculated by adding the distance to the closest curve segment on either side of the input point, both subject to half a pixel's width and then dividing by the width of the pixel, this means that if the pixel is far from any Edge then it will get a value of one meaning it is completely inside the glyph or inverted to zero if we are actually outside the glyph and for pixels getting closer of an edge, that value will get closer and closer to 0.5, so you get a smooth transition between 0 and one along the edge here which is in action with our test text above and if we expand this a little bit we can see the smoothing looks pretty decent.

Although I think that maybe it's a bit strange implementation. I later found this article that talks about sending the Rays in different directions to estimate what fraction of this small circle is covered by the glyph, which sounds a bit more flexible and precise, so I might use it in the future, in any case, that? What I'd like to do now is run a super quick performance test, so I'll paste the entire 12,000w script I have for this video up to the input and try to run it fine, taking a look at the stats. It looks like the text takes about 0.2 milliseconds to render, although I'm honestly not sure how to profile it correctly.

In this sort of thing performance falls off a cliff and surprisingly for very complex fonts here is a random font I found with a lot of little Wiggly details in the glyphs, this G for example contains 440 Bézier curves which gives us has taken from about 800 frames per second, dropping to about 150, there are ways we could optimize this through the obvious idea of ​​taking into account splitting each glyph into multiple bands so that each pixel only has to test the beia segments within of the band it's in, plus each glyph is currently represented as a quad, which is nice and simple, but in many cases it can leave quite a bit of empty space for which the Shader still needs to crunch the numbers with a bit of tweaking. preprocessing, although we could build much tighter tail meshes. specifically for each individual glyph, it is much more challenging than improving performance.

I suspect it is now improving the readability of text at small sizes. At least it's very easy to read on my screen, but if I zoom out a little further it really starts to work. downhill pretty quickly, let me zoom in on this view so we can see the problem better and take this word here for example, we can see how some parts look nice and bright, while other parts are much dimmer because maybe they fall so uncomfortable between two pixels during For example, both pixels end up being great. If I rotate the camera slightly, we can see how the readability of each letter changes as its alignment with the pixels changes and I think that seems like a difficult thing to fix.

I'd need to delve into that scary biting code interpreter topic I was so happy to skip at the beginning, so that's definitely a problem for some other day, what still bothers me a little are the downsides I showed earlier to our rendering approach nearest curve, i.e. fail. If the Contour has the wrong curvature direction and is very sensitive to self-intersections, then I decided to take everything I learned from that artifact hunting process and basically start from scratch with the counting method again. I won't bore you with another review. -Blow counts, but armed with a much better understanding of the problem, I was now able to get it working quickly without any problems in the test search.

A lot of these same ideas are still there and the new core addition is super simple. Actually just a small detail in the way curves are skipped, which actually helped enormously with the double counting problems that plagued us previously, basically when testing whether all points on a curve are above or below of the ray we need to decide if we want to include zero in the test, which means omitting the curve even if one of the points is at precisely the same height as the ray, if we don't omit those cases we will have problems with double counting in the meeting point of two curves like We have seen that, if we omit them, we essentially create small holes through which lightning can sneak into those meeting points.

Of course, we could try to solve that problem by including only zero for the P2 points, maybe since if we imagine a Contour like this, a ray that lines up perfectly at the meeting point will only cross one of the curves. However, the problem is that if the Contour looks like this, suddenly the ray no longer crosses the Contour, but just scrapes past. That's why we didn't want to touch either or both of the curves so that it wouldn't affect the final result. I think it was this kind of problem that led me to abandon the counting method originally, but now that we've processed the curves to ensure that they can only go strictly up or strictly down, it suddenly doesn't seem so important anymore, the problem it just happens when the curves go in opposite directions, one up and one down, and this is how we can handle this in the code is simply check the direction of the current curve and for One Direction we include zero only for points p 0 and for the other direction we include zero only for points P2 and that seems to work very well, so now that we are using the counting method again, we can see that the incorrectly wound J is represented correctly and the small self-intersection no longer causes any visible problems .

I was very happy with this, but the victory was short-lived because I later realized that this approach actually fails. The case of overlapping shapes again now we can fix this with a slight adjustment where we say that every time the ray crosses a downward curve, meaning it is leaving the current shape, we add one to this counter and otherwise we subtract one if it is entering the shape. if the ray came out of more shapes than it came in, it must have started within one shape. This is essentially the same idea as the original counting method, but it should be able to handle overlapping shapes, by the way, this can also be extended nicely to work with our current approach to smoothing like this is still just adding or subtracting one as before , unless the distance to the intersection isbecome extremely small like inside the current pixel and in that case we are now adding or subtracting a fractional amount, which means that in the end we again get our nice smooth blend of 0 to one along the edge of the glyph, this idea comes from that which I mentioned earlier when we were first implementing smoothing as we can see that this small adjustment has solved the overlapping shape issue although unfortunately I break the problematic J again which is quite annoying, on the other hand the intersection looks better than ever, so I'd say we can count this as a half win, at least I tried a couple different things to get the unstable J. to render correctly as it's a recurring issue I've seen in a handful of sources at the moment, but none of my attempts came particularly close to solving this one, perhaps the least close of all, so perhaps we could try to automatically detect Bad outlines and fix them by importing the source, but I need to stop worrying about these little details for now, after all this was supposed to be a quick experiment and I may have gotten a little lost in the weeds along the way, so sorry anyway after all.

I definitely feel like I've gained a much greater appreciation for the complexities of representing text. Here's one last test with our latest approach on a large wall of text with several different fonts and I think I'm pretty happy with how it looks. To end the day at least for now, so to finish, I've been having a little fun in the Vertex Shader here making the letters shake and spin to say goodbye and thanks for watching. I hope you've enjoyed following this little trip down the surprisingly deep rabbit hole of text rendering and if you have any ideas on how the current implementation could be improved I'd of course love to hear them, that's all for now, until next time, greetings.