Wednesday, 30 December 2009

How To Build A Raytracer: Part II

In the previous post we looked at some of the fundamental ideas behind raytracing and saw some stunning renders created using the technique. In this post we'll start to take a look at the camera, and how to create a three dimensional scene.

The Camera

To start with lets create a camera at a position in space [camX,camY,camZ]. This camera can move up, down, left, right, in and out around your scene, and is where all of the initial rays are fired from. The image below shows how the rays exit the camera through the scene. It is clear that we want our rays to pass from the camera through the image, as shown in this diagram, but how do we find these rays! For a horizontal camera with no rotational properties this is actually very easy, so lets take a look at how to do it.

Traditionally cameras have a property called the field of view. This is related to the range of angles that a camera can see. A fisheye lens, for example, has a large field of view (180 degrees?). High field of views can result in image curving and I've found that the optimum angle between the horizontal and the top vertical for ray tracing is around π/6 degrees giving a field of view of π/3 or 60 degrees.

Once we've decided on a field of view for our ray tracer we can determine the distance between the image plane and the camera. Remember, unless the image is completely square the field of view in the vertical range and the horizontal range will be different. Programmatically, creating a new variable called the scale of view makes things far easier where:

var scaleX:Number = Math.tan(fovX);
var scaleY:Number = Math.tan(fovY/(scenewidth/sceneheight));

In the above actionscript, scene width and scene height are the pixel height and width of the image you want to create. Once we have our scales of view we can start firing rays. In a ray tracer rays are fired through every single pixel in the image. Although it results in pixel perfect images the computation required can also be rather large for high resolutions. This is why ray tracers are not currently used in real time applications.

So the next step in the ray tracing algorithm is to cycle through each pixel creating rays. I suggest using two embedded for loops although there are other ways of doing this depending on the structure of your program:

