November 10, 2013
After a 4 week stint in Seattle at Robert McNeel & Associates headquarters I’m finally back home. A lot of things were decided regarding the future of Grasshopper 1.0 and 2.0, however since I haven’t even started writing 2.0 I don’t want to list a bunch of features that may or may not make it in lest it be misunderstood for a list of promises. Instead allow me to list all the areas in Grasshopper where everyone is agreed problems exist that we need to attempt to solve for GH2. As a result of this reformulation I cannot mention any totally new features we are planning. I guess they will remain a secret for the time being…
- Documentation is woefully inadequate
- VB/C#/Python scripting tools are woefully inadequate
- Canvas UI doesn’t scale well to large files
- Grasshopper is probably only using a small part of your computer’s processing prowess
- It is too difficult to find out which plugins exist for Grasshopper
- It is too difficult to find out which plugins you need to open a GH file
- It is too difficult to use Grasshopper
- Grasshopper SDK is cumbersome to use in many places
- Grasshopper doesn’t scale well to high resolution displays
- Grasshopper UI doesn’t scale well to many custom tabs
- It is difficult to work with multiple users on the same project
- It is difficult to debug a GH file, especially if it was made by someone else
- It takes too long to start Grasshopper, especially if many plugins are installed
- It is often too difficult to edit data quickly
- It is difficult to associate custom information with Grasshopper data items
- It is difficult to maintain version control over large Grasshopper projects (i.e. who made what changes when, which plugins were used and do all the features today work in the same way as they did when this file was last edited?)
- Grasshopper has badly suffered from feature-creep and bloat and is in need of a thorough spring cleaning
- It has also been decided that Grasshopper will become part of the standard Rhino toolset, meaning that Grasshopper 1.0 will be available in Rhino 6.0
Once the Remote Control Panel is available again, development for GH1 will stop (apart from bug fixes) and I can start typing on GH2. I’m very much looking forward to this as there is some really exciting stuff that might not even take that long to code up. Running on Rhino6 means that I can switch to .NET 4.0 or even 4.5 and those have some really cool async and threading features. But most of all I want to be able to rewrite a lot of core classes because GH1 is a total mess under the hood.
All in all it’s pretty good news me thinks. I was a bit surprised that we ended up deciding to merge GH and Rhino and that I shall be developing GH2 beta as part of Rhino6/7 beta. It does mean I no longer have to worry about installers but it also means I’m tied to the Rhino release cycle. Luckily our new updating system means we actually tend to push out beta’s every week now so it will hopefully not be a big problem.
If you have specific wishes (especially regarding the SDK if you’re a GHA developer!) feel free to post them on our forums or send them to me directly.
ps. Simon Singh was on my SeaTac → Heathrow flight, 10 rows in front. It was an overnight flight so I didn’t want to disturb him but I managed to make a fool out of myself in a record 3 seconds by thanking him for Big Bang while deboarding. In case you haven’t read it yet, do so now. Seriously. Now. Shared first place with The Selfish Gene and Chaos in the category popular science.
October 10, 2013
Nearly four-and-a-half months after moving to Austria it seems we’re finally all settled. Well, legally settled, we’re still lacking a lot of lamps and storage space in the house itself. Car import tax, car validation, car registration, ÖAMTC membership, finding an insurance advisor, getting car insurance and license plates, electric/water registration, house insurance, recycle-centre card, private bank account, finding an accountant/tax-advisor, finding a vet, getting a work-license, getting a VAT/tax id number, opening a business bank account, health-care insurance, social insurance, retirement payments, Austrian ID card and pet-cat registration in the national database. All done as of noon today.
It seems a lot more complex here than in Slovakia…
Still, all the legal hassle aside, this is an absolutely beautiful place to live. We can cycle to and swim in Plansee in about 20 minutes. Walk to Heiterwanger See in 30. There is a fantastic bike route along the Lech river. Füssen and Alpsee in Germany are only about an hour cycling from here. Garmisch-Partenkirchen and back is a lovely bike-ride that’ll take less than half a day. There’s four castle ruins within walking distance of the house in various stages of (dis)repair and it’s wonderfully, exquisitely, magnificently, sensationally quiet here.
For about two weeks we had a herd of sheep and goats in the fields next to the house. They got into the garden a few times so we’ll need to build a better fence next year. Still, they are rather cute.
There have been some buck fights around the house this month, it appears to be deer mating season. Usually they do their stuff at night but we’ve seen a few deer and bucks up close (20 meters from the house and I once nearly biked into one on the road to Rieden).
Edit: Suddenly snow!
Edit 2: Yup…
September 30, 2013
Space ship, somewhere well on its way to Jupiter and they’re having a real-time discussion with Mission Control on Earth. WTF Hollywood? Who the hell makes a Sci-Fi film and then doesn’t hire someone with at least a high-school level understanding of physics to check the script for nonsense? There’s a 3 second delay just talking to someone on the Moon for Pete’s sake.
According to Rotten Tomatoes this film is:
Claustrophobic and stylish, Europa Report is a slow-burning thriller that puts the science back into science fiction.
Except for that thing about the speed of light I suppose… Why is it so difficult to make a decent Science Fiction movie when there are so many good Science Fiction books out there?
September 28, 2013
While trying to explain curve parameters to my girlfriend (she was proofreading my previous blog post) we hit upon an apt analogy. Imagine you’re taking a car-trip from home to the nearest
Hooters book-shop. It’s a good half-hour drive which takes you over two local roads and a motorway.
If the shape of the road you travel along equals the shape of a curve, then the curve parameters are analogous to the travel times. If you take this trip once every week, then you travel along the same roads every time. Thus the shape of the curve never changes. However some weeks you run into roadworks or thick fog or a traffic jam and then your travel times start to differ. Some parts of the trip may go faster than usual, others may go slower.
The point is that once you have the entire trip data (i.e. the entire curve data, not just the shape) you can then work out your location at 12:15. And you can work out in what direction you were travelling at 12:15. And you can work out your acceleration at 12:15. And you can work out the centrifugal force you were experiencing due to turning at 12:15. All of these properties can be computed as long as you have the curve (the route) and the correct curve parameter (the time).
It’s now also easy to see that parameters can have different densities in different portions of a curve, and how parameter density can be thought of as the ‘speed’ of a curve.
It even allows us to get a feeling for curve derivatives and why parameterization matters. Derivatives are used to compute the tangency and curvature and torsion of curves. A parallel can be drawn between those properties and the forces that push you into your car-seat due to acceleration. Or the forces that pull you out of your seat sideways because you’re turning too sharply. These forces don’t just depend on the shape of the road, they also depend on your travelling speed.
September 27, 2013
One of the more common misconceptions people have regarding computational geometry has to do with curve parameters. Since the mathematics of Nurbs curves are rather involved —much of it is certainly beyond high-school level— it is quite difficult to explain how control-point coordinates, control-point weights, curve degrees and knot-vectors all conspire to complicate the parameterization of a nurbs curve. My own grip on Nurbs maths is slippery at best so I think it’s better for everyone involved if I start this discussion using much simpler types of curves.
But before we can start talking about the problem, we should first lay down some ground rules for what sort of shapes qualify as ‘curves’:
- A curve is a finite, one-dimensional object, existing in some space with an arbitrary number of dimensions. In this blog post I’ll only concern myself with two-dimensional and three-dimensional spaces as we are all familiar with them.
- Every curve must have exactly two endpoints. No more, no less.
- If the endpoints coincide, the curve is considered to be closed.
- There may be no gaps on the interior of a curve, as that would result in more than two endpoints.
- There may be no branching points on the curve, except where an endpoint is coincident with some interior point of the curve.
Basically, think of all possible curves as liquorice laces, you can stretch, bend, twist and kink them, but ultimately it’s nothing more than a bunch of deformations applied to a straight piece of chewy goop. Note that the definition above differs from the common mathematical definition of curves. Mathematicians tend to be far more inclusive and rigorous.
September 17, 2013
I’ve been thinking about Grasshopper 2.0 for a while now and there are a lot of facets to the project where I’d like to see improvement. One of the things I’m looking into is incorporating 3rd party code libraries that would provide advanced statistical and algorithmic functionality. One of the libraries I’ve been browsing is the Microsoft Solver Foundation whose main purpose is to solve optimization problems.
Looking for examples on how to use MSF I came across this blog post which poses a hypothetical (but not unrealistic) problem which can be cracked using an algorithmic solver. The post itself has some inconsistencies in the numbers it uses to describe the problem, so I’ll outline it briefly here as well:
- You own a trading company and you’re looking to import some cheap-ass furniture from China and sell it to gullible Europeans for cut-throat prices. So the goal here is profit maximization.
- We hire individual containers from a shipping company, and these containers have limits on how much weight you can put in. We’ll use a 500 kilogram limit in this tutorial. We are not concerned with volume limitations.
- There are three types of furniture we can import; chairs, tables and bookcases (the original article uses cupboards instead of bookcases, but I wanted three items that start with different letters). Each has its own specific purchasing cost, profit margin and weight.
- There is one additional constraint concerning purchasing cost; your company can only afford to spend 5000 Euros per container.
That’s it, simple enough. A profit function with three variables (amount of chairs, tables and bookcases respectively) and two hard constraints limiting the weight and purchasing costs.
Because of the weight and purchasing constraints this problem becomes non-trivial and an algorithmic approach would be good to have, if only to check your intuitions in case you’re doing the purchasing by hand.
This is a three-variable problem which means the phase space of all possible states is three-dimensional and the fitness landcape is a four-dimensional surface (if you don’t know what a fitness function/landscape is, please see this blog post or buy the Architectural Design publication with my article). I cannot draw a four-dimensional surface on a two-dimensional screen so instead I decided to just make sh*t up and hope it gets the point across regardless of being utter humbug:
Here you see a two-dimensional phase-space (let’s ignore bookcases for the time being and assume we only have to pick chairs and tables) with the resulting three-dimensional fitness landscape. From left to right we go from zero chairs to some arbitrary upper limit. From front to back we go from zero tables to some arbitrary upper limit. Every two-dimensional point is some combination (i.e. state) of chairs and tables. For every combination we can compute the profit that combination would generate, and this has been represented by the height of the landscape. The higher the surface, the more money we’re going to make. Find the highest point on the landscape and you know how many chairs and tables hit the sweet spot.
So far so good. But what about our constraints? Some combinations of chairs and tables are impossible either because they weigh too much or because they cost too much. So our landscape shouldn’t in fact exist at all when this is the case. This is known as a hard constraint and unfortunately in Galapagos it is impossible to add a hard constraint (at least for now).
Luckily we can mimic this effect with penalty clauses. We’re looking to maximize our profit, so what we’ll do is subtract a large amount of money if any of these constraints are overstepped. As long as we subtract enough, the solver will automatically avoid those areas. Enough theorizing, lets hook up some wires!
August 9, 2013
This is going to be a difficult post to write on several levels. I’m about to lay heavy blame on a number of people and organisations who are part of my loyal customer base. I am also going to incriminate the industry I work for, which includes my direct employer and —of course— myself.
At the same time I have to marshal my arguments very carefully so as not to belittle a specific individual whose work I am about to dissect and critique in a harsh tone. I firmly believe —although he probably doesn’t agree with me— he is the victim of the twin evils of underinformed educators and overeager, heedless software companies. I wish neither to patronise nor scapegoat him and I know that cushioning language is not my strong suit. Please remember this while reading the text below. This is not about ridicule, but rather about a pervasive and alarming world-wide trend in academic architecture.
I’d like to thank ███████████ for sending me his work and having the courage to allow me to publicly critique it, knowing I’d focus only on the bad and not the good.
Also my sincere thanks goes out to K. who —unlike me— did receive proper academic training during her time at University (Turku University, Department of English) and was able to comment comprehensively on the scholarly and academic aspects of this critique.
March 11, 2013
Fine, I lied. Post  wasn’t the last one after all. I’d like to propose one more optimization to the Quadtree/Octree algorithm as explained in the previous post.
As you may recall, spatial trees are clever because they [A] allow us to quickly —almost trivially— reject large portions of a dataset. The recursive nature of the spatial tree means that if we can reject a specific node, we can also reject all of its child-nodes. Furthermore, because the tree has variable density it is very well suited to handle unbalanced point collections.
We can reject a node in the spatial tree when the shortest distance from the search locus to the boundary of that node is already larger than the best answer we’ve found so far. From this it follows that the smaller the node region, the more quickly we can reject a node. Typically the regions of all child-nodes equal the region of the parent-node. However it’s only important to have a tree without gaps between nodes if we’re still in the process of inserting points into the tree. When we’re done adding points we can perform two fairly easy optimizations that will improve the search speed (though not enough to change the runtime-complexity).
Optimization number one involves shrinking every node region to contain exactly the points inside of it. Or —if the node contains child-nodes rather than points— shrinking the node region to contain exactly the regions of the child-nodes. By shrinking the node regions to the bare minimum we will increase the shortest distance from the search locus to the node region, which will —sometimes— result in earlier rejection.
Optimization number two involves simplifying the tree structure by removing nodes that contain exactly one child-node. We can ‘detach’ the single-child and plug it into the same slot as its parent used to occupy. By removing these pointless nodes we reduce the time spend traversing the tree.
The image above shows the same Quadtree we build in the previous post, but now the nodes are colour-coded to reflect what sort of optimization we can apply to them. Orange nodes are empty and can be removed entirely. Green nodes contain points whose collective bounding-box is smaller than the node region. By removing empty nodes and shrinking the remainder, we end up with a vastly reduced total structure.
Once you apply these optimizations to a tree structure it is no longer possible to insert more points, as they might fall in the gaps that now exist between adjacent nodes. Unless you’re willing to make your point insertion smart enough to grow node regions on demand of course.
Seriously, I’ll stop harping on about spatial trees now.
March 9, 2013
Welcome to the —for now— last post in this series on algorithmic optimization. We talked a bit about generic optimization, then we introduced a specific problem and explored different ways of speeding up finding the solution to that specific problem. We talked about brute-force searching and why it’s not an option when we’re dealing with large point collections. We discussed one dimensional sorting and spatial bucketing and the merits and drawbacks of each algorithm. It is now time to discuss the ultimate of closest-point-searching algorithms, the weapon of choice for the informed and discriminating programmer; spatial trees.
But let us start by briefly rehashing the logic of the square-grid-search algorithm and why it’s not a particularly good one. By creating a grid of adjacent cells and assigning each point p in a collection C to whatever cell contains it, we gain the ability to explore C in a localized fashion. Although we may not know exactly which two points are direct neighbours, we do know which two cells are direct neighbours and therefore all the points in these cells can be treated as being in the same neighbourhood. This works splendidly while single cells do not contain too many points and while there aren’t too many completely empty cells. For balanced point collections we just need to pick a clever grid size, but for unbalanced collections we are rightly and truly screwed:
If we pick a large grid cell size then too many points end up in the same bucket and we’ve converted a smart search algorithm into a brute-force algorithm. If we pick a small grid cell size then there will be loads of empty cells and iterating over them will retard the search process.
If at this point you’re thinking “If brute-force search is a prohibiting factor in the case of grid cells with many points, why not put a smaller grid inside those cells?” you can feel real good about yourself. In fact, once we establish that it’s allowed to put a smaller grid inside the cell of a bigger grid, we can simplify the whole grid notion and only support grids that are composed of 2×2 cells. To create a nested grid structure like this, we only need a very short algorithm:
- Draw a rectangle around all points in C.
- If the number of points in this rectangle exceeds N, then subdivide the rectangle into four smaller rectangles.
- Assign each of the points in the parent rectangle to the appropriate child rectangle, and then repeat steps 2 & 3 for each child rectangle.
The above algorithm is recursive and the grid structure it generates is no longer one where all cells have the same size. If points are more densely packed in one region of space, the grid-structure will subdivide more often and it will result in smaller cells. If points are completely absent from another region of space the grid-structure will not subdivide at all and we won’t be plagued by a plethora of empty grid cells. If we apply this logic to an unbalanced point collection, we should get something like this:
Level 0 represents the top-most level of the grid. The number of points inside the outer boundary is too high and the region is split into four quadrants. The lower right quadrant still has too many points so it too is split into four quadrants. Then the process repeats one more time giving us a third level of subdivision. Now we have a grid containing ten cells of varying size containing the entire point collection. In fact two of the cells contain no points and can be removed from the grid structure in order to reduce memory overhead. The entire structure also contains three cells which host nested grids.
A spatial data structure like this is typically referred to as a tree in programming because the recursive and fractal nature of the algorithm resembles the branching patterns of biological trees. There are many different flavours of spatial trees, some more suited for specific problems, some easier to implement, some optimized for point insertion or deletion. What I’ve drawn above is usually called a Quadtree (or Q-tree) because it always subdivides into quadrants. If we extend this notion to 3D space and we have to subdivide a single box volume into eight sub-volumes and we call the resulting structure an Octree instead.
So how does searching in a Quadtree work? Remember that in order to perform a fast closest point search, we need to reject as many points as possible, limiting the search to only those points which are serious candidates. In some ways searching a Quadtree is easier than searching a fixed grid, one of the reasons being that we don’t actually have any empty cells. The search algorithm might work roughly like this:
- Build a tree T from the point collection C.
- Find the cell L in T which is closest to the search point h.
- Find the point p in L which is closest to h using —once again— brute-force search.
- Start recursing to sibling and parent cells to see if they contain points closer still.
- Every cell that has a minimum distance to h which is already larger than the smallest distance we found so far can instantly be skipped, as can all child-cells within it.
Step 5 is where the real magic happens. Spatial trees make it very easy to weed out enormous portions of C that are not near h. Adding points to an existing tree structure is also very easy, even if they are outside the outer bounds of the level 0 cell. All we need to do in those cases is insert another level underneath level 0 (which then by definition becomes level 1) in order to grow the reach of the tree. Every time we add such a bottom level we double the reach, so even inserting points which are really far away will not take intolerably long (unlike fixed grids which grow in a linear rather than exponential fashion).
As I mentioned in post #1, optimization is often a difficult process and code which is optimized often gains so much complexity as to become unreadable —at least without significant effort— by third parties. Only start optimizing code once you’ve determined beyond a shadow of a doubt where the bottleneck in your program is.
March 9, 2013
One of the main drawbacks of the adapted-sorted-brute-force search algorithm we developed in the previous post is that it only sorts the data along a single coordinate axis. For two dimensional data that means we’re ignoring half the information. For three dimensional data we’re ignoring twice as much information as we’re using to speed up the search. The more dimensions, the less efficient that searcher becomes.
The key to optimizing a Closest Point Search is to reject as many points as possible because measuring the distance between points takes time. It might not take a lot of time to compute the distance between two points, but if you want to find the nearest point in a collection of 10 million points for 1 million other points, you end up computing 107 * 106 = 1013 distances if you take the brute-force approach. Even if a single distance test only takes 5 nanoseconds it will still take 50,000 seconds, which is almost 14 hours. The adapted-sorted-brute-force (which wasn’t all that brute-force by the time we were done with it) managed to reject points because their distance measured along the sorting direction exceeded the best result we’ve found so far.
What we’d like to accomplish today is roughly the same, except we want to be able to reject points in all directions, not just one. Instead of sorting all the points, what we’ll do instead is put them in spatial buckets, and these buckets in turn will be defined in such a fashion as to allow very easy navigation to neighbouring buckets. In other words: a grid.
In the image above you can see the entire point collection represented by the black dots. Point h is represented by the red cross and we’re looking for the black dot closest to h. This search algorithm also requires a pre-process step, but instead of sorting all the points we’ll instead assign them to whatever grid square contains them. So instead of a single large collection of points (C), we end up with a grid structure where each grid cell contains a subset of C. This is a very cheap process as it only takes a single subtraction, multiplication and rounding operation per dimension per point*. It’s also very easy to multithread this pre-process as it belongs to a class of problems known as embarrassingly parallel. The algorithm —which we shall henceforth refer to as the square-grid-search algorithm— would work as follows:
- Create a grid of square cells that encompasses all of C.
- Assign all points in C to their respective grid cells.
- Find which cell r contains h (or which is closest to h if h is not within the grid bounds).
- Find the nearest point p in r to h using brute-force search.
- If r is empty, extend to search to all eight neighbouring cells and so on until at least one point is encountered.
- Find the collection of grid cells R which intersect with the search boundary (represented by the green circle).
- Iterate over all points in R using brute-force to see if any of them are closer than the early result.
The algorithm is fairly straightforward and easy to implement, but —like adapted-sorted-brute-force— is has serious drawbacks. It will perform very well on balanced point collections, but the performance heavily depends on the size of the grid cells. Too small cells and many of them will be empty, causing us to spend a lot of time iterating over pointless** areas. Too big and they’ll contain a lot of points which will slow down the algorithm as the intra-cell search is brute-force.
If the collection is unbalanced then we’ll end up with many empty cells and some cells which contain many points. As long as the intra-cell search remains brute-force, square-grid-search will not be suitable for such cases.
There is a new drawback as well. It’s quite simple and very fast to insert points into a sorted collection without breaking the sort order. It is also very easy to insert points into a spatial bucketing grid, provided the points are within the grid boundaries. If you wish to add points outside of the existing grid boundary, the grid will have to be grown, which can be a computationally expensive operation***.
Up next we’ll examine ways to make spatial bucketing more effective for unbalanced —indeed, wildly unbalanced— point collections.
* Assuming the Grid only has rectangular cells. Square cells make the algorithm much easier to implement though, not to mention hexagonal or free-form cells.
** Bow down before the Master of Puns!
*** It is possible to use a data structure known as a sparse array to store the grid cells rather than a standard multi-dimensional array. This effectively solves the insertion problem, but it also makes navigation between neighbouring cells slightly slower.