imconfusedwithallofthis-blog

[imconfusedwithallofthis-blog]

Math is Hard

Update on my odissey of trying to improve on vector rendering techniques using conic intersections, and I've stumbled on a problem that I was not ready for... math is fucking hard >.<.

I mean, lets go back... my Idea seemed solid in my head, in my previous post I came to a conclusion that the default SDF font rendering technique was similar to describing a curve Ax + Bxy +Cy +D = 0, my idea was precalculating those parameters for each pixel so we no longer needed to use linear interpolation, and then we could edit te final result being mindifull and precise about how exacly it would scale. Since I would already compute the valuer per pixel i could just go the extra mile and do the full conic formula Ax^2 + Bxy +Cy^2 +Dx + Ey + F = 0.

So i got a few tests going, created a shader in Godot, to get subpixel coordinates and caculate conic values for each pixel.

The problem is that dealing with 6 abstract parameters per pixel is really hard, so i came up with the idea of doing a 3d representation of the conic and the plane. So we would manipulate directly the cone position, it would be something like this:

I would define a cone by a point P, a direction V and a linear coefficient a.

So here i go puting my sings on the paper and I quickly notice that I'm gonna fill alots of sheets to get to an answer and looking at my track record i'll surelly get something wrong .

So I got searching for something to manage those formulas for me.

Geogebra was kinda cool, but it fell short of allowing me to manipulate the formulas in the way that i wanted, i tried a few other scientific calculators.

I didn't like symbolab, somehow it felt too complicated and too simple, kind like it would be amazing if I was doing homework or had ne of the specific kind of problems it is designed to deal with.

In a fit of despair I tryied chatGPT, and I had the classic chatGPT experience, at the start i got amazed with how it gave me a result that looked like what i was expecting, but then I noticed that it halucinated new terms in my formula, and even when i got rid of those I had absolutelly no way to validate the result, and in the end I would have to redo all the work =.= , but yeah, I'm sure I'll find a use for it in a few years.

The one that I felt that was actually usefull was something called SageMath, it seems to be kind of a wrapper that unify dozens of python math librarires it gave me a way to decrlare variables, execute vector math with them, and manipulate the resulting expressions.

The result made me happy that i didn't follow trough with the plan of doing it all by hand. well, Lat this stage i still had to paste the expression to a text editor, separate the elments tha depend on x^2, xy, y^2,x, y, and 1, past it back to SageMath to simplify, then I could hack a small editor in Godot and:

well, i still have some tweaking to do to make the coordinate system play well with the one in godot, but a big part of the math is solved. well, if it usefull for anyone I'll link a pastebin with the resulting formula

hopefully I will keep making progress and this can become a tool for developers at some point :)

[imconfusedwithallofthis-blog]

Just some considerations on the limitations of alpha testing a texture that is using bilinear interpolation.

Expanding the formula for the sub sampling what we get is something of the form

F(x,y) = a + bx + cy + dxy

Visualizing the formula in 3d helped me a lot to get that the result of bilinear interpolation will either be a plane or a saddle that is aligned to the xy diagonal.

And considering the alpha testing we are actuality dealing with the inequality

a + bx + cy + dxy > 0

So the implication for me in the context is SDF fonts and textures is that the shapes between thaw sample points only have 2 possible configurations.

The shape of the border between sample points will either be a straight line in any orientation or a section of a rectangular hyperbole.

Those are the reason why SDF fonts don’t generate crisp corners when drawing polígonos, also we can’t orient the hyperbole curvature horizontally or vertically, only diagonally.

One thing that would be nice to explore is, instead of generating the coefficients implicitly from the corner points doing 4 texture samples, we could encode them directly in the rbga vales for each pixel, so instead of doing 4 samples per pixel on the screen, we could do only one.

This would add a small step of preprocessing but since SDF are already preprocessed the conversion should be pretty straightforward

[imconfusedwithallofthis-blog]

Hey! I'm back to talk a bit more about alpha tested image rendering!

This is a continuation to my previous post, so if things are not making any sense you can go back to that one and take a look ;)

Just a little recap about my arbitrary goals, I want to draw a circle on the screen (and maybe generalize for more shapes in the future!) using as base a small texture like 16x16 to a bigger size, lets say 256x256.

the setup we ended last time with was:

generate a 16x16 texture that is: - black if the center of the pixel is inside the circle - white if the center is outside

magnify the texture using bilinear scalling (interpolating the inbetween pixels with the nearest 4 linearly)

alpha testing the resulting image to get sharp corners instead if blurry areas

The astute among you may notice that the final image does not look like a circle at all, I mean, it is less blocky, and less blurry, so an improvment for sure, but we can do better.

