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;

int
remove_tri(qtptr,fptr,t_id)
   QUADTREE *qtptr;
   int *fptr;
   int t_id;
{
    int n;

   if(QT_IS_EMPTY(*qtptr))
     return(FALSE);
   /* remove id from set */
      else
      {
         if(!qtinset(*qtptr,t_id))
           return(FALSE);
         n = QT_SET_CNT(qtqueryset(*qtptr))-1;
         *qtptr = qtdelelem(*qtptr,t_id);
          if(n  == 0)
             (*fptr) |= QT_COMPRESS;
        if(!QT_FLAG_FILL_TRI(*fptr))
          (*fptr)++;
      }
    return(TRUE);
}

int
remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id)
QUADTREE *qtptr;
FVECT q0,q1,q2;
FVECT t0,t1,t2;
int n;
int *arg;
int t_id;
{
    int f = 0;
    /* NOTE compress */
    return(remove_tri(qtptr,&f,t_id));
}


smLocator_remove_tri(sm,t_id)
SM *sm;
int t_id;
{
  STREE *st;
  TRI *t;
  FVECT v0,v1,v2;

  st = SM_LOCATOR(sm);

  t = SM_NTH_TRI(sm,t_id);

  VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
  VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
  VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
  stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,t_id,NULL);
}

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,del_set)
SM *sm;
int id;
OBJECT *del_set;
{
    TRI *tri,*t_next;
    LIST *elist,*end;
    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;

    insertelem(del_set,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));
        insertelem(del_set,t_next_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);

      VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm));
      VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm));
      if(sedge_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);
}


int
smTriangulate_convex(sm,plist,add_ptr)
SM *sm;
LIST *plist,**add_ptr;
{
    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);
        *add_ptr = push_data(*add_ptr,t_id);

        /* 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);
    return(TRUE);
}
int
smTriangulate_elist(sm,plist,add_ptr)
SM *sm;
LIST *plist,**add_ptr;
{
    LIST *l,*el1;
    FVECT v0,v1,v2;
    int id0,id1,id2,e,id_next;
    char flipped;
    int done;

    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(FALSE);
      }
      /* 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
      */
      split_edge_list(id1,id_next,&l,&el1);
      /* Recurse and triangulate the two edge lists */
      done = smTriangulate_elist(sm,l,add_ptr);
      if(done)
        done = smTriangulate_elist(sm,el1,add_ptr);
      return(done);
    }
    done = smTriangulate_convex(sm,plist,add_ptr);
    return(done);
}

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

    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(): 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,add_list,del_set)
   SM *sm;
   LIST *add_list;
   OBJECT *del_set;
{
    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;

    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_in_cone(sm,v0,id_v0);
        smDir_in_cone(sm,v1,id_v1);
        smDir_in_cone(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_list,
                            del_set);
            
            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_list,del_set);
}

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

    add_list = NULL;
    /* Triangulate spherical polygon */
    smTriangulate(sm,elist,&add_list);


    /* Fix up new triangles to be Delaunay */
    smFix_edges(sm,add_list,del_set);

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