svn merge -r83872:83893 linden/branches/Branch_1-20-0-Server to linden/release

HAVOK4 IN TEH HOUSE!!11!!ONE!!
If it is broken blame Joel for not fixing the loginassetdatabaseinventorygroupIM server instead of working on this.

QAR-448

5 files changed, 565 insertions, 15 deletions

diff --git a/indra/llprimitive/llmaterialtable.cpp b/indra/llprimitive/llmaterialtable.cpp
index 40cf97099c..3eea03e0b9 100644
--- a/indra/llprimitive/llmaterialtable.cpp
+++ b/indra/llprimitive/llmaterialtable.cpp
@@ -36,9 +36,58 @@
 #include "material_codes.h"
 #include "sound_ids.h"
 #include "imageids.h"
+#include <llphysics/llphysicsversion.h>
 
 LLMaterialTable LLMaterialTable::basic(1);
 
+/* 
+	Old Havok 1 constants
+
+// these are the approximately correct friction values for various materials
+// however Havok1's friction dynamics are not very correct, so the effective
+// friction coefficients that result from these numbers are approximately
+// 25-50% too low, more incorrect for the lower values.
+F32 const LLMaterialTable::FRICTION_MIN 	= 0.2f; 	
+F32 const LLMaterialTable::FRICTION_GLASS 	= 0.2f; 	// borosilicate glass
+F32 const LLMaterialTable::FRICTION_LIGHT 	= 0.2f; 	//
+F32 const LLMaterialTable::FRICTION_METAL 	= 0.3f; 	// steel
+F32 const LLMaterialTable::FRICTION_PLASTIC	= 0.4f; 	// HDPE
+F32 const LLMaterialTable::FRICTION_WOOD 	= 0.6f; 	// southern pine
+F32 const LLMaterialTable::FRICTION_FLESH 	= 0.60f; 	// saltwater
+F32 const LLMaterialTable::FRICTION_LAND 	= 0.78f; 	// dirt
+F32 const LLMaterialTable::FRICTION_STONE 	= 0.8f; 	// concrete
+F32 const LLMaterialTable::FRICTION_RUBBER 	= 0.9f; 	//
+F32 const LLMaterialTable::FRICTION_MAX 	= 0.95f; 	//
+*/
+
+#if LL_CURRENT_HAVOK_VERSION == LL_HAVOK_VERSION_460
+// Havok4 has more correct friction dynamics, however here we have to use
+// the "incorrect" equivalents for the legacy Havok1 behavior
+F32 const LLMaterialTable::FRICTION_MIN 	= 0.15f; 	
+F32 const LLMaterialTable::FRICTION_GLASS 	= 0.13f; 	// borosilicate glass
+F32 const LLMaterialTable::FRICTION_LIGHT 	= 0.14f; 	//
+F32 const LLMaterialTable::FRICTION_METAL 	= 0.22f; 	// steel
+F32 const LLMaterialTable::FRICTION_PLASTIC	= 0.3f; 	// HDPE
+F32 const LLMaterialTable::FRICTION_WOOD 	= 0.44f; 	// southern pine
+F32 const LLMaterialTable::FRICTION_FLESH 	= 0.46f; 	// saltwater
+F32 const LLMaterialTable::FRICTION_LAND 	= 0.58f; 	// dirt
+F32 const LLMaterialTable::FRICTION_STONE 	= 0.6f; 	// concrete
+F32 const LLMaterialTable::FRICTION_RUBBER 	= 0.67f; 	//
+F32 const LLMaterialTable::FRICTION_MAX 	= 0.71f; 	//
+#endif
+
+F32 const LLMaterialTable::RESTITUTION_MIN 		= 0.02f; 	
+F32 const LLMaterialTable::RESTITUTION_LAND 	= LLMaterialTable::RESTITUTION_MIN;
+F32 const LLMaterialTable::RESTITUTION_FLESH 	= 0.2f; 	// saltwater
+F32 const LLMaterialTable::RESTITUTION_STONE 	= 0.4f; 	// concrete
+F32 const LLMaterialTable::RESTITUTION_METAL 	= 0.4f; 	// steel
+F32 const LLMaterialTable::RESTITUTION_WOOD 	= 0.5f; 	// southern pine
+F32 const LLMaterialTable::RESTITUTION_GLASS 	= 0.7f; 	// borosilicate glass
+F32 const LLMaterialTable::RESTITUTION_PLASTIC	= 0.7f; 	// HDPE
+F32 const LLMaterialTable::RESTITUTION_LIGHT 	= 0.7f; 	//
+F32 const LLMaterialTable::RESTITUTION_RUBBER 	= 0.9f; 	//
+F32 const LLMaterialTable::RESTITUTION_MAX		= 0.95f;
+
 F32 const LLMaterialTable::DEFAULT_FRICTION = 0.5f;
 F32 const LLMaterialTable::DEFAULT_RESTITUTION = 0.4f;
 
