gts/vertex.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 <math.h>
  21 #include "gts.h"
  22
  23 gboolean gts_allow_floating_vertices = FALSE;
  24
  25 static void vertex_destroy (GtsObject * object)
  26 {
  27   GtsVertex * vertex = GTS_VERTEX (object);
  28   GSList * i;
  29
  30   i = vertex->segments;
  31   while (i) {
  32     GTS_OBJECT_SET_FLAGS (i->data, GTS_DESTROYED);
  33     i = i->next;
  34   }
  35   i = vertex->segments;
  36   while (i) {
  37     GSList * next = i->next;
  38     gts_object_destroy (i->data);
  39     i = next;
  40   }
  41   g_assert (vertex->segments == NULL);
  42
  43   (* GTS_OBJECT_CLASS (gts_vertex_class ())->parent_class->destroy) (object);
  44 }
  45
  46 static void vertex_clone (GtsObject * clone, GtsObject * object)
  47 {
  48   (* GTS_OBJECT_CLASS (gts_vertex_class ())->parent_class->clone) (clone,
  49                                                                    object);
  50   GTS_VERTEX (clone)->segments = NULL;
  51 }
  52
  53 static void vertex_class_init (GtsVertexClass * klass)
  54 {
  55   klass->intersection_attributes = NULL;
  56   GTS_OBJECT_CLASS (klass)->clone = vertex_clone;
  57   GTS_OBJECT_CLASS (klass)->destroy = vertex_destroy;
  58 }
  59
  60 static void vertex_init (GtsVertex * vertex)
  61 {
  62   vertex->segments = NULL;
  63 }
  64
  65 /**
  66  * gts_vertex_class:
  67  *
  68  * Returns: the #GtsVertexClass.
  69  */
  70 GtsVertexClass * gts_vertex_class (void)
  71 {
  72   static GtsVertexClass * klass = NULL;
  73
  74   if (klass == NULL) {
  75     GtsObjectClassInfo vertex_info = {
  76       "GtsVertex",
  77       sizeof (GtsVertex),
  78       sizeof (GtsVertexClass),
  79       (GtsObjectClassInitFunc) vertex_class_init,
  80       (GtsObjectInitFunc) vertex_init,
  81       (GtsArgSetFunc) NULL,
  82       (GtsArgGetFunc) NULL
  83     };
  84     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_point_class ()),
  85                                   &vertex_info);
  86   }
  87
  88   return klass;
  89 }
  90
  91 /**
  92  * gts_vertex_new:
  93  * @klass: a #GtsVertexClass.
  94  * @x: the x-coordinate of the vertex to create.
  95  * @y: the y-coordinate of the vertex to create.
  96  * @z: the y-coordinate of the vertex to create.
  97  *
  98  * Returns: a new #GtsVertex with @x, @y and @z as coordinates.
  99  */
 100 GtsVertex * gts_vertex_new (GtsVertexClass * klass,
 101                             gdouble x, gdouble y, gdouble z)
 102 {
 103   GtsVertex * v;
 104
 105   v = GTS_VERTEX (gts_object_new (GTS_OBJECT_CLASS (klass)));
 106   gts_point_set (GTS_POINT (v), x, y, z);
 107
 108   return v;
 109 }
 110
 111 /**
 112  * gts_vertex_replace:
 113  * @v: a #GtsVertex.
 114  * @with: another #GtsVertex.
 115  *
 116  * Replaces vertex @v with vertex @with. @v and @with must be
 117  * different.  All the #GtsSegment which have @v has one of their
 118  * vertices are updated.  The segments list of vertex @v is freed and
 119  * @v->segments is set to %NULL.
 120  */
 121 void gts_vertex_replace (GtsVertex * v, GtsVertex * with)
 122 {
 123   GSList * i;
 124
 125   g_return_if_fail (v != NULL);
 126   g_return_if_fail (with != NULL);
 127   g_return_if_fail (v != with);
 128
 129   i = v->segments;
 130   while (i) {
 131     GtsSegment * s = i->data;
 132     if (s->v1 != with && s->v2 != with)
 133       with->segments = g_slist_prepend (with->segments, s);
 134     if (s->v1 == v) s->v1 = with;
 135     if (s->v2 == v) s->v2 = with;
 136     i = i->next;
 137   }
 138   g_slist_free (v->segments);
 139   v->segments = NULL;
 140 }
 141
 142 /**
 143  * gts_vertex_is_unattached:
 144  * @v: a #GtsVertex.
 145  *
 146  * Returns: %TRUE if @v is not the endpoint of any #GtsSegment,
 147  * %FALSE otherwise.
 148  */
 149 gboolean gts_vertex_is_unattached (GtsVertex * v)
 150 {
 151   g_return_val_if_fail (v != NULL, FALSE);
 152   if (v->segments == NULL)
 153     return TRUE;
 154   return FALSE;
 155 }
 156
 157 /**
 158  * gts_vertices_are_connected:
 159  * @v1: a #GtsVertex.
 160  * @v2: another #GtsVertex.
 161  *
 162  * Returns: if @v1 and @v2 are the vertices of the same #GtsSegment
 163  * this segment else %NULL.
 164  */
 165 GtsSegment * gts_vertices_are_connected (GtsVertex * v1, GtsVertex * v2)
 166 {
 167   GSList * i;
 168
 169   g_return_val_if_fail (v1 != NULL, FALSE);
 170   g_return_val_if_fail (v2 != NULL, FALSE);
 171
 172   i = v1->segments;
 173   while (i) {
 174     GtsSegment * s = i->data;
 175
 176     if (s->v1 == v2 || s->v2 == v2)
 177       return s;
 178     i = i->next;
 179   }
 180   return NULL;
 181 }
 182
 183 /**
 184  * gts_vertices_from_segments:
 185  * @segments: a list of #GtsSegment.
 186  *
 187  * Returns: a list of #GtsVertex, vertices of a #GtsSegment in @segments.
 188  * Each element in the list is unique (no duplicates).
 189  */
 190 GSList * gts_vertices_from_segments (GSList * segments)
 191 {
 192   GHashTable * hash;
 193   GSList * vertices = NULL, * i;
 194
 195   hash = g_hash_table_new (NULL, NULL);
 196   i = segments;
 197   while (i) {
 198     GtsSegment * s = i->data;
 199     if (g_hash_table_lookup (hash, s->v1) == NULL) {
 200       vertices = g_slist_prepend (vertices, s->v1);
 201       g_hash_table_insert (hash, s->v1, s);
 202     }
 203     if (g_hash_table_lookup (hash, s->v2) == NULL) {
 204       vertices = g_slist_prepend (vertices, s->v2);
 205       g_hash_table_insert (hash, s->v2, s);
 206     }
 207     i = i->next;
 208   }
 209   g_hash_table_destroy (hash);
 210   return vertices;
 211 }
 212
 213 /**
 214  * gts_vertex_triangles:
 215  * @v: a #GtsVertex.
 216  * @list: a list of #GtsTriangle.
 217  *
 218  * Adds all the #GtsTriangle which share @v as a vertex and do not
 219  * already belong to @list.
 220  *
 221  * Returns: the new list of unique #GtsTriangle which share @v as a
 222  * vertex.
 223  */
 224 GSList * gts_vertex_triangles (GtsVertex * v,
 225                                GSList * list)
 226 {
 227   GSList * i;
 228
 229   g_return_val_if_fail (v != NULL, NULL);
 230
 231   i = v->segments;
 232   while (i) {
 233     GtsSegment * s = i->data;
 234     if (GTS_IS_EDGE (s)) {
 235       GSList * j = GTS_EDGE (s)->triangles;
 236       while (j) {
 237         if (!g_slist_find (list, j->data))
 238           list = g_slist_prepend (list, j->data);
 239         j = j->next;
 240       }
 241     }
 242     i = i->next;
 243   }
 244   return list;
 245 }
 246
 247 /**
 248  * gts_vertex_faces:
 249  * @v: a #GtsVertex.
 250  * @surface: a #GtsSurface or %NULL.
 251  * @list: a list of #GtsFace.
 252  *
 253  * Adds all the #GtsFace belonging to @surface (if not %NULL) which share
 254  * @v as a vertex and do not already belong to @list.
 255  *
 256  * Returns: the new list of unique #GtsFace belonging to @surface
 257  * which share @v as a vertex.
 258  */
 259 GSList * gts_vertex_faces (GtsVertex * v,
 260                            GtsSurface * surface,
 261                            GSList * list)
 262 {
 263   GSList * i;
 264
 265   g_return_val_if_fail (v != NULL, NULL);
 266
 267   i = v->segments;
 268   while (i) {
 269     GtsSegment * s = i->data;
 270     if (GTS_IS_EDGE (s)) {
 271       GSList * j = GTS_EDGE (s)->triangles;
 272       while (j) {
 273         GtsTriangle * t = j->data;
 274         if (GTS_IS_FACE (t)
 275             &&
 276             (!surface || gts_face_has_parent_surface (GTS_FACE (t), surface))
 277             &&
 278             !g_slist_find (list, t))
 279           list = g_slist_prepend (list, t);
 280         j = j->next;
 281       }
 282     }
 283     i = i->next;
 284   }
 285   return list;
 286 }
 287
 288 /**
 289  * gts_vertex_neighbors:
 290  * @v: a #GtsVertex.
 291  * @list: a list of #GtsVertex.
 292  * @surface: a #GtsSurface or %NULL.
 293  *
 294  * Adds to @list all the #GtsVertex connected to @v by a #GtsSegment and not
 295  * already in @list. If @surface is not %NULL only the vertices connected to
 296  * @v by an edge belonging to @surface are considered.
 297  *
 298  * Returns: the new list of unique #GtsVertex.
 299  */
 300 GSList * gts_vertex_neighbors (GtsVertex * v,
 301                                GSList * list,
 302                                GtsSurface * surface)
 303 {
 304   GSList * i;
 305
 306   g_return_val_if_fail (v != NULL, NULL);
 307
 308   i = v->segments;
 309   while (i) {
 310     GtsSegment * s = i->data;
 311     GtsVertex * v1 = s->v1 == v ? s->v2 : s->v1;
 312     if (v1 != v &&
 313         (!surface ||
 314          (GTS_IS_EDGE (s) &&
 315           gts_edge_has_parent_surface (GTS_EDGE (s), surface))) &&
 316         !g_slist_find (list, v1))
 317       list = g_slist_prepend (list, v1);
 318     i = i->next;
 319   }
 320   return list;
 321 }
 322
 323 /**
 324  * gts_vertex_is_boundary:
 325  * @v: a #GtsVertex.
 326  * @surface: a #GtsSurface or %NULL.
 327  *
 328  * Returns: %TRUE if @v is used by a #GtsEdge boundary of @surface as
 329  * determined by gts_edge_is_boundary(), %FALSE otherwise.
 330  */
 331 gboolean gts_vertex_is_boundary (GtsVertex * v, GtsSurface * surface)
 332 {
 333   GSList * i;
 334
 335   g_return_val_if_fail (v != NULL, FALSE);
 336
 337   i = v->segments;
 338   while (i) {
 339     if (GTS_IS_EDGE (i->data) &&
 340         gts_edge_is_boundary (i->data, surface))
 341       return TRUE;
 342     i = i->next;
 343   }
 344
 345   return FALSE;
 346 }
 347
 348 /**
 349  * gts_vertices_merge:
 350  * @vertices: a list of #GtsVertex.
 351  * @epsilon: half the size of the bounding box to consider for each vertex.
 352  * @check: function called for each pair of vertices about to be merged
 353  * or %NULL.
 354  *
 355  * For each vertex v in @vertices look if there are any vertex of
 356  * @vertices contained in a box centered on v of size 2*@epsilon. If
 357  * there are and if @check is not %NULL and returns %TRUE, replace
 358  * them with v (using gts_vertex_replace()), destroy them and remove
 359  * them from list.  This is done efficiently using Kd-Trees.
 360  *
 361  * Returns: the updated list of vertices.
 362  */
 363 GList * gts_vertices_merge (GList * vertices,
 364                             gdouble epsilon,
 365                             gboolean (* check) (GtsVertex *, GtsVertex *))
 366 {
 367   GPtrArray * array;
 368   GList * i;
 369   GNode * kdtree;
 370
 371   g_return_val_if_fail (vertices != NULL, 0);
 372
 373   array = g_ptr_array_new ();
 374   i = vertices;
 375   while (i) {
 376     g_ptr_array_add (array, i->data);
 377     i = i->next;
 378   }
 379   kdtree = gts_kdtree_new (array, NULL);
 380   g_ptr_array_free (array, TRUE);
 381
 382   i = vertices;
 383   while (i) {
 384     GtsVertex * v = i->data;
 385     if (!GTS_OBJECT (v)->reserved) { /* Do something only if v is active */
 386       GtsBBox * bbox;
 387       GSList * selected, * j;
 388
 389       /* build bounding box */
 390       bbox = gts_bbox_new (gts_bbox_class (),
 391                            v,
 392                            GTS_POINT (v)->x - epsilon,
 393                            GTS_POINT (v)->y - epsilon,
 394                            GTS_POINT (v)->z - epsilon,
 395                            GTS_POINT (v)->x + epsilon,
 396                            GTS_POINT (v)->y + epsilon,
 397                            GTS_POINT (v)->z + epsilon);
 398
 399       /* select vertices which are inside bbox using kdtree */
 400       j = selected = gts_kdtree_range (kdtree, bbox, NULL);
 401       while (j) {
 402         GtsVertex * sv = j->data;
 403         if (sv != v && !GTS_OBJECT (sv)->reserved && (!check || (*check) (sv, v))) {
 404           /* sv is not v and is active */
 405           gts_vertex_replace (sv, v);
 406           GTS_OBJECT (sv)->reserved = sv; /* mark sv as inactive */
 407         }
 408         j = j->next;
 409       }
 410       g_slist_free (selected);
 411       gts_object_destroy (GTS_OBJECT (bbox));
 412     }
 413     i = i->next;
 414   }
 415
 416   gts_kdtree_destroy (kdtree);
 417
 418   /* destroy inactive vertices and removes them from list */
 419
 420   /* we want to control vertex destruction */
 421   gts_allow_floating_vertices = TRUE;
 422
 423   i = vertices;
 424   while (i) {
 425     GtsVertex * v = i->data;
 426     GList * next = i->next;
 427     if (GTS_OBJECT (v)->reserved) { /* v is inactive */
 428       gts_object_destroy (GTS_OBJECT (v));
 429       vertices = g_list_remove_link (vertices, i);
 430       g_list_free_1 (i);
 431     }
 432     i = next;
 433   }
 434   gts_allow_floating_vertices = FALSE;
 435
 436   return vertices;
 437 }
 438
 439 /* returns the list of edges belonging to @surface turning around @v */
 440 static GSList * edge_fan_list (GtsVertex * v,
 441                                GtsSurface * surface,
 442                                GtsFace * f,
 443                                GtsEdge * e,
 444                                GtsFace * first)
 445 {
 446   GSList * i = e->triangles;
 447   GtsFace * neighbor = NULL;
 448   GtsEdge * next = NULL, * enext = NULL;
 449
 450   while (i) {
 451     GtsFace * f1 = i->data;
 452     if (GTS_IS_FACE (f1) &&
 453         f1 != f &&
 454         gts_face_has_parent_surface (f1, surface)) {
 455       g_return_val_if_fail (neighbor == NULL, NULL); /* non-manifold edge */
 456       neighbor = f1;
 457     }
 458     i = i->next;
 459   }
 460   if (neighbor == NULL || neighbor == first) /* end of fan */
 461     return NULL;
 462
 463   if (GTS_TRIANGLE (neighbor)->e1 == e) {
 464     next = GTS_TRIANGLE (neighbor)->e2;
 465     enext = GTS_TRIANGLE (neighbor)->e3;
 466   }
 467   else if (GTS_TRIANGLE (neighbor)->e2 == e) {
 468     next = GTS_TRIANGLE (neighbor)->e3;
 469     enext = GTS_TRIANGLE (neighbor)->e1;
 470   }
 471   else if (GTS_TRIANGLE (neighbor)->e3 == e) {
 472     next = GTS_TRIANGLE (neighbor)->e1;
 473     enext = GTS_TRIANGLE (neighbor)->e2;
 474   }
 475   else
 476     g_assert_not_reached ();
 477
 478   /* checking for correct orientation */
 479   g_return_val_if_fail (GTS_SEGMENT (enext)->v1 == v ||
 480                         GTS_SEGMENT (enext)->v2 == v, NULL);
 481
 482   return g_slist_prepend (edge_fan_list (v, surface, neighbor, enext, first),
 483                           next);
 484 }
 485
 486 /**
 487  * gts_vertex_fan_oriented:
 488  * @v: a #GtsVertex.
 489  * @surface: a #GtsSurface.
 490  *
 491  * Returns: a list of #GtsEdge describing in counterclockwise order the
 492  * boundary of the fan of summit @v, the faces of the fan belonging to
 493  * @surface.
 494  */
 495 GSList * gts_vertex_fan_oriented (GtsVertex * v, GtsSurface * surface)
 496 {
 497   GtsFace * f = NULL;
 498   guint d = 2;
 499   GSList * i;
 500   GtsVertex * v1, * v2, * v3;
 501   GtsEdge * e1, * e2, * e3;
 502
 503   g_return_val_if_fail (v != NULL, NULL);
 504   g_return_val_if_fail (surface != NULL, NULL);
 505
 506   i = v->segments;
 507   while (i) {
 508     GtsEdge * e = i->data;
 509     if (GTS_IS_EDGE (e)) {
 510       GSList * j = e->triangles;
 511       GtsFace * f1 = NULL;
 512       guint degree = 0;
 513       while (j) {
 514         if (GTS_IS_FACE (j->data) &&
 515             gts_face_has_parent_surface (j->data, surface)) {
 516           f1 = j->data;
 517           degree++;
 518         }
 519         j = j->next;
 520       }
 521       if (f1 != NULL) {
 522         g_return_val_if_fail (degree <= 2, NULL); /* non-manifold edge */
 523         if (degree == 1) {
 524           gts_triangle_vertices_edges (GTS_TRIANGLE (f1), NULL,
 525                                        &v1, &v2, &v3, &e1, &e2, &e3);
 526           if (v == v2) {
 527             e2 = e3;
 528             e3 = e1;
 529           }
 530           else if (v == v3) {
 531             e3 = e2;
 532             e2 = e1;
 533           }
 534           if (e3 != e) {
 535             d = 1;
 536             f = f1;
 537           }
 538         }
 539         else if (degree <= d)
 540           f = f1;
 541       }
 542     }
 543     i = i->next;
 544   }
 545
 546   if (f == NULL)
 547     return NULL;
 548
 549   gts_triangle_vertices_edges (GTS_TRIANGLE (f), NULL,
 550                                &v1, &v2, &v3, &e1, &e2, &e3);
 551   if (v == v2) {
 552     e2 = e3;
 553     e3 = e1;
 554   }
 555   else if (v == v3) {
 556     e3 = e2;
 557     e2 = e1;
 558   }
 559
 560   return g_slist_prepend (edge_fan_list (v, surface, f, e3, f), e2);
 561 }
 562
 563 #define edge_use_vertex(e, v) (GTS_SEGMENT(e)->v1 == v ||\
 564                                GTS_SEGMENT(e)->v2 == v)
 565
 566 static GtsEdge * replace_vertex (GtsTriangle * t,
 567                                  GtsEdge * e1,
 568                                  GtsVertex * v,
 569                                  GtsVertex * with)
 570 {
 571   GtsEdge * e = NULL;
 572
 573   if (t->e1 != e1 && edge_use_vertex (t->e1, v))
 574     e = t->e1;
 575   else if (t->e2 != e1 && edge_use_vertex (t->e2, v))
 576     e = t->e2;
 577   else if (t->e3 != e1 && edge_use_vertex (t->e3, v))
 578     e = t->e3;
 579   else
 580     return NULL;
 581
 582   if (with != v) {
 583     GtsSegment * s = GTS_SEGMENT (e);
 584     if (s->v1 == v) s->v1 = with;
 585     if (s->v2 == v) s->v2 = with;
 586     with->segments = g_slist_prepend (with->segments, s);
 587     v->segments = g_slist_remove (v->segments, s);
 588   }
 589
 590   return e;
 591 }
 592
 593 static void triangle_next (GtsEdge * e, GtsVertex * v, GtsVertex * with)
 594 {
 595   GSList * i;
 596
 597   if (e == NULL)
 598     return;
 599
 600   i = e->triangles;
 601   while (i) {
 602     GtsTriangle * t = i->data;
 603     if (GTS_OBJECT (t)->reserved) {
 604       GTS_OBJECT (t)->reserved = NULL;
 605       triangle_next (replace_vertex (t, e, v, with), v, with);
 606     }
 607     i = i->next;
 608   }
 609 }
 610
 611 /**
 612  * gts_vertex_is_contact:
 613  * @v: a #GtsVertex.
 614  * @sever: if %TRUE and if @v is a contact vertex between two or more
 615  * sets of connected triangles replaces it with as many vertices,
 616  * clones of @v.
 617  *
 618  * Returns: the number of sets of connected triangles sharing @v as a
 619  * contact vertex.
 620  */
 621 guint gts_vertex_is_contact (GtsVertex * v, gboolean sever)
 622 {
 623   GSList * triangles, * i;
 624   GtsVertex * with = v;
 625   guint ncomponent = 0;
 626
 627   g_return_val_if_fail (v != NULL, 0);
 628
 629   triangles = gts_vertex_triangles (v, NULL);
 630   i = triangles;
 631   while (i) {
 632     GTS_OBJECT (i->data)->reserved = i;
 633     i = i->next;
 634   }
 635
 636   i = triangles;
 637   while (i) {
 638     GtsTriangle * t = i->data;
 639     if (GTS_OBJECT (t)->reserved) {
 640       GtsEdge * e;
 641       if (ncomponent && sever)
 642         with = GTS_VERTEX (gts_object_clone (GTS_OBJECT (v)));
 643       GTS_OBJECT (t)->reserved = NULL;
 644       e = replace_vertex (t, NULL, v, with);
 645       triangle_next (e, v, with);
 646       triangle_next (replace_vertex (t, e, v, with), v, with);
 647       ncomponent++;
 648     }
 649     i = i->next;
 650   }
 651   g_slist_free (triangles);
 652
 653   return ncomponent;
 654 }
 655
 656 /* GtsVertexNormal: Object */
 657
 658 static void vertex_normal_attributes (GtsVertex * v,
 659                                       GtsObject * e,
 660                                       GtsObject * t)
 661 {
 662   g_return_if_fail (GTS_IS_EDGE (e));
 663   g_return_if_fail (GTS_IS_TRIANGLE (t));
 664
 665   if (GTS_IS_VERTEX_NORMAL (GTS_SEGMENT (e)->v1) &&
 666       GTS_IS_VERTEX_NORMAL (GTS_SEGMENT (e)->v2)) {
 667     GtsPoint * p1 = GTS_POINT (GTS_SEGMENT (e)->v1);
 668     GtsPoint * p2 = GTS_POINT (GTS_SEGMENT (e)->v2);
 669     GtsPoint * p = GTS_POINT (v);
 670     gdouble a, b, lambda;
 671     guint i;
 672
 673     a = p2->x - p1->x; b = p->x - p1->x;
 674     if (fabs (p2->y - p1->y) > fabs (a)) {
 675       a = p2->y - p1->y; b = p->y - p1->y;
 676     }
 677     if (fabs (p2->z - p1->z) > fabs (a)) {
 678       a = p2->z - p1->z; b = p->z - p1->z;
 679     }
 680     lambda = a != 0. ? b/a : 0.;
 681     for (i = 0; i < 3; i++)
 682       GTS_VERTEX_NORMAL (v)->n[i] =
 683         (1. - lambda)*GTS_VERTEX_NORMAL (GTS_SEGMENT (e)->v1)->n[i] +
 684         lambda*GTS_VERTEX_NORMAL (GTS_SEGMENT (e)->v2)->n[i];
 685   }
 686   else {
 687     GtsVertex * v1, * v2, * v3;
 688
 689     gts_triangle_vertices (GTS_TRIANGLE (t), &v1, &v2, &v3);
 690     if (GTS_IS_VERTEX_NORMAL (v1) &&
 691         GTS_IS_VERTEX_NORMAL (v2) &&
 692         GTS_IS_VERTEX_NORMAL (v3)) {
 693       GtsVector a1, a2, a3, det;
 694       guint i, j = 0;
 695       gdouble l1, l2;
 696
 697       gts_vector_init (a1, GTS_POINT (v1), GTS_POINT (v));
 698       gts_vector_init (a2, GTS_POINT (v1), GTS_POINT (v2));
 699       gts_vector_init (a3, GTS_POINT (v1), GTS_POINT (v3));
 700       gts_vector_cross (det, a2, a3);
 701       if (fabs (det[1]) > fabs (det[0])) j = 1;
 702       if (fabs (det[2]) > fabs (det[j])) j = 2;
 703       if (det[j] == 0.) {
 704         g_warning ("vertex_normal_attributes: det[%d] == 0.", j);
 705         return;
 706       }
 707       switch (j) {
 708       case 0:
 709         l1 = (a1[1]*a3[2] - a1[2]*a3[1])/det[0];
 710         l2 = (a1[2]*a2[1] - a1[1]*a2[2])/det[0];
 711         break;
 712       case 1:
 713         l1 = (a1[2]*a3[0] - a1[0]*a3[2])/det[1];
 714         l2 = (a1[0]*a2[2] - a1[2]*a2[0])/det[1];
 715         break;
 716       case 2:
 717         l1 = (a1[0]*a3[1] - a1[1]*a3[0])/det[2];
 718         l2 = (a1[1]*a2[0] - a1[0]*a2[1])/det[2];
 719         break;
 720       default:
 721         l1 = l2 = 0.;
 722       }
 723       for (i = 0; i < 3; i++)
 724         GTS_VERTEX_NORMAL (v)->n[i] =
 725           GTS_VERTEX_NORMAL (v1)->n[i]*(1. - l1 - l2) +
 726           GTS_VERTEX_NORMAL (v2)->n[i]*l1 +
 727           GTS_VERTEX_NORMAL (v3)->n[i]*l2;
 728     }
 729   }
 730 }
 731
 732 static void gts_vertex_normal_class_init (GtsVertexClass * klass)
 733 {
 734   klass->intersection_attributes = vertex_normal_attributes;
 735 }
 736
 737 GtsVertexClass * gts_vertex_normal_class (void)
 738 {
 739   static GtsVertexClass * klass = NULL;
 740
 741   if (klass == NULL) {
 742     GtsObjectClassInfo gts_vertex_normal_info = {
 743       "GtsVertexNormal",
 744       sizeof (GtsVertexNormal),
 745       sizeof (GtsVertexClass),
 746       (GtsObjectClassInitFunc) gts_vertex_normal_class_init,
 747       (GtsObjectInitFunc) NULL,
 748       (GtsArgSetFunc) NULL,
 749       (GtsArgGetFunc) NULL
 750     };
 751     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_vertex_class ()),
 752                                   &gts_vertex_normal_info);
 753   }
 754
 755   return klass;
 756 }
 757
 758 /* GtsColorVertex: Object */
 759
 760 GtsVertexClass * gts_color_vertex_class (void)
 761 {
 762   static GtsVertexClass * klass = NULL;
 763
 764   if (klass == NULL) {
 765     GtsObjectClassInfo gts_color_vertex_info = {
 766       "GtsColorVertex",
 767       sizeof (GtsColorVertex),
 768       sizeof (GtsVertexClass),
 769       (GtsObjectClassInitFunc) NULL,
 770       (GtsObjectInitFunc) NULL,
 771       (GtsArgSetFunc) NULL,
 772       (GtsArgGetFunc) NULL
 773     };
 774     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_vertex_class ()),
 775                                   &gts_color_vertex_info);
 776   }
 777
 778   return klass;
 779 }
 780