## 5-axis distance precalculations

Wednesday, August 20th, 2008 at 5:11 pm

For reasons known to myself, I have decided that it would be convenient to be able to get a quick result for the distance of closest approach from a given point to a model…

I was going to outline how I have begun work on a giant 3D array of cells which each know the minimum answer for all the points in the cube, but have just thought of something better in the process of writing after I spent the last two days on the project.

I was going to cache all the results in an array: vector< vector< vector< double > > > subdividing the region in space and compute the closest difference between cubes and triangles, and began writing the code. Here’s the annoying code for doing it to a point:

``` void BoxClosest::MergeClosPoint(const P3& p) { double pdsq = Square(xrg.Distance(p.x)); if (pdsq > clossq) return; pdsq += Square(yrg.Distance(p.y)); if (pdsq > clossq) return; pdsq += Square(zrg.Distance(p.z)); if (pdsq > clossq) return; clossq = pdsq; } ```

where
``` struct P3 { double x, y, z } struct I1 { double lo, hi } struct BoxClosest { I1 xrg, yrg, zrg; double clossq } ```

The code for edges and triangles is very horrible. There should be some fancy algorithm to fill it in across the entire space, but I don’t know if it one exists. It’s an interesting puzzle.

Anyways, I’m hoping I can throw all that code out shortly if I proceed with something a bit more interesting that is able to cache the results and do it by points instead of cubes.

Ultimately I want a function that gives me the following:

``` bool IsDistanceGreater(const P3& p, double r, triangulated_model) { if (distance(p, triangulated_model) > r) return true; // false negatives are acceptable as long as it's fast return false; } ```

Now, if we know (have earlier calculated) that s = distance(q, triangulated_model), and it happens to be that s - distance(p, q) > r then we can get the answer quickly, using power of metric spaces.

We have ultimate case of lazy calculations here. The function remains valid for the same set of triangles, so it can be shared among several algorithms and they will constantly get faster as the computer runs on them for longer. It could be a strange situation. The first 5-axis pass will be slow. The second will be faster, as long as it doesn’t go too far away from the first. How this optimizes for multi-core coding is another problem.