pouët.net

Go to bottom

Raymarching Tutorial

category: code [glöplog]
boooooooooooooooooooooooooooring
added on the 2011-06-30 08:28:32 by havoc havoc
Ahhh. pouet. The great Teacher.
added on the 2011-06-30 08:30:54 by ringofyre ringofyre
Klosett
added on the 2011-06-30 09:57:44 by urs urs
More like the great pretender.

Ah. And hooray for MENSA überintelligence btw....
added on the 2011-06-30 09:58:35 by raer raer
kb_, Doom: Hey! It seems you didn't get we are talking about TWO DIFFERENT THINGS, ray casting and ray marching. Read my previous post again. What I said is that in ray casting, you need to compute the exact distance to the intersection point. In ray marching, you get it iteratively, and by now I've understood how it works.
added on the 2011-06-30 11:25:48 by Adok Adok
Quote:
If you are like me, your first thought on hearing about that technique will be: "WTF?! What sense does this make?" After all, ray marching is all about computing the distance from the camera to the closest object in the direction of the ray.

(emphasis added)
added on the 2011-06-30 11:44:38 by kb_ kb_
Sorry, kb_, but you have not understood it (or maybe you deliberately misrepresent the facts?). Read the first posting again. There was a section on ray casting, and then the question came up: how to compute the intersection point, and so I explained how to do so, as it is relevant for ray casting. Your quote is from a section that comes later. It is out of context.

The article starts with:

Quote:
On ray casting, ray tracing, ray marching and the like
...

Then comes:

Quote:
History: It's all about 3d
...

Next:

Quote:
Terminology
...

Then:

Quote:
General Ray casting

In general, ray casting is about displaying a 3d scene involving one or several objects. The basic idea is: You have a camera (you may also call it viewport, or the human eye) that looks at a surface (the screen). The objects are located behind this surface and are projected on it. What ray casting is all about is to determine the colour of each pixel on the screen. Imagine that you send out rays from your eye, which pass through the surface. Each pixel can be accessed by one ray. If you continue following the ray behind the surface, it will sooner or later hit one of the objects in the scene. This is the object you see at that pixel. In the most basic variant of ray casting, the colour of the pixel is simply a function of the distance from the camera to the point where the ray hits the object (the intersection point). So the ray casting algorithm has to calculate the intersection points of all the rays with all the objects, pick the closest intersection point and calculate the distance to the camera.

(emphasis added)

Now comes the section that explains how to calculate the intersection points, which I updated after the first feedback I got from las:

Quote:
How to compute the intersection points?

To compute the intersection point of a ray with an object, you need the formulas of both the ray and the object surface.

A ray is a straight line. Lines can be mathematically represented in various ways, one of them being the vector form:

P = A + t * AB

That means: Any point P is the sum of the coordinates of a point A plus the product of a vector AB and a scalar t. Actually we have three equations:

x = x0 + t * dx
y = y0 + t * dy
z = z0 + t * dz

We get the intersection point of a ray with an object by inserting the formulas for x, y and z into the formula that describes the object and solving for t. E.g. for a sphere:

(x - xc)^2 + (y - yc)^2 + (z - zc)^2 = r^2

Here xc, yc, zc are the coordinates of the center point.

Inserting this we get:

(x0 - xc + t * dx)^2 + (y0 - yc + t * dy)^2 + (z0 - zc + t * dz)^2 = r^2

(x0 - xc)^2 + 2 * (x0 - xc) * dx * t + dx^2 * t^2
+ (y0 - yc)^2 + 2 * (y0 - yc) * dy * t + dy^2 * t^2
+ (z0 - zc)^2 + 2 * (z0 - zc) * dz * t + dz^2 * t^2
= r^2

(dx^2 + dy^2 + dz^2) * t^2
+ ((x0 - xc) * dx + (y0 - yc) * dy + (z0 - zc) * dz) * t
+ (x0 - xc)^2 + (y0 - yc)^2 + (z0 - zc)^2 - r^2
= 0

So we have a quadratic equation with:

a = dx^2 + dy^2 + dz^2
b = (x0 - xc) * dx + (y0 - yc) * dy + (z0 - zc) * dz
c = (x0 - xc)^2 + (y0 - yc)^2 + (z0 - zc)^2 - r^2

