#include "config.h" #include "arrays.h" #include "point.h" #include "vector.h" #include "eval.h" #include "object.h" #include "matrix.h" #include "intersect.h" /* Operations on interval lists */ #define POS_INFTY HUGE_VAL struct intervlist { flt beg; struct object * obeg; flt end; struct object * oend; struct intervlist * next; }; typedef struct intervlist * intervlist; static intervlist cons(flt b, struct object * ob, flt e, struct object * oe, intervlist next) { intervlist l = arena_alloc(sizeof(struct intervlist)); l->beg = b; l->obeg = ob; l->end = e; l->oend = oe; l->next = next; return l; } static intervlist conshead(intervlist i, intervlist next) { intervlist l = arena_alloc(sizeof(struct intervlist)); l->beg = i->beg; l->obeg = i->obeg; l->end = i->end; l->oend = i->oend; l->next = next; return l; } static intervlist union_intervals(intervlist l1, intervlist l2) { flt beg; struct object * obeg; if (l1 == NULL) return l2; if (l2 == NULL) return l1; if (l1->end < l2->beg) /* int1 strictly before int2 */ return conshead(l1, union_intervals(l1->next, l2)); if (l2->end < l1->beg) /* int2 strictly before int1 */ return conshead(l2, union_intervals(l1, l2->next)); /* int1 and int2 overlap, merge */ if (l1->beg < l2->beg) { beg = l1->beg; obeg = l1->obeg; } else { beg = l2->beg; obeg = l2->obeg; } if (l1->end < l2->end) return union_intervals(l1->next, cons(beg, obeg, l2->end, l2->oend, l2->next)); else return union_intervals(cons(beg, obeg, l1->end, l1->oend, l1->next), l2->next); } static intervlist intersect_intervals(intervlist l1, intervlist l2) { flt beg; struct object * obeg; if (l1 == NULL) return NULL; if (l2 == NULL) return NULL; if (l1->end < l2->beg) /* int1 strictly before int2 */ return intersect_intervals(l1->next, l2); if (l2->end < l1->beg) /* int2 strictly before int1 */ return intersect_intervals(l1, l2->next); /* int1 and int2 overlap, add intersection */ if (l1->beg > l2->beg) { beg = l1->beg; obeg = l1->obeg; } else { beg = l2->beg; obeg = l2->obeg; } if (l1->end < l2->end) return cons(beg, obeg, l1->end, l1->oend, intersect_intervals(l1->next, l2)); else return cons(beg, obeg, l2->end, l2->oend, intersect_intervals(l1, l2->next)); } static intervlist difference_intervals(intervlist l1, intervlist l2) { intervlist l; if (l1 == NULL) return NULL; if (l2 == NULL) return l1; if (l1->end < l2->beg) /* int1 strictly before int2, keep int1 */ return conshead(l1, difference_intervals(l1->next, l2)); if (l2->end < l1->beg) /* int2 strictly before int1, throw int2 away */ return difference_intervals(l1, l2->next); /* int and int2 overlap */ if (l1->end > l2->end) /* int1 extends beyond int2, add segment [l2->end,l1->end] */ l = difference_intervals(cons(l2->end, l2->oend, l1->end, l1->oend, l1->next), l2->next); else /* int2 doesn't extend beyond int2, nothing to add */ l = difference_intervals(l1->next, l2); if (l1->beg < l2->beg) /* int1 starts before l2, add segment [l1->beg,l2->beg] */ l = cons(l1->beg, l1->obeg, l2->beg, l2->obeg, l); return l; } /* Intersections between rays (p + tv) and basic objects (bobj) */ static intervlist intersect_ray_plane(struct object * bobj, struct point * p, struct vector * v) { if (p->y >= 0) if (v->dy >= 0) return NULL; else return cons(- p->y / v->dy, bobj, POS_INFTY, bobj, NULL); else if (v->dy >= 0) return cons(0, bobj, - p->y / v->dy, bobj, NULL); else return cons(0, bobj, POS_INFTY, bobj, NULL); } static intervlist intersect_ray_sphere(struct object * bobj, struct point * p, struct vector * v) { flt a, b, c, d, sq, t0, t1, tswap; a = v->dx * v->dx + v->dy * v->dy + v->dz * v->dz; b = p->x * v->dx + p->y * v->dy + p->z * v->dz; c = p->x * p->x + p->y * p->y + p->z * p->z - 1.0; d = b * b - a * c; if (d <= 0) return NULL; sq = sqrt(d); /* Numerically stable solution of quadratic */ if (b >= 0) { t0 = c / (- b - sq); t1 = (- b - sq) / a; } else { t0 = c / (- b + sq); t1 = (- b + sq) / a; } if (t0 >= t1) { tswap = t0; t0 = t1; t1 = tswap; } if (t1 <= 0) { assert (t0 <= 0); return NULL; } if (t0 >= 0) { assert (t1 >= 0); return cons(t0, bobj, t1, bobj, NULL); } return cons(0, bobj, t1, bobj, NULL); } static intervlist intersect_ray_slice(struct object * bobj, flt pc, flt vc) { if (pc > 1.0) { if (vc >= 0.0) return NULL; else return cons((1.0 - pc) / vc, bobj, - pc / vc, bobj, NULL); } if (pc < 0.0) { if (vc <= 0.0) return NULL; else return cons(- pc / vc, bobj, (1.0 - pc) / vc, bobj, NULL); } if (vc == 0.0) return cons(0.0, bobj, POS_INFTY, bobj, NULL); if (vc > 0.0) return cons(0.0, bobj, (1.0 - pc) / vc, bobj, NULL); else return cons(0.0, bobj, - pc / vc, bobj, NULL); } static intervlist intersect_ray_cube(struct object * bobj, struct point * p, struct vector * v) { return intersect_intervals(intersect_ray_slice(bobj, p->x, v->dx), intersect_intervals(intersect_ray_slice(bobj, p->y, v->dy), intersect_ray_slice(bobj, p->z, v->dz))); } static intervlist intersect_ray_infinite_cylinder(struct object * bobj, struct point * p, struct vector * v) { flt a, b, c, d, sq, t0, t1, tswap; a = v->dx * v->dx + v->dz * v->dz; b = p->x * v->dx + p->z * v->dz; c = p->x * p->x + p->z * p->z - 1.0; d = b * b - a * c; if (d <= 0.0) return NULL; sq = sqrt(d); if (b >= 0.0) { t0 = c / (- b - sq); t1 = (- b - sq) / a; } else { t0 = c / (- b + sq); t1 = (- b + sq) / a; } if (t0 >= t1) { tswap = t0; t0 = t1; t1 = tswap; } if (t1 <= 0.0) { assert (t0 <= 0.0); return NULL; } if (t0 >= 0.0) { assert (t1 >= 0.0); return cons(t0, bobj, t1, bobj, NULL); } return cons(0.0, bobj, t1, bobj, NULL); } static intervlist intersect_ray_cylinder(struct object * bobj, struct point * p, struct vector * v) { return intersect_intervals(intersect_ray_infinite_cylinder(bobj, p, v), intersect_ray_slice(bobj, p->y, v->dy)); } static intervlist intersect_ray_infinite_cone(struct object * bobj, struct point * p, struct vector * v) { flt a, b, c, d, sq, t, t0, t1, tswap; a = v->dx * v->dx - v->dy * v->dy + v->dz * v->dz; b = p->x * v->dx - p->y * v->dy + p->z * v->dz; c = p->x * p->x - p->y * p->y + p->z * p->z; if (a == 0.0) { if (b == 0.0) return NULL; t = - 0.5 * c / b; if (c < 0.0) { if (t <= 0.0) return cons(0.0, bobj, POS_INFTY, bobj, NULL); else return cons(0.0, bobj, t, bobj, NULL); } if (t <= 0.0) return NULL; else return cons(t, bobj, POS_INFTY, bobj, NULL); } d = b * b - a * c; if (d <= 0.0) return NULL; sq = sqrt(d); if (b >= 0.0) { t0 = c / (- b - sq); t1 = (- b - sq) / a; } else { t0 = c / (- b + sq); t1 = (- b + sq) / a; } if (t0 >= t1) { tswap = t0; t0 = t1; t1 = tswap; } if (t1 <= 0.0) { assert (t0 <= 0.0); if (c < 0.0) return cons(0.0, bobj, POS_INFTY, bobj, NULL); else return NULL; } if (t0 >= 0.0) { assert (t1 >= 0.0); if (c < 0.0) return cons(0.0, bobj, t0, bobj, cons (t1, bobj, POS_INFTY, bobj, NULL)); else return cons(t0, bobj, t1, bobj, NULL); } if (c < 0.0) return cons(0.0, bobj, t1, bobj, NULL); else return cons(t1, bobj, POS_INFTY, bobj, NULL); } static intervlist intersect_ray_cone(struct object * bobj, struct point * p, struct vector * v) { return intersect_intervals(intersect_ray_infinite_cone(bobj, p, v), intersect_ray_slice(bobj, p->y, v->dy)); } /* Approximate test based on bounding sphere */ static inline int inside_bs(struct point * p, struct vector * v, struct object * obj) { flt x, y, z, a, b, c; assert(obj->radius >= 0.0); if (obj->radius >= POS_INFTY) return 1; /* Shift origin to obj.center */ x = p->x - obj->center.x; y = p->y - obj->center.y; z = p->z - obj->center.z; /* Check whether quadratic has positive discriminant */ a = v->dx * v->dx + v->dy * v->dy + v->dz * v->dz; b = x * v->dx + y * v->dy + z * v->dz; c = x * x + y * y + z * z - obj->radius * obj->radius; return (b * b > a * c); } /* Interval list representing the intersection of the given ray and the given composite object */ static intervlist intersect_ray_object(struct point * p, struct vector * v, struct object * obj) { #define CONVERT_V_P \ apply_to_point(obj->world2obj, p, &p2); \ apply_to_vect(obj->world2obj, v, &v2) struct point p2; struct vector v2; intervlist res; /* Fast, approximate test based on bounding sphere */ if (! inside_bs(p, v, obj)) return NULL; /* Slow, exact test */ switch (obj->kind) { case Cone: CONVERT_V_P; res = intersect_ray_cone(obj, &p2, &v2); break; case Cube: CONVERT_V_P; res = intersect_ray_cube(obj, &p2, &v2); break; case Cylinder: CONVERT_V_P; res = intersect_ray_cylinder(obj, &p2, &v2); break; case Plane: CONVERT_V_P; res = intersect_ray_plane(obj, &p2, &v2); break; case Sphere: CONVERT_V_P; res = intersect_ray_sphere(obj, &p2, &v2); break; case Union: res = union_intervals(intersect_ray_object(p, v, obj->o1), intersect_ray_object(p, v, obj->o2)); break; case Intersection: res = intersect_intervals(intersect_ray_object(p, v, obj->o1), intersect_ray_object(p, v, obj->o2)); break; case Difference: res = difference_intervals(intersect_ray_object(p, v, obj->o1), intersect_ray_object(p, v, obj->o2)); break; default: assert(0); } #undef CONVERT_V_P return res; } /* Return the closest base object intersecting the given ray, and the curvilinear abscissa t of the intersection point. Return NULL if no intersection. Return t = 0.0 if the viewpoint (origin of the ray) is inside an object. */ struct object * intersect_ray(struct point * p, struct vector * v, struct object * obj, int initial, /*out*/ flt * t) { intervlist l = intersect_ray_object(p, v, obj); if (l == NULL) return NULL; assert(l->beg >= 0.0); if (l->beg <= 0.0 && !initial) { /* skip first intersection */ l = l->next; if (l == NULL) return NULL; } *t = l->beg; return l->obeg; }