Wednesday, June 22, 2011

kd-trees

So I was trying to find a kd-tree library out there for C++ and I came across libkdtree++. At first I was a little intimidated by it because it's examples were not very straight forward. But I'm making progress is figuring it out. (Not that it took me all that long, I'm just lazy).

So now you can be lazy too by not having to search around further for the "Hello World" usage of libkdtree++. After installing libkdtree++ on your system, here are the basics. I'm going to create a typedef a 3 dimensional kd-tree, because I need it to hold Vector3 objects. The typedef just makes it coding easier.

#include <kdtree++/kdtree.hpp>
#define DIMS 3 // dimensions of the kdtree.


// This typedef is just for ease
typedef KDTree::KDTree< DIMS, Vector3, std::pointer_to_binary_function<vector3,size_t,float> > tree_type;

DIMS means the number of dimensions in the tree, which is also the number of dimensions each node has. Vector3 is the data type the tree is holding. This is my own custom datatype (but it's just a 3d vector). The last parameter defines the function signature that can be used when sorting and searching. Tip: google "pointer_to_binary_function" if you don't know what it is.

Then you need a function that will return a node's kth dimension. In this example, I need a function to return a Vector3's X, Y, or Z component. 

// Get nodes kth dimension value
inline float getDimension(Vector3 v, size_t k)
{
    // k is either 0,1,2
    if (k == 0) // x axis
        return v.x;
    else if (k == 1) // y axis
        return v.y;
    else // z axis
        return v.z;
}

Now I'm finally going to declare my tree.

int main()
{
    tree_type t(std::ptr_fun(getDimension));

    t.insert(Vector3(0,3,0));
    t.insert(Vector3(1,0,1));
    t.insert(Vector3(2,0,3));
    t.insert(Vector3(3,1,1));
    t.insert(Vector3(1,2,4));

    Vector3 target(1.5,2,0);


    // Find the node nearest to the target
    std::pair<tree_type::const_iterator, float> = t.find_nearest(target);
    cout << "nearest is: " << *found.first << endl;
    cout << "   dist is: " << found.second << endl;

}

This code will find the nearest node to the target. The look-ups here are amazingly fast. I create a tree with 10 million random points. While the tree creation took more than two minutes (125s) , the lookup was near instantaneous, less than clock_t's resolution anyway (which I understand to be around 15 ms.)

That's it for now. I'm still playing with it.

Wednesday, May 18, 2011

Orthographic Ray tracer

My first ray tracer (recreation of Figure 3.1 from Realistic Ray Tracing by Peter Shirley). This image has artifacts though. I'm not doing multisampling yet, so I think it's a ppm-to-jpeg conversion issue.


Maybe I need better ppmtojpeg options.

Sunday, November 29, 2009

New url for our blog

Hey everyone, if you're seeing this post, then you should update your bookmarks or RSS reader. We moved our blog url to http://maryandrusty.blogspot.com

That is all.

Monday, February 9, 2009

Automating Mac disk image creation - .DS_Store

I have been trying to find a way to automate the .dmg creation process for MonoDevelop for a while now. Thus far, the best thing Google has found for me are tips on creating a template disk image. It goes pretty much like this. Create a read/write disk image and set up the Finder settings the way you want (i.e. background image, a sym link to the Applications directory, the Finder window at a certain height/width etc. ). Once the template is created check it in to svn, and have your scripts mount the image and modify it with the latest binaries for your project.

The big problem I have with this is that creating a template .dmg is tedious, and checking such a large file into svn is not a good idea either. Another problem is creating a template that is the right size. If you project gets too large, you'll have to create a new larger template image. Having extra room on your .dmg to expand is good, but having a disk image that uses a lot of extra space isn't.

I still haven't found the best solution, but Andrew and I found something that's a bit better. We figured out that there's a very small binary file named .DS_Store in a disk image that holds the meta data for the various customizations for that image. Settings such as height and width, icon locations, finder settings, and back ground image are all stored in that file. (I think so anyways. Please correct me if I'm wrong) We check in that small file into svn and then automating the dmg creation is fairly simple:

  #!/bin/sh
mkdir -p tmp/.background
cp -pR MonoDevelop.app tmp
cp DS_Store tmp/.DS_Store
cp INSTALL COPYING tmp
cp dmg-bg.png tmp/.background
ln -s /Applications tmp
hdiutil create MonoDevelop.dmg -volname "MonoDevelop" \
-fs HFS+ -srcfolder tmp


The good parts of this are that hdiutil will look at the srcfolder and set the disk size based on the size of the directory, i.e. no wasted disk space. Second, the file .DS_Store is super small and easy to check in to svn. But the big downside: .DS_Store is still a binary file and you still have to go through the hassle of creating a template disk image in order to get it.

If anyone has a better way to do this stuff, I'd be interested to hear about it.