[my blog] [my software] [contacts]

back to today
 

8 april 2012

Sunset on the sea experiment

(Updated on 14 April 2012: added a paragraph about step 2 and fixed the example code)

Let's say it's Easter and the weather sucks.
You'd like to be beside the seaside, watching a beautiful sunset but...
The wind is blowing, the sea is quite far and you are lazy.

If you are like me you start coding a digital version of it. I know, there's not much people like me :)

Jokes aside, I was thinking about terrain rendering through raymarching with distance fields (also known as sphere tracing). The nice thing about this technique is that you can render almost any function and shade it just like you would do with raytracing. In other words, it's fast and easy to code (at least if you stick to the basics) and it's fun to play with it.
The results can be absolutely stunning, as the famous 4KB intro Elevated taught us in 2009.

If your browser supports WebGL you can watch my "Sunset on the sea" experiment
and play with the code directly in your browser on GLSL Sandbox:
Sunset on the sea v.1.0.1
(original version here)



And here is how it works...

If you need an introduction on raymarching, the best site where you can go is the one by I. Quilez, where you can find a useful presentation on this technique and some ideas about terrain rendering.

Rendering a terrain (or the sea in this case) by using distance fields is, computationally wise, almost the worst-case scenario, as the primary rays have to travel near the surface, producing a very high number of iterations, as you can see in the image below.



I decided to avoid recurring to existing solutions and think by myself on a way to solve this problem.
After trying some different ideas I settled for the following algorithm, that you must apply to each ray casted from the camera:
  1. Intersect the ray with a imaginary plane placed just above the sea (simple and fast raytracing technique).
  2. Raymarch by the maximum between the distance function and a fixed step size.
  3. As soon as you detect that you have stepped inside the sea bisect in this last interval until you are within a desired error threshold.




As you can see in the picture above, this algorithm is a lot faster and, if well tuned, can be quite accurate.

The purpose of step 2 is to find a rough interval where lies the first intersection between the ray and the sea. Note that a ray may intersect the sea in many different places (the front and the back of the same wave for example) but we are interested only in the nearest intersection.
In order to detect this first intersection we may use regular raymarching. This works well when a ray is distant from waves and when it's almost perpendicular to the surface, but becomes very slow when rays are almost parallel to the sea surface (as shown in the first graph).
Proceeding by fixed steps avoids this problem, but is less optimal than regular raymarching in some cases.
We can combine these two approches and get the best of each one. We can simply proceed by the maximum between the fixed step and the distance from the objects.
Additionally, I found that slightly increasing at each iteration the size of the fixed step works even better.

In step 3 of the algorithm I mentioned the bisection method. The idea is that you have two points: one over the surface and more near to the camera that we call "distMin" and one below the surface and more distant that we call "distMax".
Remember that determining if a point is over or below the surface in raymarching is as simple as determining if the distance function is greater or lower than zero.
The bisection algorithm that you would normally apply is something like this:

for (int i = 0; i < MAX_STEPS; i++) {
    distMid = distMin + (distMax - distMin) / 2.0;
    distFromObjects = map(ray_start + ray_dir * distMid);
    if (abs(distFromObjects) < PRECISION_LIMIT) return distMid; // Enough precision, stop
    if (distFromObjects > 0.0) {
        // distMid is outside the sea, then we can increase distMin
        distMin = distMid;
    } else {
        // distMid is inside the sea, then we can decrease distMax
        distMax = distMid;
    }
}
return distMid;


To this algorithm I applied a nice little optimization: as you are already computing the distance function for distMid at each step, you can use this information to further reduce the interval you are considering, then you can change the code above to the following one (differences in red):

for (int i = 0; i < MAX_STEPS; i++) {
    distMid = distMin + (distMax - distMin) / 2.0;
    distFromObjects = map(ray_start + ray_dir * distMid);
    if (abs(distFromObjects) < PRECISION_LIMIT) return distMid; // Enough precision, stop
    if (distFromObjects > 0.0) {
        // distMid is outside the sea, then we can increase distMin
        distMin = distMid + distFromObjects;
    } else {
        // distMid is inside the sea, then we can decrease distMax
        distMax = distMid + distFromObjects; // Note: distFromObjects is negative here
    }
}
return distMid;


A graphical representation of this idea (the numbers 1, 2 and 3 represent the order of the bisection steps):



Another little optimization i could think of is in the "gradientNormalFast" function.
In raymarching you generally retrieve normals by computing the gradient from six different points near the point you are considering. In this case I could use a less accurate version where I only compute three of these values.
 
2012-04-14 18:10:20
Dan Brickley wrote:
Great to see this written up so nicely!

Unfortunately it crashes Firefox on my MacBook Pro (and forces Safari to reboot). I've reported to a friend at Apple. This happens occasionally with a shader on glsl sandbox though most work. Graphics card info copied below for info, in case you've any idea.

AMD Radeon HD 6750M:

Chipset Model: AMD Radeon HD 6750M
Type: GPU
Bus: PCIe
PCIe Lane Width: x8
VRAM (Total): 1024 MB
Vendor: ATI (0x1002)
Device ID: 0x6741
Revision ID: 0x0000
ROM Revision: 113-C0170L-573
gMux Version: 1.9.23
EFI Driver Version: 01.00.573

2012-04-14 20:05:37
H3-r3 wrote:
Thanks Dan :)

