From 7b08644490cc1f897f4c327af839f0b2448351c0 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Wed, 7 Apr 2010 15:59:49 -0400
Subject: Don't use dynamic memory for dmnsn_intersection's.

Drops us from ~400,000 allocs to ~1000.  Oops ><.
---
 bench/libdimension/bvst.c       |  15 +-
 libdimension/bvst.c             |  51 +++----
 libdimension/bvst.h             |   3 +-
 libdimension/csg.c              | 322 +++++++++++++++++++++-------------------
 libdimension/cube.c             |  17 ++-
 libdimension/dimension/object.h |  10 +-
 libdimension/object.c           |  15 --
 libdimension/raytrace.c         |  24 ++-
 libdimension/sphere.c           |  16 +-
 9 files changed, 231 insertions(+), 242 deletions(-)

diff --git a/bench/libdimension/bvst.c b/bench/libdimension/bvst.c
index de568d5..dd61a80 100644
--- a/bench/libdimension/bvst.c
+++ b/bench/libdimension/bvst.c
@@ -21,13 +21,13 @@
 #include <sandglass.h>
 #include <stdlib.h>
 
-dmnsn_intersection *
-dmnsn_fake_intersection_fn(const dmnsn_object *object, dmnsn_line line)
+bool
+dmnsn_fake_intersection_fn(const dmnsn_object *object, dmnsn_line line,
+                           dmnsn_intersection *intersection)
 {
-  dmnsn_intersection *intersection = dmnsn_new_intersection();
   intersection->t       = (object->bounding_box.min.z - line.x0.z)/line.n.z;
   intersection->texture = object->texture;
-  return intersection;
+  return true;
 }
 
 void
@@ -104,7 +104,7 @@ main()
 {
   dmnsn_bvst *tree;
   dmnsn_bvst_node *node;
-  dmnsn_intersection *intersection;
+  dmnsn_intersection intersection;
   dmnsn_line ray;
   const unsigned int nobjects = 128;
   dmnsn_object *objects[nobjects];
@@ -144,11 +144,10 @@ main()
   ray.x0 = dmnsn_new_vector(0.0, 0.0, -2.0);
   ray.n  = dmnsn_new_vector(0.0, 0.0, 1.0);
 
-  dmnsn_delete_intersection((*objects[0]->intersection_fn)(objects[0], ray));
+  (*objects[0]->intersection_fn)(objects[0], ray, &intersection);
   sandglass_bench_noprecache(&sandglass, {
-    intersection = dmnsn_bvst_search(tree, ray);
+    dmnsn_bvst_search(tree, ray, &intersection);
   });
-  dmnsn_delete_intersection(intersection);
   printf("dmnsn_bvst_search(): %ld\n", sandglass.grains);
 
   /* dmnsn_bvst_splay() */
diff --git a/libdimension/bvst.c b/libdimension/bvst.c
index 958273d..9f9e94b 100644
--- a/libdimension/bvst.c
+++ b/libdimension/bvst.c
@@ -255,22 +255,26 @@ dmnsn_bvst_rotate(dmnsn_bvst_node *node)
 
 typedef struct {
   dmnsn_bvst_node *node;
-  dmnsn_intersection  *intersection;
+  bool intersected;
+  dmnsn_intersection intersection;
 } dmnsn_bvst_search_result;
 
 static dmnsn_bvst_search_result
 dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t);
 
-dmnsn_intersection *
-dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray)
+bool
+dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray,
+                  dmnsn_intersection *intersection)
 {
   dmnsn_bvst_search_result result
     = dmnsn_bvst_search_recursive(tree->root, ray, -1.0);
 
-  if (result.node)
+  if (result.intersected) {
     dmnsn_bvst_splay(tree, result.node);
+    *intersection = result.intersection;
+  }
 
-  return result.intersection;
+  return result.intersected;
 }
 
 static bool dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_bounding_box box,
