A bit better

2 files changed, 51 insertions, 110 deletions

diff --git a/src/world.c b/src/world.c
index 559b620..34747a0 100644
--- a/src/world.c
+++ b/src/world.c
@@ -1,131 +1,67 @@
 #include "world.h"
 #include "game.h"
 
-int32_t getMortonCode(Vector3 position)
-{
-  int32_t mortonCode = 0;
-  int16_t x = roundf(position.x);
-  int16_t z = roundf(position.z);
-  
-  for (int bit = 0; bit < 32; ++bit)
-  {
-    if (bit % 2)
-    {
-      mortonCode |= IS_BIT_SET(x, (bit / 2)) << bit;
-    }
-    else
-    {
-      mortonCode |= IS_BIT_SET(z, (bit / 2)) << bit;
-    }
-  }
-
-  return mortonCode;
-}
-
-void sortEntitiesUID(WorldUID entities[WORLD_ENTITY_MAX], const World* world)
-{
-  // Lazy selection sort.
-  for (int outer = 0; outer < WORLD_ENTITY_MAX - 1; ++outer)
-  {
-    int minIndex = outer;
-
-    for (int inner = outer + 1; inner < WORLD_ENTITY_MAX; ++inner)
-    {
-      int32_t entityCode = getMortonCode(
-        world->entities[entities[inner]].position);
-      int32_t minCode = getMortonCode(
-        world->entities[entities[minIndex]].position);
-
-      if (entityCode < minCode)
-      {
-        minIndex = inner;
-      }
-    }
-
-    WorldUID temp = entities[outer];
-    entities[outer] = entities[minIndex];
-    entities[minIndex] = temp;
-  }
-
-  // Test
-  /* for (int index = 0; index < WORLD_ENTITY_MAX; ++index) */
-  /* { */
-  /*   printf("%d\n", getMortonCode(world->entities[entities[index]].position)); */
-  /*   PRINT_VECTOR3(world->entities[entities[index]].position); */
-  /* } */
-}
-
 // Very messy right now. Mostly been playing around.
 void buildWorldBVH(World* world)
 {
   Entity* entities = world->entities;
   bool grouped[WORLD_ENTITY_MAX];
-  WorldUID sorted[WORLD_ENTITY_MAX];
+  int ungroupedCount = WORLD_ENTITY_MAX;
 
   // This is a mess thats not going to work.
   for (int index = 0; index < WORLD_ENTITY_MAX; ++index)
   {
     grouped[index] = false;
-    sorted[index] = index;
   }
 
-  //sortEntitiesUID(sorted, world);
+  world->bvhTestSize = 0;
 
-  for (int nodeIndex = 0; nodeIndex < BVH_LEAF_COUNT; ++nodeIndex)
+  // This is going to be slow. Optimizjl;dsfz lajtklers (:
+  while (ungroupedCount > 0)
   {
+    BVHNode leaf;
+
     for (int leafIndex = 0; leafIndex < BVH_MAX; ++leafIndex)
     {
-      BVHNode* leaf = &world->bvhTest[nodeIndex];
-
-      // First entity.
-      if (leafIndex == 0)
-      {
-        for (int index = 0; index < WORLD_ENTITY_MAX; ++index)
-        {
-          if (!grouped[index])
-          {
-            leaf->entities[0] = index;
-            grouped[index] = true;
-            break;
-          }
-        }
-        
-        continue;
-      }
-
-      // Find closest to entity one.
       int closest = -1;
       float closestDistance = world->size.x * world->size.z * 2.0;
 
+      // Find closest.
       for (int index = 0; index < WORLD_ENTITY_MAX; ++index)
       {
         if (grouped[index])
         {
           continue;
         }
+        
+        // First entity.
+        if (leafIndex == 0)
+        {
+          closest = index;
+          break;
+        }
 
-        // Average out distances and find current bounding box.
         float distance = 0.0;
         Vector3 min = entities[index].position;
-        Vector3 max = entities[index].position;
-
-        bool overlaps = false;
+        Vector3 max = min;
 
         for (int innerIndex = 0; innerIndex < leafIndex; ++innerIndex)
         {
           distance += Vector3Distance(
-            entities[leaf->entities[innerIndex]].position,
+            entities[leaf.entities[innerIndex]].position,
             entities[index].position);
-          min = Vector3Min(min, entities[leaf->entities[innerIndex]].position);
+          min = Vector3Min(min, entities[leaf.entities[innerIndex]].position);
           min = Vector3Min(min, entities[index].position);
-          max = Vector3Max(max, entities[leaf->entities[innerIndex]].position);
+          max = Vector3Max(max, entities[leaf.entities[innerIndex]].position);
           max = Vector3Max(max, entities[index].position);
         }
 
         BoundingBox overlapBox = (BoundingBox){min, max};
         distance /= (float)leafIndex;
 
-        // Check if laptop will be caused.
+        bool overlaps = false;
+
+        // Check if overlap will be caused.
         for (int overlapIndex = 0; overlapIndex < WORLD_ENTITY_MAX;
              ++overlapIndex)
         {
@@ -138,7 +74,7 @@ void buildWorldBVH(World* world)
 
           for (int partOfIndex = 0; partOfIndex < leafIndex + 1; ++partOfIndex)
           {
-            if (overlapIndex == leaf->entities[partOfIndex])
+            if (overlapIndex == leaf.entities[partOfIndex])
             {
               isPartOf = true;
               break;
@@ -159,6 +95,7 @@ void buildWorldBVH(World* world)
           }
         }
 
+        // Update distance.
         if (!overlaps && distance < closestDistance)
         {
           closestDistance = distance;
@@ -168,37 +105,38 @@ void buildWorldBVH(World* world)
 
       if (closest == -1)
       {
-        leaf->entities[leafIndex] = -1;
+        leaf.entities[leafIndex] = -1;
       }
       else
       {
-        leaf->entities[leafIndex] = closest;
+        leaf.entities[leafIndex] = closest;
         grouped[closest] = true;
       }
+    }
 
-      // Last entity
-      if (leafIndex == BVH_MAX - 1)
-      {
-        // Create bounding box. */
-        leaf->box.min = world->entities[leaf->entities[0]].position;
-        leaf->box.max = world->entities[leaf->entities[0]].position;
+    // Get bounding box.
+    leaf.box.min = world->entities[leaf.entities[0]].position;
+    leaf.box.max = world->entities[leaf.entities[0]].position;
 
-        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]].position);
-          leaf->box.max = Vector3Max(
-            leaf->box.max,
-            world->entities[leaf->entities[index]].position);
-        }
+    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]].position);
+      leaf.box.max = Vector3Max(
+        leaf.box.max,
+        world->entities[leaf.entities[index]].position);
     }
