gts/stripe.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999-2003  Wagner Toledo Correa, 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 #define PRINT_HEAP_ELEMENTS 0
  23
  24 typedef struct {
  25   GtsTriangle * t;
  26   gboolean used;
  27   GSList * neighbors;
  28   GtsEHeapPair *pos;
  29 } tri_data_t;
  30
  31 typedef struct {
  32   GHashTable * ht;
  33 } map_t;
  34
  35 typedef struct {
  36   map_t * map;
  37   GtsEHeap * heap;
  38 } heap_t;
  39
  40 static tri_data_t    * tri_data_new (GtsTriangle * t);
  41 static void            tri_data_destroy (tri_data_t * td);
  42 static guint           tri_data_num_unused_neighbors2 (const tri_data_t * td,
  43                                                        const map_t * map);
  44 static GHashTable    * tri_data_unused_neighbors2 (const tri_data_t * td,
  45                                                    const map_t * map);
  46
  47 static map_t         * map_new (GtsSurface * s);
  48 static void            map_destroy (map_t * map);
  49 static tri_data_t    * map_lookup (const map_t * map, GtsTriangle * t);
  50
  51
  52 static heap_t        * heap_new (GtsSurface * s);
  53 static void            heap_destroy (heap_t * heap);
  54 static gboolean        heap_is_empty (const heap_t * heap);
  55 static GtsTriangle   * heap_top (const heap_t * heap);
  56 static void            heap_remove (heap_t * heap, GtsTriangle * t);
  57
  58 /* helper functions */
  59
  60 static gboolean vertices_are_unique (GtsVertex * v1,
  61                                      GtsVertex * v2,
  62                                      GtsVertex * v3)
  63 {
  64   g_assert (v1 && v2 && v3);
  65   return (v1 != v2 && v1 != v3 && v2 != v3);
  66 }
  67
  68 static gboolean vertex_is_one_of (GtsVertex * v,
  69                                   GtsVertex * v1,
  70                                   GtsVertex * v2,
  71                                   GtsVertex * v3)
  72 {
  73   g_assert (v && v1 && v2 && v3);
  74   return v == v1 || v == v2 || v == v3;
  75 }
  76
  77 static guint num_shared_vertices (GtsVertex * u1,
  78                                   GtsVertex * u2,
  79                                   GtsVertex * u3,
  80                                   GtsVertex * v1,
  81                                   GtsVertex * v2,
  82                                   GtsVertex * v3)
  83 {
  84   guint n = 0;
  85
  86   g_assert (u1 && u2 && u3);
  87   g_assert (v1 && v2 && v3);
  88   g_assert (vertices_are_unique (u1, u2, u3));
  89   g_assert (vertices_are_unique (v1, v2, v3));
  90
  91   if (vertex_is_one_of (v1, u1, u2, u3))
  92     n++;
  93   if (vertex_is_one_of (v2, u1, u2, u3))
  94     n++;
  95   if (vertex_is_one_of (v3, u1, u2, u3))
  96     n++;
  97   return n;
  98 }
  99
 100 static gboolean vertices_match (GtsVertex * v1,
 101                                 GtsVertex * v2,
 102                                 GtsVertex * v3,
 103                                 GtsVertex ** v4,
 104                                 GtsVertex ** v5,
 105                                 GtsVertex ** v6)
 106 {
 107   guint i;
 108
 109   g_assert (v4 && v5 && v6);
 110   g_assert (*v4 && *v5 && *v6);
 111   g_assert (vertices_are_unique (*v4, *v5, *v6));
 112
 113   for (i = 0; i < 2; i++) {
 114     if ((!v1 || (v1 == *v4)) &&
 115         (!v2 || (v2 == *v5)) &&
 116         (!v3 || (v3 == *v6)))
 117       return TRUE;
 118     else {
 119       GtsVertex * v7 = * v4;
 120
 121       *v4 = *v5;
 122       *v5 = *v6;
 123       *v6 = v7;
 124     }
 125   }
 126   return ((!v1 || (v1 == *v4)) &&
 127           (!v2 || (v2 == *v5)) &&
 128           (!v3 || (v3 == *v6)));
 129 }
 130
 131 static GtsVertex * non_shared_vertex1 (GtsVertex * u1,
 132                                        GtsVertex * u2,
 133                                        GtsVertex * u3,
 134                                        GtsVertex * v1,
 135                                        GtsVertex * v2,
 136                                        GtsVertex * v3)
 137 {
 138   GtsVertex * u = NULL;
 139
 140   g_assert (u1 && u2 && u3);
 141   g_assert (v1 && v2 && v3);
 142   g_assert (vertices_are_unique (u1, u2, u3));
 143   g_assert (vertices_are_unique (v1, v2, v3));
 144   g_assert (num_shared_vertices (u1, u2, u3, v1, v2, v3) == 2);
 145
 146   if (!vertex_is_one_of (u1, v1, v2, v3)) {
 147     g_assert (vertex_is_one_of (u2, v1, v2, v3));
 148     g_assert (vertex_is_one_of (u3, v1, v2, v3));
 149     u = u1;
 150   } else if (!vertex_is_one_of (u2, v1, v2, v3)) {
 151     g_assert (vertex_is_one_of (u1, v1, v2, v3));
 152     g_assert (vertex_is_one_of (u3, v1, v2, v3));
 153     u = u2;
 154   } else if (!vertex_is_one_of (u3, v1, v2, v3)) {
 155     g_assert (vertex_is_one_of (u1, v1, v2, v3));
 156     g_assert (vertex_is_one_of (u2, v1, v2, v3));
 157     u = u3;
 158   } else
 159     g_assert_not_reached ();
 160
 161   return u;
 162 }
 163
 164 static void match_vertex (GtsVertex * v,
 165                           GtsVertex ** v1,
 166                           GtsVertex ** v2,
 167                           GtsVertex ** v3)
 168 {
 169   g_assert (v && v1 && v2 && v3);
 170   g_assert (*v1 && *v2 && *v3);
 171   g_assert (vertex_is_one_of (v, *v1, *v2, *v3));
 172   while (*v1 != v) {
 173     GtsVertex *v0 = *v1;
 174
 175     *v1 = *v2;
 176     *v2 = *v3;
 177     *v3 = v0;
 178   }
 179 }
 180
 181 /* tri_data_t functions */
 182
 183 static tri_data_t * tri_data_new (GtsTriangle * t)
 184 {
 185   tri_data_t * td;
 186
 187   td = g_malloc (sizeof (tri_data_t));
 188   td->t = t;
 189   td->used = FALSE;
 190   td->neighbors = gts_triangle_neighbors (t);
 191   td->pos = NULL;
 192
 193   return td;
 194 }
 195
 196 static void tri_data_destroy (tri_data_t * td)
 197 {
 198   if (!td)
 199     return;
 200   g_slist_free (td->neighbors);
 201   g_free (td);
 202 }
 203
 204 static guint tri_data_num_unused_neighbors2 (const tri_data_t * td,
 205                                              const map_t * map)
 206 {
 207   GHashTable *h;
 208   guint n;
 209
 210   g_assert (td);
 211   g_assert (map);
 212   h = tri_data_unused_neighbors2 (td, map);
 213   n = g_hash_table_size (h);
 214   g_hash_table_destroy (h);
 215   return n;
 216 }
 217
 218 static void copy_key_to_array (gpointer key,
 219                                gpointer value,
 220                                gpointer user_data)
 221 {
 222   GtsTriangle * t = key;
 223   GtsTriangle *** p = user_data;
 224
 225   (void) value;
 226   g_assert (t);
 227   g_assert (p && *p);
 228   **p = t;
 229   (*p)++;
 230 }
 231
 232 static gboolean are_neighbors_unique (GHashTable *h)
 233 {
 234   GtsTriangle ** a;
 235   GtsTriangle ** p;
 236   gint i, j, n;         /* guint won't work if n == 0 */
 237
 238   g_assert (h);
 239   n = g_hash_table_size (h);
 240 #ifdef DEBUG
 241   if (n > 9)
 242     g_warning ("triangle has %d 2-level neighbors", n);
 243 #endif /* DEBUG */
 244   a = g_malloc(n*sizeof (GtsTriangle *));
 245   p = a;
 246   g_hash_table_foreach (h, copy_key_to_array, &p);
 247   for (i = 0; i < n - 1; i++) {
 248     g_assert (a[i]);
 249     for (j = i + 1; j < n; j++) {
 250       g_assert (a[j]);
 251       if (a[i] == a[j]) {
 252         g_free (a);
 253         return FALSE;
 254       }
 255     }
 256   }
 257   g_free (a);
 258   return TRUE;
 259 }
 260
 261 static GHashTable * tri_data_unused_neighbors2 (const tri_data_t * td,
 262                                                 const map_t * map)
 263 {
 264   GHashTable * h = g_hash_table_new (NULL, NULL);
 265   GSList * li;
 266
 267   g_assert (td);
 268   g_assert (map);
 269   for (li = td->neighbors; li != NULL; li = li->next) {
 270     GtsTriangle * t2 = li->data;
 271     tri_data_t * td2 = map_lookup (map, t2);
 272     GSList * lj;
 273
 274     g_assert (td2);
 275     if (!td2->used) {
 276       g_hash_table_insert (h, t2, td2);
 277       for (lj = td2->neighbors; lj != NULL; lj = lj->next) {
 278         GtsTriangle * t3 = lj->data;
 279         tri_data_t * td3 = map_lookup (map, t3);
 280
 281         g_assert (td3);
 282         if (td3 != td && !td3->used)
 283           g_hash_table_insert (h, t3, td3);
 284       }
 285     }
 286   }
 287   g_assert (are_neighbors_unique (h));
 288   return h;
 289 }
 290
 291 #if PRINT_HEAP_ELEMENTS
 292 static void tri_data_print (const tri_data_t * td, FILE * fp)
 293 {
 294   g_assert (td);
 295   g_assert (fp);
 296   fprintf(fp, "td=%p t=%p used=%d pos=%p key=%f\n",
 297           td, td->t, td->used, td->pos,
 298           td->pos ? td->pos->key : -1.0);
 299 }
 300 #endif /* PRINT_HEAP_ELEMENTS */
 301
 302 /* heap_t functions */
 303
 304 static gdouble triangle_priority (gpointer item, gpointer data)
 305 {
 306   GtsTriangle * t = item;
 307   map_t * map = data;
 308   tri_data_t * td;
 309   gdouble k;
 310
 311   g_assert (t);
 312   g_assert (map);
 313   td = map_lookup (map, t);
 314   g_assert (td);
 315   k = tri_data_num_unused_neighbors2 (td, map);
 316   return k;
 317 }
 318
 319 #if PRINT_HEAP_ELEMENTS
 320 static void print_heap_element (gpointer data, gpointer user_data)
 321 {
 322   GtsTriangle * t = data;
 323   map_t * map = user_data;
 324   tri_data_t * td;
 325
 326   g_assert (t);
 327   g_assert (map);
 328   td = map_lookup (map, t);
 329   g_assert (td);
 330   g_assert (!td->used);
 331   g_assert (td->pos);
 332   tri_data_print (td, stderr);
 333 }
 334 #endif /* PRINT_HEAP_ELEMENTS */
 335
 336 static void insert_entry_into_heap (gpointer key,
 337                                     gpointer value,
 338                                     gpointer user_data)
 339 {
 340   GtsTriangle * t = key;
 341   tri_data_t * td = value;
 342   GtsEHeap * heap = user_data;
 343
 344   g_assert (!td->pos);
 345   td->pos = gts_eheap_insert (heap, t);
 346   g_assert (td->pos);
 347 }
 348
 349 static heap_t * heap_new (GtsSurface *s)
 350 {
 351   heap_t * heap;
 352
 353   g_assert (s);
 354   heap = g_malloc (sizeof (heap_t));
 355   heap->map = map_new (s);
 356   heap->heap = gts_eheap_new (triangle_priority, heap->map);
 357   g_hash_table_foreach (heap->map->ht,
 358                         insert_entry_into_heap,
 359                         heap->heap);
 360 #if PRINT_HEAP_ELEMENTS
 361   gts_eheap_foreach (heap->heap, print_heap_element, heap->map);
 362 #endif /* PRINT_HEAP_ELEMENTS */
 363   return heap;
 364 }
 365
 366 static void heap_destroy (heap_t * heap)
 367 {
 368   if (!heap)
 369     return;
 370   map_destroy (heap->map);
 371   gts_eheap_destroy (heap->heap);
 372   g_free (heap);
 373 }
 374
 375 static gboolean heap_is_empty (const heap_t * heap)
 376 {
 377   g_assert (heap);
 378   g_assert (heap->heap);
 379   return gts_eheap_size (heap->heap) == 0;
 380 }
 381
 382 typedef struct {
 383   const heap_t * heap;
 384   double min_key;
 385 } min_key_t;
 386
 387 static GtsTriangle * heap_top (const heap_t * heap)
 388 {
 389   GtsTriangle * t;
 390
 391   g_assert (heap);
 392   g_assert (heap->heap);
 393   t = gts_eheap_top (heap->heap, NULL);
 394   return t;
 395 }
 396
 397 static void decrease_key (gpointer key, gpointer value, gpointer user_data)
 398 {
 399   GtsTriangle * t = key;
 400   tri_data_t * td = value;
 401   heap_t *heap = user_data;
 402   gdouble k;
 403
 404   (void) t;
 405   g_assert (heap);
 406   g_assert (heap->map);
 407   g_assert (heap->heap);
 408   g_assert (td);
 409   g_assert (!td->used);
 410   g_assert (td->pos);
 411
 412   k = tri_data_num_unused_neighbors2 (td, heap->map);
 413   g_assert (k <= td->pos->key);
 414 #ifdef DEBUG
 415   if (k == td->pos->key)
 416     g_warning ("same key: %f\n", k);
 417 #endif /* DEBUG */
 418   if (k != td->pos->key) {
 419     g_assert (k < td->pos->key);
 420     g_assert (k >= 0.0);
 421     gts_eheap_decrease_key (heap->heap, td->pos, k);
 422   }
 423 }
 424
 425 static void heap_remove (heap_t * heap, GtsTriangle * t)
 426 {
 427   tri_data_t * td;
 428   GHashTable * h;
 429
 430   g_assert (heap);
 431   g_assert (t);
 432   td = map_lookup (heap->map, t);
 433   g_assert (td);
 434   g_assert (!td->used);
 435   g_assert (td->pos);
 436   td->used = TRUE;
 437   gts_eheap_remove (heap->heap, td->pos);
 438   td->pos = NULL;
 439
 440   /*    fprintf(stderr, "td: %p\n", td); */
 441   h = tri_data_unused_neighbors2 (td, heap->map);
 442   g_hash_table_foreach (h, decrease_key, heap);
 443   g_hash_table_destroy (h);
 444 }
 445
 446 /* map_t functions */
 447
 448 static gint create_map_entry (gpointer item, gpointer data)
 449 {
 450   GtsTriangle * t = item;
 451   GHashTable * ht = data;
 452   tri_data_t * td;
 453
 454   g_assert (t);
 455   g_assert (ht);
 456   td = tri_data_new (t);
 457   g_hash_table_insert (ht, t, td);
 458   return 0;
 459 }
 460
 461 static void free_map_entry (gpointer key, gpointer value, gpointer user_data)
 462 {
 463   GtsTriangle * t = key;
 464   tri_data_t * td = value;
 465
 466   (void) user_data;
 467   g_assert (t);
 468   g_assert (td);
 469   g_assert (td->t == t);
 470   tri_data_destroy (td);
 471 }
 472
 473 static map_t * map_new (GtsSurface * s)
 474 {
 475   map_t * map;
 476
 477   map = g_malloc (sizeof (map_t));
 478   map->ht = g_hash_table_new (NULL, NULL);
 479   gts_surface_foreach_face (s, create_map_entry, map->ht);
 480   return map;
 481 }
 482
 483 static void map_destroy (map_t * map)
 484 {
 485   if (!map)
 486     return;
 487   g_hash_table_foreach (map->ht, free_map_entry, NULL);
 488   g_hash_table_destroy (map->ht);
 489   g_free (map);
 490 }
 491
 492 static tri_data_t * map_lookup (const map_t * map, GtsTriangle * t)
 493 {
 494   tri_data_t * td;
 495
 496   g_assert (map);
 497   g_assert (map->ht);
 498   g_assert (t);
 499   td = g_hash_table_lookup (map->ht, t);
 500   g_assert (td);
 501   g_assert (td->t == t);
 502   return td;
 503 }
 504
 505 /* other helper functions */
 506
 507 static GtsTriangle * find_min_neighbor (heap_t * heap, GtsTriangle * t)
 508 {
 509   GtsTriangle * min_neighbor = NULL;
 510   gdouble min_key = G_MAXDOUBLE;
 511   tri_data_t * td;
 512   GSList * li;
 513
 514   g_assert (heap);
 515   g_assert (t);
 516
 517   td = map_lookup (heap->map, t);
 518   for (li = td->neighbors; li != NULL; li = li->next) {
 519     GtsTriangle * t2 = li->data;
 520     tri_data_t * td2 = map_lookup (heap->map, t2);
 521     gdouble k;
 522
 523     g_assert (td2);
 524     if (td2->used)
 525       continue;
 526     g_assert (td2->pos);
 527     k = td2->pos->key;
 528     if (k < min_key) {
 529       min_key = k;
 530       min_neighbor = t2;
 531     }
 532   }
 533   return min_neighbor;
 534 }
 535
 536 static GtsTriangle * find_neighbor_forward (heap_t * heap,
 537                                             GtsTriangle * t,
 538                                             GtsVertex ** v1,
 539                                             GtsVertex ** v2,
 540                                             GtsVertex ** v3,
 541                                             gboolean left_turn)
 542 {
 543   GtsTriangle * neighbor = NULL;
 544   tri_data_t * td;
 545   GSList * li;
 546
 547   g_assert (heap);
 548   g_assert (t);
 549   g_assert (v1 && v2 && v3);
 550   g_assert (vertices_are_unique (*v1, *v2, *v3));
 551
 552   td = map_lookup (heap->map, t);
 553   g_assert (td);
 554   for (li = td->neighbors; li && !neighbor; li = li->next) {
 555     GtsTriangle * t2 = li->data;
 556     tri_data_t * td2 = map_lookup (heap->map, t2);
 557     GtsVertex * v4, * v5, * v6;
 558
 559     g_assert (td2);
 560     if (t2 == t || td2->used)
 561       continue;
 562     gts_triangle_vertices (t2, &v4, &v5, &v6);
 563     if (left_turn) {
 564       if (!vertices_match (*v1, *v3, NULL, &v4, &v5, &v6))
 565         continue;
 566     } else {
 567       if (!vertices_match (*v3, *v2, NULL, &v4, &v5, &v6))
 568         continue;
 569     }
 570     neighbor = t2;
 571     *v1 = v4;
 572     *v2 = v5;
 573     *v3 = v6;
 574   }
 575   return neighbor;
 576 }
 577
 578 static GtsTriangle * find_neighbor_backward (heap_t * heap,
 579                                              GtsTriangle * t,
 580                                              GtsVertex ** v1,
 581                                              GtsVertex ** v2,
 582                                              GtsVertex ** v3,
 583                                              gboolean left_turn)
 584 {
 585   GtsTriangle * neighbor = NULL;
 586   tri_data_t * td;
 587   GSList * li;
 588
 589   g_assert (heap);
 590   g_assert (t);
 591   g_assert (v1 && v2 && v3);
 592   g_assert (vertices_are_unique (*v1, *v2, *v3));
 593
 594   td = map_lookup (heap->map, t);
 595   g_assert (td);
 596   for (li = td->neighbors; li && !neighbor; li = li->next) {
 597     GtsTriangle * t2 = li->data;
 598     tri_data_t * td2 = map_lookup (heap->map, t2);
 599     GtsVertex * v4, * v5, * v6;
 600
 601     g_assert (td2);
 602     if (t2 == t || td2->used)
 603       continue;
 604     gts_triangle_vertices (t2, &v4, &v5, &v6);
 605     if (left_turn) {
 606       if (!vertices_match (NULL, *v2, *v1, &v4, &v5, &v6))
 607         continue;
 608     } else if (!vertices_match(*v1, NULL, *v2, &v4, &v5, &v6))
 609       continue;
 610     neighbor = t2;
 611     *v1 = v4;
 612     *v2 = v5;
 613     *v3 = v6;
 614   }
 615   return neighbor;
 616 }
 617
 618 static GSList * grow_strip_forward (heap_t * heap,
 619                                     GSList * strip,
 620                                     GtsTriangle * t,
 621                                     GtsVertex * v1,
 622                                     GtsVertex * v2,
 623                                     GtsVertex * v3)
 624 {
 625   gboolean left_turn;
 626
 627   g_assert (heap);
 628   g_assert (g_slist_length(strip) == 2);
 629   g_assert (t);
 630   g_assert (v1 && v2 && v3);
 631   g_assert (vertices_are_unique (v1, v2, v3));
 632
 633   left_turn = TRUE;
 634   while ((t = find_neighbor_forward (heap, t, &v1, &v2, &v3,
 635                                      left_turn)) != NULL) {
 636     heap_remove (heap, t);
 637     strip = g_slist_prepend (strip, t);
 638     left_turn = !left_turn;
 639   }
 640   return strip;
 641 }
 642
 643 static GSList * grow_strip_backward (heap_t * heap,
 644                                      GSList * strip,
 645                                      GtsTriangle * t,
 646                                      GtsVertex * v1,
 647                                      GtsVertex * v2,
 648                                      GtsVertex * v3)
 649 {
 650   /* we have to make sure we add an even number of triangles */
 651   GtsTriangle * t2;
 652
 653   g_assert (heap);
 654   g_assert (g_slist_length(strip) >= 2);
 655   g_assert (t);
 656   g_assert (v1 && v2 && v3);
 657   g_assert (vertices_are_unique (v1, v2, v3));
 658
 659   while ((t2 = find_neighbor_backward (heap, t, &v1, &v2, &v3,
 660                                        FALSE)) != NULL
 661          && (t = find_neighbor_backward (heap, t2, &v1, &v2, &v3,
 662                                          TRUE)) != NULL) {
 663     heap_remove (heap, t2);
 664     heap_remove (heap, t);
 665     strip = g_slist_prepend (strip, t2);
 666     strip = g_slist_prepend (strip, t);
 667   }
 668   return strip;
 669 }
 670
 671 static gboolean find_right_turn (GtsVertex ** v1,
 672                                  GtsVertex ** v2,
 673                                  GtsVertex ** v3,
 674                                  GtsVertex ** v4,
 675                                  GtsVertex ** v5,
 676                                  GtsVertex ** v6)
 677 {
 678   GtsVertex * v;
 679
 680   g_assert (v1 && v2 && v3);
 681   g_assert (v4 && v5 && v6);
 682   g_assert (vertices_are_unique (*v1, *v2, *v3));
 683   g_assert (vertices_are_unique (*v4, *v5, *v6));
 684   g_assert (num_shared_vertices (*v1, *v2, *v3, *v4, *v5, *v6) == 2);
 685
 686   v = non_shared_vertex1 (*v1, *v2, *v3, *v4, *v5, *v6);
 687   match_vertex (v, v1, v2, v3);
 688   match_vertex (*v3, v4, v5, v6);
 689
 690   g_assert (v1 && v2 && v3);
 691   g_assert (v4 && v5 && v6);
 692   g_assert (*v4 == *v3);
 693
 694   if (*v5 == *v2) {
 695     g_assert (vertices_are_unique (*v1, *v2, *v3));
 696     g_assert (vertices_are_unique (*v4, *v5, *v6));
 697     g_assert (num_shared_vertices (*v1, *v2, *v3,
 698                                         *v4, *v5, *v6) == 2);
 699     return TRUE;
 700   } else {
 701 #ifdef DEBUG
 702     g_warning ("couldn't find a right turn");
 703 #endif /* DEBUG */
 704     return FALSE;
 705   }
 706 }
 707
 708 /**
 709  * gts_surface_strip:
 710  * @s: a #GtsSurface.
 711  *
 712  * Decompose @s into triangle strips for fast-rendering.
 713  *
 714  * Returns: a list of triangle strips containing all the triangles of @s.
 715  * A triangle strip is itself a list of successive triangles having one edge
 716  * in common.
 717  */
 718 GSList * gts_surface_strip (GtsSurface *s)
 719 {
 720   GSList * strips = NULL;
 721   heap_t * heap;
 722
 723   g_return_val_if_fail (s != NULL, NULL);
 724
 725   heap = heap_new (s);
 726   while (!heap_is_empty (heap)) {
 727     GtsTriangle * t1, * t2;
 728     GtsVertex * v1, * v2, * v3, * v4, * v5, * v6;
 729     GSList * strip = NULL;
 730
 731     /* remove heap top */
 732     t1 = heap_top (heap);
 733     g_assert (t1);
 734     heap_remove (heap, t1);
 735
 736     /* start a new strip */
 737     strip = g_slist_prepend (strip, t1);
 738
 739     /* find second triangle */
 740     t2 = find_min_neighbor (heap, t1);
 741     if (t2) {
 742       g_assert (t2 != t1);
 743
 744       /* find right turn */
 745       gts_triangle_vertices (t1, &v1, &v2, &v3);
 746       gts_triangle_vertices (t2, &v4, &v5, &v6);
 747       if (find_right_turn (&v1, &v2, &v3, &v4, &v5, &v6)) {
 748         heap_remove (heap, t2);
 749         strip = g_slist_prepend (strip, t2);
 750
 751         /* grow strip forward */
 752         strip = grow_strip_forward (heap, strip, t2, v4, v5, v6);
 753
 754         strip = g_slist_reverse (strip);
 755
 756         /* grow strip backward */
 757         strip = grow_strip_backward (heap, strip, t1, v1, v2, v3);
 758       }
 759     }
 760     strips = g_slist_prepend (strips, strip);
 761   }
 762   strips = g_slist_reverse (strips);
 763   heap_destroy (heap);
 764
 765   return strips;
 766 }