@@ -280,7 +284,10 @@ static dmnsn_bvst_search_result
 dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
 {
   dmnsn_line ray_trans;
-  dmnsn_bvst_search_result result = { NULL, NULL }, result_temp;
+  dmnsn_bvst_search_result result_temp, result = {
+    .node = NULL,
+    .intersected = false
+  };
 
   if (!node)
     return result;
@@ -288,11 +295,9 @@ dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
   /* Go down the right subtree first because the closest object is more likely
      to lie in the larger bounding boxes */
   result_temp = dmnsn_bvst_search_recursive(node->container, ray, t);
-  if (result_temp.node && (t < 0.0 || result_temp.intersection->t < t)) {
+  if (result_temp.node && (t < 0.0 || result_temp.intersection.t < t)) {
     result = result_temp;
-    t = result.intersection->t;
-  } else {
-    dmnsn_delete_intersection(result_temp.intersection);
+    t = result.intersection.t;
   }
 
   if (dmnsn_bounding_box_contains(node->bounding_box, ray.x0)
@@ -304,23 +309,24 @@ dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double 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);
+      result_temp.intersected =
+        (*node->object->intersection_fn)(node->object, ray_trans,
+                                         &result_temp.intersection);
 
-      if (result_temp.intersection
-          && (t < 0.0 || result_temp.intersection->t < t)) {
-        dmnsn_delete_intersection(result.intersection);
+      if (result_temp.intersected
+          && (t < 0.0 || result_temp.intersection.t < t)) {
         result.node = node;
+        result.intersected = true;
         result.intersection = result_temp.intersection;
-        t = result.intersection->t;
+        t = result.intersection.t;
 
         /* Transform the intersection back to the observer's view */
-        result.intersection->ray = ray;
-        result.intersection->normal = dmnsn_vector_normalize(
+        result.intersection.ray = ray;
+        result.intersection.normal = dmnsn_vector_normalize(
           dmnsn_vector_sub(
             dmnsn_matrix_vector_mul(
               node->object->trans,
-              result.intersection->normal
+              result.intersection.normal
             ),
             dmnsn_matrix_vector_mul(
               node->object->trans,
@@ -328,18 +334,13 @@ dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
             )
           )
         );
-      } else {
-        dmnsn_delete_intersection(result_temp.intersection);
       }
     }
 
     /* Go down the left subtree */
     result_temp = dmnsn_bvst_search_recursive(node->contains, ray, t);
-    if (result_temp.node && (t < 0.0 || result_temp.intersection->t < t)) {
-      dmnsn_delete_intersection(result.intersection);
+    if (result_temp.node && (t < 0.0 || result_temp.intersection.t < t)) {
       result = result_temp;
-    } else {
-      dmnsn_delete_intersection(result_temp.intersection);
     }
   }
 
diff --git a/libdimension/bvst.h b/libdimension/bvst.h
index e682b2c..d300cf9 100644
--- a/libdimension/bvst.h
+++ b/libdimension/bvst.h
@@ -60,6 +60,7 @@ void dmnsn_delete_bvst(dmnsn_bvst *tree);
 void dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object);
 void dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node);
 
-dmnsn_intersection *dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray);
+bool dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray,
+                       dmnsn_intersection *intersection);
 
 #endif /* DIMENSION_IMPL_BVST_H */
diff --git a/libdimension/csg.c b/libdimension/csg.c
index 24f1f80..4619759 100644
--- a/libdimension/csg.c
+++ b/libdimension/csg.c
@@ -32,59 +32,63 @@ dmnsn_csg_free_fn(void *ptr)
 
 /* Unions */
 
-static dmnsn_intersection *
-dmnsn_csg_union_intersection_fn(const dmnsn_object *csg, dmnsn_line line)
+static bool
+dmnsn_csg_union_intersection_fn(const dmnsn_object *csg,
+                                dmnsn_line line,
+                                dmnsn_intersection *intersection)
 {
   const dmnsn_object **params = csg->ptr;
 
   dmnsn_line line1 = dmnsn_matrix_line_mul(params[0]->trans_inv, line);
   dmnsn_line line2 = dmnsn_matrix_line_mul(params[1]->trans_inv, line);
-  dmnsn_intersection *i1 = (*params[0]->intersection_fn)(params[0], line1);
-  dmnsn_intersection *i2 = (*params[1]->intersection_fn)(params[1], line2);
 
-  if (i1) {
+  dmnsn_intersection i1, i2;
+  bool is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
+  bool is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
+
+  if (is_i1) {
     /* Transform the intersection back to the observer's view */
-    i1->ray = line;
-    i1->normal = dmnsn_vector_normalize(
+    i1.ray = line;
+    i1.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[0]->trans, i1->normal),
+        dmnsn_matrix_vector_mul(params[0]->trans, i1.normal),
         dmnsn_matrix_vector_mul(params[0]->trans, dmnsn_zero)
       )
     );
 
-    if (!i1->texture)
-      i1->texture = csg->texture;
-    if (!i1->interior)
-      i1->interior = csg->interior;
+    if (!i1.texture)
+      i1.texture = csg->texture;
+    if (!i1.interior)
+      i1.interior = csg->interior;
   }
 
