 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Real-Time Heightmap Self-Shadowing Using the Strider Technique |
|
 |
Anonymous Poster |
|||
 Posted - 7/23/2004 5:25:07 AM |
||||
| if only directional light is needed, than you should check some very very old rendering techniques (described like in 80-ties or sooner) and search for "horizont" rendering (at least I hope it's called so or something similar). It would be lot more efficient in your case. basic idea is, that you create a "horizont" line (containing heights of current horizont) perpendicular to light direction (in xz plane, it can go straigth up). Now you move this horizont line through the heigh map in direction of line by some small steps. /* i.e. if you have light directly from "north", than your horizont line needs exactly "width" of map points and your step needs to be "one row" per step. With light from any direction you may need much longer horizont line (as much as size of map*1.41) and choose the better axe to move the horizont along, etc... */ Each step firstly compare the horizont height in every point with heigh map. If horizont is above, the map is in shadow, mark it so. If it is below heigh map, than modify horizont to be heigher in that particular point (heigher shadow will be cast by that point in next step). Once you finished the step, you make the whole horizont go down a bit (or a lot), depends on the slope of light (i.e. light from above will erase whole horizont (no shadows at all), light from side will keep horizont as it is. (of course you should not modify each point in horizont line, but just modify some offset value, which will be added while comparing horizont line with heigh map) Now you make another step, until whole map is processed. (you may imagine it as some sort of "scanning" line going through map in direction of line) This way each heigh map point is processed only once (compared to have shadow and also adding shadow to next points in one step), while your way does "overdraw" shadows with each point in map, if I understand it correctly (I read it very fast, so I may be wrong). So the complexity of horizont shadows are O(size*size) and additional memory requirements are O(size). (Your way has O(1) additional memory, if I understand it correctly, but the complexity of algorithm can be in worst case O(size*size*size). The problem with this technique is, you can't have certain type of holes in scenery, the scenery has to have only one height in particular xz point. (i.e. perfect for heigh maps, but unable to process arc, which will cast "full" shadow, without the hole in it). The horizont rendering is usually used to render front-to-back "mars"-like scenery with none pixel overdraw. (for each screen column you know current max. height point, and you draw further scenery only if is visible abowe current max and update max value then). It was used for example in DOOM1/2, there were two horizonts (bottom and top one), that's the reason for no multiple floors in original DOOM. Walls with particular transparency did only save current state of horizonts in their target area in first front-to-back-no-overdraw pass, to be correctly occluded by the front scenery. Then they were rendered in second back-to-front-pixel-overdrawing pass involving also sprites. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 7/23/2004 5:58:05 AM |
||||
| ok, I just read it again, and there's no real overdraw, as you don't cast shadow from already shadowed point. OTOH you calculate float sqrt for each shadowed point?! You can precalculate at the beginning, how much long is the shadow for "1" height (for example 0.57). Than your current shadow for "WH" height will have length L = WH * 0.57; now how far do you need go in diagonal to cast such long shadow? sqrt(delta_x*delta_x + delta_y*delta_y) = L as your light is diagonal, delta_x = delta_y, but that doesn't matter much, as we need either delta_x or delta_y even in case of other light direction. delta_x = delta_y * tg(alpha) delta_x^2 + delta_y^2 = L^2 delta_x^2 + delta_x^2 * tg(alpha)^2 = WH^2 * 0.57^2 delta_x^2 * (1 + tg(alpha)^2) = WH^2 * 0.57^2 suddently we have lot of constants there (for each frame, even when light is moving, so you can precalculate them once per shadow generation), we need just to put them at right side of calculation: delta_x^2 = WH^2 * 0.57^2 / (1 + tg(alpha)^2) delta_x = WH * 0.57 / sqrt(1 + tg(alpha)^2) the "0.57 / sqrt(1 + tg(alpha)^2)" part can be precalculated ahead. (= C1) so finaly to get the length of shadow we need to calculate delta_x = WH * C1; (after the WH is fetched from current [x,z] position). In case of diagonal light C1 = 0.57 / sqrt(1 + 1) = 0.57 / 1.4142... = 0.806. Then simple: WH = fetch [x,z] heigh; delta_x = WH * 0.806; while ( delta_x-- ) { x--; z--; if ([x,z] shadowed) break; mark [x,z] } will do the same job as your loop. ........ still the horizont approarch should be more data cache friendly, as you process the heigh map in line slices with short horizont array reused for each slice. Each heigh map point is processed only once. Your way does process map in line slices with shadow "spikes" casted from each point. And each point may be fetched several times. (3 times at max IMHO? -> 1 - cast shadow, 2 - gets shadow 3 - rejects another shadow, this may happen for each point only one I think, from the diagonal neighbourgh point) ......... ped 7gods.org |
||||
|
||||
|
_DarkWIng_ Member since: 1/11/2001 From: Duplje, Slovenia |
|||
|
Posted - 7/24/2004 11:42:05 AM |
||||
| Congrats for actualy making a article of your demo. Interesting approach. You should never let your fears become the boundaries of your dreams. |
||||
|
||||
 |
jollyjeffers Moderator - DirectX and XNA Member since: 3/16/2000 From: London, United Kingdom |
|||
|
Posted - 7/25/2004 12:14:47 PM |
||||
| Interesting article, congrats. If it's of any interest, you can get good results (50fps+) with a stencil shadowed terrain and aggresive culling/lazy updates. Just been doing some work on such things over the last couple of weeks... Jack |
||||
|
||||
|
RAZORUNREAL Member since: 1/18/2004 From: Auckland, New Zealand |
|||
|
Posted - 7/30/2004 1:40:13 AM |
||||
| I implemented this about the same, before you wrote the article! I even did soft shadowing but it doesn't look that great because the shadows are only sampled at each vertice. I was shadowing directly across the terrain though, not at 45 degrees so it was especially bad (a whole line of vertices would become shadowed in unison all too often). |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
