Search This Blog

Thursday, May 08, 2008

Spatial Sorting with kd-trees - Part 1

So, today I turned in my graphics programming term project... what's done of it, anyway. Spatial Sorting with kd-trees is the name of the paper/presentation; not quite as impressive sounding as my AI project, but then, this project as a whole is less impressive than my AI project (and my third term project even less) :P

Well, I was supposed to give the presentation today, on the last day of class. Unfortunately, due to gross lack of time, that didn't actually happen. If I recall correctly, 12 people were scheduled to go today, in 75 minutes of class time; that's about 6 minutes per person. Problem is, everybody made their presentations with at least 10 minutes in mind (not unreasonable), and it took everybody a couple minutes to get their Powerpoint presentation running on the overhead projector. By the end we'd gone from allowing the first 3 or 4 people to give their full presentations, to "7 minutes each", to "5 minutes each", to "3 minutes each", to "run your demo program and sit down"; and at least one person (me) never did get a chance to go (I'm not sure if there were others). So, I wrote the URL of my blog on the whiteboard and told people I'd post the presentation there.

The presentation itself is here. I'd recommend that anyone who hasn't seen it before also look at my previous description of kd-trees and kd-tries, as I'm not sure the slides alone, without the spoken part of the presentation, will give you a clear explanation.

In addition, the demo program is also here, compiled with XNA 1.0 Refresh and XNA 2.0. The space bar toggles pause (initially paused); the H key toggles display of the kd-tree divisions, simulated view frustum, and statistics about the search for objects in the view frustum (the statistics are, in order: number of objects in the view frustum, number of objects evaluated, the percentage of objects evaluated that are in the view frustum, the number of tree nodes navigated, and the ratio of objects in the frustum to combined nodes and objects visited); the arrow keys move the view frustum. I'll probably post a rant about XNA in the near future; just make sure you download the version of my demo for the version of XNA you have installed. I'll probably post the written portion of the project tomorrow, after I finish it.

I'm still hoping to post the source to TextBreaker and kdTrieDemo, although that's gonna be at least a week from now (at the earliest), as finals are next week.

1 comment:

Rick said...

I like to see your source code for this project if you are willing to share it.