New dmnsn_bounding_box type.

7 files changed, 129 insertions, 104 deletions

diff --git a/libdimension/bvst.c b/libdimension/bvst.c
index d361215..6e23d6d 100644
--- a/libdimension/bvst.c
+++ b/libdimension/bvst.c
@@ -100,12 +100,9 @@ dmnsn_delete_bvst(dmnsn_bvst *tree)
   }
 }
 
-/* Return whether node1 contains node2 */
-static int dmnsn_box_contains(dmnsn_vector p,
-                              dmnsn_vector min, dmnsn_vector max);
 /* Expand node to contain the bounding box from min to max */
 static void dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
-                                    dmnsn_vector min, dmnsn_vector max);
+                                    dmnsn_bounding_box box);
 
 /* Insert an object into the tree */
 void
@@ -121,46 +118,18 @@ dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
   node->parent = NULL;
   node->object = object;
 
-  /* Calculate the new bounding box by finding the minimum coordinate of the
-     transformed corners of the object's original bounding box */
-
-  node->min = dmnsn_matrix_vector_mul(object->trans, object->min);
-  node->max = node->min;
-
-  dmnsn_vector corner;
-  corner = dmnsn_new_vector(object->min.x, object->min.y, object->max.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
-
-  corner = dmnsn_new_vector(object->min.x, object->max.y, object->min.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
-
-  corner = dmnsn_new_vector(object->min.x, object->max.y, object->max.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
-
-  corner = dmnsn_new_vector(object->max.x, object->min.y, object->min.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
-
-  corner = dmnsn_new_vector(object->max.x, object->min.y, object->max.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
-
-  corner = dmnsn_new_vector(object->max.x, object->max.y, object->min.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
-
-  corner = dmnsn_new_vector(object->max.x, object->max.y, object->max.z);
-  corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_bvst_node_swallow(node, corner, corner);
+  /* Calculate the new bounding box */
+  node->bounding_box = dmnsn_matrix_bounding_box_mul(object->trans,
+                                                     object->bounding_box);
 
   /* Now insert the node */
 
   while (parent) {
-    if (dmnsn_box_contains(node->min, parent->min, parent->max)
-        && dmnsn_box_contains(node->max, parent->min, parent->max)) {
+    if (dmnsn_bounding_box_contains(parent->bounding_box,
+                                    node->bounding_box.min)
+        && dmnsn_bounding_box_contains(parent->bounding_box,
+                                       node->bounding_box.max))
+    {
       /* parent fully contains node */
       if (parent->contains)
         parent = parent->contains;
@@ -173,7 +142,7 @@ dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
     } else {
       /* Expand node's bounding box to fully contain parent's if it doesn't
          already */
-      dmnsn_bvst_node_swallow(node, parent->min, parent->max);
+      dmnsn_bvst_node_swallow(node, parent->bounding_box);
       /* node now fully contains parent */
       if (parent->container)
         parent = parent->container;
@@ -189,21 +158,12 @@ dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
   dmnsn_bvst_splay(tree, node);
 }
 
-/* Return whether p is within the axis-aligned box with corners min and max */
-static int
-dmnsn_box_contains(dmnsn_vector p, dmnsn_vector min, dmnsn_vector max)
-{
-  return (p.x >= min.x && p.y >= min.y && p.z >= min.z)
-    && (p.x <= max.x && p.y <= max.y && p.z <= max.z);
-}
-
 /* Expand node to contain the bounding box from min to max */
 static void
-dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
-                        dmnsn_vector min, dmnsn_vector max)
+dmnsn_bvst_node_swallow(dmnsn_bvst_node *node, dmnsn_bounding_box box)
 {
-  node->min = dmnsn_vector_min(node->min, min);
-  node->max = dmnsn_vector_max(node->max, max);
+  node->bounding_box.min = dmnsn_vector_min(node->bounding_box.min, box.min);
+  node->bounding_box.max = dmnsn_vector_max(node->bounding_box.max, box.max);
 }
 
 /* Tree rotations */
@@ -320,8 +280,8 @@ dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray)
   return result.intersection;
 }
 
-static int dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_vector min,
-                                      dmnsn_vector max, double t);
+static bool dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_bounding_box box,
+                                       double t);
 
 static dmnsn_bvst_search_result
 dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
@@ -342,15 +302,14 @@ dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
     dmnsn_delete_intersection(result_temp.intersection);
   }
 
-  if (dmnsn_box_contains(ray.x0, node->min, node->max)
-      || dmnsn_ray_box_intersection(ray, node->min, node->max, t))
+  if (dmnsn_bounding_box_contains(node->bounding_box, ray.x0)
+      || dmnsn_ray_box_intersection(ray, node->bounding_box, t))
   {
     /* Transform the ray according to the object */
     ray_trans = dmnsn_matrix_line_mul(node->object->trans_inv, ray);
 
-    if (dmnsn_box_contains(ray_trans.x0, node->object->min, node->object->max)
-        || dmnsn_ray_box_intersection(ray_trans, node->object->min,
-                                      node->object->max, t))
+    if (dmnsn_bounding_box_contains(node->object->bounding_box, ray_trans.x0)
+        || dmnsn_ray_box_intersection(ray_trans, node->object->bounding_box, t))
     {
       result_temp.intersection =
         (*node->object->intersection_fn)(node->object, ray_trans);
@@ -394,60 +353,65 @@ dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
   return result;
 }
 
-static int
-dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_vector min, dmnsn_vector max,
-                           double t)
+static bool
+dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
 {
   double t_temp;
   dmnsn_vector p;
 
   if (line.n.x != 0.0) {
-    /* x == min.x */
-    t_temp = (min.x - line.x0.x)/line.n.x;
+    /* x == box.min.x */
+    t_temp = (box.min.x - line.x0.x)/line.n.x;
     p = dmnsn_line_point(line, t_temp);
-    if (p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z
+    if (p.y >= box.min.y && p.y <= box.max.y
+        && p.z >= box.min.z && p.z <= box.max.z
         && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return 1;
+      return true;
 
-    /* x == max.x */
-    t_temp = (max.x - line.x0.x)/line.n.x;
+    /* x == box.max.x */
+    t_temp = (box.max.x - line.x0.x)/line.n.x;
     p = dmnsn_line_point(line, t_temp);
-    if (p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z
+    if (p.y >= box.min.y && p.y <= box.max.y
+        && p.z >= box.min.z && p.z <= box.max.z
         && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return 1;
+      return true;
   }
 
   if (line.n.y != 0.0) {
-    /* y == -1.0 */
-    t_temp = (min.y - line.x0.y)/line.n.y;
+    /* y == box.min.y */
+    t_temp = (box.min.y - line.x0.y)/line.n.y;
     p = dmnsn_line_point(line, t_temp);
-    if (p.x >= min.x && p.x <= max.x && p.z >= min.z && p.z <= max.z
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.z >= box.min.z && p.z <= box.max.z
         && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return 1;
+      return true;
 
-    /* y == 1.0 */
-    t_temp = (max.y - line.x0.y)/line.n.y;
+    /* y == box.max.y */
+    t_temp = (box.max.y - line.x0.y)/line.n.y;
     p = dmnsn_line_point(line, t_temp);
-    if (p.x >= min.x && p.x <= max.x && p.z >= min.z && p.z <= max.z
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.z >= box.min.z && p.z <= box.max.z
         && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return 1;
+      return true;
   }
 
   if (line.n.z != 0.0) {
-    /* z == -1.0 */
-    t_temp = (min.z - line.x0.z)/line.n.z;
+    /* z == box.min.z */
+    t_temp = (box.min.z - line.x0.z)/line.n.z;
     p = dmnsn_line_point(line, t_temp);
-    if (p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.y >= box.min.y && p.y <= box.max.y
         && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return 1;
+      return true;
 
-    /* z == 1.0 */
-    t_temp = (max.z - line.x0.z)/line.n.z;
+    /* z == box.max.z */
+    t_temp = (box.max.z - line.x0.z)/line.n.z;
     p = dmnsn_line_point(line, t_temp);
-    if (p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.y >= box.min.y && p.y <= box.max.y
         && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return 1;
+      return true;
   }
 
-  return 0;
+  return false;
 }
diff --git a/libdimension/bvst.h b/libdimension/bvst.h
index b783117..e682b2c 100644
--- a/libdimension/bvst.h
+++ b/libdimension/bvst.h
@@ -46,8 +46,8 @@ struct dmnsn_bvst_node {
   /* Parent node for easy backtracking */
   dmnsn_bvst_node *parent;
 
-  /* Bounding box corners */
-  dmnsn_vector min, max;
+  /* Bounding box */
+  dmnsn_bounding_box bounding_box;
 
   /* Node payload */
   dmnsn_object *object;
diff --git a/libdimension/cube.c b/libdimension/cube.c
index 8b77da8..a6f656d 100644
--- a/libdimension/cube.c
+++ b/libdimension/cube.c
@@ -38,10 +38,10 @@ dmnsn_new_cube()
 {
   dmnsn_object *cube = dmnsn_new_object();
   if (cube) {
-    cube->intersection_fn = &dmnsn_cube_intersection_fn;
-    cube->inside_fn       = &dmnsn_cube_inside_fn;
-    cube->min             = dmnsn_new_vector(-1.0, -1.0, -1.0);
-    cube->max             = dmnsn_new_vector(1.0, 1.0, 1.0);
+    cube->intersection_fn  = &dmnsn_cube_intersection_fn;
+    cube->inside_fn        = &dmnsn_cube_inside_fn;
+    cube->bounding_box.min = dmnsn_new_vector(-1.0, -1.0, -1.0);
+    cube->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
   }
   return cube;
 }
diff --git a/libdimension/dimension/geometry.h b/libdimension/dimension/geometry.h
index 0be0c6a..754e46d 100644
--- a/libdimension/dimension/geometry.h
+++ b/libdimension/dimension/geometry.h
@@ -26,19 +26,23 @@
 #define DIMENSION_GEOMETRY_H
 
 #include <math.h>
+#include <stdbool.h>
 
-/* Vector and matrix types. */
+/* Vector and matrix types */
 
-typedef struct { double x, y, z; } dmnsn_vector;
+typedef struct dmnsn_vector { double x, y, z; } dmnsn_vector;
 
-typedef struct { double n[4][4]; } dmnsn_matrix;
+typedef struct dmnsn_matrix { double n[4][4]; } dmnsn_matrix;
 
-/* A line, or ray. */
-typedef struct {
+/* A line, or ray */
+typedef struct dmnsn_line {
   dmnsn_vector x0; /* A point on the line */
   dmnsn_vector n;  /* A normal vector; the direction of the line */
 } dmnsn_line;
 
+/* A bounding box */
+typedef struct dmnsn_bounding_box { dmnsn_vector min, max; } dmnsn_bounding_box;
+
 /* Constants */
 
 #define dmnsn_epsilon 1.0e-9
@@ -189,6 +193,8 @@ double dmnsn_vector_axis_angle(dmnsn_vector v1, dmnsn_vector v2,
 dmnsn_matrix dmnsn_matrix_inverse(dmnsn_matrix A);
 dmnsn_matrix dmnsn_matrix_mul(dmnsn_matrix lhs, dmnsn_matrix rhs);
 dmnsn_vector dmnsn_matrix_vector_mul(dmnsn_matrix lhs, dmnsn_vector rhs);
+dmnsn_bounding_box dmnsn_matrix_bounding_box_mul(dmnsn_matrix lhs,
+                                                 dmnsn_bounding_box rhs);
 
 /* Affine line transformation; n = lhs*(x0 + n) - lhs*x0, x0 *= lhs */
 DMNSN_INLINE dmnsn_line
@@ -227,4 +233,12 @@ dmnsn_line_add_epsilon(dmnsn_line l)
 /* Solve for the t value such that x0 + t*n = x */
 double dmnsn_line_index(dmnsn_line l, dmnsn_vector x);
 
+/* Return whether p is within the axis-aligned bounding box */
+DMNSN_INLINE bool
+dmnsn_bounding_box_contains(dmnsn_bounding_box box, dmnsn_vector p)
+{
+  return (p.x >= box.min.x && p.y >= box.min.y && p.z >= box.min.z)
+      && (p.x <= box.max.x && p.y <= box.max.y && p.z <= box.max.z);
+}
+
 #endif /* DIMENSION_GEOMETRY_H */
diff --git a/libdimension/dimension/object.h b/libdimension/dimension/object.h
index bd78a35..525c637 100644
--- a/libdimension/dimension/object.h
+++ b/libdimension/dimension/object.h
@@ -68,7 +68,7 @@ struct dmnsn_object {
   dmnsn_matrix trans, trans_inv;
 
   /* Bounding box */
-  dmnsn_vector min, max;
+  dmnsn_bounding_box bounding_box;
 
   /* Callback functions */
   dmnsn_object_intersection_fn *intersection_fn;
diff --git a/libdimension/geometry.c b/libdimension/geometry.c
index fd21d52..7dc6725 100644
--- a/libdimension/geometry.c
+++ b/libdimension/geometry.c
@@ -359,6 +359,53 @@ dmnsn_matrix_vector_mul(dmnsn_matrix lhs, dmnsn_vector rhs)
   return dmnsn_vector_div(r, w);
 }
 
+/* Give an axis-aligned box that contains the given box transformed by `lhs' */
+dmnsn_bounding_box
+dmnsn_matrix_bounding_box_mul(dmnsn_matrix trans, dmnsn_bounding_box box)
+{
+  dmnsn_vector corner;
+  dmnsn_bounding_box ret;
+  ret.min = dmnsn_matrix_vector_mul(trans, box.min);
+  ret.max = ret.min;
+
+  corner  = dmnsn_new_vector(box.min.x, box.min.y, box.max.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  corner  = dmnsn_new_vector(box.min.x, box.max.y, box.min.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  corner  = dmnsn_new_vector(box.min.x, box.max.y, box.max.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  corner  = dmnsn_new_vector(box.max.x, box.min.y, box.min.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  corner  = dmnsn_new_vector(box.max.x, box.min.y, box.max.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  corner  = dmnsn_new_vector(box.max.x, box.max.y, box.min.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  corner  = dmnsn_new_vector(box.max.x, box.max.y, box.max.z);
+  corner  = dmnsn_matrix_vector_mul(trans, corner);
+  ret.min = dmnsn_vector_min(ret.min, corner);
+  ret.max = dmnsn_vector_max(ret.max, corner);
+
+  return ret;
+}
+
 /* Solve for the t value such that x0 + t*n = x */
 double
 dmnsn_line_index(dmnsn_line l, dmnsn_vector x)
diff --git a/libdimension/sphere.c b/libdimension/sphere.c
index f42ef17..7c2894b 100644
--- a/libdimension/sphere.c
+++ b/libdimension/sphere.c
@@ -40,10 +40,10 @@ dmnsn_new_sphere()
 {
   dmnsn_object *sphere = dmnsn_new_object();
   if (sphere) {
-    sphere->intersection_fn = &dmnsn_sphere_intersection_fn;
-    sphere->inside_fn       = &dmnsn_sphere_inside_fn;
-    sphere->min             = dmnsn_new_vector(-1.0, -1.0, -1.0);
-    sphere->max             = dmnsn_new_vector(1.0, 1.0, 1.0);
+    sphere->intersection_fn  = &dmnsn_sphere_intersection_fn;
+    sphere->inside_fn        = &dmnsn_sphere_inside_fn;
+    sphere->bounding_box.min = dmnsn_new_vector(-1.0, -1.0, -1.0);
+    sphere->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
   }
   return sphere;
 }