Link algorithm exposed
When linking two or more primitives in
SL [libary:9c3c460b34]Abkürzung für [Second Life][/libary:9c3c460b34] the operation may fail if the pieces are too far apart. I've had a few requests for details about the algorithm used to determine whether a collection of primitives can be linked or not, and have decided to post the details here for those who want them.
So here is the algorithm in pseudo-code. First, let me declare some definitions and constants...
Code:
AABB = axis aligned bounding box
// The AABB of a primitive is the box that contains the sphere
// (centered on the primitive's center of mass (as computed by
// Havok, not the "primitive's geometric center)) that contains
// the primitive for all rotations.
float MAX_LINK_PAIR_DISTANCE = 1; // cap max dist btw tiny prims
float MAX_LINK_DISTANCE = 32; // cap max dist btw large prims
... and then there are two key functions...
Code:
// --------------------------------------------------------------
// can_link(collection_of_primitives)
// --------------------------------------------------------------
AABB box_list[] = array of AABB's of the collection_of_primitives
// first do quick check of the absolute size of final linked collection
AABB total_box = tight box that contains the centers of all
the boxes in box_list[];
float L = length of diagonal of total_box;
if (L > MAX_LINK_DISTANCE) return FALSE;
// The link did not fail due to its sheer size, however if the
// individual pieces are too small then the link may still fail.
total_box = box_list[0];
int linked_box_count = 1;
while (linked_box_count < total_box_count
&& the_last_pass_did_not_fail)
{
the_last_pass_did_not_fail = FALSE;
for (i=0; i<total_box_count; i++)
{
if (box_list[i] not yet linked)
{
if we_can_link(box_list[i] with total_box)
{
total_box = smallest_union_box(total_box and box_list[i]);
the_last_pass_did_not_fail = TRUE;
total_box_count++;
}
}
}
}
return (linked_box_count == total_box_count)
// --------------------------------------------------------------
// can_link(box_a with box_b)
// --------------------------------------------------------------
// the link can fail if the centers of the boxes are too far apart
// or if the distance between the boxes is too small for the sum
// of their sizes
float da = diagonal of box_a;
float db = diagonal of box_b;
float ab = distance between centers of box_a and box_b;
return (ab < MAX_LINK_DISTANCE
&& ab < (da + db + MAX_LINK_PAIR_DISTANCE));
A few final comments...
(1) It is possible that this algorithm may change in the future, however we'll try hard not to make it more restrictive, since this would cause some currently linked objects to cease to link. I mention this because when we move to Havok-2 it is possible that the computations of the AABB's of the various pieces may change (for instance it may be that tight spheres will be used instead of AABB's as the proxy collision objects of some objects).
(2) The link test is done server-side only so there is no way to bypass it by cracking the client. In fact, virtually all operations that have any effect on the world fail or succeed on the server rather than the client. For some operations we also check on the client so we can disable the UI for those that are guaranteed to fail. The reason we don't do that for linking is that the client knows nothing about the physics engine and we use information from the physics engine to determine link success.
(3) The astute may have noticed that there is a slight order-of-operations failure for collections of clumps of very small primitives where the clumps rhemselves are spaced such that they just barely link, and each clump barely links itself. For such a scenario the link will succeed or fail depending on the order in which the primitives are selected. This is a known problem, however all of these objects sparse (mostly empty space) and barely fit into the set of objects that we wanted to support for linking.