Seems like on OS X there are some problems with complex GLSL shaders.
Maybe there's some bug in the OpenGL drivers.
I got similar error reports some time ago for another shader:
http://www.postronic.org/h3/pid59.html

I don't have a Mac so I can't reproduce it, I hope they will fix it.


2012-05-05 08:41:09
Phil wrote:
Awesome thinking here. I'm wondering -- as soon as you have other raymarched geometry in the scene, say some balls in the water or some birdy thingies just atop of it, this optimization could no longer be used, right?

2012-05-05 14:12:58
H3-r3 wrote:
Thanks Phil :)

With some little modifications these optimizations could still be used, you could simply have two distance estimation functions:
1) The sea distance function
2) The distance function for all the other objects

You could do regular raymarching, marching by the minimum between these two functions.

In order to have reflections on the water one optimization should be removed: currently all rays pointing up are discarded, this would prevent having these reflections and should be removed at least for secondary rays.

2012-05-10 05:58:11
Phil wrote:
I tried to implement this but weren't getting anywhere and admittedly didn't fully grok it in all its glory.

So I tried with a simplified understanding of this:

1. intersect the ray *once* with both the flat plane that's just on top of the highest possible elevation, and the flat plane that's just below the lowest possible elevation. Two flat planes intersected just once as per classical ray-plane intersection test returning distance to intersection point.

2. If both distances are < 0, don't proceed at all of course. The ray never even potentially intersects the "terrain".

3. Otherwise, classical raymarch but not until the usual fMaxDist (whether this may be 30 or 300 or as in my case 3000000) but only the distance returned by the intersection test (more like the max of both distances returned). Then stop marching.

This is equivalent to "finding the interval within normal marching happens", no?

This gives an OK little speedup -- from 32-36fps without the optimization I'm now getting 48-52fps. Very nice, but not massive. I'm wondering if I'm missing something else? I'm not really "bisecting" anything as far as I'm aware, just normal marching, could that be it? If so, then I'm not getting what it is you're doing exactly in step 3. that isn't already provided by step 2 (normal raymarching) or how it speeds things up... got a hint for me what I'm missing? ;)

Btw I did study the sources of course. But still having a brain-block here :D

2012-05-11 05:47:27
Phil wrote:
Ah my above isn't quite complete:

Just before step 3 -- *if* rayPos.y is above upper plane or below lower plane, position at intersection point and march from there, and set maxDist to distance from intersection of the *other* plane.

Works pretty fine. Still wondering if I'm missing out regarding all that bisection stuff though =)

2012-05-12 16:23:03
H3-r3 wrote:
In your approach you are currently getting these two optimizations:

1. You are not marching rays that don’t hit the surface
2. You are skipping some initial raymarching steps thanks to the ray/plane intersection

So you are basically implementing something similar to my “step 1”.

In “step 2” I was not doing regular raymarching with a distance field. What I was doing is raymarching using the maximum between the distance field and a fixed value. This fixed value should be the highest possible value that does not miss the first intersection between the ray and the surface.
The consequence is that “step 2” is faster but only gives you a coarse interval for the intersection point. This is why “step 3” is needed: “step 3” is used to refine the rough result of “step 2”.

2012-05-12 16:24:17
H3-r3 wrote:
Another unrelated note: if your surface is axis-aligned, you can make some optimizations for “step 1”, for example, if the surface is perpendicular to y axis you can do these tests:

1. If (ray_start.y > surfaceHighestY && ray_dir.y >=0) discard the ray
2. If (ray_start.y < surfaceLowestY && ray_dir.y <=0) discard the ray

This way you have to do only one check in most cases. In my shader I was doing only test 1 because I knew that all the rays were started from above the surface.

2012-05-12 16:27:59
H3-r3 wrote:
In general the main trick is that you don’t really have to always raymarch by a distance field.
For example if you have a very complex distance-field function and you find a way to remove some heavy computations from this function ending up with a new function that gives you a higher estimate of the distance instead of the real distance, you could use this modified function for your raymarching. You would end up having more iterations, but if each iteration is a lot faster, then the overall loop could be faster.


In order to have a scene with standard objects and a terrain I would try implementing something like this:

for each raymarching step {
__ distanceToTerrain = 99999999999. // init with max possible value
__ calculate distanceToObjects // using regular distance-field functions, do not consider the terrain
__ if (point outside the two terrain-bounding-planes) {
______ calculate distanceToNearsetPlane
______ if (distanceToObjects > distanceToNearestPlane) {
__________ calculate minTerrainDistance and maxTerrainDistance using my “step 2” algorithm
__________ if (distanceToObjects > minTerrainDistance) {
______________ calculate distanceToTerrain using my “step 3” algorithm
__________ }
______ }
__ }
__ ray-march by min between the two distances: dist += min(distanceToObjects, distanceToTerrain)
}

2012-05-17 11:00:33
Phil wrote:
Thanks a lot for going into more detail with this! I will try to re-feed the brain with this once again shortly =)

2014-03-18 10:30:17
Nsssuofdvi wrote:
Bkfqsqptuspojd, ddusptysvz , [url=http://www.wejxywwoiq.com/]nbmgfdwghw[/url], http://www.mivnxovilf.com/ ddusptysvz

You can leave a comment

name:
comment:
Links:
Feeds:
XML Blog feed (RSS)
XML Comments feed (RSS)