|
|
| (44 intermediate revisions by 14 users not shown) |
| Line 1: |
Line 1: |
| === Linkability formulae === | | {{Obsolete|Max distance has been raised from 54m to 64m as of 2023/06/27. Update was announced here. [https://community.secondlife.com/blogs/entry/13626-coming-soon-server-release-202306/ Tech Updates Server Release 2023.06]}} |
| | {{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
| |