-  if (i2) {
-    i2->ray = line;
-    i2->normal = dmnsn_vector_normalize(
+  if (is_i2) {
+    i2.ray = line;
+    i2.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[1]->trans, i2->normal),
+        dmnsn_matrix_vector_mul(params[1]->trans, i2.normal),
         dmnsn_matrix_vector_mul(params[1]->trans, dmnsn_zero)
       )
     );
 
-    if (!i2->texture)
-      i2->texture = csg->texture;
-    if (!i2->interior)
-      i2->interior = csg->interior;
+    if (!i2.texture)
+      i2.texture = csg->texture;
+    if (!i2.interior)
+      i2.interior = csg->interior;
   }
 
-  if (!i1)
-    return i2;
-  if (!i2)
-    return i1;
-
-  if (i1->t < i2->t) {
-    dmnsn_delete_intersection(i2);
-    return i1;
+  if (!is_i1 && !is_i2) {
+    return false;
+  } else if (is_i1 && !is_i2) {
+    *intersection = i1;
+  } else if (!is_i1 && is_i2) {
+    *intersection = i2;
+  } else if (i1.t < i2.t) {
+    *intersection = i1;
   } else {
-    dmnsn_delete_intersection(i1);
-    return i2;
+    *intersection = i2;
   }
+  return true;
 }
 
 static bool
@@ -124,86 +128,88 @@ dmnsn_new_csg_union(dmnsn_object *A, dmnsn_object *B)
 
 /* Intersections */
 
-static dmnsn_intersection *
-dmnsn_csg_intersection_intersection_fn(const dmnsn_object *csg, dmnsn_line line)
+static bool
+dmnsn_csg_intersection_intersection_fn(const dmnsn_object *csg,
+                                       dmnsn_line line,
+                                       dmnsn_intersection *intersection)
 {
   const dmnsn_object **params = csg->ptr;
 
   dmnsn_line line1 = dmnsn_matrix_line_mul(params[0]->trans_inv, line);
   dmnsn_line line2 = dmnsn_matrix_line_mul(params[1]->trans_inv, line);
-  dmnsn_intersection *i1 = (*params[0]->intersection_fn)(params[0], line1);
-  dmnsn_intersection *i2 = (*params[1]->intersection_fn)(params[1], line2);
+
+  dmnsn_intersection i1, i2;
+  bool is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
+  bool is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
 
   double oldt = 0.0;
-  while (i1) {
-    i1->ray = line;
-    i1->t += oldt;
-    oldt = i1->t;
-    i1->normal = dmnsn_vector_normalize(
+  while (is_i1) {
+    i1.ray = line;
+    i1.t += oldt;
+    oldt = i1.t;
+    i1.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[0]->trans, i1->normal),
+        dmnsn_matrix_vector_mul(params[0]->trans, i1.normal),
         dmnsn_matrix_vector_mul(params[0]->trans, dmnsn_zero)
       )
     );
 
-    if (!i1->texture)
-      i1->texture = csg->texture;
-    if (!i1->interior)
-      i1->interior = csg->interior;
+    if (!i1.texture)
+      i1.texture = csg->texture;
+    if (!i1.interior)
+      i1.interior = csg->interior;
 
-    dmnsn_vector point = dmnsn_line_point(i1->ray, i1->t);
+    dmnsn_vector point = dmnsn_line_point(i1.ray, i1.t);
     point = dmnsn_matrix_vector_mul(params[1]->trans_inv, point);
     if (!(*params[1]->inside_fn)(params[1], point)) {
-      line1.x0 = dmnsn_line_point(line1, i1->t);
+      line1.x0 = dmnsn_line_point(line1, i1.t);
       line1 = dmnsn_line_add_epsilon(line1);
-      dmnsn_delete_intersection(i1);
-      i1 = (*params[0]->intersection_fn)(params[0], line1);
+      is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
     } else {
       break;
     }
   }
 
   oldt = 0.0;
