So, what do distance field equations look like? And how do we solve them?
category: code [glöplog]
iq, could you please explain why we should not march the whole distance but only a small fraction of it? My logic says that the whole distance should be OK and is the right thing to do...
It depends on how you construct your implicit function. If it's actually tracking normalized distances and you're only using Euclidean transformation (rotations/reflections+translations), you can walk the whole way. But for the given example, the absolute value of the implicit function doesn't actually denote distances anymore. Moving by a small amount along the y axis will yield a different rotation and hence result in a different distance along x and z as well.
For the given example, it's probably easiest to see what's happening in cylindrical coordinates. At any point in space, dPhi/dy=1 (here using y to stay with the source code, instead of the more customary z for cylindrical coordinates). As a result, distances in the regular cartesian world space (where you're tracing your rays) don't agree with distances in the deformed object space: If you plot the object-space shortest path between two points on the surface in world space, you'll get a helix. The world-space shortest path between them is a line, and the helix is a detour.
You need to compensate for the path distortion to make sure you don't ever overestimate distances (which would cause you to overshoot). For the example, any step size smaller than 1/sqrt(2) (so ca. 0.707) should do. With stronger distortion, this value will be smaller; if you rotate by c*y but keep the rest of the setup the same, it should be 1/sqrt(1+c^2) unless I'm missing something.
As long as you underestimate the distances you're fine (you're just converging more slowly), but if you overestimate them you can screw up and miss the root you're looking for.
For the given example, it's probably easiest to see what's happening in cylindrical coordinates. At any point in space, dPhi/dy=1 (here using y to stay with the source code, instead of the more customary z for cylindrical coordinates). As a result, distances in the regular cartesian world space (where you're tracing your rays) don't agree with distances in the deformed object space: If you plot the object-space shortest path between two points on the surface in world space, you'll get a helix. The world-space shortest path between them is a line, and the helix is a detour.
You need to compensate for the path distortion to make sure you don't ever overestimate distances (which would cause you to overshoot). For the example, any step size smaller than 1/sqrt(2) (so ca. 0.707) should do. With stronger distortion, this value will be smaller; if you rotate by c*y but keep the rest of the setup the same, it should be 1/sqrt(1+c^2) unless I'm missing something.
As long as you underestimate the distances you're fine (you're just converging more slowly), but if you overestimate them you can screw up and miss the root you're looking for.
Thanks ryg! :)
I think i've posted this before in one of the many "why the hell does my tracing fail when I'm distorting my objects"-threads, but here's a picture supplement ryg's explanation:
As you see, the phenomenon appears in two dimensions too when trying to measure the distance to a distorted quad. The distortion in question here is a simple shear transformation $sh$ that preserves horizontal lines.
As you see, the phenomenon appears in two dimensions too when trying to measure the distance to a distorted quad. The distortion in question here is a simple shear transformation $sh$ that preserves horizontal lines.
The important thing to realize is that distance field raymarchers are fucking boring and repetitive shit, and that you should do something interesting instead. But the technique is certainly useful for other purposes (like non-sucky AO).
kusma: <3
lol kusma, is it the only excuse that you found out, loser? :D
i'm with kusma. unless you do something a bit more elaborated than twisted cubes or perlin-noised planes, stop the raymarching plague, please.
I'll do as I please.
hehehe
glad to hear you haven't figured out how to render meshes using raymarching...
but honnestly i don't care what iq thinks..
or actually, i don't care what anyone thinks at pouet.net... :D
FU when you have NOTHING you have NOTHING TO LOSE!!!
I was thinking about how to improve efficiency today, and I had the thought of tracing with a stretched sphere bound, stretched along the direction of the ray, to avoid inefficient cases like where the surfaces are roughly parallel to the ray. I returned to reading the zeno.pdf paper and only found the Lipschitz factor for uniform scaling. So I did a search for "lipschitz constant for nonuniform scaling" and found the following jch paper.
iq, have you read this other paper of John C. Hart?
"Sphere Tracing: Simple Robust Antialiased Rendering of Distance-Based Implicit Surfaces"
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.8663
It appears to be an earlier (1993) draft of the 1996 zeno.pdf paper. What's interesting is that he mentions tracing with ellipsoids in his "Further Research" section:
"One particularly nasty problem that arose from this research was the derivation of the exact distance to an ellipsoid, which resulted in a sixth degree polynomial! Being able to find the exact distance to a non-uniformly scaled object, such as an ellipsoid, can increase the efficiency of sphere tracing. Consider a collection of objects and a ray and a scaling deformation that leaves invariant the plane intersecting the ray origin perpendicular to the ray direction. Take the scaling factor of this non-uniform scale to the limit. Then the exact distance from the ray origin to the deformed version of each object is the distance to the first ray intersection with each object. Hence, sphere tracing would converge to the first ray intersection after a single application of each of the implicit functions."
What are your thoughts.
iq, have you read this other paper of John C. Hart?
"Sphere Tracing: Simple Robust Antialiased Rendering of Distance-Based Implicit Surfaces"
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.8663
It appears to be an earlier (1993) draft of the 1996 zeno.pdf paper. What's interesting is that he mentions tracing with ellipsoids in his "Further Research" section:
"One particularly nasty problem that arose from this research was the derivation of the exact distance to an ellipsoid, which resulted in a sixth degree polynomial! Being able to find the exact distance to a non-uniformly scaled object, such as an ellipsoid, can increase the efficiency of sphere tracing. Consider a collection of objects and a ray and a scaling deformation that leaves invariant the plane intersecting the ray origin perpendicular to the ray direction. Take the scaling factor of this non-uniform scale to the limit. Then the exact distance from the ray origin to the deformed version of each object is the distance to the first ray intersection with each object. Hence, sphere tracing would converge to the first ray intersection after a single application of each of the implicit functions."
What are your thoughts.
bodigital:
we had that in another thread ( one of em "few" about this topic floating around here ) already.
it doesnt help at all if you ask me, considering the overhead per pixel to find the correct ellipsoid ! ( while having a 3-dimensional-rotating-camera and stuff , atleast for pixel-shaders )
thanx for linkage tho ! :)
we had that in another thread ( one of em "few" about this topic floating around here ) already.
it doesnt help at all if you ask me, considering the overhead per pixel to find the correct ellipsoid ! ( while having a 3-dimensional-rotating-camera and stuff , atleast for pixel-shaders )
thanx for linkage tho ! :)
glad you don't care, pulu. that's rule number 1
bodigital, i did the distance to an ellipse, and resulted in a cubic (which thankfully can be resolved analytically, but by means of branching and trigonometric functions :( ), so i'm not surprised the ellipsoid is a 6 degree thing. even the distance to a cubic curve (spline, bezier) is unsolvable. damn the maths, we are in the stone age for some things.
bodigital, i did the distance to an ellipse, and resulted in a cubic (which thankfully can be resolved analytically, but by means of branching and trigonometric functions :( ), so i'm not surprised the ellipsoid is a 6 degree thing. even the distance to a cubic curve (spline, bezier) is unsolvable. damn the maths, we are in the stone age for some things.
ha, i found it in a dark corner of my hd!!
(ea,eb) are the radii of the ellipse (which is centered in the origin and aligned to the xy axes). The (x,y) params are your point in the (+,+) cuadrant, and (ex, ey) the resulting closest point in the ellipse.
It took me few hours to make the code, but never used it in the end, so I don't guarantee it works in all situations.
For an ellipsoid, go numerical.
Code:
void closestPointInEllipse( float *ex, float *ey, float ea, float eb, float x, float y )
{
const float k = eb*eb - ea*ea;
const float a = ea*x/k; const float a2 = a*a;
const float b = eb*y/k; const float b2 = b*b;
const float c = (a2 + b2 - 1.0f)/3.0f; const float c3 = c*c*c;
const float q = c3 + b2*a2*2.0f;
const float d = c3 + b2*a2;
const float g = a + a*b2;
float co;
if( d<0.0f )
{
const float p = acosf(q/c3)/3.0f;
const float m = cosf(p);
const float n = sinf(p)*sqrtf(3.0f);
const float rx = sqrtf( -c*(m + n + 2.0f) + a2 );
const float ry = sqrtf( -c*(m - n + 2.0f) + a2 );
const float s = rx + g/(rx*ry);
co = ( ry + (k>0.0f?rx:-rx) + fabsf(g)/(rx*ry) - a)/2.0f;
}
else
{
const float h = 2.0f*a*b*sqrtf( d );
const float s = powf( q+h, 1.0f/3.0f );
const float u = powf( q-h, 1.0f/3.0f );
const float rx = -s - u - c*4.0f + 2.0f*a2;
const float ry = (s - u)*sqrtf(3.0f);
const float rm = sqrtf( rx*rx + ry*ry );
const float p = ry/sqrtf(rm-rx);
co = (p + 2.0f*g/rm - a)/2.0f;
}
if( co>1.0f ) co=1.0f;
const float si = sqrtf( 1.0f - co*co );
ex[0] = ea*co;
ey[0] = eb*si;
}(ea,eb) are the radii of the ellipse (which is centered in the origin and aligned to the xy axes). The (x,y) params are your point in the (+,+) cuadrant, and (ex, ey) the resulting closest point in the ellipse.
It took me few hours to make the code, but never used it in the end, so I don't guarantee it works in all situations.
For an ellipsoid, go numerical.
I'm having trouble calculating the normal... Can someone post some code or something ^_^
örm, sure.
Where: e is a virtual epsilon. Something like 0.0001 works well, though it really depends on your geometry and your taste. n is the normal that we're calculating, ƒ(∂) is your distance field function, p is the current point of evaluation and the notation {k, l, m} signifies a threefold vector.
I hope this helps.
Code:
float e = …;
vec3 n = vec3(ƒ(p + {e, 0, 0}) - ƒ(p - {e, 0, 0}), ƒ(p + {0, e, 0}) - ƒ(p - {0, e, 0}), ƒ(p + {0, 0, e}) - ƒ(p - {0, 0, e}));
n = normalize(n);
Where: e is a virtual epsilon. Something like 0.0001 works well, though it really depends on your geometry and your taste. n is the normal that we're calculating, ƒ(∂) is your distance field function, p is the current point of evaluation and the notation {k, l, m} signifies a threefold vector.
I hope this helps.
Thanks Decipher! That totally helped.
@p01 Yea I saw that trick, but I need the normal to calculate AO. I think...
I'm also having trouble getting AO to work... I'm going for IQs aprroch from his presentation. "Sample the distance field at a few points around p" OK "And compare the result to the actual distance to p" huh?
I think its funny that it requires LESS calculations to get AO than to get the normal :3
@p01 Yea I saw that trick, but I need the normal to calculate AO. I think...
I'm also having trouble getting AO to work... I'm going for IQs aprroch from his presentation. "Sample the distance field at a few points around p" OK "And compare the result to the actual distance to p" huh?
I think its funny that it requires LESS calculations to get AO than to get the normal :3
That's why that kind of AO is so brilliant, it's cheap and looks good :)
@Mewler: Less code, probably, but not really less calculations :)
extra note on normals, you probably want to make epsilon dependent on the distance from the intersection/shading point to the camera (this reduces aliasing, especially when using high frequency geometry or normal mapping). Elevated uses an epsilon proportional to that distance.
where calcNormal() is pretty much Decipher's function up there (plus bump mapping perhaps)
Code:
float t = intersect( ro, rd );
vec3 p = ro + t*rd;
float e = t*k; // k depends on screen resolution and camera FOV
vec3 n = calcNormal( p, e );
where calcNormal() is pretty much Decipher's function up there (plus bump mapping perhaps)