gts/edge.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999 Stéphane Popinet
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include "gts.h"
  21
  22 gboolean gts_allow_floating_edges = FALSE;
  23
  24 static void edge_destroy (GtsObject * object)
  25 {
  26   GtsEdge * edge = GTS_EDGE (object);
  27   GSList * i;
  28
  29   i = edge->triangles;
  30   while (i) {
  31     GSList * next = i->next;
  32     gts_object_destroy (i->data);
  33     i = next;
  34   }
  35   g_assert (edge->triangles == NULL);
  36
  37   (* GTS_OBJECT_CLASS (gts_edge_class ())->parent_class->destroy) (object);
  38 }
  39
  40 static void edge_clone (GtsObject * clone, GtsObject * object)
  41 {
  42   (* GTS_OBJECT_CLASS (gts_edge_class ())->parent_class->clone) (clone,
  43                                                                  object);
  44   GTS_SEGMENT (clone)->v1 = GTS_SEGMENT (clone)->v2 = NULL;
  45   GTS_EDGE (clone)->triangles = NULL;
  46 }
  47
  48 static void edge_class_init (GtsObjectClass * klass)
  49 {
  50   klass->clone = edge_clone;
  51   klass->destroy = edge_destroy;
  52 }
  53
  54 static void edge_init (GtsEdge * edge)
  55 {
  56   edge->triangles = NULL;
  57 }
  58
  59 /**
  60  * gts_edge_class:
  61  *
  62  * Returns: the #GtsEdgeClass.
  63  */
  64 GtsEdgeClass * gts_edge_class (void)
  65 {
  66   static GtsEdgeClass * klass = NULL;
  67
  68   if (klass == NULL) {
  69     GtsObjectClassInfo edge_info = {
  70       "GtsEdge",
  71       sizeof (GtsEdge),
  72       sizeof (GtsEdgeClass),
  73       (GtsObjectClassInitFunc) edge_class_init,
  74       (GtsObjectInitFunc) edge_init,
  75       (GtsArgSetFunc) NULL,
  76       (GtsArgGetFunc) NULL
  77     };
  78     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_segment_class ()),
  79                                   &edge_info);
  80   }
  81
  82   return klass;
  83 }
  84
  85 /**
  86  * gts_edge_new:
  87  * @klass: a #GtsEdgeClass.
  88  * @v1: a #GtsVertex.
  89  * @v2: a #GtsVertex.
  90  *
  91  * Returns: a new #GtsEdge linking @v1 and @v2.
  92  */
  93 GtsEdge * gts_edge_new (GtsEdgeClass * klass,
  94                         GtsVertex * v1, GtsVertex * v2)
  95 {
  96   return GTS_EDGE (gts_segment_new (GTS_SEGMENT_CLASS (klass), v1, v2));
  97 }
  98
  99 void gts_edge_remove(GtsEdge *edge)
 100 {
 101   edge->segment.v1->segments = g_slist_remove(edge->segment.v1->segments, &edge->segment);
 102   edge->segment.v2->segments = g_slist_remove(edge->segment.v2->segments, &edge->segment);
 103   edge_destroy(GTS_OBJECT (edge));
 104 }
 105
 106 /**
 107  * gts_edge_replace:
 108  * @e: a #GtsEdge.
 109  * @with: a #GtsEdge.
 110  *
 111  * Replaces @e with @with. For each triangle which uses @e as an
 112  * edge, @e is replaced with @with. The @with->triangles list is
 113  * updated appropriately and the @e->triangles list is freed and set
 114  * to %NULL.
 115  */
 116 void gts_edge_replace (GtsEdge * e, GtsEdge * with)
 117 {
 118   GSList * i;
 119
 120   g_return_if_fail (e != NULL && with != NULL && e != with);
 121
 122   i = e->triangles;
 123   while (i) {
 124     GtsTriangle * t = i->data;
 125     if (t->e1 == e) t->e1 = with;
 126     if (t->e2 == e) t->e2 = with;
 127     if (t->e3 == e) t->e3 = with;
 128     if (!g_slist_find (with->triangles, t))
 129       with->triangles = g_slist_prepend (with->triangles, t);
 130     i = i->next;
 131   }
 132   g_slist_free (e->triangles);
 133   e->triangles = NULL;
 134 }
 135
 136 /**
 137  * gts_edge_has_parent_surface:
 138  * @e: a #GtsEdge.
 139  * @surface: a #GtsSurface.
 140  *
 141  * Returns: a #GtsFace of @surface having @e as an edge, %NULL otherwise.
 142  */
 143 GtsFace * gts_edge_has_parent_surface (GtsEdge * e, GtsSurface * surface)
 144 {
 145   GSList * i;
 146
 147   g_return_val_if_fail (e != NULL, NULL);
 148
 149   i = e->triangles;
 150   while (i) {
 151     if (GTS_IS_FACE (i->data) &&
 152         gts_face_has_parent_surface (i->data, surface))
 153       return i->data;
 154     i = i->next;
 155   }
 156   return NULL;
 157 }
 158
 159 /**
 160  * gts_edge_has_any_parent_surface:
 161  * @e: a #GtsEdge.
 162  *
 163  * Returns: %NULL if @e is not an edge of any triangle or if all the
 164  * faces having @e has an edge do not belong to any surface,
 165  * a #GtsFace belonging to a surface and having @e as an edge.
 166  */
 167 GtsFace * gts_edge_has_any_parent_surface (GtsEdge * e)
 168 {
 169   GSList * i;
 170
 171   g_return_val_if_fail (e != NULL, NULL);
 172
 173   i = e->triangles;
 174   while (i) {
 175     GtsTriangle * t = i->data;
 176     if (GTS_IS_FACE (t) && GTS_FACE (t)->surfaces != NULL)
 177       return GTS_FACE (t);
 178     i = i->next;
 179   }
 180   return NULL;
 181 }
 182
 183 /**
 184  * gts_edge_is_boundary:
 185  * @e: a #GtsEdge.
 186  * @surface: a #GtsSurface or %NULL.
 187  *
 188  * Returns: the unique #GtsFace (which belongs to @surface) and which
 189  * has @e as an edge (i.e. @e is a boundary edge (of @surface)) or %NULL
 190  * if there is more than one or no faces (belonging to @surface) and
 191  * with @e as an edge.
 192  */
 193 GtsFace * gts_edge_is_boundary (GtsEdge * e, GtsSurface * surface)
 194 {
 195   GSList * i;
 196   GtsFace * f = NULL;
 197
 198   g_return_val_if_fail (e != NULL, NULL);
 199
 200   i = e->triangles;
 201   while (i) {
 202     if (GTS_IS_FACE (i->data)) {
 203       if (!surface || gts_face_has_parent_surface (i->data, surface)) {
 204         if (f != NULL)
 205           return NULL;
 206         f = i->data;
 207       }
 208     }
 209     i = i->next;
 210   }
 211   return f;
 212 }
 213
 214 /**
 215  * gts_edges_from_vertices:
 216  * @vertices: a list of #GtsVertex.
 217  * @parent: a #GtsSurface.
 218  *
 219  * Returns: a list of unique #GtsEdge which have one of their vertices in
 220  * @vertices and are used by a face of @parent.
 221  */
 222 GSList * gts_edges_from_vertices (GSList * vertices, GtsSurface * parent)
 223 {
 224   GHashTable * hash;
 225   GSList * edges = NULL, * i;
 226
 227   g_return_val_if_fail (parent != NULL, NULL);
 228
 229   hash = g_hash_table_new (NULL, NULL);
 230   i = vertices;
 231   while (i) {
 232     GSList * j = GTS_VERTEX (i->data)->segments;
 233     while (j) {
 234       GtsSegment * s = j->data;
 235       if (GTS_IS_EDGE (s) &&
 236           gts_edge_has_parent_surface (GTS_EDGE (s), parent) &&
 237           g_hash_table_lookup (hash, s) == NULL) {
 238         edges = g_slist_prepend (edges, s);
 239         g_hash_table_insert (hash, s, i);
 240       }
 241       j = j->next;
 242     }
 243     i = i->next;
 244   }
 245   g_hash_table_destroy (hash);
 246   return edges;
 247 }
 248
 249 /**
 250  * gts_edge_face_number:
 251  * @e: a #GtsEdge.
 252  * @s: a #GtsSurface.
 253  *
 254  * Returns: the number of faces using @e and belonging to @s.
 255  */
 256 guint gts_edge_face_number (GtsEdge * e, GtsSurface * s)
 257 {
 258   GSList * i;
 259   guint nt = 0;
 260
 261   g_return_val_if_fail (e != NULL, 0);
 262   g_return_val_if_fail (s != NULL, 0);
 263
 264   i = e->triangles;
 265   while (i) {
 266     if (GTS_IS_FACE (i->data) &&
 267         gts_face_has_parent_surface (GTS_FACE (i->data), s))
 268       nt++;
 269     i = i->next;
 270   }
 271   return nt;
 272 }
 273
 274 /**
 275  * gts_edge_is_duplicate:
 276  * @e: a #GtsEdge.
 277  *
 278  * Returns: the first #GtsEdge different from @e which shares the
 279  * same endpoints or %NULL if there is none.
 280  */
 281 GtsEdge * gts_edge_is_duplicate (GtsEdge * e)
 282 {
 283   GSList * i;
 284   GtsVertex * v2;
 285
 286   g_return_val_if_fail (e != NULL, NULL);
 287
 288   v2 = GTS_SEGMENT (e)->v2;
 289   i = GTS_SEGMENT (e)->v1->segments;
 290   if (GTS_SEGMENT (e)->v1 == v2) /* e is degenerate: special treatment */
 291     while (i) {
 292       GtsSegment * s = i->data;
 293       if (s != GTS_SEGMENT (e) &&
 294           GTS_IS_EDGE (s) &&
 295           s->v1 == v2 && s->v2 == v2)
 296         return GTS_EDGE (s);
 297       i = i->next;
 298     }
 299   else /* e is not degenerate */
 300     while (i) {
 301       GtsSegment * s = i->data;
 302       if (s != GTS_SEGMENT (e) &&
 303           GTS_IS_EDGE (s) &&
 304           (s->v1 == v2 || s->v2 == v2))
 305         return GTS_EDGE (s);
 306       i = i->next;
 307     }
 308   return NULL;
 309 }
 310
 311 /**
 312  * gts_edges_merge:
 313  * @edges: a list of #GtsEdge.
 314  *
 315  * For each edge in @edges check if it is duplicated (as
 316  * returned by gts_edge_is_duplicate()). If it is replace it by its
 317  * duplicate, destroy it and remove it from the list.
 318  *
 319  * Returns: the updated @edges list.
 320  */
 321 GList * gts_edges_merge (GList * edges)
 322 {
 323   GList * i = edges;
 324
 325   /* we want to control edge destruction */
 326   gts_allow_floating_edges = TRUE;
 327   while (i) {
 328     GtsEdge * e = i->data;
 329     GtsEdge * de = gts_edge_is_duplicate (e);
 330     if (de) {
 331       GList * next = i->next;
 332       edges = g_list_remove_link (edges, i);
 333       g_list_free_1 (i);
 334       i = next;
 335       gts_edge_replace (e, de);
 336       gts_object_destroy (GTS_OBJECT (e));
 337     }
 338     else
 339       i = i->next;
 340   }
 341   gts_allow_floating_edges = FALSE;;
 342
 343   return edges;
 344 }
 345
 346 static void triangle_vertices_edges (GtsTriangle * t,
 347                                      GtsEdge * e,
 348                                      GtsVertex ** v,
 349                                      GtsEdge ** ee1,
 350                                      GtsEdge ** ee2)
 351 {
 352   GtsEdge * e1 = t->e1, * e2 = t->e2, * e3 = t->e3;
 353   GtsVertex * v1 = GTS_SEGMENT (e)->v1;
 354
 355   if (e1 == e)        e1 = e3;
 356   else if (e2 == e)   e2 = e3;
 357   else                g_assert (e3 == e);
 358
 359   if (GTS_SEGMENT (e2)->v1 == v1 || GTS_SEGMENT (e2)->v2 == v1) {
 360     e3 = e1; e1 = e2; e2 = e3;
 361   }
 362   if (GTS_SEGMENT (e1)->v1 == v1)
 363     *v = GTS_SEGMENT (e1)->v2;
 364   else
 365     *v = GTS_SEGMENT (e1)->v1;
 366   *ee1 = e1;
 367   *ee2 = e2;
 368 }
 369
 370 /**
 371  * gts_edge_belongs_to_tetrahedron:
 372  * @e: a #GtsEdge.
 373  *
 374  * Returns: %TRUE if @e is used by faces forming a tetrahedron, %FALSE
 375  * otherwise.
 376  */
 377 gboolean gts_edge_belongs_to_tetrahedron (GtsEdge * e)
 378 {
 379   GSList * i;
 380
 381   g_return_val_if_fail (e != NULL, FALSE);
 382
 383   i = e->triangles;
 384   while (i) {
 385     GtsEdge * e1, * e2;
 386     GtsVertex * vt1;
 387     GSList * j = i->next;
 388     triangle_vertices_edges (i->data, e, &vt1, &e1, &e2);
 389     while (j) {
 390       GtsSegment * s5;
 391       GtsEdge * e3, * e4;
 392       GtsVertex * vt2;
 393
 394       triangle_vertices_edges (j->data, e, &vt2, &e3, &e4);
 395       s5 = gts_vertices_are_connected (vt1, vt2);
 396       if (GTS_IS_EDGE (s5) &&
 397           gts_triangle_use_edges (e1, e3, GTS_EDGE (s5)) &&
 398           gts_triangle_use_edges (e2, e4, GTS_EDGE (s5)))
 399         return TRUE;
 400       j = j->next;
 401     }
 402     i = i->next;
 403   }
 404
 405   return FALSE;
 406 }
 407
 408 #define edge_use_vertex(e, v) (GTS_SEGMENT(e)->v1 == v ||\
 409                                GTS_SEGMENT(e)->v2 == v)
 410
 411 static GtsEdge * next_edge (GtsTriangle * t,
 412                             GtsEdge * e1,
 413                             GtsEdge * e)
 414 {
 415   GtsVertex * v1 = GTS_SEGMENT (e)->v1;
 416   GtsVertex * v2 = GTS_SEGMENT (e)->v2;
 417
 418   if (t->e1 != e1 && t->e1 != e &&
 419       (edge_use_vertex (t->e1, v1) || edge_use_vertex (t->e1, v2)))
 420     return t->e1;
 421   else if (t->e2 != e1 && t->e2 != e &&
 422            (edge_use_vertex (t->e2, v1) || edge_use_vertex (t->e2, v2)))
 423     return t->e2;
 424   else if (t->e3 != e1 && t->e3 != e &&
 425            (edge_use_vertex (t->e3, v1) || edge_use_vertex (t->e3, v2)))
 426     return t->e3;
 427   g_assert_not_reached ();
 428   return NULL;
 429 }
 430
 431 static void triangle_next (GtsEdge * e1, GtsEdge * e)
 432 {
 433   GSList * i;
 434
 435   i = e1->triangles;
 436   while (i) {
 437     GtsTriangle * t = i->data;
 438     if (GTS_OBJECT (t)->reserved) {
 439       GTS_OBJECT (t)->reserved = NULL;
 440       triangle_next (next_edge (t, e1, e), e);
 441     }
 442     i = i->next;
 443   }
 444 }
 445
 446 /**
 447  * gts_edge_is_contact:
 448  * @e: a #GtsEdge.
 449  *
 450  * Returns: the number of sets of connected triangles sharing @e as a
 451  * contact edge.
 452  */
 453 guint gts_edge_is_contact (GtsEdge * e)
 454 {
 455   GSList * i, * triangles;
 456   guint ncomponent = 0;
 457
 458   g_return_val_if_fail (e != NULL, 0);
 459
 460   triangles = gts_vertex_triangles (GTS_SEGMENT (e)->v1, NULL);
 461   i = triangles = gts_vertex_triangles (GTS_SEGMENT (e)->v2, triangles);
 462   while (i) {
 463     GTS_OBJECT (i->data)->reserved = i;
 464     i = i->next;
 465   }
 466
 467   i = e->triangles;
 468   while (i) {
 469     GtsTriangle * t = i->data;
 470     if (GTS_OBJECT (t)->reserved) {
 471       GtsEdge * e1;
 472       GTS_OBJECT (t)->reserved = NULL;
 473       e1 = next_edge (t, NULL, e);
 474       triangle_next (e1, e);
 475       triangle_next (next_edge (t, e1, e), e);
 476       ncomponent++;
 477     }
 478     i = i->next;
 479   }
 480
 481   g_slist_foreach (triangles, (GFunc) gts_object_reset_reserved, NULL);
 482   g_slist_free (triangles);
 483
 484   return ncomponent;
 485 }
 486
 487 /**
 488  * gts_edge_swap:
 489  * @e: a #GtsEdge.
 490  * @s: a #GtsSurface.
 491  *
 492  * Performs an "edge swap" on the two triangles sharing @e and
 493  * belonging to @s.
 494  */
 495 void gts_edge_swap (GtsEdge * e, GtsSurface * s)
 496 {
 497   GtsTriangle * t1 = NULL, * t2 = NULL, * t;
 498   GtsFace * f;
 499   GSList * i;
 500   GtsVertex * v1, * v2, * v3, * v4, * v5, * v6;
 501   GtsEdge * e1, * e2, * e3, * e4;
 502   GtsSegment * v3v6;
 503
 504   g_return_if_fail (e != NULL);
 505   g_return_if_fail (s != NULL);
 506
 507   i = e->triangles;
 508   while (i) {
 509     if (GTS_IS_FACE (i->data) && gts_face_has_parent_surface (i->data, s)) {
 510       if (!t1)
 511         t1 = i->data;
 512       else if (!t2)
 513         t2 = i->data;
 514       else
 515         g_return_if_fail (gts_edge_face_number (e, s) == 2);
 516     }
 517     i = i->next;
 518   }
 519   g_assert (t1 && t2);
 520
 521   gts_triangle_vertices_edges (t1, e, &v1, &v2, &v3, &e, &e1, &e2);
 522   gts_triangle_vertices_edges (t2, e, &v4, &v5, &v6, &e, &e3, &e4);
 523   g_assert (v2 == v4 && v1 == v5);
 524
 525   v3v6 = gts_vertices_are_connected (v3, v6);
 526   if (!GTS_IS_EDGE (v3v6))
 527     v3v6 = GTS_SEGMENT (gts_edge_new (s->edge_class, v3, v6));
 528   f = gts_face_new (s->face_class, e1, GTS_EDGE (v3v6), e4);
 529   if ((t = gts_triangle_is_duplicate (GTS_TRIANGLE (f))) &&
 530       GTS_IS_FACE (t)) {
 531     gts_object_destroy (GTS_OBJECT (f));
 532     f = GTS_FACE (t);
 533   }
 534   gts_surface_add_face (s, f);
 535
 536   f = gts_face_new (s->face_class, GTS_EDGE (v3v6), e2, e3);
 537   if ((t = gts_triangle_is_duplicate (GTS_TRIANGLE (f))) &&
 538       GTS_IS_FACE (t)) {
 539     gts_object_destroy (GTS_OBJECT (f));
 540     f = GTS_FACE (t);
 541   }
 542   gts_surface_add_face (s, f);
 543
 544   gts_surface_remove_face (s, GTS_FACE (t1));
 545   gts_surface_remove_face (s, GTS_FACE (t2));
 546 }
 547
 548 /**
 549  * gts_edge_manifold_faces:
 550  * @e: a #GtsEdge.
 551  * @s: a #GtsSurface.
 552  * @f1: pointer for first face.
 553  * @f2: pointer for second face.
 554  *
 555  * If @e is a manifold edge of surface @s, fills @f1 and @f2 with the
 556  * faces belonging to @s and sharing @e.
 557  *
 558  * Returns: %TRUE if @e is a manifold edge, %FALSE otherwise.
 559  */
 560 gboolean gts_edge_manifold_faces (GtsEdge * e, GtsSurface * s,
 561                                   GtsFace ** f1, GtsFace ** f2)
 562 {
 563   GSList * i;
 564
 565   g_return_val_if_fail (e != NULL, FALSE);
 566   g_return_val_if_fail (s != NULL, FALSE);
 567   g_return_val_if_fail (f1 != NULL, FALSE);
 568   g_return_val_if_fail (f2 != NULL, FALSE);
 569
 570   *f1 = *f2 = NULL;
 571   i = e->triangles;
 572   while (i) {
 573     if (GTS_IS_FACE (i->data) && gts_face_has_parent_surface (i->data, s)) {
 574       if (!(*f1)) *f1 = i->data;
 575       else if (!(*f2)) *f2 = i->data;
 576       else return FALSE;
 577     }
 578     i = i->next;
 579   }
 580
 581   return (*f1 && *f2);
 582 }