Flash fractals
Today I've been playing with fractals after being inspired by a couple of posts by Nick Porcino on various procedural stuff. Despite being a computer graphics geek I've never before implemented a classical fractal renderer. But I've discovered that it's quite fun and very easy to create some amazing images.
I wrote a GLSL based program that lets you explore the Julia sets associated with the Mandelbrot set. I really liked the interactivity so I wanted to publish it here. But first, I ported it to Flash Player using Pixel Bender (view source enabled source here):
Pixel Bender shaders are quite fast, but since they doesn't support recursive calls (neither does GLSL, AFAIK) or loops (at least when exported to Flash Player) you're a bit limited in the complexity of shaders you can create. I had to unwind my loops and put a hard limit on 20 iterations using 20 if-statements in a row. This also caused a huge performance hit until I nested the statements in groups of five.
If I have the energy I'll look into orbit trapping next. Orbit trapping is a
technique for mapping textures to a fractal space, resulting in images such as
this one (by Tom Beddard):
Playing with expression trees in the rain
In addition to meeting friends and family, my vacation has offered a lot of hacking opportunities, as the weather has been far from optimal. I've been looking into Expression Trees, which is what makes LINQ (a C# 3.0 feature) fly. First of all LINQ stands for Language INtegrated Query (I guess LIQ wasn't such a good name), sort-of SQL integrated into the programming language itself. You can run queries on collections, XML and databases out-of-the-box or you can write your own LINQ provider.
This is where Expression Trees comes into the picture. Expression trees is a feature most often found in compilers as a subset of AST (Abstract syntax trees). Expression trees are data structures for representing expressions. The relation between LINQ and expression trees are not the point of this blog post, lets just say that LINQ ships with an expression tree implementation which can be used for other purposes. The System.LINQ.Expressions namespace (which I think lives in the DLR project on Codeplex, which means it is Open Source under Ms-PL) contains everything you need to create your own expressions and compile them at run-time.
After reading about Expression Trees I digged up a small hack of mine called Symbols. It is a tiny library (just barely a shelf actually) for calculating the derivative of mathematical functions.
Variable x = new Variable(), y = new Variable(); RealNToReal G = x*x + x*y + y*y; RealNToReal dGdx = G.dfd(x); // dG/dx RealNToReal dGdy = G.dfd(y); // dG/dy x.Value = 45; y.Value = 30; Console.WriteLine( "G({0},{1}): {2}, dG/dx({0},{1}): {3}, dG/dy({0},{1}): {4}", x.Value, y.Value, G.Evaluate(), dGdx.Evaluate(), dGdy.Evaluate()); // Outputs G(45,30): 4275, dG/dx(45,30): 120, dG/dy(45,30): 105
Behind the scenes this code actually creates a tree of objects of different types for different purposes. Of course this is very simple since the parsing is implicitly done by the overloaded operators. For example, the object G will contain this tree:
Add Add Mult Variable (45) Variable (45) Mult Variable (45) Variable (30) Mult Variable (30) Variable (30)
But the dfd(Varible v) method explicitly manipulates this tree (actually, it creates a new one), for example dGdx becomes:
Add
Add
Add
Mult
Constant (1)
Variable (45)
Mult
Variable (45)
Constant (1)
Add
Mult
Constant (1)
Variable (30)
Mult
Variable (45)
Constant (0)
Add
Mult
Constant (0)
Variable (30)
Mult
Variable (30)
Constant (0)
As you can see there is room for optimizations (reduce multiplications of 1 and 0, anyone?). However, this is a perfect example of Expression Trees, though I didn't realize it when I wrote it. But I've now added a method that creates a System.LINQ.Expression from a RealNToReal tree. This allows the tree to be compiled to a delegate, which means much faster evaluation (execution actually) and more convinience:
var lambda = dGdx.GetExpression<Func<double, double, double>>(); var comp = (Func<double, double, double>)lambda.Compile();
I also wrote this snippet to find out the difference in execution time:
Func<double, double, double> eval = (X, Y) => { x.Value = X; y.Value = Y; return dGdx.Evaluate(); }; start = DateTime.Now; for (int i = 0; i < 1000000; i++) eval(i, 45); TimeSpan diff1 = DateTime.Now - start; start = DateTime.Now; for (int i = 0; i < 1000000; i++) comp(i, 45); TimeSpan diff2 = DateTime.Now - start; Console.WriteLine(diff1); Console.WriteLine(diff2); Console.ReadLine();
Which outputs something like
00:00:00.6084000 00:00:00.0156000
most of the time. Sometimes the difference is less though, but what varies is the evaluated tree, not the compiled method. One important thing is the cast to the delegate type (Func<double, double, double>). If this is not performed you'll have to run the method using DynamicInvoke, which is much slower! Spent some time wondering why my tree evaluation was faster than the compiled method. Lesson learned.
If anyone else is bored by crappy weather, feel free to play around with the code: Symbols.cs.
Rigs of Rods
I've been watching videos from Channel 9 lately, especially those featuring Brian Beckman. He is a former physicist now working at Microsoft. His videos mostly deals with functional programming, but last night I watched one called The Physics in Games in which he mentioned this awesome project, Rigs of Rods. It is a truck simulation game with fantastic physics. But rather than combining domain-specific physics like rigid body simulation, tire and engine physics, only one simulation method is used. All models are built up by masses connected by springs and dampers. Watch this awesome video:
A couple of years ago I did a similar simulation, although I only simulated a single cube falling on a single triangle. I had no dampers and I used forward euler integration, so it was not very stable either. This was before I learned "how to do simulations", but maybe that was the right track after all.. I just wished I had continued that project. Back then I actually had time for such things..
Using Lambda expressions to step through algorithms
Debugging number-crunching algorithms can be hard, and when the algorithm actually ends up as something visual (as in computer graphics), it feels somewhat awkward to break the executing program and use the debugger to look at numeric data.
To debug my rigid body simulator I wanted a way to break/step/continue through the algorithm while still running the graphics loop so that I can inspect the collisions visually. I came up with a nice way to do this in C# using Action delegates and Lambda expressions.
This is the original algorithm (simplified here as it is not the focus of this blog post):
for (int i=0; i<5; i++) {
advance(true,false,false);
detectCollisions();
collisionResponse();
}
advance(true,true,false);
detectCollisions();
contactResolution();
advance(true,true,false);
What I did was that I encapsulated each call in a lambda expression and stored them in a list:
Action [] myAlgorithm = new Action []{
() => i = 0,
() => advance(true,false,false),
() => detectCollisions(),
() => collisionResponse(),
() => { if (++i < 5) executionPointer = 1; },
() => advance(true,true,false),
() => detectCollisions(),
() => contactResolution(),
() => advance(true,true,false),
};
Then I wrote a simple class with a few methods for executing this sequence. A method called Run which runs the whole sequence once (from the current position), a method Step which just executes the next statement (perhaps I should call it method or even expression, but it’s really just a wrapped statement).
AlgorithmStepper stepper = new AlgorithmStepper();
stepper.Algorithm = myAlgorithm;
...
while (Running) {
renderScene();
if (UserPressedAMagicButton)
stepper.Step();
if (UserPressedAnotherMagicButton)
stepper.Run();
}
This way I can have a fully interactive application, with a frozen simulation in it. I can visualize the current state of objects, their velocities and any found collision points, collision normals and penetration depths, and just press a button to execute the next part of the algorithm (to see what is going wrong…).
One problem here is that I need to step a whole lot of times before something interesting happens. To make things a little bit easier I added a third method to the AlgorithmStepper class, namely RunToBreak(), which runs the algorithm until a fourth method Break() is called. I could then add a conditional break to the algorithm:
Action [] myAlgorithm = new Action []{
() => i = 0,
() => advance(true,false,false),
() => detectCollisions(),
() => collisionResponse(),
() => if (CollisionsFound) stepper.Break();
() => { if (++i < 5) executionPointer = 1; },
() => advance(true,true,false),
() => detectCollisions(),
() => contactResolution(),
() => advance(true,true,false),
};
This does not in any way replace looking at numerical data, but it has been a really nice complement on the road to understand problems in the simulation. And yet another reason to be happy I made this in C#.
What is a lambda expression?
I’ve got a few comments about my blog posts not being easy to follow, so I’ve split the next topic in two posts. In the next post I'll show you how I did (sort-of) continuations using lambda expressions, to be able to visualize different states in an algorithm. If you know what lambda expressions are you can ignore this post.
Code is data too
Lambda expressions are the fundamental concept of lambda calculus. If you ever touched a functional programming language you already know how to use them. I won't get into the theory behind them, only enough for you to use them in C#. Simply put: in C#, a lambda expression is a dead-easy and elegant way to declare an anonymous function. Anonymous functions are as the name implies functions without names, which in practice means that they are not declared as either class or instance functions, but rather as data. JavaScript has a very clear way to define anonymous functions, so I’ll use that as a first example:
var myFunction = function (x) { return x*x*x; };
As you can see, anonymous functions are stored in variables. You call the function by calling the variable, for example myFunction(4); Anonymous functions are very useful, they can be used to execute code when a file transfer is finished or when a button is clicked. In C#, prior to version 3.0, the way to define anonymous functions was like this:
// inside a class or namespace, declare a delegate prototype: delegate int MyFunctionDelegate(int x); // inside a code block: MyFunctionDelegate myFunction = delegate (int x) { return x*x*x ; };
The first line defines the function signature or prototype, because in C#, anonymous methods are strictly typed. The second line is more similar to the JavaScript code, but two important things have changed; we must use a type for the variable, this is the type we defined on the first line. The second is that “function” has changed to “delegate”. A little less clear IMHO, but it gets better. In C# 3.0, lambda expressions were introduced, and along with them, a bunch of predefined prototypes. I will not go in to those here, except for the one I will use in the next post, Action, which is a prototype for functions that does not return anything and takes no arguments (OK, the other important one is Func):
public delegate void Action();
A lambda expression is a short way of defining an anonymous method. The only thing you need to write is the argument names in parentheses followed by “=>” and followed by an expression. The types are implicitly defined by the prototype, so the declaration is very compact. Here is an example:
using System; public class LambdaExpressionExample { static Action myFunction; public static void Main() { // store a method myFunction = () => Console.WriteLine("Hello world"); // outputs "Hello, world" myFunction(); // store another method myFunction = () => Console.WriteLine("Good bye, cruel world"); // outputs "Good bye, cruel world" myFunction(); Console.ReadLine(); } }
Rigid Body Simulation, 2009 edition
A couple of years ago me and a couple of friends (Jonas, Nypan and Henke) developed a rigid body simulator as a course project. I’ve considered it the project I’m most proud of so far, only now perhaps superseded by GAV Flash and OECD eXplorer (and winning the MT-Awards with Linnaeus made me proud of that too, of course).
Back then, we had a lot of trouble with collision detection and its performance. I’ve since then felt that I’ve matured quite a bit as a programmer and also picked up a thing or two about collision detection. So last weekend I decided to try and implement another rigid body simulator to see what I would do different and what performance I could achieve.
Last time we only used AABBs and then tested triangles against vertices and edges against edges for each triangle. What I did different this time around:
- Sweep-and-prune AABBs (very effective)
- A triangle-triangle query, either based on separating axis theorem or Tomas Möller's algorithm
- On intersecting triangles A & B, test points from A against surface of B, then vice versa
- Test edges only if triangle query positive but no other collisions found in step 3.
I got the system into a semi-working state quite quickly, but just like last time I’m having some problems with collision detection. But even though I haven't done any optimizations I have a lot better performance than the old project. Now I’ve started to use some interactive visualizations to debug the collision detection issues and will post about that again later. Btw, I think the use of visualizations in software debugging and profiling is a very interesting subject.
In the screen shot below (yes, the colorless one with the lame lighting), 60 bodies are simulated at approximately 90 fps.
The (convex) bodies are randomly generated using a simple scheme; a couple of vertices are placed at random positions on a circle, in addition to two vertices placed on each side of the circle, right above/below the center. Each triangle is made up of two vertices from the circle and one of the other points:
Using scons with gcc/mingw on windows
Just spent way too much time trying to get scons (an alternative to 'make' and 'makefiles') to build one of my projects on windows using gcc/g++/mingw. The scons documentation was not very helpful, but in the end it was quite easy:
#SConstruct
import platform
import os
...
if platform.system() == 'Windows':
env = Environment(tools = ['mingw'], ENV = os.environ)
env.PrependENVPath('PATH', 'C:\\Dev-Cpp\\bin')
env.PrependENVPath('LIB', 'C:\\Dev-Cpp\\lib')
else:
env = Environment(ENV = os.environ)
...
env.Program(['main.cpp'], LIBS = libs, LIBPATH=libpath, CCFLAGS=cflags)
As you can see I'm using the compilers and libraries distributed by Dev-C++, hard-coded the paths for now. Good night internets.
Check the details
Thank you, Adobe, for the helpful information.
Accept javascript as the one-and-only language of the future?
Update: comments work again. Thanks to Aaron for reporting the problem.
The major problem with the web/html as an application platform is the lack of choice when it comes to programming/scripting languages on the client side. The de facto (and to some extent de jure) language on the client side is (as we all know) javascript.
A lot of code execution needs to be done on the client side to have acceptable performance (no one would render 3D-games on the server side and then transport them to the client). Much other code execution is preferably done on the client side as well - any type of signal processing - like audio, image and video processing. These applications would put a lot of load on the servers. Why concentrate computing power instead of letting it stay (in a way) distributed?
I'm not saying that javascript cannot do these things - because obviously it can. I'm just saying that a whole lot of other languages are used by programmers today and are preferred for different reasons.
IMO, instead of javascript, a language independent runtime (or VM) should be shipped with the browsers. This runtime shouldn't even assume that the languages are dynamic (python and javascript doesn't differ that much, other than syntax). This way programmers can use whatever language they prefer and compile the code into bytecode that can be executed by this runtime.
The sad thing about this is that code will no longer be open by default but instead compiled. I learned all javascript, css and html I know today by reading other's page sources. In the world I'm describing the programmers of the future won't have that possibility.
Note that greasemonkey and similar browser plug-ins would still be possible, albeit a bit harder to write if you don't have access to the code of the application you are modifying. Although, with sensible object introspection (aka reflection) in the runtime that shouldn't be too bad either.
Flex framework debugging
One of the great features of Flex is that the SDK is open source. Even better is the integration of the Flex Framework source code in Flex Builder. I will now explain how I came to the conclusion that Flex swallowed an exception without even a warning (at least during compile or run time).
A couple of weeks ago I was debugging a weird behavior in GAV Flash. For some reason, a particular event handler was never called, even though the event must have been registered, I thought. The following code snippet is a much simplified version of the class I was debugging (also, I might have renamed a few properties):
package { import flash.events.MouseEvent; import mx.controls.Button; public class MyComponent extends Button { private var _factory: IncompleteClass = new ChaChaFactory (); private var _theChaCha: String; private var _doTheChaCha: Boolean = false; public function set doTheChaCha(b: Boolean): void { if (doTheChaCha) removeEventListener(MouseEvent.CLICK, onMouseClick); _doTheChaCha = b; if (doTheChaCha) { _theChaCha = _factory.getTheChaCha(); addEventListener(MouseEvent.CLICK, onMouseClick); } } public function get doTheChaCha(): Boolean { return _doTheChaCha; } private function onMouseClick(event: MouseEvent): void { label = _theChaCha; } } }
When the doTheChaCha setter is called with b = true, I would expect the MouseEvent.CLICK-event to be properly registered and thus the event handler onMouseClick to be called when an instance of this button gets clicked.
But, onMouseClick was never called. I fired up the Flex Debugging perspective and put a breakpoint on if (doTheChaCha). As I expected, doTheChaCha was true. I put breakpoints on each of the following two lines and hit "Resume", and the debugger stopped on the following line. What completely upset me was that the next time I hit “Resume”, the debugger did
What in the name of the… major bug in AVM2? Yes it is, obviously.
Someone once said that "
So, I stepped into getTheChaCha() by putting a breakpoint on the first line. Everything went fine. I also put a breakpoint on the only return-statement in that method. Again, the debugger
But where did the exception go? Thanks to the open source nature of the Flex Framework I was able to step into the calling code. The setter was called from MXML using a binding to another property. And it turns out that the exception is caught in Binding::wrapFunctionCall(*) and then silently ignored.
A comment in the Binding.as-file states:
// Certain errors are normal when executing a srcFunc or destFunc,
// so we swallow them:
// Error #1006: Call attempted on an object that is not a function.
// Error #1009: null has no properties.
// Error #1010: undefined has no properties.
// Error #1055: - has no properties.
// Error #1069: Property - not found on - and there is no default value
// We allow any other errors to be thrown.
Good choice, Flex Team – it only cost me half an afternoon. OK, it was my fault – but a runtime warning would have saved a lot of time. However, I'm glad that I could debug the framework code, so that I could enlightened about what was happening.
Book meme
- Grab the nearest book.
- Open it to page 56.
- Find the fifth sentence.
- Post the text of the sentence in your journal along with these instructions.
- Don’t dig for your favorite book, the cool book, or the intellectual one: pick the CLOSEST.
"If the points on the dividing plane are considered included in the halfspace, the halfspace if closed (otherwise , it is called open)."
From Christer Ericson's Real-time collision detection. Awesome book by the way.
Functional programming: F# ray tracer
I'm subscribed to a lot of blogs. I don't really read a lot of them, I mostly scroll through them and look for interesting news or subjects. Sometimes I find particularly nice posts, like a couple of weeks ago; Christer Ericsson blogged about functional programming. I've been curious about learning a functional language since then.
I try to do some recreational programming every other weekend when Jennie is working, to develop my skills and to recapture the fun. So when I was in need of a project for last weekend I had two alternatives; to port Moonlight to the iPhone, or; do something with a functional language. The first alternative (that of course was an idea born out of alcohol) seamed a bit to ambitious. So I settled for the second, and decided that "do something" meant "write a ray tracer".
Functional programming is a different beast from "ordinary" (imperative, procedural, object oriented) programming:
- Instead of storing values of computations in variables you often see nested function calls, pattern matching and pipelines. Storing values in objects is known as a 'side effect' in CS lingo, so is I/O. In functional programming you often try to avoid functions with side effects. A function that has no side effects is called a pure function. Those are easier to optimize and parallelize, something that is becoming increasingly important (as all of us know by now, I guess).
- Recursion is often used instead of loops, in fact, loops doesn't exist as you might know them. Recursion might sound ineffective and limiting (call stack overflows etc.), but a lot of common recursions are optimized away by the compiler.
-
Type declarations are often short, defined in a mathematical way and they can be recursive.
Defining a binary tree data type in F# is as easy as:
type Tree = | Leaf of int | Node of int * Tree * Tree
An instance of this tree is also easy to create:
let myTree = Node(3, Leaf(1), Node(2, Leaf(3), Leaf(4)))
Which describes the tree:
I decided to go with F# for my ray tracer, a functional language created by Microsoft and released as a technology preview. It is compiled into a .NET application, which means that you can reference and use all the classes in the .NET Framework. This of course isn't of much use to a ray tracer, the only classes I used were the System.Drawing.Bitmap and System.Drawing.Color classes to save the rendered image as a png.
Results so far:
x86 assembly in C# revisited
As I mentioned, the original code I wrote didn't run on Windows with .NET, but it ran on Windows using Mono. However, after digging a little deeper (with the help of the nice folks at mono-list) I found that the problem wasn't the runtime stopping me from executing code, but rather my assembly code being invalid (who would have thought ;-) ?). Or more precisely, the code didn't follow certain conventions that must be followed.
The assembly code works if compiled into a single program, but when interacting with (here, being called by) other methods written in other languages, there are certain rules that must be followed so that the stack and registers aren't messed up while executing. There are certain registers that must be the same after the method returns, and the stack pointer must either be untouched or properly changed (depending on which convention is used).
After getting that last one right I thought that my code was OK, and that was when I posted the C# code. However, what I didn't get right was that the ebx register (and a few others) must not be changed (mov ebx 9 is essentially assignment; ebx = 9).
So this time I let GCC do the work for me by compiling a single C function and then disassemble it. After that it's just inserting the opcodes in the C# array just like the last time:
using System; using System.Collections.Generic; using System.Text; using System.Runtime.InteropServices; class X86AssemblyExec { [UnmanagedFunctionPointer(CallingConvention.Cdecl)] private delegate int TheDelegate(); public static void Main(string[] args) { // 0: 55 push ebp // 1: 89 e5 mov ebp,esp // 3: 83 ec 10 sub esp, 16 // 6: c7 45 fc 06 00 00 00 mov [ebp-4], 6 // d: c7 45 f8 0c 00 00 00 mov [ebp-8], 12 // 14: 8b 45 f8 mov eax,[ebp-8] // 17: 01 45 fc add [ebp-4],eax // 1a: 8b 45 fc mov eax,[ebp-4] // 1d: c9 leave // 1e: c3 ret // opcode List<byte> codeList = new List<byte>(); codeList.Add(0x55); codeList.Add(0x89); codeList.Add(0xe5); codeList.Add(0x83); codeList.Add(0xec); codeList.Add(0x10); codeList.Add(0xc7); codeList.Add(0x45); codeList.Add(0xfc); codeList.Add(0x06); codeList.Add(0x00); codeList.Add(0x00); codeList.Add(0x00); codeList.Add(0xc7); codeList.Add(0x45); codeList.Add(0xf8); codeList.Add(0x0c); codeList.Add(0x00); codeList.Add(0x00); codeList.Add(0x00); codeList.Add(0x8b); codeList.Add(0x45); codeList.Add(0xf8); codeList.Add(0x01); codeList.Add(0x45); codeList.Add(0xfc); codeList.Add(0x8b); codeList.Add(0x45); codeList.Add(0xfc); codeList.Add(0xc9); codeList.Add(0xc3); byte [] code = codeList.ToArray(); unsafe { fixed (void *ptr = code) { // create the delegate TheDelegate del = (TheDelegate) Marshal.GetDelegateForFunctionPointer( new IntPtr(ptr), typeof(TheDelegate)); // call the function int x = del(); // outputs 18 Console.WriteLine(x); } } } }
The difference is that now it runs on MS .NET too!
x86 assembly in C# apparently Mono/Linux only
Tried the code from my post this morning on Windows with the MS .NET runtime and I couldn't get it to run, it threw an AccessViolationException. Don't know if there is a way around it, if I should expect it to fail on Linux too in a later version of Mono or if I should write the assembly code differently for it to run on Windows, but right now it doesn't work.
Inline x86 assembly in C#
Well, not exactly inline. But yesterday I found a way to execute arbitrary x86 code as a function call in C#. I actually thought it would be much harder but it turned out to be only a couple of lines (in addition to the assembly code).
What make it work is the UnmanagedFunctionPointer attribute which creates a delegate from a C-style function pointer. The only thing you need to know is the address of the function in memory.
The actual assembly code is stored in a byte array, which we can get a pointer to using unsafe C# code.
I don't know how fast these delegates are; any performance you make up by writing optimized assembly code, you might loose in the overhead of the delegate call. But, I'm optimistic and perhaps I'll get the time to profile this some day.
In this simple example, the assembly code adds two integers (8,9) and returns the value (17):
using System; using System.Text; using System.Runtime.InteropServices; class X86AssemblyExec { [UnmanagedFunctionPointer(CallingConvention.Cdecl)] private delegate int TheDelegate(); public static void Main(string[] args) { // C: // int eax = 8; // int ebx = 9; // eax += ebx; // return eax; // x86 assembly: // mov eax 8 B8 08 00 00 00 // mov ebx 9 BB 09 00 00 00 // add eax ebx 01 d8 // ret C3 // opcode byte [] code = new byte[14]; code[0] = (byte) 0xB8; code[1] = (byte) 0x08; code[2] = (byte) 0x00; code[3] = (byte) 0x00; code[4] = (byte) 0x00; code[5] = (byte) 0xBB; code[6] = (byte) 0x09; code[7] = (byte) 0x00; code[8] = (byte) 0x00; code[9] = (byte) 0x00; code[10] = (byte)0x01; code[11] = (byte)0xd8; code[12] = (byte)0xC3; code[13] = 0; unsafe { fixed (void *ptr = code) { // create the delegate TheDelegate del = (TheDelegate) Marshal.GetDelegateForFunctionPointer( new IntPtr(ptr), typeof(TheDelegate)); // call the function int x = del(); // outputs 17 Console.WriteLine(x); } } } }
More GPU ray tracing
Worked a little bit more on my GPU ray tracer today, an hour or so. Spent most of the day cleaning and updating my CV and my portfolio page. However, I managed to get reflections working (again actually):
The tricky part is that GLSL doesn't support recursive functions, so reflections has to be done in a loop, which isn't much harder, unless you also want refractions, sss or anything else that requires more than one ray. In that case you'll have to look into creating some sort of stack with new rays. I don't think I'll go down that road, will most likely limit myself to diffuse surfaces if I am to work more with this.
Saturday night hacking
Haven't done any 3D programming in a couple of months so I felt a bit rough around the edges when I this week took up my project in a course in procedural methods for imaging. However, it triggered some ideas.
After a long walk with the dog and some running I decided to sit down and see how far I could get on a GPU-only ray tracer. So far so good:
The implementation is far from general, it cannot render polygon meshes and the whole scene (except for light sources, for a change! :-D) is defined in the shader. The implementation uses distance fields for all bodies, so instead of explicitly solving for an intersection between the ray and objects, I use a method presented here.
The method in short:
- Sample the distance field at the current point
- If the distance is "close enough" to an object, we have an hit. Here you either stop tracing and we have a shadow in the last iteration, you do a reflection/refraction and continue along that ray, or you send one ray to each light source to see if this surface is lighted.
- If not (close enough), we walk along the ray the distance sampled before. We will end up somewhere in space, but we know it is not inside an object. This new position is our new current, and we go back to point 1
As you can see I only have three types of objects: floor, sphere and capsule. These are the only objects I've implemented distance fields for so far, but I'll extend this tomorrow, perhaps with some discrete (3D-texture) objects or some noise based procedural ones.
Might even use this as renderer for the previously mentioned course project.
GAV Flash based Google Spreadsheet Gadget
Been hacking a bit on my spare time on a Google Spreadsheet Gadget that incorporates the
visualization components that we've been developing. Thought I'd share a screenshot of
something running:
GEdit language files for MXML, ActionScript and GLSL
(I know it's "gedit" and not "GEdit", but the former looks horrible at the beginning of a sentence and especially in a title on, say, a blog.)
I've written a MXML language file for gedit based on
Julien Castelain's ActionScript language file
and the default XHTML language file that comes with gtksourceview-2.0. A language file let
gedit or any program that used gtksourceview (like Anjuta and Mono Develop) do proper syntax highlighting for the given language. This makes hacking Flex under Ubuntu a pleasure since I've grown used to gedit's ways of doing things.
I've also modified Juliens language file to support a few new language features like get/set functions. I also moved the const keyword from 'reserved' to 'declarations'.
Download: actionscript.lang MXML.lang
Put these files in ~/.local/share/gtksourceview-2.0/language-specs/ or in /usr/share/gtksourceview-2.0/.
GLSL
This reminded me that I also created an OpenGL Shading Language (GLSL) language file a while back.
Download: glsl.lang
Again, put it in ~/.local/share/gtksourceview-2.0/language-specs/ or in /usr/share/gtksourceview-2.0/.
ActionScript BitArray
A couple of weeks ago I decided to take the plunge and implement a BitArray in ActionScript 3 for use in GAV Flash. I had designed a event based infrastructure to communicate (boolean) item status changes between a bunch of graphical components. But I found myself again and again storing the item status in each of these components and decided that I had to do something about this and have the storage in one place.
Before I implemented it I took a look around the internets for other implementations, but didn't find any. So I thought I'd make other people in my situation happy by posting here.
So, here is the BitArray.as for download or view:
package gav.utils { /** * @author markus <markus.johnsson.84@gmail.com> */ public class BitArray { private static const LAST_BIT: uint = 0x80000000; private static const FIRST_BIT: uint = 1; /** * Constructs a BitArray of the given length */ public function BitArray(length: uint=0) { var fields: uint = uint(Math.ceil(Number(length)/32.0)) || 1; _bitFields = new Array(fields); for (var f:uint=0; f<fields; f++) _bitFields[f] = uint(0); _bitLength = length; } private var _bitFields: Array; //----------------------------------------------------------------------------------------- // // Properties // //----------------------------------------------------------------------------------------- //----------------------------------------------------------------------------------------- // length //----------------------------------------------------------------------------------------- private var _bitLength: uint; /** * The length of the array. * * Will add zeros to the end if the new length is longer than the previous. */ public function get length(): uint { return _bitLength; } public function set length(s: uint): void { if (s == _bitLength) return; if (s < _bitLength) { while (s < _bitLength) remove(_bitLength-1); } var fields: uint = uint(Math.ceil(Number(s)/32.0)) || 1; while (fields > _bitFields.length) { _bitFields.push(uint(0)); } _bitLength = s; } //----------------------------------------------------------------------------------------- // all //----------------------------------------------------------------------------------------- /** * Returns true if all bits are 1. */ public function get all(): Boolean { for (var i:uint=0; i<_bitFields.length-1; i++) { if (uint(_bitFields[i]) != uint.MAX_VALUE) return false; } var lastBitIndex: uint = (_bitLength & 31); var mask:uint = ~(uint.MAX_VALUE & ((1 << lastBitIndex)-1)); // if lastBitIndex is 3, mask = (11111111 11111111 11111111 11111000) // if lastBitIndex is 6, mask = (11111111 11111111 11111111 11000000) // etc var word: uint = _bitFields[_bitFields.length-1]; var result: uint = word | mask; return result == uint.MAX_VALUE; } //----------------------------------------------------------------------------------------- // any //----------------------------------------------------------------------------------------- /** * Returns true if any bit is 1. */ public function get any(): Boolean { for (var i:uint=0; i<_bitFields.length; i++) { if (_bitFields[i] > 0) return true; } return false; } //----------------------------------------------------------------------------------------- // // Public methods // //----------------------------------------------------------------------------------------- /** * Adds a bit to the end of the array. */ public function push(value: Boolean): void { var lastFieldIndex: uint = _bitFields.length-1; // == (_bitLength / 32)-1; var lastBitIndex: uint = (_bitLength - 1) & 31; // == (_bitLength-1) % 32; if ( _bitLength == 0 ) { lastFieldIndex = 0; lastBitIndex = 0; } else if ( lastBitIndex == 31 ) { _bitFields.push(uint(0)); lastFieldIndex++; lastBitIndex = 0; } else { lastBitIndex++; } var mask: uint = (1 << lastBitIndex); var word: uint = _bitFields[lastFieldIndex]; _bitFields[lastFieldIndex] ^= (-uint(value) ^ word) & mask; // // above is same as below, without branching (i.e. cooler). // // if (value) // _bitFields[lastFieldIndex] = word | mask; // else // _bitFields[lastFieldIndex] = word & ~mask; // _bitLength++; } /** * Removes the bit at the given position. */ public function remove(index: uint): void { var fieldIndex: uint = uint(index / 32); var lastFieldIndex: uint = _bitFields.length-1; if (fieldIndex > lastFieldIndex) throw new RangeError("index"); var bitIndex: uint = index & 31; var word: uint; var next: uint; var shift: uint; var mask: uint; word = uint(_bitFields[fieldIndex]); // 1110 1011 1010 1101 1110 1011 1010 1101 shift = (word >>> 1); // 0111 0101 1101 0110 1111 0101 1101 0110 mask = (1 << bitIndex)-1; // 0000 0000 0000 0000 0000 0000 0001 1111 // shift the last part of the word one bit right _bitFields[fieldIndex] = shift ^ ((shift ^ word) & mask); // 0111 0101 1101 0110 1111 0101 1100 1101 // // above is same as below, with one op less. // // _bitFields[fieldIndex] = (word & mask) | (shift & ~mask); // while (fieldIndex < lastFieldIndex) { word = uint(_bitFields[fieldIndex]); next = uint(_bitFields[fieldIndex+1]) // copy first bit in next word to last bit in the current word var firstbit: uint = next & FIRST_BIT; //_bitFields[fieldIndex] ^= (-uint(firstbit>0) ^ word) & LAST_BIT; if (firstbit > 0) _bitFields[fieldIndex] = word | LAST_BIT; // shift the next word one bit _bitFields[fieldIndex+1] = (next >>> 1); fieldIndex++; } _bitLength--; } /** * Returns the value at the given position. */ public function getAt(index: uint): Boolean { var bitIndex: uint = index & 31; // index % 32 var fieldIndex: uint = uint(index / 32); var mask: uint = (1 << bitIndex); var word: uint = _bitFields[fieldIndex]; return Boolean(uint(word & mask)); } /** * Sets the value at the given position. */ public function setAt(index: uint, value: Boolean): void { var bitIndex: uint = index & 31; // index % 32 var fieldIndex: uint = uint(index / 32); var mask: uint = (1 << bitIndex); var word: uint = _bitFields[fieldIndex]; _bitFields[fieldIndex] ^= (-uint(value) ^ word) & mask; } } }
RSS and comments
Finally added a RSS feed and a comment system to the site,
so I guess now I can actually call it a blog.
Django really makes this stuff easy and python is a pleasure to work with after using ActionScript only for three months. When will I need C# for actual work?
Also updated the graphics of the site. Still no Flex version though.
GAV Flash updated web site
My boss put up a new web site for the project I'm working on at the university yesterday. The project is called GAV Flash (where GAV = GeoAnalytics Visualization) and 'Flash' is referring to Adobe Flash ™. From the site:
GAV Flash provides a collection of interactive GeoAnalytics visualization components
based on state-of-the-art technique from the information and geovisualization research domain.
Many features needed in a visual explorative and analytical reasoning process are included such
as coordinated multi-linked views, multivariate attribute data exploration,parallel coordinates
with embedded dynamic visual inquiries and highlighted outliers.
There are also links to demo applications on the site: OECD eXplorer and SCB eXplorer. The names of the applications hints about what is to come in the future.
You will most likely hear about the project a couple of times if you stay tuned.
Links from an old wiki
I removed a wiki for a short-lived project named "WoW" (short for Wascally Outwageous Wobots), that me and a couple of friends begun designing. I had collected a couple of links there, so I'll post them here instead:
- Alex J. Champandard (Rockstar Games, Guerrilla) aigamedev.com blog/tutorial collectoin about the AI-parts in game development. Some of the earlier posts have more general topics:
- Nick Porcino (Disney Iteractive, LucasArts) meshula.net blog with mixed topics. Some interesting posts about the engine used in Lost Planet:
- Finding Next Gen - CryEngine 2 paper from SIGGRAPH 2007 about graphics in the Crysis engine.
New Flango based site coming up
Just wanted to say that I'm working on a new web site, based on Django and Flex (a combination known as Flango). I have no deadline for the new site, but will post here now and then during the development.
So far I've decided to have a blog to rant about stupid things, and hopefully also write a few post that could actually be interesting to people, especially to those people interested in programming, computer graphics or web development. I'm also going to create a portfolio to show some of the projects I've worked with so far in my young career.
Some of the challenges with the new site is that, while I want to use Flex, I also want to be able to use ads (preferrably Google Adsense). Another (most likely easier) is that I want it to be search engine friendly. Guessing the last one is easier, but I can't say that I often stumble upon flex apps when I'm googling.
© 2008 Markus Johnsson