summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--libdimension/triangle.c104
1 files changed, 67 insertions, 37 deletions
diff --git a/libdimension/triangle.c b/libdimension/triangle.c
index f7081b4..87efacc 100644
--- a/libdimension/triangle.c
+++ b/libdimension/triangle.c
@@ -20,37 +20,33 @@
/**
* @file
- * Triangles.
+ * Triangles. See
+ * http://tavianator.com/2014/05/a-beautiful-raytriangle-intersection-method/
+ * for a description of the intersection algorithm.
*/
#include "dimension.h"
-/** Triangle type. */
-typedef struct {
- dmnsn_object object;
- dmnsn_vector na, nab, nac;
-} dmnsn_triangle;
+/** Optimized ray/triangle intersection test. */
+static inline bool
+dmnsn_ray_triangle_intersection(dmnsn_line l, double *t, double *u, double *v)
+{
+ /* See the change of basis in dmnsn_triangle_basis() */
+ *t = -l.x0.z/l.n.z;
+ *u = l.x0.x + (*t)*l.n.x;
+ *v = l.x0.y + (*t)*l.n.y;
+ return *t >= 0.0 && *u >= 0.0 && *v >= 0.0 && *u + *v <= 1.0;
+}
/** Triangle intersection callback. */
static bool
dmnsn_triangle_intersection_fn(const dmnsn_object *object, dmnsn_line l,
dmnsn_intersection *intersection)
{
- const dmnsn_triangle *triangle = (const dmnsn_triangle *)object;
-
- /* See the change of basis in dmnsn_new_triangle() */
- double t = -l.x0.z/l.n.z;
- double u = l.x0.x + t*l.n.x;
- double v = l.x0.y + t*l.n.y;
- if (t >= 0.0 && u >= 0.0 && v >= 0.0 && u + v <= 1.0) {
- intersection->t = t;
- intersection->normal = dmnsn_vector_add(
- triangle->na,
- dmnsn_vector_add(
- dmnsn_vector_mul(u, triangle->nab),
- dmnsn_vector_mul(v, triangle->nac)
- )
- );
+ double t, u, v;
+ if (dmnsn_ray_triangle_intersection(l, &t, &u, &v)) {
+ intersection->t = t;
+ intersection->normal = dmnsn_z;
return true;
}
@@ -64,45 +60,79 @@ dmnsn_triangle_inside_fn(const dmnsn_object *triangle, dmnsn_vector point)
return false;
}
-dmnsn_object *
-dmnsn_new_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3])
+/** Smooth triangle type. */
+typedef struct {
+ dmnsn_object object;
+ dmnsn_vector na, nab, nac;
+} dmnsn_smooth_triangle;
+
+/** Smooth triangle intersection callback. */
+static bool
+dmnsn_smooth_triangle_intersection_fn(const dmnsn_object *object, dmnsn_line l,
+ dmnsn_intersection *intersection)
{
- dmnsn_vector normal = dmnsn_vector_cross(
- dmnsn_vector_sub(vertices[1], vertices[0]),
- dmnsn_vector_sub(vertices[2], vertices[0])
- );
- dmnsn_vector normals[] = { normal, normal, normal };
- return dmnsn_new_smooth_triangle(pool, vertices, normals);
+ const dmnsn_smooth_triangle *triangle = (const dmnsn_smooth_triangle *)object;
+
+ double t, u, v;
+ if (dmnsn_ray_triangle_intersection(l, &t, &u, &v)) {
+ intersection->t = t;
+ intersection->normal = dmnsn_vector_add(
+ triangle->na,
+ dmnsn_vector_add(
+ dmnsn_vector_mul(u, triangle->nab),
+ dmnsn_vector_mul(v, triangle->nac)
+ )
+ );
+ return true;
+ }
+
+ return false;
}
-/* Allocate a new triangle */
-dmnsn_object *
-dmnsn_new_smooth_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3], dmnsn_vector normals[3])
+/** Make a change-of-basis matrix. */
+static inline dmnsn_matrix
+dmnsn_triangle_basis(dmnsn_vector vertices[3])
{
/*
- * Make a change-of-basis matrix
- *
* The new vector space has corners at <0, 1, 0>, <0, 0, 1>, and 0,
* corresponding to the basis (ab, ac, ab X ac).
*/
dmnsn_vector ab = dmnsn_vector_sub(vertices[1], vertices[0]);
dmnsn_vector ac = dmnsn_vector_sub(vertices[2], vertices[0]);
dmnsn_vector normal = dmnsn_vector_cross(ab, ac);
- dmnsn_matrix P = dmnsn_new_matrix4(ab, ac, normal, vertices[0]);
+ return dmnsn_new_matrix4(ab, ac, normal, vertices[0]);
+}
+
+dmnsn_object *
+dmnsn_new_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3])
+{
+ dmnsn_object *object = dmnsn_new_object(pool);
+ object->intersection_fn = dmnsn_triangle_intersection_fn;
+ object->inside_fn = dmnsn_triangle_inside_fn;
+ object->bounding_box.min = dmnsn_zero;
+ object->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 0.0);
+ object->intrinsic_trans = dmnsn_triangle_basis(vertices);
+ return object;
+}
+
+dmnsn_object *
+dmnsn_new_smooth_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3], dmnsn_vector normals[3])
+{
+ dmnsn_matrix P = dmnsn_triangle_basis(vertices);
/* Transform the given normals. */
dmnsn_vector na = dmnsn_vector_normalized(dmnsn_transform_normal(P, normals[0]));
dmnsn_vector nb = dmnsn_vector_normalized(dmnsn_transform_normal(P, normals[1]));
dmnsn_vector nc = dmnsn_vector_normalized(dmnsn_transform_normal(P, normals[2]));
- dmnsn_triangle *triangle = DMNSN_PALLOC(pool, dmnsn_triangle);
+ dmnsn_smooth_triangle *triangle = DMNSN_PALLOC(pool, dmnsn_smooth_triangle);
triangle->na = na;
triangle->nab = dmnsn_vector_sub(nb, na);
triangle->nac = dmnsn_vector_sub(nc, na);
dmnsn_object *object = &triangle->object;
dmnsn_init_object(pool, object);
- object->intersection_fn = dmnsn_triangle_intersection_fn;
+ object->intersection_fn = dmnsn_smooth_triangle_intersection_fn;
object->inside_fn = dmnsn_triangle_inside_fn;
object->bounding_box.min = dmnsn_zero;
object->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 0.0);