Scratch

Scalars, Points, and Vectors

I'm going to start by talking about scalars and vectors.  A scalar is just a regular value.  It has no dimensions and can be used to express such things as size, length, speed, or scale.  If you create a variable in Scratch that variable is considered a scalar.

A vector is a single dimensional set of values.  With a vector you can express both size and direction.  If we take the scratch variables x and y and put them together then that would be a vector expressed as [x y].  If we create a vector variable it will normally be denoted with a bar over it or with an apostrophe.  So we would say that A' = [ x y ].

A point is similar to a vector in that it is a single dimensional set of values, but it represents a position, rather than a direction like a vector.  Normally when defining a point there is no apostrophe: B = [ x y ]

If you have two points then you can create a vector by subtracting one from the other.  If you have a point A defined as an [ x y ] position and you have a point B defined as an [ x y ] position then to calculate a vector between A and B you would subtract the x value in A from the x value B and the same with the y values to get the vector AB' = B - A.

Here is a Scratch program that illustrates the differences between points and vectors:  http://scratch.mit.edu/projects/Canthiar/39385

Please let me know if you see any errors or have any questions.

andresmh wrote:

The project illustrates it very well. I'd be following your explanation of the raytracing project works because I have not had the time to analyze your code 

The code is a little hard to read because I did a lot of copy paste to speed things up. Hopefully this will help clear things up. 

It's going to be a few more posts before I get into how the program works because I want to kind of give an overview of the math that is involved.  I'm going to skip over a lot of stuff that you would normally learn about in a complete course of linear algebra, but hopefully that will allow me to get through this faster.

thankyou for taking the time to do this.  i am looking forward to seeing how you incorporated this.

I'm making assumptions about how much math people know in these posts.  If there is anything that you don't know and want clarification on then please let me know.

The next few posts will talk about rays and how they intersect with objects using the methods mentioned above.

edit: Also please let me know if the timing in the presentations is too fast.  Since I'm familiar with the topics it's hard for me to know if I'm skipping anything or if it takes extra time to understand the material.

Last edited by Canthiar (2007-09-30 13:31:24)

The Ray in the Raytracer

In the real world photons are generated from a light source, such as the sun or a light bulb, and they are reflected off objects and back to your eye.  The problem is that a light source generates too many photons to calculate quickly.  Instead a raytracer will start a ray at the eye and point it toward a set of objects.

When the ray intersects an object rays will be generated to check for light and reflected objects.  A ray will be generated at the point of intersection pointing toward each light in the world, if the ray doesn't intersect any objects before it gets to the light then no shadow is cast on the original object.

Intersection

In a pure mathematical way intersections are done by taking the equation for a shape and the equation for the ray and finding the intersection.  This is normally done using a quadratic, cubic, or quartic equation to solve the roots in both equations.

If you define a sphere as any position that is radius distance from a center point then you can use a norm to to write a sphere equation as: radius = | position - center |.  We would then use the ray equation that was used in a previous discussion(position = ray_start + ray_direction*time) to find the intersection between the two equations.

Substitute the ray equation into the sphere equation:

radius = | ray_start + ray_direction*time - center |

Now solve for time:

radius = | (ray_start-center) + ray_direction*time |

raidus = sqrt( (ray_start-center) + ray_direction*time ) dot ( (ray_start-center) + ray_direction*time)

radius^2 = ( (ray_start-center) + ray_direction*time ) dot ( (ray_start-center) + ray_direction*time)

radius^2 = (ray_start-center) dot (ray_start-center) + (ray_start-center) dot ray_direction*time + (ray_start-center) dot ray_direction*time + ray_direction*time dot ray_direction*time

radius^2 = (ray_start-center) dot (ray_start-center) + 2(ray_start-center) dot ray_direction*time + (ray_direction dot ray_direction)*time^2

0 = (ray_start-center) dot (ray_start-center) - radius ^2 + 2(ray_start-center) dot ray_direction*time + (ray_direction dot ray_direction)*time^2

Pulling out time for use in a quadratic equation you get

A = (ray_direction dot ray_direction)
B = 2(ray_start-center) dot ray_direction
C = (ray_start-center) dot (ray_start-center) - radius ^2

let dot_product = (ray_start-center) dot ray_direction
let to_center = |ray_start-center|
ray_direction dot ray_direction is 1 since ray_direction is a unit length vector.  With these substitutions the values become:

A = 1
B = 2 * dot_product
C = to_center^2 - radius^2

The quadratic equation is defined as: time = -B +- sqrt( B^2 - 4AC) / 2A

Plugging in the values:

time = 2*dot_product +- sqrt( (2 * dot_product)^2 - 4 * (to_center^2 - radius^2) ) / 2

time = 2*dot_product +- sqrt( 4 * (dot_product^2) - 4 * (to_center^2 - radius^2) ) / 2

time = 2*dot_product +- 2 * sqrt( dot_product^2 - to_center^2 - radius^2 ) / 2

time = dot_product +- sqrt( dot_product^2 - to_center^2 - radius^2 )

For our purposes we only need the closest time, so the equation becomes:

time = dot_product - sqrt( dot_product^2 - to_center^2 - radius^2 )

For any value less than 0 or for any square root of a negative number there is no intersection.

Here is a Scratch program to demonstrate this: http://scratch.mit.edu/projects/Canthiar/40988

