# Simple Terrain Shadow Algorithm (source code)

This topic is 4605 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Well i dont know if there has been posted a similar method alrdy... i thought id post it and hope fo some comments and maybe help out others who also has problems with lighting terrain... its pretty simple and this implementation works only for light along the x-axis
// Calculate horizons for each vertex. Does light reach it (1.0f), or not (0.0f).
// Works by calculating a ray from each point using tangent and if the terrain
// is higher than the ray at any point than the point is in shadow
void CTERRAIN::CalculateHorizonMap()
{

int Angle = 30;
int x, x1, z;

int MapSize = 256;
float TempHorizonMap[256][256];

for ( z = 0; z < MapSize; z++)
{
for (x = 0; x < MapSize; x++)
{
TempHorizonMap[x][z] = 1.0;

for (x1 = x+1; x1 < MapSize; x1++)
{
if ((float( x1-x ) * tan(Angle*3.14159/180) + GetScaledHeightAtPoint(x, z) ) < GetScaledHeightAtPoint(x1, z) )
{
TempHorizonMap[x][z] =  0;
x1 = MapSize;

}
}

}
}

//Blur the map with avarge values so that u dont get sharp shadow edges
for ( z = 0; z < MapSize; z++){
for (int x = 0; x < MapSize; x++){
if (true){
HorizonMap[x][z] = ( ( TempHorizonMap[x-1][z+1] + TempHorizonMap[x][z+1]
+ TempHorizonMap[x-1][z]    + TempHorizonMap[x][z]
+ TempHorizonMap[x-1][z-1]  + TempHorizonMap[x][z-1])/6 );
}
}
}

}

//Calculate mesh normals
void CTERRAIN::CalculateNormals( )
{

Vector A, B, C, D, E;
Vector CA, CB, CD, CE;

Vector AverageNormal;
Vector NormalACB,NormalBCE,NormalECD,NormalDCA;

for (int z = 1; z < 256; z++)
{
for (int x = 1; x < 256; x++)
{
A.Set( float(x  ),GetScaledHeightAtPoint(x, z+1), float(z+1) );
B.Set( float(x-1),GetScaledHeightAtPoint(x-1, z) , float(z  ) );
C.Set( float(x  ),GetScaledHeightAtPoint(x, z) , float(z  ) );
D.Set( float(x+1),GetScaledHeightAtPoint(x+1, z) , float(z  ) );
E.Set( float(x  ),GetScaledHeightAtPoint(x, z-1), float(z-1) );

CA = A - C;
CB = B - C;
CD = D - C;
CE = E - C;

NormalACB = CA.CrossVector(CB);
NormalBCE = CB.CrossVector(CE);
NormalECD = CE.CrossVector(CD);
NormalDCA = CD.CrossVector(CA);

NormalACB.NormalizeVector();
NormalBCE.NormalizeVector();
NormalECD.NormalizeVector();
NormalDCA.NormalizeVector();

AverageNormal.x=(NormalACB.x + NormalBCE.x + NormalECD.x + NormalDCA.x)/(float)4.0;
AverageNormal.y=(NormalACB.y + NormalBCE.y + NormalECD.y + NormalDCA.y)/(float)4.0;
AverageNormal.z=(NormalACB.z + NormalBCE.z + NormalECD.z + NormalDCA.z)/(float)4.0;

AverageNormal.NormalizeVector();

NormalMap[x][z] = AverageNormal;
}
}
}

void CTERRAIN::CalculateLighting()
{
int Angle = 30;

//Calcualte sun normal based on angle
float tempx = cos(Angle*3.14159/180);
float tempy = sin(Angle*3.14159/180);
float tempz = 0;

Vector SunNormal;
SunNormal.Set(-tempx, -tempy, 0.0);

//Set the suns color ( x = Red, y = Green, z = Blue)
Vector SunColor;
SunColor.Set(1.0, 0.8, 0.8);

for (int z = 1; z < 256; z++)
{
for (int x = 1; x < 256; x++)
{
// Get brightness of point by taking the dotproduct of
//the normalvector and sun vector
float sun = NormalMap[x][z].DotVector(SunNormal);

// Make sure we dont get to high or to low values
if ( sun > 1)
{
sun = 1;
}
if (sun < 0.0f)
{
sun = 0.0f;
}

// Multiple the brightness with the horizonmap and suns color
LightMap[x][z].x = HorizonMap[x][z]*sun*SunColor.x;
LightMap[x][z].y = HorizonMap[x][z]*sun*SunColor.y;
LightMap[x][z].z = HorizonMap[x][z]*sun*SunColor.z;

}

}
}

}


and here is the results: http://img427.imageshack.us/img427/2701/method3mq.jpg its pretty simple to add atmospheric lighting and indirect illumination using the horizonmap fnction.. u just have to calculate the horizonmap for all 180 angles... Maybe ill post this later.. for those who are intrested in the vetor class.. here it is..
#ifndef _3Dvector_H_
#define _3Dvector_H_

#include "math.h"

