• 05/07/02 11:26 AM
    Sign in to follow this  

    Fast Computation of Terrain Shadow Maps

    Graphics and GPU Programming

    Myopic Rhino
    [size="5"][b]Introduction[/b][/size]

    The topic of terrain rendering is a very big one. This paper will focus on the lighting and shadowing aspects of terrain rendering. In the pictures below you can see the effect of this technique in action.

    [center][attachment=3960:selfshadows_0.jpg] [attachment=3961:selfshadows_1.jpg]
    [b]Terrain shadows generated using this algorithm[/b][/center]

    [size="5"][b]Algorithm description[/b][/size]

    The algorithm is quite simple in fact. For every grid point, we check if the ray from the light position to the point intersects the map. This is done very quickly by checking only the points that are under the projection of the vector L, as shown in Figure 1.

    [center][attachment=3962:img_1.gif][/center]
    Let us consider the following notations:
    [list][*]A = working point[*]B = coordinates of the sun position projection ( vector B = vector(sun_pos.x, 0, sun_pos.z) );[*]C = coordinates of the sun position;[*]L = light direction vector ( L = A - C );[*]P = any point that lays under the projection of vector L;[*]X(P) = coordinates on the L vector whose projection is point P (computed used simple LERP).[/list] The points P are generated using a 2D line algorithm from the working point (A) to the projection of the sun position point (B). Then, for every point P, you check to see if the height map value for point P is bigger than the y value of point X(P). If it turns out to be bigger, then we know that the ray L intersects the map, and the illumination at point A will be equal to the 'ambient_color_value', and we can safely move to the next working point.

    If all the P-type points have been tested and no intersection was found, then the illumination at point A is computed using the following formula:

    [b]Illum(A) = ambient_color_value + (L dot N)[/b]

    clamped to the range [0,1].


    [size="5"][b]Algorithm implementation[/b][/size]

    [center][attachment=3963:img_0.gif]
    [/center]
    If the above description wasn't clear, the code should help. The most important function of this algorithm's implementation is the function [b]intersect_map[/b]. This function checks to see if the working point is occluded, by testing to see if the light direction ray intersects the map. This function is called for every point in the height map. When an intersection point is found, the testing for the current working point stops, and another working point from the lightdir projection is fetched to be tested (the gray points from the picture at the right). As I said in the algorithm description, if the working point isn't occluded, its illumination value is computed using the formula shown above.

    The function [b]genLightmap[/b] handles the light map generation. It tests and illuminates every point on the height map.

    [i] Note: If you plan to copy & paste this code into your own program you should know that the normals are compressed from 1 float per component, to 1 byte per component. (see the [b]note [/b]at the end of the paper)[/i]

    [code]int intersect_map(const vector3& iv,const ray& r,Image* hm,float fHeightScale){
    int w,hits;
    float d,h,D;
    vector3 v,dir;

    v = iv + r.direction;
    w = hm->w;

    hits = 0;

    while (!(( v.x >= w-1 ) || ( v.x <= 0 ) || ( v.z >= w-1 ) || ( v.z <= 0 ))){
    // length of lightdir's projection
    D = Magnitude(vector3(v.x,0,v.z)-vector3(r.origin.x,0,r.origin.z));
    d = Magnitude(iv-v); // light direction
    h = iv.y + (d*r.origin.y) / D; // X(P) point

    // check if height in point P is bigger than point X's height
    if (hm->data[ifloor(v.z)* w + ifloor(v.x)] * fHeightScale > h){
    hits++; // if so, mark as hit, and skip this work point.
    break;
    };

    dir = r.direction;
    dir.y = 0;
    v += Normalize(dir); // fetch new working point
    };
    return hits;
    };

    Image* genLightmap(char* normal,Image* hm,vector3 fSunDir,int w,float fAmbient){
    int i,j,hits;
    float f,dot;
    vector3 n,fVertex;
    Image* lmap;
    ray r;

    float fHeightScale = 10.0f / 255.0f;
    lmap = new Image(w,w,1);
    if (!lmap){printf("(!) Error: cannot alloc lightmap!\n");return 0;};

    for (j=0; jdata[j*w+i] * fHeightScale;
    fVertex.z = j;

    f = fAmbient ;

    r.origin = fVertex + fSunDir * 2000.0f;
    r.direction = fSunDir;

    // checks current working point for intersection
    if (!intersect_map(fVertex,r,hm,fHeightScale)){
    // compute the lighting equation
    n.x = (float)(normal[3*(j*w+i)+0]);
    n.y = (float)(normal[3*(j*w+i)+1]);
    n.z = (float)(normal[3*(j*w+i)+2]);
    f += 0.5f*(1.0f+DotProduct(Normalize(n),Normalize(fSunDir)));
    if (f>1.0f) f = 1.0f;
    };

    dot = f * 255.0f;
    lmap->data[j*w+i] = (unsigned char)dot;
    };
    };
    return lmap;
    };[/code]After you have successfully created your light maps, you will probably want to use them. I will tell you two ways to add them to your own terrain engine: one is to use them as light maps, and the other is to set the color of each point in the terrain according to its corresponding color in the shadow map.

    [center][attachment=3965:colormap.jpg]
    [b]Terrain color map[/b]

    [attachment=3966:lightmap.jpg]
    [b]Terrain shadow map[/b]

    [attachment=3967:colormap_shaded.jpg]
    [b]Final terrain texture[/b]


    [left][size="5"][b]Lightmapping[/b][/size]

    If you intend to use the shadow map as a light map, you should consider the use of a supplementary texture unit. In any case, if you decide to use this technique, you should set the texture environment mode to modulate. In OpenGL, this is done in the following manner :

    [code]glTexEnvi(GL_TEXTURE_ENV,GL_TEXTURE_ENV_MODE,GL_MODULATE);[/code]
    [b][size="5"]Color component[/size][/b]

    When using the shadow map pixels as color components for the terrain geometry, you should consider using separate buffers for each vertex component. By doing this, you will be able to send the data returned by genLightmap directly to the renderer, by setting the color array pointer to the address of the returned data. In OpenGL, this is done with the [font="Courier New"][color="#000080"]glColorPointer[/color][/font] function.


    [b][size="5"]Note[/size][/b]

    For any questions or suggestions, feel free to e-mail me at [email="nervus@go.ro"]nervus@go.ro[/email]

    The full sources for this article can be found at [url="http://nervus.go.ro/"]http://nervus.go.ro/[/url] in the [i][b]Downloads [/b][/i]section.

    The sources are free, you can do whatever you want with them, but if you include them in your project, or use this algorithm for any commercial or non-commercial use, please give me credit.


    [b][size="5"]Bibliography[/size][/b]

    [b]Global Illumination Compendium[/b]
    March 16, 2000,
    Philip Dutr?
    [email="phil@graphics.cornell.edu"]phil@graphics.cornell.edu[/email]
    Program of Computer Graphics
    Cornell University
    [url="http://www.graphics.cornell.edu/%7Ephil/GI/"]http://www.graphics.cornell.edu/~phil/GI/[/url]
    [/left][/center]


      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.