summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libdimension/kD_splay_tree.c173
-rw-r--r--libdimension/kD_splay_tree.h3
-rw-r--r--libdimension/raytrace.c72
3 files changed, 176 insertions, 72 deletions
diff --git a/libdimension/kD_splay_tree.c b/libdimension/kD_splay_tree.c
index 5f90213..1d099d5 100644
--- a/libdimension/kD_splay_tree.c
+++ b/libdimension/kD_splay_tree.c
@@ -274,3 +274,176 @@ dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node)
P->container = B;
}
}
+
+typedef struct {
+ dmnsn_kD_splay_node *node;
+ dmnsn_intersection *intersection;
+} dmnsn_kD_splay_search_result;
+
+static dmnsn_kD_splay_search_result
+dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
+ double t);
+
+dmnsn_intersection *
+dmnsn_kD_splay_search(dmnsn_kD_splay_node *root, dmnsn_line ray)
+{
+ dmnsn_kD_splay_search_result result =
+ dmnsn_kD_splay_search_recursive(root, ray, -1.0);
+
+ if (result.node)
+ dmnsn_kD_splay(result.node);
+
+ return result.intersection;
+}
+
+static dmnsn_kD_splay_search_result
+dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
+ double t)
+{
+ double t_temp;
+ dmnsn_line ray_trans;
+ dmnsn_kD_splay_search_result result = { NULL, NULL }, result_temp;
+ int search_left = 0; /* Whether to search the left branch */
+
+ if (!node)
+ return result;
+
+ if ((ray.x0.x >= node->min.x && ray.x0.y >= node->min.y
+ && ray.x0.z >= node->min.z)
+ && (ray.x0.x <= node->max.x && ray.x0.y <= node->max.y
+ && ray.x0.z <= node->max.z))
+ {
+ /*
+ * Our line's origin is inside the bounding box - we have no choice but to
+ * recurse down both sides of the tree.
+ */
+ search_left = 1;
+ } else {
+ /*
+ * We are outside the bounding box, so only follow the left branch if we
+ * intersect this one, and only test the object if the bounding box is
+ * closer than `t'.
+ */
+ t_temp = dmnsn_ray_box_intersection(ray, node->min, node->max);
+
+ search_left = t_temp >= 0.0 && (t < 0.0 || t_temp < t)
+ }
+
+ if (search_left) {
+ /* Transform the ray according to the object */
+ ray_trans = dmnsn_matrix_line_mul(node->object->trans, ray);
+ /* Test for an intersection with the current object */
+ result.intersection =
+ (*node->object->intersection_fn)(node->object, ray_trans);
+
+ if (result.intersection) {
+ if (t < 0.0 || result.intersection->t < t) {
+ result.node = node;
+ t = result.intersection->t;
+ } else {
+ dmnsn_delete_intersection(result.intersection);
+ result.intersection = NULL;
+ }
+ }
+
+ /* Go down the left branch */
+ result_temp = dmnsn_kD_splay_search_recursive(node->contains, ray, t);
+ if (result_temp.intersection) {
+ if (t < 0.0 || result_temp.intersection->t < t) {
+ if (result.intersection)
+ dmnsn_delete_intersection(result.intersection);
+ result = result_temp;
+ t = result->intersection->t;
+ } else {
+ dmnsn_delete_intersection(result_temp.intersection);
+ }
+ }
+ }
+
+ /* Go down the right branch */
+ result_temp = dmnsn_kD_splay_search_recursive(node->container, ray, t);
+ if (result_temp.intersection) {
+ if (t < 0.0 || result_temp.intersection->t < t) {
+ if (result.intersection)
+ dmnsn_delete_intersection(result.intersection);
+ result = result_temp;
+ t = result->intersection->t;
+ } else {
+ dmnsn_delete_intersection(result_temp.intersection);
+ }
+ }
+
+ return result;
+}
+
+static double dmnsn_ray_box_intersection(dmnsn_line ray,
+ dmnsn_vector min, dmnsn_vector max);
+
+static double
+dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_vector min, dmnsn_vector max)
+{
+ double t = -1.0, t_temp;
+ dmnsn_vector p;
+
+ if (line.n.x != 0.0) {
+ /* x == min.x */
+ t_temp = (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
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ {
+ t = t_temp;
+ }
+
+ /* x == max.x */
+ t_temp = (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
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ {
+ t = t_temp;
+ }
+ }
+
+ if (line.n.y != 0.0) {
+ /* y == -1.0 */
+ t_temp = (-1.0 - 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
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ {
+ t = t_temp;
+ }
+
+ /* y == 1.0 */
+ t_temp = (1.0 - 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
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ {
+ t = t_temp;
+ }
+ }
+
+ if (line.n.z != 0.0) {
+ /* z == -1.0 */
+ t_temp = (-1.0 - 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
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ {
+ t = t_temp;
+ }
+
+ /* z == 1.0 */
+ t_temp = (1.0 - 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
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ {
+ t = t_temp;
+ }
+ }
+
+ return t;
+}
diff --git a/libdimension/kD_splay_tree.h b/libdimension/kD_splay_tree.h
index daa2ad6..b64be35 100644
--- a/libdimension/kD_splay_tree.h
+++ b/libdimension/kD_splay_tree.h
@@ -56,4 +56,7 @@ dmnsn_kD_splay_node *dmnsn_kD_splay_insert(dmnsn_kD_splay_node *root,
dmnsn_object *object);
void dmnsn_kD_splay(dmnsn_kD_splay_node *node);
+dmnsn_intersection *dmnsn_kD_splay_search(dmnsn_kD_splay_node *root,
+ dmnsn_line ray);
+
#endif /* DIMENSION_IMPL_KD_SPLAY_TREE_H */
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index 21ad1e8..df61d6b 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -229,9 +229,6 @@ dmnsn_raytrace_scene_impl(dmnsn_progress *progress, dmnsn_scene *scene,
return 0;
}
-static double dmnsn_ray_bounding_box(dmnsn_line ray,
- dmnsn_vector min, dmnsn_vector max);
-
/* Shoot a ray, and calculate the color, using `color' as the background */
static dmnsn_color
dmnsn_raytrace_shoot(dmnsn_scene *scene, dmnsn_color color, dmnsn_line ray)
@@ -289,72 +286,3 @@ dmnsn_raytrace_shoot(dmnsn_scene *scene, dmnsn_color color, dmnsn_line ray)
return color;
}
-
-static double
-dmnsn_ray_bounding_box(dmnsn_line ray, dmnsn_vector min, dmnsn_vector max)
-{
- double t = -1.0, t_temp;
- dmnsn_vector p;
-
- if (line.n.x != 0.0) {
- /* x == min.x */
- t_temp = (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
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- {
- t = t_temp;
- }
-
- /* x == max.x */
- t_temp = (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
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- {
- t = t_temp;
- }
- }
-
- if (line.n.y != 0.0) {
- /* y == -1.0 */
- t_temp = (-1.0 - 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
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- {
- t = t_temp;
- }
-
- /* y == 1.0 */
- t_temp = (1.0 - 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
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- {
- t = t_temp;
- }
- }
-
- if (line.n.z != 0.0) {
- /* z == -1.0 */
- t_temp = (-1.0 - 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
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- {
- t = t_temp;
- }
-
- /* z == 1.0 */
- t_temp = (1.0 - 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
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- {
- t = t_temp;
- }
- }
-
- return t;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 06:11:23 +0000