Sign in to follow this  

Simple Terrain Shadow Algorithm (source code)

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to 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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Two comments:

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
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 ;)


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]

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragon_Strike
Quote:
Original post by Anonymous Poster
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 ;)


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


I think they mean to use vectors instead of angles, that'll get rid of all the trig. Since the light is horizonal, you'd only use a 2d vector. I did this with my light mapping and sped things up 10 fold.
It shouldn't effect (non) self shadowing.

Share this post


Link to post
Share on other sites
Quote:
Original post by Johnny123
Quote:
Original post by Dragon_Strike
Quote:
Original post by Anonymous Poster
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 ;)


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


I think they mean to use vectors instead of angles, that'll get rid of all the trig. Since the light is horizonal, you'd only use a 2d vector. I did this with my light mapping and sped things up 10 fold.
It shouldn't effect (non) self shadowing.


Im not taht good with vectors... how could i replace the trigonomerty with vector calcualtions?

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

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

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

Sign in to follow this