pouët.net

Raymarching Beginners' Thread

category: code [glöplog]
las: If you had slightly longer variable names and perhaps a comment or two this would be quite a good code example ;) (eg. the main loop with the cone tracing optimisation is a bit hard to understand if you don't already know what it does)
added on the 2011-07-07 11:42:58 by kb_ kb_
But it would be way less 1337 then.
added on the 2011-07-07 13:46:48 by doomdoom doomdoom
Lord Graga: Yes. Try it. Remove the abs ;)
added on the 2011-07-07 16:21:01 by las las
Quote:

@las: Your using DX now? How is it, faster?

Yes. Yes, depends. ;)
added on the 2011-07-07 16:39:55 by las las
Quote:
iq, is your notation defined somewhere ?


http://en.wikipedia.org/wiki/Inner_product_space

it's the standard and only notation to define inner and dot products... introduced at school or college, the one everybody uses. don't you remember anymore?

also, I can copy from the other thread:

Quote:

<A,B> is the dot (inner) product of A and B. <A,B> = dot(A,B) = A·B
|A| is the length of A, such that |A|² = <A,A>.


Quote:
Also is it just me, or 99% of the math found on the web is anything but self evident because of the extreme use of shorthand and no context definition.


of course you need context, you are not going to rebuild mathematics from scratch and its basic axioms every time you want to express something, are you? if you don't assume A context, you cannot speak and communicate with others like in maths, english, music, and any language... don't you?
added on the 2011-07-07 21:01:22 by iq iq
It might be because of my lack of background but 2<> din't jump at me as "The square root of the dot product of ..."
I would have written (A.B)^1/2

But I do like your notation and my question was genuine, if I'm going to give solving intersection myself, I want to follow some well defined notation. (not of just a dot product, but of the comprehensive set)

My other rant (not related to your vector math example) was in reference to what I read on the web, it doesn't seem well defined.
M(A^B), (A*B)*m, AxB*m, ...
And, most importantly, not labeling variable.

So I'm not looking for proof, but to read something without ambiguity.
The math I see seem to be written using the person own 'dialect' using short hand notation and omitting vital labeling needed for a solid understanding.
"Why should I tell the reader what Q is, its self evident, isn't it?"

BTW, my first interest was to solve ray/cylinder intersection... instead I used a bounding volume and use the distance formula :)
I tweaked the raymaching loop to bail if the distance from one step to the other is not smaller.
The result is so encouraging, that I dont think I'm going to add new ray traced primitives to my code.

added on the 2011-07-08 00:44:25 by T21 T21
hey, T21, this is how you solve a ray-cylinder intersection by using only vectors and no coordinates. It's written in Spanish, but you can probably follow the logic?

http://www.iquilezles.org/blog/?p=732

Sumarizing, you get your t by solving the quadratic equation

k2·t² + k1·t + k0 = 0

with

k0 = |oc|² - <oc,a>² - r²
k1 = 2·<oc,d> - 2<oc,a>·<d,a>
k2 = 1 - <a,d>²

where o is the ray origin, d is the ray direction, c is the base point of the cylinder and a is the orientation axis of the cylinder. YES, it works for arbitrarily oriented cylinders, not only axis aligned. It's the beauty of not having coordinates nor axes, just vectors. Yay!

By the way people, some months ago I asked people with experience in raymarching to send me an email. Unfortunately I lost all my email data right after that, so I would love to get them back if possible? Thanx so much!
added on the 2011-07-08 10:03:04 by iq iq
Ah, the mystery email request! Will we find out what it's for this time? :D

Btw, any recommendations for a good online 'beginners guide' to the kind of maths we're doing here? I didn't do vector or matrix maths at university (well, a little, but nothing I can remember), I've picked up a lot but there's huge gaps in my knowledge still.
added on the 2011-07-08 10:52:29 by psonice psonice
psonice: solving quadratic and cubic equations is very pre-university stuff. learn that last years in college or as basic courses the first year in uni.
linear algebra covers stuff like scalars, vectors and vector spaces, projection, linear independence, matrices, dot & cross product etc..
added on the 2011-07-08 11:26:17 by rudi rudi
psonice: I recommend the math primer of "realtime collision detection" - it's a great book. Might be also a nice read for raytracers.
In addition to that I can recommend you "the holy bible for raytracing beginners" called "Physically based Rendering" from two professional NV[/Intel] guys - but that's a >1000 pager and contains pretty hard stuff :D. Both books are a definite BUY if you can afford it and they contain tons of sourcecodes.

