octreeoptimisation.cpp 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
  1. /*
  2. * DoRayMe - a quick and dirty Raytracer
  3. * Octree world optimiser implementation
  4. *
  5. * Created by Manoël Trapier
  6. * Copyright (c) 2020 986-Studio.
  7. *
  8. */
  9. #include <worldoptimiser.h>
  10. void OctreeOptimisation::makeTree(Group *leaf)
  11. {
  12. /* Let's take the bounding box of the root */
  13. BoundingBox rootBB = leaf->getBounds();
  14. /* Take the mid value for each axes */
  15. double midX = (rootBB.max.x - rootBB.min.x) / 2.0 + rootBB.min.x;
  16. double midY = (rootBB.max.y - rootBB.min.y) / 2.0 + rootBB.min.y;
  17. double midZ = (rootBB.max.z - rootBB.min.z) / 2.0 + rootBB.min.z;
  18. BoundingBox QuadrantBB[8];
  19. int quadrantIdx;
  20. Group *Quadrants[8];
  21. int i;
  22. if (leaf->getObjectCount() > 4)
  23. {
  24. /* Split the main bounding box into 8 boxes */
  25. QuadrantBB[0] | rootBB.min;
  26. QuadrantBB[0] | Point(midX, midY, midZ);
  27. QuadrantBB[1] | Point(midX, rootBB.min.y, rootBB.min.z);
  28. QuadrantBB[1] | Point(rootBB.max.x, midY, midZ);
  29. QuadrantBB[2] | Point(rootBB.min.x, midY, rootBB.min.z);
  30. QuadrantBB[2] | Point(midX, rootBB.max.y, midZ);
  31. QuadrantBB[3] | Point(midX, midY, rootBB.min.z);
  32. QuadrantBB[3] | Point(rootBB.max.x, rootBB.max.y, midZ);
  33. QuadrantBB[4] | Point(rootBB.min.x, midY, midZ);
  34. QuadrantBB[4] | Point(midX, rootBB.max.y, rootBB.max.z);
  35. QuadrantBB[5] | Point(midX, midY, midZ);
  36. QuadrantBB[5] | rootBB.max;
  37. QuadrantBB[6] | Point(rootBB.min.x, rootBB.min.y, midZ);
  38. QuadrantBB[6] | Point(midX, midY, rootBB.max.z);
  39. QuadrantBB[7] | Point(midX, rootBB.min.y, midZ);
  40. QuadrantBB[7] | Point(rootBB.max.x, midY, rootBB.max.z);
  41. for (quadrantIdx = 0 ; quadrantIdx < 8 ; quadrantIdx++)
  42. {
  43. Quadrants[quadrantIdx] = nullptr;
  44. }
  45. for (i = 0 ; i < leaf->getObjectCount(); i++)
  46. {
  47. Shape *shp = leaf->getObject(i);
  48. if ((shp->getType() != Shape::GROUP) && (shp->getType() != Shape::OBJFILE))
  49. {
  50. BoundingBox objBB = shp->getBounds();
  51. for (quadrantIdx = 0 ; quadrantIdx < 8 ; quadrantIdx++)
  52. {
  53. if (QuadrantBB[quadrantIdx].fitsIn(objBB))
  54. {
  55. if (Quadrants[quadrantIdx] == nullptr)
  56. {
  57. char name[32];
  58. snprintf(name, 32, "Quadrant %d", quadrantIdx);
  59. Quadrants[quadrantIdx] = new Group(name);
  60. }
  61. Quadrants[quadrantIdx]->addObject(shp);
  62. leaf->removeObject(shp);
  63. i -= 1;
  64. break;
  65. }
  66. }
  67. }
  68. else
  69. {
  70. leaf->removeObject(shp);
  71. /* No cleanup for now, it's bad, I know */
  72. //delete shp;
  73. i -= 1;
  74. }
  75. }
  76. /* Now add the quadrant to the root and recurse in it */
  77. for (quadrantIdx = 0 ; quadrantIdx < 8 ; quadrantIdx++)
  78. {
  79. if (Quadrants[quadrantIdx] != nullptr)
  80. {
  81. this->makeTree(Quadrants[quadrantIdx]);
  82. leaf->addObject(Quadrants[quadrantIdx]);
  83. }
  84. }
  85. }
  86. }
  87. void OctreeOptimisation::run()
  88. {
  89. /* First let's clear our hands */
  90. this->moveInfiniteObjects();
  91. /* Then let's have some fun! */
  92. this->moveAllObjects();
  93. /* Now.. The fun start ! */
  94. makeTree(this->root);
  95. }