From 4d27a7f75bc9b0e45ea92aa05f84f61971f10942 Mon Sep 17 00:00:00 2001 From: Barak Itkin Date: Thu, 26 Apr 2012 18:10:12 +0300 Subject: [PATCH] Implement P2trMesh --- refine/math.c | 45 ++++++++++----- refine/math.h | 21 +++++++ refine/mesh.c | 149 +++++++++++++++++++++++++++++++++++++++++++++++++ refine/mesh.h | 28 +++++----- refine/utils.h | 5 +- 5 files changed, 218 insertions(+), 30 deletions(-) create mode 100644 refine/mesh.c diff --git a/refine/math.c b/refine/math.c index 1c26159..a2e32d7 100644 --- a/refine/math.c +++ b/refine/math.c @@ -63,14 +63,16 @@ p2tr_matrix_det4 (gdouble a00, gdouble a01, gdouble a02, gdouble a03, * * http://www.blackpawn.com/texts/pointinpoly/default.html */ -#define INTRIANGLE_EPSILON 0e-9 - -P2trInTriangle -p2tr_math_intriangle(const P2trVector2 *A, - const P2trVector2 *B, - const P2trVector2 *C, - const P2trVector2 *P) +void +p2tr_math_triangle_barcycentric (const P2trVector2 *A, + const P2trVector2 *B, + const P2trVector2 *C, + const P2trVector2 *P, + gdouble *u, + gdouble *v) { + gdouble dot00, dot01, dot02, dot11, dot12, invDenom; + /* Compute the vectors offsetted so that A is the origin */ P2trVector2 v0, v1, v2; p2tr_vector2_sub(C, A, &v0); @@ -78,17 +80,30 @@ p2tr_math_intriangle(const P2trVector2 *A, p2tr_vector2_sub(P, A, &v2); /* Compute dot products */ - double dot00 = VECTOR2_DOT(&v0, &v0); - double dot01 = VECTOR2_DOT(&v0, &v1); - double dot02 = VECTOR2_DOT(&v0, &v2); - double dot11 = VECTOR2_DOT(&v1, &v1); - double dot12 = VECTOR2_DOT(&v1, &v2); + dot00 = VECTOR2_DOT(&v0, &v0); + dot01 = VECTOR2_DOT(&v0, &v1); + dot02 = VECTOR2_DOT(&v0, &v2); + dot11 = VECTOR2_DOT(&v1, &v1); + dot12 = VECTOR2_DOT(&v1, &v2); /* Compute barycentric coordinates */ - double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); - double u = (dot11 * dot02 - dot01 * dot12) * invDenom; - double v = (dot00 * dot12 - dot01 * dot02) * invDenom; + invDenom = 1 / (dot00 * dot11 - dot01 * dot01); + *u = (dot11 * dot02 - dot01 * dot12) * invDenom; + *v = (dot00 * dot12 - dot01 * dot02) * invDenom; +} + +#define INTRIANGLE_EPSILON 0e-9 + +P2trInTriangle +p2tr_math_intriangle (const P2trVector2 *A, + const P2trVector2 *B, + const P2trVector2 *C, + const P2trVector2 *P) +{ + gdouble u, v; + p2tr_math_triangle_barcycentric(A, B, C, P, &u, &v); + /* Check if point is in triangle - i.e. whether (u + v) < 1 and both * u and v are positive */ if ((u >= INTRIANGLE_EPSILON) && (v >= INTRIANGLE_EPSILON) && (u + v < 1 - INTRIANGLE_EPSILON)) diff --git a/refine/math.h b/refine/math.h index 266aaa9..d75c004 100644 --- a/refine/math.h +++ b/refine/math.h @@ -19,6 +19,27 @@ typedef enum P2TR_INTRIANGLE_IN = 1 } P2trInTriangle; +/** + * Return the barycentric coordinates of a point inside a triangle. This + * means that the computation returns @ref u and @ref v so that the + * following equation is satisfied: + * {{{ AP = u * AB + v * AC }}} + * + * @param[in] A The first point of the triangle + * @param[in] B The second point of the triangle + * @param[in] C The third point of the triangle + * @param[in] P The point whose barycentric coordinates should be + * computed + * @param[out] u The first barycentric coordinate + * @param[out] v The second barycentric coordinate + */ +void p2tr_math_triangle_barcycentric (const P2trVector2 *A, + const P2trVector2 *B, + const P2trVector2 *C, + const P2trVector2 *P, + gdouble *u, + gdouble *v); + P2trInTriangle p2tr_math_intriangle (const P2trVector2 *A, const P2trVector2 *B, const P2trVector2 *C, diff --git a/refine/mesh.c b/refine/mesh.c new file mode 100644 index 0000000..bb10c80 --- /dev/null +++ b/refine/mesh.c @@ -0,0 +1,149 @@ +#include +#include "utils.h" + +#include "mesh.h" +#include "point.h" +#include "edge.h" +#include "triangle.h" + +P2trMesh* +p2tr_mesh_new (void) +{ + P2trMesh *mesh = g_slice_new (P2trMesh); + + mesh->refcount = 1; + mesh->edges = p2tr_hash_set_new_default (); + mesh->points = p2tr_hash_set_new_default (); + mesh->triangles = p2tr_hash_set_new_default (); + + mesh->_is_clearing_now = FALSE; + + return mesh; +} + +P2trPoint* +p2tr_mesh_new_point (P2trMesh *self, + const P2trVector2 *c) +{ + P2trPoint *pt = p2tr_point_new (c); + + pt->mesh = self; + p2tr_mesh_ref (self); + + p2tr_hash_set_insert (self->points, pt); + p2tr_point_ref (pt); + + return pt; +} + +P2trEdge* +p2tr_mesh_new_edge (P2trMesh *self, + P2trPoint *start, + P2trPoint *end, + gboolean constrained) +{ + P2trEdge *ed = p2tr_edge_new (start, end, constrained); + + p2tr_hash_set_insert (self->edges, ed); + p2tr_pdge_ref (ed); + + return ed; +} + +P2trTriangle* +p2tr_mesh_new_triangle (P2trMesh *self, + P2trEdge *AB, + P2trEdge *BC, + P2trEdge *CA) +{ + P2trTriangle *tr = p2tr_triangle_new (AB, BC, CA); + + p2tr_hash_set_insert (self->triangles, tr); + p2tr_pdge_ref (tr); + + return tr; +} + +void +p2tr_mesh_on_point_removed (P2trMesh *self, + P2trPoint *point) +{ + if (self != point->mesh) + p2tr_exception_programmatic ("Point does not belong to this mesh!"); + + point->mesh = NULL; + p2tr_mesh_unref (self); + + if (! self->_is_clearing_now) + p2tr_hash_set_remove (self->points, point); + p2tr_point_unref (point); +} + +void +p2tr_mesh_on_edge_removed (P2trMesh *self, + P2trEdge *edge) +{ + if (! self->_is_clearing_now) + p2tr_hash_set_remove (self->edges, edge); + p2tr_edge_unref (edge); +} + +void +p2tr_mesh_on_triangle_removed (P2trMesh *self, + P2trTriangle *triangle) +{ + if (! self->_is_clearing_now) + p2tr_hash_set_remove (self->triangles, triangle); + p2tr_triangle_unref (triangle); +} + +void +p2tr_mesh_clear (P2trMesh *self) +{ + P2trHashSetIter iter; + gpointer temp; + + self->_is_clearing_now = TRUE; + + p2tr_hash_set_iter_init (&iter, self->triangles); + while (p2tr_hash_set_iter_next (&iter, &temp)) + p2tr_triangle_remove ((P2trTriangle*)temp); + p2tr_hash_set_remove_all (self->triangles); + + p2tr_hash_set_iter_init (&iter, self->edges); + while (p2tr_hash_set_iter_next (&iter, &temp)) + p2tr_edge_remove ((P2trEdge*)temp); + p2tr_hash_set_remove_all (self->edges); + + p2tr_hash_set_iter_init (&iter, self->points); + while (p2tr_hash_set_iter_next (&iter, &temp)) + p2tr_point_remove ((P2trPoint*)temp); + p2tr_hash_set_remove_all (self->points); + + self->_is_clearing_now = FALSE; +} + +void +p2tr_mesh_free (P2trMesh *self) +{ + p2tr_mesh_clear (self); + + p2tr_hash_set_free (self->points); + p2tr_hash_set_free (self->edges); + p2tr_hash_set_free (self->triangles); + + g_slice_free (P2trMesh, self); +} + +void +p2tr_mesh_unref (P2trMesh *self) +{ + if (--self->refcount == 0) + p2tr_mesh_free (self); +} + +void +p2tr_mesh_ref (P2trMesh *self) +{ + ++self->refcount; +} diff --git a/refine/mesh.h b/refine/mesh.h index 1041f46..d3b0df2 100644 --- a/refine/mesh.h +++ b/refine/mesh.h @@ -2,6 +2,7 @@ #define __P2TC_REFINE_MESH_H__ #include +#include "vector2.h" #include "utils.h" #include "triangulation.h" @@ -10,6 +11,10 @@ struct P2trMesh_ P2trHashSet *triangles; P2trHashSet *edges; P2trHashSet *points; + + guint refcount; + + gboolean _is_clearing_now; }; P2trMesh* p2tr_mesh_new (void); @@ -18,27 +23,22 @@ P2trPoint* p2tr_mesh_new_point (P2trMesh *mesh, const P2trVector2 *c); P2trEdge* p2tr_mesh_new_edge (P2trMesh *mesh, - P2trPoint *A, - P2trPoint *B, + P2trPoint *start, + P2trPoint *end, gboolean constrained); -P2trTriangle* p2tr_mesh_new_triangle (P2trMesh *mesh, - P2trPoint *A, - P2trPoint *B, - P2trPoint *C); +P2trTriangle* p2tr_mesh_new_triangle (P2trMesh *mesh, + P2trEdge *AB, + P2trEdge *BC, + P2trEdge *CA); -P2trTriangle* p2tr_mesh_new_triangle2 (P2trMesh *mesh, - P2trEdge *AB, - P2trEdge *BC, - P2trEdge *CA); - -gboolean p2tr_mesh_on_point_removed (P2trMesh *mesh, +void p2tr_mesh_on_point_removed (P2trMesh *mesh, P2trPoint *point); -gboolean p2tr_mesh_on_edge_removed (P2trMesh *mesh, +void p2tr_mesh_on_edge_removed (P2trMesh *mesh, P2trEdge *edge); -gboolean p2tr_mesh_on_triangle_removed (P2trMesh *mesh, +void p2tr_mesh_on_triangle_removed (P2trMesh *mesh, P2trTriangle *triangle); void p2tr_mesh_clear (P2trMesh *mesh); diff --git a/refine/utils.h b/refine/utils.h index 3f651a4..7af984a 100755 --- a/refine/utils.h +++ b/refine/utils.h @@ -50,10 +50,13 @@ extern "C" typedef GHashTable P2trHashSet; typedef GHashTableIter P2trHashSetIter; -#define p2tr_hash_set_set_new(hash_func, equal_func, destroy) g_hash_table_new_full ((hash_func), (equal_func), (destroy),NULL) +#define p2tr_hash_set_new_default() g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, NULL) +#define p2tr_hash_set_new(hash_func, equal_func, destroy) g_hash_table_new_full ((hash_func), (equal_func), (destroy),NULL) #define p2tr_hash_set_insert(set,element) g_hash_table_insert ((set), (element), (element)) #define p2tr_hash_set_contains(set,element) g_hash_table_lookup_extended ((set), (element), NULL, NULL) #define p2tr_hash_set_remove(set,element) g_hash_table_remove ((set), (element)) +#define p2tr_hash_set_remove_all(set) g_hash_table_remove_all ((set)) +#define p2tr_hash_set_free(set) g_hash_table_destroy(set) #define p2tr_hash_set_iter_init(iter,hash_set) g_hash_table_iter_init ((iter),(hash_set)) #define p2tr_hash_set_iter_next(iter,val) g_hash_table_iter_next ((iter),(val),NULL) -- 2.40.0