diff --git a/indra/llprimitive/llmaterialtable.h b/indra/llprimitive/llmaterialtable.h
index 46b6f070d9..e84e75c677 100644
--- a/indra/llprimitive/llmaterialtable.h
+++ b/indra/llprimitive/llmaterialtable.h
@@ -33,11 +33,36 @@
 #define LL_LLMATERIALTABLE_H
 
 #include "lluuid.h"
-#include "linked_lists.h"
 #include "llstring.h"
 
+#include <list>
+
 const U32 LLMATERIAL_INFO_NAME_LENGTH = 256;
 
+// We've moved toward more reasonable mass values for the Havok4 engine.
+// The LEGACY_DEFAULT_OBJECT_DENSITY is used to maintain support for
+// legacy scripts code (llGetMass()) and script energy consumption.
+const F32 DEFAULT_OBJECT_DENSITY = 1000.0f;			// per m^3
+const F32 LEGACY_DEFAULT_OBJECT_DENSITY = 10.0f;
+
+// Avatars density depends on the collision shape used.  The approximate
+// legacy volumes of avatars are:
+// Body_Length Body_Width Body_Fat Leg_Length  Volume(m^3)
+// -------------------------------------------------------
+//    min     |   min    |  min   |    min    |   0.123   |
+//    max     |   max    |  max   |    max    |   0.208   |
+//
+// Either the avatar shape must be tweaked to match those volumes
+// or the DEFAULT_AVATAR_DENSITY must be adjusted to achieve the 
+// legacy mass.
+//
+// The current density appears to be low because the mass and
+// inertia are computed as if the avatar were a cylinder which
+// has more volume than the actual collision shape of the avatar.
+// See the physics engine mass properties code for more info.
+const F32 DEFAULT_AVATAR_DENSITY = 445.3f;		// was 444.24f;
+
+
 class LLMaterialInfo
 {
 public:
@@ -84,9 +109,33 @@ public:
 class LLMaterialTable
 {
 public:
+	static const F32 FRICTION_MIN;
+	static const F32 FRICTION_GLASS;
+	static const F32 FRICTION_LIGHT;
+	static const F32 FRICTION_METAL;
+	static const F32 FRICTION_PLASTIC;
+	static const F32 FRICTION_WOOD;
+	static const F32 FRICTION_LAND;
+	static const F32 FRICTION_STONE;
+	static const F32 FRICTION_FLESH;
+	static const F32 FRICTION_RUBBER;
+	static const F32 FRICTION_MAX;
+
+	static const F32 RESTITUTION_MIN;
+	static const F32 RESTITUTION_LAND;
+	static const F32 RESTITUTION_FLESH;
+	static const F32 RESTITUTION_STONE;
+	static const F32 RESTITUTION_METAL;
+	static const F32 RESTITUTION_WOOD;
+	static const F32 RESTITUTION_GLASS;
+	static const F32 RESTITUTION_PLASTIC;
+	static const F32 RESTITUTION_LIGHT;
+	static const F32 RESTITUTION_RUBBER;
+	static const F32 RESTITUTION_MAX;
+
 	typedef std::list<LLMaterialInfo*> info_list_t;
 	info_list_t mMaterialInfoList;
-	
+
 	LLUUID *mCollisionSoundMatrix;
 	LLUUID *mSlidingSoundMatrix;
 	LLUUID *mRollingSoundMatrix;
@@ -117,8 +166,8 @@ public:
 	char*  getName(U8 mcode);
 
 	F32 getDensity(U8 mcode);						        // kg/m^3, 0 if not found
-	F32 getFriction(U8 mcode);						        // havok values
-	F32 getRestitution(U8 mcode);						    // havok values
+	F32 getFriction(U8 mcode);						        // physics values
+	F32 getRestitution(U8 mcode);						    // physics values
 	F32 getHPMod(U8 mcode);
 	F32 getDamageMod(U8 mcode);
 	F32 getEPMod(U8 mcode);
diff --git a/indra/llprimitive/llprimitive.cpp b/indra/llprimitive/llprimitive.cpp
index 77bca8f803..cc676f73f1 100644
--- a/indra/llprimitive/llprimitive.cpp
+++ b/indra/llprimitive/llprimitive.cpp
@@ -113,9 +113,38 @@ const BOOL FLEXIBLE_OBJECT_DEFAULT_RENDERING_COLLISION_SPHERE = FALSE;
 
 const char *SCULPT_DEFAULT_TEXTURE = "be293869-d0d9-0a69-5989-ad27f1946fd4"; // old inverted texture: "7595d345-a24c-e7ef-f0bd-78793792133e";
 
+//static 
+// LEGACY: by default we use the LLVolumeMgr::gVolumeMgr global
+// TODO -- eliminate this global from the codebase!
+LLVolumeMgr* LLPrimitive::sVolumeManager = NULL;
+
+// static
+void LLPrimitive::setVolumeManager( LLVolumeMgr* volume_manager )
+{
+	if ( !volume_manager || sVolumeManager )
+	{
+		llerrs << "Unable to set LLPrimitive::sVolumeManager to NULL" << llendl;
+	}
+	sVolumeManager = volume_manager;
+}
+
+// static
+bool LLPrimitive::cleanupVolumeManager()
+{
+	BOOL res = FALSE;
+	if (sVolumeManager) 
+	{
+		res = sVolumeManager->cleanup();
+		delete sVolumeManager;
+		sVolumeManager = NULL;
+	}
+	return res;
+}
+
 
 //===============================================================
 LLPrimitive::LLPrimitive()
+:	mMiscFlags(0)
 {
 	mPrimitiveCode = 0;
 
@@ -149,7 +178,7 @@ LLPrimitive::~LLPrimitive()
 	// Cleanup handled by volume manager
 	if (mVolumep)
 	{
-		gVolumeMgr->cleanupVolume(mVolumep);
+		sVolumeManager->cleanupVolume(mVolumep);
 	}
 	mVolumep = NULL;
 }
@@ -162,7 +191,7 @@ LLPrimitive *LLPrimitive::createPrimitive(LLPCode p_code)
 	
 	if (retval)
 	{
-		retval->init(p_code);
+		retval->init_primitive(p_code);
 	}
 	else
 	{
@@ -173,7 +202,7 @@ LLPrimitive *LLPrimitive::createPrimitive(LLPCode p_code)
 }
 
 //===============================================================
-void LLPrimitive::init(LLPCode p_code)
+void LLPrimitive::init_primitive(LLPCode p_code)
 {
 	if (mNumTEs)
 	{
@@ -533,6 +562,8 @@ S32 LLPrimitive::setTEGlow(const U8 te, const F32 glow)
 
 LLPCode LLPrimitive::legacyToPCode(const U8 legacy)
 {
+	// TODO: Should this default to something valid?
+	// Maybe volume?
 	LLPCode pcode = 0;
 
 	switch (legacy)
@@ -621,7 +652,7 @@ LLPCode LLPrimitive::legacyToPCode(const U8 legacy)
 		pcode = LL_PCODE_TREE_NEW;
 		break;
 	default:
-		llwarns << "Unknown legacy code " << legacy << "!" << llendl;
+		llwarns << "Unknown legacy code " << legacy << " [" << (S32)legacy << "]!" << llendl;
 	}
 
 	return pcode;
@@ -904,10 +935,10 @@ BOOL LLPrimitive::setVolume(const LLVolumeParams &volume_params, const S32 detai
 			}
 		}
 
-		volumep = gVolumeMgr->getVolume(volume_params, detail);
+		volumep = sVolumeManager->getVolume(volume_params, detail);
 		if (volumep == mVolumep)
 		{
-			gVolumeMgr->cleanupVolume( volumep );  // gVolumeMgr->getVolume() creates a reference, but we don't need a second one.
+			sVolumeManager->cleanupVolume( volumep );  // LLVolumeMgr::getVolume() creates a reference, but we don't need a second one.
 			return TRUE;
 		}
 	}
@@ -950,7 +981,7 @@ BOOL LLPrimitive::setVolume(const LLVolumeParams &volume_params, const S32 detai
 
 
 	// build the new object
-	gVolumeMgr->cleanupVolume(mVolumep);
+	sVolumeManager->cleanupVolume(mVolumep);
 	mVolumep = volumep;
 	
 	U32 new_face_mask = mVolumep->mFaceMask;
diff --git a/indra/llprimitive/llprimitive.h b/indra/llprimitive/llprimitive.h
index eef58341e7..2b738f8d29 100644
--- a/indra/llprimitive/llprimitive.h
+++ b/indra/llprimitive/llprimitive.h
@@ -48,6 +48,7 @@ class LLColor4;
 class LLColor3;
 class LLTextureEntry;
 class LLDataPacker;
+class LLVolumeMgr;
 
 enum LLGeomType // NOTE: same vals as GL Ids
 {
@@ -269,11 +270,32 @@ public:
 class LLPrimitive : public LLXform
 {
 public:
+
+	// HACK for removing LLPrimitive's dependency on gVolumeMgr global.
+	// If a different LLVolumeManager is instantiated and set early enough
+	// then the LLPrimitive class will use it instead of gVolumeMgr.
+	static LLVolumeMgr* getVolumeManager() { return sVolumeManager; }
+	static void setVolumeManager( LLVolumeMgr* volume_manager);
+	static bool cleanupVolumeManager();
+
+	// these flags influence how the RigidBody representation is built
+	static const U32 PRIM_FLAG_PHANTOM 				= 0x1 << 0;
+	static const U32 PRIM_FLAG_VOLUME_DETECT 		= 0x1 << 1;
+	static const U32 PRIM_FLAG_DYNAMIC 				= 0x1 << 2;
+	static const U32 PRIM_FLAG_AVATAR 				= 0x1 << 3;
+	static const U32 PRIM_FLAG_SCULPT 				= 0x1 << 4;
+	// not used yet, but soon
+	static const U32 PRIM_FLAG_COLLISION_CALLBACK 	= 0x1 << 5;
+	static const U32 PRIM_FLAG_CONVEX 				= 0x1 << 6;
+	static const U32 PRIM_FLAG_DEFAULT_VOLUME		= 0x1 << 7;
+	static const U32 PRIM_FLAG_SITTING				= 0x1 << 8;
+	static const U32 PRIM_FLAG_SITTING_ON_GROUND	= 0x1 << 9;		// Set along with PRIM_FLAG_SITTING
+
 	LLPrimitive();
 	virtual ~LLPrimitive();
 
 	static LLPrimitive *createPrimitive(LLPCode p_code);
-	void init(LLPCode p_code);
+	void init_primitive(LLPCode p_code);
 
 	void setPCode(const LLPCode pcode);
 	const LLVolume *getVolumeConst() const { return mVolumep; }		// HACK for Windoze confusion about ostream operator in LLVolume
@@ -369,8 +391,15 @@ public:
 
 	void setTextureList(LLTextureEntry *listp);
 
-	inline BOOL			isAvatar() const;
-	
+	inline BOOL	isAvatar() const;
+	inline BOOL	isSittingAvatar() const;
+	inline BOOL	isSittingAvatarOnGround() const;
+
+	void setFlags(U32 flags) { mMiscFlags = flags; }
+	void addFlags(U32 flags) { mMiscFlags |= flags; }
+	void removeFlags(U32 flags) { mMiscFlags &= ~flags; }
+	U32 getFlags() const { return mMiscFlags; }
+
 	static const char *pCodeToString(const LLPCode pcode);
 	static LLPCode legacyToPCode(const U8 legacy);
 	static U8 pCodeToLegacy(const LLPCode pcode);
@@ -388,11 +417,28 @@ protected:
 	LLTextureEntry		*mTextureList;		// list of texture GUIDs, scales, offsets
 	U8					mMaterial;			// Material code
 	U8					mNumTEs;			// # of faces on the primitve	
+	U32 				mMiscFlags;			// home for misc bools
+
+	static LLVolumeMgr* sVolumeManager;
 };
 
 inline BOOL LLPrimitive::isAvatar() const
 {
-	return mPrimitiveCode == LL_PCODE_LEGACY_AVATAR;
+	return ( LL_PCODE_LEGACY_AVATAR == mPrimitiveCode ) ? TRUE : FALSE;
+}
+
+inline BOOL LLPrimitive::isSittingAvatar() const
+{
+	// this is only used server-side
+	return ( LL_PCODE_LEGACY_AVATAR == mPrimitiveCode 
+			 &&	 ((getFlags() & (PRIM_FLAG_SITTING | PRIM_FLAG_SITTING_ON_GROUND)) != 0) ) ? TRUE : FALSE;
+}
+
+inline BOOL LLPrimitive::isSittingAvatarOnGround() const
+{
+	// this is only used server-side
+	return ( LL_PCODE_LEGACY_AVATAR == mPrimitiveCode 
+			 &&	 ((getFlags() & PRIM_FLAG_SITTING_ON_GROUND) != 0) ) ? TRUE : FALSE;
 }
 
 // static
diff --git a/indra/llprimitive/llprimlinkinfo.h b/indra/llprimitive/llprimlinkinfo.h
new file mode 100644
index 0000000000..139617f969
--- /dev/null
+++ b/indra/llprimitive/llprimlinkinfo.h
@@ -0,0 +1,375 @@
+/** 
+ * @file llprimlinkinfo.h
+ * @author andrew@lindenlab.com
+ * @brief A template for determining which prims in a set are linkable
+ *
+ * Copyright (c) 2007-$CurrentYear$, Linden Research, Inc.
+ * $License$
+ */
+
+
+#ifndef LL_PRIM_LINK_INFO_H
+#define LL_PRIM_LINK_INFO_H
+
+// system includes
+#include <iostream>
+#include <map>
+#include <list>
+#include <vector>
+
+// common includes
+#include "stdtypes.h"
+#include "v3math.h"
+#include "llquaternion.h"
+#include "llsphere.h"
+
+
+const F32 MAX_OBJECT_SPAN = 54.f;		// max distance from outside edge of an object to the farthest edge
+const F32 OBJECT_SPAN_BONUS = 2.f;		// infinitesimally small prims can always link up to this distance
+const S32 MAX_PRIMS_PER_OBJECT = 255;
+
+
+template < typename DATA_TYPE >
+class LLPrimLinkInfo
+{
+public:
+	LLPrimLinkInfo();
+	LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere );
+	~LLPrimLinkInfo();
+
+	void set( DATA_TYPE data, const LLSphere& sphere );
+	void append( DATA_TYPE data, const LLSphere& sphere );
+	void getData( std::list< DATA_TYPE >& data_list ) const;
+	F32 getDiameter() const;
+	LLVector3 getCenter() const;
+
+	// returns 'true' if this info can link with other_info
+	bool canLink( const LLPrimLinkInfo< DATA_TYPE >& other_info );
+
+	S32 getPrimCount() const { return mDataMap.size(); }
+
+	void mergeLinkableSet( typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );
+
+	void transform(const LLVector3& position, const LLQuaternion& rotation);
+
+private:
+	// returns number of merges made
+	S32 merge(LLPrimLinkInfo< DATA_TYPE >& other_info);
+
+	// returns number of collapses made
+	static S32 collapse(typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );
+
+	void computeBoundingSphere();
+
+	// Internal utility to encapsulate the link rules
+	F32 get_max_linkable_span(const LLSphere& first, const LLSphere& second);
+	F32 get_span(const LLSphere& first, const LLSphere& second);
+
+private:
+	std::map< DATA_TYPE, LLSphere > mDataMap;
+	LLSphere mBoundingSphere;
+};
+
+
+
+template < typename DATA_TYPE >
+LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo()
+:	mBoundingSphere( LLVector3(0.f, 0.f, 0.f), 0.f )
+{
+}
+
+template < typename DATA_TYPE >
+LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere)
+:	mBoundingSphere(sphere)
+{
+	mDataMap[data] = sphere;
+}
+
+template < typename DATA_TYPE >
+LLPrimLinkInfo< DATA_TYPE >::~LLPrimLinkInfo()
+{
+	mDataMap.clear();
+}
+
+template < typename DATA_TYPE >
+void LLPrimLinkInfo< DATA_TYPE>::set( DATA_TYPE data, const LLSphere& sphere )
+{
+	if (!mDataMap.empty())
+	{
+		mDataMap.clear();
+	}
+	mDataMap[data] = sphere;
+	mBoundingSphere = sphere;
+}
+
+template < typename DATA_TYPE >
+void LLPrimLinkInfo< DATA_TYPE>::append( DATA_TYPE data, const LLSphere& sphere )
+{
+	mDataMap[data] = sphere;
+	if (!mBoundingSphere.contains(sphere))
+	{
+		computeBoundingSphere();
+	}
+}
+
+template < typename DATA_TYPE >
+void LLPrimLinkInfo< DATA_TYPE >::getData( std::list< DATA_TYPE >& data_list) const
+{
+	typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
+	for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
+	{
+		data_list.push_back(map_itr->first);
+	}
+}
+
+template < typename DATA_TYPE >
+F32 LLPrimLinkInfo< DATA_TYPE >::getDiameter() const
+{ 
+	return 2.f * mBoundingSphere.getRadius();
+}
+
+template < typename DATA_TYPE >
+LLVector3 LLPrimLinkInfo< DATA_TYPE >::getCenter() const
+{ 
+	return mBoundingSphere.getCenter(); 
+}
+
+template < typename DATA_TYPE >
+F32 LLPrimLinkInfo< DATA_TYPE >::get_max_linkable_span(const LLSphere& first, const LLSphere& second)
+{
+	F32 max_span = 3.f * (first.getRadius() + second.getRadius()) + OBJECT_SPAN_BONUS;
+	if (max_span > MAX_OBJECT_SPAN)
+	{
+		max_span = MAX_OBJECT_SPAN;
+	}
+
+	return max_span;
+}
+
+template < typename DATA_TYPE >
+F32 LLPrimLinkInfo< DATA_TYPE >::get_span(const LLSphere& first, const LLSphere& second)
+{
+	F32 span = (first.getCenter() - second.getCenter()).length()
+				+ first.getRadius() + second.getRadius();
+	return span;
+}
+
+// static
+// returns 'true' if this info can link with any part of other_info
+template < typename DATA_TYPE >
+bool LLPrimLinkInfo< DATA_TYPE >::canLink(const LLPrimLinkInfo& other_info)
+{
+	F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);
+
+	F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);
+	
+	if (span <= max_span)
+	{
+		// The entire other_info fits inside the max span.
+		return TRUE;
+	}
+	else if (span > max_span + 2.f * other_info.mBoundingSphere.getRadius())
+	{
+		// there is no way any piece of other_info could link with this one
+		return FALSE;
+	}
+
+	// there may be a piece of other_info that is linkable
+	typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
+	for (map_itr = other_info.mDataMap.begin(); map_itr != other_info.mDataMap.end(); ++map_itr)
+	{
+		const LLSphere& other_sphere = (*map_itr).second;
+		max_span = get_max_linkable_span(mBoundingSphere, other_sphere);
+
+		span = get_span(mBoundingSphere, other_sphere);
+
+		if (span <= max_span)
+		{
+			// found one piece that is linkable
+			return TRUE;
+		}
+	}
+	return FALSE;
+}
+
+// merges elements of 'unlinked' 
+// returns number of links made (NOT final prim count, NOR linked prim count)
+// and removes any linkable infos from 'unlinked' 
+template < typename DATA_TYPE >
+void LLPrimLinkInfo< DATA_TYPE >::mergeLinkableSet(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
+{
+	bool linked_something = true;
+	while (linked_something)
+	{
+		linked_something = false;
+
+		typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = unlinked.begin();
+		while ( other_itr != unlinked.end()
+			   && getPrimCount() < MAX_PRIMS_PER_OBJECT )
+		{
+			S32 merge_count = merge(*other_itr);
+			if (merge_count > 0)
+			{
+				linked_something = true;
+			}
+			if (0 == (*other_itr).getPrimCount())
+			{
+				unlinked.erase(other_itr++);
+			}
+			else
+			{
+				++other_itr;
+			}
+		}
+		if (!linked_something
+			&& unlinked.size() > 1)
+		{
+			S32 collapse_count = collapse(unlinked);
+			if (collapse_count > 0)
+			{
+				linked_something = true;
+			}
+		}
+	}
+}
+
+// transforms all of the spheres into a new reference frame
+template < typename DATA_TYPE >
+void LLPrimLinkInfo< DATA_TYPE >::transform(const LLVector3& position, const LLQuaternion& rotation)
+{
+	typename std::map< DATA_TYPE, LLSphere >::iterator map_itr;
+	for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
+	{
+		(*map_itr).second.setCenter((*map_itr).second.getCenter() * rotation + position);
+	}
+	mBoundingSphere.setCenter(mBoundingSphere.getCenter() * rotation + position);
+}
+
+// private
+// returns number of links made
+template < typename DATA_TYPE >
+S32 LLPrimLinkInfo< DATA_TYPE >::merge(LLPrimLinkInfo& other_info)
+{
+	S32 link_count = 0;
+
+//	F32 other_radius = other_info.mBoundingSphere.getRadius();
+//	other_info.computeBoundingSphere();
+//	if ( other_radius != other_info.mBoundingSphere.getRadius() )
+//	{
+//		llinfos << "Other bounding sphere changed!!" << llendl;
+//	}
+
+//	F32 this_radius = mBoundingSphere.getRadius();
+//	computeBoundingSphere();
+//	if ( this_radius != mBoundingSphere.getRadius() )
+//	{
+//		llinfos << "This bounding sphere changed!!" << llendl;
+//	}
+
+
+	F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);
+
+	//  F32 center_dist = (mBoundingSphere.getCenter() - other_info.mBoundingSphere.getCenter()).length();
+	//	llinfos << "objects are " << center_dist << "m apart" << llendl;
+	F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);
+
+	F32 span_limit = max_span + (2.f * other_info.mBoundingSphere.getRadius());
+	if (span > span_limit)
+	{
+		// there is no way any piece of other_info could link with this one
+		// llinfos << "span too large:  " << span << " vs. " << span_limit << llendl;
+		return 0;
+	}
+
+	bool completely_linkable = (span <= max_span) ? true : false;
+
+	typename std::map< DATA_TYPE, LLSphere >::iterator map_itr = other_info.mDataMap.begin();
+	while (map_itr != other_info.mDataMap.end()
+			&& getPrimCount() < MAX_PRIMS_PER_OBJECT )
+	{
+		DATA_TYPE other_data = (*map_itr).first;
+		LLSphere& other_sphere = (*map_itr).second;
+
+		if (!completely_linkable)
+		{
+			max_span = get_max_linkable_span(mBoundingSphere, other_sphere);
+	
+			F32 span = get_span(mBoundingSphere, other_sphere);
+
+			if (span > max_span)
+			{
+				++map_itr;
+				continue;
+			}
+		}
+
+		mDataMap[other_data] = other_sphere;
+		++link_count;
+
+		if (!mBoundingSphere.contains(other_sphere) )
+		{
+			computeBoundingSphere();
+		}
+
+		// remove from the other info
+		other_info.mDataMap.erase(map_itr++);
+	}
+
+	if (link_count > 0 && other_info.getPrimCount() > 0)
+	{
+		other_info.computeBoundingSphere();
+	}
+	return link_count;
+}
+
+// links any linkable elements of unlinked
+template < typename DATA_TYPE >
+S32 LLPrimLinkInfo< DATA_TYPE >::collapse(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
+{ 
+	S32 link_count = 0;
+	bool linked_something = true;
+	while (linked_something)
+	{
+		linked_something = false;
+
+		typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator this_itr = unlinked.begin();
+		typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = this_itr;
+		++other_itr;
+		while ( other_itr != unlinked.end() )
+			   
+		{
+			S32 merge_count = (*this_itr).merge(*other_itr);
+			if (merge_count > 0)
+			{
+				linked_something = true;
+				link_count += merge_count;
+			}
+			if (0 == (*other_itr).getPrimCount())
+			{
+				unlinked.erase(other_itr++);
+			}
+			else
+			{
+				++other_itr;
+			}
+		}
+	}
+	return link_count;
+}
+
+
+template < typename DATA_TYPE >
+void LLPrimLinkInfo< DATA_TYPE >::computeBoundingSphere()
+{ 
+	std::vector< LLSphere > sphere_list;
+	typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
+	for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
+	{
+		sphere_list.push_back(map_itr->second);
+	}
+	mBoundingSphere = LLSphere::getBoundingSphere(sphere_list);
+}
+
+
+#endif
+