1 Introduction #

The terrain rendering topic is a very big one. This paper tries to cover only the lighting and shadowing parts of terrain rendering. In the pictures below you can see the effect of this technique in action.

Terrain shadows generated using this algorithm

[edit]

2 Algorithm description #

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 fast by checking only the points that are under the projection of the vector L, just like you can see in figure 1.

Let us consider the following notations:

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).

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, check if the height map value for point P is bigger than the y value of point X(P). If it turns to be bigger, then we can consider that the ray L intersects the map, and the illumination in point A will be equal to the 'ambient_color_value', so we can safely move to a next working point. If all the P-type points have been tested and no intersection was found, then the illumination in point A is computed using the following formula: Illum(A) = ambient_color_value + (L dot N) , clamped to the range 0,1.

[edit]

3 Algorithm implementation #

If the above description didn't clear up things a bit, the code surely will do this. The most important function of this algorithm's implementation is the function intersect_map. This function checks if the working point is occluded, by testing 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 is stopped, 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 Illum(A) = ambient_color_value + (L dot N) , clamped to the range 0,1. The function genLightmap handles the light map generation. It tests and illuminates all height map points.

Note: If you plan to copy & paste this sources into your own program you should know that the normals are compressed from 1 float per component, to 1 byte per component.

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 ))){
        D = Magnitude(vector3(v.x,0,v.z)-vector3(r.origin.x,0,r.origin.z)); // length of lightdir's projection
        d = Magnitude(iv-v); // light direction
        h = iv.y + (d*r.origin.y) / D; // X(P) point
        if (hm->data[ifloor(v.z)* w + ifloor(v.x)] * fHeightScale > h){ // check if height in point P is bigger than point X's height
            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; j<w; j++){
        for (i=0; i<w; i++){
            fVertex.x = i;
            fVertex.y = hm->data[j*w+i] * fHeightScale;
            fVertex.z = j;

            f = fAmbient ;

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

            if (!intersect_map(fVertex,r,hm,fHeightScale)){ // checks current working point for intersection
                // computing 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;
};

After you successfully created your light maps, you will probably try to use them. I will tell you two ways to use them into your own terrain engine: one is use them as light maps, and another way is to set the color of each point from the terrain points according to its correspondent color in the shadow map.

Terrain color map + Terrain shadow map = Final terrain texture

[edit]

4 Lightmapping #

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

glTexEnvi(GL_TEXTURE_ENV,GL_TEXTURE_ENV_MODE,GL_MODULATE);

[edit]

5 Color component #

When using the resulted shadow map pixels as color components for the terrain geometry, you should consider using separated buffers for each vertex component. By doing this, you will be able to send the data retured by genLightmap directly to the renderer, by setting the color pointer to the returned data's address.In OpenGL, this is done with the glColorPointer function.

ID
Password
Join

Contents

1 Introduction #

2 Algorithm description #

3 Algorithm implementation #

4 Lightmapping #

5 Color component #