diff options
Diffstat (limited to 'indra/llprimitive/llprimlinkinfo.h')
| -rw-r--r-- | indra/llprimitive/llprimlinkinfo.h | 486 |
1 files changed, 243 insertions, 243 deletions
diff --git a/indra/llprimitive/llprimlinkinfo.h b/indra/llprimitive/llprimlinkinfo.h index bee25975f1..67e40fd5be 100644 --- a/indra/llprimitive/llprimlinkinfo.h +++ b/indra/llprimitive/llprimlinkinfo.h @@ -1,4 +1,4 @@ -/** +/** * @file llprimlinkinfo.h * @author andrew@lindenlab.com * @brief A template for determining which prims in a set are linkable @@ -6,21 +6,21 @@ * $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$ */ @@ -42,8 +42,8 @@ #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 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; @@ -51,125 +51,125 @@ template < typename DATA_TYPE > class LLPrimLinkInfo { public: - LLPrimLinkInfo(); - LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere ); - ~LLPrimLinkInfo(); + 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; + 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 ); + // returns 'true' if this info can link with other_info + bool canLink( const LLPrimLinkInfo< DATA_TYPE >& other_info ); - S32 getPrimCount() const { return mDataMap.size(); } + S32 getPrimCount() const { return mDataMap.size(); } - void mergeLinkableSet( typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked ); + void mergeLinkableSet( typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked ); - void transform(const LLVector3& position, const LLQuaternion& rotation); + void transform(const LLVector3& position, const LLQuaternion& rotation); private: - // returns number of merges made - S32 merge(LLPrimLinkInfo< DATA_TYPE >& other_info); + // 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 ); + // returns number of collapses made + static S32 collapse(typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked ); - void computeBoundingSphere(); + 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); + // 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; + 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 ) +: 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) +: mBoundingSphere(sphere) { - mDataMap[data] = sphere; + mDataMap[data] = sphere; } template < typename DATA_TYPE > LLPrimLinkInfo< DATA_TYPE >::~LLPrimLinkInfo() { - mDataMap.clear(); + 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; + 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(); - } + 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); - } + 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(); +{ + return 2.f * mBoundingSphere.getRadius(); } template < typename DATA_TYPE > LLVector3 LLPrimLinkInfo< DATA_TYPE >::getCenter() const -{ - return mBoundingSphere.getCenter(); +{ + 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; - } + 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; + 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; + F32 span = (first.getCenter() - second.getCenter()).length() + + first.getRadius() + second.getRadius(); + return span; } // static @@ -177,90 +177,90 @@ F32 LLPrimLinkInfo< DATA_TYPE >::get_span(const LLSphere& first, const LLSphere& 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; + 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' +// merges elements of 'unlinked' // returns number of links made (NOT final prim count, NOR linked prim count) -// and removes any linkable infos from 'unlinked' +// 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; - } - } - } + 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); + 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 @@ -268,124 +268,124 @@ void LLPrimLinkInfo< DATA_TYPE >::transform(const LLVector3& position, const LLQ 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; + 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; +{ + 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); +{ + 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); } |