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 ><.
---
 libdimension/csg.c | 322 +++++++++++++++++++++++++++--------------------------
 1 file changed, 166 insertions(+), 156 deletions(-)

(limited to 'libdimension/csg.c')

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
-- 
cgit v1.2.3