From a767c658cb603de9ec9f0577627b9b32cbf82b2b Mon Sep 17 00:00:00 2001 From: pacien Date: Fri, 22 Dec 2017 01:53:55 +0100 Subject: Simplify and add geom. and matrix utility functions Signed-off-by: pacien --- include/common/geom.h | 54 ++++++++++++++++++++++++++++++++++++++++++++++++ include/common/matrix.h | 51 --------------------------------------------- include/morpher/matrix.h | 41 ++++++++++++++++++++++++++++++++++++ 3 files changed, 95 insertions(+), 51 deletions(-) delete mode 100644 include/common/matrix.h create mode 100644 include/morpher/matrix.h (limited to 'include') diff --git a/include/common/geom.h b/include/common/geom.h index a843c76..b3564a5 100644 --- a/include/common/geom.h +++ b/include/common/geom.h @@ -38,6 +38,46 @@ typedef struct { CartesianVector origin, target; } CartesianMapping; + +/** + * Function: m + * Shorthand for an identity mapping. + * + * Parameters: + * x - the x-coordinate + * y - the y-coordinate + * + * Returns: + * A cartesian identity mapping + */ +CartesianMapping m(int x, int y); + +/** + * Function: v + * Shorthand for a vector. + * + * Parameters: + * x - the x-coordinate + * y - the y-coordinate + * + * Returns: + * An integer vector + */ +CartesianVector v(int x, int y); + +/** + * Function: mappings_equals + * Compares two cartesian mappings. + * + * Parameters: + * m1 - the first mapping + * m2 - the second mapping + * + * Returns: + * T(m1 is equal to m2) + */ +bool mappings_equals(CartesianMapping m1, CartesianMapping m2); + /** * Function: vector_equals * Compares two cartesian vectors. @@ -51,4 +91,18 @@ typedef struct { */ bool vector_equals(CartesianVector v1, CartesianVector v2); +/** + * Function: triangle_area + * Computes the area of a triangle. + * + * Parameters: + * v1 - first vertex + * v2 - second vertex + * v3 - third vertex + * + * Returns: + * The area of the triangle spawned by the three supplied vertices + */ +IntVector triangle_area(CartesianVector v1, CartesianVector v2, CartesianVector v3); + #endif diff --git a/include/common/matrix.h b/include/common/matrix.h deleted file mode 100644 index fe4a12a..0000000 --- a/include/common/matrix.h +++ /dev/null @@ -1,51 +0,0 @@ -#ifndef UPEM_MORPHING_MATRIX -#define UPEM_MORPHING_MATRIX - -/** - * File: matrix.h - * Matrices representation and useful operations. - * - * See also: - * The film - */ - -#include "geom.h" - -/** - * Struct: IntSquareMatrix - * Represents a square integer matrix. - * - * Fields: - * **elements - NULL-terminated array of element pointers - * dim - dimension - */ -typedef struct { - IntVector **elements; - IntVector dim; -} IntSquareMatrix; - -/** - * Function: matrix_int_det - * Computes and returns the determinant of a square integer matrix. - * - * Parameters: - * *matrix - pointer to input matrix - * - * Returns: - * The integer determinant - */ -IntVector matrix_int_det(IntSquareMatrix *matrix); - -/** - * Function: matrix_reshape - * Reshapes a flat vector into a bi-dimensional row pointer array. - * - * Parameters: - * **bi_dim - pointer to the result row array - * *flat - flat vector - * width - number of elements per row - * height - number of rows - */ -void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height); - -#endif diff --git a/include/morpher/matrix.h b/include/morpher/matrix.h new file mode 100644 index 0000000..8118727 --- /dev/null +++ b/include/morpher/matrix.h @@ -0,0 +1,41 @@ +#ifndef UPEM_MORPHING_MATRIX +#define UPEM_MORPHING_MATRIX + +/** + * File: matrix.h + * Determinant operations. + * + * See also: + * The film + */ + +#include "common/geom.h" + +/** + * Function: matrix_int_det2 + * Computes and returns the determinant of a square integer matrix of size 2. + * + * Parameters: + * uij - element at the i-th row and j-th column, counting from 1 + * + * Returns: + * The integer determinant + */ +IntVector matrix_int_det2(IntVector u11, IntVector u12, + IntVector u21, IntVector u22); + +/** + * Function: matrix_int_det3 + * Computes and returns the determinant of a square integer matrix of size 3. + * + * Parameters: + * uij - element at the i-th row and j-th column, counting from 1 + * + * Returns: + * The integer determinant + */ +IntVector matrix_int_det3(IntVector u11, IntVector u12, IntVector u13, + IntVector u21, IntVector u22, IntVector u23, + IntVector u31, IntVector u32, IntVector u33); + +#endif -- cgit v1.2.3 From 553dc4a5b272a1828940e72a07b1c9a7210be464 Mon Sep 17 00:00:00 2001 From: pacien Date: Fri, 22 Dec 2017 01:57:03 +0100 Subject: Add triangle map and quadrilateral representation and common operations Signed-off-by: pacien --- include/morpher/quadrilateral.h | 39 +++++++++++++ include/morpher/trianglemap.h | 123 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 162 insertions(+) create mode 100644 include/morpher/quadrilateral.h create mode 100644 include/morpher/trianglemap.h (limited to 'include') diff --git a/include/morpher/quadrilateral.h b/include/morpher/quadrilateral.h new file mode 100644 index 0000000..c8cf3a1 --- /dev/null +++ b/include/morpher/quadrilateral.h @@ -0,0 +1,39 @@ +#ifndef UPEM_MORPHING_QUADRILATERAL +#define UPEM_MORPHING_QUADRILATERAL + +/** + * File: quadrilateral.h + * Operations on quadrilaterals formed by adjacent triangles pairs. + */ + +#include +#include "common/geom.h" +#include "morpher/trianglemap.h" + +/** + * Function: quadrilateral_flip_diagonal + * Flips the diagonal of a quadrilateral formed by two triangles sharing a common edge, + * using a positive rotation-like transform inverting both references. + * This transforms keeps the positive orientation of the vertices. + * Pointers to surrounding triangles are updated accordingly. + * + * Parameters: + * *t1 - the first triangle + * *t2 - the second triangle + */ +void quadrilateral_flip_diagonal(TriangleMap *t1, TriangleMap *t2); + +/** + * Function: quadrilateral_is_delaunay + * Tells whether the quadrilateral formed by the two supplied adjacent triangle forms a Delaunay triangulation. + * + * Parameters: + * *t1 - first triangle + * *t2 - second triangle adjacent to the first one + * + * Returns: + * T(t1 and t2 are a Delaunay triangulation in the quadrilateral formed by the twos) + */ +bool quadrilateral_is_delaunay(TriangleMap *t1, TriangleMap *t2); + +#endif diff --git a/include/morpher/trianglemap.h b/include/morpher/trianglemap.h new file mode 100644 index 0000000..05e7b87 --- /dev/null +++ b/include/morpher/trianglemap.h @@ -0,0 +1,123 @@ +#ifndef UPEM_MORPHING_TRIANGLEMAP +#define UPEM_MORPHING_TRIANGLEMAP + +/** + * File: trianglemap.h + * Represents a triangle map in a triangulation, in a plane oriented left to right and top to bottom. + */ + +#include +#include "common/geom.h" + +/** + * Struct: TriangleMap + * Represents a triangle mapping. + * + * Fields: + * vertices[] - array of vertices + * *neighbors[] - array of neighboring triangles ordered by the edges spawned by the vertices + * *next - pointer to another triangle for linear browsing, or NULL + */ +typedef struct _TriangleMap { + CartesianMapping vertices[3]; + struct _TriangleMap *neighbors[3]; + struct _TriangleMap *next; +} TriangleMap; + +/** + * Function: trianglemap_create + * Creates a TriangleMap, instantiating it on the heap. + * + * Parameters: + * vertex1 - first vertex + * vertex2 - second vertex + * vertex3 - third vertex + * + * Returns: + * A pointer to the newly created triangle + */ +TriangleMap *trianglemap_create(CartesianMapping v1, CartesianMapping v2, CartesianMapping v3); + +/** + * Function: trianglemap_destroy + * Destroys a triangle, freeing its dynamically allocated resources. + * Also returns the next triangle for convenience. + * Does not update surrounding triangles. + * + * Parameters: + * *t - pointer to the triangle to destroy + * + * Returns: + * A pointer to the next linear triangle + */ +TriangleMap *trianglemap_destroy(TriangleMap *t); + +/** + * Function: trianglemap_to + * Returns a pointer to the current or the closest adjacent neighbour TriangleMap + * minimizing the distance to the targeted position. + * + * Parameters: + * *t - the origin triangle + * v - the target position vector + * + * Returns: + * A pointer to the current or an immediate neighbour TriangleMap + */ +TriangleMap *trianglemap_to(TriangleMap *t, CartesianVector v); + +/** + * Function: trianglemap_find_common_edge + * Finds the index of the commonly shared edge in the neighbourhood of t. + * + * Parameters: + * *t - the base triangle + * *neighbor - the neighbour to search for + * + * Returns: + * The index of the common neighbour in the listing of t. + */ +int trianglemap_find_common_edge(TriangleMap *t, TriangleMap *neighbor); + +/** + * Function: trianglemap_set_neighbors + * Updates a triangle neighbors. + * Vertices must be given in a positively oriented (trigonometric) order. + * Neighbours must be given in the same order as the vertices. + * + * Parameters: + * *t - the triangle to modify + * *n1 - first neighbour + * *n2 - second neighbour + * *n3 - third neighbour + * *next - linear neighbour + */ +void trianglemap_set_neighbors(TriangleMap *t, TriangleMap *n1, TriangleMap *n2, TriangleMap *n3, TriangleMap *next); + +/** + * Function: triangle_replace_neighbor + * Substitutes a given neighbour in a neighbourhood. + * + * Parameters: + * *t - the base triangle + * *old - the neighbour to replace + * *new - the new neighbour + */ +void trianglemap_replace_neighbor(TriangleMap *t, TriangleMap *old, TriangleMap *new); + +/** + * Function: trianglemap_split + * Splits a triangle into three sub-triangles at the supplied center vertex, updating the surrounding triangles. + * The first triangle resulting from the split is returned, with the two others chained as linear neighbours. + * Those generated triangles each have one of the original surrounding neighbour as first element in their listings. + * + * Parameters: + * *t - the triangle to split + * v - the new vertex to add + * + * Returns: + * The first generated TriangleMap + */ +TriangleMap *trianglemap_split(TriangleMap *t, CartesianMapping v); + +#endif -- cgit v1.2.3 From cdbae7a5e7515ba50ae21f15929a086fc40fcae3 Mon Sep 17 00:00:00 2001 From: pacien Date: Sun, 24 Dec 2017 00:07:53 +0100 Subject: Implement Delaunay propagation Signed-off-by: pacien --- include/morpher/quadrilateral.h | 11 +++++++++++ include/morpher/trianglemap.h | 10 ++++++++++ 2 files changed, 21 insertions(+) (limited to 'include') diff --git a/include/morpher/quadrilateral.h b/include/morpher/quadrilateral.h index c8cf3a1..8691263 100644 --- a/include/morpher/quadrilateral.h +++ b/include/morpher/quadrilateral.h @@ -36,4 +36,15 @@ void quadrilateral_flip_diagonal(TriangleMap *t1, TriangleMap *t2); */ bool quadrilateral_is_delaunay(TriangleMap *t1, TriangleMap *t2); +/** + * Function: quadrilateral_propagate_delaunay + * Ensures that the quadrilateral spawned by the given triangles fulfills the Delaunay criterion, + * flipping the diagonal if necessary and propagating the changes to the neighbouring triangles. + * + * Parameters: + * *start - the starting triangle + * *neighbor - a neighboring triangle + */ +void quadrilateral_propagate_delaunay(TriangleMap *start, TriangleMap *neighbor); + #endif diff --git a/include/morpher/trianglemap.h b/include/morpher/trianglemap.h index 05e7b87..0bb6a1d 100644 --- a/include/morpher/trianglemap.h +++ b/include/morpher/trianglemap.h @@ -105,6 +105,16 @@ void trianglemap_set_neighbors(TriangleMap *t, TriangleMap *n1, TriangleMap *n2, */ void trianglemap_replace_neighbor(TriangleMap *t, TriangleMap *old, TriangleMap *new); +/** + * Function: trianglemap_foreach_neighbor + * Executes the given function for each existing (non-NULL) neighbour of the supplied triangle. + * + * Parameters: + * *t - the base triangle + * *f - the function + */ +void trianglemap_foreach_neighbor(TriangleMap *t, void (*f)(TriangleMap *current, TriangleMap *neighbor)); + /** * Function: trianglemap_split * Splits a triangle into three sub-triangles at the supplied center vertex, updating the surrounding triangles. -- cgit v1.2.3 From 2a9ca610acdd24ebf1a215f779bf2a5d9f80d9cf Mon Sep 17 00:00:00 2001 From: pacien Date: Sun, 24 Dec 2017 15:35:54 +0100 Subject: Move Delaunay propagation function Signed-off-by: pacien --- include/morpher/quadrilateral.h | 11 ----------- include/morpher/trianglemap.h | 10 ++++++++++ 2 files changed, 10 insertions(+), 11 deletions(-) (limited to 'include') diff --git a/include/morpher/quadrilateral.h b/include/morpher/quadrilateral.h index 8691263..c8cf3a1 100644 --- a/include/morpher/quadrilateral.h +++ b/include/morpher/quadrilateral.h @@ -36,15 +36,4 @@ void quadrilateral_flip_diagonal(TriangleMap *t1, TriangleMap *t2); */ bool quadrilateral_is_delaunay(TriangleMap *t1, TriangleMap *t2); -/** - * Function: quadrilateral_propagate_delaunay - * Ensures that the quadrilateral spawned by the given triangles fulfills the Delaunay criterion, - * flipping the diagonal if necessary and propagating the changes to the neighbouring triangles. - * - * Parameters: - * *start - the starting triangle - * *neighbor - a neighboring triangle - */ -void quadrilateral_propagate_delaunay(TriangleMap *start, TriangleMap *neighbor); - #endif diff --git a/include/morpher/trianglemap.h b/include/morpher/trianglemap.h index 0bb6a1d..f690a37 100644 --- a/include/morpher/trianglemap.h +++ b/include/morpher/trianglemap.h @@ -115,6 +115,16 @@ void trianglemap_replace_neighbor(TriangleMap *t, TriangleMap *old, TriangleMap */ void trianglemap_foreach_neighbor(TriangleMap *t, void (*f)(TriangleMap *current, TriangleMap *neighbor)); +/** + * Function: trianglemap_propagate_delaunay + * Ensures that the quadrilateral spawned by the given triangles and its neighbours fulfill the Delaunay criterion, + * flipping the diagonal if necessary and propagating the changes to the neighbouring triangles. + * + * Parameters: + * *t - the starting triangle + */ +void trianglemap_propagate_delaunay(TriangleMap *t); + /** * Function: trianglemap_split * Splits a triangle into three sub-triangles at the supplied center vertex, updating the surrounding triangles. -- cgit v1.2.3 From 45d01bc6d74ac1982c974f1b891b0ad96b878f3a Mon Sep 17 00:00:00 2001 From: pacien Date: Tue, 26 Dec 2017 16:30:12 +0100 Subject: Detail doc Signed-off-by: pacien --- include/morpher/trianglemap.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include') diff --git a/include/morpher/trianglemap.h b/include/morpher/trianglemap.h index f690a37..3dc5f96 100644 --- a/include/morpher/trianglemap.h +++ b/include/morpher/trianglemap.h @@ -14,7 +14,7 @@ * Represents a triangle mapping. * * Fields: - * vertices[] - array of vertices + * vertices[] - array of vertices mappings, positively ordered * *neighbors[] - array of neighboring triangles ordered by the edges spawned by the vertices * *next - pointer to another triangle for linear browsing, or NULL */ -- cgit v1.2.3 From 2f74af6a1069b9d662676e3d2cbbc671a67574b5 Mon Sep 17 00:00:00 2001 From: pacien Date: Tue, 26 Dec 2017 18:16:55 +0100 Subject: Implement morphing functions and adapt blender Signed-off-by: pacien --- include/blender/blender.h | 2 +- include/morpher/morphing.h | 58 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 59 insertions(+), 1 deletion(-) create mode 100644 include/morpher/morphing.h (limited to 'include') diff --git a/include/blender/blender.h b/include/blender/blender.h index 8e89208..26ff802 100644 --- a/include/blender/blender.h +++ b/include/blender/blender.h @@ -8,7 +8,7 @@ #include "common/time.h" #include "blender/canvas.h" -#include "morpher/morpher.h" +#include "morpher/morphing.h" /** * Function: blender_blend_canvas diff --git a/include/morpher/morphing.h b/include/morpher/morphing.h new file mode 100644 index 0000000..028cd87 --- /dev/null +++ b/include/morpher/morphing.h @@ -0,0 +1,58 @@ +#ifndef UPEM_MORPHING_MORPHING +#define UPEM_MORPHING_MORPHING + +/** + * File: morphing.h + * Coordinate mapping for morphing transforms. + */ + +#include "common/geom.h" +#include "common/time.h" +#include "morpher/trianglemap.h" + +/** + * Struct: Morphing + * Represents an abstract coordinate transform from a source to a destination coordinate matrix, + * constrained by a given set of points. + * + * Fields: + * dim - dimension in pixels + * *first - the first triangle in the linked list + * *center - the center triangle + */ +typedef struct { + CartesianVector dim; + TriangleMap *first, *center; +} Morphing; + +/** + * Function: morphing_init + * Initialises a morphing. + * + * Parameters: + * width - coordinate matrix width in pixels + * height - coordinate matrix height in pixels + */ +Morphing *morphing_create(IntVector width, IntVector height); + +/** + * Function: morphing_free + * Frees any resources allocated to a morphing. + * + * Parameters: + * *m - pointer to the morphing to destroy + */ +void morphing_destroy(Morphing *m); + +/** + * Function: morphing_add_constraint + * Adds a constraint point to a morphing. + * + * Parameters: + * *m - pointer to the morphing to alter + * origin - constraint point coordinates on the origin matrix + * destination - constraint point coordinates on the target matrix + */ +void morphing_add_constraint(Morphing *m, CartesianVector origin, CartesianVector destination); + +#endif -- cgit v1.2.3