Michael McCandless Thinking it through further, here are some more ways we could proceed.
(1) Since the problem is that the numerically approximated point is not actually on the surface, I can provide a "projection" method, which will generate a point on the surface given an (x,y,z) that is not quite on the surface. This has some cost because it will involve a sqrt operation per point so projected, but it is probably acceptable. The question is, does it help? What would we do differently in BKD?
(2) I can, maybe in conjunction with (1) above, make geo3d shapes no longer find any point that is not on the surface to be "within" any surface shape. This is of trivial cost (but requires changes to a number of classes). That will make the relationships not be confusing since points not on the surface will be excluded from the search, but it might mean that nothing gets returned at all from BKD by design. :-P
(3) I could add a method that would allow you to determine if a BKD cell intersected the surface or not. This, however, is maybe not a good solution, because cells can intersect on two sides and I can foresee issues when one side just doesn't make it etc. So maybe this won't help.
(4) When you stop to think about it, a quantized BKD point actually represents a little cell; it represents a range of possible values in x, y, and z. If we knew what that range was, maybe we could compute intersection with each BKD cell. This is a more robust way of looking at the "minimum BKD cell size" idea. I could provide a construct, e.g. GeoFuzzyPoint, which would express this. But we'd still need to figure out what operations you would need to be able to do with a fuzzy point in order to not have problems arise. Would we need new "isWithin" methods? Or just "getRelationship()" support between such fuzzy points and XYZSolids? Or what, exactly? Depending on the answer, the fuzzy point might be very similar in logic to the XYZSolid, so the cost of creating one would be similar (i.e. not trivially cheap).
Let's discuss possible solutions using these tools – if not this morning then maybe at lunch.