add part of n-point deformation library

3 files changed, 363 insertions, 0 deletions

diff --git a/libs/npd/deformation.c b/libs/npd/deformation.c
new file mode 100644
index 00000000..415e53b7
--- /dev/null
+++ b/libs/npd/deformation.c
@@ -0,0 +1,203 @@
+/*
+ * This file is part of n-point image deformation library.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Copyright (C) 2013 Marek Dvoroznak <dvoromar@gmail.com>
+ */
+
+#include "deformation.h"
+#include <math.h>
+
+#define NPD_COMPUTE_CENTROID(suffix, arg1, arg2, WEIGHTS, accessor)     \
+void                                                                    \
+npd_compute_centroid_##suffix (gint      num_of_points,                 \
+                               arg1,                                    \
+                               arg2,                                    \
+                               NPDPoint *centroid)                      \
+{                                                                       \
+  gfloat x_sum = 0, y_sum = 0, weights_sum = 0;                         \
+  gint i;                                                               \
+                                                                        \
+  /* first compute sum of all values for each coordinate */             \
+  for (i = 0; i < num_of_points; ++i)                                   \
+    {                                                                   \
+      x_sum       += (WEIGHTS) * points[i] accessor x;                  \
+      y_sum       += (WEIGHTS) * points[i] accessor y;                  \
+      weights_sum += (WEIGHTS);                                         \
+    }                                                                   \
+                                                                        \
+  /* then compute mean */                                               \
+  centroid->x = x_sum / weights_sum;                                    \
+  centroid->y = y_sum / weights_sum;                                    \
+}
+
+NPD_COMPUTE_CENTROID (of_overlapping_points,
+                      NPDPoint *points[],
+                      gfloat weights[],
+                      1,
+                      ->)
+NPD_COMPUTE_CENTROID (from_weighted_points,
+                      NPDPoint points[],
+                      gfloat weights[],
+                      weights[i],
+                      .)
+
+void
+npd_compute_ARSAP_transformation (gint     num_of_points,
+                                  NPDPoint reference_points[],
+                                  NPDPoint current_points[],
+                                  gfloat   weights[],
+                                  gboolean ARAP)
+{
+  NPDPoint pc = {0, 0}, qc = {0, 0};
+  gfloat a = 0, b = 0, mu_part = 0, mu, r1, r2, x0, y0;
+  gint i;
+
+  /* p - points of reference pose */
+  npd_compute_centroid_from_weighted_points (num_of_points,
+                                             reference_points,
+                                             weights,
+                                            &pc);
+  /* q - points of current pose */
+  npd_compute_centroid_from_weighted_points (num_of_points,
+                                             current_points,
+                                             weights,
+                                            &qc);
+
+  /* get rotation */
+  for (i = 0; i < num_of_points; ++i)
+    {
+      gfloat px_minus_pcx = reference_points[i].x - pc.x;
+      gfloat py_minus_pcy = reference_points[i].y - pc.y;
+      gfloat qx_minus_qcx =   current_points[i].x - qc.x;
+      gfloat qy_minus_qcy =   current_points[i].y - qc.y;
+
+      a += weights[i]
+              * ((px_minus_pcx)
+              *  (qx_minus_qcx)
+              +  (py_minus_pcy)
+              *  (qy_minus_qcy));
+      b += weights[i]
+              * ((px_minus_pcx)
+              *  (qy_minus_qcy)
+              -  (py_minus_pcy)
+              *  (qx_minus_qcx));
+
+      mu_part += weights[i]
+              * ((px_minus_pcx)
+              *  (px_minus_pcx)
+              +  (py_minus_pcy)
+              *  (py_minus_pcy));
+    }
+
+  mu = 1;
+  if (ARAP) mu = sqrt(a * a + b * b);
+  else      mu = mu_part;
+
+  r1 =  a / mu;
+  r2 = -b / mu;
+
+  /* get translation */
+  x0 = qc.x - ( r1 * pc.x + r2 * pc.y);
+  y0 = qc.y - (-r2 * pc.x + r1 * pc.y);
+
+  /* transform points */
+  for (i = 0; i < num_of_points; ++i)
+    {
+      if (!current_points[i].fixed)
+        {
+          current_points[i].x =  r1 * reference_points[i].x
+                  + r2 * reference_points[i].y + x0;
+          current_points[i].y = -r2 * reference_points[i].x
+                  + r1 * reference_points[i].y + y0;
+        }
+    }
+}
+
+void
+npd_compute_ARSAP_transformations (NPDHiddenModel *hidden_model)
+{
+  gint i;
+  for (i = 0; i < hidden_model->num_of_bones; ++i)
+    {
+      NPDBone *reference_bones = &hidden_model->reference_bones[i];
+      NPDBone *current_bones   = &hidden_model->current_bones[i];
+      npd_compute_ARSAP_transformation (reference_bones->num_of_points,
+                                        reference_bones->points,
+                                        current_bones->points,
+                                        current_bones->weights,
+                                        hidden_model->ARAP);
+    }
+}
+
+void
+npd_deform_model (NPDModel *model,
+                  gint      rigidity)
+{
+  gint i;
+  for (i = 0; i < rigidity; ++i)
+    {
+      npd_deform_model_once (model);
+    }
+}
+
+void
+npd_deform_model_once (NPDModel *model)
+{
+  gint i, j;
+  
+  /* updates associated overlapping points according to this control point */
+  for (i = 0; i < model->control_points->len; ++i)
+    {
+      NPDControlPoint *cp = &g_array_index (model->control_points,
+                                            NPDControlPoint,
+                                            i);
+
+      for (j = 0; j < cp->overlapping_points->num_of_points; ++j)
+        {
+          npd_set_point_coordinates (cp->overlapping_points->points[j],
+                                     &cp->point);
+        }
+    }
+
+  npd_deform_hidden_model_once (model->hidden_model);
+}
+
+void
+npd_deform_hidden_model_once (NPDHiddenModel *hidden_model)
+{
+  gint i, j;
+  npd_compute_ARSAP_transformations (hidden_model);
+
+  /* overlapping points are not overlapping after the deformation,
+     so we have to move them to their centroid */
+  for (i = 0; i < hidden_model->num_of_overlapping_points; ++i)
+    {
+      NPDOverlappingPoints *list_of_ops
+              = &hidden_model->list_of_overlapping_points[i];
+      NPDPoint centroid;
+      
+      npd_compute_centroid_of_overlapping_points (list_of_ops->num_of_points,
+                                                  list_of_ops->points,
+                                                  NULL,
+                                                 &centroid);
+
+      for (j = 0; j < list_of_ops->num_of_points; ++j)
+        {
+          list_of_ops->points[j]->x = centroid.x;
+          list_of_ops->points[j]->y = centroid.y;
+        }
+    }
+}
diff --git a/libs/npd/deformation.h b/libs/npd/deformation.h
new file mode 100644
index 00000000..326d14ff
--- /dev/null
+++ b/libs/npd/deformation.h
@@ -0,0 +1,46 @@
+/*
+ * This file is part of n-point image deformation library.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Copyright (C) 2013 Marek Dvoroznak <dvoromar@gmail.com>
+ */
+
+#ifndef __NPD_DEFORMATION_H__
+#define	__NPD_DEFORMATION_H__
+
+#include "npd_common.h"
+
+void  npd_compute_centroid_from_weighted_points
+                                        (gint              num_of_points,
+                                         NPDPoint          points[],
+                                         gfloat            weights[],
+                                         NPDPoint         *centroid);
+void  npd_compute_centroid_of_overlapping_points
+                                        (gint              num_of_points,
+                                         NPDPoint         *points[],
+                                         gfloat            weights[],
+                                         NPDPoint         *centroid);
+void  npd_compute_ARSAP_transformation  (gint              num_of_points,
+                                         NPDPoint          reference_shape[],
+                                         NPDPoint          current_shape[],
+                                         gfloat            weights[],
+                                         gboolean          ARAP);
+void  npd_compute_ARSAP_transformations (NPDHiddenModel   *model);
+void  npd_deform_model                  (NPDModel         *model,
+                                         gint              rigidity);
+void  npd_deform_model_once             (NPDModel         *model);
+void  npd_deform_hidden_model_once      (NPDHiddenModel   *hidden_model);
+
+#endif	/* __NPD_DEFORMATION_H__ */
\ No newline at end of file
diff --git a/libs/npd/npd_common.h b/libs/npd/npd_common.h
new file mode 100644
index 00000000..c3bb4525
--- /dev/null
+++ b/libs/npd/npd_common.h
@@ -0,0 +1,114 @@
+/*
+ * This file is part of n-point image deformation library.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Copyright (C) 2013 Marek Dvoroznak <dvoromar@gmail.com>
+ */
+
+#ifndef __NPD_COMMON_H__
+#define	__NPD_COMMON_H__
+
+#include <glib.h>
+
+/* opaque types for independency on used display library */
+typedef struct _NPDImage    NPDImage;
+typedef struct _NPDColor    NPDColor;
+typedef struct _NPDDisplay  NPDDisplay;
+typedef struct _NPDMatrix   NPDMatrix;
+
+typedef struct
+{
+  gfloat                x;
+  gfloat                y;
+  gboolean              fixed;
+  gfloat               *weight;            /* reference to weight in array
+                                              of weights */
+} NPDPoint;
+
+typedef struct
+{
+  gint                  num_of_points;
+  NPDPoint             *points;            /* array of points */
+  gfloat               *weights;           /* array of weights */
+} NPDBone;
+
+typedef struct
+{
+  gint                  num_of_points;
+  NPDPoint             *representative;    /* reference to representative
+                                              of cluster */
+  NPDPoint            **points;            /* array of references to points */
+} NPDOverlappingPoints;
+
+typedef struct
+{
+  gint                  num_of_bones;
+  gint                  num_of_overlapping_points;
+  gboolean              ARAP;
+  NPDBone              *current_bones;     /* array of current bones */
+  NPDBone              *reference_bones;   /* array of reference bones */
+  NPDOverlappingPoints *list_of_overlapping_points; /* array of overlapping
+                                                       points */
+} NPDHiddenModel;
+
+typedef struct
+{
+  NPDPoint              point;
+  NPDOverlappingPoints *overlapping_points; /* reference to overlapping
+                                               points */
+} NPDControlPoint;
+
+typedef struct
+{
+  gint                  control_point_radius;
+  gboolean              control_points_visible;
+  gboolean              mesh_visible;
+  gboolean              texture_visible;
+  gint                  mesh_square_size;
+  GArray               *control_points;     /* GArray of control points */
+  NPDHiddenModel       *hidden_model;
+  NPDImage             *reference_image;
+  NPDDisplay           *display;
+} NPDModel;
+
+void               npd_init_model             (NPDModel        *model);
+void               npd_destroy_hidden_model   (NPDHiddenModel  *model);
+void               npd_destroy_model          (NPDModel        *model);
+
+NPDControlPoint   *npd_add_control_point      (NPDModel        *model,
+                                               NPDPoint        *coord);
+void               npd_remove_control_point   (NPDModel        *model,
+                                               NPDControlPoint *control_point);
+void               npd_remove_all_control_points
+                                              (NPDModel        *model);
+void               npd_set_control_point_weight
+                                              (NPDControlPoint *cp,
+                                               gfloat           weight);
+gboolean           npd_equal_coordinates      (NPDPoint        *p1,
+                                               NPDPoint        *p2,
+                                               gfloat           epsilon);
+NPDControlPoint   *npd_get_control_point_at   (NPDModel        *model,
+                                               NPDPoint        *coord);
+
+void               npd_create_list_of_overlapping_points
+                                              (NPDHiddenModel  *model);
+void               npd_set_overlapping_points_weight
+                                              (NPDOverlappingPoints *op,
+                                               gfloat           weight);
+
+void               npd_set_point_coordinates  (NPDPoint        *target,
+                                               NPDPoint        *source);
+
+#endif	/* __NPD_COMMON_H__ */
\ No newline at end of file