19
$\begingroup$

There have been lots of papers over the years on different techniques for drawing height-field terrain in a ray-tracer. Some algorithms ray-march the grid directly (or via a quadtree); others transform the terrain into a polygon mesh and use a standard ray-triangle intersection test. The research seems to have moved on in the last few years, and it's hard to find papers written in the last decade, but the balance between memory and compute (both CPU and GPU) is still changing.

What kind of algorithm gives best performance on high-end desktop machines nowadays? Or if there isn't a single answer, how do the performance characteristics of the current best algorithms differ?

Improve this question
$\endgroup$
5
  • $\begingroup$ Screen-space reflections: create a height-field using the depth and frame buffer, ray trace it to get crude reflections. I don't know about the details, but I'd imagine Crysis, Killzone, lately Frostbite etc. will have used some sophisticated technique to get it fast. Have you looked into this? $\endgroup$
    – David Kuri
    Commented Nov 17, 2015 at 10:15
  • 1
    $\begingroup$ @DavidKuri Thanks, that's a good pointer for how to get the core ray-marching fast. There should be a lot of optimizations possible for a more static height-field that don't work so well on screen-space tracing, such as pre-computing mipmaps or a min-max quadtree, so I'm still hoping for an answer that covers that. $\endgroup$
    – Dan Hulme
    Commented Nov 17, 2015 at 10:38
  • $\begingroup$ Hey Dan BTW are you looking for CPU or GPU solutions? And real time or non real time rendering? $\endgroup$
    – Alan Wolfe
    Commented Nov 17, 2015 at 14:27
  • $\begingroup$ @AlanWolfe My use is GPU and non-real-time (i.e. max throughput rather than best image quality you can manage in 16 ms), but I'll still upvote interesting answers that are fast on the CPU or primarily for interactive renderers. $\endgroup$
    – Dan Hulme
    Commented Nov 17, 2015 at 14:46
  • $\begingroup$ You could try to create a signed distance field from the height map. Thats basically a 3d texture that stores the distance to the next surface. This allows to "travel the ray faster". Unreal Engine 4 uses this for mid-range ambient occlusion, soft shadows and terrain shadows in general $\endgroup$
    – user1888
    Commented Nov 17, 2015 at 15:34

3 Answers 3

Reset to default
13
$\begingroup$

For the current state-of-the-art, look for this paper: "Maximum Mipmaps for Fast, Accurate, and Scalable Dynamic Height Field Rendering", Tevs et al. 2008

The basic idea is to skip a lot of space by having knowledge of the maximum value over large areas of terrain. If the ray stays above that, skip to the next large area.

If you look at Figure 8, you'll see a comparison of basic linear stepping vs. maximum mipmaps. Linear stepping results in 200 steps, which can be done real-time on modern gpus but is still actually slow. Max mipmaps do the same in about 10 steps, all in shader.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Have you found any demos with Maximum mipmaps? Thanks. $\endgroup$
    – Jón Trausti Arason
    Commented Feb 14, 2017 at 15:31
  • $\begingroup$ I haven't read the paper, but this "maximum mipmaps" sounds very similar to the technique used for Cone Step Mapping (which improves over parallax occlusion mapping by skipping large areas thanks to cones). $\endgroup$
    – Julien Guertault
    Commented Oct 27, 2017 at 3:35
  • $\begingroup$ @JulienGuertault I would say this is plain HiZ tracing. it's a safe method to be sure of what you hit. But not very fast compared to unsafe methods like binary search. $\endgroup$
    – v.oddou
    Commented Oct 30, 2017 at 2:46
4
$\begingroup$

The best I've personally seen is the stuff inigo quillez does, which is used in demoscene stuff. Ray March the terrain, taking larger steps the farther you get from the camera since (usually) detail matters less at a distance (exception = thin walls!). He uses penetration info and other easily gotten metrics to simulate ambient occlusion and other sophisticated lighting techniques.

Here's a demo of the stuff in action: https://www.youtube.com/watch?v=_YWMGuh15nE

And here is IQ's page on the terrain raymarching which is a pretty interesting read: http://www.iquilezles.org/www/articles/terrainmarching/terrainmarching.htm

BTW, in modern games, the technique of "screen space reflection" often is just a ray march against the Z buffer of the rendered scene. The Z buffer is really just a heightfield.

I saw some talks on this at siggraph 2014, and while some of the people were using similar techniques as IQ, a few were doing things not even as well as IQ, which was interesting to see :P

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ The algorithm in your link is very simple. It looks less sophisticated than some of the papers I found from the nineties. It looks like a good starting point, but I'm hoping for the highest-performance solution for a production system, not just a "my first raytracer". $\endgroup$
    – Dan Hulme
    Commented Nov 17, 2015 at 8:35
  • $\begingroup$ This stuff is used in demoscene code and screenspace reflections in the most advanced modern games. The fastest code is sometimes the simplest. I wouldn't dismiss it due to its simplicity. It'll be interesting to see if you get any other responses though. $\endgroup$
    – Alan Wolfe
    Commented Nov 17, 2015 at 14:18
  • 2
    $\begingroup$ What's missing in your response is that IQ uses a standard heightfield mesh as an initial guess to kickstart raymarching the actual terrain. He first renders a low-poly version of the terrain using standard rasterization, and then runs a pixel shader over the image that starts raymarching at the rasterized depth minus some conservative threshold. This is the only way to actually make this realtime. $\endgroup$
    – Benedikt Bitterli
    Commented Nov 17, 2015 at 19:23
  • $\begingroup$ I believe that only part of what you are saying is true. he does use heuristics based on terrain height (along with distance from camera) to come up with how far the ray can march, but as far as i have heard, he doesn't use rasterization. Here is an example of his work, which does not use rasterization, but that isn't to say that there aren't implementations that DO use rasterization: shadertoy.com/view/MdX3Rr $\endgroup$
    – Alan Wolfe
    Commented Nov 17, 2015 at 19:27
  • $\begingroup$ I'm a little confused that the question is about ray tracing, and this answer is about ray marching. There is a fundamental difference between the two and what they can achieve. $\endgroup$
    – Julien Guertault
    Commented Nov 19, 2015 at 12:35
4
$\begingroup$

Cone Step Mapping and Relaxed Cone Step Mapping appear to be very decent algorithms. These rely on a bit of preprocessing of the height field to create a 2D map used for more efficient lookups.

http://www.lonesock.net/files/ConeStepMapping.pdf https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch18.html

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.