so how much quicker would you raytracer run in scratch had direct functions such as cos, sin,tan and sqrt?

Illumination

In order to see objects in a ray traced scene they need to interact with light sources.  There are many different types of light sources such as point, directional, spot, and area.  Each object also has a material that reflects light differently and with different colors.

Normally there are several components to how a surface reflects light.  The most common are ambient, diffuse, and specular. 

Ambient simulates all of the light reflecting off of everything in the scene.  It is the darkest something can get if there is no light directly shining on it.  Ambient light is a constant value applied regardless of light level.  It is very easy to calculate color = surface_color * ambient_color

Diffuse simulates light that indirectly reflects off of a surface.  When light hits a surface it will scatter into many directions.  The most common calculation for diffuse lighting is Lambert lighting.  It is the dot product between the surface normal and the direction to the light source.  The calculation looks like this color = (normal' dot to_light') * surface_color * light_color.  The vector to_light' can be the direction of a directional light or a vector from the point on the surface pointing toward the light source. 

If it's a point source then the light can optionally attenuate with distance.  This means that the further away you get from a light source the dimmer it will be.  This is done by dividing the distance from the surface to the light source by some maximum distance that the light can travel.  To prevent an unnatural linear falloff this attenuation value is squared or cubed.  You can simulate different atmospheric effects by combining some value of squared and cubic attenuations with different attenuation colors.

Specular simulates light that directly reflects off of the surface.  When light hits a surface it will reflect based on the direction that the surface is facing.  The most intense will be reflected at an angle between the viewer and the light source.  There are two popular specular models; Blinn and Phong.  Phong uses the reflection vector that had been mentioned earlier.  Blinn uses what is referred to as a half-way vector that is meant to be fast to compute.  Since I was already calculating a reflection vector I went with Phong.  Phong is basically color = ( reflected' dot to_light') ^ phong_power * phong_color * light_color.  Phong technically has the ambient and diffuse component in the same equation.

Reflected light can also come from other objects in the scene.  Depending on how shiny a surface is this can make an object look a mirror.  This is simply done by casting another ray into the scene for the point of intersection in the reflected direction.

Once all of the lighting values have been calculated they are just added up along with contributions and capped at 100%.  A value at or greater than 100% is considered fully saturated.  final_color = ambient_color * ambient_intensity + diffuse_color * diffuse_intensity + specular_color * specular_intensity + reflection_color * reflection_intensity.

Shadows are created by casting a ray to a light source, if there is an object between the start of the ray and the light source then only the ambient and reflective components contribute to the surface color.

Last edited by Canthiar (2007-10-09 17:05:43)

Getting it all into Scratch Part 2

Creating the initial ray that goes into the scene is fairly simple.  Define some point in space and designate that point to by your camera position, that will be the start of the ray.  Then update x and y over the screen.  The direction of your ray will simply be [x y 1] / |[x y 1]|.

There is a problem with generating your rays like this.  The ray will point in a very wide range of directions and will change based on the size of the image.  To fix this we will have to divide the x and y value in the range by some value to make it more reasonable.

I'm going to take you though some steps that I didn't do in my original ray tracers since I wasn't as familiar with Scratch as I am now.

With a camera or normal vision you can only see a certain distance to the left or right without moving the camera or your eye.  Everything that you can see is in your field of view.  If you draw a line out from your eye on the left and right into the distance and measure the angle between them then this is the horizontal angle of the field of view. 

Try this exercise.  Open your hands flat and place them on each side of your head next to your eyes with the palms facing inward and slowly rotate them until you can't see them any more.  For most people your hands will be at almost 180 degrees apart.  For a single eye they will be a over 90 degrees apart.  If you do the same thing with a camera then the value will be a lot lower.

To get a ray traced image  to have a consistent angle we must scale the ray by some value calculated from the FOV.  The equation is scale = tan( angle / 2 ) / image_width.

Since Scratch doesn't have any trig functions we can use some of the behaviors in Scratch that do.  When you set a sprite to point in a particular direction then it uses trig functions to calculate movement.  If you move a distance of 1 from the center at an angle then the following trig values can be derived:  sin = x, cos = y, tan = x/y.  Putting this into scratch code it would look like this:

<go to x   0 )y   0 )>
<point in direction((( <{ FOV  }> </> 2 )))>
<move( 1 )steps>
<set{ FOVScale  }to(((  <x position></>  (( <y position> <*> <{ Width  }> )))))>


Here is a Scratch example that uses these concepts to create a ray traced scene: http://scratch.mit.edu/projects/Canthiar/43278

The example will draw the distance to an object as different colors.

A RAY TRACER!!!??, I am thirty minutes new and I see this! This makes me feel there is a long way to go!

I'm not really a Scratch Einstein since I didn't really know Scratch all that well when I started this project.  I've written ray tracers before and this felt like a fun challenge.  There's a bunch of stuff that I messed up on or cheated on to get working since I was trying to do everything from memory.  Once you know the math and how everything works it's really not that hard.

It is not crazy to be a university graduate in mathematics.  I got both a BS and an MS in math before switching to computer science, where I got a PhD.  I now work in bioinformatics (a field also known as computational biology), where the math and computer science both come in handy. 

I have had to keep taking courses, though, as I did not take enough science or statistics when I was a student.  In any case, biology has changed a *lot* since I was a student, as even beginning biology courses contain a lot of molecular biology that simply wasn't known when I was in high school.