/** * @file llprimlinkinfo.h * @author andrew@lindenlab.com * @brief A template for determining which prims in a set are linkable * * $LicenseInfo:firstyear=2007&license=viewerlgpl$ * Second Life Viewer Source Code * Copyright (C) 2010, Linden Research, Inc. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; * version 2.1 of the License only. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA * $/LicenseInfo$ */ #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 = 256; 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() ) // { // LL_INFOS() << "Other bounding sphere changed!!" << LL_ENDL; // } // F32 this_radius = mBoundingSphere.getRadius(); // computeBoundingSphere(); // if ( this_radius != mBoundingSphere.getRadius() ) // { // LL_INFOS() << "This bounding sphere changed!!" << LL_ENDL; // } F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere); // F32 center_dist = (mBoundingSphere.getCenter() - other_info.mBoundingSphere.getCenter()).length(); // LL_INFOS() << "objects are " << center_dist << "m apart" << LL_ENDL; 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 // LL_INFOS() << "span too large: " << span << " vs. " << span_limit << LL_ENDL; 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