Cone Step Mapping, Paper & Demo [bummer [8^(

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,

very nice! I'd like to see the article for that!

me too :) so the video, how many iterations is it?
also can you explain for us not so maths types why and what is
df/dx, and df/dy i rememeber doing something like this in year 12 but i've forgotten :P

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?

Seems like a good method [grin].

I have actually been looking at implementing the method described in "Per-Pixel Displacement Mapping with Distance Functions" from GPU Gems 2 in an HL2 mod I'm working on, however it seems that I can't actually use 3D textures in shaders created with the SDK (Valve supplies nothing in their materials API to load them or bind them) which makes implementing it rather problematic (I was thinking on emulating 3D textures with a big 2D one but that'd be a rather nasty solution). Your method is similar to the one in GPU Gems 2 but it has the nice advantage of only needing a 2D texture which lessens memory requirements a lot (i.e. you have one 256x256 texture versus a 256x256x16 texture).

I'd be very interested in seeing the source of the shaders and the preprocessor, although I guess I could work it all out myself seeing some source would help.

Oh and I've put your video up on my gamedev webspace here it may disappear at some point but as I hardly use my webspace it should be there for a while.

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):

Can you explain how you derived the formula for calculating the scale distance? I can't really work out where it came from.

Certainly!

OK, the "w" is just the over-relaxation parameter, pretend it's a 1.0 and ignore it.

The (1.0-ds.z*sc-t.r) is just the height of my sample point above the heightmap.

now for the tricky part: This is all done in 2-D (as the cone is such a nice symmetrical figure [8^). I will use a setup where height is scaled to 1.0.

given:
* sample point at (0,1) (here the scaled height is 1.0)
* a normalized sampling vector (iz,-z) (where iz = sqrt (1-z*z))
* line through the origin with slope = 1/Cone_Ratio (called the cone-line)

find:
* a value for Step_Ratio such that (0,1) + Step_Ratio*(iz,-z) is on the cone-line

equation for the cone-line:
-x + Cone_Ratio*y = 0.0

solving:
-(Step_Ratio*iz) + Cone_Ratio*(1-Step_Ratio*z) = 0

yields:
Step_Ratio = Cone_Ratio / (iz - z*Cone_Ratio);

multiplying both top and bottom by (1/Cone_Ratio) becomes:
Step_Ratio = 1 / (iz/Cone_Ratio - z);


And that's it. Remember that in my implementation, the z term is already negative (so change the sign), and I store the sqrt(Cone_Ratio) in t.g, so I need to re-square it to recover the number I want. Once you have Step_Ratio, you multiply that by height and you're all done!

[Edited by - lonesock on January 31, 2006 3:55:07 PM]

OK, here is the shader code and Shader Designed project!
(EDIT: link REMOVED)(you'll need 7-Zip to open it, and again, if this get's popular I'd appreciate any mirrors!)

The preprocessing tool and source is included (you'll need the Corona image library to compile it). Just drag and drop some heightmap image files on the exe and it will do the rest. To get SD to run the shader you'll have to place the three step.* files into its "shaders" directory, and the 2 images rock*.* into the "textures" directory.

In the shader code, try the _fixed, _loop, and _exact versions of the functions to see how they behave/perform. Also, you can uncomment a section that will just show returned height in red (useful to spot problem areas, whatever).

Enjoy, and please hit me with any questions or improvements, whatever. All the code is under MIT license (unless you have any other favorites you'd like to request [;^)

[Edited by - lonesock on February 19, 2006 3:14:33 AM]

All this silly shader stuff..

Cant you just apply a heightmap to a wall the same way you can use a heightmap for terrain?

Therefore your walls actually have bumps and crevices in them?

@Shamino: of course...it's called displacement mapping, but that's another story [8^)

Sure you can do that but its gonna greatly increase the number of polygons needed to get this kind of detail. Since modern GPUs have so much pixel processing power its fairly efficient to just render a single quad using a technique like this compared to rendering that many polygons

Quote:

Original post by lonesock ...if this get's popular I'd appreciate any mirrors

I mirrored it here:
http://www.mganin.com/ConeStepMap.7z

@Code-R: Thanks so much for mirroring the file!

By the way, has anyone else gotten this to run in Shader Designer? Or even more wild, in their own apps? On my end this thing has only been tested on 1 video card and 1 OS with 1 piece of software, etc.

If someone would volunteer some feedback on the following items I'd really appreciate it!

* if/how it ran on different hardware (did you have to change the GLSL code to get it to compile)?
* how well did it perform on your machine (specs?), specifically compared to your own implementations of parallax and/or relief mapping?
* how did it look? (subjectively, how was it visually?)
* any obvious changes I can make to speed it up / improve it in any way?
* any problems with the pre-processor tool?

edit: And is the name OK? Should it be shortened to "Cone Mapping", or "Step Mapping", or something else entirely?

thanks,

[Edited by - lonesock on February 1, 2006 10:13:57 AM]

When I get some time I'm gonna try and implement this with DX and HLSL. Once I've got that working I'm gonna try it in Source. Thanks for releasing all the source code, it'll be very useful. [grin]

I've also put another mirror of the file up here.

Quote:

Original post by Monder When I get some time I'm gonna try and implement this with DX and HLSL. Once I've got that working I'm gonna try it in Source. Thanks for releasing all the source code, it'll be very useful. [grin] I've also put another mirror of the file up here.

Excellent! When you're done, would you mind releasing the HLSL code? I'm going to be doing a write-up of this method for GameDev and my website and it would be nice to reference your work for people in the DX side of development! BTW, how long before your HL2 mod is released? (You can be the first ever to release a game with "Cone Step Mapping! [grin])

You are welcome for the source. It was just such a cool idea, and I was so surprised that it worked, I had to share. Plus I'm just doing this as a hobby (though I think my work suffered a bit last week as I developed this [8^), so there is no reason for me to keep the source proprietary(sp?). I just hope that the method catches on, and then every game in the world will use it, and then I shall rule the Universe! (insert maniacal laughter here)

(Oh, it seems the shader link doesn't work, though the video one works fine still. Thanks for hosting!)

edit: I found a nicer adaptive step count for the intersect_cone_loop function. Use this:
for (int i = int(float(conesteps)*(0.5+iz)); i > 0; --i)
1st, it takes care of the casting, 2nd it averages (approx) to conesteps while still adapting to the overall angle of the view ray!

[Edited by - lonesock on February 1, 2006 11:54:50 AM]

Hmm I'm not entirely sure why that link isn't working, prehaps Gamedev's server doesn't like the 7z extension or something.

I'll release all the code once I've done a little DX demo, though I'm probably not going to manage to get round to that for a little while. I'll probably do a little write-up in my journal as well. As for the HL2 mod no idea when it's going to be release really, the webpage for it is here though there's not much to see atm.

that's really great idea, i'm sure it will rule the world.