CAM world *intersecting* SQL Server world

I never thought that my current area of work (in general auditing and recovery of SQL Server databases) would somehow *intersect* (pun intended - see below) with my previous efforts in 2D CAM (Computer Aided Manufacturing.) But SQL Server 2008: Spatial indexes article by Paul Randal proved me wrong. In the article Paul explains how SQL Server 2008 spatial indexes work but what was most interesting to me was that the solution he described matches a solution I applied in a 2.5D CAM application some 10 or more years ago. Don't get me wrong, that doesn't make me rocket scientist since and anyone who had to work with intensive 2D geometry calculations sooner or later figures out that calculating intersection of curves is expensive (sometimes more, sometimes less: depends on the curves) so avoiding it in advance by using "bounding boxes" is, in general case, much better than blindly trying to calculate every intersection. I remember that one great advantage in my case was that we were able to use comparison of integers instead of floating points which further sped up the algorithm. Also, in our case there was just one "bounding box" per curve which was more coarse but didn't use that much memory and was easily calculated.

The 2.5D CAM application that I refer to above was called "Impakt!" It was used to generate G-code programs for 2.5D CNC (Computer Numerical Control) mills. Half of D means that mill could only position itself in height without really orienting the tool in three dimensions. Thus the geometrical problems were reduced to creating optimal 2D cutting paths and then additionally repositioning the tool between different 2D depth levels.

We started development of Impakt! in Delphi 2.0 sometime in 1996. Impakt! worked like this:
1. You would load 2D geometry from a file in Autodesk's DXF format.
2. You would define depth of each contour by choosing each area and then setting the depth (this could then be saved in our own file format that kept depth and other information)
3. You would define your tool set for the job (we kept a DB of tools and users were able to define their own tools)
4. Application would then generate tool paths by going through the following process:
4.1 Take the tool with the largest diameter in the tool set and start with contours on the highest level of the defined geometry.
4.2 Analyze the contours and identify "lakes" (outward contours) and "islands" (inner contours)
4.3 Grow "islands" outward and shrink lakes inward by the radius of the current tool.
4.4 Solve intersections of the grown/shrank contours thus defining tool path. This really solves one particular path through Voronoi diagram of the 2D contours available on the given depth level (I can't remember why we didn't just calculate Voronoi diagrams and then generate paths... I think that there were cases we couldn't or didn't know how to handle with Voronoi diagrams and I don't think we even had math for it, at first anyway)
4.5 Continue with the process in 4.2 and 4.3 until all contours would fold on themselves.
4.6 Take next smaller tool in tool set, take left over contours from the last successful iteration of 4.5 and then start again at 4.3.
4.7 Once there are no more available tools in the tool set go to the next depth as defined by geometry and start again at 4.2.
4.8 Once you have generated geometry for all depth levels you are finished.
5. You would then define cutting parameters for the job (this only influenced G-code generation)
6. G-code (or some other type of CNC code depending on loaded modules) would be generated from tool paths and cutting parameters. Unlike geometry generation where paths for all tools were calculated at once for each depth level, G-code was generated by following the paths of the largest tool on all depth levels, then changing the tool to the next smaller one and following all its paths on all depth levels and so on until the smallest tool in the tool set.
7. If I remember correctly we had a separate tool for transferring G-code (through RS-232!) to CNC machines.

Heh, more and more stuff is starting to crawl out from the back of my brain. I just remembered that once a contour was identified as an "island" or a "lake" we would reorient it if necessary so that it would go in counter-clock-wise direction if it was an "island" or in clock-wise direction if it was a "lake" (or vice-versa, it doesn't really matter so long as they had different orientations.) This allowed us to grow/shrink the contours with the same parameters ignoring the orientation as they would then "naturally" either grow or shrink depending on the orientation we gave it.

I hope that someday we will make open code source for "Impakt!" I would probably be rather embarrassed with the quality of the code but maybe somebody could find some use for it.