<p>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.</p>

<p>Here's a demo of the stuff in action:
<a href="https://www.youtube.com/watch?v=_YWMGuh15nE" rel="nofollow">https://www.youtube.com/watch?v=_YWMGuh15nE</a></p>

<p>And here is IQ's page on the terrain raymarching which is a pretty interesting read:
<a href="http://www.iquilezles.org/www/articles/terrainmarching/terrainmarching.htm" rel="nofollow">http://www.iquilezles.org/www/articles/terrainmarching/terrainmarching.htm</a></p>

<p>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.</p>

<p>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</p>

CC BY-SA 3.0
2018-03-13T15:52:41.167Z
@BenediktBitterli What? Isn't everything done through the fragment shader?  He's got some of this stuff on shadertoy, you can't make a "low poly version" of this because you don't have access to the fragment shader or any geometry in the first place...
Krupip
CC BY-SA 3.0
2015-11-17T08:35:18.037Z
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".
Dan Hulme
CC BY-SA 3.0
2015-11-17T14:18:41.427Z
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.
Alan Wolfe
CC BY-SA 3.0
2015-11-17T19:23:46.443Z
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.
Benedikt Bitterli
CC BY-SA 3.0
2015-11-17T19:27:12.690Z
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:  https://www.shadertoy.com/view/MdX3Rr
Alan Wolfe
CC BY-SA 3.0
2015-11-19T12:35:05.170Z
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.
Julien Guertault
CC BY-SA 3.0
2015-11-19T14:46:45.220Z
If you notice, the question mentions ray marching (through a grid) as an example algorithm that he has read about in the past.
Alan Wolfe
CC BY-SA 3.0
2015-11-16T18:19:51.997Z
2015-11-16T19:00:24.480Z
2015-11-16T19:00:24.480Z
Alan Wolfe
<p>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.</p>

<p><a href="http://www.lonesock.net/files/ConeStepMapping.pdf" rel="nofollow noreferrer">http://www.lonesock.net/files/ConeStepMapping.pdf</a>
<a href="https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch18.html" rel="nofollow noreferrer">https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch18.html</a></p>

CC BY-SA 3.0
2016-06-10T14:16:48.143Z
2017-10-26T10:32:07.660Z
2017-10-26T10:32:07.660Z
cbuchner1
<p>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</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2017-02-14T15:31:06.090Z
Have you found any demos with Maximum mipmaps? Thanks.
Jón Trausti Arason
CC BY-SA 3.0
2017-10-27T03:35:22.803Z
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).
Julien Guertault
CC BY-SA 3.0
2017-10-30T02:46:17.023Z
@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.
v.oddou
CC BY-SA 3.0
2016-02-05T08:07:12.037Z
2016-02-05T08:07:12.037Z
Rama
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2015-11-17T10:15:27.807Z
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?
David Kuri
CC BY-SA 3.0
2015-11-17T10:38:27.833Z
@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.
Dan Hulme
CC BY-SA 3.0
2015-11-17T14:27:43.217Z
Hey Dan BTW are you looking for CPU or GPU solutions? And real time or non real time rendering?
Alan Wolfe
CC BY-SA 3.0
2015-11-17T14:46:44.920Z
@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.
Dan Hulme
CC BY-SA 3.0
2015-11-17T15:34:12.997Z
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
user1888
<raytracing><height-field>
What's the current state-of-the-art algorithm for ray-tracing height-fields?
Dan Hulme
# What's the current state-of-the-art algorithm for ray-tracing height-fields?

(Asked by: username_0 on 2015-11-16)

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?

**Tags:** raytracing, height-field

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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.  
> **username_2**: Hey Dan BTW are you looking for CPU or GPU solutions? And real time or non real time rendering?  
> **username_0**: @username_2 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.  
> **username_3**: 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  

---

## 3 answers

### Answer by username_8 on 2016-02-05. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_9**: Have you found any demos with Maximum mipmaps? Thanks.  
> **username_6**: 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).  
> **username_10**: @username_6 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.  

---

### Answer by username_2 on 2015-11-16. Score: 4

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

> **Comments:**
> **username_0**: 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".  
> **username_2**: 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.  
> **username_5**: 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.  
> **username_2**: 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:  https://www.shadertoy.com/view/MdX3Rr  
> **username_6**: 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.  
> **username_2**: If you notice, the question mentions ray marching (through a grid) as an example algorithm that he has read about in the past.  
> **username_4**: @username_5 What? Isn't everything done through the fragment shader?  He's got some of this stuff on shadertoy, you can't make a "low poly version" of this because you don't have access to the fragment shader or any geometry in the first place...  

---

### Answer by username_7 on 2016-06-10. Score: 4

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>


---

