src/hd/sm_del.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 *  sm_del.c
 */
#include "standard.h"

#include "sm_list.h"
#include "sm_geom.h"
#include "sm.h"

static EDGE Edges[MAX_EDGES];
static int Ecnt=0;


smLocator_remove_tri(sm,t_id)
SM *sm;
int t_id;
{
  STREE *st;
  char found;
  TRI *t;
  FVECT p0,p1,p2;

  st = SM_LOCATOR(sm);

  t = SM_NTH_TRI(sm,t_id);

  smDir(sm,p0,T_NTH_V(t,0));
  smDir(sm,p1,T_NTH_V(t,1));
  smDir(sm,p2,T_NTH_V(t,2));

  found = stRemove_tri(st,t_id,p0,p1,p2);

  return(found);
}

smFree_tri(sm,id)
SM *sm;
int id;
{
  TRI *tri;

  tri = SM_NTH_TRI(sm,id);
  /* Add to the free_list */
  T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
  SM_FREE_TRIS(sm) = id;
  T_VALID_FLAG(tri) = -1;
}

/* Assumes mesh pointers have been cleaned up appropriately: just deletes from
   Point location and triangle data structure
*/
smDelete_tri(sm,t_id)
SM *sm;
int t_id;
{


  /* NOTE: Assumes that a new triangle adjacent to each vertex
     has been added- before the deletion: replacing
     the old tri- and therefore dont need to dereference any pointers
     to id because the vertices can no longer
     point to tri id as being the first triangle pointer
  */
  if(!SM_IS_NTH_T_BASE(sm,t_id))
  {
    SM_NUM_TRIS(sm)--;
    if(SM_IS_NTH_T_NEW(sm,t_id))
      smNew_tri_cnt--;
  }
  smClear_tri_flags(sm,t_id);

  smFree_tri(sm,t_id);

}


LIST
*smVertex_star_polygon(sm,id)
SM *sm;
int id;
{
    TRI *tri,*t_next;
    LIST *elist,*end,*tlist;
    int t_id,v_next,t_next_id;
    int e;

    elist = end =  NULL;
    /* Get the first triangle adjacent to vertex id */
    t_id = SM_NTH_VERT(sm,id);
    tri = SM_NTH_TRI(sm,t_id);

    
    if((e = eNew_edge()) == SM_INVALID)
    {
#ifdef DEBUG
        eputs("smVertex_star_polygon():Too many edges\n");
#endif
        return(NULL);
    }
    elist = add_data_to_circular_list(elist,&end,e);
    v_next = (T_WHICH_V(tri,id)+1)%3;
    SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next));
    SET_E_NTH_TRI(e,0,SM_INVALID);
    SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next));
    v_next = (T_WHICH_V(tri,id)+2)%3;
    SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next));

    
    t_next_id = t_id;
    t_next = tri;

    tlist = push_data(NULL,t_id);

    while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id)
    {   
        if((e = eNew_edge()) == SM_INVALID)
        {
#ifdef DEBUG
            eputs("smVertex_star_polygon():Too many edges\n");
#endif
            return(NULL);
        }
        elist = add_data_to_circular_list(elist,&end,e);
        t_next = SM_NTH_TRI(sm,t_next_id);
        v_next = (T_WHICH_V(t_next,id)+1)%3;
        SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next));
        SET_E_NTH_TRI(e,0,SM_INVALID);
        SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next));
        v_next = (T_WHICH_V(t_next,id)+2)%3;
        SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next));
        tlist = push_data(tlist,t_next_id);
    }
    while(tlist)
    {
        t_id = (int)pop_list(&tlist);
        /* first remove from point location structure */
        smLocator_remove_tri(sm,t_id);
        smDelete_tri(sm,t_id);
    }
    return(elist);
}

