Skip to content

Instantly share code, notes, and snippets.

@tavianator
Last active May 1, 2022 14:12
Show Gist options
  • Save tavianator/132d081ed4d410c755fd to your computer and use it in GitHub Desktop.
Save tavianator/132d081ed4d410c755fd to your computer and use it in GitHub Desktop.
Ray/bounding box intersection test program
/****************************************************************************
* Copyright (C) 2015 Tavian Barnes <tavianator@tavianator.com> *
* *
* Permission to use, copy, modify, and/or distribute this software for any *
* purpose with or without fee is hereby granted. *
* *
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
****************************************************************************/
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double origin[3];
double dir_inv[3];
} ray;
typedef struct {
double min[3];
double max[3];
} box;
static inline double min(double x, double y) {
#if SSE
return x < y ? x : y;
#elif IEEE
return y != y ? x : (x < y ? x : y);
#elif JAVA
return x != x ? x : (x < y ? x : y);
#endif
}
static inline double max(double x, double y) {
#if SSE
return x > y ? x : y;
#elif IEEE
return y != y ? x : (x > y ? x : y);
#elif JAVA
return x != x ? x : (x > y ? x : y);
#endif
}
bool intersection(box b, ray r) {
double tmin = -INFINITY, tmax = INFINITY;
for (int i = 0; i < 3; ++i) {
double t1 = (b.min[i] - r.origin[i])*r.dir_inv[i];
double t2 = (b.max[i] - r.origin[i])*r.dir_inv[i];
#if SSE
tmin = max(tmin, min(min(t1, t2), tmax));
tmax = min(tmax, max(max(t1, t2), tmin));
#else
tmin = max(tmin, min(t1, t2));
tmax = min(tmax, max(t1, t2));
#endif
}
return tmax > max(tmin, 0.0);
}
void check_reflections(ray r, bool expected, int* count, int* total) {
box b = {{-1.0, -1.0, -1.0}, {1.0, 1.0, 1.0}};
for (int i = 0; i < 1 << 3; ++i) {
ray rr;
for (int j = 0; j < 3; ++j) {
if (i & (1 << j)) {
rr.origin[j] = -r.origin[j];
rr.dir_inv[j] = -r.dir_inv[j];
} else {
rr.origin[j] = r.origin[j];
rr.dir_inv[j] = r.dir_inv[j];
}
}
if (intersection(b, rr) != expected) {
printf("(%g, %g, %g) + t*(%g, %g, %g): \t%s\n",
rr.origin[0], rr.origin[1], rr.origin[2],
rr.dir_inv[0], rr.dir_inv[1], rr.dir_inv[2],
!expected ? "true" : "false");
} else {
++*count;
}
++*total;
}
}
void check_permutations(ray r, bool expected, int* count, int* total) {
static const int permutations[][3] = {
{0, 1, 2},
{0, 2, 1},
{1, 0, 2},
{1, 2, 0},
{2, 0, 1},
{2, 1, 0},
};
for (int i = 0; i < 6; ++i) {
ray rr;
for (int j = 0; j < 3; ++j) {
rr.origin[j] = r.origin[permutations[i][j]];
rr.dir_inv[j] = r.dir_inv[permutations[i][j]];
}
check_reflections(rr, expected, count, total);
}
}
void check_scaled(double factor, bool expected, int* count, int* total) {
ray r;
r.origin[1] = factor;
r.origin[2] = -2.0;
r.dir_inv[2] = 1.0;
for (int i = -1; i <= 1; ++i) {
r.origin[0] = factor*i;
for (int j = -1; j <= 1; j += 2) {
r.dir_inv[1] = j*INFINITY;
for (int k = 0; k <= 1 - abs(i); ++k) {
r.dir_inv[0] = 8.0/k;
check_permutations(r, expected, count, total);
r.dir_inv[0] = -r.dir_inv[0];
check_permutations(r, expected, count, total);
}
}
}
}
int main() {
int count = 0, total = 0;
check_scaled(1.01, false, &count, &total);
check_scaled(1.00, false, &count, &total);
check_scaled(0.99, true, &count, &total);
printf("%d/%d\n", count, total);
return count == total ? EXIT_SUCCESS : EXIT_FAILURE;
}
@SkybuckFlying
Copy link

The code is not suited for "ray segment" intersection of a box. But if you can adept it, try ! I also recommend more test cases ! ;)

@tavianator
Copy link
Author

tavianator commented May 1, 2022

@SkybuckFlying For a line segment, you can just start with tmin and tmax equal to the start and end of the segment in intersection().

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment