Software Development

So we set up DirectX or OpenGL to draw a 256x256 virtual texture on screen that has a one to one pixel to texel correspondence. This means that if you were to draw a real texture on screen, each texel would appear as a pixel. No scaling at all.

Now we can use a pixel shader. The pixel shader needs to know the radius though. So you can pass this either as a pixel shader constant or through one of the other texture unit's coordinates (as x,y or z values). Passing it as a texture coordinate is encouraged on older video cards as it hold higher precision than pixel shader constants. IOW, pass it as a vertex shader constant which will then pass it on as a texture coordinate (say Texture #2).

How do we calculate the radius? Well, if we have 120 for radius, then in texel space, it's simply 120/256 or 0.46875.

So we can simply calculate the following, assuming the z coordinate is always reset to zero or not used at all which it what we assume here:

First, we need coordinates that go -0.5 to 0 and back up to 0.5 instead of [0,1].

tex0=tex0-0.5;

Now we can compare the radius to the calculated distance of the texel to the center of the virtual texture.

alpha = radius-sqrt(dot(tex0,tex0));

// Or

alpha = radius-sqrt(tex0.x*tex0.x+tex0.y*tex0.y);

If the alpha is negative, it should not be drawn. So we could do something like this.

alpha = (alpha)?1:0

Then simply output the color of your choice with the calculated alpha, given through a constant, texture coordinate, or given by the vertex shader through the diffuse color v0, or whatever else. Make sure you have the proper blending settings so that alpha will be taken into account. You may also set up an alpha test so that an alpha of zero is not drawn.

On older cards, you have a problem. There is no such thing as a square root in pixel shaders. But you don't need the square root. You can work with squares instead. So send both the radius and radius2 where that last one will be the square of the radius. In fact, newer cards could use this as well as it's two operations less.

alpha = radius2-dot(tex0,tex0);
alpha = (alpha)?1:0

// OR
alpha = radius2-dot(tex0,tex0);
clip(alpha)
return myRGBColor;

Before setting alpha to 1 or 0, you could also use clip() or texkill instruction. That way, you don't even need the alpha value as shown.

Ok, so far, this is all boring. We draw a circle, but it's all blocky. How do we get it to be antialiased? The first thing is to add half a pixel to the radius to allow for antialiased pixels.

We still use the same technique for clipping pixels outside of the circle. But now we need a way to calculate the correct alpha value on the border of the circle. How is this done? Well, it's actually easy with the use of saturate.

For this to work, we need the actual distance. We cannot use the square of the radius. So we need to use the square root function within the pixel shader. If you have pixel shader 1.4, you can create a lookup table with a texture of V16U16. You need at least 12 bits of precision and this is the only texture available that allows for it. Use it. These are signed values, but we only use positive ones. So make sure you scale to 32767 and not 65535. Here is some code to fill out a 1 by width texture. Width should be any power of two that is larger than the biggest circle you will ever draw. Hopefully, you can build a width bigger than your screen size. Here's some code for ps 1.4 to fill in the data for this texture. The cool thing is that texture space is always between 0 and 1. Texture values are always automatically converted to that range, so this works out well.

  // tex is a container that holds the D3D texture interface and the width and height.
  D3DLOCKED_RECT r;
  if (D3D_OK!=tex->pRenderTexture->LockRect(0,&r,NULL,D3DLOCK_DISCARD)) 
    return; // ERROR

  unsigned int *t = (unsigned int*)r.pBits;
  for(int i=0;i<tex->Width;i++)
  {
    double n = (double)i;
    n+=0.5;
    n/=(double)tex->Width;
    n = sqrt(n)*32767.0;
    *t++=(int)n;
  }
  tex->pRenderTexture->UnlockRect(0);

Hook this texture up to a free texture unit and now your pixel shader can use a dependent read to get the square root. Make sure the original value is in the x coordinate. Also make sure you use POINT filtering. LINEAR produces terrible results because there isn't enough precision, though it works fantastic on newer cards and on the reference driver.

Ok, so we calculated the distance of our texel to the center of the virtual texture. And we have a method for getting the square root on both old and new video cards. Great! We then take the original radius (NOT squared) and subtract the square root we just calculated.