int
smEdge_intersect_polygon(sm,v0,v1,l)
SM *sm;
FVECT v0,v1;
LIST *l;
{
    FVECT e0,e1;
    int e,id_e0,id_e1;
    LIST *el,*eptr;
    
    /* Test the edges in l against v0v1 to see if v0v1 intersects
       any other edges
     */
    
    el = l;

    while(el)
    {
      e = (int)LIST_DATA(el);
      id_e0 = E_NTH_VERT(e,0);
      id_e1 = E_NTH_VERT(e,1);

      smDir(sm,e0,id_e0);
      smDir(sm,e1,id_e1);
      if(spherical_polygon_edge_intersect(v0,v1,e0,e1))
        return(TRUE);

      el = LIST_NEXT(el);
      if(el == l)
        break;
    }
    return(FALSE);
}

int
smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
   SM *sm;
   int id0,id1;
   FVECT v0,v1;
   LIST *l;
{
    int e,id;
    LIST *el;
    FVECT v;

    /* starting with the end of edge at head of l, search sequentially for
      vertex v such that v0v1v is a convex angle, and the edge v1v does
      not intersect any other edges
   */
    id = SM_INVALID;
    el = l;
    while(id != id0)
    {
        e = (int)LIST_DATA(el);
        id = E_NTH_VERT(e,1);

        smDir(sm,v,id); 

        if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l))
           return(id);
              
        el = LIST_NEXT(el);
        if(el == l)
           break;
    }
    return(SM_INVALID);
}

int
split_edge_list(id0,id_new,l,lnew)
int id0,id_new;
LIST **l,**lnew;
{
    LIST *list,*lptr,*end;
    int e,e1,e2,new_e;

    e2 = SM_INVALID;
    list = lptr = *l;

    if((new_e = eNew_edge())==SM_INVALID)
     {
#ifdef DEBUG
            eputs("split_edge_list():Too many edges\n");
#endif
         return(FALSE);
     }
    SET_E_NTH_VERT(new_e,0,id0);
    SET_E_NTH_VERT(new_e,1,id_new);
    SET_E_NTH_TRI(new_e,0,SM_INVALID);
    SET_E_NTH_TRI(new_e,1,SM_INVALID);
    
    while(e2 != id_new)
    {
        lptr = LIST_NEXT(lptr);
        e = (int)LIST_DATA(lptr);
        e2 = E_NTH_VERT(e,1);
        if(lptr == list)
        {
#ifdef DEBUG        
          eputs("split_edge_list():cant find vertex\n");
#endif
          *lnew = NULL;
          return(FALSE);
        }

    }
    end = lptr;
    lptr =  LIST_NEXT(lptr);
    list = add_data_to_circular_list(list,&end,-new_e);
    *lnew = list;

    /* now follow other cycle */

    list = lptr;
    e2 = SM_INVALID;
    while(e2 != id0)
    {
        lptr = LIST_NEXT(lptr);
        e = (int)LIST_DATA(lptr);
        e2 = E_NTH_VERT(e,1);
        if(lptr == list)
        {
#ifdef DEBUG        
          eputs("split_edge_list():cant find intial vertex\n");
#endif
          *l = NULL;
          return(FALSE);
        }

    }
    end = lptr;
    list = add_data_to_circular_list(list,&end,new_e);
    *l = list;
    return(TRUE);
}


LIST
*smTriangulate_convex(sm,plist)
SM *sm;
LIST *plist;
{
    TRI *tri;
    int t_id,e_id0,e_id1,e_id2;
    int v_id0,v_id1,v_id2;
    LIST *lptr;
    int cnt;

    lptr = plist;
    e_id0 = (int)LIST_DATA(lptr);
    v_id0 = E_NTH_VERT(e_id0,0);
    lptr = LIST_NEXT(lptr);
    while(LIST_NEXT(lptr) != plist)
    {
        e_id1 = (int)LIST_DATA(lptr);
        v_id1 = E_NTH_VERT(e_id1,0);
        v_id2 = E_NTH_VERT(e_id1,1);
        /* form a triangle for each triple of with v0 as base of star */
        t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri);
        smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2);
        /* add which pointer?*/

        lptr = LIST_NEXT(lptr);

        if(LIST_NEXT(lptr) != plist)
        {
            e_id2 = eNew_edge();
            SET_E_NTH_VERT(e_id2,0,v_id2);
            SET_E_NTH_VERT(e_id2,1,v_id0);
        }
        else
           e_id2 = (int)LIST_DATA(lptr);
         
        /* set appropriate tri for each edge*/ 
        SET_E_NTH_TRI(e_id0,0,t_id);
        SET_E_NTH_TRI(e_id1,0,t_id);
        SET_E_NTH_TRI(e_id2,0,t_id);

        e_id0 = -e_id2;
    }
    free_list(plist);
}

