Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Link algorithm exposed

Andrew Linden
Linden staff
Join date: 18 Nov 2002
Posts: 692
04-02-2004 15:43
When linking two or more primitives in SL 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 not yet linked)
{
if we_can_link(box_list with total_box)
{
total_box = smallest_union_box(total_box and box_list);
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.
Xylor Baysklef
Scripting Addict
Join date: 4 May 2003
Posts: 109
04-03-2004 18:35
Perfect timing, Andrew ^_~. I just ran into this problem again, and this is exactly what I needed, thanks =).

Xylor
Eep Quirk
Absolutely Relative
Join date: 15 Dec 2004
Posts: 1,211
02-06-2005 15:35
Link distance is bugged: if I have two .5m^3 blocks 20m apart, the link fails, but if I make one block 9.88m long along the axis pointing to the other block, the link works. Why? The centers of both prims are well within 32m...

Then if I try and link a 3rd .5m^3 block 15m away from the middle block (9.88m), on the same axis, if I link the 3rd block to the middle block (root), I get a link failed error but if I link the middle block to the 3rd block I get no error but no link occurs. Uh...
Mike Zidane
Registered User
Join date: 10 Apr 2004
Posts: 255
02-07-2005 08:02
It's not bugged, it's just not friendly.

There is more to it than the center of your prims. The size play a part too. I dunno if that's in the code he posted cuz I didn't read it cuz I dont typically have a problem.
_____________________
I'm only faking when I get it right. - CC
Eep Quirk
Absolutely Relative
Join date: 15 Dec 2004
Posts: 1,211
02-07-2005 11:26
It's bugged when it doesn't work as it's explained to work. The LSL Wiki says the link distance is 32m but I have shown a case where that's just not true. Hence, the bug. Size shouldn't matter since only prim origin is supposed to determine link distance.
Kelly Linden
Linden Developer
Join date: 29 Mar 2004
Posts: 896
02-07-2005 11:52
Link distance is related to the size of the prims.

In particular note from the psuedo code above, in the first box there are two variables that describe the link distance cap for large and small prims:
float MAX_LINK_PAIR_DISTANCE = 1; // cap max dist btw tiny prims
float MAX_LINK_DISTANCE = 32; // cap max dist btw large prims


At the bottom of the second code box is 'can_link' which does the check. The comment there says:
// 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


The outcome of this is:
* All prims, no matter how small, with centers within 1 meter of each other are linkable.
* No prims, no matter how large, can be linked if their centers are further than 32 meters apart.
* In all other cases the max link distance is related to prim size
_____________________
- Kelly Linden
Cross Lament
Loose-brained Vixen
Join date: 20 Mar 2004
Posts: 1,115
02-07-2005 12:38
Hmm... my question is... why is the link distance related to the size of the prims, in the first place? :)
_____________________
- Making everyone's day just a little more surreal -

Teeple Linden: "OK, where did the tentacled thing go while I was playing with my face?"
Eep Quirk
Absolutely Relative
Join date: 15 Dec 2004
Posts: 1,211
02-07-2005 12:40
Indeed...

Thanks for clarification, Kelly.
Strife Onizuka
Moonchild
Join date: 3 Mar 2004
Posts: 5,887
02-07-2005 13:03
It should be noted that link distance restriction enforcement is dependant on the sim. Also you should never break a link bigger the 512 meters while more then one avatar is sitting on the object.

The link distance is related to the size of the prims because it is possible to use the edit tools to expand an object's scale (and possibly bypassing the link distance restriction). Why it doesn't just clamp the scale to stop this I don't know.
_____________________
Truth is a river that is always splitting up into arms that reunite. Islanded between the arms, the inhabitants argue for a lifetime as to which is the main river.
- Cyril Connolly

