1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#include "Private/UnitTests/BsUtilityTestSuite.h"
4#include "Private/UnitTests/BsFileSystemTestSuite.h"
5#include "Utility/BsOctree.h"
6#include "Utility/BsBitfield.h"
7#include "Utility/BsDynArray.h"
8#include "Math/BsComplex.h"
9#include "Utility/BsMinHeap.h"
10#include "Utility/BsQuadtree.h"
11#include "Utility/BsBitstream.h"
12#include "Utility/BsUSPtr.h"
13
14namespace bs
15{
16 struct DebugOctreeElem
17 {
18 AABox box;
19 mutable OctreeElementId octreeId;
20 };
21
22 struct DebugOctreeData
23 {
24 Vector<DebugOctreeElem> elements;
25 };
26
27 struct DebugOctreeOptions
28 {
29 enum { LoosePadding = 16 };
30 enum { MinElementsPerNode = 8 };
31 enum { MaxElementsPerNode = 16 };
32 enum { MaxDepth = 12};
33
34 static simd::AABox getBounds(UINT32 elem, void* context)
35 {
36 DebugOctreeData* octreeData = (DebugOctreeData*)context;
37 return simd::AABox(octreeData->elements[elem].box);
38 }
39
40 static void setElementId(UINT32 elem, const OctreeElementId& id, void* context)
41 {
42 DebugOctreeData* octreeData = (DebugOctreeData*)context;
43 octreeData->elements[elem].octreeId = id;
44 }
45 };
46
47 typedef Octree<UINT32, DebugOctreeOptions> DebugOctree;
48
49 struct DebugQuadtreeElem
50 {
51 Rect2 box;
52 mutable QuadtreeElementId quadtreeId;
53 };
54
55 struct DebugQuadtreeData
56 {
57 Vector<DebugQuadtreeElem> elements;
58 };
59
60 struct DebugQuadtreeOptions
61 {
62 enum { LoosePadding = 8 };
63 enum { MinElementsPerNode = 4 };
64 enum { MaxElementsPerNode = 8 };
65 enum { MaxDepth = 6 };
66
67 static simd::Rect2 getBounds(UINT32 elem, void* context)
68 {
69 DebugQuadtreeData* quadtreeData = (DebugQuadtreeData*)context;
70 return simd::Rect2(quadtreeData->elements[elem].box);
71 }
72
73 static void setElementId(UINT32 elem, const QuadtreeElementId& id, void* context)
74 {
75 DebugQuadtreeData* quadtreeData = (DebugQuadtreeData*)context;
76 quadtreeData->elements[elem].quadtreeId = id;
77 }
78 };
79
80 typedef Quadtree<UINT32, DebugQuadtreeOptions> DebugQuadtree;
81 void UtilityTestSuite::startUp()
82 {
83 SPtr<TestSuite> fileSystemTests = create<FileSystemTestSuite>();
84 add(fileSystemTests);
85 }
86
87 void UtilityTestSuite::shutDown()
88 {
89 }
90
91 UtilityTestSuite::UtilityTestSuite()
92 {
93 BS_ADD_TEST(UtilityTestSuite::testOctree);
94 BS_ADD_TEST(UtilityTestSuite::testBitfield)
95 BS_ADD_TEST(UtilityTestSuite::testSmallVector)
96 BS_ADD_TEST(UtilityTestSuite::testDynArray)
97 BS_ADD_TEST(UtilityTestSuite::testComplex)
98 BS_ADD_TEST(UtilityTestSuite::testMinHeap)
99 BS_ADD_TEST(UtilityTestSuite::testQuadtree)
100 BS_ADD_TEST(UtilityTestSuite::testVarInt)
101 BS_ADD_TEST(UtilityTestSuite::testBitStream)
102 }
103
104 void UtilityTestSuite::testBitfield()
105 {
106 static constexpr UINT32 COUNT = 100;
107 static constexpr UINT32 EXTRA_COUNT = 32;
108
109 Bitfield bitfield(true, COUNT);
110
111 // Basic iteration
112 UINT32 i = 0;
113 for (auto iter : bitfield)
114 {
115 BS_TEST_ASSERT(iter == true)
116 i++;
117 }
118
119 UINT32 curCount = COUNT;
120 BS_TEST_ASSERT(i == curCount);
121
122 // Dynamic additon
123 bitfield.add(false);
124 bitfield.add(false);
125 bitfield.add(true);
126 bitfield.add(false);
127 curCount += 4;
128
129 // Realloc
130 curCount += EXTRA_COUNT;
131 for (uint32_t j = 0; j < 32; j++)
132 bitfield.add(false);
133
134 BS_TEST_ASSERT(bitfield.size() == curCount);
135
136 BS_TEST_ASSERT(bitfield[COUNT + 0] == false);
137 BS_TEST_ASSERT(bitfield[COUNT + 1] == false);
138 BS_TEST_ASSERT(bitfield[COUNT + 2] == true);
139 BS_TEST_ASSERT(bitfield[COUNT + 3] == false);
140
141 // Modify during iteration
142 i = 0;
143 for (auto iter : bitfield)
144 {
145 if (i >= 50 && i <= 70)
146 iter = false;
147
148 i++;
149 }
150
151 // Modify directly using []
152 bitfield[5] = false;
153 bitfield[6] = false;
154
155 for (UINT32 j = 50; j < 70; j++)
156 BS_TEST_ASSERT(bitfield[j] == false);
157
158 BS_TEST_ASSERT(bitfield[5] == false);
159 BS_TEST_ASSERT(bitfield[6] == false);
160
161 // Removal
162 bitfield.remove(10);
163 bitfield.remove(10);
164 curCount -= 2;
165
166 for (UINT32 j = 48; j < 68; j++)
167 BS_TEST_ASSERT(bitfield[j] == false);
168
169 BS_TEST_ASSERT(bitfield[5] == false);
170 BS_TEST_ASSERT(bitfield[6] == false);
171
172 BS_TEST_ASSERT(bitfield.size() == curCount);
173
174 // Find
175 BS_TEST_ASSERT(bitfield.find(true) == 0);
176 BS_TEST_ASSERT(bitfield.find(false) == 5);
177 }
178
179 void UtilityTestSuite::testOctree()
180 {
181 DebugOctreeData octreeData;
182 DebugOctree octree(Vector3::ZERO, 800.0f, &octreeData);
183
184 struct SizeAndCount
185 {
186 float sizeMin;
187 float sizeMax;
188 UINT32 count;
189 };
190
191 SizeAndCount types[]
192 {
193 { 0.02f, 0.2f, 2000 }, // Very small objects
194 { 0.2f, 1.0f, 2000 }, // Small objects
195 { 1.0f, 5.0f, 5000 }, // Medium sized objects
196 { 5.0f, 30.0f, 4000 }, // Large objects
197 { 30.0f, 100.0f, 2000 } // Very large objects
198 };
199
200 float placementExtents = 750.0f;
201 for(UINT32 i = 0; i < sizeof(types)/sizeof(types[0]); i++)
202 {
203 for (UINT32 j = 0; j < types[i].count; j++)
204 {
205 Vector3 position(
206 ((rand() / (float)RAND_MAX) * 2.0f - 1.0f) * placementExtents,
207 ((rand() / (float)RAND_MAX) * 2.0f - 1.0f) * placementExtents,
208 ((rand() / (float)RAND_MAX) * 2.0f - 1.0f) * placementExtents
209 );
210
211 Vector3 extents(
212 types[i].sizeMin + ((rand() / (float)RAND_MAX)) * (types[i].sizeMax - types[i].sizeMin) * 0.5f,
213 types[i].sizeMin + ((rand() / (float)RAND_MAX)) * (types[i].sizeMax - types[i].sizeMin) * 0.5f,
214 types[i].sizeMin + ((rand() / (float)RAND_MAX)) * (types[i].sizeMax - types[i].sizeMin) * 0.5f
215 );
216
217 DebugOctreeElem elem;
218 elem.box = AABox(position - extents, position + extents);
219
220 UINT32 elemIdx = (UINT32)octreeData.elements.size();
221 octreeData.elements.push_back(elem);
222 octree.addElement(elemIdx);
223 }
224 }
225
226 DebugOctreeElem manualElems[3];
227 manualElems[0].box = AABox(Vector3(100.0f, 100.0f, 100.f), Vector3(110.0f, 115.0f, 110.0f));
228 manualElems[1].box = AABox(Vector3(200.0f, 100.0f, 100.f), Vector3(250.0f, 150.0f, 150.0f));
229 manualElems[2].box = AABox(Vector3(90.0f, 90.0f, 90.f), Vector3(105.0f, 105.0f, 110.0f));
230
231
232 for(UINT32 i = 0; i < 3; i++)
233 {
234 UINT32 elemIdx = (UINT32)octreeData.elements.size();
235 octreeData.elements.push_back(manualElems[i]);
236 octree.addElement(elemIdx);
237 }
238
239 AABox queryBounds = manualElems[0].box;
240 DebugOctree::BoxIntersectIterator interIter(octree, queryBounds);
241
242 Vector<UINT32> overlapElements;
243 while(interIter.moveNext())
244 {
245 UINT32 element = interIter.getElement();
246 overlapElements.push_back(element);
247
248 // Manually check for intersections
249 BS_TEST_ASSERT(octreeData.elements[element].box.intersects(queryBounds));
250 }
251
252 // Ensure that all we have found all possible overlaps by manually testing all elements
253 UINT32 elemIdx = 0;
254 for(auto& entry : octreeData.elements)
255 {
256 if(entry.box.intersects(queryBounds))
257 {
258 auto iterFind = std::find(overlapElements.begin(), overlapElements.end(), elemIdx);
259 BS_TEST_ASSERT(iterFind != overlapElements.end());
260 }
261
262 elemIdx++;
263 }
264
265 // Ensure nothing goes wrong during element removal
266 for(auto& entry : octreeData.elements)
267 octree.removeElement(entry.octreeId);
268 }
269
270 void UtilityTestSuite::testSmallVector()
271 {
272 struct SomeElem
273 {
274 int a = 10;
275 int b = 0;
276 };
277
278 // Make sure initial construction works
279 SmallVector<SomeElem, 4> v(4);
280 BS_TEST_ASSERT(v.size() == 4);
281 BS_TEST_ASSERT(v.capacity() == 4);
282 BS_TEST_ASSERT(v[0].a == 10);
283 BS_TEST_ASSERT(v[3].a == 10);
284 BS_TEST_ASSERT(v[3].b == 0);
285
286 // Making the vector dynamic
287 v.add({3, 4});
288 BS_TEST_ASSERT(v.size() == 5);
289 BS_TEST_ASSERT(v[0].a == 10);
290 BS_TEST_ASSERT(v[3].a == 10);
291 BS_TEST_ASSERT(v[3].b == 0);
292 BS_TEST_ASSERT(v[4].a == 3);
293 BS_TEST_ASSERT(v[4].b == 4);
294
295 // Make a copy
296 SmallVector<SomeElem, 4> v2 = v;
297 BS_TEST_ASSERT(v2.size() == 5);
298 BS_TEST_ASSERT(v2[0].a == 10);
299 BS_TEST_ASSERT(v2[3].a == 10);
300 BS_TEST_ASSERT(v2[3].b == 0);
301 BS_TEST_ASSERT(v2[4].a == 3);
302 BS_TEST_ASSERT(v2[4].b == 4);
303
304 // Pop an element
305 v2.pop();
306 BS_TEST_ASSERT(v2.size() == 4);
307 BS_TEST_ASSERT(v2[0].a == 10);
308 BS_TEST_ASSERT(v2[3].a == 10);
309 BS_TEST_ASSERT(v2[3].b == 0);
310
311 // Make a static only copy
312 SmallVector<SomeElem, 4> v3 = v2;
313 BS_TEST_ASSERT(v3.size() == 4);
314 BS_TEST_ASSERT(v3.capacity() == 4);
315 BS_TEST_ASSERT(v3[0].a == 10);
316 BS_TEST_ASSERT(v3[3].a == 10);
317 BS_TEST_ASSERT(v3[3].b == 0);
318
319 // Remove an element
320 v.remove(2);
321 BS_TEST_ASSERT(v.size() == 4);
322 BS_TEST_ASSERT(v[0].a == 10);
323 BS_TEST_ASSERT(v[2].a == 10);
324 BS_TEST_ASSERT(v[3].a == 3);
325 BS_TEST_ASSERT(v[3].b == 4);
326
327 // Move a static vector
328 SmallVector<SomeElem, 4> v4 = std::move(v3);
329 BS_TEST_ASSERT(v3.size() == 0);
330 BS_TEST_ASSERT(v4.size() == 4);
331 BS_TEST_ASSERT(v4.capacity() == 4);
332 BS_TEST_ASSERT(v4[0].a == 10);
333 BS_TEST_ASSERT(v4[3].a == 10);
334 BS_TEST_ASSERT(v4[3].b == 0);
335
336 // Move a dynamic vector
337 SmallVector<SomeElem, 4> v5 = std::move(v2);
338 BS_TEST_ASSERT(v2.size() == 0);
339 BS_TEST_ASSERT(v5.size() == 4);
340 BS_TEST_ASSERT(v5[0].a == 10);
341 BS_TEST_ASSERT(v5[3].a == 10);
342 BS_TEST_ASSERT(v5[3].b == 0);
343
344 // Move a dynamic vector into a dynamic vector
345 v.add({33, 44});
346 SmallVector<SomeElem, 4> v6 = std::move(v);
347 BS_TEST_ASSERT(v.size() == 0);
348 BS_TEST_ASSERT(v6.size() == 5);
349 BS_TEST_ASSERT(v6[0].a == 10);
350 BS_TEST_ASSERT(v6[3].a == 3);
351 BS_TEST_ASSERT(v6[3].b == 4);
352 BS_TEST_ASSERT(v6[4].a == 33);
353 BS_TEST_ASSERT(v6[4].b == 44);
354 }
355
356 void UtilityTestSuite::testDynArray()
357 {
358 struct SomeElem
359 {
360 int a = 10;
361 int b = 0;
362 };
363
364 // Make sure initial construction works
365 DynArray<SomeElem> v(4);
366 BS_TEST_ASSERT(v.size() == 4);
367 BS_TEST_ASSERT(v.capacity() == 4);
368 BS_TEST_ASSERT(v[0].a == 10);
369 BS_TEST_ASSERT(v[3].a == 10);
370 BS_TEST_ASSERT(v[3].b == 0);
371
372 // Add an element
373 v.add({3, 4});
374 BS_TEST_ASSERT(v.size() == 5);
375 BS_TEST_ASSERT(v[0].a == 10);
376 BS_TEST_ASSERT(v[3].a == 10);
377 BS_TEST_ASSERT(v[3].b == 0);
378 BS_TEST_ASSERT(v[4].a == 3);
379 BS_TEST_ASSERT(v[4].b == 4);
380
381 // Make a copy
382 DynArray<SomeElem> v2 = v;
383 BS_TEST_ASSERT(v2.size() == 5);
384 BS_TEST_ASSERT(v2[0].a == 10);
385 BS_TEST_ASSERT(v2[3].a == 10);
386 BS_TEST_ASSERT(v2[3].b == 0);
387 BS_TEST_ASSERT(v2[4].a == 3);
388 BS_TEST_ASSERT(v2[4].b == 4);
389
390 // Pop an element
391 v2.pop();
392 BS_TEST_ASSERT(v2.size() == 4);
393 BS_TEST_ASSERT(v2[0].a == 10);
394 BS_TEST_ASSERT(v2[3].a == 10);
395 BS_TEST_ASSERT(v2[3].b == 0);
396
397 // Remove an element
398 v.remove(2);
399 BS_TEST_ASSERT(v.size() == 4);
400 BS_TEST_ASSERT(v[0].a == 10);
401 BS_TEST_ASSERT(v[2].a == 10);
402 BS_TEST_ASSERT(v[3].a == 3);
403 BS_TEST_ASSERT(v[3].b == 4);
404
405 // Insert an element
406 v.insert(v.begin() + 2, { 99, 100 });
407 BS_TEST_ASSERT(v.size() == 5);
408 BS_TEST_ASSERT(v[0].a == 10);
409 BS_TEST_ASSERT(v[2].a == 99);
410 BS_TEST_ASSERT(v[3].a == 10);
411 BS_TEST_ASSERT(v[4].a == 3);
412 BS_TEST_ASSERT(v[4].b == 4);
413
414 // Insert a list
415 v.insert(v.begin() + 1, {{ 55, 100 }, { 56, 100 }, { 57, 100 }});
416 BS_TEST_ASSERT(v.size() == 8);
417 BS_TEST_ASSERT(v[0].a == 10);
418 BS_TEST_ASSERT(v[1].a == 55);
419 BS_TEST_ASSERT(v[2].a == 56);
420 BS_TEST_ASSERT(v[3].a == 57);
421 BS_TEST_ASSERT(v[4].a == 10);
422 BS_TEST_ASSERT(v[5].a == 99);
423 BS_TEST_ASSERT(v[6].a == 10);
424 BS_TEST_ASSERT(v[7].a == 3);
425 BS_TEST_ASSERT(v[7].b == 4);
426
427 // Erase a range of elements
428 v.erase(v.begin() + 2, v.begin() + 5);
429 BS_TEST_ASSERT(v.size() == 5);
430 BS_TEST_ASSERT(v[0].a == 10);
431 BS_TEST_ASSERT(v[1].a == 55);
432 BS_TEST_ASSERT(v[2].a == 99);
433 BS_TEST_ASSERT(v[3].a == 10);
434 BS_TEST_ASSERT(v[4].a == 3);
435 BS_TEST_ASSERT(v[4].b == 4);
436
437 // Insert a range
438 v.insert(v.begin() + 1, v2.begin() + 1, v2.begin() + 3);
439 BS_TEST_ASSERT(v.size() == 7);
440 BS_TEST_ASSERT(v[0].a == 10);
441 BS_TEST_ASSERT(v[1].a == 10);
442 BS_TEST_ASSERT(v[2].a == 10);
443 BS_TEST_ASSERT(v[3].a == 55);
444 BS_TEST_ASSERT(v[4].a == 99);
445 BS_TEST_ASSERT(v[5].a == 10);
446 BS_TEST_ASSERT(v[6].a == 3);
447 BS_TEST_ASSERT(v[6].b == 4);
448
449 // Shrink capacity
450 v.shrink();
451 BS_TEST_ASSERT(v.size() == v.capacity());
452 BS_TEST_ASSERT(v[0].a == 10);
453 BS_TEST_ASSERT(v[1].a == 10);
454 BS_TEST_ASSERT(v[2].a == 10);
455 BS_TEST_ASSERT(v[3].a == 55);
456 BS_TEST_ASSERT(v[4].a == 99);
457 BS_TEST_ASSERT(v[5].a == 10);
458 BS_TEST_ASSERT(v[6].a == 3);
459 BS_TEST_ASSERT(v[6].b == 4);
460
461 // Move it
462 DynArray<SomeElem> v3 = std::move(v2);
463 BS_TEST_ASSERT(v2.size() == 0);
464 BS_TEST_ASSERT(v3.size() == 4);
465 BS_TEST_ASSERT(v3[0].a == 10);
466 BS_TEST_ASSERT(v3[3].a == 10);
467 BS_TEST_ASSERT(v3[3].b == 0);
468 }
469
470 void UtilityTestSuite::testComplex()
471 {
472 Complex<float> c(10.0, 4.0);
473 BS_TEST_ASSERT(c.real() == 10.0);
474 BS_TEST_ASSERT(c.imag() == 4.0);
475
476 Complex<float> c2(15.0, 5.0);
477 BS_TEST_ASSERT(c2.real() == 15.0);
478 BS_TEST_ASSERT(c2.imag() == 5.0);
479
480 Complex<float> c3 = c + c2;
481 BS_TEST_ASSERT(c3.real() == 25.0);
482 BS_TEST_ASSERT(c3.imag() == 9.0);
483
484 Complex<float> c4 = c - c2;
485 BS_TEST_ASSERT(c4.real() == -5.0);
486 BS_TEST_ASSERT(c4.imag() == -1.0);
487
488 Complex<float> c5 = c * c2;
489 BS_TEST_ASSERT(c5.real() == 130.0);
490 BS_TEST_ASSERT(c5.imag() == 110.0);
491
492 Complex<float> c6 = c / c2;
493 BS_TEST_ASSERT(c6.real() == 0.680000007f);
494 BS_TEST_ASSERT(c6.imag() == 0.0399999991f);
495
496 BS_TEST_ASSERT(Complex<float>::abs(c) == 10.7703295f);
497 BS_TEST_ASSERT(Complex<float>::arg(c) == 0.380506366f);
498 BS_TEST_ASSERT(Complex<float>::norm(c) == 116);
499
500 Complex<float> c7 = Complex<float>::conj(c);
501 BS_TEST_ASSERT(c7.real() == 10);
502 BS_TEST_ASSERT(c7.imag() == -4);
503 c7 = 0;
504
505 c7 = Complex<float>::polar(2.0, 0.5);
506 BS_TEST_ASSERT(c7.real() == 1.75516510f);
507 BS_TEST_ASSERT(c7.imag() == 0.958851099f);
508 c7 = 0;
509
510 c7 = Complex<float>::cos(c);
511 BS_TEST_ASSERT(c7.real() == -22.9135609f);
512 BS_TEST_ASSERT(c7.imag() == 14.8462915f);
513 c7 = 0;
514
515 c7 = Complex<float>::cosh(c);
516 BS_TEST_ASSERT(c7.real() == -7198.72949f);
517 BS_TEST_ASSERT(c7.imag() == -8334.84180f);
518 c7 = 0;
519
520 c7 = Complex<float>::exp(c);
521 BS_TEST_ASSERT(c7.real() == -14397.4580f);
522 BS_TEST_ASSERT(c7.imag() == -16669.6836f);
523 c7 = 0;
524
525 c7 = Complex<float>::log(c);
526 BS_TEST_ASSERT(c7.real() == 2.37679505f);
527 BS_TEST_ASSERT(c7.imag() == 0.380506366f);
528 c7 = 0;
529
530 c7 = Complex<float>::pow(c, 2.0);
531 BS_TEST_ASSERT(c7.real() == 84.0000000f);
532 BS_TEST_ASSERT(c7.imag() == 79.9999924f);
533 c7 = 0;
534
535 c7 = Complex<float>::sin(c);
536 BS_TEST_ASSERT(c7.real() == -14.8562555f);
537 BS_TEST_ASSERT(c7.imag() == -22.8981915f);
538 c7 = 0;
539
540 c7 = Complex<float>::sinh(c);
541 BS_TEST_ASSERT(c7.real() == -7198.72900f);
542 BS_TEST_ASSERT(c7.imag() == -8334.84277f);
543 c7 = 0;
544
545 c7 = Complex<float>::sqrt(c);
546 BS_TEST_ASSERT(c7.real() == 3.22260213f);
547 BS_TEST_ASSERT(c7.imag() == 0.620616496f);
548 c7 = 0;
549 }
550
551 void UtilityTestSuite::testMinHeap()
552 {
553 struct SomeElem
554 {
555 int a;
556 int b;
557 };
558
559 MinHeap<SomeElem, int> m;
560 m.resize(8);
561 BS_TEST_ASSERT(m.valid() == true);
562
563 SomeElem elements;
564 elements.a = 4;
565 elements.b = 5;
566
567 m.insert(elements, 10);
568 BS_TEST_ASSERT(m[0].key.a == 4);
569 BS_TEST_ASSERT(m[0].key.b == 5);
570 BS_TEST_ASSERT(m[0].value == 10);
571 BS_TEST_ASSERT(m.size() == 1);
572
573 int v = 11;
574 m.insert(elements, v);
575 BS_TEST_ASSERT(m[1].key.a == 4);
576 BS_TEST_ASSERT(m[1].key.b == 5);
577 BS_TEST_ASSERT(m[1].value == 11);
578 BS_TEST_ASSERT(m.size() == 2);
579
580 SomeElem minKey;
581 int minValue;
582
583 m.minimum(minKey, minValue);
584 BS_TEST_ASSERT(minKey.a == 4);
585 BS_TEST_ASSERT(minKey.b == 5);
586 BS_TEST_ASSERT(minValue == 10);
587
588 m.erase(elements, v);
589 BS_TEST_ASSERT(m.size() == 1);
590 }
591
592 void UtilityTestSuite::testQuadtree()
593 {
594 DebugQuadtreeData quadtreeData;
595 DebugQuadtree quadtree(Vector2(0, 0), 800.0f, &quadtreeData);
596
597 struct SizeAndCount
598 {
599 float sizeMin;
600 float sizeMax;
601 UINT32 count;
602 };
603
604 SizeAndCount types[]
605 {
606 { 0.02f, 0.2f, 2000 }, // Very small objects
607 { 0.2f, 1.0f, 2000 }, // Small objects
608 { 1.0f, 5.0f, 5000 }, // Medium sized objects
609 { 5.0f, 30.0f, 4000 }, // Large objects
610 { 30.0f, 100.0f, 2000 } // Very large objects
611 };
612
613 float placementExtents = 750.0f;
614 for (UINT32 i = 0; i < sizeof(types) / sizeof(types[0]); i++)
615 {
616 for (UINT32 j = 0; j < types[i].count; j++)
617 {
618 Vector2 position(
619 ((rand() / (float)RAND_MAX) * 2.0f - 1.0f) * placementExtents,
620 ((rand() / (float)RAND_MAX) * 2.0f - 1.0f) * placementExtents
621 );
622
623 Vector2 extents(
624 types[i].sizeMin + ((rand() / (float)RAND_MAX)) * (types[i].sizeMax - types[i].sizeMin) * 0.5f,
625 types[i].sizeMin + ((rand() / (float)RAND_MAX)) * (types[i].sizeMax - types[i].sizeMin) * 0.5f
626 );
627
628 DebugQuadtreeElem elem;
629 elem.box = Rect2(position - extents, extents);
630
631 UINT32 elemIdx = (UINT32)quadtreeData.elements.size();
632 quadtreeData.elements.push_back(elem);
633 quadtree.addElement(elemIdx);
634 }
635 }
636
637 DebugQuadtreeElem manualElems[3];
638 manualElems[0].box = Rect2(Vector2(100.0f, 100.0f), Vector2(110.0f, 115.0f));
639 manualElems[1].box = Rect2(Vector2(200.0f, 100.0f), Vector2(250.0f, 150.0f));
640 manualElems[2].box = Rect2(Vector2(90.0f, 90.0f), Vector2(105.0f, 105.0f));
641
642
643 for (UINT32 i = 0; i < 3; i++)
644 {
645 UINT32 elemIdx = (UINT32)quadtreeData.elements.size();
646 quadtreeData.elements.push_back(manualElems[i]);
647 quadtree.addElement(elemIdx);
648 }
649
650 Rect2 queryBounds = manualElems[0].box;
651 DebugQuadtree::BoxIntersectIterator interIter(quadtree, queryBounds);
652
653 Vector<UINT32> overlapElements;
654 while (interIter.moveNext())
655 {
656 UINT32 element = interIter.getElement();
657 overlapElements.push_back(element);
658
659 // Manually check for intersections
660 assert(quadtreeData.elements[element].box.overlaps(queryBounds));
661 }
662
663 // Ensure that all we have found all possible overlaps by manually testing all elements
664 UINT32 elemIdx = 0;
665 for (auto& entry : quadtreeData.elements)
666 {
667 if (entry.box.overlaps(queryBounds))
668 {
669 auto iterFind = std::find(overlapElements.begin(), overlapElements.end(), elemIdx);
670 assert(iterFind != overlapElements.end());
671 }
672
673 elemIdx++;
674 }
675
676 // Ensure nothing goes wrong during element removal
677 for (auto& entry : quadtreeData.elements)
678 quadtree.removeElement(entry.quadtreeId);
679 }
680
681 void UtilityTestSuite::testVarInt()
682 {
683 UINT32 u0 = 0;
684 UINT32 u1 = 127;
685 UINT32 u2 = 255;
686 UINT32 u3 = 123456;
687
688 INT32 i0 = 0;
689 INT32 i1 = 127;
690 INT32 i2 = -1;
691 INT32 i3 = -123456;
692 INT32 i4 = 123456;
693
694 UINT8 output[50];
695
696 UINT32 writeIdx = Bitwise::encodeVarInt(u0, output);
697 BS_TEST_ASSERT(writeIdx == 1);
698
699 writeIdx += Bitwise::encodeVarInt(u1, output + writeIdx);
700 BS_TEST_ASSERT(writeIdx == 2);
701
702 writeIdx += Bitwise::encodeVarInt(u2, output + writeIdx);
703 BS_TEST_ASSERT(writeIdx == 4);
704
705 writeIdx += Bitwise::encodeVarInt(u3, output + writeIdx);
706
707 writeIdx += Bitwise::encodeVarInt(i0, output + writeIdx);
708 writeIdx += Bitwise::encodeVarInt(i1, output + writeIdx);
709 writeIdx += Bitwise::encodeVarInt(i2, output + writeIdx);
710 writeIdx += Bitwise::encodeVarInt(i3, output + writeIdx);
711 writeIdx += Bitwise::encodeVarInt(i4, output + writeIdx);
712
713 UINT32 readIdx = 0;
714 UINT32 uv;
715 readIdx += Bitwise::decodeVarInt(uv, output + readIdx, writeIdx - readIdx);
716 BS_TEST_ASSERT(uv == u0);
717 BS_TEST_ASSERT(writeIdx > readIdx);
718
719 readIdx += Bitwise::decodeVarInt(uv, output + readIdx, writeIdx - readIdx);
720 BS_TEST_ASSERT(uv == u1);
721 BS_TEST_ASSERT(writeIdx > readIdx);
722
723 readIdx += Bitwise::decodeVarInt(uv, output + readIdx, writeIdx - readIdx);
724 BS_TEST_ASSERT(uv == u2);
725 BS_TEST_ASSERT(writeIdx > readIdx);
726
727 readIdx += Bitwise::decodeVarInt(uv, output + readIdx, writeIdx - readIdx);
728 BS_TEST_ASSERT(uv == u3);
729 BS_TEST_ASSERT(writeIdx > readIdx);
730
731 INT32 iv;
732 readIdx += Bitwise::decodeVarInt(iv, output + readIdx, writeIdx - readIdx);
733 BS_TEST_ASSERT(iv == i0);
734 BS_TEST_ASSERT(writeIdx > readIdx);
735
736 readIdx += Bitwise::decodeVarInt(iv, output + readIdx, writeIdx - readIdx);
737 BS_TEST_ASSERT(iv == i1);
738 BS_TEST_ASSERT(writeIdx > readIdx);
739
740 readIdx += Bitwise::decodeVarInt(iv, output + readIdx, writeIdx - readIdx);
741 BS_TEST_ASSERT(iv == i2);
742 BS_TEST_ASSERT(writeIdx > readIdx);
743
744 readIdx += Bitwise::decodeVarInt(iv, output + readIdx, writeIdx - readIdx);
745 BS_TEST_ASSERT(iv == i3);
746 BS_TEST_ASSERT(writeIdx > readIdx);
747
748 readIdx += Bitwise::decodeVarInt(iv, output + readIdx, writeIdx - readIdx);
749 BS_TEST_ASSERT(iv == i4);
750 BS_TEST_ASSERT(writeIdx == readIdx);
751 }
752
753 void UtilityTestSuite::testBitStream()
754 {
755 uint32_t v0 = 12345;
756 bool v1 = true;
757 uint32_t v2 = 67890;
758 bool v3 = true;
759 bool v4 = false;
760 uint32_t v5 = 987;
761 String v6 = "Some test string";
762 int32_t v7 = -777;
763 uint64_t v8 = 1919191919191919ULL;
764 float v9 = 0.3333f;
765 float v10 = 10.54321f;
766
767 uint64_t v11 = 5555555555ULL;
768
769 Bitstream bs;
770
771 bs.write(v0); // 0 - 32
772 bs.write(v1); // 32 - 33
773 bs.write(v2); // 33 - 65
774 bs.write(v3); // 65 - 66
775 bs.write(v4); // 66 - 67
776
777 bs.writeBits((uint8_t*)&v5, 10); // 67 - 77
778 bs.write(v6); // 77 - 213
779 bs.writeVarInt(v7); // 213 - 229
780 bs.writeVarIntDelta(v7, 0); // 229 - 246
781 bs.writeVarInt(v8); // 246 - 310
782 bs.writeVarIntDelta(v8, v8); // 310 - 311
783 bs.writeNorm(v9); // 311 - 327
784 bs.writeRange(v10, 5.0f, 15.0f); // 327 - 343
785 bs.writeRange(v5, 500U, 1000U); // 343 - 352
786
787 bs.align(); // 352
788 bs.write(v11); // 352 - 416
789
790 BS_TEST_ASSERT(bs.size() == 416);
791
792 uint32_t uv;
793 uint64_t ulv;
794 int32_t iv;
795 bool bv;
796 float fv;
797 String sv;
798
799 bs.seek(0);
800 bs.read(uv);
801 BS_TEST_ASSERT(uv == v0);
802
803 bs.read(bv);
804 BS_TEST_ASSERT(bv == v1);
805
806 bs.read(uv);
807 BS_TEST_ASSERT(uv == v2);
808
809 bs.read(bv);
810 BS_TEST_ASSERT(bv == v3);
811
812 bs.read(bv);
813 BS_TEST_ASSERT(bv == v4);
814
815 uv = 0;
816 bs.readBits((uint8_t*)&uv, 10);
817 BS_TEST_ASSERT(uv == v5);
818
819 bs.read(sv);
820 BS_TEST_ASSERT(sv == v6);
821
822 bs.readVarInt(iv);
823 BS_TEST_ASSERT(iv == v7);
824
825 bs.readVarIntDelta(iv, 0);
826 BS_TEST_ASSERT(iv == v7);
827
828 bs.readVarInt(ulv);
829 BS_TEST_ASSERT(ulv == v8);
830
831 bs.readVarIntDelta(v8, v8);
832 BS_TEST_ASSERT(ulv == v8);
833
834 bs.readNorm(fv);
835 BS_TEST_ASSERT(Math::approxEquals(fv, v9, 0.01f));
836
837 bs.readRange(fv, 5.0f, 15.0f);
838 BS_TEST_ASSERT(Math::approxEquals(fv, v10, 0.01f));
839
840 bs.readRange(uv, 500U, 1000U);
841 BS_TEST_ASSERT(uv == v5);
842
843 bs.align();
844 bs.read(ulv);
845 BS_TEST_ASSERT(ulv == v11);
846 }
847}
848