smTriangulate_elist(sm,plist)
SM *sm;
LIST *plist;
{
    LIST *l,*el1;
    FVECT v0,v1,v2;
    int id0,id1,id2,e,id_next;
    char flipped;
    int debug = TRUE;

    l = plist;
    
    while(l)
    {
        /* get v0,v1,v2 */
      e = (int)LIST_DATA(l);
      id0 = E_NTH_VERT(e,0);
      id1 = E_NTH_VERT(e,1);
      l = LIST_NEXT(l);
      e = (int)LIST_DATA(l);
      id2 = E_NTH_VERT(e,1);

      smDir(sm,v0,id0);
      smDir(sm,v1,id1);
      smDir(sm,v2,id2);
      /* determine if convex (left turn), or concave(right turn) angle */
      if(convex_angle(v0,v1,v2))
      {
        if(l == plist)
          break;
        else
          continue;
      }
      /* if concave: add edge and recurse on two sub polygons */
      id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l));
      if(id_next == SM_INVALID)
      {
#ifdef DEBUG
          eputs("smTriangulate_elist():Unable to find convex vertex\n");
#endif
          return;
      }
      /* add edge */
      el1 = NULL;
      /* Split edge list l into two lists: one from id1-id_next-id1,
         and the next from id2-id_next-id2
      */
      debug = split_edge_list(id1,id_next,&l,&el1);
      /* Recurse and triangulate the two edge lists */
      if(debug)
        debug = smTriangulate_elist(sm,l);
      if(debug)
        debug = smTriangulate_elist(sm,el1);

      return(debug);
    }
    smTriangulate_convex(sm,plist);
    return(TRUE);
}

int
smTriangulate_polygon(sm,plist)
SM *sm;
LIST *plist;
{
    int e,id_t0,id_t1,e0,e1;
    TRI *t0,*t1;
    int test;
    
    test = smTriangulate_elist(sm,plist,NULL);

    if(!test)
       return(test);
    FOR_ALL_EDGES(e)
    {
        id_t0 = E_NTH_TRI(e,0);
        id_t1 = E_NTH_TRI(e,1);
        if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
        {
#ifdef DEBUG
           eputs("smTriangulate_polygon(): Unassigned edge neighbor\n");
#endif
            continue;
        }
        t0 = SM_NTH_TRI(sm,id_t0);
        t1 = SM_NTH_TRI(sm,id_t1);
        
        e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
        T_NTH_NBR(t0,e0) = id_t1;

        e1 = T_WHICH_V(t1,E_NTH_VERT(e,1));
        T_NTH_NBR(t1,e1) = id_t0;
    }
    return(test);
}