-  while (i2) {
-    i2->ray = line;
-    i2->t += oldt;
-    oldt = i2->t;
-    i2->normal = dmnsn_vector_normalize(
+  while (is_i2) {
+    i2.ray = line;
+    i2.t += oldt;
+    oldt = i2.t;
+    i2.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[1]->trans, i2->normal),
+        dmnsn_matrix_vector_mul(params[1]->trans, i2.normal),
         dmnsn_matrix_vector_mul(params[1]->trans, dmnsn_zero)
       )
     );
 
-    if (!i2->texture)
-      i2->texture = csg->texture;
-    if (!i2->interior)
-      i2->interior = csg->interior;
+    if (!i2.texture)
+      i2.texture = csg->texture;
+    if (!i2.interior)
+      i2.interior = csg->interior;
 
-    dmnsn_vector point = dmnsn_line_point(i2->ray, i2->t);
+    dmnsn_vector point = dmnsn_line_point(i2.ray, i2.t);
     point = dmnsn_matrix_vector_mul(params[0]->trans_inv, point);
     if (!(*params[0]->inside_fn)(params[0], point)) {
-      line2.x0 = dmnsn_line_point(line2, i2->t);
+      line2.x0 = dmnsn_line_point(line2, i2.t);
       line2 = dmnsn_line_add_epsilon(line2);
-      dmnsn_delete_intersection(i2);
-      i2 = (*params[1]->intersection_fn)(params[1], line2);
+      is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
     } else {
       break;
     }
   }
 
-  if (!i1)
-    return i2;
-  if (!i2)
-    return i1;
-
-  if (i1->t < i2->t) {
-    dmnsn_delete_intersection(i2);
-    return i1;
+  if (!is_i1 && !is_i2) {
+    return false;
+  } else if (is_i1 && !is_i2) {
+    *intersection = i1;
+  } else if (!is_i1 && is_i2) {
+    *intersection = i2;
+  } else if (i1.t < i2.t) {
+    *intersection = i1;
   } else {
-    dmnsn_delete_intersection(i1);
-    return i2;
+    *intersection = i2;
   }
+  return true;
 }
 
 static bool
@@ -243,86 +249,88 @@ dmnsn_new_csg_intersection(dmnsn_object *A, dmnsn_object *B)
 
 /* Differences */
 
-static dmnsn_intersection *
-dmnsn_csg_difference_intersection_fn(const dmnsn_object *csg, dmnsn_line line)
+static bool
+dmnsn_csg_difference_intersection_fn(const dmnsn_object *csg,
+                                     dmnsn_line line,
+                                     dmnsn_intersection *intersection)
 {
   const dmnsn_object **params = csg->ptr;
 
   dmnsn_line line1 = dmnsn_matrix_line_mul(params[0]->trans_inv, line);
   dmnsn_line line2 = dmnsn_matrix_line_mul(params[1]->trans_inv, line);
-  dmnsn_intersection *i1 = (*params[0]->intersection_fn)(params[0], line1);
-  dmnsn_intersection *i2 = (*params[1]->intersection_fn)(params[1], line2);
+
+  dmnsn_intersection i1, i2;
+  bool is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
+  bool is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
 
   double oldt = 0.0;
-  while (i1) {
-    i1->ray = line;
-    i1->t += oldt;
-    oldt = i1->t;
-    i1->normal = dmnsn_vector_normalize(
+  while (is_i1) {
+    i1.ray = line;
+    i1.t += oldt;
+    oldt = i1.t;
+    i1.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[0]->trans, i1->normal),
+        dmnsn_matrix_vector_mul(params[0]->trans, i1.normal),
         dmnsn_matrix_vector_mul(params[0]->trans, dmnsn_zero)
       )
     );
 
-    if (!i1->texture)
-      i1->texture = csg->texture;
-    if (!i1->interior)
-      i1->interior = csg->interior;
+    if (!i1.texture)
+      i1.texture = csg->texture;
+    if (!i1.interior)
+      i1.interior = csg->interior;
 
-    dmnsn_vector point = dmnsn_line_point(i1->ray, i1->t);
+    dmnsn_vector point = dmnsn_line_point(i1.ray, i1.t);
     point = dmnsn_matrix_vector_mul(params[1]->trans_inv, point);
     if ((*params[1]->inside_fn)(params[1], point)) {
-      line1.x0 = dmnsn_line_point(line1, i1->t);
+      line1.x0 = dmnsn_line_point(line1, i1.t);
       line1 = dmnsn_line_add_epsilon(line1);
-      dmnsn_delete_intersection(i1);
-      i1 = (*params[0]->intersection_fn)(params[0], line1);
+      is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
     } else {
       break;
     }
   }
 
   oldt = 0.0;
