signalsondisplay

I’m moving to blog.signalsondisplay.com.
I will not be updating this blog anymore, except for stuff related to AS3.0.
Peace out.

Writing “compilers” seems to be all the rage lately, especially in the Javascript community (I feel bad for you guys…). So here is my contribution to the world of compiling one language to another: brainfuck to C.
Now I’m sure we both agree that it’s pointless, many people have done it before and done it better, but it’s fun and I haven’t posted anything in a while so there!

So, how does this awesome bloody compiler work ?! Like any other, pass in the source file, and the destination file, and voila!

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
#include "BFTranslator.h"
 
int main( void )
{
	BFTranslator t;
	if (t.translate( "infile.txt", "outfile.txt" ))
		std::cout << "hooray, it worked!" << std::endl;
	else
		std::cout << "oops, something went wrong =[" << std::endl;
	return 0;
}

So, with this awesome tool, now you can turn this horrible code:

1

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

into this:

1
2
3
4
5
6
7
8
9
10
11
12
13

#include<stdio.h>
int main(){char m[60000]={0};char *p=m;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;
(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;while(*p){p++;(*p)++;(*p)++;(*p)++;
(*p)++;(*p)++;(*p)++;(*p)++;p++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;
(*p)++;(*p)++;(*p)++;(*p)++;p++;(*p)++;(*p)++;(*p)++;p++;(*p)++;p--;p--;
p--;p--;(*p)--;}p++;(*p)++;(*p)++;putchar(*p);p++;(*p)++;putchar(*p);
(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;putchar(*p);putchar(*p);
(*p)++;(*p)++;(*p)++;putchar(*p);p++;(*p)++;(*p)++;putchar(*p);p--;p--;
(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;
(*p)++;(*p)++;(*p)++;(*p)++;(*p)++;putchar(*p);p++;putchar(*p);(*p)++;
(*p)++;(*p)++;putchar(*p);(*p)--;(*p)--;(*p)--;(*p)--;(*p)--;(*p)--;
putchar(*p);(*p)--;(*p)--;(*p)--;(*p)--;(*p)--;(*p)--;(*p)--;(*p)--;
putchar(*p);p++;(*p)++;putchar(*p);p++;putchar(*p);}

And there you have it! If you compile the unreadable C code it will print out those two words every programmer knows, “Hello world!”.

Make sure you get the source:
BFTranslator.cpp, BFTranslator.h.

So… alchemy… yeah. Install a bunch of crap on your system, write C/C++ code, compile it to a swc with gcc/g++, wait for the compiler to finish it’s work, use that heavy as hell swc in your AS3 code… realise calling alchemy code often is a performance killer, minimise calls to alchemy functions/code, write more C/C++ code…
It’s a little redundant to say the least, and thank god I use a Makefile…
All in all alchemy is a pain in the ass, in my opinion.

Anyway, I tried it out and got a small real time raytracer working, with a couple lights, some spheres and reflections. There is no way that would be possible in pure AS3 (well, I’m incapable of doing it in pure AS3), so there is no doubt alchemy give a pretty neat performance boost to AS3. Now that’s cool, and people have been doing some cool stuff with it. But then I think, if alchemy code if the same thing as compiled AS3, why the hell is it faster ? I’ve not really gotten into the details of what happens to the nice C code after the llvm has it’s way with it, but when I think about it, it’s like someone is asking me the meaning of life.

Ah well, who cares in the end, the performance is there, let’s take advantage of it.

About raytracing in AS3, there are a few better ones than mine out there. Frank is using alchemy, David too (I think), and Simo is using pixel bender, and I’ve done another one, not in real time and without alchemy, that I might finish one day if I get some time. It’s really cool to see where people are taking AS3, and pushing it to it’s limits.

non-real time:

real time:

A quick note: all this happens in model space. All vectors are relative to the model origin (0, 0, 0), they are said to be in standard position, such a vector is also called “position vector”.
A vector in standard position can be used to represent a point in 3D space (a vertex). The location of the tip of the vector corresponds to the location of the vertex.
I use the term vertex and vector interchangeably.

In part 1, I roughly explained how displacement maps work, and how you can use them to distort an image. This time, we are going to use the data from the displacement map to “distort” a 3D model. The model I used is a sphere, it’s a little boring, I know, but it’s easy to apply this to any model.

The idea is pretty simple. For each vertex in the model, get a displacement value and then scale the vertex by that same value.

Just like last time, you first to create a displacement map, usually using the perlin method on the BitmapData class. We need to create a BitmapData instance that has one pixel for each vertex in the model. So, say you have a model with 745 vertices, we need a displacement map with 745 pixels, in order to have one pixel per vertex and thus, one displacement value per vertex.

Then we need to iterate over each pixel the map and grab it’s colour. For each pixel, we get corresponding vertex.
Now that we have a colour value and a vertex to modify, we need to map the value from 0/255 to -.5/1.5. We then have a scalar in the range -.5/1.5 to scale the current vertex.

As an example, let u = (145, -78, 108) be the 9th vertex in the model.

Let the displacement value d = 1.4 be the mapped coluor from the 9th pixel in the displacement map. We multiply each component of the vertex by that value d, and that gives us the displaced position for that vertex.

Doing this on each vertex of the model, with a smooth displacement map will smoothly distort your 3D model.

Here is the result. The sphere is rendered using (unoptimised) custom code, no 3D engine or API is being used. If you want the source, let me know.

A few thoughts:

• This could be a way to create 3D soft bodies, without using complex physics.
• The AS3 “3D API” or “2.5D API”, call it what you want, is a load of shit.

This is the first post of what may be a a little series on displacement mapping. This is the demo for this article.

First thing first, what is displacement mapping ?
Simply said, displacement mapping is the act of modifying a bitmap or 3D model (but not only) with the data from another bitmap, also called the ‘displacement map’.

In order to do that, you need to sample the colour channels from each pixel in the displacement map. The colour channels then give you the amount of displacement you need to apply to the corresponding pixel in your source image or to the vertices in the model.
I’m going to show you an example using bitmaps.

Step 1: retrieve colour data
For every pixel in the source image, get the corresponding pixel in the displacement map, and sample the colour channels. The images shows the colour channel values for the pixel at x:10 y:1.

Step 2: using the colour data
The next step is to decide how to use the values. For our example, we will use the red channel for the X axis, and the green channel for the Y axis.
We will also use this simple rule:

for values ranging from 0 to 126, the displacement will be negative along the axis, and for values ranging from 127 to 255, displacements will be positive along the axis.

Now that we have our value (R:193, G:109), we need to find a way to make them “usable”. If we were to use those values as they are, we wouldn’t have much control on the displacement, we would just say: “for pixel at position x:10 y:1 in the source image, replace pixel color by pixel at x:10 + 193 y:1 – 109″. It’s not very flexible.
What we need is a way to “scale” the values.

Step 3: scaling the displacement
The way to do this, is by mapping the values from the colour channels from 0 – 255 to -1 – 1, and then multiply the result by a scaling value.
Note: when I speak about “mapping” here, I’m talking about taking a value contained in on range and “moving it over” to another range.

int r = 193;
int g = 109;
float scale = 8; // this can be any value you want
 
float mr = -1 + 2 * ( r / 255 ); // map r from 0/255 to -1/1
float mg = -1 + 2 * ( g / 255 ); // map g from 0/255 to -1/1
// rm = 0.513
// mg = -0.14
 
// multiply both mapped values to get the final displacement amount.
int dx = mr * scale;
int dy = mg * scale;
// dx = 4
// dy = -1

You can now see that by using a scaling factor we have much more control over the amount of displacement we are going to apply to our source image.
The bigger the scale, the bigger the displacement, the smaller the scale, the smaller the displacement… you get the point!

Step 4: moving pixels around
Finally, we get to the last step. Time to apply the displacement.

Get the channel values from the current pixel in the displacement map:

Compute the position of the new pixel:

Get the colour of the pixel at the displaced position:

Apply the new color to the value to the current pixel on the source image:

Here is a demo I built to show you the displacement map in action. I’m not using the AS3 built-in DisplacementMapFilter, and that’s how I got a circular displacement map without using masks or anything.

One thing to note is that you don’t really ever display the displacement map image. It’s basicaly just an image that you will use to get color data from to modify another image. Most of the time displacement maps will be filled with perlin noise, or just anything you want.
And that’s about it. Of course you need to repeat those steps for each pixel in the source image. I didn’t get in to much detail, so just ask google or feel free to leave me a comment or send me an email.

I was reading this blog post in which the author writes:
“If the array is not initialized — and thus filled with random elements — we cannot know if a mark has been set!”.
OK. So, out of context this might not mean much at all, but if you read the article, Jasper Van der Jeugt says that the allocated memory returned to you by malloc will contain undefined data. If you read his blog post, you’ll see why that is a problem to him.

Now what Jasper says is not completely true.
When a program starts running, the memory space set aside for it by the system is cleared before it is handed over. The reason for this is simple. Say you have a program that handles important data, like an ssh connection or something, the passwords used for that connection would all be stored somewhere in memory, and so if that memory was handed over to another program without being cleared, that program running on the memory space the ssh was running, could access those passwords… you can see where this is going! It’s just plain insecure to not initialise the memory the system hands over to a program.

Therefor, when you call malloc in your code, the elements in the allocated blocs will be initialised to a certain value!
A simple piece of code will prove this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <stdio.h>
#include <stdlib.h>
 
int     main( void )
{
  int   *array;
  int   i;
  int   len;
 
  len = 300000;
  array = malloc( len * sizeof( *array ) );
  if ( array != NULL )
    {
      for ( i = 0; i < len; i++ )
        {
          if ( array[ i ] != 0 )
            {
              printf( "random value: %d.\n", i );
              break;
            }
        }
      free( array );
    }
  else
    printf( "error allocating memory.\n" );
  return ( EXIT_SUCCESS );
}

Run this as many times as you want, not once will it print anything on the standard output, because all the elements are initialised.
I tested this on FreeBsd, Mac OS X and Windows. The code for Windows is a little different.
You can now see that there is no random data in the allocated memory.

That being said, there are a few things I want to add.
The reason the memory returned by malloc can contain random elements, is because of the way malloc works.
When a program starts running, in short, the system gives it a chunk or memory it can use. Before it does that, the memory is cleared for security reasons.
So when you call malloc, the memory you get back from that call is always clean, except after your first call to free!
The reason for this is because of the way memory allocators work.
Basically when you call malloc, the allocator looks for a chunk of memory large enough for the size you requested and returns the base address of that chunk to you. It does that every time malloc is called.
On the other hand, when you call free on a pointer, it basically marks that chunk as “free” and knows it can be re-used, but in most cases it doesn’t change the data in that bloc, doesn’t reinitialise it or anything. So, as long as you don’t call free, the memory is clean, but once you call free, you have changed some of the memory your program owns and therefor, if you call malloc again, you may very well get a chunk with non empty elements returned to you.
It’s important to note that the way the allocator works can be different depending on the system or the algorithm the allocator uses.

So lately I’ve been working on a little multiplayer game in which I need to have N spheres rotating around a point. Each sphere needs to be at the same distance from the point as all other spheres, but they cannot overlap. When there are only a few spheres, that’s pretty easy, just use basic circular distribution:

1
2
3

angle = ( 2 * Math.PI / NUM_SPHERES ) * i;
spheres[ i ].X = CENTER_X + cos( angle * i ) * radius;
spheres[ i ].Z = CENTER_Z + sin( angle * i ) * radius;

But what if you have so many spheres that they start to overlap ? Well in most cases you are going to want to do something like this, but in my case, all spheres or objects need to be at a constant radius from the center point. So the trick in that case is fairly straightforward:
just lower the scale of the spheres proportionally to the amount of “overlap” between the objects.
This is actually pretty easy!

1. Check the number of spheres you are wanting to distribute. If that number if higher than a certain threshold, move on to step 2.
2. Plot out two points using the usual algorithm as described earlier, then get the distance between those to points.
3. If the distance between those two points is smaller than the diameter of the spheres, the are overlapping.
4. scale down the spheres by the “overlap amount” so they don’t overlap anymore.

That’s about it! Now I know in my example I talk about using spheres, but in my source code it actually use circles. To lazy to set up a DX program and all… You know how it is.

get the fla.

I was reading about convex hulls just last night. It’s pretty interesting! If found a nice article with detailed explanations about the various algorithms you can use to compute a convex hull. After reading it I started to implement something like the Graham’s Algorithm and then drifted off onto something “home made” that kind of jumped out at me.
I’m not sure it’s the best algorithm out there, but it gets the job done, and performance doesn’t seem too bad.
It’s very simple:

1. First you need to find the right-most point. This is a little like in Graham’s Algorithm, except we’re not looking for the lowest right-most point. We’ll call this first point A.
2. Next we need to find the point B with the lowest angle from A. Just like for Graham’s Algorithm, the angle is measured in a anti-clockwise direction relative to the positive horizontal direction. The line from A to B is the first edge in the hull.
3. This step is a little weird. You need to “rotate” the positive horizontal direction counter-clockwise by the angle between A and B. I’m not sure how to explain this with words, so I’ll try with an image. When calculating angles from A, the plane is horizontal, then when moving onto B, the plane is rotate counter-clockwise around B by roughly 130°.
   The reason for this, is that, in order to find the convex hull of a set of points, you want to draw a line from the current point to the point with the lowest angle.
   Sorry if this makes no sense, I pretty much randomly came up with it.
4. Then we repeat just repeat that process from point to point, until we reach the right-most point again. We then have found the convex hull to the set of points.
5. Profit, I guess.

However, there may be some cases where my algorithm brakes, I haven’t seen any yet, but they may be lurking in the dark…
Here is a working example, with fully commented source code, and here is a nicer convex hull demo.

I tried to port this over to alchemy, and it was slow as hell, if anyone has an idea why…

libcinder is pretty cool. I’ve been messing around with it for a few days now, it’s easy to use and “programmer friendly” (in my opinion).
Here is a little something I came up with, it’s a water effect I ported over to C++/cinder from one of my HLSL shaders, for science! Nothing very impressive, but it makes for a nice little effect when running smoothly.
Get the application, click and drag to add waves.

Just a quick tip, as mentioned in the cinder documentation, when iterating over the pixels in an image, use the built in Iter class!

surprise for a programmer.
That kind of made my day, along with cinder.