eIn_tri(e,t)
int e;
TRI *t;
{

  if(T_NTH_V(t,0)==E_NTH_VERT(e,0)) 
    return(T_NTH_V(t,1)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
  else
    if(T_NTH_V(t,1)==E_NTH_VERT(e,0))
      return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
    else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
      return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1));
  return(FALSE);
}
smFix_edges(sm)
   SM *sm;
{
    int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next;
    TRI *t0,*t1,*nt0,*nt1;
    int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1;
    FVECT v0,v1,v2,p,np,v;
    LIST *add,*del;
    
    add = del = NULL;
    FOR_ALL_EDGES(e)
    {
        id_t0 = E_NTH_TRI(e,0);
        id_t1 = E_NTH_TRI(e,1);
        if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
        {
#ifdef DEBUG
            eputs("smFix_edges: Unassigned edge nbr\n");
#endif
            continue;
        }
        t0 = SM_NTH_TRI(sm,id_t0);
        t1 = SM_NTH_TRI(sm,id_t1);
        
        e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
        e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0));
        e0_next = (e0+2)%3;
        e1_next = (e1+2)%3;
        id_v0 = E_NTH_VERT(e,0);
        id_v1 = E_NTH_VERT(e,1);
        id_v2 = T_NTH_V(t0,e0_next);
        id_p = T_NTH_V(t1,e1_next);

        smDir(sm,v0,id_v0);
        smDir(sm,v1,id_v1);
        smDir(sm,v2,id_v2);
        
        VCOPY(p,SM_NTH_WV(sm,id_p));    
        VSUB(p,p,SM_VIEW_CENTER(sm));
        if(point_in_cone(p,v0,v1,v2))
        {
            smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del);
            
            nt0 = SM_NTH_TRI(sm,nid_t0);
            nt1 = SM_NTH_TRI(sm,nid_t1);
            FOR_ALL_EDGES_FROM(e,i)
            {
              if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1)
              {
                if(eIn_tri(i,nt0))
                  SET_E_NTH_TRI(i,0,nid_t0);
                else
                  SET_E_NTH_TRI(i,0,nid_t1);
              }

              if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1)
              {
                if(eIn_tri(i,nt0))
                  SET_E_NTH_TRI(i,1,nid_t0);
                else
                  SET_E_NTH_TRI(i,1,nid_t1);
              }
            }
            id_t0 = nid_t0;
            id_t1 = nid_t1;
            e_new = eNew_edge();
            SET_E_NTH_VERT(e_new,0,id_p);
            SET_E_NTH_VERT(e_new,1,id_v2);
            SET_E_NTH_TRI(e_new,0,id_t0);
            SET_E_NTH_TRI(e_new,1,id_t1);
        }
    }
    smUpdate_locator(sm,add,del);
}

int
smMesh_remove_vertex(sm,id)
   SM *sm;
   int id;
{
    int tri;
    LIST *elist;
    int cnt,debug;
    /* generate list of vertices that form the boundary of the
       star polygon formed by vertex id and all of its adjacent
       triangles
     */
    eClear_edges();
    elist = smVertex_star_polygon(sm,id);
    if(!elist)
       return(FALSE);

    /* Triangulate spherical polygon */
    debug = smTriangulate_polygon(sm,elist);


    /* Fix up new triangles to be Delaunay */
    if(debug)
       smFix_edges(sm);

    return(TRUE);
}
   
/* Remove point from samples, and from mesh. Delete any triangles
   adjacent to the point and re-triangulate the hole
   Return TRUE is point found , FALSE otherwise
*/
int
smDelete_point(sm,id)
SM *sm;
int id;
{

    /* Remove the corresponding vertex from the mesh */
    smMesh_remove_vertex(sm,id);
    /* Free the sample point */
    smDelete_sample(sm,id);
    return(TRUE);
}


