# pouët.net

Go to bottom

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)
But it would be way less 1337 then.
Lord Graga: Yes. Try it. Remove the abs ;)
Quote:

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

Yes. Yes, depends. ;)
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?
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.

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

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!
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.
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..
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
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={{1,0,0},{0,1,0},{0,0,1},{.577,.577,.577},{-.577,.577,.577},{.577,-.577,.5 77}, {.577,.577,-.577},{0,.357,.934},{0,-.357,.934},{.934,0,.357},{-.934,0,.357},{.35 7,.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? ;)
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={{1,0,0},{0,1,0},{0,0,1},{.577,.577,.577},{-.577,.577,.577},{.577,-.577,.5 77}, {.577,.577,-.577},{0,.357,.934},{0,-.357,.934},{.934,0,.357},{-.934,0,.357},{.35 7,.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? ;)
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.
That's the spirit!
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.

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'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. Was it even horribly slow using a very tight bounding sphere?
Nice work!
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 ;)
T21: how many fps do you get from that scene?
NASM prototype. Uiuiui. Sound like fun :)
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.
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...
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.