Setting up Kinect on OSX the easy way

Open Terminal

Install homebrew with the following command

/usr/bin/ruby -e "$(curl -fsSL https://raw.github.com/gist/323731)" 

Make sure homebrew is up to date with

sudo brew update

Change directory to your brew home folder with


cd /usr/local/Library/Formula
curl --insecure -O "https://raw.github.com/OpenKinect/libfreenect/master/platform/osx/homebrew/libfreenect.rb"
curl --insecure -O "https://raw.github.com/OpenKinect/libfreenect/master/platform/osx/homebrew/libusb-freenect.rb"

brew install libfreenect

glview

GlView showing kinect depth view

Advertisements

DStarLite Java Pathfinding

D* Lite is an incremental heuristic search algorithm that is used by agents (game ai, or robots) where the surrounding terrain is not completely known. The algorithm makes assumptions about the unknown terrain. D*Lite finds the shortest route from the start to the goal position, and as it encounters new obstacles these are taken into account and only part of the path is modified. Alternatively, pathfinding algorithms like A* typically have to replan the entire path when the environment changes.

D* Lite was developed by Sven Koenig in 2002 is based on the LPA* algorithm. I needed a suitable, computationally efficient algorithm for pathfinding in my current project and couldn’t find any java versions of the D*Lite algorithm that would have suited my purpose. My version is a standalone java version of D*Lite based on an existing C++ implementation.

This implementation is based on the original research paper http://idm-lab.org/bib/abstracts/Koen02e.html and also based on the c++ version located here: http://code.google.com/p/dstarlite/

For further reading check out the wikipedia article: Here
Sven Koenig’s personal page: Here
There is also an applet to help understand the algorithm: Here 

You can find my DStarLiteJava project on GitHub: Here

Hardware Instancing with XNA (minecraft style)

Lately I have been really enjoying a game called Minecraft. It’s an indie game made by one guy, I highly recommend it!

I have ported the heightmap generation code in one of my earlier posts to C# and using XNA I have been creating a minecraft style rendering for fun. My first approach was a brute force, render everything test. As you might have guessed, that didn’t turn out so well when rendering a decent sized terrain. The method I am using now is hardware instancing without any kind of occlusion culling at the moment. I am getting a decent frame rate (about 80fps for 20000 models) for the moment and I am going to continue on improving this method. The example that is linked at the bottom of this article shows how to perform hardware, and shader instancing.

Here’s a video of it in action:

Links:

Minecraft

XNA Mesh Instancing

OpenGL / openFrameworks Terrain Loader Update

Just a quick update on what I have been working on. One of the first posts on this blog was a terrain viewer. That project was thrown together very quickly for a weekly assessment, so it wasn’t coded very well and was exceptionally bloated for what it did. I have had some spare time, so I started a fresh and commenced building a minimal terrain loader from the ground up. So far, I have terrain loading from file (generated with the tool in previous posts), and displaying a texture mapped, shadowed terrain using glDrawElements. I have specifically not included loading from heightmap in this project because it is easier to load a point struct from a binary file, but heightmap loading could be added in easily and probably will be in the coming days / weeks.

The code is written using OpenGL and the openFrameworks toolkit. OpenFrameworks is used for loading the textures and setting up a window, etc. The size of the file is surprisingly small, just a few hundred lines. I thought I would upload this before I changed everything to a class and added some level of detail stuff to it. So here is a picture showing the pretty terrain.

Textured 512x512 shadowed terrain

I have heaps more work to do on this subject, but for now here is the source code.
Just drop this into your openFrameworks project (or use with openGL and load your own images).
The zip file also contains the terrain and the texture.

Download Link

Smoothing Terrain

The terrain generated in the last post was quite bumpy, what if I want smooth rolling hills or something that isn’t quite so bumpy. There are two options here – you can either play around with the diamond-square weights and method of generating the terrain or you can smooth the result. The method I have chosen is a mean (average) filter also known as a box filter. The filter works by moving a square (say 3×3) across the terrain values taking the average of the pixels surrounding it to give the center value an averaged result.

The box filter size is usually a power of 2 + 1. Some examples are 3×3, 5×5, 9×9, etc. The image below shows how the filter works. The 3×3 square is slid over the terrain averaging it’s neighbours. The center pixel is also taken into account.

3x3 Box Filter

Ok, time for some source code. The following code loops over the 2d array of pixels, the inner loop loops from the position minus the filter size to the position plus the filter size in each dimension, this allows us to have an arbitrary filter size without hand coding the weights and positions of each pixel in the filter. The count variable keeps track of how many points contribute to the average and we ignore edge cases meaning that if a point in the filter is outside the array, it gives no contribution to the average.

