diff options
| -rw-r--r-- | libdimension-python/dimension.pxd | 10 | ||||
| -rw-r--r-- | libdimension-python/dimension.pyx | 27 | ||||
| -rw-r--r-- | libdimension/Makefile.am | 3 | ||||
| -rw-r--r-- | libdimension/dimension/objects.h | 14 | ||||
| -rw-r--r-- | libdimension/triangle.c | 2 | ||||
| -rw-r--r-- | libdimension/triangle_fan.c | 186 |
6 files changed, 239 insertions, 3 deletions
diff --git a/libdimension-python/dimension.pxd b/libdimension-python/dimension.pxd index a7b8a53..0c62df6 100644 --- a/libdimension-python/dimension.pxd +++ b/libdimension-python/dimension.pxd @@ -37,6 +37,15 @@ cdef extern from "../libdimension/dimension.h": double dmnsn_epsilon + ########## + # Malloc # + ########## + + void *dmnsn_malloc(size_t size) + void *dmnsn_realloc(void *ptr, size_t size) + char *dmnsn_strdup(const char *s) + void dmnsn_free(void *ptr) + ######### # Pools # ######### @@ -321,6 +330,7 @@ cdef extern from "../libdimension/dimension.h": dmnsn_object *dmnsn_new_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3]) dmnsn_object *dmnsn_new_smooth_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3], dmnsn_vector normals[3]) + dmnsn_object *dmnsn_new_triangle_fan(dmnsn_pool *pool, dmnsn_vector *vertices, size_t nvertices) dmnsn_object *dmnsn_new_plane(dmnsn_pool *pool, dmnsn_vector normal) dmnsn_object *dmnsn_new_sphere(dmnsn_pool *pool) dmnsn_object *dmnsn_new_cube(dmnsn_pool *pool) diff --git a/libdimension-python/dimension.pyx b/libdimension-python/dimension.pyx index 0c4d665..1ad6d0b 100644 --- a/libdimension-python/dimension.pyx +++ b/libdimension-python/dimension.pyx @@ -1143,6 +1143,33 @@ cdef class Triangle(Object): self._object = dmnsn_new_smooth_triangle(_get_pool(), vertices, normals) Object.__init__(self, *args, **kwargs) +cdef class TriangleFan(Object): + """A triangle.""" + def __init__(self, vertices, *args, **kwargs): + """ + Create a TriangleFan. + + Keyword arguments: + vertices -- the vertices of the fan, starting in the center + + Additionally, TriangleFan() accepts any arguments that Object() accepts. + """ + cdef size_t nvertices = len(vertices) + if nvertices < 3: + raise TypeError("expected at least 3 vertices") + + cdef dmnsn_vector *varray + try: + varray = <dmnsn_vector *>dmnsn_malloc(nvertices*sizeof(dmnsn_vector)) + for i in range(nvertices): + varray[i] = Vector(vertices[i])._v + + self._object = dmnsn_new_triangle_fan(_get_pool(), varray, nvertices) + finally: + dmnsn_free(varray) + + Object.__init__(self, *args, **kwargs) + cdef class Plane(Object): """A plane.""" def __init__(self, normal, double distance, *args, **kwargs): diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am index 00d0549..c488016 100644 --- a/libdimension/Makefile.am +++ b/libdimension/Makefile.am @@ -117,7 +117,8 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS) \ threads.h \ timer.c \ torus.c \ - triangle.c + triangle.c \ + triangle_fan.c libdimension_la_CFLAGS = $(AM_CFLAGS) libdimension_la_LDFLAGS = -version-info 0:0:0 -no-undefined $(AM_LDFLAGS) libdimension_la_LIBADD = diff --git a/libdimension/dimension/objects.h b/libdimension/dimension/objects.h index b5d3bd7..b328025 100644 --- a/libdimension/dimension/objects.h +++ b/libdimension/dimension/objects.h @@ -26,9 +26,10 @@ #include <stdbool.h> /** - * A flat triangle, without normal interpolation. + * A flat triangle. * @param[in] pool The memory pool to allocate from. * @param[in] vertices The corners of the triangle. + * @return A triangle. */ dmnsn_object *dmnsn_new_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3]); @@ -37,10 +38,21 @@ dmnsn_object *dmnsn_new_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3]); * @param[in] pool The memory pool to allocate from. * @param[in] vertices The corners of the triangle. * @param[in] normals The normals at each corner. + * @return A smooth triangle. */ dmnsn_object *dmnsn_new_smooth_triangle(dmnsn_pool *pool, dmnsn_vector vertices[3], dmnsn_vector normals[3]); /** + * A triangle fan. + * @param[in] pool The memory pool to allocate from. + * @param[in] vertices The vertices of the fan, starting in the center. + * @param[in] nvertices The number of vertices. + * @return A triangle fan. + */ +dmnsn_object * +dmnsn_new_triangle_fan(dmnsn_pool *pool, dmnsn_vector vertices[], size_t nvertices); + +/** * A plane. * @param[in] pool The memory pool to allocate from. * @param[in] normal The normal vector of the plane. diff --git a/libdimension/triangle.c b/libdimension/triangle.c index 30ba6c0..6025caa 100644 --- a/libdimension/triangle.c +++ b/libdimension/triangle.c @@ -122,7 +122,7 @@ static inline dmnsn_matrix dmnsn_triangle_basis(dmnsn_vector vertices[3]) { /* - * The new vector space has corners at <0, 1, 0>, <0, 0, 1>, and 0, + * The new vector space has corners at <1, 0, 0>, <0, 1, 0>, and 0, * corresponding to the basis (ab, ac, ab X ac). */ dmnsn_vector ab = dmnsn_vector_sub(vertices[1], vertices[0]); diff --git a/libdimension/triangle_fan.c b/libdimension/triangle_fan.c new file mode 100644 index 0000000..48a64ff --- /dev/null +++ b/libdimension/triangle_fan.c @@ -0,0 +1,186 @@ +/************************************************************************* + * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * <http://www.gnu.org/licenses/>. * + *************************************************************************/ + +/** + * @file + * Triangle fans. See + * http://tavianator.com/2014/05/a-beautiful-raymesh-intersection-algorithm/ + * for a description of the intersection algorithm. + */ + +#include "dimension.h" + +/** Triangle fan type. */ +typedef struct { + dmnsn_object object; + size_t ncoeffs; + double coeffs[][6]; +} dmnsn_triangle_fan; + +/** Change basis from one triangle to the next. */ +static inline dmnsn_vector +dmnsn_change_basis(const double coeffs[6], dmnsn_vector v) +{ + return dmnsn_new_vector( + coeffs[0]*v.x + coeffs[1]*v.z + v.y, + coeffs[2]*v.x + coeffs[3]*v.z, + coeffs[4]*v.x + coeffs[5]*v.z + ); +} + +/** Change basis from one triangle to the next for a normal vector. */ +static inline dmnsn_vector +dmnsn_change_normal_basis(const double coeffs[6], dmnsn_vector n) +{ + return dmnsn_new_vector( + coeffs[0]*n.x + coeffs[2]*n.y + coeffs[4]*n.z, + n.x, + coeffs[1]*n.x + coeffs[3]*n.y + coeffs[5]*n.z + ); +} + +/** Triangle intersection callback. */ +static bool +dmnsn_triangle_fan_intersection_fn(const dmnsn_object *object, dmnsn_line l, dmnsn_intersection *intersection) +{ + const dmnsn_triangle_fan *fan = (const dmnsn_triangle_fan *)object; + + 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; + + double best_t = INFINITY; + if (t >= 0.0 && u >= 0.0 && v >= 0.0 && u + v <= 1.0) { + best_t = t; + } + + dmnsn_vector normal = dmnsn_z; + dmnsn_vector best_normal = normal; + + for (size_t i = 0; i < fan->ncoeffs; ++i) { + const double *coeffs = fan->coeffs[i]; + l = dmnsn_new_line(dmnsn_change_basis(coeffs, l.x0), dmnsn_change_basis(coeffs, l.n)); + normal = dmnsn_change_normal_basis(coeffs, normal); + + t = -l.x0.z/l.n.z; + u = l.x0.x + t*l.n.x; + v = l.x0.y + t*l.n.y; + + if (t >= 0.0 && t < best_t && u >= 0.0 && v >= 0.0 && u + v <= 1.0) { + best_t = t; + best_normal = normal; + } + } + + if (!isinf(best_t)) { + intersection->t = t; + intersection->normal = best_normal; + return true; + } + + return false; +} + +/** Triangle fan inside callback. */ +static bool +dmnsn_triangle_fan_inside_fn(const dmnsn_object *object, dmnsn_vector point) +{ + return false; +} + +/** Triangle fan bounding callback. */ +static dmnsn_bounding_box +dmnsn_triangle_fan_bounding_fn(const dmnsn_object *object, dmnsn_matrix trans) +{ + const dmnsn_triangle_fan *fan = (const dmnsn_triangle_fan *)object; + + dmnsn_vector a = dmnsn_transform_point(trans, dmnsn_zero); + dmnsn_vector b = dmnsn_transform_point(trans, dmnsn_x); + dmnsn_vector c = dmnsn_transform_point(trans, dmnsn_y); + + dmnsn_bounding_box box = dmnsn_new_bounding_box(a, a); + box = dmnsn_bounding_box_swallow(box, b); + box = dmnsn_bounding_box_swallow(box, c); + + dmnsn_matrix P = trans; + + for (size_t i = 0; i < fan->ncoeffs; ++i) { + const double *coeffs = fan->coeffs[i]; + dmnsn_matrix incremental = dmnsn_new_matrix(coeffs[0], 1.0, coeffs[1], 0.0, + coeffs[2], 0.0, coeffs[3], 0.0, + coeffs[4], 0.0, coeffs[5], 0.0); + P = dmnsn_matrix_mul(P, dmnsn_matrix_inverse(incremental)); + dmnsn_vector d = dmnsn_transform_point(P, dmnsn_y); + box = dmnsn_bounding_box_swallow(box, d); + } + + return box; +} + +/** Triangle fan vtable. */ +static dmnsn_object_vtable dmnsn_triangle_fan_vtable = { + .intersection_fn = dmnsn_triangle_fan_intersection_fn, + .inside_fn = dmnsn_triangle_fan_inside_fn, + .bounding_fn = dmnsn_triangle_fan_bounding_fn, +}; + +dmnsn_object * +dmnsn_new_triangle_fan(dmnsn_pool *pool, dmnsn_vector vertices[], size_t nvertices) +{ + dmnsn_assert(nvertices >= 3, "Not enough vertices for one triangle"); + + size_t ncoeffs = nvertices - 3; + dmnsn_triangle_fan *fan = dmnsn_palloc(pool, sizeof(dmnsn_triangle_fan) + ncoeffs*sizeof(double[6])); + fan->ncoeffs = ncoeffs; + + dmnsn_object *object = &fan->object; + dmnsn_init_object(object); + object->vtable = &dmnsn_triangle_fan_vtable; + object->bounding_box.min = dmnsn_zero; + object->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 0.0); + + /* Compute the initial matrix and the coefficients */ + dmnsn_vector a = vertices[0]; + dmnsn_vector ab = dmnsn_vector_sub(vertices[1], a); + dmnsn_vector ac = dmnsn_vector_sub(vertices[2], a); + dmnsn_vector normal = dmnsn_vector_cross(ab, ac); + dmnsn_matrix P = dmnsn_new_matrix4(ab, ac, normal, a); + object->intrinsic_trans = P; + + for (size_t i = 0; i < ncoeffs; ++i) { + ab = ac; + ac = dmnsn_vector_sub(vertices[i + 3], a); + normal = dmnsn_vector_cross(ab, ac); + + dmnsn_matrix newP = dmnsn_new_matrix4(ab, ac, normal, a); + dmnsn_matrix incremental = dmnsn_matrix_mul(dmnsn_matrix_inverse(newP), P); + double *coeffs = fan->coeffs[i]; + coeffs[0] = incremental.n[0][0]; + coeffs[1] = incremental.n[0][2]; + coeffs[2] = incremental.n[1][0]; + coeffs[3] = incremental.n[1][2]; + coeffs[4] = incremental.n[2][0]; + coeffs[5] = incremental.n[2][2]; + + P = newP; + } + + return object; +} |