+
+static void flip_hit(struct hit *hit)
+{
+ hit->nx = -hit->nx;
+ hit->ny = -hit->ny;
+ hit->nz = -hit->nz;
+}
+
+static struct hinterv *interval_union(struct hinterv *a, struct hinterv *b)
+{
+ struct hinterv *res, *res2;
+
+ if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+ /* disjoint */
+ res = alloc_hits(2);
+ res2 = res->next;
+
+ if(a->end[0].t < b->end[0].t) {
+ *res = *a;
+ *res2 = *b;
+ } else {
+ *res = *b;
+ *res2 = *a;
+ }
+ res->next = res2;
+ res2->next = 0;
+ return res;
+ }
+
+ res = alloc_hits(1);
+ res->end[0] = a->end[0].t <= b->end[0].t ? a->end[0] : b->end[0];
+ res->end[1] = a->end[1].t >= b->end[1].t ? a->end[1] : b->end[1];
+ return res;
+}
+
+static struct hinterv *interval_isect(struct hinterv *a, struct hinterv *b)
+{
+ struct hinterv *res;
+
+ if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+ /* disjoint */
+ return 0;
+ }
+
+ res = alloc_hits(1);
+
+ if(a->end[0].t <= b->end[0].t && a->end[1].t >= b->end[1].t) {
+ /* B in A */
+ *res = *a;
+ res->next = 0;
+ return res;
+ }
+ if(a->end[0].t > b->end[0].t && a->end[1].t < b->end[1].t) {
+ /* A in B */
+ *res = *b;
+ res->next = 0;
+ return res;
+ }
+
+ /* partial overlap */
+ if(a->end[0].t < b->end[1].t) {
+ res->end[0] = b->end[1];
+ res->end[1] = a->end[0];
+ } else {
+ res->end[0] = a->end[1];
+ res->end[1] = a->end[0];
+ }
+ return res;
+}
+
+static struct hinterv *interval_sub(struct hinterv *a, struct hinterv *b)
+{
+ struct hinterv *res;
+
+ if(a->end[0].t >= b->end[0].t && a->end[1].t <= b->end[1].t) {
+ /* A in B */
+ return 0;
+ }
+
+ if(a->end[0].t < b->end[0].t && a->end[1].t > b->end[1].t) {
+ /* B in A */
+ res = alloc_hits(2);
+ res->end[0] = a->end[0];
+ res->end[1] = b->end[0];
+ res->next->end[0] = b->end[1];
+ res->next->end[1] = a->end[1];
+ return res;
+ }
+
+ res = alloc_hits(1);
+
+ if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+ /* disjoint */
+ *res = *a;
+ res->next = 0;
+ return res;
+ }
+
+ /* partial overlap */
+ if(a->end[0].t <= b->end[0].t) {
+ res->end[0] = a->end[0];
+ res->end[1] = b->end[0];
+ } else {
+ res->end[0] = b->end[1];
+ res->end[1] = a->end[1];
+ }
+
+ flip_hit(res->end + 0);
+ flip_hit(res->end + 1);
+ return res;
+}