-  while (i2) {
-    i2->ray = line;
-    i2->t += oldt;
-    oldt = i2->t;
-    i2->normal = dmnsn_vector_normalize(
+  while (is_i2) {
+    i2.ray = line;
+    i2.t += oldt;
+    oldt = i2.t;
+    i2.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[1]->trans, i2->normal),
+        dmnsn_matrix_vector_mul(params[1]->trans, i2.normal),
         dmnsn_matrix_vector_mul(params[1]->trans, dmnsn_zero)
       )
     );
 
-    if (!i2->texture)
-      i2->texture = csg->texture;
-    if (!i2->interior)
-      i2->interior = csg->interior;
+    if (!i2.texture)
+      i2.texture = csg->texture;
+    if (!i2.interior)
+      i2.interior = csg->interior;
 
-    dmnsn_vector point = dmnsn_line_point(i2->ray, i2->t);
+    dmnsn_vector point = dmnsn_line_point(i2.ray, i2.t);
     point = dmnsn_matrix_vector_mul(params[0]->trans_inv, point);
     if (!(*params[0]->inside_fn)(params[0], point)) {
-      line2.x0 = dmnsn_line_point(line2, i2->t);
+      line2.x0 = dmnsn_line_point(line2, i2.t);
       line2 = dmnsn_line_add_epsilon(line2);
-      dmnsn_delete_intersection(i2);
-      i2 = (*params[1]->intersection_fn)(params[1], line2);
+      is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
     } else {
       break;
     }
   }
 
-  if (!i1)
-    return i2;
-  if (!i2)
-    return i1;
-
-  if (i1->t < i2->t) {
-    dmnsn_delete_intersection(i2);
-    return i1;
+  if (!is_i1 && !is_i2) {
+    return false;
+  } else if (is_i1 && !is_i2) {
+    *intersection = i1;
+  } else if (!is_i1 && is_i2) {
+    *intersection = i2;
+  } else if (i1.t < i2.t) {
+    *intersection = i1;
   } else {
-    dmnsn_delete_intersection(i1);
-    return i2;
+    *intersection = i2;
   }
+  return true;
 }
 
 static bool
@@ -356,86 +364,88 @@ dmnsn_new_csg_difference(dmnsn_object *A, dmnsn_object *B)
 
 /* Merges */
 
