00001
00024 #ifndef LL_PRIM_LINK_INFO_H
00025 #define LL_PRIM_LINK_INFO_H
00026
00027
00028 #include <iostream>
00029 #include <map>
00030 #include <list>
00031 #include <vector>
00032
00033
00034 #include "stdtypes.h"
00035 #include "v3math.h"
00036 #include "llquaternion.h"
00037 #include "llsphere.h"
00038
00039
00040 const F32 MAX_OBJECT_SPAN = 54.f;
00041 const F32 OBJECT_SPAN_BONUS = 2.f;
00042 const S32 MAX_PRIMS_PER_OBJECT = 255;
00043
00044
00045 template < typename DATA_TYPE >
00046 class LLPrimLinkInfo
00047 {
00048 public:
00049 LLPrimLinkInfo();
00050 LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere );
00051 ~LLPrimLinkInfo();
00052
00053 void set( DATA_TYPE data, const LLSphere& sphere );
00054 void append( DATA_TYPE data, const LLSphere& sphere );
00055 void getData( std::list< DATA_TYPE >& data_list ) const;
00056 F32 getDiameter() const;
00057 LLVector3 getCenter() const;
00058
00059
00060 bool canLink( const LLPrimLinkInfo< DATA_TYPE >& other_info );
00061
00062 S32 getPrimCount() const { return mDataMap.size(); }
00063
00064 void mergeLinkableSet( typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );
00065
00066 void transform(const LLVector3& position, const LLQuaternion& rotation);
00067
00068 private:
00069
00070 S32 merge(LLPrimLinkInfo< DATA_TYPE >& other_info);
00071
00072
00073 static S32 collapse(typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );
00074
00075 void computeBoundingSphere();
00076
00077
00078 F32 get_max_linkable_span(const LLSphere& first, const LLSphere& second);
00079 F32 get_span(const LLSphere& first, const LLSphere& second);
00080
00081 private:
00082 std::map< DATA_TYPE, LLSphere > mDataMap;
00083 LLSphere mBoundingSphere;
00084 };
00085
00086
00087
00088 template < typename DATA_TYPE >
00089 LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo()
00090 : mBoundingSphere( LLVector3(0.f, 0.f, 0.f), 0.f )
00091 {
00092 }
00093
00094 template < typename DATA_TYPE >
00095 LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere)
00096 : mBoundingSphere(sphere)
00097 {
00098 mDataMap[data] = sphere;
00099 }
00100
00101 template < typename DATA_TYPE >
00102 LLPrimLinkInfo< DATA_TYPE >::~LLPrimLinkInfo()
00103 {
00104 mDataMap.clear();
00105 }
00106
00107 template < typename DATA_TYPE >
00108 void LLPrimLinkInfo< DATA_TYPE>::set( DATA_TYPE data, const LLSphere& sphere )
00109 {
00110 if (!mDataMap.empty())
00111 {
00112 mDataMap.clear();
00113 }
00114 mDataMap[data] = sphere;
00115 mBoundingSphere = sphere;
00116 }
00117
00118 template < typename DATA_TYPE >
00119 void LLPrimLinkInfo< DATA_TYPE>::append( DATA_TYPE data, const LLSphere& sphere )
00120 {
00121 mDataMap[data] = sphere;
00122 if (!mBoundingSphere.contains(sphere))
00123 {
00124 computeBoundingSphere();
00125 }
00126 }
00127
00128 template < typename DATA_TYPE >
00129 void LLPrimLinkInfo< DATA_TYPE >::getData( std::list< DATA_TYPE >& data_list) const
00130 {
00131 typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
00132 for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
00133 {
00134 data_list.push_back(map_itr->first);
00135 }
00136 }
00137
00138 template < typename DATA_TYPE >
00139 F32 LLPrimLinkInfo< DATA_TYPE >::getDiameter() const
00140 {
00141 return 2.f * mBoundingSphere.getRadius();
00142 }
00143
00144 template < typename DATA_TYPE >
00145 LLVector3 LLPrimLinkInfo< DATA_TYPE >::getCenter() const
00146 {
00147 return mBoundingSphere.getCenter();
00148 }
00149
00150 template < typename DATA_TYPE >
00151 F32 LLPrimLinkInfo< DATA_TYPE >::get_max_linkable_span(const LLSphere& first, const LLSphere& second)
00152 {
00153 F32 max_span = 3.f * (first.getRadius() + second.getRadius()) + OBJECT_SPAN_BONUS;
00154 if (max_span > MAX_OBJECT_SPAN)
00155 {
00156 max_span = MAX_OBJECT_SPAN;
00157 }
00158
00159 return max_span;
00160 }
00161
00162 template < typename DATA_TYPE >
00163 F32 LLPrimLinkInfo< DATA_TYPE >::get_span(const LLSphere& first, const LLSphere& second)
00164 {
00165 F32 span = (first.getCenter() - second.getCenter()).length()
00166 + first.getRadius() + second.getRadius();
00167 return span;
00168 }
00169
00170
00171
00172 template < typename DATA_TYPE >
00173 bool LLPrimLinkInfo< DATA_TYPE >::canLink(const LLPrimLinkInfo& other_info)
00174 {
00175 F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);
00176
00177 F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);
00178
00179 if (span <= max_span)
00180 {
00181
00182 return TRUE;
00183 }
00184 else if (span > max_span + 2.f * other_info.mBoundingSphere.getRadius())
00185 {
00186
00187 return FALSE;
00188 }
00189
00190
00191 typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
00192 for (map_itr = other_info.mDataMap.begin(); map_itr != other_info.mDataMap.end(); ++map_itr)
00193 {
00194 const LLSphere& other_sphere = (*map_itr).second;
00195 max_span = get_max_linkable_span(mBoundingSphere, other_sphere);
00196
00197 span = get_span(mBoundingSphere, other_sphere);
00198
00199 if (span <= max_span)
00200 {
00201
00202 return TRUE;
00203 }
00204 }
00205 return FALSE;
00206 }
00207
00208
00209
00210
00211 template < typename DATA_TYPE >
00212 void LLPrimLinkInfo< DATA_TYPE >::mergeLinkableSet(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
00213 {
00214 bool linked_something = true;
00215 while (linked_something)
00216 {
00217 linked_something = false;
00218
00219 typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = unlinked.begin();
00220 while ( other_itr != unlinked.end()
00221 && getPrimCount() < MAX_PRIMS_PER_OBJECT )
00222 {
00223 S32 merge_count = merge(*other_itr);
00224 if (merge_count > 0)
00225 {
00226 linked_something = true;
00227 }
00228 if (0 == (*other_itr).getPrimCount())
00229 {
00230 unlinked.erase(other_itr++);
00231 }
00232 else
00233 {
00234 ++other_itr;
00235 }
00236 }
00237 if (!linked_something
00238 && unlinked.size() > 1)
00239 {
00240 S32 collapse_count = collapse(unlinked);
00241 if (collapse_count > 0)
00242 {
00243 linked_something = true;
00244 }
00245 }
00246 }
00247 }
00248
00249
00250 template < typename DATA_TYPE >
00251 void LLPrimLinkInfo< DATA_TYPE >::transform(const LLVector3& position, const LLQuaternion& rotation)
00252 {
00253 typename std::map< DATA_TYPE, LLSphere >::iterator map_itr;
00254 for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
00255 {
00256 (*map_itr).second.setCenter((*map_itr).second.getCenter() * rotation + position);
00257 }
00258 mBoundingSphere.setCenter(mBoundingSphere.getCenter() * rotation + position);
00259 }
00260
00261
00262
00263 template < typename DATA_TYPE >
00264 S32 LLPrimLinkInfo< DATA_TYPE >::merge(LLPrimLinkInfo& other_info)
00265 {
00266 S32 link_count = 0;
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283 F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);
00284
00285
00286
00287 F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);
00288
00289 F32 span_limit = max_span + (2.f * other_info.mBoundingSphere.getRadius());
00290 if (span > span_limit)
00291 {
00292
00293
00294 return 0;
00295 }
00296
00297 bool completely_linkable = (span <= max_span) ? true : false;
00298
00299 typename std::map< DATA_TYPE, LLSphere >::iterator map_itr = other_info.mDataMap.begin();
00300 while (map_itr != other_info.mDataMap.end()
00301 && getPrimCount() < MAX_PRIMS_PER_OBJECT )
00302 {
00303 DATA_TYPE other_data = (*map_itr).first;
00304 LLSphere& other_sphere = (*map_itr).second;
00305
00306 if (!completely_linkable)
00307 {
00308 max_span = get_max_linkable_span(mBoundingSphere, other_sphere);
00309
00310 F32 span = get_span(mBoundingSphere, other_sphere);
00311
00312 if (span > max_span)
00313 {
00314 ++map_itr;
00315 continue;
00316 }
00317 }
00318
00319 mDataMap[other_data] = other_sphere;
00320 ++link_count;
00321
00322 if (!mBoundingSphere.contains(other_sphere) )
00323 {
00324 computeBoundingSphere();
00325 }
00326
00327
00328 other_info.mDataMap.erase(map_itr++);
00329 }
00330
00331 if (link_count > 0 && other_info.getPrimCount() > 0)
00332 {
00333 other_info.computeBoundingSphere();
00334 }
00335 return link_count;
00336 }
00337
00338
00339 template < typename DATA_TYPE >
00340 S32 LLPrimLinkInfo< DATA_TYPE >::collapse(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
00341 {
00342 S32 link_count = 0;
00343 bool linked_something = true;
00344 while (linked_something)
00345 {
00346 linked_something = false;
00347
00348 typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator this_itr = unlinked.begin();
00349 typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = this_itr;
00350 ++other_itr;
00351 while ( other_itr != unlinked.end() )
00352
00353 {
00354 S32 merge_count = (*this_itr).merge(*other_itr);
00355 if (merge_count > 0)
00356 {
00357 linked_something = true;
00358 link_count += merge_count;
00359 }
00360 if (0 == (*other_itr).getPrimCount())
00361 {
00362 unlinked.erase(other_itr++);
00363 }
00364 else
00365 {
00366 ++other_itr;
00367 }
00368 }
00369 }
00370 return link_count;
00371 }
00372
00373
00374 template < typename DATA_TYPE >
00375 void LLPrimLinkInfo< DATA_TYPE >::computeBoundingSphere()
00376 {
00377 std::vector< LLSphere > sphere_list;
00378 typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
00379 for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
00380 {
00381 sphere_list.push_back(map_itr->second);
00382 }
00383 mBoundingSphere = LLSphere::getBoundingSphere(sphere_list);
00384 }
00385
00386
00387 #endif
00388