Hi, All! edit: the (UPDATED and faster!) demo is here! Check it out (requires GLSL capable card) This demo has all the latest in it (including GLSL shader compilation error reporting, Parallax Occlusion Mapping, a few extra textures, square cones, a faster pre-processor that also outputs DDS files with mipmapping info [8^) edit: Here is the newest version of the video, hosted on my site. (If you can run the demo, don't bother with this...it's lower quality and slower, and a bigger download [8^) edit: (OUTDATED) Code-R has once again hosted a copy of the full demo here. Thanks!! edit: if you had the old demo already, then here is the Upgraded demo, download this as well (includes Parallax Occlusion Mapping and self-shadowing CSM!) and you will also need the new textures found here! edit: once again Code-R comes to the mirroring rescue! CSM Paper edit Feb 8, (3:20AM local): here's the alpha version of the paper documenting this method! edit Feb 8, 11:30PM: now it's the beta version...same links! edit: Monder has kindly mirrored the video here. (Thanks!!) edit: and Promit put up this one. (Thanks!!) ----------------- OK, I'm really excited because I just got a GeForce 6600 (I know, it's still not cutting edge) and can finally visit the happy land of shader developers! I am using TyphoonLabs Shader Developer with GLSL as I really am a beginner, and that seemed the easiest way to do GLSL. I am comparing my implementation against the Parallax&Bump and Relief Mapping demos that come with the app, so I'm not sure if those are the fastest implementations of their respective algorithms. I had been reading about relief mapping and steep parallax, both methods with a height-map walking type algorithm, and I came up with my own idea. It is kind of like "space leaping" or "sphere steps", but adapted to a heightmap instead of voxels. I pre-process a heightmap with a tool I wrote to get stepping and slope information, and then store height, step-info, df/dx, and df/dy (for normals w/o using the derivative operator) in the RGBA channels of an image. (can do tiled textures in x, y, both, or neither) First I approached the shader as an all-out solver (sorry, I'm a numerical-methods guy [8^). I got pretty decent performance with accurate results (between 0-15% slower than Relief Mapping, but very accurate...no hand tuning a "number_of_linear_steps" and "number_of_binary_steps"). By overrelaxing my own algorithm I could beat Relief Mapping's performance (by the same 15% margin). However that is still too slow for games, at least on my machine [8^) For performance reasons I modified the algorithm to be less of an exact solver (getting rid of all of the dynamic branching), and it just performs a fixed number of iterations (10 in the demo video). With only 1 iteration it looks very much like parallax mapping (each step is limited, so it may not go far enough, but definately will not go too far), and is a tiny bit slower. The good news is that I can do 5-10 more iterations with a minimal performance hit (runs at ~80% of parallax), and have results that look like Relief Mapping! Note 1: It is a 1MB XVID AVI, so this will eat up my available bandwidth pretty quick...anybody have some hosting capabilities they wouldn't mind sharing? Note 2: The timings may be suspicious...Shader Designer never seemed to go above 50 fps, even with just a flat shaded quad taking up approx. 100 pixels! I disabled vsync in the nVidia driver but that didn't change anything. The precompiled GLSL examples from the nVidia SDK run in the 100-300 fps range on my machine, so I'm not really sure what's going on...maybe SD has it's own compiler or automatically turns on debug info or something?? I'm now working to get this into an actual compiled demo for more serious testing. Note 3: the Relief Mapping code came with a second pass to determine self-shadowing. Since my shader doesn't do that yet, I just disabled that feature in the RM version to have it be comparable (instead of RM doing 2x the work) Note 4: if anybody is interested, I'd like to write this method up and submit it as an article here on GameDev. [Edited by - lonesock on May 11, 2006 12:26:36 PM]

Hi,

I am interested in knowing more about the algorithm you developed to ray-trace the heightmap in the shader. Could you please post details about it and about the preprocessing step involved with it?
Moreover, you might want to read this article :

Link to paper

It describes a clever way to get rid of silhouettes in the context of relief mapping. It requires a fitting of the mesh to a quadratic surface but that should not be a problem for a mathematical skilled guy like you.
Cheers,

OK, a few more details at the bottom, but first:

@nooan: That is a very cool paper! Since it requires pre-processing the mesh, I can't do it yet for Shader Designer (they have their own special model format)...I'll have to wait until I get my compiled version working (will take some time as I've got no code base...I'm starting from scratch with shader programming [8^). Thanks for the link!

@LtJax & supagu: thanks for your feedback!

@AP: my method is very similar...what they are using is a 3D texture (256x256x16 in the paper, I believe), which is pretty much an implementation from "Fast and Reliable Space Leaping for Interactive Volume Rendering" by Wan et.al. in 2002. My only contribution for this algorithm was to adapt the 3D (voxel) requirement to work with simple 2D heightmaps.

OK, the quick details! I'm going to actually post the preprocessor (in c++ source and exe) and the SD project on my website. Everything will be under MIT license (or similar...maybe ZLIB?), so you can use it for anything (although I always appreciate credit [8^). That will probably take a little while, though, so in the meantime...

The first step is preprocessing the heightfield texture, so for each pixel in the texture:

* compute the heightmap's slope (derivative in each direction, but not properly scaled! remember, I'm processing this with an image [0..255])
-- using the central difference method for all internal points
-- df/dx = 127 + (f(x+1,y) - f(x-1,y)) / 2
-- df/dy = 127 + (f(x,y+1) - f(x,y-1)) / 2
-- using forward or backward difference (as appropriate) for edge pixels

* compute the Cone_Ratio! This is the secret sauce right here! For each point on the heightfield (per texel, in other words) I find the largest cone that can sit on that point, along the vertical axis, that just touches some other point in the heightfield. Some basic points of interest:
-- Cone_Ratio is R/Height, where R is the lateral distance and Height is above the surface of the heightfield (yeah, I know, duh [8^)
-- if my view vector is perfectly vertical, a very good step size is Height! (obvious, I know)
-- if my view vector is perfectly horizontal, a very good step size is Height * Cone_Ratio!
-- there is some really simple math to scale between the 2, based on the vertical component of the view vector. It requires a sqrt per pixel, but the speedup is tremendous
-- Cone_Ratio is always (0,1] (i.e. 0.0 < Cone_Ratio <= 1.0). >0 because I need to divide by it in the shader, and <= 1 because hardly any pixels ever had a value >1 and 1 is so stinking convenient in texture space!
-- the histogram of Cone_Ratio showed that most pixels have low values, so in the preprocessor I actually store sqrt(Cone_Ratio) because it improves the spread and it is easy to square the ratio inside the shader (multiply being a very cheap operation)!

Now I store the following in a PNG texture (compressed, and has 4 channels):
Red <- height
Green <- sqrt(Cone_Ratio)
Blue <- df/dx
Alpha <- df/dy

* Inside the shader I start at height 1.0 (so the actual polygon surface is considered the top of the heightmap)
* Each step I see how far above the heightfield I am (using the Red component).
* Using the vertical component of the vector, I scale Step_Ratio between 1.0 (if it was totally vertical) and Cone_Ratio (if it was totally horizontal)
* now I take a step of length = (Height * Step_Ratio)! You can also use overrelaxation (values of 1.1 or 1.2 work well)
* repeat!

And that's it...an iterative method without branching! There are 2 versions with branching:
1) actually went until the surface was reached, but that was as slow as relief mapping, though more accurate, and
2) pass in a number of steps and use a for loop. 2) was really beautiful in that it is easy to do LOD (distant objects get 1 iteration, medium get 5, near get 20, or something like that). However that branching seemed to be much slower than the actual computation for each step, so the implementation you see has a fixed number (10) unrolled. (It would have been easy to use the full solver version for the video, BTW, but I didn't [8^)

If I use this in a game I'd probably leave in all 3 versions as alternate code paths so in the future people with huge machines can use the exact version if they want to play a (by then) retro game!



BTW, I need a cool name for this method (results are just not enough...I need marketing! [8^). I was thinking "Cone Step Mapping". Any ideas or votes?

RapidShare mirror for the link.

@Monder & Promit: Thanks so much!

I'll try to get the files I have into a 7z and on my website tonight. As a teaser, though, here is the workhorse shader code (this is the loop version, not unrolled, for brevity):