This is an experimental concept. We can compute the distance from a point source in open space using an equation, which is far faster than using the dijkstra based method (1.2 MVx/sec (105.9 sec) vs 192 MVx/sec (0.65 sec) on a field of ones). However, the method is extremely brittle as an kind of kink in the shape invalidates the results of the equation.

        // easiest to understand form of the eqn. We use an algebreically rearranged
        // version that is about 25% faster
        float dx = std::abs(static_cast<float>(x - src_x));
        float dy = std::abs(static_cast<float>(y - src_y));
        float dz = std::abs(static_cast<float>(z - src_z));

        float corners = std::min(std::min(dx, dy), dz);
        float edge_xy = std::min(dx, dy) - corners;
        float edge_yz = std::min(dy, dz) - corners;
        float edge_xz = std::min(dx, dz) - corners;
        float edges = edge_xy + edge_yz + edge_xz;

        float faces = (dx + dy + dz) - 2 * edges - 3 * corners;

        dist[loc] = corners * sqrt(3) + edges * sqrt(2) + faces;

I'm trying to find a way to hybridize the free space equation and dijkstra's method.

Problems:

1. How to define the region around the point source where the equation is valid without performing an expensive calculation?
2. Can we use the free space burst only at the start or more than once? Some duplicate work can result if loops are present in the shape.
3. Does assuming a loop free structure make a difference? What about a hole free structure?

• Can the equation be made to work with anisotropy? The assumption about the fastest path isn't right if the dimensions don't match.

Ideas:

1. Can we do a first pass burst over the entire shape and then fix problem areas? How would we identify problem areas?
2. The valid area is the same as the sight-lines from the point source.
3. How to describe a region as "free space"? Divergence? Compressibility of flow? How can we establish an area as free space without performing a dijkstra-like flood fill? Would a 6-connected dijkstra flood fill be sufficient and significantly faster?
4. Could we travel along the surface of the shape to define some internal area?
5. In Kimimaro, we have the distance to boundary field already computed, is that useful?

If we can make this faster, it accounts for about 20% of Kimimaro's run time.