Iq: I am still waiting for whatever you wanted to tell us! So you want us to send you a mail again? Do you request a special subject so you can filter your mails easily? I suggest "Raymarching Mystery" :D
added on the 2011-07-08 12:16:41 by las las
Code: // Obvious parameters. If you don't get the following two lines - you might want to stop reading. float time; float2 resolution; // Constants from "Generalized Distance Functions" float3 c[19]={{1,0,0},{0,1,0},{0,0,1},{.577,.577,.577},{-.577,.577,.577},{.577,-.577,.577}, {.577,.577,-.577},{0,.357,.934},{0,-.357,.934},{.934,0,.357},{-.934,0,.357},{.357,.934,0}, {-.357,.934,0},{0,.851,.526},{0,-.851,.526},{.526,0,.851},{-.526,0,.851},{.851,.526,0}, {-.851,.526,0}}; // This will generate the distance function for some kind of spikeball. // It's a bit magic - it's based on the paper "Generalized Distance Functions" // - don't ask - play. float spikeball(float3 p){ float l = length(p); p = normalize(p); float b = 0; for (int i=3; i<19; i++) b=max(abs(dot(p, c[i])), b); b=1 - acos(b - .01)/(acos(-1) * .5); b=smoothstep(.78, 1, b); return l-2.2*pow(1.5,b*(1.-lerp(.1,2,sin(time*2)*.5+.5)*b)); } // Rotation macro - see toolbox thread #define R(p, a) p=cos(a)*p+sin(a)*float2(p.y,-p.x) // Our distance function f we want to raymarch, you want to read RWWTT to // understand this. float f(float3 p){ p.z+=10.; p.y+=.5; float3 q=p; R(p.yz,time); R(p.xz,time*2.+p.x*sin(time)*0.2); float d = spikeball(p); float nd = dot(q+float3(0.,3., 0.), float3(0., 1.,0.)); return min(nd,d)*0.8; } float4 main(float2 v:TEXCOORD):COLOR{ // p: Position / d: Direction float3 p = float3(0,0,3); float3 d = float3(v*float2(resolution.x/resolution.y,1), 0) - p; // For proper raymarching we need ||d|| = 1 d = normalize(d); // Iteration counter float i; // What distance did we march on the ray? float t; // Loop using i, loops from i = 0 to i = 1 for (i=0; i<1; i+=1/64.){ float l = f(p); // Advance along our ray into direction d or step back a little in // case f(p) is negative - this might actually happen. p += l * d; // In order to compute l = abs(l); t += l; // If |f(p)| is below a magic threshold we are close enough and can // stop here. Using t to determine the threshold might be a good // idea here - this implements some kind of cone tracing - for further // information you want to read the zeno paper from John C. Hart. if (l < .001*t) break; } // In case this is true we didn't hit anything. This also means this ray // was very expensive - you should do something to avoid that - bounding // spheres are a good start. if (i >= 1.) { return float4(1,1,1,1); } // Compute normal using central differences - for other, faster and // possibly more imprecise methods you want to read the toolbox thread float2 epsilon = {.001,0}; float3 normal = normalize( float3( f(p+epsilon.xyy) - f(p-epsilon.xyy), f(p+epsilon.yxy) - f(p-epsilon.yxy), f(p+epsilon.yyx) - f(p-epsilon.yyx) ) ); // Now let's shade that thing return max(1 + dot(normal,d), 0); }

kb: Are you satisfied now? ;)
added on the 2011-07-08 16:06:08 by las las
fail. Once again. Sorry.
Code: // Obvious parameters. If you don't get the following two lines - you might want to stop reading. float time; float2 resolution; // Constants from "Generalized Distance Functions" float3 c[19]={{1,0,0},{0,1,0},{0,0,1},{.577,.577,.577},{-.577,.577,.577},{.577,-.577,.577}, {.577,.577,-.577},{0,.357,.934},{0,-.357,.934},{.934,0,.357},{-.934,0,.357},{.357,.934,0}, {-.357,.934,0},{0,.851,.526},{0,-.851,.526},{.526,0,.851},{-.526,0,.851},{.851,.526,0}, {-.851,.526,0}}; // This will generate the distance function for some kind of spikeball. // It's a bit magic - it's based on the paper "Generalized Distance Functions" // - don't ask - play. float spikeball(float3 p){ float l = length(p); p = normalize(p); float b = 0; for (int i=3; i<19; i++) b=max(abs(dot(p, c[i])), b); b=1 - acos(b - .01)/(acos(-1) * .5); b=smoothstep(.78, 1, b); return l-2.2*pow(1.5,b*(1.-lerp(.1,2,sin(time*2)*.5+.5)*b)); } // Rotation macro - see toolbox thread #define R(p, a) p=cos(a)*p+sin(a)*float2(p.y,-p.x) // Our distance function f we want to raymarch, you want to read RWWTT to // understand this. float f(float3 p){ p.z+=10.; p.y+=.5; float3 q=p; R(p.yz,time); R(p.xz,time*2.+p.x*sin(time)*0.2); float d = spikeball(p); float nd = dot(q+float3(0.,3., 0.), float3(0., 1.,0.)); return min(nd,d)*0.8; } float4 main(float2 v:TEXCOORD):COLOR{ // p: Position / d: Direction float3 p = float3(0,0,3); float3 d = float3(v*float2(resolution.x/resolution.y,1), 0) - p; // For proper raymarching we need ||d|| = 1 d = normalize(d); // Iteration counter float i; // What distance did we march on the ray? float t; // Loop using i, loops from i = 0 to i = 1 for (i=0; i<1; i+=1/64.){ float l = f(p); // Advance along our ray into direction d or step back a little in // case f(p) is negative - this might actually happen. p += l * d; // In order to compute t we want to use the absolute value of f(p) - // we need the absolute value anyways to check against the threshold l = abs(l); t += l; // If |f(p)| is below a magic threshold we are close enough and can // stop here. Using t to determine the threshold might be a good // idea here - this implements some kind of cone tracing - for further // information you want to read the zeno paper from John C. Hart. if (l < .001*t) break; } // In case this is true we didn't hit anything. This also means this ray // was very expensive - you should do something to avoid that - bounding // spheres are a good start. if (i >= 1.) { return float4(1,1,1,1); } // Compute normal using central differences - for other, faster and // possibly more imprecise methods you want to read the toolbox thread float2 epsilon = {.001,0}; float3 normal = normalize( float3( f(p+epsilon.xyy) - f(p-epsilon.xyy), f(p+epsilon.yxy) - f(p-epsilon.yxy), f(p+epsilon.yyx) - f(p-epsilon.yyx) ) ); // Now let's shade that thing return max(1 + dot(normal,d), 0); }