Revision:	3.2
Committed:	Mon Aug 24 12:38:57 1998 UTC (25 years, 8 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.1:	+8 -5 lines
Log Message:	optimized triangle addition/deletion during edge swapping
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ SGI";
5			#endif
6
7			/*
8			* sm_del.c
9			*/
10			#include "standard.h"
11
12			#include "sm_list.h"
13			#include "sm_geom.h"
14			#include "sm.h"
15
16			static EDGE Edges[MAX_EDGES];
17			static int Ecnt=0;
18
19
20			smLocator_remove_tri(sm,t_id)
21			SM *sm;
22			int t_id;
23			{
24			STREE *st;
25			char found;
26			TRI *t;
27			FVECT p0,p1,p2;
28
29			st = SM_LOCATOR(sm);
30
31			t = SM_NTH_TRI(sm,t_id);
32
33			smDir(sm,p0,T_NTH_V(t,0));
34			smDir(sm,p1,T_NTH_V(t,1));
35			smDir(sm,p2,T_NTH_V(t,2));
36
37			found = stRemove_tri(st,t_id,p0,p1,p2);
38
39			return(found);
40			}
41
42			smFree_tri(sm,id)
43			SM *sm;
44			int id;
45			{
46			TRI *tri;
47
48			tri = SM_NTH_TRI(sm,id);
49			/* Add to the free_list */
50			T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
51			SM_FREE_TRIS(sm) = id;
52			T_VALID_FLAG(tri) = -1;
53			}
54
55			/* Assumes mesh pointers have been cleaned up appropriately: just deletes from
56			Point location and triangle data structure
57			*/
58			smDelete_tri(sm,t_id)
59			SM *sm;
60			int t_id;
61			{
62
63
64			/* NOTE: Assumes that a new triangle adjacent to each vertex
65			has been added- before the deletion: replacing
66			the old tri- and therefore dont need to dereference any pointers
67			to id because the vertices can no longer
68			point to tri id as being the first triangle pointer
69			*/
70			if(!SM_IS_NTH_T_BASE(sm,t_id))
71			{
72			SM_NUM_TRIS(sm)--;
73			if(SM_IS_NTH_T_NEW(sm,t_id))
74			smNew_tri_cnt--;
75			}
76			smClear_tri_flags(sm,t_id);
77
78			smFree_tri(sm,t_id);
79
80			}
81
82
83
84			LIST
85			*smVertex_star_polygon(sm,id)
86			SM *sm;
87			int id;
88			{
89			TRI tri,t_next;
90			LIST elist,end,*tlist;
91			int t_id,v_next,t_next_id;
92			int e;
93
94			elist = end = NULL;
95			/* Get the first triangle adjacent to vertex id */
96			t_id = SM_NTH_VERT(sm,id);
97			tri = SM_NTH_TRI(sm,t_id);
98
99
100			if((e = eNew_edge()) == SM_INVALID)
101			{
102			#ifdef DEBUG
103			eputs("smVertex_star_polygon():Too many edges\n");
104			#endif
105			return(NULL);
106			}
107			elist = add_data_to_circular_list(elist,&end,e);
108			v_next = (T_WHICH_V(tri,id)+1)%3;
109			SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next));
110			SET_E_NTH_TRI(e,0,SM_INVALID);
111			SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next));
112			v_next = (T_WHICH_V(tri,id)+2)%3;
113			SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next));
114
115
116			t_next_id = t_id;
117			t_next = tri;
118
119			tlist = push_data(NULL,t_id);
120
121			while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id)
122			{
123			if((e = eNew_edge()) == SM_INVALID)
124			{
125			#ifdef DEBUG
126			eputs("smVertex_star_polygon():Too many edges\n");
127			#endif
128			return(NULL);
129			}
130			elist = add_data_to_circular_list(elist,&end,e);
131			t_next = SM_NTH_TRI(sm,t_next_id);
132			v_next = (T_WHICH_V(t_next,id)+1)%3;
133			SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next));
134			SET_E_NTH_TRI(e,0,SM_INVALID);
135			SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next));
136			v_next = (T_WHICH_V(t_next,id)+2)%3;
137			SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next));
138			tlist = push_data(tlist,t_next_id);
139			}
140			while(tlist)
141			{
142			t_id = (int)pop_list(&tlist);
143	gwlarson	3.2	/* first remove from point location structure */
144			smLocator_remove_tri(sm,t_id);
145	gwlarson	3.1	smDelete_tri(sm,t_id);
146			}
147			return(elist);
148			}
149
150			int
151			smEdge_intersect_polygon(sm,v0,v1,l)
152			SM *sm;
153			FVECT v0,v1;
154			LIST *l;
155			{
156			FVECT e0,e1;
157			int e,id_e0,id_e1;
158			LIST el,eptr;
159
160			/* Test the edges in l against v0v1 to see if v0v1 intersects
161			any other edges
162			*/
163
164			el = l;
165
166			while(el)
167			{
168			e = (int)LIST_DATA(el);
169			id_e0 = E_NTH_VERT(e,0);
170			id_e1 = E_NTH_VERT(e,1);
171
172			smDir(sm,e0,id_e0);
173			smDir(sm,e1,id_e1);
174			if(spherical_polygon_edge_intersect(v0,v1,e0,e1))
175			return(TRUE);
176
177			el = LIST_NEXT(el);
178			if(el == l)
179			break;
180			}
181			return(FALSE);
182			}
183
184			int
185			smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
186			SM *sm;
187			int id0,id1;
188			FVECT v0,v1;
189			LIST *l;
190			{
191			int e,id;
192			LIST *el;
193			FVECT v;
194
195			/* starting with the end of edge at head of l, search sequentially for
196			vertex v such that v0v1v is a convex angle, and the edge v1v does
197			not intersect any other edges
198			*/
199			id = SM_INVALID;
200			el = l;
201			while(id != id0)
202			{
203			e = (int)LIST_DATA(el);
204			id = E_NTH_VERT(e,1);
205
206			smDir(sm,v,id);
207
208			if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l))
209			return(id);
210
211			el = LIST_NEXT(el);
212			if(el == l)
213			break;
214			}
215			return(SM_INVALID);
216			}
217
218			int
219			split_edge_list(id0,id_new,l,lnew)
220			int id0,id_new;
221			LIST l,lnew;
222			{
223			LIST list,lptr,*end;
224			int e,e1,e2,new_e;
225
226			e2 = SM_INVALID;
227			list = lptr = *l;
228
229			if((new_e = eNew_edge())==SM_INVALID)
230			{
231			#ifdef DEBUG
232			eputs("split_edge_list():Too many edges\n");
233			#endif
234			return(FALSE);
235			}
236			SET_E_NTH_VERT(new_e,0,id0);
237			SET_E_NTH_VERT(new_e,1,id_new);
238			SET_E_NTH_TRI(new_e,0,SM_INVALID);
239			SET_E_NTH_TRI(new_e,1,SM_INVALID);
240
241			while(e2 != id_new)
242			{
243			lptr = LIST_NEXT(lptr);
244			e = (int)LIST_DATA(lptr);
245			e2 = E_NTH_VERT(e,1);
246			if(lptr == list)
247			{
248			#ifdef DEBUG
249			eputs("split_edge_list():cant find vertex\n");
250			#endif
251			*lnew = NULL;
252			return(FALSE);
253			}
254
255			}
256			end = lptr;
257			lptr = LIST_NEXT(lptr);
258			list = add_data_to_circular_list(list,&end,-new_e);
259			*lnew = list;
260
261			/* now follow other cycle */
262
263			list = lptr;
264			e2 = SM_INVALID;
265			while(e2 != id0)
266			{
267			lptr = LIST_NEXT(lptr);
268			e = (int)LIST_DATA(lptr);
269			e2 = E_NTH_VERT(e,1);
270			if(lptr == list)
271			{
272			#ifdef DEBUG
273			eputs("split_edge_list():cant find intial vertex\n");
274			#endif
275			*l = NULL;
276			return(FALSE);
277			}
278
279			}
280			end = lptr;
281			list = add_data_to_circular_list(list,&end,new_e);
282			*l = list;
283			return(TRUE);
284			}
285
286
287
288			LIST
289			*smTriangulate_convex(sm,plist)
290			SM *sm;
291			LIST *plist;
292			{
293			TRI *tri;
294			int t_id,e_id0,e_id1,e_id2;
295			int v_id0,v_id1,v_id2;
296			LIST *lptr;
297			int cnt;
298
299			lptr = plist;
300			e_id0 = (int)LIST_DATA(lptr);
301			v_id0 = E_NTH_VERT(e_id0,0);
302			lptr = LIST_NEXT(lptr);
303			while(LIST_NEXT(lptr) != plist)
304			{
305			e_id1 = (int)LIST_DATA(lptr);
306			v_id1 = E_NTH_VERT(e_id1,0);
307			v_id2 = E_NTH_VERT(e_id1,1);
308			/* form a triangle for each triple of with v0 as base of star */
309			t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri);
310	gwlarson	3.2	smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2);
311	gwlarson	3.1	/* add which pointer?*/
312
313			lptr = LIST_NEXT(lptr);
314
315			if(LIST_NEXT(lptr) != plist)
316			{
317			e_id2 = eNew_edge();
318			SET_E_NTH_VERT(e_id2,0,v_id2);
319			SET_E_NTH_VERT(e_id2,1,v_id0);
320			}
321			else
322			e_id2 = (int)LIST_DATA(lptr);
323
324			/* set appropriate tri for each edge*/
325			SET_E_NTH_TRI(e_id0,0,t_id);
326			SET_E_NTH_TRI(e_id1,0,t_id);
327			SET_E_NTH_TRI(e_id2,0,t_id);
328
329			e_id0 = -e_id2;
330			}
331			free_list(plist);
332			}
333
334			smTriangulate_elist(sm,plist)
335			SM *sm;
336			LIST *plist;
337			{
338			LIST l,el1;
339			FVECT v0,v1,v2;
340			int id0,id1,id2,e,id_next;
341			char flipped;
342			int debug = TRUE;
343
344			l = plist;
345
346			while(l)
347			{
348			/* get v0,v1,v2 */
349			e = (int)LIST_DATA(l);
350			id0 = E_NTH_VERT(e,0);
351			id1 = E_NTH_VERT(e,1);
352			l = LIST_NEXT(l);
353			e = (int)LIST_DATA(l);
354			id2 = E_NTH_VERT(e,1);
355
356			smDir(sm,v0,id0);
357			smDir(sm,v1,id1);
358			smDir(sm,v2,id2);
359			/* determine if convex (left turn), or concave(right turn) angle */
360			if(convex_angle(v0,v1,v2))
361			{
362			if(l == plist)
363			break;
364			else
365			continue;
366			}
367			/* if concave: add edge and recurse on two sub polygons */
368			id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l));
369			if(id_next == SM_INVALID)
370			{
371			#ifdef DEBUG
372			eputs("smTriangulate_elist():Unable to find convex vertex\n");
373			#endif
374			return;
375			}
376			/* add edge */
377			el1 = NULL;
378			/* Split edge list l into two lists: one from id1-id_next-id1,
379			and the next from id2-id_next-id2
380			*/
381			debug = split_edge_list(id1,id_next,&l,&el1);
382			/* Recurse and triangulate the two edge lists */
383			if(debug)
384			debug = smTriangulate_elist(sm,l);
385			if(debug)
386			debug = smTriangulate_elist(sm,el1);
387
388			return(debug);
389			}
390			smTriangulate_convex(sm,plist);
391			return(TRUE);
392			}
393
394			int
395			smTriangulate_polygon(sm,plist)
396			SM *sm;
397			LIST *plist;
398			{
399			int e,id_t0,id_t1,e0,e1;
400			TRI t0,t1;
401			int test;
402
403			test = smTriangulate_elist(sm,plist,NULL);
404
405			if(!test)
406			return(test);
407			FOR_ALL_EDGES(e)
408			{
409			id_t0 = E_NTH_TRI(e,0);
410			id_t1 = E_NTH_TRI(e,1);
411			if((id_t0==SM_INVALID) \|\| (id_t1==SM_INVALID))
412			{
413			#ifdef DEBUG
414			eputs("smTriangulate_polygon(): Unassigned edge neighbor\n");
415			#endif
416			continue;
417			}
418			t0 = SM_NTH_TRI(sm,id_t0);
419			t1 = SM_NTH_TRI(sm,id_t1);
420
421			e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
422			T_NTH_NBR(t0,e0) = id_t1;
423
424			e1 = T_WHICH_V(t1,E_NTH_VERT(e,1));
425			T_NTH_NBR(t1,e1) = id_t0;
426			}
427			return(test);
428			}
429
430			eIn_tri(e,t)
431			int e;
432			TRI *t;
433			{
434
435			if(T_NTH_V(t,0)==E_NTH_VERT(e,0))
436			return(T_NTH_V(t,1)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,2)==E_NTH_VERT(e,1));
437			else
438			if(T_NTH_V(t,1)==E_NTH_VERT(e,0))
439			return(T_NTH_V(t,0)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,2)==E_NTH_VERT(e,1));
440			else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
441			return(T_NTH_V(t,0)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,1)==E_NTH_VERT(e,1));
442			return(FALSE);
443			}
444			smFix_edges(sm)
445			SM *sm;
446			{
447			int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next;
448			TRI t0,t1,nt0,nt1;
449			int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1;
450			FVECT v0,v1,v2,p,np,v;
451	gwlarson	3.2	LIST add,del;
452
453			add = del = NULL;
454	gwlarson	3.1	FOR_ALL_EDGES(e)
455			{
456			id_t0 = E_NTH_TRI(e,0);
457			id_t1 = E_NTH_TRI(e,1);
458			if((id_t0==SM_INVALID) \|\| (id_t1==SM_INVALID))
459			{
460			#ifdef DEBUG
461			eputs("smFix_edges: Unassigned edge nbr\n");
462			#endif
463			continue;
464			}
465			t0 = SM_NTH_TRI(sm,id_t0);
466			t1 = SM_NTH_TRI(sm,id_t1);
467
468			e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
469			e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0));
470			e0_next = (e0+2)%3;
471			e1_next = (e1+2)%3;
472			id_v0 = E_NTH_VERT(e,0);
473			id_v1 = E_NTH_VERT(e,1);
474			id_v2 = T_NTH_V(t0,e0_next);
475			id_p = T_NTH_V(t1,e1_next);
476
477			smDir(sm,v0,id_v0);
478			smDir(sm,v1,id_v1);
479			smDir(sm,v2,id_v2);
480
481			VCOPY(p,SM_NTH_WV(sm,id_p));
482			VSUB(p,p,SM_VIEW_CENTER(sm));
483			if(point_in_cone(p,v0,v1,v2))
484			{
485	gwlarson	3.2	smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del);
486	gwlarson	3.1
487			nt0 = SM_NTH_TRI(sm,nid_t0);
488			nt1 = SM_NTH_TRI(sm,nid_t1);
489			FOR_ALL_EDGES_FROM(e,i)
490			{
491			if(E_NTH_TRI(i,0)==id_t0 \|\| E_NTH_TRI(i,0)==id_t1)
492			{
493			if(eIn_tri(i,nt0))
494			SET_E_NTH_TRI(i,0,nid_t0);
495			else
496			SET_E_NTH_TRI(i,0,nid_t1);
497			}
498
499			if(E_NTH_TRI(i,1)==id_t0 \|\| E_NTH_TRI(i,1)==id_t1)
500			{
501			if(eIn_tri(i,nt0))
502			SET_E_NTH_TRI(i,1,nid_t0);
503			else
504			SET_E_NTH_TRI(i,1,nid_t1);
505			}
506			}
507			id_t0 = nid_t0;
508			id_t1 = nid_t1;
509			e_new = eNew_edge();
510			SET_E_NTH_VERT(e_new,0,id_p);
511			SET_E_NTH_VERT(e_new,1,id_v2);
512			SET_E_NTH_TRI(e_new,0,id_t0);
513			SET_E_NTH_TRI(e_new,1,id_t1);
514			}
515			}
516	gwlarson	3.2	smUpdate_locator(sm,add,del);
517	gwlarson	3.1	}
518
519			int
520			smMesh_remove_vertex(sm,id)
521			SM *sm;
522			int id;
523			{
524			int tri;
525			LIST *elist;
526			int cnt,debug;
527			/* generate list of vertices that form the boundary of the
528			star polygon formed by vertex id and all of its adjacent
529			triangles
530			*/
531			eClear_edges();
532			elist = smVertex_star_polygon(sm,id);
533			if(!elist)
534			return(FALSE);
535
536			/* Triangulate spherical polygon */
537			debug = smTriangulate_polygon(sm,elist);
538
539
540			/* Fix up new triangles to be Delaunay */
541			if(debug)
542			smFix_edges(sm);
543
544			return(TRUE);
545			}
546
547			/* Remove point from samples, and from mesh. Delete any triangles
548			adjacent to the point and re-triangulate the hole
549			Return TRUE is point found , FALSE otherwise
550			*/
551			int
552			smDelete_point(sm,id)
553			SM *sm;
554			int id;
555			{
556
557			/* Remove the corresponding vertex from the mesh */
558			smMesh_remove_vertex(sm,id);
559			/* Free the sample point */
560			smDelete_sample(sm,id);
561			return(TRUE);
562			}
563
564
565
566
567
568
569
570
571
572
573
574
575
576