Without the political will to find common ground, the continual friction of tactic and counter tactic, only creates suspicion and hatred and vengeance, and perpetuates the cycle of violence.
- James Nachtwey
Eata Kitty
Registered User
Join date: 21 Jan 2005
Posts: 387
01-04-2007 16:33
The link rules differ for already linked objects, why? This has given me a ton of problems in that groups of already linked objects will refuse to link due to distance but if unlinked will link fine. Order of linking an actual physical distance (Of the sets) has no effect, the sets will just refuse to link until certain prims have been removed from them.

Unlinking is not much help as it ruins scripted linking, you can very quickly link five existing sets of links but the two hundred individual prims will take a very long time to link.
Lee Ponzu
What Would Steve Do?
Join date: 28 Jun 2006
Posts: 1,770
01-05-2007 09:04
From: Eep Quirk
It's bugged when it doesn't work as it's explained to work. The LSL Wiki says the link distance is 32m but I have shown a case where that's just not true. Hence, the bug. Size shouldn't matter since only prim origin is supposed to determine link distance.

Maybe the problem is in the explanation. If a Wiki isn't correct, then the Wiki user can correct it. That's the idea of a Wiki.
Evgeny Zabelin
Registered User
Join date: 8 Mar 2007
Posts: 1
04-25-2007 02:48
From: Strife Onizuka
It should be noted that link distance restriction enforcement is dependant on the sim. Also you should never break a link bigger the 512 meters while more then one avatar is sitting on the object.

The link distance is related to the size of the prims because it is possible to use the edit tools to expand an object's scale (and possibly bypassing the link distance restriction). Why it doesn't just clamp the scale to stop this I don't know.



I noticed that bypassing the link distance restriction with the edit tools will result in a very unstable link. very often I have to relink the whole object again when I login the next day. and that is no fun.
Lex Neva
wears dorky glasses
Join date: 27 Nov 2004
Posts: 1,361
04-25-2007 09:02
Such unstable links will also tend to unlink the next time you rez them.
Shep Planer
Registered User
Join date: 9 Apr 2007
Posts: 153
08-08-2007 18:41
ok well whatever the problem is I dont care, I just would like someone to please tell me what to do when this stupid and annoying link fail thing happens. Ive moved the guilty prim around and around, ive changed its size etc etc but it still wont link!! what should I do?
Rusty Satyr
Meadow Mythfit
Join date: 19 Feb 2004
Posts: 610
08-08-2007 18:57
From: Shep Planer
ok well whatever the problem is I dont care, I just would like someone to please tell me what to do when this stupid and annoying link fail thing happens. Ive moved the guilty prim around and around, ive changed its size etc etc but it still wont link!! what should I do?


I've had a situation that refused to go away until I did this:

Unlink the entire object

Shift-Drag the set of selected prims off to the side.

The dragged copy is the OLD copy, the copy left behind is the NEW copy.

Select the prims of the NEW copy and link those together.


You may be able to get away with simply unlinking the object, moving them and then re-selecting the prims to re-link them as well.
Shep Planer
Registered User
Join date: 9 Apr 2007
Posts: 153
08-09-2007 02:20
Thnaks for the help, I Tried this and it didnt work, what now?
Learjeff Innis
musician & coder
Join date: 27 Nov 2006
Posts: 817
08-09-2007 07:53
Link the prims together one at a time until you find the offending ones. This may offer a clue as to the problem. (You might be able to do this more quickly by linking in subsets or prims at a time.)

This can happen due to "poison prims", prims which are somehow borked and won't link any more. The shift-drag to copy usually fixes it by making every prim anew.

It may be that your object was linked and then they changed the rules, so now you can never link it together again.
Rusty Satyr
Meadow Mythfit
Join date: 19 Feb 2004
Posts: 610
08-09-2007 09:36
You're most likely to encounter this problem if you take an already linked object and then stretch the whole object larger and then try to do any linking/unlinking. The prim sizes and distances may no longer be within acceptable ranges to be re-linked.

(Putting small buttons onto a large object causes me linking grief most often.)