+
+    world->bvhTest[world->bvhTestSize] = leaf;
+    ++world->bvhTestSize;
+    --ungroupedCount;
+    printf("size: %d\n", world->bvhTestSize);
   }
 
   // test
@@ -209,6 +147,8 @@ void buildWorldBVH(World* world)
       printf("%d\n", index);
     }
   }
+
+  printf("size: %d\n", world->bvhTestSize);
 }
 
 World createWorld(int seed)
@@ -258,7 +198,8 @@ void updateWorld(World* world, Game* game)
     updateEntity(&world->entities[index], game);
   }
 
-  for (int index = 0; index < BVH_LEAF_COUNT; ++index)
+  // Draw BVH leafs.
+  for (int index = 0; index < world->bvhTestSize; ++index)
   {
     Color colors[] = {RED, GREEN, BLUE, ORANGE, YELLOW, PINK};
     DrawBoundingBox(world->bvhTest[index].box, colors[index % 6]);
diff --git a/src/world.h b/src/world.h
index 69f81bd..6ad658d 100644
--- a/src/world.h
+++ b/src/world.h
@@ -33,7 +33,7 @@ typedef struct {
   Model heightmap;
   Entity entities[WORLD_ENTITY_MAX];
   BVHNode bvh;
-  BVHNode bvhTest[BVH_LEAF_COUNT];
+  BVHNode bvhTest[WORLD_ENTITY_MAX];
   int bvhTestSize;
 } World;