Another rewrite (:

2 files changed, 125 insertions, 169 deletions

diff --git a/src/world.c b/src/world.c
index 157f759..a15e1be 100644
--- a/src/world.c
+++ b/src/world.c
@@ -118,7 +118,6 @@ size_t buildWorldBVHLeafs(BVHNode leafs[WORLD_ENTITY_MAX], const World* world)
     }
 
     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;
@@ -154,173 +153,131 @@ size_t buildWorldBVHLeafs(BVHNode leafs[WORLD_ENTITY_MAX], const World* world)
   return leafsSize;
 }
 
-BVHNode buildWorldBVHTree(BVHNode* leafs, size_t leafsSize,
-                          const World* world)
+size_t buildWorldBVHTree(BVHNode* nodes, size_t nodesSize const World* world)
 {
-  BVHNode* nodes = leafs;
-  size_t nodesSize = leafsSize;
-  int startNode = 0;
-
-  // Yet another copy and paste half fix.
-  while (nodesSize > 1)
-  {
-    BVHNode node;
-    memset(&node, 0, sizeof(BVHNode));
-    int branches[BVH_MAX_BRANCH_COUNT];
-    
-    for (int branchIndex = 0; branchIndex < BVH_MAX_BRANCH_COUNT;
-         ++branchIndex)
-    {
-      int closest = -1;
-      float closestDistance = Vector3LengthSqr(world->size);
-      
-      for (int nodeIndex = 0; nodeIndex < nodesSize; ++nodeIndex)
-      {
-        // First branch.
-        if (branchIndex == 0)
-        {
-          closest = startNode;
-          break;
-        }
-
-        float distance = 0.0;
-        BoundingBox box = node.branches[0]->box;
-        bool alreadyUsed = false;
-
-        // Get distance and box with node at index.
-        for (int index = 0; index < branchIndex; ++index)
-        {
-          // Already a branch.
-          if (branches[index] == nodeIndex)
-          {
-            alreadyUsed = true;
-            break;
-          }
-          
-          distance += Vector3Distance(node.branches[index]->position,
-                                      nodes[nodeIndex].position);
-          box.min = Vector3Min(box.min, node.branches[index]->box.min);
-          box.min = Vector3Min(box.min, nodes[nodeIndex].box.min);
-          box.max = Vector3Max(box.max, node.branches[index]->box.max);
-          box.max = Vector3Max(box.max, nodes[nodeIndex].box.max);
-        }
-
-        if (alreadyUsed)
-        {
-          continue;
-        }
-
-        distance /= (float)branchIndex;
-
-        // Check for overlap.
-        bool overlaps = false;
-
-        for (int index = 0; index < nodesSize; ++index)
-        {
-          alreadyUsed = false;
-
-          if (nodes[index].level > node.level)
-          {
-            continue;
-          }
-          
-          for (int innerBranch = 0; innerBranch < node.branchCount;
-               ++innerBranch)
-          {
-            if (branches[innerBranch] == index)
-            {
-              alreadyUsed = true;
-              break;
-            }
-          }
-          
-          if (!alreadyUsed && index != nodeIndex &&
-              CheckCollisionBoxes(nodes[index].box, box))
-          {
-            overlaps = true;
-            break;
-          }
-        }
-
-        if (!overlaps && distance < closestDistance)
-        {
-          closest = nodeIndex;
-          closestDistance = distance;
-        }
-      }
-
-      if (closest == -1)
-      {
-        break;
-      }
-
-      // Add closest node to branches.
-      node.branches[node.branchCount] = (BVHNode*)FT_MALLOC(sizeof(BVHNode));
-
-      if (node.branches[node.branchCount] == NULL)
-      {
-        ALLOCATION_ERROR;
-      }
-
-      memcpy(node.branches[node.branchCount], &nodes[closest],
-             sizeof(BVHNode));
-
-      // Update level.
-      if (nodes[closest].level > node.level)
-      {
-        node.level = nodes[closest].level;
-      }
-      
-      branches[node.branchCount] = closest;
-      ++node.branchCount;
-    }
-
-    // Create node bounding box and get position.
-    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);
-    ++node.level;
-
-    // Remove taken nodes.
-    nodes[branches[0]] = node;
-
-    int nodeIndex = 0;
-    int removedCount = 0;
-
-    for (int index = 0; index < nodesSize; ++index)
-    {
-      bool notUsed = true;
-
-      for (int branchIndex = 1; branchIndex < node.branchCount; ++branchIndex)
-      {
-        if (branches[branchIndex] == index)
-        {
-          notUsed = false;
-          ++removedCount;
-          break;
-        }
-      }
-
-      if (notUsed)
-      {
-        nodes[nodeIndex] = nodes[index];
-        ++nodeIndex;
-      }
-    }
-
-    nodesSize -= removedCount;
-    ++startNode;
-    startNode %= nodesSize;
-    printf("%ld\n", nodesSize);
-  }
-
-  return nodes[0];
+  /* 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; */
+  /*       } */
+        
+  /*       // 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;
 }
 
 void buildWorldBVH(World* world)
@@ -330,7 +287,7 @@ void buildWorldBVH(World* world)
   // Get leafs.
   BVHNode leafs[WORLD_ENTITY_MAX];
   size_t leafsSize = buildWorldBVHLeafs(leafs, world);
-  world->bvh = buildWorldBVHTree(leafs, leafsSize, world);
+  // world->bvh = buildWorldBVHTree(leafs, leafsSize, world);
 
   world->bvhDebugSelect = 0;
 }
diff --git a/src/world.h b/src/world.h
index 3f167f8..ada9fa1 100644
--- a/src/world.h
+++ b/src/world.h
@@ -21,7 +21,6 @@
 typedef int16_t WorldUID;
 
 typedef struct BVHNode {
-  int8_t level;
   BoundingBox box;
   Vector3 position;
   WorldUID entities[BVH_MAX]; // Only for leafs.