-static dmnsn_intersection *
-dmnsn_csg_merge_intersection_fn(const dmnsn_object *csg, dmnsn_line line)
+static bool
+dmnsn_csg_merge_intersection_fn(const dmnsn_object *csg,
+                                dmnsn_line line,
+                                dmnsn_intersection *intersection)
 {
   const dmnsn_object **params = csg->ptr;
 
   dmnsn_line line1 = dmnsn_matrix_line_mul(params[0]->trans_inv, line);
   dmnsn_line line2 = dmnsn_matrix_line_mul(params[1]->trans_inv, line);
-  dmnsn_intersection *i1 = (*params[0]->intersection_fn)(params[0], line1);
-  dmnsn_intersection *i2 = (*params[1]->intersection_fn)(params[1], line2);
+
+  dmnsn_intersection i1, i2;
+  bool is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
+  bool is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
 
   double oldt = 0.0;
-  while (i1) {
-    i1->ray = line;
-    i1->t += oldt;
-    oldt = i1->t;
-    i1->normal = dmnsn_vector_normalize(
+  while (is_i1) {
+    i1.ray = line;
+    i1.t += oldt;
+    oldt = i1.t;
+    i1.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[0]->trans, i1->normal),
+        dmnsn_matrix_vector_mul(params[0]->trans, i1.normal),
         dmnsn_matrix_vector_mul(params[0]->trans, dmnsn_zero)
       )
     );
 
-    if (!i1->texture)
-      i1->texture = csg->texture;
-    if (!i1->interior)
-      i1->interior = csg->interior;
+    if (!i1.texture)
+      i1.texture = csg->texture;
+    if (!i1.interior)
+      i1.interior = csg->interior;
 
-    dmnsn_vector point = dmnsn_line_point(i1->ray, i1->t);
+    dmnsn_vector point = dmnsn_line_point(i1.ray, i1.t);
     point = dmnsn_matrix_vector_mul(params[1]->trans_inv, point);
     if ((*params[1]->inside_fn)(params[1], point)) {
-      line1.x0 = dmnsn_line_point(line1, i1->t);
+      line1.x0 = dmnsn_line_point(line1, i1.t);
       line1 = dmnsn_line_add_epsilon(line1);
-      dmnsn_delete_intersection(i1);
-      i1 = (*params[0]->intersection_fn)(params[0], line1);
+      is_i1 = (*params[0]->intersection_fn)(params[0], line1, &i1);
     } else {
       break;
     }
   }
 
   oldt = 0.0;
-  while (i2) {
-    i2->ray = line;
-    i2->t += oldt;
-    oldt = i2->t;
-    i2->normal = dmnsn_vector_normalize(
+  while (is_i2) {
+    i2.ray = line;
+    i2.t += oldt;
+    oldt = i2.t;
+    i2.normal = dmnsn_vector_normalize(
       dmnsn_vector_sub(
-        dmnsn_matrix_vector_mul(params[1]->trans, i2->normal),
+        dmnsn_matrix_vector_mul(params[1]->trans, i2.normal),
         dmnsn_matrix_vector_mul(params[1]->trans, dmnsn_zero)
       )
     );
 
-    if (!i2->texture)
-      i2->texture = csg->texture;
-    if (!i2->interior)
-      i2->interior = csg->interior;
+    if (!i2.texture)
+      i2.texture = csg->texture;
+    if (!i2.interior)
+      i2.interior = csg->interior;
 
-    dmnsn_vector point = dmnsn_line_point(i2->ray, i2->t);
+    dmnsn_vector point = dmnsn_line_point(i2.ray, i2.t);
     point = dmnsn_matrix_vector_mul(params[0]->trans_inv, point);
     if ((*params[0]->inside_fn)(params[0], point)) {
-      line2.x0 = dmnsn_line_point(line2, i2->t);
+      line2.x0 = dmnsn_line_point(line2, i2.t);
       line2 = dmnsn_line_add_epsilon(line2);
-      dmnsn_delete_intersection(i2);
-      i2 = (*params[1]->intersection_fn)(params[1], line2);
+      is_i2 = (*params[1]->intersection_fn)(params[1], line2, &i2);
     } else {
       break;
     }
   }
 
-  if (!i1)
-    return i2;
-  if (!i2)
-    return i1;
-
-  if (i1->t < i2->t) {
-    dmnsn_delete_intersection(i2);
-    return i1;
+  if (!is_i1 && !is_i2) {
+    return false;
+  } else if (is_i1 && !is_i2) {
+    *intersection = i1;
+  } else if (!is_i1 && is_i2) {
+    *intersection = i2;
+  } else if (i1.t < i2.t) {
+    *intersection = i1;
   } else {
-    dmnsn_delete_intersection(i1);
-    return i2;
+    *intersection = i2;
   }
+  return true;
 }
 
 static bool
diff --git a/libdimension/cube.c b/libdimension/cube.c
index 033d2fb..19c67b9 100644
--- a/libdimension/cube.c
+++ b/libdimension/cube.c
@@ -26,8 +26,9 @@
  */
 
 /* Cube callbacks */
-static dmnsn_intersection *dmnsn_cube_intersection_fn(const dmnsn_object *cube,
-                                                      dmnsn_line line);
+static bool dmnsn_cube_intersection_fn(const dmnsn_object *cube,
+                                       dmnsn_line line,
+                                       dmnsn_intersection *intersection);
 static bool dmnsn_cube_inside_fn(const dmnsn_object *cube,
                                  dmnsn_vector point);
 
@@ -44,12 +45,12 @@ dmnsn_new_cube()
 }
 
 /* Intersections callback for a cube */
-static dmnsn_intersection *
-dmnsn_cube_intersection_fn(const dmnsn_object *cube, dmnsn_line line)
+static bool
+dmnsn_cube_intersection_fn(const dmnsn_object *cube, dmnsn_line line,
+                           dmnsn_intersection *intersection)
 {
   double t = -1.0, t_temp;
   dmnsn_vector p, normal;
-  dmnsn_intersection *intersection = NULL;
 
   /* Six ray-plane intersection tests (x, y, z) = +/- 1.0 */
 
@@ -120,15 +121,15 @@ dmnsn_cube_intersection_fn(const dmnsn_object *cube, dmnsn_line line)
   }
 
   if (t >= 0.0) {
-    intersection = dmnsn_new_intersection();
     intersection->ray      = line;
     intersection->t        = t;
     intersection->normal   = normal;
     intersection->texture  = cube->texture;
     intersection->interior = cube->interior;
+    return true;
+  } else {
+    return false;
   }
-
-  return intersection;
 }
 
 /* Inside callback for a cube */
