00001
00024 #include "linden_common.h"
00025 #include "lltut.h"
00026 #include "llprimlinkinfo.h"
00027 #include "llrand.h"
00028
00029
00030
00031 void randomize_sphere(LLSphere& sphere, F32 center_range, F32 radius_range)
00032 {
00033 F32 radius = ll_frand(2.f * radius_range) - radius_range;
00034 LLVector3 center;
00035 for (S32 i=0; i<3; ++i)
00036 {
00037 center.mV[i] = ll_frand(2.f * center_range) - center_range;
00038 }
00039 sphere.setRadius(radius);
00040 sphere.setCenter(center);
00041 }
00042
00043
00044 void randomize_sphere(LLSphere& sphere, F32 center_range, F32 minimum_radius, F32 maximum_radius)
00045 {
00046 F32 radius = ll_frand(maximum_radius - minimum_radius) + minimum_radius;
00047 LLVector3 center;
00048 for (S32 i=0; i<3; ++i)
00049 {
00050 center.mV[i] = ll_frand(2.f * center_range) - center_range;
00051 }
00052 sphere.setRadius(radius);
00053 sphere.setCenter(center);
00054 }
00055
00056
00057 bool random_sort( const LLPrimLinkInfo< S32 >&, const LLPrimLinkInfo< S32 >& b)
00058 {
00059 return (ll_rand(64) < 32);
00060 }
00061
00062 namespace tut
00063 {
00064 struct linkable_data
00065 {
00066 LLPrimLinkInfo<S32> info;
00067 };
00068
00069 typedef test_group<linkable_data> linkable_test;
00070 typedef linkable_test::object linkable_object;
00071 tut::linkable_test wtf("prim linkability");
00072
00073 template<> template<>
00074 void linkable_object::test<1>()
00075 {
00076
00077
00078
00079 S32 number_of_tests = 100;
00080 for (S32 test = 0; test < number_of_tests; ++test)
00081 {
00082
00083 F32 first_radius = 0.f;
00084 F32 second_radius = 0.f;
00085
00086
00087
00088 F32 max_link_span = ll_frand(MAX_OBJECT_SPAN);
00089 if (max_link_span < OBJECT_SPAN_BONUS)
00090 {
00091 max_link_span += OBJECT_SPAN_BONUS;
00092 }
00093 LLVector3 first_center(
00094 ll_frand(2.f * max_link_span) - max_link_span,
00095 ll_frand(2.f * max_link_span) - max_link_span,
00096 ll_frand(2.f * max_link_span) - max_link_span);
00097
00098
00099
00100 LLVector3 direction(ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
00101 direction.normalize();
00102 F32 half_milimeter = 0.0005f;
00103 LLVector3 second_center;
00104
00105
00106
00107 {
00108 second_center = first_center + (OBJECT_SPAN_BONUS - half_milimeter) * direction;
00109 LLPrimLinkInfo<S32> first_info(0, LLSphere(first_center, first_radius) );
00110 LLPrimLinkInfo<S32> second_info(1, LLSphere(second_center, second_radius) );
00111 ensure("these nearby objects should link", first_info.canLink(second_info) );
00112 }
00113
00114
00115 {
00116 second_center = first_center + (OBJECT_SPAN_BONUS + half_milimeter) * direction;
00117 LLPrimLinkInfo<S32> first_info(0, LLSphere(first_center, first_radius) );
00118 LLPrimLinkInfo<S32> second_info(1, LLSphere(second_center, second_radius) );
00119 ensure("these nearby objects should NOT link", !first_info.canLink(second_info) );
00120 }
00121
00122
00123 {
00124 first_radius = 0.3f * ll_frand(max_link_span - OBJECT_SPAN_BONUS);
00125
00126
00127 second_radius = ((max_link_span - OBJECT_SPAN_BONUS) / 3.f) - first_radius;
00128 second_center = first_center + (max_link_span - first_radius - second_radius - half_milimeter) * direction;
00129
00130 LLPrimLinkInfo<S32> first_info(0, LLSphere(first_center, first_radius) );
00131 LLPrimLinkInfo<S32> second_info(1, LLSphere(second_center, second_radius) );
00132
00133 ensure("these objects should link", first_info.canLink(second_info) );
00134 }
00135
00136
00137 {
00138
00139 second_center += (2.f * half_milimeter) * direction;
00140 LLPrimLinkInfo<S32> first_info(0, LLSphere(first_center, first_radius) );
00141 LLPrimLinkInfo<S32> second_info(1, LLSphere(second_center, second_radius) );
00142
00143 ensure("these objects should NOT link", !first_info.canLink(second_info) );
00144 }
00145
00146
00147 {
00148 second_center = first_center + (MAX_OBJECT_SPAN + 2.f * half_milimeter) * direction;
00149 second_radius = 0.3f * MAX_OBJECT_SPAN;
00150 LLPrimLinkInfo<S32> first_info(0, LLSphere(first_center, first_radius) );
00151 LLPrimLinkInfo<S32> second_info(1, LLSphere(second_center, second_radius) );
00152 ensure("these objects should NOT link", !first_info.canLink(second_info) );
00153 }
00154
00155 }
00156 }
00157
00158 template<> template<>
00159 void linkable_object::test<2>()
00160 {
00161
00162
00163
00164
00165 F32 radius = 5.f;
00166 F32 spacing = 10.f;
00167
00168 LLVector3 line_direction(ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
00169 line_direction.normalize();
00170
00171 LLVector3 first_center(ll_frand(2.f * spacing) -spacing, ll_frand(2.f * spacing) - spacing, ll_frand(2.f * spacing) - spacing);
00172
00173 LLPrimLinkInfo<S32> infos[8];
00174
00175 for (S32 index = 0; index < 8; ++index)
00176 {
00177 LLVector3 center = first_center + ((F32)(index) * spacing) * line_direction;
00178 infos[index].set(index, LLSphere(center, radius));
00179 }
00180
00181
00182
00183 {
00184 LLPrimLinkInfo<S32> root_info = infos[0];
00185 std::list< LLPrimLinkInfo<S32> > info_list;
00186 info_list.push_back(infos[2]);
00187 root_info.mergeLinkableSet(info_list);
00188 S32 prim_count = root_info.getPrimCount();
00189 ensure_equals("0&2 prim count should be 2", prim_count, 2);
00190 ensure_equals("0&2 unlinkable list should have length 0", (S32) info_list.size(), 0);
00191 }
00192
00193
00194
00195 {
00196 LLPrimLinkInfo<S32> root_info = infos[0];
00197 std::list< LLPrimLinkInfo<S32> > info_list;
00198 info_list.push_back(infos[3]);
00199 root_info.mergeLinkableSet(info_list);
00200 S32 prim_count = root_info.getPrimCount();
00201 ensure_equals("0&4 prim count should be 1", prim_count, 1);
00202 ensure_equals("0&4 unlinkable list should have length 1", (S32) info_list.size(), 1);
00203 }
00204
00205
00206
00207
00208 {
00209 LLPrimLinkInfo<S32> root_info = infos[0];
00210 std::list< LLPrimLinkInfo<S32> > info_list;
00211 for (S32 index = 1; index < 5; ++index)
00212 {
00213 info_list.push_back(infos[index]);
00214 }
00215 root_info.mergeLinkableSet(info_list);
00216 S32 prim_count = root_info.getPrimCount();
00217 ensure_equals("01234 prim count should be 5", prim_count, 5);
00218 ensure_equals("01234 unlinkable list should have length 0", (S32) info_list.size(), 0);
00219 }
00220
00221
00222
00223 {
00224 LLPrimLinkInfo<S32> root_info = infos[0];
00225 std::list< LLPrimLinkInfo<S32> > info_list;
00226 for (S32 index = 4; index > 0; --index)
00227 {
00228 info_list.push_back(infos[index]);
00229 }
00230 root_info.mergeLinkableSet(info_list);
00231 S32 prim_count = root_info.getPrimCount();
00232 ensure_equals("04321 prim count should be 5", prim_count, 5);
00233 ensure_equals("04321 unlinkable list should have length 0", (S32) info_list.size(), 0);
00234 }
00235
00236
00237 {
00238 LLPrimLinkInfo<S32> root_info = infos[0];
00239 std::list< LLPrimLinkInfo<S32> > info_list;
00240 info_list.push_back(infos[1]);
00241 info_list.push_back(infos[4]);
00242 info_list.push_back(infos[2]);
00243 info_list.push_back(infos[3]);
00244 root_info.mergeLinkableSet(info_list);
00245 S32 prim_count = root_info.getPrimCount();
00246 ensure_equals("01423 prim count should be 5", prim_count, 5);
00247 ensure_equals("01423 unlinkable list should have length 0", (S32) info_list.size(), 0);
00248 }
00249
00250
00251 {
00252 LLPrimLinkInfo<S32> root_info = infos[0];
00253 std::list< LLPrimLinkInfo<S32> > info_list;
00254 for (S32 index = 1; index < 6; ++index)
00255 {
00256 info_list.push_back(infos[index]);
00257 }
00258 root_info.mergeLinkableSet(info_list);
00259 S32 prim_count = root_info.getPrimCount();
00260 ensure_equals("012345 prim count should be 5", prim_count, 5);
00261 ensure_equals("012345 unlinkable list should have length 1", (S32) info_list.size(), 1);
00262 std::list< LLPrimLinkInfo<S32> >::iterator info_itr = info_list.begin();
00263 if (info_itr != info_list.end())
00264 {
00265
00266 std::list<S32> unlinked_indecies;
00267 info_itr->getData(unlinked_indecies);
00268
00269 ensure_equals("012345 unlinkable index count should be 1", (S32) unlinked_indecies.size(), 1);
00270
00271 std::list<S32>::iterator unlinked_index_itr = unlinked_indecies.begin();
00272 S32 unlinkable_index = *unlinked_index_itr;
00273 ensure_equals("012345 unlinkable index should be 5", (S32) unlinkable_index, 5);
00274 }
00275 }
00276
00277
00278 {
00279 LLPrimLinkInfo<S32> root_info = infos[0];
00280 std::list< LLPrimLinkInfo<S32> > info_list;
00281 for (S32 index = 1; index < 8; ++index)
00282 {
00283 info_list.push_back(infos[index]);
00284 }
00285 root_info.mergeLinkableSet(info_list);
00286 S32 prim_count = root_info.getPrimCount();
00287 ensure_equals("01234567 prim count should be 5", prim_count, 5);
00288
00289 ensure_equals("01234567 unlinkable list should have length 1", (S32) info_list.size(), 1);
00290 std::list< LLPrimLinkInfo<S32> >::iterator info_itr = info_list.begin();
00291 if (info_itr != info_list.end())
00292 {
00293
00294 std::list<S32> unlinked_indecies;
00295 info_itr->getData(unlinked_indecies);
00296 ensure_equals("0123456 unlinkable index count should be 3", (S32) unlinked_indecies.size(), 3);
00297
00298
00299 std::list<S32>::iterator unlinked_index_itr = unlinked_indecies.begin();
00300 S32 unlinkable_index = *unlinked_index_itr;
00301 ensure_equals("0123456 first unlinkable index should be 5", (S32) unlinkable_index, 5);
00302 ++unlinked_index_itr;
00303 unlinkable_index = *unlinked_index_itr;
00304 ensure_equals("0123456 second unlinkable index should be 6", (S32) unlinkable_index, 6);
00305 ++unlinked_index_itr;
00306 unlinkable_index = *unlinked_index_itr;
00307 ensure_equals("0123456 third unlinkable index should be 7", (S32) unlinkable_index, 7);
00308
00309 }
00310 }
00311 }
00312
00313 template<> template<>
00314 void linkable_object::test<3>()
00315 {
00316
00317
00318 S32 number_of_tests = 5;
00319 for (S32 test = 0; test < number_of_tests; ++test)
00320 {
00321
00322 F32 first_radius = 1.f;
00323 F32 second_radius = 2.f;
00324 F32 third_radius = 3.f;
00325
00326
00327 F32 half_milimeter = 0.0005f;
00328 F32 max_first_second_span = 3.f * (first_radius + second_radius) + OBJECT_SPAN_BONUS;
00329 F32 linkable_distance = max_first_second_span - first_radius - second_radius - half_milimeter;
00330
00331 F32 max_full_span = 3.f * (0.5f * max_first_second_span + third_radius) + OBJECT_SPAN_BONUS;
00332 F32 unlinkable_distance = max_full_span - 0.5f * linkable_distance - third_radius + half_milimeter;
00333
00334
00335 LLVector3 first_direction(ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
00336 first_direction.normalize();
00337 LLVector3 second_direction(ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
00338 second_direction.normalize();
00339 LLVector3 third_direction(ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
00340 third_direction.normalize();
00341
00342
00343 LLVector3 first_center = ll_frand(10.f) * first_direction;
00344 LLVector3 second_center = first_center + ll_frand(linkable_distance) * second_direction;
00345 LLVector3 first_join_center = 0.5f * (first_center + second_center);
00346 LLVector3 third_center = first_join_center + unlinkable_distance * third_direction;
00347
00348
00349 {
00350
00351 S32 index = 0;
00352 LLPrimLinkInfo<S32> first_info(index++, LLSphere(first_center, first_radius));
00353 LLPrimLinkInfo<S32> second_info(index++, LLSphere(second_center, second_radius));
00354 LLPrimLinkInfo<S32> third_info(index++, LLSphere(third_center, third_radius));
00355
00356
00357 std::list< LLPrimLinkInfo<S32> > info_list;
00358 info_list.push_back(second_info);
00359 info_list.push_back(third_info);
00360
00361
00362 first_info.mergeLinkableSet(info_list);
00363 S32 prim_count = first_info.getPrimCount();
00364
00365 ensure_equals("prim count should be 2", prim_count, 2);
00366 ensure_equals("unlinkable list should have length 1", (S32) info_list.size(), 1);
00367 }
00368
00369
00370 {
00371
00372 S32 index = 0;
00373 LLPrimLinkInfo<S32> first_info(index++, LLSphere(first_center, first_radius));
00374 LLPrimLinkInfo<S32> second_info(index++, LLSphere(second_center, second_radius));
00375 LLPrimLinkInfo<S32> third_info(index++, LLSphere(third_center, third_radius));
00376
00377
00378 std::list< LLPrimLinkInfo<S32> > info_list;
00379 info_list.push_back(third_info);
00380 info_list.push_back(second_info);
00381
00382
00383 first_info.mergeLinkableSet(info_list);
00384 S32 prim_count = first_info.getPrimCount();
00385
00386 ensure_equals("prim count should be 2", prim_count, 2);
00387 ensure_equals("unlinkable list should have length 1", (S32) info_list.size(), 1);
00388 }
00389 }
00390 }
00391
00392 template<> template<>
00393 void linkable_object::test<4>()
00394 {
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412 F32 root_center_range = 0.f;
00413 F32 min_prim_radius = 0.1f;
00414 F32 max_prim_radius = 2.f;
00415
00416
00417
00418
00419 F32 child_center_range = 0.45f * ( (6*min_prim_radius) + OBJECT_SPAN_BONUS );
00420
00421 S32 number_of_tests = 100;
00422 S32 number_of_spheres = 10;
00423 S32 number_of_scrambles = 10;
00424 S32 number_of_random_bubble_sorts = 10;
00425
00426 for (S32 test = 0; test < number_of_tests; ++test)
00427 {
00428 LLSphere sphere;
00429 S32 sphere_index = 0;
00430
00431
00432 randomize_sphere(sphere, root_center_range, min_prim_radius, max_prim_radius);
00433 info.set( sphere_index++, sphere );
00434
00435
00436 std::list< LLPrimLinkInfo<S32> > info_list;
00437 for (; sphere_index < number_of_spheres; ++sphere_index)
00438 {
00439 randomize_sphere(sphere, child_center_range, min_prim_radius, max_prim_radius);
00440 LLPrimLinkInfo<S32> child_info( sphere_index, sphere );
00441 info_list.push_back(child_info);
00442 }
00443
00444
00445 std::list<S32> first_linked_list;
00446
00447 {
00448
00449
00450 LLPrimLinkInfo<S32> test_info( 0, LLSphere(info.getCenter(), 0.5f * info.getDiameter()) );
00451 std::list< LLPrimLinkInfo<S32> > test_list;
00452 test_list.assign(info_list.begin(), info_list.end());
00453
00454
00455 test_info.mergeLinkableSet(test_list);
00456
00457 ensure("All prims should link, but did not.",test_list.empty());
00458
00459
00460 test_info.getData(first_linked_list);
00461 first_linked_list.sort();
00462 }
00463
00464
00465 for (S32 scramble = 0; scramble < number_of_scrambles; ++scramble)
00466 {
00467 LLPrimLinkInfo<S32> test_info(0, LLSphere(info.getCenter(), 0.5f * info.getDiameter()) );
00468
00469
00470 std::list< LLPrimLinkInfo<S32> > test_list;
00471 test_list.assign(info_list.begin(), info_list.end());
00472 for (S32 i = 0; i < number_of_random_bubble_sorts; i++)
00473 {
00474 test_list.sort(random_sort);
00475 }
00476
00477
00478 test_info.mergeLinkableSet(test_list);
00479
00480
00481 std::list<S32> linked_list;
00482 test_info.getData(linked_list);
00483 linked_list.sort();
00484
00485 ensure_equals("linked set size should be order independent",linked_list.size(),first_linked_list.size());
00486 }
00487 }
00488 }
00489 }
00490