The key thing to notice is that by applying those steps to the image to upscale it, basically we redefined how we are describing our shape, instead of a pixel directly describing the color we want to paint, we end up with something more like describing a shape by a math equation, wherever this math equation is bigger then 0.5 we are inside our shape, and wherever it is smaller then 0.5 we are outside our shape

Noticing, this we may do some cool things with the first step, If we know that what we care with the image is the position of the resulting 0.5 (grey) contour, we can paint our initial pixels in a way so that when we scale our image with the bilinear interpolation we get an isoline that better represents a circle

One method that is very common is to paint each pixel in the original image with the distance to the nearest point in the shape.

there is just a few problems that we have two big problems with using this:

The distance defines our shape as the exact point where d = 0, and since we are sampling points and linearly interpolating we end in the border interpolating something between 0.02 and 0.03, so we are never getting a perfect zero, maybe the best we can do is consider as zero anything smaller than some arbitrary epsilon, and end up wiht something like this for the border:

We also cannot easilly differentiate what is the inside and outside of our shape, in our previous technique we could just check if the value in our scalled image was bigger or smaller than 0.5

there is a technique that kinda solves those two problems, and it is so useful in so manu areas that it gets its own name it is Signed Distance Fields (or simply SDF)

the idea is that we do the same thing that we did before, but now, if the point that we are looking at is inside the shape we say that the distance is negative, so now:

Near two points in the border we are interpolating between something like 0.02 and -0.03 so it clearly will always passes trough 0

to check if we are inside or outside our image we can just check the sign!

well, let the result speak for itself (in this case, i draw positive values as shades of purple, and negative as green)

and now, our border, is way better defined as well!

Nice! now our circle is looking way more circular now, and we are still only using our old 16x16 texture!!

Well, actually there are still a few small things that we can improve, the first thing is that our texture color values only go from 0 to 1, so we had to cheat a little using an rgb texture so we use different colors for positive and negative values (we also, also divide the distance by the size of the image so we never actually get smaller than 0 or bigger than 1), this also makes so the bilinear interpolation is a little funky, since it interpolates the channels separetly.

So what actually gets used in games and other media, where this application makes sense is a Pseudo Signed Distance Field, we basically observe that:

we dont care about having precision far from the area where we have borders, so we can clamp our SDF between -2 and 2 pixels from the border for example

we also, dont need the contour to be specifically 0, if we go back to before, and set the border with 0.5 as a value, we can transpose and scale our values from -2 and 2 to to 0 and 1 by dividing by 4 and adding 0.5.

what we get at the end of this is a single image 16x16 image that we can apply the exact same steps that we were doing before, so basically no new "runtime" computation needed and now we get a way smoother circle:

That is a great result, but this is not the end of the road for our technique!

For now all I did was describe techniques that are fairly well known

there are a lot of things to understand yet.

and if we understant better those things maybe we can push the technique forward and make improvements in quality and performance, and maybe get smaller, better looking games ;)

some of the things that I've been trying to understand are:

why specifically did we use the distance field as the underlying way to to encode our shape

what are its limitations

is it the best we can do?

how much can we zoom before we start getting visual glitches?

can we get similar results in a shader with less texture samples?

can we get better results with more?

what are the implications of interpolating with bicubic or biquadratic?

and if we dont use a single value for our isosuface we oculd maybe get lines thinner than a pixel from the original image!

how can we best decide what is the best texture size to encode our original image.

This seems like such a simple sequence of steps, but there is so much more that we can do and so much further that we can push it!

[imconfusedwithallofthis-blog]

Smooth upscaling with alphatesting

OK lets do a quick review of using signed distances fields as textures, starting with alpha testing:

ok, lets say we want to draw a circle and we only have a 16x16 texture available to us, one thiong that we can do, is just to define our ciclce (with a radius and a center) and color each pixel of our texture with this rule:

if the sample point is inside a circle, we paint the pixel as black and if it is outside we paint it white, and to display we just map the pixels of our texture to the screen and we end up with something like this:

I mean, it is a circle allright, but if we want it to occupy a larger space on our screen we have have to make some decisions, I mean, we are sure about the color of those 256 (16*16) points in our texture, but if we want to make it occupy the space of 256x256 suddenly we have to come up a color for 65280 pixels points in our screen that are currently undefined!

One way to do is to stretch our original texture, and basicallly we just look at each point in our screen to look at the point in the texture thàt woud be nearest to it, and color it with the same color, this way of stretching images in computer graphicss has the apt name of "nearest neightbor filtering" and now our very small circle texture can be seen in a new 256 x 256 glory

what, it is not a circle anymore? hmmm, you are right, we have a lot of area to paint and if we just take the closest sample point we end up with this blocky result for our image

