TeamDS
Signed Distance Field Generator
Team Members
- Dawood Shirzada - Developer
Progress
Assignment 1
What is Signed Distance Field?
Signed Distance Field also know as SDF, is a technique developed by Valve company that uses low resolution textures to display extremely high resolution looking fonts and decals. Valve used SDF in their game engines that run such games as Half-Life 2, Counter-Strike 2 and etc. SDF is so effective that no matter how many times the font or decal is zoomed in, it will always look crisp and sharp while using very small textures. This allows fonts and decals in game to have much higher quality with low memory compare to using regular high resolution textures.
For more detailed information please read Valve's publication: http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf
Examples from Valve
Examples in action
https://youtu.be/CGZRHJvJYIg?t=40
How does Signed Distance Field work?
SDF ONLY works with monochromatic images such as decals and fonts. SDF takes the original texture as an input and creates a SDF version of that texture and saves it in an image format.
SDF version is actually much different than the original image. the SDF version no longer stores the pixel color intensity like normal images do, but instead stores the distance to nearest opposite color. For example, since monochromatic images only have black and white, for every white pixel, you look for the nearest black pixel and stores the distance between the two and vice versa.
To read the SDF version of image, we will need to use a custom shader that can understand the SDF version. With help of custom shaders, we can do many more effects such as edge glows, drop shadows, soft edges and etc. All these effects at virtually no additional rendering costs. SDF is a huge win when it comes to gaming performance!
How to convert image to SDF version?
It turns out to convert a image to SDF, it is very computationally expensive. There are however, many methods that approximates and are relatively fast, but the Brute-Force method produces the most accurate result and it is the method that Valve used for their textures. Therefore, I will be using this method as well.
Big-O Complexity
For every pixel in a image, we will need to test it against every other pixel. This makes its complexity O(n^2). For example a 256x256 has 65,536 pixel. Each pixel would have to be tested against 65536 pixels to find out the nearest corresponding pixel. So it needs 65,536 * 65,536 = 4,294,967,296 array element look ups!
Why I chose this
I chose SDF image conversion because it has lots of potential for parallelization. Since all the operations of a pixel are independent of each other and reads data from one single array, this allows for massive gains when using GPU multi-threading.
The code
| NBody Hot Functions |
|---|
void dowork(double t){
int numtimes=int(abs(t/dt));
dt=t/double(numtimes+1);
numtimes=numtimes+1;
for (int i=0;i<numtimes;i++){
CRO_step(dt,a);
}
}
void CRO_step(register double mydt,void (*a)()){
long double macr_a[4] = {0.5153528374311229364, -0.085782019412973646,0.4415830236164665242, 0.1288461583653841854};
long double macr_b[4] = {0.1344961992774310892, -0.2248198030794208058, 0.7563200005156682911, 0.3340036032863214255};
for (int i=0;i<4;i++){
a();
for (int j=0;j<ncobjects;j++){
cobjects[j]->v += cobjects[j]->a * mydt*macr_b[i];
cobjects[j]->pos += cobjects[j]->v * mydt*macr_a[i];
}
} //We should really expand the loop for efficiency
}
void calculate_a(){
for (int j1=0;j1<ncobjects;j1++){
cobjects[j1]->a=vect(0,0,0);
}
for (int j1=0; j1<ncobjects;j1++){
for (int j2=j1+1;j2<ncobjects;j2++){
double m1=cobjects[j1]->m;
double m2=cobjects[j2]->m;
vect dist=cobjects[j1]->pos-cobjects[j2]->pos;
double magd=dist.mag();
vect base=dist*(1.0/(magd*magd*magd));
cobjects[j1]->a+=base*(-m2);
cobjects[j2]->a+=base*m1;
}
}
} |
