diff options
| -rw-r--r-- | libdimension/bvst.c | 140 | ||||
| -rw-r--r-- | libdimension/bvst.h | 4 | ||||
| -rw-r--r-- | libdimension/cube.c | 8 | ||||
| -rw-r--r-- | libdimension/dimension/geometry.h | 24 | ||||
| -rw-r--r-- | libdimension/dimension/object.h | 2 | ||||
| -rw-r--r-- | libdimension/geometry.c | 47 | ||||
| -rw-r--r-- | libdimension/sphere.c | 8 | ||||
| -rw-r--r-- | tests/libdimension/bvst.c | 12 |
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(); |