for(var i:int = 0; i < scenewidth; i++)
      for(var j:int = 0; j
             rayX = scaleX*(2*i-scenewidth)/scenewidth;
             rayY = scaleY*(2*j-sceneheight)/sceneheight;
             rayZ = 1;
             // After we have created the ray we calculate collisions - and then render the pixel

The above is a simple example of creating all the rays needed for a scene.

In vector mathematics a lot of calculations rely on the vector being unitary (meaning of length 1). To fix this just take the modulus of (rayX, rayY, rayZ) and divide each of rayX, rayY, and rayZ by this modulus.

This simple model can be extended by adding yaw and pitch, and for the really enthusiastic even roll! These are 3 types of rotation. The simplest way to create rotations is to rotate the ray vectors around the camera's location once they have been generated using matrix transforms. This will fit into a later tutorial.

Stay tuned for the next in the series soon!

How To Build A Raytracer: Part I

This is the first of what I hope to be a few posts that describe the fundamental theories behind building a raytracer. I will specifically look at how to build one in flash using AS3, but the theories should be easily transferrable to any other scripting language so whether you use C++ and openGL, Java, Python or AS3 this set of tutorials will point you in the right direction.

This is not just source code that I'm posting up, I will describe everything that I feel is needed to build a ray tracing engine without necessarily giving too much code. In the end I feel this is a far more rewarding way of learning flash and creating new projects, and is how I have taught myself in the past. Certain aspects of maths throughout the tutorial may be of a reasonable level but most high school vector course books should give enough knowhow to be able to see what is going on. So lets begin.

Note: the image to the right shows the kinds of lighting effects a raytracer can produce.

What is a raytracer

In nature a ray of light travels from a light source - interacts with some objects and either disappears into space or reaches our eyes. What we see depends on what the ray has collided with on the way to our eye. For example taking a light source to be the sun, trillions of rays hit earth every second, each of these reflects, refracts and is absorbed by trees, by roads, by cars and by other people. For us, the onlookers, only a tiny fraction of these rays hit our eyes, but when they do, the individual rays (photons) create the scene we see in front of us on the back of our eyes ready for our brains to untangle and interpret.

The idea of a raytracer - at least in the sense of this tutorial - takes what happens in nature and reverses all of the processes. Rays are created in the back of our eyes and are fired in a range of directions at our scene. Each ray passes through a point in our image and will either pass through our scene or hit an object. The image to the left helped me understand the ray firing process. When a ray hits an object there are 3 possibilities:

(i) The ray absorbs the ray
(ii) The ray reflects the ray
(iii) The ray refracts the ray

In the first case, a new ray is case from the point where the ray scene collision occurred, in the direction of any light sources in the scene. If there are no objects in the way then the object is lit, otherwise the object is in shadow.

In the second case a new ray can be cast depending on the surface normal of the object which can interact with the scene again. The ray can keep colliding with objects up to an arbitrary number of times so theoretically a ray could bounce between objects forever.

In the third case a new ray can be cast depending on the surface normal and refractive index of the material. As above this ray can continue to interact with the scene.

These three cases are not mutually exclusive. In a scene there can be any amount of refraction, refraction, absorption and shadowing, which gives ray tracers their realism. Take a look at the top image for examples of all three, and the image by pixar below is another example.

We've seen that a raytracer is just a way to render a scene which is physically realistic and can produce effects like shadowing, reflection and refraction in a far simpler way than many other rendering methods.

In my next post I'll explain how the camera works and how to set up our first scene.

My Fluid Dynamics Engine in AS3

This post and my recent experiments have been inspired largely by the work of Eugene Zatepyakin and that of Jos Stam on fluid dynamics.

Jos Stam's article on fluid dynamics for games started it all, having a similar effect on this area of research as Thomas Jakobsen's article had on the use of Verlet Integration in physics engines. The beauty of the fluid solver is that it provides a computationally quick and stable approach to simulation of fluid dynamics, which can be easily expanded into 3 dimensions and used to solve many more advanced problems.

Eugene Zatepyakin was the next step in the chain creating a fast engine in AS3 which I talked about in a previous post. I decided to write my own version of the engine and here it is:

The first example shows 4000 particles floating around in the simulated fluid - just click on it to launch to flash file - once it is running click and drag to make the fluid move.

The second example shows the pressure grid being used as a displacement filter for the image below. This starts to add a bit of realism and creates a more three dimensional feel.

Wednesday, 16 December 2009

Flash Ray Tracer Reflections

Finally managed to get reflections properly working in my actionscript raytracer. The mathematics behind reflections is very simple. Given an incoming light ray V, and a surface normal N, we can calculate the reflected light ray R using:

a = V.N
R = V + 2*a*N

I applied this theory to the ray tracer and the results are beautiful. Its amazing how much realism a few shadows and reflections can create! The number of reflections obviously changes the image realism. The images below show 1, 2 and 3 reflections per ray. Surprisingly there really isn't much of a reduction in performance - and for the purposes of a flash raytracer 3 reflections should be plenty!

Just need to add some functionality for box reflection and then I'll set the engine rendering some nice scenes!

One further extension I might set myself is diffuse reflections. Instead of light being reflected directly along the normal, there could be random fluctuations in the reflection vector. I think this could produce quite a nice wave effect. I'll keep you posted!

On a performance note the image with 3 reflections took just over 2 minutes to render in 1600x1600 with no real optimisation. For a resolution of 400x400 pixels it takes about 2.5 seconds. Not too bad at all in my opinion!

Update: Here are a few fuzzy shots. The first one is less fuzzy and the second one is more fuzzy. Quite an interesting effect I think:

Decided to go a bit mad and rendered a rather large image with a load of boxes and reflective spheres. Inspired by SuperJers PixelMachine, but rendered completely using flash and AS3, not OpenGL and C++. Here it is (Something has gone wrong with the reflections of the boxes - there is no shadowing - but I didn't have the heart to stop it once it was half way through!):

Here is another nice one, 2880 by 2880 pixels, back to the original room but with the reflection stuff added. Looks quite nice in the super high resolution!

Update: I've rendered few more large reflective images - there is still something slightly wrong with the reflections I think, check them out:

Tuesday, 15 December 2009

New Raytracer Features

I've been working on this now that term is over. The features I've added are diffuse shadows - multiple directional lighting - and box rendering. Here are a few renders. In order they show a low resolution diffuse shadow render, a high resolution render with a cube, and a high resolution render without global lighting with two point lights:

And here is a render I like with 4 lights:

Update: Deciding to take the whole concept a bit further and show you that the ray tracer is not just good for rendering spheres and cubes I rendered a really simple office scene of some description - here it is:

Update: Finally started looking at reflections. I've got the maths bit of it sorted. Just got to look at the way I'm structuring my code to help it make a bit more sense. Here is my first result, to show that the angles work!

Update: Same again but this time with 50 or so spheres floating around in the sky - and a reflective floor. Nice to see it almost working!

New Scientist Features the Mandelbulb

I discovered an article in the latest New Scientist magazine about Daniel White's Mandelbulb. Found it really cool as I've been working on this stuff quite a lot recently! Read the whole article here at New Scientist!

Friday, 11 December 2009

Quick example of real-time raytracing in flash

Just a quick low res, and completely un-optimized example of an animated version of the ray tracer I've been working on. The light source moves in real time and you can move the camera around with the mouse.

Just click the image below to launch it!

Friday, 4 December 2009

Plane Intersections Added to Flash Raytracer

I was working late on this last night when I should have been doing coursework. Anyway I managed to get plane intersections in the AS3. The maths was actually very simple. I'm still working on reflections so stay tuned! Below is a nice example of spheres and planes being rendered. Total time about 15 seconds, 1100 x 800 pixels.

Tuesday, 1 December 2009

First Screenshots of my AS3 Raytracer

After writing a really simple ray tracer to render the Mandelbulb in my last post, I thought I'd write a slightly more advanced one, with more accurate shadows, reflections and all things nice ray tracers have.

I started just getting the raytracer to draw some spheres, but the results weren't very pretty. I added some shadows and some distance based lighting and they began to get a bit better.

Anyway here are the first screenshots. Once I'm at a stage where I'm happy with everything and know that I understand it I'll write a tutorial covering the fundamentals.

First image rendered with shadows - no distance lighting but shadows work

Another similar example

Trying to get distance decay of lighting intensity but using the wrong vector. This causes brightness where there are more spheres for some weird reason!

Fixed it - Shadows look good and added a load more spheres!

I'm starting to like this!

So the next step for this is reflection. This just involves firing another ray when a collision is found and checking for collisions. For those who are interested the resolution is 1100x800 pixels, and the images render in about 5 seconds. Not too bad at all!

Stay tuned for updates.

Update: Just a thought, I think altering brightness depending on the direction of the normal of a plane to the light source would increase realism, also create effects like specularity, I don't know but I'll give it a go and post some screens of it!

Update: Here are a few shots of directional lighting in action! I have to say for such a minor change the realism massively increases. Instead of clear shadow lines, they are all a lot more diffuse! Lovely.

A day time shot:

And at night time - with no global illumination:

Update: Just rewrote almost everything, should make it easier to add new features though. Its looking good, nearly got reflections working, then I'll add some other objects (probably boxes and planes).

Thursday, 26 November 2009

Ray Tracer in AS3: Rendering the Mandelbulb in Flash

So I went off for a few hours and thought how I could improve the voxel engine. Both from an efficiency perspective as well as that of realism.

I realised that the only route was ray tracing and after reading this fantastic article by SuperJer about his pixel machine experiment I was motivated and inspired to try something along these lines for my renderer.

The article takes the creation of a ray tracer from its very early stages to a really polished program. All this happens in one weekend by the way, I really suggest you read it.

Anyway the idea behind raytracing is that a ray of light is passed from your camera through a pixel on the screen. The ray formed between the two points continues to pass through your scene until it hits something. When it hits something the pixel through which the ray passed is updated with the colour value of the object it hit, or failing that the colour of the sky behind, and a ray is "fired" through the next pixel until your image is formed.

So in my case I'm trying to render the Mandulbulb set. Something I've now done many times before, but lets be honest, in the past I've needed huge numbers of voxels and the results weren't great. So what happens in the ray tracer?

1. I fire a ray through the current pixel - starting at 0,0 working all the way to the image width/height.

2. I check along the length of the ray to see if that location is a part of the Mandelbulb Set.

3. If it is - check if that point is in light or shade.

4. Fire another ray from this point to my light source.

5. Check a bit away from this point in the direction of the light source, if that point is also a member then any light from the light source would have been stopped. So shadow the pixel.

6. Otherwise colour the pixel normally.

The resulting images that are built up show a lot more detail. Not only that they have pixel perfect shadowing, perspective, rotation and you can't see any stupid voxels.

Lets take a look below at some ray tracing in flash. Below you can see increasing resolutions from
137 x 100 to 1100 x 800 pixels.

And below is one I left to render for about an hour (2200 x 1600 pixels). Just click to enlarge it!

Tuesday, 24 November 2009

Radially Coloured Render of 3D Mandelbrot in flash

Just click to enlarge it! Going to start working on volumetric ray-casting for flash next so that we can get some real shadows in there!

The colours are produced using the radial term of each point in 3D space. For some reason this actually makes it look like there are shadows being cast which is nice, although there aren't. This really brings out a lot more detail in the render!

Sunday, 22 November 2009

Inverse Mandelbulb Pixel Mapping in Flash

When we map the 2d Mandelbrot Set we normally colour a pixel depending on the rate at which that point tends to infinity on some colour scale. In 3D normally this wouldn't work - where you have solid objects you'd be changing their colour internally. But since we are looking at cross sections using the voxel renderer it is actually very doable. Here are a few examples:

Remember that the inverse is being mapped. I really like the effect, and its definitely nice to add some colour to the dull grey images of the previous post.

Its like looking into a three dimensional cave of fractal goodness. Another possibility would be to use transparent pixels and change transparency levels. I will give this a go next as it would allow the whole shape to be seen externally, with colour (possibly? we'll see!)  Anyway click here to see all this fractal goodness happening in real time in flash using AS3! Enjoy

Working - 3D Mandelbrot in Flash

Possibly a world first, I don't know, but I can confirm that I have rendered Daniel White's Mandelbulb set using AS3.

The first render is 216 Million voxels (600*600*600) and took about 10 minutes to do.

This is the 8th order of the Mandelbulb (where things start to get interesting from a fractal detail point of view).

First screenshot is half way through the rendering process:

And here is the finished product:

Hopefully soon I'll have a 3D Mandelbrot Explorer ready and working much like the 2d version previously. I'm currently rendering an image 1000x1000x1000 voxels in size (1 Gigavoxel), and I'll add it to this post when it comes out!

edit: here is the gigavoxel render (zoomed in a bit too much though which I'm annoyed about so it cut off the "colosseum" structure at the top!

here is a quick preview of the voxel engine rendering a lower resolution (400x400x400) version.

To zoom in at the moment you'll just have to right click and press "zoom in" but this won't actually zoom in, just give you can enlarged version. Worth doing if you want to see individual voxels though :)


edit: Just started playing with zooming and rotating:

Here is a view of the colosseum structure (normally at the top) from the side:

Wednesday, 18 November 2009

First Demo of the Mandelbulb in flash.

So I've put together a demo of the Voxel Renderer doing something - not entirely sure if it is the true Mandelbrot in 3d - but  click the image below to see the approach I'm taking -

Zoom in and you'll see how it's constructed from isometric cubes.

Tuesday, 17 November 2009

Mandelbulb - First Thoughts

In light of Harry's comment I thought I'd take a look at trying to code a Mandelbulb set.

The first obstacle was how to render:

The examples I've seen mainly use ray tracing - there is no way as3 is capable of raytracing this kind of complexity within my lifetime. I decided to write a simple voxel (3D pixel) engine to display the set. The theory behind this is fairly simple. Work in isometry (no perspective), render from left to right, bottom to top and front to back and all should work out.

Just so I knew the kinds of things I was looking for here are a few of Daniel Whites original renders of the Mandelbulb.

So quite something to aim for with flash!

Anyway, I thought I'd start BIG, and by BIG I probably mean I regret doing it now because of the insane render time. Poor flash player.

As I write this the whole render (1000x1000x1000 - 1 million voxels - 1 mega voxel!) is about 2 percent complete. I don't know whether what I am rendering is the right thing or not but hopefully as more shapes begin to unveil themselves it will become clear and I'll know whether to start again or not!

Here are a few renders using the Voxel Engine:

The first few cross-sections - some potential? We'll see..

About 10 cross-sections down - only 990 to go! There are some interesting shapes going on though - note this is a zoom. You can see the individual voxels and how I build them up quite nicely. There does seem to be an awfully regular plane forming which shouldn't be there.

Yet more complete - starting to get some nice inwards curving - hopefully it will make a shape thats kind of spherical...

Just a bit more - about an hour down and the stage I go to bed at! I'll take another look in the morning - until then good night!

Below is what I found the next morning: Not exactly what I was looking for - fractal? possibly - but not nearly as complex as the Mandelbrot I should have been getting.

Unfortunately this means I'll have to change the settings and start over: at least I know the Voxel Engine works, and that I shouldn't do quite as ambitious renders! I'll keep you updated on the results!