t can now be computed by simply inserting these parameters into the general solution formula for quadratic equations:

t = -b +/- sqrt (b^2 - 4 * a * c) / (2 * a)

After obtaining t, we can compute x, y and z.

This is NOT related to ray marching.

I admit that even ray casting does perhaps not require to calculate the intersection points with all objects, but it is enough to calculate the distances to objects, and only compute the intersection point with the closest object. However, you definitely need to compute this single intersection point.
added on the 2011-06-30 12:12:02 by Adok Adok
Quote:
This is NOT related to ray marching.


*flicks lightswitch*

this was never about raycasting.
added on the 2011-06-30 13:11:06 by superplek superplek
*sigh*

Quote:
Now comes the section that explains how to calculate the intersection points, which I updated after the first feedback I got from las:
Quote:

How to compute the intersection points?
[skipped lots of maths that could be replaced by a wikipedia quote that explains ray-sphere intersection better]

This is NOT related to ray marching.


Then WHAT is it doing in a ray marching tutorial?

That's the whole point that you, again, missed because you are just lacking the ability to let any criticism penetrate your thick skull. You start off a tutorial by deliberately misleading (and, in its first version, factually incorrect) information. That's ALL we tried to point out. YOU SUCK AT TEACHING.

added on the 2011-06-30 13:15:33 by kb_ kb_
Please be kind with him, he just seems to be different...
added on the 2011-06-30 13:33:43 by hfr hfr
wow, i'm fascinated with this ubermensa member.
added on the 2011-06-30 14:20:26 by martin martin
and he teaches at sucking! :)
added on the 2011-06-30 14:20:40 by superplek superplek
people please stop. all.

-- ANYONE WRITING SINGLE WORD UNDER THIS LINE IS 100 % LAME --

(who's next? :)
added on the 2011-06-30 14:37:53 by maq maq
kb_: How superficially did you read the tutorial? The headline is:

Quote:
On ray casting, ray tracing, ray marching and the like

So it's clearly not only about ray marching.
added on the 2011-07-01 11:20:51 by Adok Adok
That changes everything.
added on the 2011-07-01 14:01:37 by xernobyl xernobyl
BB Image
added on the 2011-07-01 14:04:55 by Punqtured Punqtured

Hey Adok ... thx for this. :)

I wanted to have a look at it and you save me quite some time and work. :)


added on the 2011-07-03 15:53:06 by doc^21o6 doc^21o6

wow, i finally finished reading the thread.

Hilarious ! *LOL*

added on the 2011-07-03 16:27:14 by doc^21o6 doc^21o6
:)
added on the 2011-07-03 16:38:11 by Adok Adok
i still see people using coordinates to solve intersections ????? NEVER DO THAT! Use vectors!

Quote:
P = A + t * AB

That means: Any point P is the sum of the coordinates of a point A plus the product of a vector AB and a scalar t. Actually we have three equations:

x = x0 + t * dx
y = y0 + t * dy
z = z0 + t * dz

We get the intersection point of a ray with an object by inserting the formulas for x, y and z into the formula that describes the object and solving for t. E.g. for a sphere:

(x - xc)^2 + (y - yc)^2 + (z - zc)^2 = r^2

Here xc, yc, zc are the coordinates of the center point.

Inserting this we get:

(x0 - xc + t * dx)^2 + (y0 - yc + t * dy)^2 + (z0 - zc + t * dz)^2 = r^2

(x0 - xc)^2 + 2 * (x0 - xc) * dx * t + dx^2 * t^2
+ (y0 - yc)^2 + 2 * (y0 - yc) * dy * t + dy^2 * t^2
+ (z0 - zc)^2 + 2 * (z0 - zc) * dz * t + dz^2 * t^2
= r^2

(dx^2 + dy^2 + dz^2) * t^2
+ ((x0 - xc) * dx + (y0 - yc) * dy + (z0 - zc) * dz) * t
+ (x0 - xc)^2 + (y0 - yc)^2 + (z0 - zc)^2 - r^2
= 0

So we have a quadratic equation with:

