If aliens invade earth I am in support of the aliens

1 files changed, 116 insertions, 124 deletions

diff --git a/src/world.c b/src/world.c
index a15e1be..6c46eba 100644
--- a/src/world.c
+++ b/src/world.c
@@ -16,7 +16,6 @@ size_t buildWorldBVHLeafs(BVHNode leafs[WORLD_ENTITY_MAX], const World* world)
     for (int leafIndex = 0; leafIndex < BVH_MAX; ++leafIndex)
     {
       int closest = -1;
-      int closestGroupedIndex = 0;
       float closestDistance = world->size.x;
 
       // Find closest.
@@ -153,131 +152,124 @@ size_t buildWorldBVHLeafs(BVHNode leafs[WORLD_ENTITY_MAX], const World* world)
   return leafsSize;
 }
 
-size_t buildWorldBVHTree(BVHNode* nodes, size_t nodesSize const World* world)
+size_t buildWorldBVHSubTree(BVHNode* subtree,
+                         const BVHNode* nodes, size_t nodesSize,
+                         const World* world)
 {
-  /* size_t leafsSize = 0; */
-  /* const Entity* entities = world->entities; */
-  /* bool grouped[WORLD_ENTITY_MAX]; */
-  /* int ungroupedCount = WORLD_ENTITY_MAX; */
-  /* memset(grouped, 0, sizeof(grouped)); */
-
-  /* while (ungroupedCount > 0) */
-  /* { */
-  /*   BVHNode leaf; */
-
-  /*   for (int leafIndex = 0; leafIndex < BVH_MAX; ++leafIndex) */
-  /*   { */
-  /*     int closest = -1; */
-  /*     int closestGroupedIndex = 0; */
-  /*     float closestDistance = world->size.x; */
-
-  /*     // Find closest. */
-  /*     for (int index = 0; index < WORLD_ENTITY_MAX; ++index) */
-  /*     { */
-  /*       if (grouped[index]) */
-  /*       { */
-  /*         continue; */
-  /*       } */
+  size_t nodeCount = 0;
+  bool grouped[nodesSize];
+  int ungroupedCount = nodesSize;
+  memset(grouped, 0, sizeof(grouped));
+
+  while (ungroupedCount > 0)
+  {
+    BVHNode node;
+    memset(&node, 0, sizeof(BVHNode));
+
+    for (int branchIndex = 0; branchIndex < BVH_MAX_BRANCH_COUNT;
+         ++branchIndex)
+    {
+      int closest = -1;
+      float closestDistance = world->size.x;
+
+      // Find closest.
+      for (int index = 0; index < nodesSize; ++index)
+      {
+        if (grouped[index])
+        {
+          continue;
+        }
         
-  /*       // First entity. */
-  /*       if (leafIndex == 0) */
-  /*       { */
-  /*         closest = index; */
-  /*         break; */
-  /*       } */
-
-  /*       float distance = 0.0; */
-  /*       BoundingBox overlapBox; */
-  /*       overlapBox.min = entities[index].position; */
-  /*       overlapBox.max = overlapBox.min; */
-
-  /*       for (int innerIndex = 0; innerIndex < leafIndex; ++innerIndex) */
-  /*       { */
-  /*         distance += Vector3Distance( */
-  /*           entities[leaf.entities[innerIndex]].position, */
-  /*           entities[index].position); */
-  /*         overlapBox.min = Vector3Min( */
-  /*           overlapBox.min, */
-  /*           entities[leaf.entities[innerIndex]].box.min); */
-  /*         overlapBox.min = Vector3Min( */
-  /*           overlapBox.min, */
-  /*           entities[index].box.min); */
-  /*         overlapBox.max = Vector3Max( */
-  /*           overlapBox.max, */
-  /*           entities[leaf.entities[innerIndex]].box.max); */
-  /*         overlapBox.max = Vector3Max( */
-  /*           overlapBox.max, */
-  /*           entities[index].box.max); */
-  /*       } */
-
-  /*       distance /= (float)leafIndex; */
-
-  /*       bool overlaps = false; */
-
-  /*       // Too big (will count it as a overlap). */
-  /*       if (Vector3Distance(overlapBox.min, overlapBox.max) >= BVH_BOX_MAX) */
-  /*       { */
-  /*         overlaps = true; */
-  /*       } */
-
-  /*       // Check if overlap is already happening. */
-  /*       for (int nodeIndex = 0; nodeIndex < leafsSize && !overlaps; */
-  /*            ++nodeIndex) */
-  /*       { */
-  /*         if (CheckCollisionBoxes(overlapBox, leafs[nodeIndex].box)) */
-  /*         { */
-  /*           overlaps = true; */
-  /*           break; */
-  /*         } */
-  /*       } */
-
-  /*       // Update distance. */
-  /*       if (!overlaps && distance < closestDistance) */
-  /*       { */
-  /*         closestDistance = distance; */
-  /*         closest = index; */
-  /*       } */
-  /*     } */
-
-  /*     if (closest == -1) */
-  /*     { */
-  /*       leaf.entities[leafIndex] = -1; */
-  /*     } */
-  /*     else */
-  /*     { */
-  /*       leaf.entities[leafIndex] = closest; */
-  /*       grouped[closest] = true; */
-  /*       --ungroupedCount; */
-  /*     } */
-  /*   } */
-
-  /*   // Get bounding box. */
-  /*   leaf.box = world->entities[leaf.entities[0]].box; */
-
-  /*   for (int index = 1; index < BVH_MAX; ++index) */
-  /*   { */
-  /*     if (leaf.entities[index] == -1) */
-  /*     { */
-  /*       continue; */
-  /*     } */
-
-  /*     leaf.box.min = Vector3Min( */
-  /*       leaf.box.min, */
-  /*       world->entities[leaf.entities[index]].box.min); */
-  /*     leaf.box.max = Vector3Max( */
-  /*       leaf.box.max, */
-  /*       world->entities[leaf.entities[index]].box.max); */
-  /*   } */
-
-  /*   leaf.position = Vector3Scale(Vector3Add(leaf.box.min, leaf.box.max), 0.5); */
-  /*   leaf.level = 0; */
-
-  /*   memset(leaf.branches, 0, BVH_MAX_BRANCH_COUNT * sizeof(BVHNode*)); */
-  /*   leafs[leafsSize] = leaf; */
-  /*   ++leafsSize; */
-  /* } */
-
-  return 0;
+        // First branch.
+        if (branchIndex == 0)
+        {
+          closest = index;
+          break;
+        }
+
+        float distance = 0.0;
+        BoundingBox overlapBox;
+        overlapBox.min = nodes[index].position;
+        overlapBox.max = overlapBox.min;
+
+        for (int innerIndex = 0; innerIndex < branchIndex; ++innerIndex)
+        {
+          distance += Vector3Distance(node.branches[innerIndex]->position,
+                                      nodes[index].position);
+          overlapBox.min = Vector3Min(overlapBox.min,
+                                      node.branches[innerIndex]->box.min);
+          overlapBox.min = Vector3Min(overlapBox.min, nodes[index].box.min);
+          overlapBox.max = Vector3Max(overlapBox.max,
+                                      node.branches[innerIndex]->box.max);
+          overlapBox.max = Vector3Max(overlapBox.max, nodes[index].box.max);
+        }
+
+        distance /= (float)branchIndex;
+
+        bool overlaps = false;
+
+        // Too big (will count it as a overlap).
+        if (Vector3Distance(overlapBox.min, overlapBox.max) >= BVH_BOX_MAX)
+        {
+          overlaps = true;
+        }
+
+        // Check if overlap is already happening.
+        for (int nodeIndex = 0; nodeIndex < nodesSize && !overlaps;
+             ++nodeIndex)
+        {
+          if (CheckCollisionBoxes(overlapBox, nodes[nodeIndex].box))
+          {
+            overlaps = true;
+            break;
+          }
+        }
+
+        // Update distance.
+        if (!overlaps && distance < closestDistance)
+        {
+          closestDistance = distance;
+          closest = index;
+        }
+      }
+
+      if (closest == -1)
+      {
+        continue;
+      }
+
+      node.branches[node.branchCount] = (BVHNode*)FT_MALLOC(sizeof(BVHNode));
+
+      if (node.branches[node.branchCount] == NULL)
+      {
+        ALLOCATION_ERROR;
+        break;
+      }
+
+      memcpy(node.branches[node.branchCount], &nodes[closest],
+             sizeof(BVHNode));
+
+      ++node.branchCount;
+      grouped[closest] = true;
+      --ungroupedCount;
+    }
+
+    // Get bounding box.
+    node.box = node.branches[0]->box;
+
+    for (int index = 1; index < node.branchCount; ++index)
+    {
+      node.box.min = Vector3Min(node.box.min, node.branches[index]->box.min);
+      node.box.max = Vector3Max(node.box.max, node.branches[index]->box.max);
+    }
+
+    node.position = Vector3Scale(Vector3Add(node.box.min, node.box.max), 0.5);
+
+    subtree[nodeCount] = node;
+    ++nodeCount;
+  }
+
+  return nodeCount;
 }
 
 void buildWorldBVH(World* world)