diff --git a/libdimension/dimension/object.h b/libdimension/dimension/object.h
index 525c637..f0395cd 100644
--- a/libdimension/dimension/object.h
+++ b/libdimension/dimension/object.h
@@ -41,18 +41,14 @@ typedef struct dmnsn_intersection {
   const dmnsn_interior *interior;
 } dmnsn_intersection;
 
-/* Intersection allocation cannot fail */
-dmnsn_intersection *dmnsn_new_intersection();
-void dmnsn_delete_intersection(dmnsn_intersection *intersection);
-
 /* Forward-declare dmnsn_object */
 typedef struct dmnsn_object dmnsn_object;
 
 /* Object callback types */
 
-typedef dmnsn_intersection *
-dmnsn_object_intersection_fn(const dmnsn_object *object, dmnsn_line line);
-
+typedef bool dmnsn_object_intersection_fn(const dmnsn_object *object,
+                                          dmnsn_line line,
+                                          dmnsn_intersection *intersection);
 typedef bool dmnsn_object_inside_fn(const dmnsn_object *object,
                                     dmnsn_vector point);
 
diff --git a/libdimension/object.c b/libdimension/object.c
index 51db42f..bb4a766 100644
--- a/libdimension/object.c
+++ b/libdimension/object.c
@@ -21,21 +21,6 @@
 #include "dimension.h"
 #include <errno.h>
 
