Tuesday, November 10, 2009

Reflection and Refraction

After some tinkering with the stats, I got some interesting finds. Many people coming across this blog were searching for "cream pasta", but more importantly, the rest 75% were actually searching for ray tracing topics, especially reflection and refraction. While the image from the last post beautiful as it is, it does not give too much info. Some Java code snipets should help a bit more.
Now reflection is fairly simple. The angle between the reflected ray and the normal is the same as the angle between the incoming ray and the normal.

public static Vec3 reflect(Vec3 normal, Vec3 incident) {
float cosTheta = normal.dot(incident);
return incident.minus( normal.times(2 * cosTheta) );
Calculating the direction of the ray after refraction is a bit more involved. We start with Snell's Law, stating that ratio of the sines of the angles of incidence and refraction is equivalent to the opposite ratio of the indices of refraction, to get the direction of the refracted ray. The outgoing angle is obviously not always defined with this formula, which bring us to the next phenomena. When the light is traveling from a medium with higher optical density to a medium with a lower one and the incident angle is larger than the critical angle total internal reflection occurs and no light leaves the medium. In fact some light is almost always reflected and the amount is governed by the Fresnel equations. In my implementation I just approximate the amount with the dot product (with complete disregard for all the complexities, not to mention frequency and polarization), but the visual result is good.
With some lengthy transformations we can get a formula for the direction of the refracted ray that contains the same condition, defining total internal reflection, as Snell's law. Thus, when the flowing method can't calculate the direction total internal reflection has occurred.

public static Vec3 refract(Vec3 normal, Vec3 incident, float n1, float n2) {
float dn = incident.dot(normal);

float c = 1 - ((n1*n1)*(1-dn*dn) ) / (n2*n2);
if(c < 0)
return null;

Vec3 t = incident.minus( normal.times( dn ) ).times( n1/n2 )
normal.times( (float)Math.sqrt(c)) );

return t;
I hope that was more insightful. Feel free to drop a comment.

Saturday, October 3, 2009

Tracing Rays

I have never considered simple rays more precious than I do now and not just because I am building a ray tracer, but because I have recently moved Utrecht, Netherlands and sunlight is a scarce commodity here. I missed the thrill of long lectures and midterm exams, so am student yet again! Game and Media Technology postgraduate at Utrecht University and so far it's great. This brings me back to my ray tracer and no ray tracer is complete without a Cornell Box and some balls, exhibit below:
It sports a vast number of very basic features (hugely popular in ray tracers from the early 90's) like:
  • Phong materials
  • Anti-aliasing
  • Light reflection
  • Light refraction (with Fresnel reflection)
  • Area light and soft shadows
  • Soft reflections
  • and more to come!
The policy of the university on source sharing is "No." so no code pasting this time, but I am open for questions and discussion. I don't think too many people will find the code useful anyhow and plus you can always download POV ray, which is a world class open source ray tracer.

Wednesday, April 1, 2009

Last.fm and Spinach Pasta

The latest news from Last.fm says that users who are in countries other than USA, UK and Germany will have to subscribe for €3.00 per month for listening to Last.fm Radio. I am not too happy about this, generally because I have discovered a whole bunch of new bands and musicians with Last.fm, even with the very limited selection of songs the service has. In fact lets make an experiment. Go to http://www.last.fm/listen and waste one of your 30 trail plays by typing "Hot Action Cop". I bet "Fever The Flava" will start in few seconds. It is a cool song, but gets a bit old after ten times in the same day. Now €3.00 is not really that much in some countries but the again in some it might be, and the selectiveness is just plain not cool. Being bought up in half country, half zoo one might think that I should have grown immune to any discrimination coming my way, but somehow this bothers me.
Now so far this post has been somewhat informative, but not really helpful. But instead of geeky advices on how to get streaming music now when last.fm has gone all sour, I will tell you what else you can do with €3.00. How about a nice spinach and cream pasta.*

Preheat the oven to 200ºC (473 K). Boil some pasta, preferably whole wheat pasta for this one, in a big bowl. Throw about 150 gr of spinach into a sauce pan and drizzle it with olive oil. Add just a bit of garlic and salt. When the spinach is soft, but still bright green add some white cheese or alternatively some feta cheese. After a minute of stirring, add some cream. As soon as the cream gets homogeneous, reduce the heat to very low and let it simmer. The pasta should be done by now, so drain it and mix it with the creamy sauce. Add some freshly grounded pepper and grated parmesan. Put it in the oven for 20 minutes. Bon appétit!

*Note that the quantities and costs are per serving. The total cost of the meal may vary with to electricity prices and hence country.

Saturday, March 21, 2009


As I wrote the previous post, this week I'll be writing about AI agents. It is a cool subject and I am eager to see what the final results will be. Now, AI might be a strong word for the dumb behavior that this vehicle displays but all the underlying math is there and should provide a basis for development of a more sophisticated system. To make thing more interesting I have decided to implement everything in Silverlight so that can be available in a browser and to test drive the technology while I am at it. Lets see the final result, and than go through the process.

I have used the Vehicles as a title, generally because it's the title of a vary inspirational book by Valentino Braitenberg, that touches the subject of autonomus agents as a early as 1984 and I can recomend it to anyone even remotely interested in the subject. It's just 17$ on Amazon. While this book gives more than enough philosophical background, most of the engeenering is based on the Steering Behaviors by Craig W. Reynolds. Steering behaviors are just simple rules that give steering directions to the vehicles. By smart use and combination of these rules we can build complex behaviors that mimic the behavior a bird or sheep in a flock. Some pepole like Craig W. Reynolds have been working on steering behaviors since the 80's, making them more experinced on the subject than I am in waking, so I will not give a watered down explanation, rather just refer to their pages. What I will give is a some C# code. Now why C# and Silverlight? I have been a long time Flash user for small demos like this one. But having a real programing language like C# is just too good not to try and I am not a huge fan of scripting languages, like Action Script. Plus the tools are completely free. For this post I will implement only the most basic behavoirs seek and flee. Bacause I would like to use it in a Silverlight aplication I will create a Silverlight Library project in Visual Studio. This will be our AI library and should not be aware of any drawing code, so that it can be used in a difirent project, say an XNA game. Now, the first thing that stroke me was that the System.Windows.Vector was just not available on my computer and of course I have the latest SDK. Now instead of wasting couple of days I decided to write my own implementation of a 2D Vector. I think I have done one in every language I have come across. And then a Matrix class implementation to do some transformations over the vectors (I assume knowledge basic linear algebra). With all that in place we can make a simple vehicle class which simply takes the output from the steering behavior and apply is as a force. The update method of the vehicle class looks something like this:

virtual Update(float dt)
Vector2 steeringForce = steering.Calculate();
//Acceleration = Force/Mass
Vector2 acceleration = steeringForce / mass;
velocity += acceleration * dt;
position += velocity * dt;
if (velocity.LengthSq > 0.00000001)
heading = Vector2.Normalize(velocity);
side = heading.Perp;
position.WrapAround(400, 400);
The Seek and Flee methods are extremely simple as you can see:

Vector2 Seek(Vector2 targetPos)
if ((targetPos - vehicle.Position).LengthSq > threshold)
Vector2 desiredVelocity = Vector2.Normalize(targetPos - vehicle.Position) * vehicle.MaxSpeed;
return desiredVelocity - vehicle.Velocity;
return new Vector2(0.0f);

private Vector2 Flee(Vector2 targetPos)
if ((vehicle.Position - targetPos).LengthSq < panicDistanceSq && (vehicle.Position - targetPos).LengthSq > 0.1f)
Vector2 desiredVelocity = Vector2.Normalize(vehicle.Position - targetPos) * vehicle.MaxSpeed;
return desiredVelocity - vehicle.Velocity;
return newVector2(0.0f);

In the Calculate method we just average the force from both, like so:

Vector2 Calculate()
return (Seek(target1) + Flee(target2)) * 0.8f;

Now I want to use that in the Silverlight application, and one of the coolest features in Silverlight, the MatrixTransform class enabling us to apply some affine transformations fast. Anyone who has done some graphics programming will appreciate this. All we need to do is take the heading vector from the vehicle, its perpendicular vector and the position of the vehicle and we have our transformation matrix:

transformMatrix.M11 = vehicle.Heading.x;
transformMatrix.M12 = vehicle.Heading.y;
transformMatrix.M21 = vehicle.Heading.Perp.x;
transformMatrix.M22 = vehicle.Heading.Perp.y;
transformMatrix.OffsetX = vehicle.Position.x;
transformMatrix.OffsetY = vehicle.Position.y;
transform.Matrix = transformMatrix; // Makes sense ha?
shape.RenderTransform = transform;

Just be careful with the origin of the transformation. Expression Blend uses the center by default, while the API will use top left. You can download the code here.

Next week pizza! Just kidding, I’ll be adding obstacles.

Sunday, March 15, 2009

Cave Day

Lets start in a completely reverse order, with a nice photo of the Postojna Cave.
It has been confirmed by a comity of four friends that this place is actually more humid than my apartment in Ljubljana. Which brings me to another topic, I currently live in Ljubljana, Slovenia, where I work for ZootFly, a medium size game studio. The studio is very busy developing a game based on popular TV series by Fox that has lot to do with someone escaping from place where you put convicts in. This somewhat explains the hiatus on this blog. Now to add some twist, next post will be on simple AI agents.