Difference between revisions of "Linkability Rules"

From Second Life Wiki
Jump to navigation Jump to search
(43 intermediate revisions by 13 users not shown)
Line 1: Line 1:
=== Linkability formulae ===
{{Multi-lang}}
= New Linkability Rule =
'''The linkability rule for objects changed as of Dec 2010.'''  The main motivation was to make the linkability check more efficient but a consequence is that they are also much simpler.  The size-dependency of the prims has been discarded.  The only thing that matters is the bounding sphere of the collection of prim centers.  The linkability rule can be written as:


Consider two primitives, A and B.  Whether they can be linked or not is determined
  LINKABLE = {{HoverText|D|diameter of the smallest bounding sphere of the collection of prim centers}} < 54  AND  {{HoverText|N|number of prims in the collection}} ≤ 256
by measuring the ''span'' from the edge of one object's ''bounding sphere''to
  where D = diameter of the smallest bounding sphere of the collection of prim centers
the far opposite edge of the other's bounding sphere and comparing that value to the  
  and N = number of prims in the collection
''maximum linkability span'' which is a function of the radii of the two bounding spheres:


    (1)    max_link_span = minimum( 3 * (radius_A + radius_B) + SMALLEST_MAX, LARGEST_MAX )
[[User:Andrew Linden|Andrew Linden]] 21:47, 02 December 2010 (UTC)


where:
If you are interested in how the old formula worked, see [[Linkability Rules/Havok 4]].


    (3)    SMALLEST_MAX = 1.0 meters
=== Notes ===
    (4)    LARGEST_MAX = 54.0 meters
* [2011-08-27-16:52]  Andrew Linden: 54 was the minimum sphere that still contained all of the legacy linkable content.
    (5)    radius_X = radius of the primitive X's ''bounding sphere'' (Figure A)
    (6)    minimum(C, D) = C if less than D, otherwise D


If the measured span of the two primitives is less than or equal to max_link_span then they can be linked.  Put in mathematical
[[Category:Havok]]
terms:
 
    (7)    A_can_link_to_B = ( length(center_A - center_B) + radius_A + radius_B <= max_link_distance )
 
{|align="right"
|[[Image:Primitive_diameter.png]]
|}
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.
 
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 ====
radius_A = ~0.01
 
radius_B = ~0.01
 
SMALLEST_MAX = 1.0 meters
 
LARGEST_MAX = 54.0 meters
 
max_link_distance = 1.06m
 
==== one large prim and one small prim ====
radius_A = 5m
 
radius_B = ~0.01
 
SMALLEST_MAX = 1.0 meters
 
LARGEST_MAX = 54.0 meters
 
3 * (radius_A + radius_B) + SMALLEST_MAX = 15.03 meters
 
15.03m is smaller than 54.0m
 
Thus the max_link_distance = 15.03m
 
==== 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.
 
radius_A = 8.66m
 
radius_B = 8.66m
 
SMALLEST_MAX = 1.0 meters
 
LARGEST_MAX = 54.0 meters
 
3 * (radius_A + radius_B) + SMALLEST_MAX = 52.96m
 
52.96m is smaller than 54m
 
Thus max_link_distance = 52.96m

Revision as of 16:57, 26 August 2011

New Linkability Rule

The linkability rule for objects changed as of Dec 2010. The main motivation was to make the linkability check more efficient but a consequence is that they are also much simpler. The size-dependency of the prims has been discarded. The only thing that matters is the bounding sphere of the collection of prim centers. The linkability rule can be written as: 

 LINKABLE = D < 54  AND  N ≤ 256
 where D = diameter of the smallest bounding sphere of the collection of prim centers
 and N = number of prims in the collection

Andrew Linden 21:47, 02 December 2010 (UTC)

If you are interested in how the old formula worked, see Linkability Rules/Havok 4.

Notes

  • [2011-08-27-16:52] Andrew Linden: 54 was the minimum sphere that still contained all of the legacy linkable content.
Retrieved from "https://wiki.secondlife.com/w/index.php?title=Linkability_Rules&oldid=1152486"