a = dx^2 + dy^2 + dz^2
b = (x0 - xc) * dx + (y0 - yc) * dy + (z0 - zc) * dz
c = (x0 - xc)^2 + (y0 - yc)^2 + (z0 - zc)^2 - r^2

t can now be computed by simply inserting these parameters into the general solution formula for quadratic equations:

t = -b +/- sqrt (b^2 - 4 * a * c) / (2 * a)


all that crap can be summarized to this much shorter, less error prone and coordinate system-free solution:

Quote:

line: P = A + t * AB
sphere: |P - C| = r

substitute P

|AC + t * AB| = r

|AC + t * AB|² = r²

|AC|² + t² * |AB|² + 2*t*<AC,AB> = r²

So we have a quadratic equation with:

a = |AB|²
b = 2<AC,AB>
c = |AC|² - r²

therefore

t = -b +/- sqrt (b² - 4*a*c) / (2*a)


You can of course do b = <AC,AB> and a=1, and then t = -b +/- sqrt(b² - c)


Same coordinate-free method can (and should) be used for other primitives. For example, a plane

Quote:
line: P = A + t * AB
plane: <P,C> = d

substitute P

<A + t * AB,C> = d

<A,AB> + t * <AB,C> = d

t = (d - <A,AB>) / <AB,C>


You can use the same for cylinders, cones, and any other shape that you can describe with vector operations (distances, projections/dots, mirrors, etc).

Specially if you pretend to write a tutorial, keep it simple, PLEASE do not mess up people's head with millions of unnecessarily long equations.
added on the 2011-07-03 20:36:09 by iq iq
iq: Thanks for your hints! I'll update the tutorial.
added on the 2011-07-03 20:38:39 by Adok Adok
iq solution to intersection is as elegant as you get.

I still dont like math notation in general because of the amount of context required.
This come from an era where ink was made of mermaids tears and it was decided that "The less we write the better"
It then turned into an obfuscation contest...

This is one reason why I dont like people overloading operators in C++ to change their concept. On one line * is a mul, on another line * is a cross product? or concatenating strings using + ... [\rant]







added on the 2011-07-03 22:13:52 by T21 T21
i agree with iq.
adok: don't write long equations, i was bored after reading the first few because of bad explanations. :( it's better if one actually knows the differences to just say what it is.

someone like to call raycasting and raytracing the same thing. i.e. Foley,Van Dam's CGP&P.
though my own experience about raycasting was that back in the day it was used in games like wolfenstein and commance: maximum overkill (and in demos with voxel-landscapes) etc. it was just casting rays along the lines in the field of view and checking the ray wheter the height was shorter than the previous one and discarding it if so. in 3d it may be that raycasting doesnt involve anything except for hitting an object and nothing else. (i am not sure, and really i dont care).

so, there are a couple of good tutorials about raycasting and raytracing out there. i've read through understood much. about raymarching - i dont know if it has anything to do with marching-cubes (just because the names uses marching, i would guess there are some similarities - but my intuition says not. (marching cubes was used for metaballs effects in the late 90's and early 00's when those where popping up in the demoscene just to remind). the little i've read or flushed through about raymarching has nothing to do about implicit surfaces or anything. i guess its just a technique to find object-intersection faster. ive seen them in 4k's and demos of today. even if marching-cubes uses a 3d'grid, i would guess raymarching doesnt make subdivision surfaces of metaobjects (the 2^8 different triangles in a cube (and then interpolating the edges), but ive seen them in demos, so this is confusing me a bit :D anyway it's not such a big deal, im not planing on doing a raymarching-engine anyway, it would just be fun to know what the difference is between it and the other ray-intersection techniques that are out there.

and for something else:
i dont know if this has anything to do with raymarching, but in raytracing you only need the discriminant to indicate whether a ray is intersecting a sphere. for other objects its a different story. it doesnt probably have anything to do with the marching-technique because it just a intersection-hit-thing. that is if i think of raymarching as the layer's in an apple and the intersection as the apple itself. or the other way around. hehe :P
added on the 2011-07-04 08:31:24 by rudi rudi
rudi you should write a raymarching tutorial...
added on the 2011-07-04 11:36:26 by xTr1m xTr1m

login

Go to top