but maybe there is something better that we can do, there is this cool technique, called bilinear interpolation! basically when we are trying to fill an area between 4 points, instead of simply choosing the closest one, we do a kind of weighted avare between the points, in a way that the closers one has a higher impact in the color of the specific point, but all of the 4 samples contribute to its color.

it sure is less blocky, and look, how cool , a few of the areas even have some "roundness" between them even if they ends up being kinda blurry, but i guess that is fair, we dont have a lot of information to go on, lets try to see the whole picture again in a 256x256 area of our screens

Hey it is... better? i guess... i dont know, i mean, sure it feels a little "rounder" but now i feel like searching for my glasses why is it not simple to draw a simple circle, do we really need a super high resolution image as source if we want to have nicelly defined curves and edges for a simple circle... I refuse to believe that. ok lets force our circle back to only two colors this way we have a defined shape and not a blurry mess, we can do something like... pump the "contrast" way up so if something is dark grey, lets change it to a darker grey, and light greyh, to lighter, if we do this enought we should end up again with a image that is just black or white:

wait, that is actually pretty cool we end up with a much more orgsanic shape than before, and it is actually a shape and not a blurry mess! look:

I mean, we are still a little distant from our perfect circle with a small texture, but this technique sure is cool, this is called alpha testing, in this case our shaped is not defined only by the pixel values, but by the function that we use to calculate our "new pixels", in particular, the contour is preciselly where our image is that perfect middle grey, in this sence there is a huge change in the way we define our shape, not by explicit pixels, but by implicit parameters to a function, and maybe there is some way to manipulate those function parameter so we can get closer again to a perfect circle drawn with our humble 16x16 tecture! and maybe much more!!!!

[imconfusedwithallofthis-blog]

I sometimes think about that like why did I not finish one of my various personal projects and released it as an indie game/ framework/tool etc, and I noticed that I feel very motivated by a core problem in each project and once I solve (or sufficiently understand) the hard part I kinda lose the motivation to continue with it.

After suffering a lot with it I just decided that I really like solving experimenting with some very specific computational problems that interest me and I’m ok with it.

I decided to stop comparing myself with “cases of success” of the open source/indie dev scene and decided that I would just have fun with those things that I like to know more about.

I don’t know if your frustration comes from the same place that mine did, but if it does, know that it is ok to do what you want because you want it without the feeling that you need to justify it with some specific result.

I dunno, programming for 6 years without even a prototype finished can burn a little bit.

I'm tired of learning! I wanna MAKE. And I want the enthusiasm for it to last.

[imconfusedwithallofthis-blog]

Oh I think i saw this presentation on youtube years ago! I did not play the game, but the technical problems solved are amazing. but you are right! i was completelly vage whit what I ment about SDF textures, what i was in fact refering to is a 2D application of signed distance fields to do alpha tested magnification that is described in this valve paper. and the evolution of the technique that is the multichannel sdf techique where we do intersection of areas using the different image color channels to get sharp corners. it is just that these techniques for alpha testing became known as SDF font the thing that i ment by mathematically solving that, if we have the upscalling sampling formula, linear or cubic for example, at the time we are creating the texture, we don have to guess that creating a distance field will place the best cutoff point that represent the original vectore image. in a sence what I'm proposing is using the same rendering technique, or apply minor variaitons to it, but changing how we generate the original texture.

Since I started studying SDF textures it kept blowing my mind, the idea to use texture data to keep something other then color data it genial

And it is so underutilized too, I mean, we use it for text sure, but add a little color information and overlay a few textures and we could have such a fast way to render vector graphics for games, every time I see a 2k texture for a vector image that probably has less than 1000 points I suffer a little inside.

And another thing is that it looks that the technology barely changed since it was published by Valve in 2007 and there is so much to question why do we calculate the distance to get a smooth curve why not try to solve mathematically for the shape of the curve, why not use a 3d texture and do some fluid animations? There is much potential with it

So I started a series of studies on where we can take the technology and hopefully will post some iterations here in the future!

[imconfusedwithallofthis-blog]

Since I started studying SDF textures it kept blowing my mind, the idea to use texture data to keep something other then color data it genial

And it is so underutilized too, I mean, we use it for text sure, but add a little color information and overlay a few textures and we could have such a fast way to render vector graphics for games, every time I see a 2k texture for a vector image that probably has less than 1000 points I suffer a little inside.

And another thing is that it looks that the technology barely changed since it was published by Valve in 2007 and there is so much to question why do we calculate the distance to get a smooth curve why not try to solve mathematically for the shape of the curve, why not use a 3d texture and do some fluid animations? There is much potential with it

So I started a series of studies on where we can take the technology and hopefully will post some iterations here in the future!