Box Filter Smoothing Code

So the results for running this on the terrain in the previous post are as follows:


Terrain with no smoothing

Smoothed Terrain with a box size of 9x9

And of course the smoothing can be iterated over many times. Here is the same filter size as above, but repeated 50 times.

Box size of 9x9, filtering done 50x

Here is a link to the code in the image for use with the previous terrain code : Download Link

Other useful links:

Band filtering example : http://www.lighthouse3d.com/opengl/terrain/index.php3?smoothing
Filter functions: http://www.wheatchex.com/projects/filters/

Terrain Generation – Diamond Square Algorithm

I have posted previously about a simple terrain heightmap display program I have made, but never talked about some of the methods of generating and manipulating heightmap based terrain systems.

The method I have implemented in my terrain generation program is known as the Diamond-Square algorithm and is a method of procedural terrain generation. The Diamond-Square algorithm is also known as random midpoint displacement fractal, cloud fractal or the plasma fractal.

We start with a 2D array of size (n^2 + 1) E.g. 257, 513 etc. Set the four corners to initial values, these can be random or preset it doesn’t really matter too much at this point.

We then perform the diamond step which consists of taking the four points arranged in a square shape, averaging the four values and adding a random value to the average, creating diamond shapes. The square step then averages the four corners of the diamonds created in the previous step. The center value of this step becomes the corners of the next step. The diamond and square step are repeated until all the points in the grid have values assigned to them.

The image above shows the alternating steps being carried out. The red dots are the pixels with new values, the black dots are pixels with existing values. The pseudocode from gameprogrammer.com is as follows:

 While the length of the side of the squares
 is greater than zero {
 Pass through the array and perform the diamond
 step for each square present.
 Pass through the array and perform the square
 step for each diamond present.
 Reduce the random number range.
 } (GameProgrammer.com)

Then we end up with a program that can generate terrain / cloud maps / general fractal noise. Below is an example image that I have generated at 512×512.

Heightmap 512x512

Heightmap 512x512

Below is a sample of what the terrain looks like with simple shading in OpenGL without textures. The shading effect is calculated by giving a colour based on the minimum and maximum values of the heightmap. E.g. VertexColour = (value – minY) / (maxY – minY);

Simple Terrain 512x512

I find that the easiest way to import data from my terrain generation program into the display program is to use the built-in IO functions to create an easy to read file format. The advantage of using this method is that you can store heights as floating point values instead of bytes (0-255) this gives many more possible heights, a greater dynamic range. The code to write these files is quite simple:

void SaveTerrFile(){
        //Write to file
        FILE *fp;
        fp = fopen("terrain.terr", "wb");

        //print out the data
        for(int x=0; x < DATA_SIZE-1; x++){
            for(int y=0; y < DATA_SIZE-1; y++){
                  //populate the point struct
                  point.x = x;
                  point.y = data[x][y];
                  point.z = y;
                  //smooth out the range a bit
                  point.y = (point.y-minY)/(maxY-minY);
                  point.y *= 255;
                  //write to file
                  fwrite(&point, sizeof(point), 1, fp);
           }
        }
        //close file pointer
        fclose(fp);
}

Other features that I think need to be added to this code is the ability to generate textures as well based on the height values, smoothing of the terrain and improvements to the viewer. For now though, here is some source code. This code saves the height values to a file. I haven’t included any image saving functionality in this version because I am not sure of the licensing issues that may arise. Will find out soon, more updates to this coming in the next couple of days.

Link: Download Source Code

Other Useful Links / Articles:

http://www.gameprogrammer.com/fractal.html#diamond
http://stackoverflow.com/questions/2755750/diamond-square-algorithm
http://en.wikipedia.org/wiki/Diamond-square_algorithm

Particle System

Today I was kind of bored so I decided to write a simple particle system in XNA. The helpful tutorials over at http://rbwhitaker.wikidot.com/ helped point me in the right direction. This particle system is very primitive at the moment, a particle emitter follows the mouse around the window. When I get the time (or the motivation) I am going to add a few more features such as different particles (smoke, water, fire, etc.), some different effects like attraction and repulsion and maybe the option to place multiple emitters in the scene.

Although this particle system is in 2D, the concepts are easily translated into 3D. Most games engines include a standard particle system like Ogre3D does, but I wanted to learn how to create one from scratch anyway. The image in this post shows the particles following the mouse around the screen. I can post source code on request, but I would rather upload after I add some more features.

XNA Particle System

Here is a download link for the application for you to play around with (windows only) – Link