From 6681e5e78772be7168b5ed2a5688d2e89ee4f5d5 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 5 Jun 2010 23:46:29 -0600 Subject: Add children to dmnsn_objects, which enables splitting unions. Also, use PR-trees for unions internally. --- libdimension/csg.c | 94 +++++++++++++++-------------------------- libdimension/dimension/object.h | 3 ++ libdimension/object.c | 5 +++ libdimension/plane.c | 2 +- libdimension/prtree.c | 26 +++++++++++- 5 files changed, 68 insertions(+), 62 deletions(-) diff --git a/libdimension/csg.c b/libdimension/csg.c index eb7f2c5..ee77739 100644 --- a/libdimension/csg.c +++ b/libdimension/csg.c @@ -18,7 +18,7 @@ * . * *************************************************************************/ -#include "dimension.h" +#include "dimension_impl.h" #include /* Apply the properties of `csg' to its children */ @@ -38,16 +38,6 @@ dmnsn_csg_cascade(const dmnsn_object *csg, dmnsn_object *object) object->trans = dmnsn_matrix_mul(csg->trans, object->trans); } -/* Generic CSG free function */ -static void -dmnsn_csg_free_fn(void *ptr) -{ - dmnsn_object **params = ptr; - dmnsn_delete_object(params[1]); - dmnsn_delete_object(params[0]); - free(ptr); -} - /* Unions */ static bool @@ -55,58 +45,38 @@ dmnsn_csg_union_intersection_fn(const dmnsn_object *csg, dmnsn_line line, dmnsn_intersection *intersection) { - const dmnsn_object **params = csg->ptr; - - dmnsn_intersection i1, i2; - bool is_i1 = (*params[0]->intersection_fn)(params[0], line, &i1); - bool is_i2 = (*params[1]->intersection_fn)(params[1], line, &i2); - - if (is_i1 && is_i2) { - if (i1.t < i2.t) { - *intersection = i1; - } else { - *intersection = i2; - } - } else if (is_i1) { - *intersection = i1; - } else if (is_i2) { - *intersection = i2; - } else { - return false; - } - - intersection->ray = line; - intersection->normal = dmnsn_transform_normal(csg->trans, - intersection->normal); - return true; + dmnsn_prtree *prtree = csg->ptr; + return dmnsn_prtree_search(prtree, line, intersection); } static bool dmnsn_csg_union_inside_fn(const dmnsn_object *csg, dmnsn_vector point) { - dmnsn_object **params = csg->ptr; - return (*params[0]->inside_fn)(params[0], point) - || (*params[1]->inside_fn)(params[1], point); + DMNSN_ARRAY_FOREACH (dmnsn_object **, child, csg->children) { + if (((*child)->inside_fn)(*child, point)) + return true; + } + return false; } static void dmnsn_csg_union_init_fn(dmnsn_object *csg) { - dmnsn_object **params = csg->ptr; - dmnsn_object *A = params[0]; - dmnsn_object *B = params[1]; - - dmnsn_csg_cascade(csg, A); - dmnsn_csg_cascade(csg, B); + DMNSN_ARRAY_FOREACH (dmnsn_object **, child, csg->children) { + dmnsn_csg_cascade(csg, *child); + dmnsn_object_init(*child); + } + csg->trans = dmnsn_identity_matrix(); - dmnsn_object_init(A); - dmnsn_object_init(B); + dmnsn_prtree *prtree = dmnsn_new_prtree(csg->children); + csg->ptr = prtree; + csg->bounding_box = prtree->root->bounding_box; +} - csg->trans = dmnsn_identity_matrix(); - csg->bounding_box.min - = dmnsn_vector_min(A->bounding_box.min, B->bounding_box.min); - csg->bounding_box.max - = dmnsn_vector_max(A->bounding_box.max, B->bounding_box.max); +static void +dmnsn_csg_union_free_fn(void *ptr) +{ + dmnsn_delete_prtree(ptr); } dmnsn_object * @@ -114,19 +84,26 @@ dmnsn_new_csg_union(dmnsn_object *A, dmnsn_object *B) { dmnsn_object *csg = dmnsn_new_object(); - dmnsn_object **params = dmnsn_malloc(2*sizeof(dmnsn_object *)); - params[0] = A; - params[1] = B; - - csg->ptr = params; + dmnsn_array_push(csg->children, &A); + dmnsn_array_push(csg->children, &B); csg->intersection_fn = &dmnsn_csg_union_intersection_fn; csg->inside_fn = &dmnsn_csg_union_inside_fn; csg->init_fn = &dmnsn_csg_union_init_fn; - csg->free_fn = &dmnsn_csg_free_fn; + csg->free_fn = &dmnsn_csg_union_free_fn; return csg; } +/* Generic CSG free function */ +static void +dmnsn_csg_free_fn(void *ptr) +{ + dmnsn_object **params = ptr; + dmnsn_delete_object(params[1]); + dmnsn_delete_object(params[0]); + free(ptr); +} + /* Generic CSG intersection function */ static bool dmnsn_csg_intersection_fn(const dmnsn_object *csg, dmnsn_line line, @@ -190,9 +167,6 @@ dmnsn_csg_intersection_fn(const dmnsn_object *csg, dmnsn_line line, return false; } - intersection->ray = line; - intersection->normal = dmnsn_transform_normal(csg->trans, - intersection->normal); return true; } diff --git a/libdimension/dimension/object.h b/libdimension/dimension/object.h index 11847b0..5cc62a1 100644 --- a/libdimension/dimension/object.h +++ b/libdimension/dimension/object.h @@ -69,6 +69,9 @@ struct dmnsn_object { /* Bounding box */ dmnsn_bounding_box bounding_box; + /* Child objects */ + dmnsn_array *children; + /* Callback functions */ dmnsn_object_init_fn *init_fn; dmnsn_object_intersection_fn *intersection_fn; diff --git a/libdimension/object.c b/libdimension/object.c index a714f6e..d87eb12 100644 --- a/libdimension/object.c +++ b/libdimension/object.c @@ -40,6 +40,7 @@ dmnsn_new_object() object->texture = NULL; object->interior = NULL; object->trans = dmnsn_identity_matrix(); + object->children = dmnsn_new_array(sizeof(dmnsn_object *)); object->init_fn = NULL; object->free_fn = NULL; return object; @@ -50,6 +51,10 @@ void dmnsn_delete_object(dmnsn_object *object) { if (object) { + DMNSN_ARRAY_FOREACH (dmnsn_object **, child, object->children) { + dmnsn_delete_object(*child); + } + dmnsn_delete_array(object->children); dmnsn_delete_interior(object->interior); dmnsn_delete_texture(object->texture); if (object->free_fn) { diff --git a/libdimension/plane.c b/libdimension/plane.c index 08da44c..76071df 100644 --- a/libdimension/plane.c +++ b/libdimension/plane.c @@ -75,7 +75,7 @@ dmnsn_plane_intersection_fn(const dmnsn_object *plane, dmnsn_line line, return false; } -/* Return whether a point is inside a plane (x**2 + y**2 + z**2 < 1.0) */ +/* Return whether a point is inside a plane */ static bool dmnsn_plane_inside_fn(const dmnsn_object *plane, dmnsn_vector point) { diff --git a/libdimension/prtree.c b/libdimension/prtree.c index b99c7e1..7fcc8ab 100644 --- a/libdimension/prtree.c +++ b/libdimension/prtree.c @@ -436,6 +436,30 @@ dmnsn_pseudo_prtree_leaves(const dmnsn_pseudo_prtree *pseudo) return leaves; } +/* Add objects from an array to a list, splitting unions etc. */ + +static void +dmnsn_list_add_object(dmnsn_list *objects, const dmnsn_object *object) +{ + if (dmnsn_array_size(object->children) == 0) { + dmnsn_list_push(objects, &object); + } else { + DMNSN_ARRAY_FOREACH (const dmnsn_object **, child, object->children) { + dmnsn_list_add_object(objects, *child); + } + } +} + +static dmnsn_list * +dmnsn_object_list(const dmnsn_array *objects) +{ + dmnsn_list *list = dmnsn_new_list(sizeof(dmnsn_object *)); + DMNSN_ARRAY_FOREACH (const dmnsn_object **, object, objects) { + dmnsn_list_add_object(list, *object); + } + return list; +} + /* Split the unbounded objects into a new list */ static dmnsn_list * dmnsn_split_unbounded(dmnsn_list *objects) @@ -464,7 +488,7 @@ dmnsn_split_unbounded(dmnsn_list *objects) dmnsn_prtree * dmnsn_new_prtree(const dmnsn_array *objects) { - dmnsn_list *leaves = dmnsn_list_from_array(objects); + dmnsn_list *leaves = dmnsn_object_list(objects); dmnsn_list *unbounded = dmnsn_split_unbounded(leaves); dmnsn_pseudo_prtree *pseudo = dmnsn_new_pseudo_prtree(leaves, true, 0); -- cgit v1.2.3