   Simple Terrain Shadow Algorithm (source code)
  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 shadowvoid 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 edgesfor ( 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 normalsvoid 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 anglefloat 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 vectorfloat sun = NormalMap[x][z].DotVector(SunNormal);    // Make sure we dont get to high or to low valuesif ( sun > 1){sun = 1;}if (sun < 0.0f){sun = 0.0f;}// Multiple the brightness with the horizonmap and suns colorLightMap[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.jpgits 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]
  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++   ;  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..   ;  you could simply pre-calculate it into a 3d array...   ;  """double post""   ;  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   ;  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 ;)   ;  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.   ;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];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]