Linkability Rules

The following linking rules are invalid. Linking is being revisited to be easier to understand. Dan 10/4/07

Linkability formulae

Consider two primitives, A and B. The maximum distance at which they can be linked is given by the following formula:

   (1)     max_link_distance = minimum( diameter_A + diameter_B + SMALLEST_MAX, LARGEST_MAX )

where:

   (3)     SMALLEST_MAX = 1.0 meters
   (4)     LARGEST_MAX = 32.0 meters
   (5)     diameter_X = diameter of the primitive X's bounding sphere (Figure A)
   (6)     minimum(C, D) = C if less than D, otherwise D

If the distance between the geometric centers of the two primitives is less than or equal to max_link_distance then they can be linked. Put in mathematical terms:

   (7)     A_can_link_to_B = ( length(center_A - center_B) <= max_link_distance )

The bounding sphere is the smallest sphere that totally encloses the primitive's local bounding box.

The local bounding box is centered at the primitive's geometric center and whose local-frame sides are equal to the primitive's scale.

The geometric center of the primitive is its local symmetric center prior to any cut, shear, twist, taper, or hollow operations.

Note that a primitive's bounding sphere is not necessarily the tightest sphere possible for its shape, unless it is a simple box or sphere. The bounding sphere depends only on the primitive's position and scale, so any severly cut and hollowed primitive will be significantly smaller than its bounding sphere, and not necessarily near the center. Also, a primitive with twist and/or shear may have corners that extend outside of its bounding sphere. Since the linkability rules depend only on the bounding sphere, which is ultimately dependent only on the primitive's position and scale, the linkability of two prims is independent of changes to form and rotation.

Linkability algorithm

The rules governing the linkability of multi-prim objects is very similar to the two-primitive case. The same formulae (1) and (7) apply, but the bounding spheres of multi-prim objects are the smallest spheres that completely contain all of the bounding spheres of the corresponding primitives. (See Figure C)

When linking three or more objects the algorithm iterates over the candidate objects until all linkable pieces have been found. First the root object is tested against each candidate object and the larger bounding sphere is recomputed after a successful link. Then any unlinked pieces are tested between themselves and merged into larger collections according to the formulae. The root object is then re-tested against the modified candidates and the process continues until all objects are linked, or no new links have been found.

Failure modes

If an unlinkable set is tested by the linkability algorithm then the final subset of linkable parts is determined by the order in which the candidates were submitted. The trivial proof for this is to consider a root primitive in the middle of an infinite grid of other primitives. It can't link to everything, but it were first tested against all primitives west of it the final linkable subset of that first operation might not link to any primitives to the east because of the LARGEST_MAX requirement (4). If the primitives to the east were tested first then the final result would be different.

If a linkable set is tested by the linkability algorithm then the final subset of linkable parts is NOT affected by the order in which the candidates were submitted. That is, if just the linkable subsets of the failure modes above are tested for all permutations of sequence they will always link. The proof of this is left as an exercise for the reader.

Examples

2 very small prims

diameter_A = ~0.01

diameter_B = ~0.01

SMALLEST_MAX = 1.0 meters

LARGEST_MAX = 32.0 meters

max_link_distance = 1.02m

one large prim and one small prim

diameter_A = 10m

diameter_B = ~0.01

SMALLEST_MAX = 1.0 meters

LARGEST_MAX = 32.0 meters

diameter_A + diameter_B + SMALLEST_MAX = 11.01m

11.01m is smaller than 32.0m

Thus the max_link_distance = 11.01m

2 very large prims

The diameter of a bounding sphere is the square root of x^2 + y^2 + z^2 thus, the diameter of a 10m x 10m x 10m prim is the square root of (100+100+100) = ~17.3m and the diameter of a 10m x 1m x 1m prim is square root (100+1+1) = ~10.1m (The type of prim doesn't matter for this calculation. We only care about the dimentions.) Let's take the case of two 10m x 10m x 10m prims.

diameter_A = 17.3m

diameter_B = 17.3m

SMALLEST_MAX = 1.0 meters

LARGEST_MAX = 32.0 meters

diameter_A + diameter_B + SMALLEST_MAX = ~35.6m

32.0m is smaller than 35.6m

Thus max_link_distance = 32.0m