Thursday, 3 March 2016
Tuesday, 16 December 2014
Friday, 12 December 2014
I was a bit late in noticing it but so far they have given away some pretty interesting titles so it might be a good idea to check it out for more to come...
Saturday, 13 April 2013
kd-trees are an efficient way to store data that is associated with a location in any number of dimensions up to twenty or so. Specifically, kd-trees allow for nearest neighbor searches in O(log n) time, something I desperately needed for my Blender tree generation add-on. In this article I highlight some of the design decisions that that shaped my pure Python implementation of a kd-tree module.
There exist quite a few implementations in C or C++ that are part of robust and well tested libraries but for my Blender add-on I needed a platform neutral (= pure python) implementation that I could ship with the add-on. There are a few Python implementations but because I could not determine how well tested they were or because they did not quite meet my requirements I decided to develop an implementation myself.
My requirements might not be everybody's requirements so besides supporting adding nodes and providing a nearest neighbor search what were the issues that were important to me?
- Comes with test-suite
- It might seem strange to make this the first requirement but because it's a part that is so essential to my add-on and because the code is quite tricky, I opted for test driven development. Adding unit tests to a python module is quite simple and although I can't claim that the tests cover all edge cases, they are nevertheless quite comprehensive. There is also a small performance test included.
- Works with any iterable as position
- A node in a kd-tree consists besides other things primarily of a position attribute. For use in Blender this typically would be a Vector instance but in other situations you might want to use other vector implementations. This kd-tree implementation assumes very little about its position attributes, just that it is subscriptable and that it supports a .dot() member function that returns the sum of the pairwise multiplication of its items (in other words, the dot product which is equal to the distance squared). Individual items should be floats (or anything that supports substraction, addition and comparisons). Probably any vector implementation will meet these requirements. The test-suite implements its own, based on Python's
- Allows easy deletion
- Deleting nodes from a kd-tree is tricky and costly because of the rebalancing that has to be performed. I therefor opted for a much simpler solution: Instead of deleting a node we set its
Noneand add an option to the
.nearest()member function to ignore nodes without data. Of course this won't make the tree any smaller but even when we delete a third of the nodes in random fashion (a typical use case for my tree add-on) the performance impact on nearest neighbor searches is minimal.
Thursday, 8 November 2012
I finished a Blender add-on tutorial the other day that might be an interesting read. And actually I liked the way my cover image turned out, so I reproduce it here :-)
Monday, 1 October 2012
during a short holiday break I did some reading on Web2py and my first impression is that that it looks really good. It seems to be much more complete and data centric than CherryPy. I think I will spend some time experimenting with it the coming months.
Saturday, 22 September 2012
My publisher Packt Publishing is about to release their 1000th title, which I think is pretty amazing. Them being altogether very pleasant people to work with I have no reservations pointing you to their site. If you sign up before September 30. there's even some surprise for you in store. You can read all about in their press release.
Being an author myself and having reviewed quite a number of the books published by them, I know it takes some genuine effort to produce a good book. Reaching your 1000th in about 8 years time is therefore a serious achievement. Conratulations!