Raymarching Tutorial
category: code [glöplog]
+1
+1
Speaking as somebody who learned this yesterday...
Your explanation sucks.
Basic Problem:
We need to know the 3d positions of the surfaces of all the objects on the screen. Once we have these we can light and shade the pixels at these points.
Approach:
Make sure all objects are represented by an equation which returns a distance to any given point.
E.g. For a sphere |rayPos-centre| - r;
Make a ray per pixel, walk along it using this new point as input to the scene distance function (this function will return the smallest distance to any object in the scene).
E.g. min( sphere1(rayPos,...), sphere2(rayPos,...) )
Using this "lowest distance to any scene object" walk along the ray this much in the ray direction.
Once the smallest distance is less than a given value (epsilon) call that a hit and use the point for shading.
This is basically all the original paper says, and I implemented it from that. Pretty simple.
Shading:
For this take a look at IQ's paper for NVScene.
He also has diagrams in there! Infact this entire thread is pointless!
Tada:
Your explanation sucks.
Basic Problem:
We need to know the 3d positions of the surfaces of all the objects on the screen. Once we have these we can light and shade the pixels at these points.
Approach:
Make sure all objects are represented by an equation which returns a distance to any given point.
E.g. For a sphere |rayPos-centre| - r;
Make a ray per pixel, walk along it using this new point as input to the scene distance function (this function will return the smallest distance to any object in the scene).
E.g. min( sphere1(rayPos,...), sphere2(rayPos,...) )
Using this "lowest distance to any scene object" walk along the ray this much in the ray direction.
Once the smallest distance is less than a given value (epsilon) call that a hit and use the point for shading.
This is basically all the original paper says, and I implemented it from that. Pretty simple.
Code:
t = 0.0f;
while(t < maxDist)
{
d = DistanceFunc( rayStart + rayDir * t)
if( d < epsilon ) break;
t += d;
}
if( t >= maxDist ) // No "collision"
else do some shading with rayStart + rayDir * t
Shading:
For this take a look at IQ's paper for NVScene.
He also has diagrams in there! Infact this entire thread is pointless!
Tada:
Quote:
Adok, why on earth do you feel obligated to write a tutorial about something that you have obviously no clue about?
Because nobody else has written one and the stuff that is available on the web (linked in the original post) is too difficult to understand for average people in a reasonable period of time. Do you think the average person has the capacities to digest ten long pouet threads filled mostly with postings of people with a doubtful command of the English language (not to state that mine is better, but at least I try to make an effort), or read and understand a scientific paper? If you want to get more people into demo making, you must present the knowledge in such a way that the average person is at least able to remotely get a clue what you are talking about. I mean, even I did not interpret everything correctly, so how should the average person be able to do so, just by reading pouet threads and papers? We need people to educate others, and that does not only mean answering questions in a way *you* would understand, but in a way that anybody with an average (or below average) understanding of the English language, an average programming and math background, and an average intelligence quotient would grasp. So that's what I'm trying. Of course it would be better if somebody who is more of an expert at this subject did it, but apparently none of the experts here are interested!
Quote:
Speaking as somebody who learned this yesterday...
Your explanation sucks.
You'll get one beer too. :)
Nice basic tutorial.
Adok: Your tutorial is not to the point (as in: "Raymarching Tutorial"), incorrect, covers no dis-/advantages/quirks of raymarching, has no example source code or pictures.
The 30 lines xwize wrote cover it much better. So, sorry, but yes, this is pretty much a failed attempt...
The 30 lines xwize wrote cover it much better. So, sorry, but yes, this is pretty much a failed attempt...
Quote:
Because nobody else has written one blah, blah, blah, but apparently none of the experts here are interested!
Adok ≄ expert?
Wait what ? He wants to teach something he has never learned ???
I'm speechless...
I'm speechless...
Quote:
Of course it would be better if somebody who is more of an expert at this subject did it, but apparently none of the experts here are interested!
Maybe you didn't read carefully the zillion pouet threads on this subject...
As a person with an average understanding of, but not limited to, English, math and programming I assure you that I can digest ten long pouet threads and/or read and understand a scientific paper.
Quote:
The seminar by las at Demoscene Outreach Event II has made me get interested in sphere tracing / ray marching, and since I was unable to find a really good beginners' tutorial on that topic, I decided to write one myself after reading everything related I could find on the web.
Since I'm not an expert on ray marching myself, I guess my tutorial might contain some shortcomings, so please, if you find anything wrong, correct my errors.
On ray casting, ray tracing, ray marching and the like
There is a hype about ray marching in the demoscene. This is what people call a technique that is used mostly in 4k procedural graphics and 4k intros to create 3d pictures with interesting looks. Since there used to be no comprehensive tutorial on the matter, many people initially found it confusing to understand the underlying principle, which we can see in the huge number of threads in the pouet.net BBS dealing with various aspects of ray marching. The answers more experienced coders gave were partially a bit hard to grasp, and so I guess there are still some people around who do not really feel satisfied with their understanding of ray marching. For these people, I've written the following article.
History: It's all about 3d
While the first scrollers were strictly two-dimensional, 3d effects became omnipresent in demos rather soon. Already in C64 demos of the 1980s we can spot things such as rotating cubes. While first only the lines of the cubes were displayed, it did not take long until techniques to fill the sides with colours emerged: flat shading, gouraud shading, phong shading - you name them. Cubes were followed by more complex objects such as dodecahedra. To display spheres, a technique known as tesselation was used: the round surface was subdivided into a lot of small polygons; thus the shape of the sphere was approximated.
Techniques such as ray marching are a different way of displaying 3d objects. Since they are computationally more expensive, they were not often used in demos until computers became more powerful; you might remember the 64k intro Heaven Seven by Exceed from 1999, which featured realtime ray tracing. The demoscene, however, would not be the demoscene if it did not try to break barriers, and by now you can also find some sorts of ray casting in productions made for weaker systems.
Terminology
Ray casting, ray tracing, ray marching - are they different things, or are they just different names for the same thing or similar things? The latter possibility applies. As a matter of fact the original method is ray casting, and the other two are just variants of it. Ray tracing is a more sophisticated algorithm involving diffraction and reflection, thus generating images looking even more realistic; alas, it is computationally more expensive, of course. Ray marching, which is the thing that is so popular in the demoscene at the moment, is a variant of ray casting that permits the use of objects for which there is no analytic formula so that the intersection with the ray cannot be simply computed by solving an algebraic equation. Ray marching is also called sphere tracing, for a reason I will explain later on. Actually what's most widely used in the demoscene is not the general ray marching algorithm, but a variant of it involving a distance field - I'll show you what this is all about.
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.
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. In 2d, straight lines usually have a formula of the form:
y = k * x + d
In 3d, the same formula can be used, but we also need to compute the z coordinate for each x coordinate:
z = l * x + e
How to get k, d, l and e? All you have at first is the location of the camera x1, y1, z1 and the coordinates of the point on the surface (screen) the ray goes through x2, y2, z2. From these pieces of information k and l can be calculated easily:
k = (y2 - y1) / (x2 - x1)
l = (z2 - z1) / (x2 - x1)
d and e can then be computed by substituting x with x1, y with y1, z with z1 and inserting the already obtained formulas for k and l:
d = y - k * x = y1 - x1 * (y2 - y1) / (x2 - x1) = (x2 * y1 - x1 * y2) / (x2 - x1)
e = (x2 * z1 - x1 * z2) / (x2 - x1)
Eventually we get the following formulas for a straight line (ray):
y = x * (y2 - y1) / (x2 - x1) + (x2 * y1 - x1 * y2) / (x2 - x1)
= ((x - x1) * y2 - (x - x2) * y1) / (x2 - x1)
z = ((x - x1) * z2 - (x - x2) * z1) / (x2 - x1)
We get the intersection point of a ray with an object by inserting the formulas for y and z into the formula that describes the object and solving for x. E.g. for a sphere:
(x - x0)^2 + (y - y0)^2 + (z - z0)^2 = r^2
Here x0, y0, z0 are the coordinates of the center point.
This formula must be converted to:
x^2 - 2 * x0 * x + x0^2 + y^2 - 2 * y0 * y + y0^2 + z^2 - 2 * z0 * z + z0^2 - r^2 = 0
Now we can insert the fomulas for y and z:
x^2 - 2 * x0 * x + x0^2 + (x * (y2 - y1) / (x2 - x1) + (x2 * y1 - x1 * y2) / (x2 - x1))^2 - 2 * y0 * (x * (y2 - y1) / (x2 - x1) + (x2 * y1 - x1 * y2) / (x2 - x1)) + y0^2 + (x * (z2 - z1) / (x2 - x1) + (x2 * z1 - x1 * z2) / (x2 - x1))^2 - 2 * z0 * (x * (z2 - z1) / (x2 - x1) + (x2 * z1 - x1 * z2) / (x2 - x1)) + z0^2 - r^2 = 0
To solve this to quadratic equation, a tool like Maple may be useful. I entered the equation above surrounded by solve(..., x) in Maple and got two really, really looooooooong solutions. Typing these solutions into a programming language IDE in a form the programming language understands is tedious, error-prone work. So what else can be done?
Ray marching
The ray marching algorithm has the advantage over traditional ray casting that you need not compute intersection points. Instead, you walk along the ray and simply check after each step whether you've hit an object.
The distance you walk per step may be constant or variable. In the simpler, constant case, the easiest way is to take the vector P1P2 (where P1 is the location of the camera and P2 the surface point the colour of which you want to compute) and add it to the current point at each step, starting with P2. So you need not even compute an analytic function of the ray. All you do is calculate the x, y, z coordinates for the current point and insert it into the formulas of the objects. Now if some point Pa has coordinates for which the sphere equation results in the left side being lower than the right side, and the next point Pa+1 yields the opposite result (the left side is greater than the right side), you know that somewhere between Pa and Pa+1, the sphere has been hit. By keeping track of the number of steps you have walked on the ray, you have automatically obtained the distance, and thus are able to calculate the colour of the pixel to put.
This approach is far easier to implement than standard ray casting. It may be a bit slow if the distance you walk on the rays is low and the objects are far away, but that does not seem to matter much. A real disadvantage is that it is not precise and depends on the distance you walk per step. The larger the distance per step, the faster it goes, but the less accurate it is. Large distances per steps also have the disadvantage that you might overlook objects as it may be possible that they are so small that you virtually step over them, and do not notice that the ray has hit them between two subsequent points. (You can only detect an object if one point is outside of it, and the next point inside. If both points are outside, then you will not notice anything.) So the distance per step is a crucial point.
Distance field
What is especially popular in the demoscene at the moment is distance fields. The basic idea is that the distance per step is not constant, but variable. It depends on the distance of the current point to the object that is closest to it. If you know that distance, it is safe to walk exactly that distance on the ray, as chances are zero that you will hit an object if you walk less than that.
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. So why compute distances to objects while walking on the ray - each of these calculations is as computationally expensive as the original problem, i.e. you try to solve an instance of a problem by solving several instances of itself; that won't work.
The answer to that paradoxon is that you do not compute the distances to the closest objects, but read them from a 3d matrix - the distance field. In other words, the distances to the closest objects from each 3d point (voxel) must be already known. Demosceners mostly use this technique to render interesting images such as the 4k procedural graphics by iq of rgba.
Other applications of ray marching
Ray marching also has the advantage over traditional ray casting that you need not have analytic formulas of the objects in the 3d scene. You may also use it with volumetric data, like a set of voxels. This is the technique that is used in 3d reconstruction of CT scans in clinical radiology, for instance.
Sphere tracing
The reason why ray marching is also called sphere tracing: You can picture the distance between two steps as the radius of a sphere. Each of these spheres touches at least one object. So you virtually follow the intersection points of these spheres with the ray.
Ray tracing
A couple of words on ray tracing: The main idea behind that is that you do not only compute the ray from the camera to the object, but also from the object to the light source, whereever it is. By checking whether an object actually gets light and taking this into consideration in the formula computing the colour of the pixel, you can get more realistic pictures. Moreover, reflection and diffraction can be implemented as well, to make the pictures looking even more like photos.
Conclusion
This article has been the most demoscene-related of the technical articles I've written so far, and I hope that it has fulfilled its purpose.
Links related to this article
The original paper about sphere tracing (page not available?)
Rendering Worlds with Two Triangles - presentation by iq/rgba
A paper about Ray tracing implicit surfaces on the GPU
An unfinished draft of a tutorial on distance fields and sphere tracing
A paper on Generalized Distance Functions
Wikipedia on Ray casting
Wikipedia on Ray tracing
Wikipedia on Distance fields
Pouet.net: Raymarching Beginners' Thread
Pouet.net: Raymarching Toolbox Thread
Pouet.net: Thread about distance field equations
Pouet.net: Problem with ray marching when applying twist distortion
Pouet.net: Raymarching idea - Invertible Surfaces
Pouet.net: Thread about the making of Cdak by Quite
Pouet.net: Trick for 1k raymarchers - lighting
Pouet.net: Implicit function to distance function
Example: Terrain Ray Marching in Processing
Example: An 1k JavaScript intro involving ray marching
Example: 704 (anther 1k JavaScript intro)
Example: Valleyball by BluFlame
Example: Legoland 2 by Fairlight (ray tracing on C64)
Example: Slisesix by Rgba
Example: Fallty by Loonies (one of the first intros using ray marching)
Example: Puls by Rrrola (256b intro using ray marching)
Example: Cdak by Quite and Orange
Example: nop by Stroboholics and Metalvotze
successful troll is successful.
Adok, that's all fine and dandy, but it seems your brain shut off after reading the word "tutorial" and skipped the second part of the question. The problem isn't that you're writing explanations for beginners, the problem is that you neither understand the topic at all nor are the slightest bit qualified to teach anything to anyone because you can't even for a second think about anyone else than yourself.
Or do you really think it helps to explain in excruciating detail how you arrived at a cumbersome, mathematically underdeveloped (not even assuming basic vector math knowledge in 3D graphics programming isn't "beginner level", it's plain stupid) and wrong solution? Hint: NO. Nobody wants to read about your "Hey, I thought about that thing and it didn't work. Here's exactly how it didn't work, also you need Maple".
And then when you had the chance to actually start explaining what is the right solution and what raymarching/sphere tracing/SDFs are _really_ about, you fail. There's no useful information whatsoever in your "article". It's "ok, perhaps it's something like that but I don't understa.... see? here's a few helpful links". You call that helpful? To who exactly?
Again, because you're just too thick and I'm just too into pointless endeavours: Beginners' tutorials should be written by people who
1. Have knowledge about the topic at hand beyond the beginner level
2. Know what beginners think like and want/need to know
You're obviously incompent on both accounts. So, again, why are you doing this?
Or do you really think it helps to explain in excruciating detail how you arrived at a cumbersome, mathematically underdeveloped (not even assuming basic vector math knowledge in 3D graphics programming isn't "beginner level", it's plain stupid) and wrong solution? Hint: NO. Nobody wants to read about your "Hey, I thought about that thing and it didn't work. Here's exactly how it didn't work, also you need Maple".
And then when you had the chance to actually start explaining what is the right solution and what raymarching/sphere tracing/SDFs are _really_ about, you fail. There's no useful information whatsoever in your "article". It's "ok, perhaps it's something like that but I don't understa.... see? here's a few helpful links". You call that helpful? To who exactly?
Again, because you're just too thick and I'm just too into pointless endeavours: Beginners' tutorials should be written by people who
1. Have knowledge about the topic at hand beyond the beginner level
2. Know what beginners think like and want/need to know
You're obviously incompent on both accounts. So, again, why are you doing this?
Quote:
...too difficult to understand for average people... Do you think the average person has the capacities... at least I try to make an effort... that the average person is at least able to remotely get a clue. I mean, even I did not interpret everything correctly, so how should the average person be able to do so...
Yeah it doesn't help, that whole "for average people" attitude. Other than that, the article provides about as much information as I got from a single minute's thought on this matter.
Another question I am asking myself...
Was my seminar in vienna really THAT bad?
I thought I explained the basic idea in a very intuitive way using nice funny examples - but I guess that didn't work out so well - at least for Adok.
I feel a bit insulted by this tutorial/article.
Was my seminar in vienna really THAT bad?
I thought I explained the basic idea in a very intuitive way using nice funny examples - but I guess that didn't work out so well - at least for Adok.
I feel a bit insulted by this tutorial/article.
Quote:
I feel a bit insulted by this tutorial/article.
I wouldn't, it was done by Aspie-nazi-dok after all.
I wish I could thumb-up las' comment there...
las I think you forgot the part where we store all our distance fields in huge semi-precalcualted matrices! :)
(hello blobs)
(hello blobs)
I know at least two demos that do! :)
*sigh*
las I think your seminar was just dandy. I also liked the explanation where Widdy was the raymarcher and the object a bottle of sangria. Talk about real world ready explanations.
And now back to waiting for the video as it contains material which *might* turn into a release at some point. You haven't been at the outreach? That's what you get for it! :)
las I think your seminar was just dandy. I also liked the explanation where Widdy was the raymarcher and the object a bottle of sangria. Talk about real world ready explanations.
And now back to waiting for the video as it contains material which *might* turn into a release at some point. You haven't been at the outreach? That's what you get for it! :)
widdy and a bottle of sangria... that sounds about right when addressing a bunch of "boys next door" / "regular joes" :)
oh and swap('a', 'l') somewhere above. nobody likes calcualting.
oh and swap('a', 'l') somewhere above. nobody likes calcualting.
Las, can I have those slydes and/or papers from your seminar please. I need a fix after this "tutorial".
Those slides consist mainly of some pictures you can find in the beginners thread - some inkscape graphics and some already published code snippets.
There's nothing that much new but you can have them if you figure out how to contact me via IRC (IRCNet #revision). ;)
There's nothing that much new but you can have them if you figure out how to contact me via IRC (IRCNet #revision). ;)
You need to be at least this tall at math to ride.
las - you should make them publicly available either way. Currently only IQs nvscene-slides and a paper on doing a raymarching-modeller is available. We could use more public info :)
