|
|
| (16 intermediate revisions by 7 users not shown) |
| Line 1: |
Line 1: |
| Determining whether or not a set of prims/objects is linkable is somewhat complex. Generally, larger prims and objects may have greater distances between them to become linked, with a minimum of 2 meters and a maximum of 54. The distance depends on the position and the X/Y/Z size of each prim, but not their shapes, rotations, size changes due to cuts, hollows, etc.
| | {{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: |
|
| |
|
| ==In Brief== | | 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 |
| *If the ''distance'' between two or more objects is too large, they cannot be linked.
| | where D = diameter of the smallest bounding sphere of the collection of prim centers |
| *The allowed distance is larger for large objects, and smaller for small objects.
| | and N = number of prims in the collection |
| *The real rules are quite complicated.
| |
| ==Quick overview==
| |
| Kelly's Quick Overview:
| |
| * Two pieces can link if their bounding boxes would completely fit within a "Linkability Sphere".
| |
| * The size of the Linkability Sphere is between 2m and 54m diameter, depending on the scale of the two pieces being linked.
| |
| ** Specifically the size is 3 times the sum of both object's bounding sphere radius plus 2 meters, up to a maximum of 54m.
| |
| * If linking more than two pieces, treat any 2 pieces that can link by the above rule as 1 piece whose scale encompasses both pieces.
| |
| * Repeat until everything is linked.
| |
|
| |
|
| At the small extreme: two tiny prims can be linked if they are within about 2 meters from each other.
| | [[User:Andrew Linden|Andrew Linden]] 21:47, 02 December 2010 (UTC) |
|
| |
|
| At the large extreme: the largest linked object that can be created must fit within a sphere with a diameter of 54 meters.
| | If you are interested in how the old formula worked, see [[Linkability Rules/Havok 4]]. |
|
| |
|
| [[Image:Primitive_diameter.png|thumb|right|Figure A: The bounding spheres of two example prims, one of which has been cut. The two spheres are identical in size.]] | | === Notes === |
| * Whether two prims can be linked depends only on each prim's X/Y/Z scale and position. Other properties (such as rotation, hollow, cut, sculpt, etc.) are ignored. This means that linking calculations are done as if every prim were a rectangular box that is stretched but otherwise undistorted (i.e. with the X, Y, and Z sizes the same as the original prim, but everything else 'normal').
| | * [2011-08-27-16:52] Andrew Linden: 54 was the minimum sphere that still contained all of the legacy linkable content. |
| ** Editing and selecting any object and selecting the 'stretch' tool will display this "''local bounding box''" for that object.
| |
| ** Exception for megaprims: If any side is more than 10 meters, treat that side as if it were 10 meters.
| |
|
| |
|
| A way to visualize the procedure:
| | [[Category:Havok]] |
| # Imagine transforming every prim in every object into the aforementioned boxes.
| |
| # For each existing (linked-together) object, imagine the smallest sphere that totally encloses the bounding boxes of the prims which belong to it. (For individual prims, just enclose that one box.)
| |
| # Triple the size of each sphere, then add another meter around each sphere. (Don't move the centers of the spheres.)
| |
| # You can link objects if their spheres touch or intersect. Link everything that can be linked at this point.
| |
| #* Exception: If any new object would need a sphere of bigger than 54 meters to enclose all its boxes, you can't make that object.
| |
| # Repeat this procedure with the newly linked objects until you can't link any more.
| |
| | |
| Read the section below for details of the linkability formula, including examples and what actually gets linked if you can't link everything.
| |
| | |
| ==The details==
| |
| Consider two primitives, A and B. Whether they can be linked or not is determined
| |
| by measuring the ''span'' from the edge of one object's ''bounding sphere'' to
| |
| the far opposite edge of the other's bounding sphere and comparing that value to the
| |
| ''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) + LINK_BONUS, LARGEST_MAX )
| |
| | |
| where:
| |
| | |
| (3) LINK_BONUS = 2.0 meters
| |
| (4) LARGEST_MAX = 54.0 meters
| |
| (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 bounding spheres is less than or equal to max_link_span then the corresponding primitives can be linked. Put in mathematical
| |
| terms:
| |
| | |
| (7) A_can_link_to_B = ( length(center_A - center_B) + radius_A + radius_B <= max_link_span )
| |
| | |
| 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
| |
| has sides that are equal to the primitive's ''scale''. One exception to this
| |
| rule is that megaprim scale components greater than 10 meters are clamped to 10.
| |
| | |
| 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. 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.
| |
| | |
| TODO -- we need a new figure_A that shows ''radius'' instead of ''diameter''.
| |
| Also need new figures _B and _C for two linkable prims and two linkable multi-prim objects.
| |
| | |
| === Linkability algorithm ===
| |
| | |
| [[Image:Linking_example.png|thumb|right|Figure B: Example of how groups of primitives are linked to a root primitive for three or more objects.]]
| |
| 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.
| |
| | |
| === Formulas ===
| |
| | |
| Radius of the Bounding Sphere: SQRT(x^2 + y^2 + z^2)/2
| |
| | |
| Maximum link span (two prims): Minimum of (3 * (radius_A + radius_B) + LINK_BONUS) and 54
| |
| | |
| Distance between the centers (two prims): Minimum of ((3 * (radius_A + radius_B) + LINK_BONUS) - (radius_A + radius_B)) and 54 - (radius_A + radius_B).
| |
| If the 54 meters maximum is not reached the distance between centers formula can be condensed to:
| |
| | |
| SQRT(Xa^2 + Ya^2 + Za^2) + SQRT(Xb^2 + Yb^2 + Zb^2) + LINK_BONUS
| |
| | |
| === Examples ===
| |
| | |
| ==== 2 very small prims ====
| |
| radius_A = ~0.01
| |
| | |
| radius_B = ~0.01
| |
| | |
| LINK_BONUS = 2.0 meters
| |
| | |
| LARGEST_MAX = 54.0 meters
| |
| | |
| 3 * (radius_A + radius_B) + LINK_BONUS = 2.06 meters
| |
| | |
| 2.06 is less than 54
| |
| | |
| Thus max_link_span = 2.06m
| |
| | |
| ==== one large prim and one small prim ====
| |
| radius_A = 5m
| |
| (Note: This is not a 10m prim. A 10x10x10m prim would have radius of 8.66m even if it's a sphere or sculpty. This example should probably be changed to use a radius_A of 8.66.)
| |
| | |
| radius_B = ~0.01
| |
| | |
| LINK_BONUS = 2.0 meters
| |
| | |
| LARGEST_MAX = 54.0 meters
| |
| | |
| 3 * (radius_A + radius_B) + LINK_BONUS = 17.03 meters
| |
| | |
| 17.03 is smaller than 54.0
| |
| | |
| Thus max_link_span = 17.03m
| |
| | |
| Note this is NOT the maximum distance between the two centers. The center of the large prim is actually 5 meters inside the bounding sphere, so the max distance between the centers is approximately 12.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 dimensions.)
| |
| Let's take the case of two 10m x 10m x 10m prims.
| |
| | |
| radius_A = 8.66m
| |
| | |
| radius_B = 8.66m
| |
| | |
| LINK_BONUS = 2.0 meters
| |
| | |
| LARGEST_MAX = 54.0 meters
| |
| | |
| 3 * (radius_A + radius_B) + LINK_BONUS = 53.96m
| |
| | |
| 53.96 is smaller than 54
| |
| | |
| Thus max_link_span = 53.96m
| |
| | |
| Note this is NOT the maximum distance between the two centers. The center of each prim is actually 8.66m meters inside the bounding sphere, so the max distance between the centers is approximately 36.64m.
| |
| | |
| Distance between centers: SQRT(Xa^2 + Ya^2 + Za^2) + SQRT(Xb^2 + Yb^2 + Zb^2) + LINK_BONUS
| |
| | |
| SQRT(10^2+10^2+10^2) + SQRT(10^2+10^2+10^2) + 2
| |
| | |
| SQRT(300) + SQRT(300) + 2
| |
| | |
| 17.32 + 17.32 + 2 = 36.64m
| |
| | |
| == Bugs ==
| |
| ===Some stuff that linked in Havok1 do not link in Havok4.===
| |
| The Havok4 linkability limits are larger that Havok1 for most prim collections, however there is indeed a set of objects that were linkable in Havok1 that are NOT linkable in Havok4.
| |
| | |
| Havok1 used an "axis aligned bounding box" (AABB) algorithm, and it turns out that the span (distance from one corner of the AABB to the opposite corner) of the maximum box in Havok1 is longer than the diameter of the maximum bounding sphere in Havok4.
| |
| | |
| The maximum AABB was actually a box with sides of about 32 meters ==> span was 55.4 meters. So the Havok1 box almost fits inside the 54 diameter sphere used in Havok4... but has some corners that stick out very slightly ==> any house that just barely fits inside the AABB might not link in Havok4.
| |
| | |
| Note that the "AA" means "axis aligned" and that means that if you were to rotate your house... the maximum box would NOT rotate since it was always aligned with the axes of the world (East, North, and Up), and your house would not fit inside the box in its rotated state, and would unlink later after the region suffered a shutdown/load cycle (this was a bug in Havok1), or if you were to take it to inventory in its rotated state and then rez that inventory (it would show up unlinked).
| |
| | |
| ===When I link two prims the maximum distance between them does NOT agree with the formula above.===
| |
| Make sure you are measuring the span of the final bounding sphere and not the distances between the centers of the two primitives.
| |
| | |
| [[Category:Havok4]] | |