What this does is tell us how far away we are from the edge of the circle, but from the inside. The further we are away from the edge, the higher the value and the closer we are to the center of the circle. Negative values don't get drawn, so that part is taken care of.

What we want now is a way to have all texels except for the ones less than ONE PIXEL away from the circle border have a value of 1.0 (or 255 in RGB). How do we do this? It's actually quite simple. But the reason behind it is a little difficult to explain.

In the scale of [0,1] that pixel shaders use, what is the width of ONE PIXEL on screen? Well, it depends on our virtual texture size. If we used a 256x256 virtual texture, then one pixel is 1/256 in texture space. If we had used a 64x64 (for circles with a radius of less than 32), one pixel is 1/64 in texture space.

Why is this important? Because that is the size around our circle that will be antialiased. One pixel is always the antialiasing width. AND!!! We know what our distance is from the edge of our circle. Since everything less than one pixel away will have a value less than 1/256, we can simply multiply by 256 to get a proper alpha channel that will end up being between 0 and 1. Everything that is further away than 1 pixel (or 1/256 in texel space) will produce a result above 1. We saturate those values to keep them at 1. Heck, we can even saturate the distance beforehand to get negative values to 0 (and thus produce an alpha value of 0 which means those pixels beyond the circle won't be drawn).

So simply multiply the distance (called alpha above) by your virtual texture size while saturating.

alpha = saturate(alpha*textureWidth);

Again, you need to find a way to send textureWidth to the pixel shader. Use whatever method you think is fine. On older video cards, there is a problem. Constants can only store values between -1 and +1. So use texture coordinates. Again, there is a problem. While texture coordinates can hold large values, pixel shader registers can only hold values -4 to +4. The specs say -8 to +8, but it's not actually 8. It's more like 7.999999999999. It simply sets all bits, but will give artifacts if you try to use this as the number 8.

There are two ways of solving this problem. Either produce a pixel shader for each virtual texture size and use of several _x8 modifiers along with other math and source modifiers (like _x2) to produce the correct result. Or send a total of 5 (or 6) values through two texture registers (using x,y,z coordinates). Each of those should have a value of 1, 2 or 4 so that if you were to multiply them all together, you would get the texture size. Multiply each one with alpha while saturating the result. 4^6 = 4096 which is bigger than the largest available texture size. So you're all set to go. Do NOT multiply them together inside the pixel shader. Each one must be multiplied with the alpha value in turn. If you multiply 4*4 before multiplying with the alpha, you'll get 16. But 16 can't be stored by any registers. So you're gonna get incorrect results. Always multiply each value with the alpha one value at a time while saturating each time as well.

This produces a few problems. Larger circles will look worse than smaller ones. Here's why. You have 12 bits of precision with pixelshader 1.4. When you use a virtual texture size of 256 and you multiply by 256, the first 8 bits will automatically be zero since the distance is less than 1/256. That leaves the 4 lower bits for specifying the alpha value. You'll get 16 different values. When you go to virtual texture sizes of 512, you will have 8 values for antialised pixels. Luckily, you probably won't be drawing circles that big.

One way to double the number of alpha values is from the fact that we are testing radius distances. The radius is always HALF our texture size. So we can double our radius and pass that to our pixel shader. This means we only need to multiply by 128 (since we already doubled once). IOW, the pixel shader only needs to multiply by half the texture size afterwards. This will give you one extra bit of precision on older video cards and double the number of values for antialised pixels. Now you have 32 different alpha values (instead of 16) for circles up to 256x256 in total size. This gives quite good results. Not as good as floating point precision, but you'd have to look at individual pixels side by side to notice the difference. And smaller circles will look better and better. Note that NONE of the other calculations change. And as a side effect, since we're using the full range for square roots (up to 1 instead of up to 0.5), we get better results here too.

To sum up, you need to pass the following information to the pixel shader:
(Note that the 0.5 added to the radius is to allow an extra half pixel for antialiasing).

1. R = 2*(radius+0.5)
2. R2 = 4*(radius+0.5)*(radius+0.5)
3. tSize = textureSize/2
4. color = RGB value for circle

float2 UV = (tex0-0.5)*2;  
float dotUV = dot(UV,UV);
float dist2 = R2 - dotUV;
clip(dist2);

float dist = R2 - sqrt(dotUV);
float alpha = saturate(dist*tSize);
color.a *= alpha;
return color;

For PS 1.4, the first two lines can be done with the following code if you send 0.5 as the z cordinate in texture unit #0:

dp3 r0.x, r0_bx2, r0_bx2

And the sqrt() would a dependent read on a texture unit that holds precalculated square roots values.

As you can see, the actual code is rather simple. But getting there and understanding why this works takes a little doing.

So new or old video cards can draw circles on the fly. I'm trying to create a similar algorithm for drawing ellipses, but the computations are rather involved and require multiple square roots divided by each other. Precision problems are a real pain, but I think it may be doable. The real problem with existing algorithms is that the antialiasing is more than a pixel wide on the sides. That's because people try to use the x²/a²+y²/b² = 1 equation. If it's less than 1, then you're within the ellipse. As with the circle, you can use this for clipping. But it's useless for antialiasing because the x and y coordinates are scaled differently. My algorithm here fixes this, but is more complicated.

I can now basically draw any shape as long as I have an algorithm for calculating the distance to the border of the shape. With the circle, I also have code that can stroke the edge of the circle. For this, you simply take the width of the outline subtracted by the the absolute value of distance from the border. You then multiply that value by half the texture size. So by adding a single line of code to your pixel shader, you can get fully antialiased outline circle drawing. Oh, also make sure the distance to the border has not been saturated before doing the above calculation since you need the negative values. Your texture size also needs to be wider (2*(radius+0.5)+outlineWidth).

IOW, take the maximum distance allowed, subtract from it the calculated distance to the center of your shape for that texel and multiply (and saturate) by the size of your virtual texture. It's the same algorithm for drawing ANY shape.

All the following algorithms assume that you've scaled your texel coordinates to the range of [-0.5,+0.5] instead of the default [0,1] which can be accomplished by subtracting 0.5 from both coordinates.

For a rectangle, it's

float2 dist;
dist.x = rect.width/2-abs(texel.x)
dist.y = rect.height/2-abs(texel.y)
clip(dist)

dist.x = saturate(dist.x*textureWidth);
dist.y = saturate(dist.y*textureHeight);
color.a = saturate(color.a*saturate(dist.x*dist.y));

For a circle, it's

float dist = radius - sqrt(dot(texel,texel));
clip(dist);
dist = saturate(dist*textureWidth);
color.a = saturate(color.a*dist);

For a circle outline, (requires square virtual texture)

float dist = outlineWidth - abs(radius - sqrt(dot(texel,texel)));
clip(dist);
dist = saturate(dist*textureWidth);
color.a = saturate(color.a*dist);

For an ellipse, it's

float2 texel2 = texel;
texel2.x*=b;
texel2.y*=a;
float scale = a*b/sqrt(dot(texel2,texel2));

float2 border = abs(texel)*scale;
float2 diff = texel-border;

float dist = sqrt(dot(diff,diff));

dist = saturate(dist*textureWidth);
color.a = saturate(color.a*dist);

The ellipse algorithm doesn't compute the 100% pixel perfect antialised pixel value, but I don't think there's any way to tell by just looking at what it draws on screen. The distance algorithm is based on the center of the ellipse. Of course, on the left and right of the ellipse, there are parts where the normal to the tangent of the ellipse border doesn't point to the center of the ellipse. So whatever the angle is off will produce slight errors, but it's not something that you can notice by eye.

The actual error is distance to center subtracted by distance to x-axis. That error needs to be scaled down by the textureSize. Since the error can never be larger than the texture size, the error is in the alpha value only along the border. So an alpha value might be a shade slightly lighter than it should be. But whatever. No one will ever see that. What it does mean is that I can't use this algorithm for drawing the outline of an ellipse because the outline will appear thinner in some places where the normal doesn't point to the center. The bigger the angle difference, the thinner the line will be. I'll see if I can't find another algorithm to fix this issue.

I really wish I could get an algorithm for cubic splines, but from what I've seen, it looks really complicated.

Update:

Screenshot! (Click on image for larger version)
This is on an ATI 9200SE (PS 1.4) on my old test box.
Screenshots for newer cards available upon request (the only difference is smoother antialiasing since they have more precision available).