-/* Allocate an intersection */
-dmnsn_intersection *
-dmnsn_new_intersection()
-{
-  dmnsn_intersection *intersection = dmnsn_malloc(sizeof(dmnsn_intersection));
-  return intersection;
-}
-
-/* Free an intersection */
-void
-dmnsn_delete_intersection(dmnsn_intersection *intersection)
-{
-  free(intersection);
-}
-
 /* Allocate a dummy object */
 dmnsn_object *
 dmnsn_new_object()
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index 812b6a6..9b87364 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -286,30 +286,28 @@ dmnsn_raytrace_light_ray(const dmnsn_raytrace_state *state,
 
   unsigned int reclevel = state->reclevel;
   while (reclevel) {
-    dmnsn_intersection *shadow_caster
-      = dmnsn_bvst_search(state->bvst, shadow_ray);
+    dmnsn_intersection shadow_caster;
+    bool shadow_casted
+      = dmnsn_bvst_search(state->bvst, shadow_ray, &shadow_caster);
 
-    if (!shadow_caster || shadow_caster->t > 1.0) {
-      dmnsn_delete_intersection(shadow_caster);
+    if (!shadow_casted || shadow_caster.t > 1.0) {
       break;
     }
 
     dmnsn_raytrace_state shadow_state = *state;
-    shadow_state.intersection = shadow_caster;
+    shadow_state.intersection = &shadow_caster;
     shadow_state.reclevel     = reclevel;
 
     dmnsn_raytrace_pigment(&shadow_state);
     if (shadow_state.pigment.filter || shadow_state.pigment.trans) {
       color = dmnsn_color_filter(color, shadow_state.pigment);
-      shadow_ray.x0 = dmnsn_line_point(shadow_ray, shadow_caster->t);
+      shadow_ray.x0 = dmnsn_line_point(shadow_ray, shadow_caster.t);
       shadow_ray.n  = dmnsn_vector_sub(light->x0, shadow_ray.x0);
       shadow_ray = dmnsn_line_add_epsilon(shadow_ray);
     } else {
-      dmnsn_delete_intersection(shadow_caster);
       return dmnsn_black;
     }
 
-    dmnsn_delete_intersection(shadow_caster);
     --reclevel;
   }
 
@@ -448,12 +446,12 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
     return dmnsn_black;
   --state->reclevel;
 
-  dmnsn_intersection *intersection
-    = dmnsn_bvst_search(state->bvst, ray);
+  dmnsn_intersection intersection;
+  bool intersected = dmnsn_bvst_search(state->bvst, ray, &intersection);
 
   dmnsn_color color = state->scene->background;
-  if (intersection) {
-    state->intersection = intersection;
+  if (intersected) {
+    state->intersection = &intersection;
     state->r = dmnsn_line_point(state->intersection->ray,
                                 state->intersection->t);
     state->viewer = dmnsn_vector_normalize(
@@ -494,8 +492,6 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
     }
 
     color = dmnsn_color_add(state->diffuse, state->additional);
-
-    dmnsn_delete_intersection(intersection);
   }
 
   return color;
diff --git a/libdimension/sphere.c b/libdimension/sphere.c
index 77fd1d4..09b6767 100644
--- a/libdimension/sphere.c
+++ b/libdimension/sphere.c
@@ -27,9 +27,9 @@
 
 /* Sphere object callbacks */
 
-static dmnsn_intersection *
-dmnsn_sphere_intersection_fn(const dmnsn_object *sphere, dmnsn_line line);
-
+static bool dmnsn_sphere_intersection_fn(const dmnsn_object *sphere,
+                                         dmnsn_line line,
+                                         dmnsn_intersection *intersection);
 static bool dmnsn_sphere_inside_fn(const dmnsn_object *sphere,
                                    dmnsn_vector point);
 
@@ -46,11 +46,11 @@ dmnsn_new_sphere()
 }
 
 /* Returns the closest intersection of `line' with `sphere' */
-static dmnsn_intersection *
-dmnsn_sphere_intersection_fn(const dmnsn_object *sphere, dmnsn_line line)
+static bool
+dmnsn_sphere_intersection_fn(const dmnsn_object *sphere, dmnsn_line line,
+                             dmnsn_intersection *intersection)
 {
   double a, b, c, t;
-  dmnsn_intersection *intersection = NULL;
 
   /* Solve (x0 + nx*t)^2 + (y0 + ny*t)^2 + (z0 + nz*t)^2 == 1 */
 
@@ -65,16 +65,16 @@ dmnsn_sphere_intersection_fn(const dmnsn_object *sphere, dmnsn_line line)
     }
 
     if (t >= 0.0) {
-      intersection = dmnsn_new_intersection();
       intersection->ray      = line;
       intersection->t        = t;
       intersection->normal   = dmnsn_line_point(line, t);
       intersection->texture  = sphere->texture;
       intersection->interior = sphere->interior;
+      return true;
     }
   }
 
-  return intersection;
+  return false;
 }
 
 /* Return whether a point is inside a sphere (x**2 + y**2 + z**2 < 1.0) */
-- 
cgit v1.2.3