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!
Sunday, 26 February 2012
A Blender add mesh extension
As of Blender 2.64 there is a native Convex Hull operator availablein Blender.
I won't elaborate too much on my adaption as it has nothing to do with web development. The script can be downloaded from my site and should be installed in Blenders addons directory and enabled in the user preferences. It is tested with Blender 2.61.
I still think it is a nice implementation and although it is pure Python, it performs quite well. Of course there is a native convex hull implementation in Blender game engine but that one isn't accessible from Python. Previous implemenations relied on external programs like qhull, which might be faster for large point sets but having a pure Python implementation that is tightly integrated with Blender feels cleaner. It certainly can handle points sets of up to a couple of thousand points.
I have adapted it to randomize the order of the vertices if the hull algorithm bombs. This will happen if adding a point involves calculating the volume of many degenerate tetrahedrons which is the case when trying to compute the hull of Blenders default uv-sphere. I tried to use Python's decimal module but the results did not improve so now if an error is encountered the vertices are reordered and a second attempt is made. Not clean, but simple.