summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libdimension/bvst.c140
-rw-r--r--libdimension/bvst.h4
-rw-r--r--libdimension/cube.c8
-rw-r--r--libdimension/dimension/geometry.h24
-rw-r--r--libdimension/dimension/object.h2
-rw-r--r--libdimension/geometry.c47
-rw-r--r--libdimension/sphere.c8
-rw-r--r--tests/libdimension/bvst.c12
8 files changed, 135 insertions, 110 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;
}
diff --git a/tests/libdimension/bvst.c b/tests/libdimension/bvst.c
index e026977..33c737b 100644
--- a/tests/libdimension/bvst.c
+++ b/tests/libdimension/bvst.c
@@ -34,14 +34,14 @@ main()
obj2 = dmnsn_new_object();
obj3 = dmnsn_new_object();
- obj1->min = dmnsn_new_vector(0.0, 0.0, 0.0);
- obj1->max = dmnsn_new_vector(1.0, 1.0, 1.0);
+ obj1->bounding_box.min = dmnsn_new_vector(0.0, 0.0, 0.0);
+ obj1->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
- obj2->min = dmnsn_new_vector(-2.0, -2.0, -2.0);
- obj2->max = dmnsn_new_vector(1.0, 1.0, 1.0);
+ obj2->bounding_box.min = dmnsn_new_vector(-2.0, -2.0, -2.0);
+ obj2->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
- obj3->min = dmnsn_new_vector(-1.0, -1.0, -1.0);
- obj3->max = dmnsn_new_vector(0.0, 0.0, 0.0);
+ obj3->bounding_box.min = dmnsn_new_vector(-1.0, -1.0, -1.0);
+ obj3->bounding_box.max = dmnsn_new_vector(0.0, 0.0, 0.0);
tree = dmnsn_new_bvst();
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 17:37:16 +0000