kb: Are you satisfied now? ;)
added on the 2011-07-08 16:10:18 by las las
las: As me being quite a newbie to 1) raymarching and 2) C-coding on x86 (formerly active almost only on Risc OS/ARM), is it possible to get a whole frame/project-folder for that example for e.g. Visual Studio (just guessing you might use that, or...) ? No offense for bugging you with that, just that first step is quite a hazzle for a platform newbie.
added on the 2011-07-08 17:10:04 by Kuemmel Kuemmel
That's the spirit!
added on the 2011-07-08 17:34:34 by pommak pommak
One place to start would be with iqs 64k framework, or Ferris' 4k framework. Then you 'just' need to draw a fullscreen quad, and correctly set the uniforms for the shader.
added on the 2011-07-08 19:53:41 by revival revival
kuemmel, go to iq's webpage and download the opengl + shader example and deploy las's fragment shader there. should be doable :-)

however, if your new to the architecture - this might not be the "hello world" :-)
in other words "what revival said"
iq, thanks for doing my 'homework' :) This is great, using google translate as my spanish is even worse then my math skill.

I wish your website was indexed first by google.

I'm sharing my first 'raymarched' image to show what I'm doing with this thread shared knowledge.

Its CPU rendered and interactive. I'm using iq rounded box and las marching loop with the addition of an early exit : if a marching step if not getting me closer, I bail. This is ok for 'convex' object like cube/cone.
I also use the normal calculation using the code right above.

The scene is using an octree of bounding volume and is raytraced.
when a ray hit a volume it switches to raymarching.
Adding reflection to the cube make the system switch back/worth between raytacing/raymarching.
I generate my own octree by I use "An Efficient Parametric Algorithm for Octree Traversal" by J. Revelles, C. Urena and M. Lastra for traversal.

The sphere soft shadow will be adapted to the raymarched object as it leverage distance to surface. so right now sphere cast soft shadow, raymarched object hard shadow.
"Single Sample Soft Shadows" by Steven Parker, Peter Shirley, Brian Smits


las spiky ball rendered as advertised, but I dont have much accelerated trig function (beside arcos that I use in generating UV for the sphere) so it was super slow.

Raymarching inside a raytracer was simpler then I expected.

BB Image
added on the 2011-07-08 22:36:25 by T21 T21
Was it even horribly slow using a very tight bounding sphere?
Nice work!
added on the 2011-07-09 08:55:39 by las las
Kuemmel: As mentioned - iq's framework is a great start - or just use RenderMonkey or FXComposer to play with the shader.

At this point of time I only have a NASM prototype which I can't release to the major public ;)
added on the 2011-07-09 08:58:31 by las las
T21: how many fps do you get from that scene?
added on the 2011-07-09 12:00:28 by rudi rudi
NASM prototype. Uiuiui. Sound like fun :)
added on the 2011-07-09 12:16:35 by raer raer
On a closeup like this I get ~6fps with my core2 Q6600, with ~41% spent in the ray marching loop.
I will look at all this in more detail when the code gets cleaner.

But so far I believe that my biggest speedup opportunity would be to use packet tracing to reduce tree traversal. And possibly use a faster primary ray intersection method. Right now its all brute force.

I will also analyse the raymarching loop to see if I missed anything.
added on the 2011-07-09 13:08:54 by T21 T21
las, it was slow because the math library pow() and sin() are slow.
I think it would be fine if I replaced them with good approximation.

BTW, the raymarching toolbox was helpfull :) (thx for driving all this)
I'm still surprised that all this was a simple drop in.

Well, I'm late to the party, but I'm happy to be here...
added on the 2011-07-09 13:20:37 by T21 T21
Just to clarify. in the screen shot the reflective cube, and yellow cube are raymarched, the rest is raytraced.
I have yet to generate UV for the raymarched obects, thats why only the plane and sphere are textured.
added on the 2011-07-09 13:22:45 by T21 T21

login