From bef2ee791ec2adc196280287fc550fb25842d62d Mon Sep 17 00:00:00 2001 From: Nicola Fontana Date: Wed, 23 Sep 2009 13:50:03 +0200 Subject: [PATCH] [AdgMatrix] Added adg_matrix_normalize() Implemented the normalization of a matrix. Check out the function docblock for details on the algorithm used. --- adg/adg-matrix.c | 167 ++++++++++++++++++++++++++++++++++++++++++++++++------- adg/adg-matrix.h | 4 +- 2 files changed, 149 insertions(+), 22 deletions(-) diff --git a/adg/adg-matrix.c b/adg/adg-matrix.c index b8410b7f..20170346 100644 --- a/adg/adg-matrix.c +++ b/adg/adg-matrix.c @@ -55,6 +55,27 @@ adg_matrix_get_type(void) } /** + * adg_matrix_identity: + * + * A constant identity matrix provided as facility. + * + * Returns: a pointer to the identity matrix + **/ +const AdgMatrix * +adg_matrix_identity(void) +{ + static AdgMatrix identity_matrix; + static gboolean initialized = FALSE; + + if (G_UNLIKELY(!initialized)) { + cairo_matrix_init_identity(&identity_matrix); + initialized = TRUE; + } + + return &identity_matrix; +} + +/** * adg_matrix_copy: * @matrix: the destination #AdgMatrix * @src: the source #AdgMatrix @@ -92,27 +113,6 @@ adg_matrix_dup(const AdgMatrix *matrix) } /** - * adg_matrix_identity: - * - * A constant identity matrix provided as facility. - * - * Returns: a pointer to the identity matrix - **/ -const AdgMatrix * -adg_matrix_identity(void) -{ - static AdgMatrix identity_matrix; - static gboolean initialized = FALSE; - - if (G_UNLIKELY(!initialized)) { - cairo_matrix_init_identity(&identity_matrix); - initialized = TRUE; - } - - return &identity_matrix; -} - -/** * adg_matrix_equal: * @matrix1: an #AdgMatrix * @matrix2: an #AdgMatrix @@ -127,5 +127,130 @@ adg_matrix_equal(const AdgMatrix *matrix1, const AdgMatrix *matrix2) g_return_val_if_fail(matrix1 != NULL, FALSE); g_return_val_if_fail(matrix2 != NULL, FALSE); + /* XXX: I don't know if the following is always correct */ return memcmp(matrix1, matrix2, sizeof(AdgMatrix)) == 0; } + +/** + * adg_matrix_normalize: + * @matrix: an #AdgMatrix + * + * Gets rid of the scaling component of a matrix: considering the + * (0,0) and (1,1) points, this function normalizes @matrix by + * forcing a %M_SQRT2 distance (that is the distance these points + * have on the identity matrix). This is done by applying a common + * factor to the xx and yy + * components of @matrix, without considering translations. + * + * From the documentation of the + * cairo matrix + * we have: + * + * |[ + * x_new = xx * x + xy * y + x0; + * y_new = yx * x + yy * y + y0. + * ]| + * + * Calling P0 = (0, 0) and P1 = (1, 1), their coordinates in @matrix, + * applying an arbitrary factor (k) on the scaling + * component, are: + * + * |[ + * P0.x = x0; + * P0.y = y0; + * P1.x = k * matrix->xx + matrix->xy + x0; + * P1.y = k * matrix->yx + matrix->yy + y0. + * ]| + * + * Translating @matrix of (-x0, -y0), as I don't care of the translation + * component (the original translation will be kept intact): + * + * |[ + * P0.x = 0; + * P0.y = 0; + * P1.x = k * matrix->xx + matrix->xy; + * P1.y = k * matrix->yx + matrix->yy. + * ]| + * + * Let's force a distance of %2 on the sum of their squared difference, + * as Pythagoras suggests: + * + * |[ + * (P1.x - P0.x)² + (P1.y - P0.y)² = 2. + * (k matrix->xx + matrix->xy)² + (k matrix->yy + matrix->yx)² = 2. + * k² matrix->xx² + matrix->xy² + 2 k matrix->xx matrix->xy + + * k² matrix->yy² + matrix->yx² + 2 k matrix->yy matrix->yx = 2. + * k² (matrix->xx² + matrix->yy²) + + * 2k (matrix->xx matrix->xy + matrix->yy matrix->yx) + + * matrix->xy² + matrix->yx² - 2 = 0. + * ]| + * + * Now we'll calculate the k factor by calling + * a, b and c + * the respective coefficients and using the second degree equation + * solver, taking only the greater root: + * + * |[ + * a = matrix->xx² + matrix->yy²; + * b = 2 (matrix->xx matrix->xy + matrix->yy matrix->yx); + * c = matrix->xy² + matrix->yx² - 2; + * -b + √(b² - 4ac) + * k = ----------------. + * 2a + * ]| + * + * If the discriminant is less than %0 the negative square root is not + * possible with real numbers, so @matrix is left untouched and + * %FALSE is returned. Otherwise, once the k factor + * is found, it is applied to the original matrix and %TRUE is returned. + * + * As a bonus, in the quite common case the original matrix has a scaling + * ratio of %1 (that is matrix->xx == matrix->yy) and it is not rotated + * (matrix->xy and matrix->yx are %0), we have: + * + * |[ + * // Shortcut for uniform scaled matrices not rotated: + * a = 2 matrix->xx²; + * b = 0; + * c = -2; + * -b + √(b² - 4ac) √(16 matrix->xx²) 1 + * k = ---------------- = ----------------- = ----------. + * 2a 4 matrix->xx² matrix->xx + * ]| + * + * avoiding square root and a lot of multiplications. + * + * Returns: %TRUE on success, %FALSE on errors + **/ +gboolean +adg_matrix_normalize(AdgMatrix *matrix) +{ + gdouble k; + + g_return_val_if_fail(matrix != NULL, FALSE); + + if (matrix->xx == matrix->yy && matrix->xy == 0 && matrix->yx == 0) { + /* Common situation: original matrix scaled with a + * ratio of 1 and not rotated */ + k = 1. / matrix->xx; + } else { + gdouble a, b, c, d; + + a = matrix->xx * matrix->xx + matrix->yy * matrix->yy; + b = (matrix->xx * matrix->xy + matrix->yy * matrix->yx) * 2; + c = matrix->xy * matrix->xy + matrix->yx * matrix->yx - 2; + + /* Compute and check the discriminant */ + d = b * b - a * c * 4; + if (d < 0) + return FALSE; + + k = (sqrt(d) - b) / (a * 2); + } + + /* Apply the normalization factor */ + matrix->xx *= k; + matrix->yy *= k; + + return TRUE; +} diff --git a/adg/adg-matrix.h b/adg/adg-matrix.h index 58393be7..0ef9a4b8 100644 --- a/adg/adg-matrix.h +++ b/adg/adg-matrix.h @@ -34,12 +34,14 @@ typedef cairo_matrix_t AdgMatrix; GType adg_matrix_get_type (void) G_GNUC_CONST; +const AdgMatrix*adg_matrix_identity (void) G_GNUC_CONST; + AdgMatrix * adg_matrix_copy (AdgMatrix *matrix, const AdgMatrix *src); AdgMatrix * adg_matrix_dup (const AdgMatrix *matrix); -const AdgMatrix*adg_matrix_identity (void) G_GNUC_CONST; gboolean adg_matrix_equal (const AdgMatrix *matrix1, const AdgMatrix *matrix2); +gboolean adg_matrix_normalize (AdgMatrix *matrix); G_END_DECLS -- 2.11.4.GIT