class Vector
{
private:

public:
float x, y,z ;

Vector(float ex = 0, float why = 0, float zee = 0)
{
x = ex; y = why; z = zee;
}

~Vector() {}

void comptopolar(int angle)
{
x = cos(angle*3.14159/180);
y = sin(angle*3.14159/180);
z = 0;
}
float GetMagnitude()
{
float value = x * x + y * y + z * z;
return sqrtf(value);
}

Vector operator*(float num) const
{
return Vector(x*num, y*num, z*num);
}

friend Vector operator*(float num, const Vector &vec)
{
return Vector(vec.x*num, vec.y*num, vec.z*num);
}

Vector operator+(const Vector &vec) const
{
return Vector(x+vec.x, y+vec.y, z+vec.z);
}

Vector operator-(const Vector &vec) const
{
return Vector(x-vec.x, y-vec.y, z-vec.z);
}

void NormalizeVector()
{
float mag = sqrtf(x*x+y*y+z*z);
x /= mag; y /= mag; z /= mag;
}

void NormalizeValues()
{
float max = 0;

if (x > max)
{
max = x;
}
if (y > max)
{
max = y;
}
if (z > max)
{
max = z;
}

x /= max; y /= max; z /= max;

}

float DotVector(const Vector &vec)
{
return x * vec.x + y*vec.y + z * vec.z;
}

Vector CrossVector(const Vector &vec)
{
return Vector(y*vec.z - z*vec.y, z*vec.x - x*vec.z, x*vec.y - y*vec.x);
}

void Set(float ex, float why, float zee)
{
x = ex; y = why; z = zee;
}
};

#endif


[Edited by - Dragon_Strike on June 9, 2006 6:03:45 PM]

##### Share on other sites
This is exremely helpful, thanks alot!

Not only do I have use for the lightning algorithm (I was just about to implement a similar one when I randomly stumbled into this from your IOTD), your CalculateNormals() function will help aswell since I'm too lazy figuring it out again for myself (I did it once but lost the code ^^).

A well deserved rating++

##### Share on other sites
This is interesting, just an an idea...

Maybe this could be implemented in a real-time (or near real-time) method for time-of-day transitions..

you wouldnt need to loop through each vertex every frame, it could be spread out, becasue your transitions dont have have to be very fast of course..

##### Share on other sites
you could simply pre-calculate it into a 3d array...

"""double post""

##### Share on other sites
this is horizon bump mapping on terrain.
not that this is bad but just so everybody knows that it has already been there.

regards,
m4gnus

##### Share on other sites
From a quick look, you could get rid of the triginometry and use a dotproduct instead, that'll speed things up enough for real time.

Otherwise, that's pretty much how most engines do a horizon map. Good work, I love your terrain ;)

##### Share on other sites

1. I think the way you create your horizon map could be done much faster. Not a big deal for a 256x256 terrain, but it could be for larger terrains. You're algorithm for finding the shadowed vertices along a row in the elevation map has a running time of O(n^2) with n beeing the the number of columns(MapSize). Imagine if your terrain was flat, but with a spike at [z, MapSize-1] causing all other points on that row to be in shadow. Then, in your algoritmh the inner for-loop would traverse all vertices from the one you're shadowing to MapSize. A better approach would be the following pseudo, which has a running time of O(n):

for (z=0; z<MapSize; z++) {  for (x=MapSize; x>=0; x--) {    horizonMap[x][z] = 1;    x1 = x-1;    while (x1>=0 && elevationAt(x, z)+(x-x1)*tan(angle)<elevationAt(x1, z)) {      horizonMap[x1][z] = 0;      x1--;    }    x=x1;  }}

This would work for angles<90'. For angles >90' you would traverse x from 0 to MapSize instead.

2. A better approach than to store whether a point is in shadow might be to store the light angle at which the points comes into or out of shadow. That way the light could be moved in real time without the need for recalculating the horizon map. Of course you would have to store 2 angles if the light could move beyond 90 degrees. This could be done by traversing each row two times, one from the left and one from the right.

##### Share on other sites
for (z=0; z<MapSize; z++) {  for (x=MapSize; x>=0; x--) {    horizonMap[x][z] = 1;    x1 = x-1;    while (x1>=0 && elevationAt(x, z)+(x-x1)*tan(angle)<elevationAt(x1, z)) {      horizonMap[x1][z] = 0;      x1--;    }    x=x1;  }}

i dont think this will work since u will only enter the while loop if x-1 dirctly is in shadow... and u have the x1++ in the loop soo it wont check the points that come safter x-1...

EDIT: I guess u coul do it like this.. dunno if it faster though,...
	for ( int z = 0; z < m_size; z++)	{		for (int x = 0; x < m_size; x++)		{			HorizonMap[x][z] = 1.0;			int x1 = x+1;			while ( (float( x1-x ) * tan(Angle*3.14159/180) + GetScaledHeightAtPoint(x, z) ) > GetScaledHeightAtPoint(x1, z) && x1 < m_size )			{				x1++;			}        			if (x1 < m_size )			{					x = x1;					while (x1 >= x)					{						HorizonMap[x1][z] = 0;						x1--;					}							}		}	}

Quote:
 2. A better approach than to store whether a point is in shadow might be to store the light angle at which the points comes into or out of shadow. That way the light could be moved in real time without the need for recalculating the horizon map. Of course you would have to store 2 angles if the light could move beyond 90 degrees. This could be done by traversing each row two times, one from the left and one from the right.

ive been thinking about that.. its a good idea.. just have to figure out how to implement it..

[Edited by - Dragon_Strike on June 11, 2006 7:28:19 AM]

##### Share on other sites
Quote:
 Original post by Anonymous PosterFrom a quick look, you could get rid of the triginometry and use a dotproduct instead, that'll speed things up enough for real time.Otherwise, that's pretty much how most engines do a horizon map. Good work, I love your terrain ;)

if i use only dot product then the terrain will only self-shadow? wont it? thats why im using a horizon map 2..?

[Edited by - Dragon_Strike on June 11, 2006 7:32:43 AM]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 27
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634102
• Total Posts
3015533
×