llprimlinkinfo.h
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:11k
源码类别:

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file llprimlinkinfo.h
  3.  * @author andrew@lindenlab.com
  4.  * @brief A template for determining which prims in a set are linkable
  5.  *
  6.  * $LicenseInfo:firstyear=2007&license=viewergpl$
  7.  * 
  8.  * Copyright (c) 2007-2010, Linden Research, Inc.
  9.  * 
  10.  * Second Life Viewer Source Code
  11.  * The source code in this file ("Source Code") is provided by Linden Lab
  12.  * to you under the terms of the GNU General Public License, version 2.0
  13.  * ("GPL"), unless you have obtained a separate licensing agreement
  14.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  15.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  16.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  17.  * 
  18.  * There are special exceptions to the terms and conditions of the GPL as
  19.  * it is applied to this Source Code. View the full text of the exception
  20.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  21.  * online at
  22.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  23.  * 
  24.  * By copying, modifying or distributing this software, you acknowledge
  25.  * that you have read and understood your obligations described above,
  26.  * and agree to abide by those obligations.
  27.  * 
  28.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  29.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  30.  * COMPLETENESS OR PERFORMANCE.
  31.  * $/LicenseInfo$
  32.  */
  33. #ifndef LL_PRIM_LINK_INFO_H
  34. #define LL_PRIM_LINK_INFO_H
  35. // system includes
  36. #include <iostream>
  37. #include <map>
  38. #include <list>
  39. #include <vector>
  40. // common includes
  41. #include "stdtypes.h"
  42. #include "v3math.h"
  43. #include "llquaternion.h"
  44. #include "llsphere.h"
  45. const F32 MAX_OBJECT_SPAN = 54.f; // max distance from outside edge of an object to the farthest edge
  46. const F32 OBJECT_SPAN_BONUS = 2.f; // infinitesimally small prims can always link up to this distance
  47. const S32 MAX_PRIMS_PER_OBJECT = 256;
  48. template < typename DATA_TYPE >
  49. class LLPrimLinkInfo
  50. {
  51. public:
  52. LLPrimLinkInfo();
  53. LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere );
  54. ~LLPrimLinkInfo();
  55. void set( DATA_TYPE data, const LLSphere& sphere );
  56. void append( DATA_TYPE data, const LLSphere& sphere );
  57. void getData( std::list< DATA_TYPE >& data_list ) const;
  58. F32 getDiameter() const;
  59. LLVector3 getCenter() const;
  60. // returns 'true' if this info can link with other_info
  61. bool canLink( const LLPrimLinkInfo< DATA_TYPE >& other_info );
  62. S32 getPrimCount() const { return mDataMap.size(); }
  63. void mergeLinkableSet( typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );
  64. void transform(const LLVector3& position, const LLQuaternion& rotation);
  65. private:
  66. // returns number of merges made
  67. S32 merge(LLPrimLinkInfo< DATA_TYPE >& other_info);
  68. // returns number of collapses made
  69. static S32 collapse(typename std::list< LLPrimLinkInfo < DATA_TYPE > >& unlinked );
  70. void computeBoundingSphere();
  71. // Internal utility to encapsulate the link rules
  72. F32 get_max_linkable_span(const LLSphere& first, const LLSphere& second);
  73. F32 get_span(const LLSphere& first, const LLSphere& second);
  74. private:
  75. std::map< DATA_TYPE, LLSphere > mDataMap;
  76. LLSphere mBoundingSphere;
  77. };
  78. template < typename DATA_TYPE >
  79. LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo()
  80. : mBoundingSphere( LLVector3(0.f, 0.f, 0.f), 0.f )
  81. {
  82. }
  83. template < typename DATA_TYPE >
  84. LLPrimLinkInfo< DATA_TYPE >::LLPrimLinkInfo( DATA_TYPE data, const LLSphere& sphere)
  85. : mBoundingSphere(sphere)
  86. {
  87. mDataMap[data] = sphere;
  88. }
  89. template < typename DATA_TYPE >
  90. LLPrimLinkInfo< DATA_TYPE >::~LLPrimLinkInfo()
  91. {
  92. mDataMap.clear();
  93. }
  94. template < typename DATA_TYPE >
  95. void LLPrimLinkInfo< DATA_TYPE>::set( DATA_TYPE data, const LLSphere& sphere )
  96. {
  97. if (!mDataMap.empty())
  98. {
  99. mDataMap.clear();
  100. }
  101. mDataMap[data] = sphere;
  102. mBoundingSphere = sphere;
  103. }
  104. template < typename DATA_TYPE >
  105. void LLPrimLinkInfo< DATA_TYPE>::append( DATA_TYPE data, const LLSphere& sphere )
  106. {
  107. mDataMap[data] = sphere;
  108. if (!mBoundingSphere.contains(sphere))
  109. {
  110. computeBoundingSphere();
  111. }
  112. }
  113. template < typename DATA_TYPE >
  114. void LLPrimLinkInfo< DATA_TYPE >::getData( std::list< DATA_TYPE >& data_list) const
  115. {
  116. typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
  117. for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
  118. {
  119. data_list.push_back(map_itr->first);
  120. }
  121. }
  122. template < typename DATA_TYPE >
  123. F32 LLPrimLinkInfo< DATA_TYPE >::getDiameter() const
  124. return 2.f * mBoundingSphere.getRadius();
  125. }
  126. template < typename DATA_TYPE >
  127. LLVector3 LLPrimLinkInfo< DATA_TYPE >::getCenter() const
  128. return mBoundingSphere.getCenter(); 
  129. }
  130. template < typename DATA_TYPE >
  131. F32 LLPrimLinkInfo< DATA_TYPE >::get_max_linkable_span(const LLSphere& first, const LLSphere& second)
  132. {
  133. F32 max_span = 3.f * (first.getRadius() + second.getRadius()) + OBJECT_SPAN_BONUS;
  134. if (max_span > MAX_OBJECT_SPAN)
  135. {
  136. max_span = MAX_OBJECT_SPAN;
  137. }
  138. return max_span;
  139. }
  140. template < typename DATA_TYPE >
  141. F32 LLPrimLinkInfo< DATA_TYPE >::get_span(const LLSphere& first, const LLSphere& second)
  142. {
  143. F32 span = (first.getCenter() - second.getCenter()).length()
  144. + first.getRadius() + second.getRadius();
  145. return span;
  146. }
  147. // static
  148. // returns 'true' if this info can link with any part of other_info
  149. template < typename DATA_TYPE >
  150. bool LLPrimLinkInfo< DATA_TYPE >::canLink(const LLPrimLinkInfo& other_info)
  151. {
  152. F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);
  153. F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);
  154. if (span <= max_span)
  155. {
  156. // The entire other_info fits inside the max span.
  157. return TRUE;
  158. }
  159. else if (span > max_span + 2.f * other_info.mBoundingSphere.getRadius())
  160. {
  161. // there is no way any piece of other_info could link with this one
  162. return FALSE;
  163. }
  164. // there may be a piece of other_info that is linkable
  165. typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
  166. for (map_itr = other_info.mDataMap.begin(); map_itr != other_info.mDataMap.end(); ++map_itr)
  167. {
  168. const LLSphere& other_sphere = (*map_itr).second;
  169. max_span = get_max_linkable_span(mBoundingSphere, other_sphere);
  170. span = get_span(mBoundingSphere, other_sphere);
  171. if (span <= max_span)
  172. {
  173. // found one piece that is linkable
  174. return TRUE;
  175. }
  176. }
  177. return FALSE;
  178. }
  179. // merges elements of 'unlinked' 
  180. // returns number of links made (NOT final prim count, NOR linked prim count)
  181. // and removes any linkable infos from 'unlinked' 
  182. template < typename DATA_TYPE >
  183. void LLPrimLinkInfo< DATA_TYPE >::mergeLinkableSet(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
  184. {
  185. bool linked_something = true;
  186. while (linked_something)
  187. {
  188. linked_something = false;
  189. typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = unlinked.begin();
  190. while ( other_itr != unlinked.end()
  191.    && getPrimCount() < MAX_PRIMS_PER_OBJECT )
  192. {
  193. S32 merge_count = merge(*other_itr);
  194. if (merge_count > 0)
  195. {
  196. linked_something = true;
  197. }
  198. if (0 == (*other_itr).getPrimCount())
  199. {
  200. unlinked.erase(other_itr++);
  201. }
  202. else
  203. {
  204. ++other_itr;
  205. }
  206. }
  207. if (!linked_something
  208. && unlinked.size() > 1)
  209. {
  210. S32 collapse_count = collapse(unlinked);
  211. if (collapse_count > 0)
  212. {
  213. linked_something = true;
  214. }
  215. }
  216. }
  217. }
  218. // transforms all of the spheres into a new reference frame
  219. template < typename DATA_TYPE >
  220. void LLPrimLinkInfo< DATA_TYPE >::transform(const LLVector3& position, const LLQuaternion& rotation)
  221. {
  222. typename std::map< DATA_TYPE, LLSphere >::iterator map_itr;
  223. for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
  224. {
  225. (*map_itr).second.setCenter((*map_itr).second.getCenter() * rotation + position);
  226. }
  227. mBoundingSphere.setCenter(mBoundingSphere.getCenter() * rotation + position);
  228. }
  229. // private
  230. // returns number of links made
  231. template < typename DATA_TYPE >
  232. S32 LLPrimLinkInfo< DATA_TYPE >::merge(LLPrimLinkInfo& other_info)
  233. {
  234. S32 link_count = 0;
  235. // F32 other_radius = other_info.mBoundingSphere.getRadius();
  236. // other_info.computeBoundingSphere();
  237. // if ( other_radius != other_info.mBoundingSphere.getRadius() )
  238. // {
  239. // llinfos << "Other bounding sphere changed!!" << llendl;
  240. // }
  241. // F32 this_radius = mBoundingSphere.getRadius();
  242. // computeBoundingSphere();
  243. // if ( this_radius != mBoundingSphere.getRadius() )
  244. // {
  245. // llinfos << "This bounding sphere changed!!" << llendl;
  246. // }
  247. F32 max_span = get_max_linkable_span(mBoundingSphere, other_info.mBoundingSphere);
  248. //  F32 center_dist = (mBoundingSphere.getCenter() - other_info.mBoundingSphere.getCenter()).length();
  249. // llinfos << "objects are " << center_dist << "m apart" << llendl;
  250. F32 span = get_span(mBoundingSphere, other_info.mBoundingSphere);
  251. F32 span_limit = max_span + (2.f * other_info.mBoundingSphere.getRadius());
  252. if (span > span_limit)
  253. {
  254. // there is no way any piece of other_info could link with this one
  255. // llinfos << "span too large:  " << span << " vs. " << span_limit << llendl;
  256. return 0;
  257. }
  258. bool completely_linkable = (span <= max_span) ? true : false;
  259. typename std::map< DATA_TYPE, LLSphere >::iterator map_itr = other_info.mDataMap.begin();
  260. while (map_itr != other_info.mDataMap.end()
  261. && getPrimCount() < MAX_PRIMS_PER_OBJECT )
  262. {
  263. DATA_TYPE other_data = (*map_itr).first;
  264. LLSphere& other_sphere = (*map_itr).second;
  265. if (!completely_linkable)
  266. {
  267. max_span = get_max_linkable_span(mBoundingSphere, other_sphere);
  268. F32 span = get_span(mBoundingSphere, other_sphere);
  269. if (span > max_span)
  270. {
  271. ++map_itr;
  272. continue;
  273. }
  274. }
  275. mDataMap[other_data] = other_sphere;
  276. ++link_count;
  277. if (!mBoundingSphere.contains(other_sphere) )
  278. {
  279. computeBoundingSphere();
  280. }
  281. // remove from the other info
  282. other_info.mDataMap.erase(map_itr++);
  283. }
  284. if (link_count > 0 && other_info.getPrimCount() > 0)
  285. {
  286. other_info.computeBoundingSphere();
  287. }
  288. return link_count;
  289. }
  290. // links any linkable elements of unlinked
  291. template < typename DATA_TYPE >
  292. S32 LLPrimLinkInfo< DATA_TYPE >::collapse(std::list< LLPrimLinkInfo< DATA_TYPE > > & unlinked)
  293. S32 link_count = 0;
  294. bool linked_something = true;
  295. while (linked_something)
  296. {
  297. linked_something = false;
  298. typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator this_itr = unlinked.begin();
  299. typename std::list< LLPrimLinkInfo< DATA_TYPE > >::iterator other_itr = this_itr;
  300. ++other_itr;
  301. while ( other_itr != unlinked.end() )
  302.    
  303. {
  304. S32 merge_count = (*this_itr).merge(*other_itr);
  305. if (merge_count > 0)
  306. {
  307. linked_something = true;
  308. link_count += merge_count;
  309. }
  310. if (0 == (*other_itr).getPrimCount())
  311. {
  312. unlinked.erase(other_itr++);
  313. }
  314. else
  315. {
  316. ++other_itr;
  317. }
  318. }
  319. }
  320. return link_count;
  321. }
  322. template < typename DATA_TYPE >
  323. void LLPrimLinkInfo< DATA_TYPE >::computeBoundingSphere()
  324. std::vector< LLSphere > sphere_list;
  325. typename std::map< DATA_TYPE, LLSphere >::const_iterator map_itr;
  326. for (map_itr = mDataMap.begin(); map_itr != mDataMap.end(); ++map_itr)
  327. {
  328. sphere_list.push_back(map_itr->second);
  329. }
  330. mBoundingSphere = LLSphere::getBoundingSphere(sphere_list);
  331. }
  332. #endif