   Shadow map generation way too slow
  Hey there!I'm trying to create a shadowmap for my terrain, but for some reason I don't understand it's way too sloooow.I never did something like ray casting, so I just wrote this ugly piece of code:void GeometryTerrain::computeLightmap(const Vector3& _vlightSource){GLubyte* shadowMapTexture = (GLubyte*)malloc(GetWidth()*GetWidth()*3);memset(shadowMapTexture, 0, GetWidth()*GetWidth()*3);   //Iterate through mapfor(int z =0; z <= GetLength(); ++z){for(int x = 0; x <= GetWidth(); ++x){float f = 255;    //create a ray, position vector = terrain vertex; direction vector = sun position-positionvectorRay lightRay(Vector3(x, getHeight(x, z), z), _vlightSource );    //this vector holds current position of the ray, which travels from the vertex in direction of sunVector3 current_ray_pos(Vector3(x, getHeight(x, z), z));float d = 0;int numRayHits = 0;//while(current_ray_pos.x < _vlightSource.x && current_ray_pos.y < _vlightSource.y && current_ray_pos.z < _vlightSource.z)while(!(current_ray_pos.x <= 0 || current_ray_pos.x >= GetWidth() || current_ray_pos.z <= 0 || current_ray_pos.z >= GetWidth() )){  //This line is an ugly hack, if I'd remove it, the whole method stucks at 12.5% work. But even that line doesn't make it "fast". Creation still needs 3 minutesif(current_ray_pos.magnitude() > 1024) break;//Vector3 projectedPoint = current_ray_pos.project(current_ray_pos, Vector3(x, getHeight(x, z), z));  //check if the terrains height value underneath the current ray position is larger than the y value of the rayif(getHeight((int)floor(current_ray_pos.x), (int)floor(current_ray_pos.z)) > current_ray_pos.y){numRayHits++;break;}//light has not reached map boundaries//...let it travel further in direction of the suncurrent_ray_pos += lightRay.m_v3Direction.normalize();}if(!numRayHits)f = 255;shadowMapTexture[(x+z*GetWidth())*3 + 0] = (int)f;shadowMapTexture[(x+z*GetWidth())*3 + 1] = (int)f;shadowMapTexture[(x+z*GetWidth())*3 + 2] = (int)f;}}ilTexImage(GetWidth(),GetWidth(), 1, 3, IL_RGB, IL_UNSIGNED_BYTE, shadowMapTexture);ilSetData(shadowMapTexture);//ilSetInteger(IL_IMAGE_BITS_PER_PIXEL,32);ilEnable(IL_FILE_OVERWRITE);ilSave(IL_JPG, "lightmap.jpg");free(shadowMapTexture);}Notice the comment near this line "if(current_ray_pos.magnitude() > 1024) break;"I'm confused. Any ideas? Thank you!   
  You sometimes use 'GetLength()' to refer to the extent in the Z direction, but other times use 'GetWidth()'. That smells like a bug. Also, you seem to have a few bugs in your inequalities (study closely how I've written them). Oh, and you don't end up actually marking any shadow because 'f' is initialized to 255 ahead of time, and set to 255 if there aren't any ray hits... it's never set to anything else. And then the shadow map is unconditionally updated with those values for every position. :)Anyway, some suggestions for code cleanliness, first without actually trying to understand the algorithm:void GeometryTerrain::computeLightmap(const Vector3& _vlightSource){int width = GetWidth();int length = GetLength();// Trust me, this part is not your bottleneck ;) but doing it this// way is a lot neaterstd::vector<GLubyte> shadowMapTexture(width * length * 3);//Iterate through mapfor (int z = 0; z < length; ++z){for(int x = 0; x < width; ++x){Vector3 current_ray_pos(x, getHeight(x, z), z);Vector3 direction_to_sun = Ray(current_ray_pos, _vlightSource).m_v3Direction.normalize();boolean shadow = false;// This is a simpler expression of the loop condition,// which can be derived by DeMorgan's Lawswhile (current_ray_pos.x >= 0 && current_ray_pos.x < width &&current_ray_pos.z >= 0 && current_ray_pos.z < length &&current_ray_pos.magnitude() > 1024) {// Is the terrain blocking the ray at this point?if (getHeight((int)floor(current_ray_pos.x), (int)floor(current_ray_pos.z)) > current_ray_pos.y){shadow = true;break;}current_ray_pos += direction_to_sun;}if (!shadow) {int index = (x + z * width) * 3;for (int i = 0; i < 3; ++i) {shadowMapTexture[index + i] = 255;}}}}ilTexImage(width, length, 1, 3, IL_RGB, IL_UNSIGNED_BYTE, shadowMapTexture);ilSetData(shadowMapTexture);ilEnable(IL_FILE_OVERWRITE);ilSave(IL_JPG, "lightmap.jpg");}As for fixing the speed, I'd guess what you want to do is project the rays downward from peaks instead of upward from valleys. ;) But getting that to work robustly isn't straightforward...Another thing you could try is to find the max (I'm assuming Y increases as you go upwards in your coordinate conventions) Y value of all the points first, and then use that value instead of the hard-coded 1024 in your "hack".Another thing you could try is to optimize traversal along the ray, by first figuring out which (x, z) coordinates are involved (hint: Bresenham's line drawing algorithm) and then finding the y value of both the ray and the terrain at that coordinate. (This is probably more robust, too, actually.)   ;  Thank you!Quote:Original post by ZahlmanAs for fixing the speed, I'd guess what you want to do is project the rays downward from peaks instead of upward from valleys. ;) But getting that to work robustly isn't straightforward...Tried that, same speed :(Quote:Original post by ZahlmanAnother thing you could try is to find the max (I'm assuming Y increases as you go upwards in your coordinate conventions) Y value of all the points first, and then use that value instead of the hard-coded 1024 in your "hack".Did that too :). Still slow as hell.I took a look at this article http://www.gamedev.net/reference/articles/article1817.asp and it seems to be a lot faster, even though I cant find any differences which make it faster.   ;  Moving this to Math may be better.   ;  You need to profile it to really determine what is the cause of the slow down. For all we know it could be writing the jpeg file which is the slowest part.I suggest CodeAnalyst if your using a AMD chip and if your on Intel, you can get a trial of Vtune, barring that you can try using the built in profiling tools that comes with MSCV (been ages sicne i last looked at those).Good Luck!-ddn   ;Quote:Original post by ddn3You need to profile it to really determine what is the cause of the slow down. For all we know it could be writing the jpeg file which is the slowest part.I can assure you that writing a .jpg file with a *library call* would not reasonably take the majority of 3 minutes (the amount of runtime cited), and even if it did, there wouldn't really be a way around that (besides switching to another library). :)But your point holds, in general: programmers are known for making spectacularly poor guesses about where the bottleneck is.   ;  Who knows, maybe he makes a texture map 12800x12800 :D Which would assuredly take 3 minutes or more to compress with jpeg :D-ddn   