Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

FaceSurface.cpp

Go to the documentation of this file.
00001 
00002 /*
00003     TEDDY - General graphics application library
00004     Copyright (C) 1999-2002  Timo Suoranta
00005     tksuoran@cc.helsinki.fi
00006 
00007         Adapted from
00008 
00009         3DC - http://www.on-the-web.ch/3dc/
00010         Copyright (C) 2000  Martin Herren
00011         sputnik@on-the-web.ch
00012 
00013     This library is free software; you can redistribute it and/or
00014     modify it under the terms of the GNU Lesser General Public
00015     License as published by the Free Software Foundation; either
00016     version 2.1 of the License, or (at your option) any later version.
00017 
00018     This library is distributed in the hope that it will be useful,
00019     but WITHOUT ANY WARRANTY; without even the implied warranty of
00020     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00021     Lesser General Public License for more details.
00022 
00023     You should have received a copy of the GNU Lesser General Public
00024     License along with this library; if not, write to the Free Software
00025     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00026 
00027     $Id: FaceSurface.cpp,v 1.1 2002/02/16 12:41:39 tksuoran Exp $
00028 */
00029 
00030 
00031 #if 0
00032 #include "gts.h"
00033 #include "Teddy/Models/Face.h"
00034 #include "Teddy/ColDet/ColDet.h"
00035 #include <cassert>
00036 
00037 
00038 namespace Teddy  {
00039 namespace Models {
00040 
00041 
00042 void util_prepend( gpointer data, GSList **lst ){
00043     *lst = g_slist_prepend( *lst, data );
00044 }
00045 
00046 
00047 void util_prepend_glist( gpointer data, GList **lst ){
00048     *lst = g_list_prepend( *lst, data);
00049 }
00050 
00051 
00052 GList *util_gslist2glist( GSList *gslist ){
00053     GList *glist = NULL;
00054 
00055     while( gslist ){
00056         glist  = g_list_append( glist, gslist->data );
00057         gslist = gslist->next;
00058     }
00059 
00060     return glist;
00061 }
00062 
00063 
00064 GSList *util_glist2gslist( GList *glist ){
00065     GSList *gslist = NULL;
00066     
00067     while( glist ){
00068         gslist = g_slist_append( gslist, glist->data );
00069         glist  = glist->next;
00070     }
00071     
00072     return gslist;
00073 }
00074 
00075 
00077 GSList *util_edges_get_vertices( GSList *edges ){
00078     GtsEdge *e        = NULL;
00079     GSList  *p        = edges;
00080     GList   *lst      = NULL;  // dummy list needed by gts_vertices_merge()
00081     GSList  *vertices = NULL;
00082     
00083     while( p ){
00084         e = (GtsEdge *)p->data;
00085         vertices = g_slist_append( vertices, e->segment.v1 );
00086         vertices = g_slist_append( vertices, e->segment.v2 );
00087         p = p->next;
00088     }
00089     
00090     printf( "gtsExt_edges_get_vertices: vertices: %i", g_slist_length(vertices) );
00091     lst = util_gslist2glist( vertices );
00092     g_slist_free( vertices );
00093     vertices = NULL;
00094     lst      = gts_vertices_merge( lst, 0 );
00095     vertices = util_glist2gslist ( lst );
00096     g_list_free( lst );
00097     printf( " -> %i\n", g_slist_length(vertices) );
00098     
00099     return vertices;
00100 }
00101 
00102 
00103 bool aligned( GtsVertex *v1, GtsVertex *v2, GtsVertex *v3 ){
00104     double x1;
00105     double x2;
00106     double y1;
00107     double y2;
00108     double z1;
00109     double z2;
00110     double x;
00111     double y;
00112     double z;
00113 
00114     x1 = (v2->p.x - v1->p.x);
00115     y1 = (v2->p.y - v1->p.y);
00116     z1 = (v2->p.z - v1->p.z);
00117     x2 = (v3->p.x - v1->p.x);
00118     y2 = (v3->p.y - v1->p.y);
00119     z2 = (v3->p.z - v1->p.z);
00120     x  = y1 * z2 - z1 * y2;
00121     y  = z1 * x2 - x1 * z2;
00122     z  = x1 * y2 - y1 * x2;
00123 
00124     return (x == 0) && (y == 0) && (z == 0) ? true : false;
00125 }
00126 
00127 
00129 GtsMatrix *get_matrix( GSList *v ){
00130     GtsVertex   *v1;
00131     GtsVertex   *v2;
00132     GtsVertex   *v3;
00133     GtsEdge     *e1;
00134     GtsEdge     *e2;
00135     GtsEdge     *e3;
00136     GtsTriangle *t;
00137     GtsMatrix   *m;
00138   
00139     if( !v || (g_slist_length(v) < 3) ){
00140         return NULL;
00141     }
00142 
00143     //  Getting the first 3 vertices
00144     v1 = (GtsVertex*)v->data;  //  Getting the first vertex
00145     v  = v->next;
00146     v2 = (GtsVertex*)v->data;  //  Getting the second vertex
00147     v  = v->next;
00148     
00149     //  Letting vertices point to the first
00150     //  vertex which is not colinear with v2 and v2
00151     while( v && aligned(v1, v2, (GtsVertex *)v->data) ){
00152         v = v->next;
00153     }
00154     if( !v ){
00155         return NULL;
00156     }
00157 
00158     //  Now we found our 3rd vertex
00159     v3 = (GtsVertex*)v->data; 
00160     
00161     //  Building the 3 edges
00162     e1 = gts_edge_new( gts_edge_class(), v1, v2 );
00163     e2 = gts_edge_new( gts_edge_class(), v2, v3 );
00164     e3 = gts_edge_new( gts_edge_class(), v3, v1 );
00165     
00166     //  Building the reference triangle and the matrix
00167     t = gts_triangle_new( gts_triangle_class(), e1, e2, e3 );
00168     m = gts_matrix_projection( t );
00169     
00170     //  Destroying the reference triangle
00171     gts_allow_floating_vertices = TRUE;
00172     gts_object_destroy( (GtsObject *) t );
00173     gts_allow_floating_vertices = FALSE;
00174     
00175     //  and good-bye
00176     return m;
00177 }
00178 
00179 
00184 GSList *faces_in_vertices( GtsSurface *s, GSList *v ){
00185     GSList *t = NULL;  //  GSList with all the triangles of the surface s
00186     GSList *p = NULL;  //  Pointer used to parse t
00187     GSList *f = NULL;  //  List of faces to be returned
00188 
00189     gts_surface_foreach_face( s, (GtsFunc) util_prepend, &t );
00190     p = t;
00191 
00192     while( p ){
00193         GtsVertex *v1=NULL, *v2=NULL, *v3=NULL;
00194         
00195         gts_triangle_vertices( (GtsTriangle*)p->data, &v1, &v2, &v3 );
00196         if( g_slist_find(v, v1) && g_slist_find(v, v2) && g_slist_find(v, v3) ){
00197             f = g_slist_append( f, p->data );
00198         }
00199         p = p->next;
00200     }
00201 
00202     g_slist_free( t );
00203     return f;
00204 }
00205 
00206 
00215 GtsSurface *triangulate_polygon( GSList *polygons ){
00216     GSList      *p = NULL;   //  a pointer to a polygon (GSList of vertices), used in loops
00217     GSList      *v = NULL;   //  a pointer to a vertex
00218     GList       *g = NULL;   //  a pointer to a GList, needed for gts_XXXX_merge
00219     GtsTriangle *t = NULL;   //  a triangle, needed to build the enclosing triangle
00220     GtsVertex   *v1;         //  the vertices of the enclosing triangle,
00221     GtsVertex   *v2;         //  needed for its destruction
00222     GtsVertex   *v3;
00223 
00224     //  The returned triangulated surface
00225     GtsSurface *s = gts_surface_new(
00226         gts_surface_class(),  
00227         gts_face_class(),
00228         gts_edge_class(),
00229         gts_vertex_class()
00230     );
00231 
00232     //  The transformation matrix and its inverse
00233     GtsMatrix *m   = NULL;  
00234     GtsMatrix *m_i = NULL;
00235 
00236     if( polygons==NULL ){
00237         return NULL;
00238     }
00239 
00240     //  v points to the first vertex list in polygons, which is the outer polygon
00241     v = (GSList*)polygons->data;
00242 
00243     if( !v || (g_slist_length(v) < 3) ){
00244         return NULL;
00245     }
00246 
00247     m = get_matrix( v );
00248     if( m==NULL ){
00249         return NULL;
00250     }
00251     m_i = gts_matrix_inverse( m );
00252 
00253     //  Rotates all vertices in the xy-plane
00254     p = polygons;
00255     while( p ){
00256         v = (GSList*)p->data;
00257         while( v ){
00258             gts_point_transform( (GtsPoint*)v->data, m_i );
00259             v = v->next;
00260         }
00261         p = p->next;
00262     }
00263 
00264     //  Creating the enclosing triangle of the outer boundary
00265     //  and adding it as first face to the surface s
00266     v = (GSList*)polygons->data;
00267     t = gts_triangle_enclosing( gts_triangle_class(), v, 100.0 );
00268     gts_surface_add_face(
00269         s,
00270         gts_face_new(
00271             gts_face_class(),
00272             t->e1,
00273             t->e2,
00274             t->e3
00275         )
00276     );
00277 
00278     //  Adding all vertices to the surface s
00279     p = polygons;
00280     while( p ){
00281         v = (GSList*)p->data;
00282         while( v ){
00283             assert(
00284                 gts_delaunay_add_vertex(
00285                     s,
00286                     (GtsVertex*)v->data,
00287                     NULL
00288                 ) == 0
00289             );
00290             v = v->next;
00291         }
00292         p = p->next;
00293     }
00294 
00295     /*   gts_surface_foreach_vertex(s, (GtsFunc) util_prepend_glist, &g); */
00296     /*   g = gts_vertices_merge(g, 0); */
00297     /*   g_list_free(g); */
00298     
00299     //  Now t can be destroyed
00300     gts_triangle_vertices( t, &v1, &v2, &v3 );
00301     gts_allow_floating_vertices = TRUE;
00302     gts_object_destroy( (GtsObject*)v1 );
00303     gts_object_destroy( (GtsObject*)v2 );
00304     gts_object_destroy( (GtsObject*)v3 );
00305     gts_allow_floating_vertices = FALSE;
00306     
00307     //  Adding the segments between consecutive vertices as constraints
00308     //  to the surface s
00309     p = polygons;
00310     while( p ){
00311         v = (GSList*)p->data;
00312         while( v ){
00313 
00314             //  If this isn't the last vertex, adds the edge to the next vertex
00315             if( v->next ){
00316                 //  No test is made if the vertex was added succesfully
00317                 gts_delaunay_add_constraint(
00318                     s,
00319                     (GtsConstraint *)gts_edge_new(
00320                         (GtsEdgeClass *)gts_constraint_class(),
00321                         (GtsVertex*)v->data,
00322                         (GtsVertex*)v->next->data
00323                     )
00324                 );
00325 
00326             //  Here we got the last vertex, adds the edge to the first vertex
00327             }else{  
00328                 //  No test is made if the constraint was added succesfully
00329                 gts_delaunay_add_constraint(
00330                     s,
00331                     (GtsConstraint *)gts_edge_new(
00332                         (GtsEdgeClass *)gts_constraint_class(),
00333                         (GtsVertex*)v->data,
00334                         (GtsVertex*)( ((GSList *)p->data)->data )
00335                     )
00336                 );
00337             }
00338             v = v->next;
00339         }
00340         p = p->next;
00341     }
00342 
00343     //  Cleaning up the surface... needed by gts_delaunay_remove_hull
00344     g = NULL;
00345     gts_surface_foreach_edge( s, (GtsFunc)util_prepend_glist, &g );
00346     g = gts_edges_merge( g );
00347     g_list_free( g );
00348 
00349     //  Remove the hull
00350     gts_delaunay_remove_hull( s );
00351 
00352 #   if 0
00353     //  Removing the faces in the holes
00354     //  p points to the first vertex-list representing a hole
00355     p = polygons->next;
00356     while( p ){
00357         //  Here v is the face-list of the faces needing to be removed
00358         v = faces_in_vertices( s, (GSList*)p->data );
00359         g_slist_foreach( v, (GFunc)gts_object_destroy, NULL );
00360         p = p->next;
00361     }
00362 #   endif
00363 
00364     //  Rotates all points back
00365     p = polygons;
00366     while( p ){
00367         v = (GSList*)p->data;
00368         while( v ){
00369             gts_point_transform( (GtsPoint*)v->data, m );
00370             v = v->next;
00371         }
00372         p = p->next;
00373     }
00374 
00375     return s;
00376 }
00377 
00378 
00383 /*virtual*/ GtsSurface *Face::makeSurface(){
00384 
00385     //  1: Transform vertices so that they lie on x,y,0 plane. Then 
00386     //  2: Use Gts Delaunay triangulation adding all face vertices
00387     //  3: Transfrom vertices back to original orientation
00388     
00389     return NULL;
00390 }
00391 
00392 
00393 };  //  namespace Models
00394 };  //  namespace Teddy
00395 
00396 
00397 #endif
00398 
00399