pouët.net

Is there any way to make a distance table or function, without using a 3D texture?

that shoud help a bit... http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter08.html

It doesn't... they use 3D textures.

I'm not sure about your question... If you mean "is it possible to perform a raymarching algo on a 2D-heighmap without using a precalculated 3D-distance-map based on this 2D-heighmap?"... well, I have never tested it and I might be wrong, but I suspect the code to be too much gpu intensive on a per-pixel shading : every pixel should have to recalculate the distance map from the heighmap, even if nearby pixels will in fact be using the same distance map calculated values...

[url]http://en.wikipedia.org/wiki/Distance_transform[url]

There are very fast and good approximations on this in O(n). There is also an exact solution in O(n), but by my tests it doesn't help so much rendering speed but the precalc time is longer and the algorithm is far more complex.

In elevated they choose another approach : precompute the heighmap with a regular triangle-mesh rendering... and apply a final texturing once the distance is computed, enabling to achieve it in realtime.

Instead of having a 3D-distance map, they let the GPU calculate the exact distance for each pixel, avoiding a costly and unnecessary raymarching algo...

It's more like "is there another aproach instead of having a 3D texture", an approach that uses less memory. Some property that I was missing... with an heightmap you have the distance to the ground, you could have the nearest distance from the ground to some sort of feature that would give you a good enough step approximation.

Oh, and, in software rendering it speed ups a lot, but of course it depends on the terrain properties. I don't know about gpu rendering, but probably it is not going to be as good as optimization as in software rendering.

Oh, now I see what you mean... I'm doing not the same...

I still don't get it, are we talking about a 2D height-map or a 3D height-map? Because you can't approximate cavities and other features not pertaining to the surface of your height-map if you are talking about a non-3D, light-weight, non-generative, approximative storage of height-map derivatives and their relative, respective distances.

xernobyl, you could probably compute a local distance map working on a small kernel of the 2D heighmap (like 4x4 pixels)... around the current "camera" pixel. This approach would result in more "marching" steps but would save the cost of building a 3D distance map...

Decipher, indeed It's not possible to reconstitute cavities from a 2D heighmap... as I understand xernobyl question, he is talking about the process of calculating a 3D distance map from a 2D heighmap (textured or calculated). This 3D distance map that enable to perform a correct ray marching other the heighmap... (as it is explained in the GPU Gems2 article)...

@decipher: Z(X,Y) = heightmap, and D(X,Y,Z) = distance table.
And I don't want a fucking huge D table with w*h*256*sizeof(float) bytes.

It's not that I don't want it, but I was just wondering if there's a lower memory solution.

And I know that it isn't that much memory for today's machines, that have at least 4GB of ram, and 1GB of video ram.

@lx: I think the only problem with your approach is, if there's no immediate storage for this 4x4 kernel then a fragment calculated within another kernel won't be able to occlude or cast-shadows on the current fragment, which means incorrect lighting.

If we were to store the kernel then he might as well just load the texture :).
On the other hand, there really is no benefit of slicing the calculations as the distance information has to be somehow generated from the 2D height-map in realtime. He might as well brute-force :).

PS: I hope I got your technique right.

So you want a table as end result, but you don't want to use the memory for it? ;)
If you just want to raymarch, you can get along with a little lower distance estimate, as long as the slopes are limited. Doing many simple steps can easily be faster than fewer expensive.
If you really want the right distance from a point, you could make a maximum-filtered mipmap chain and do some quadtree like traversion within in the sphere defined by the distance straight down.

@Decipher, yep the kernel idea was a bad technique/vocabulary "transposition"... in fact, the main idea is to compute only the distance from the heighmap along the projected 2D camera ray... performing a "coarse grain" distance map from the 2D heightmap... then it depends on the granularity of the heighmap.... It would probably worth to work on a heighmap with a lower LOD, to perform the coarse grain distance map, and gradually use higher lod...
But this has to be tested... I'm not sure there is a definitive algo for such a problem...

@lx: Sounds like you and Psycho are actually talking of pretty similar things :).

I guess Psycho has formulated much better than me what I was meaning... ;)

@Decipher... hehe, exactly :D

texel: Linear speed exact distance transforms aren't that complicated. Sure the math behind "Distance Transforms of Sampled Functions" (Felzenszwalb et al.) might be a bit tricky to grok, but my implementation cooked down to around 30 LOC. And "dead reckoning" is pretty much trivial - I'd say it's even simpler to grok than most approximations ;)

Are you looking for something like anistotropic cone mapping ? I think olivieras work at UNC might be applicable... transform the heightmap to a cone map before rendering so the lookup into the texture map gives distance that can be stepped?

assuming the max slope in the terrain is M, you can compute a conservative cone on the fly and compute the biggest safe step size like this:



h is the height difference between your camera and the heightmap at current camera position. dy is the y (vertical) component of the ray direction, and dx = sqrtf( dx*dx+dz*dz ) the horizontal component of the ray direction. Speeds up quite a lot compared to constant size/distance unaware raymarching.