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_flag.h"
#include "sm_list.h"
#include "sm_geom.h"
#include "sm_qtree.h"
#include "sm_stree.h"
#include "sm.h"

static int Max_edges=200;
static EDGE *Edges=NULL;
static int Ecnt=0;

#define remove_tri_compress remove_tri
remove_tri(qtptr,fptr,tptr)
   QUADTREE *qtptr;
   int *fptr;
   int *tptr;
{
    int n;

    if(QT_IS_EMPTY(*qtptr))
      return;
    if(QT_LEAF_IS_FLAG(*qtptr))
      return;

    n = QT_SET_CNT(qtqueryset(*qtptr))-1;
    *qtptr = qtdelelem(*qtptr,*tptr);
    if(n  == 0)
      (*fptr) |= QT_COMPRESS;
    if(!QT_FLAG_FILL_TRI(*fptr))
      (*fptr)++;
}


smLocator_remove_tri(sm,t_id,v0_id,v1_id,v2_id)
SM *sm;
int t_id;
int v0_id,v1_id,v2_id;
{
  STREE *st;
  FVECT v0,v1,v2;
  
  st = SM_LOCATOR(sm);

  VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
  VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
  VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));

  qtClearAllFlags();
  
  stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,&t_id);

}

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_SAMPLE_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);
}


int
eNew_edge()
{
  if(!Edges)
    if(!(Edges = (EDGE *)realloc(NULL,(Max_edges+1)*sizeof(EDGE))))
      goto memerr;

  if(Ecnt >= Max_edges)
    {
      if(Max_edges > 10000)
        error(CONSISTENCY,"Too many edges in vertex loop\n");
      Max_edges += 100;
      if(!(Edges = (EDGE *)realloc(Edges,(Max_edges+1)*sizeof(EDGE))))
        goto memerr;
    }
  return(++Ecnt);

memerr:
  error(SYSTEM,"eNew_edge(): Unable to allocate memory");
}

LIST 
*smVertex_star_polygon(sm,id,delptr)
SM *sm;
int id;
QUADTREE *delptr;
{
    TRI *tri,*t_next;
    LIST *elist,*end;
    int t_id,v_next,t_next_id;
    int e;
    OBJECT del_set[2];

    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()) == INVALID)
      return(NULL);

    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,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));
    elist = add_data_to_circular_list(elist,&end,e);

    t_next_id = t_id;
    t_next = tri;

    del_set[0] =1; del_set[1] = t_id;
    *delptr = qtnewleaf(del_set);

    while((t_next_id = T_NTH_NBR(t_next,v_next)) != t_id)
    {   
      if((e = eNew_edge()) == INVALID)
        return(NULL);

      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,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));
      elist = add_data_to_circular_list(elist,&end,e);


      if(qtinset(*delptr,t_next_id))
        {
#ifdef DEBUG
          eputs("smVertex_star_polygon(): id already in set\n");
#endif    
          free_list(elist);
          return(NULL);
        }
      else
        qtaddelem(*delptr,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 = 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(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 = INVALID;
    list = lptr = *l;

    if((new_e = eNew_edge())==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,INVALID);
    SET_E_NTH_TRI(new_e,1,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 = 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;
{
    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);
        *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 == 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_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
SM *sm;
int id0,id1,id2,e0,e1,*e2ptr;
{
  int t_id;
  int e2;

  t_id = smAdd_tri(sm,id0,id1,id2);
  if(*e2ptr == 0)
  {
    e2 = eNew_edge();
    SET_E_NTH_VERT(e2,0,id2);
    SET_E_NTH_VERT(e2,1,id0);
  }
  else
    e2 = *e2ptr;
  /* set appropriate tri for each edge*/ 
  SET_E_NTH_TRI(e0,0,t_id);
  SET_E_NTH_TRI(e1,0,t_id);
  SET_E_NTH_TRI(e2,0,t_id);

  *e2ptr = e2;
  return(t_id);
}
int
smTriangulate_elist_new(sm,id,plist,add_ptr)
SM *sm;
int id;
LIST *plist,**add_ptr;
{
    LIST *l,*prev,*t;
    FVECT v0,v1,v2,n,p;
    int is_tri,loop,t_id,id0,id1,id2,e2,eprev,enext;
    double dp;

    smDir(sm,p,id);
    enext=0;
    is_tri= loop = FALSE;
    l = prev = plist;
    /* get v0,v1,v2 */
    eprev = (int)LIST_DATA(l);
    id0 = E_NTH_VERT(eprev,0);
    id1 = E_NTH_VERT(eprev,1);
    smDir(sm,v0,id0);
    smDir(sm,v1,id1);   
    while(l)
    {
      l = LIST_NEXT(l);
      e2 = (int)LIST_DATA(l);
      id2 = E_NTH_VERT(e2,1);
      /* Check if have a triangle */
      if(LIST_NEXT(LIST_NEXT(l)) == prev)
      {
        is_tri = TRUE;
        break;
      }
      if(LIST_NEXT(l) == plist)
      {
        if(!loop)
          loop = 1;
        else
          loop++;
        if(loop > 3)
          break;
      }
      smDir(sm,v2,id2);
      /* determine if convex (left turn), or concave(right turn) angle */
      if(!convex_angle(v0,v1,v2))
      {
        VCOPY(v0,v1);
        VCOPY(v1,v2);
        id0 = id1;
        id1 = id2;
        prev = l;
        eprev = e2;
        continue;
      }
      VCROSS(n,v0,v2);
      dp = DOT(n,p);
      if(loop <=1 && (!ZERO(dp) && dp  < 0.0))
      {
        VCOPY(v0,v1);
        VCOPY(v1,v2);
        id0 = id1;
        id1 = id2;
        eprev = e2;
        prev = l;
        continue;
      }
      loop = FALSE;

      enext = 0;
      t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext);
      *add_ptr = push_data(*add_ptr,t_id);

      LIST_NEXT(prev) = LIST_NEXT(l);
      LIST_DATA(prev) = eprev = -enext;
      LIST_NEXT(l)=NULL;
      if(l== plist)
        plist = prev;
      free_list(l);
      l = prev;
      VCOPY(v1,v2);
      id1 = id2;
    }
    if(is_tri)
    {
      l = LIST_NEXT(l);
      enext = (int)LIST_DATA(l);
      t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext);
      *add_ptr = push_data(*add_ptr,t_id);
      free_list(l);
     }
    else
      {
#ifdef DEBUG       
        eputs("smTriangulate_elist()Unable to triangulate\n");
#endif
        return(FALSE);
      }
    return(TRUE);
}

int
smTriangulate(sm,p_id,plist,add_ptr)
SM *sm;
int p_id;
LIST *plist,**add_ptr;
{
    int e,id_t0,id_t1,e0,e1;
    int test;

    test = smTriangulate_elist_new(sm,p_id,plist,add_ptr);
#if 0
    test = smTriangulate_elist(sm,plist,add_ptr);
#endif

    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==INVALID) || (id_t1==INVALID))
        {
#ifdef DEBUG
           eputs("smTriangulate(): Unassigned edge neighbor\n");
#endif
            continue;
        }
        
        e0 = T_WHICH_V(SM_NTH_TRI(sm,id_t0),E_NTH_VERT(e,0));
        T_NTH_NBR(SM_NTH_TRI(sm,id_t0),e0) = id_t1;

        e1 = T_WHICH_V(SM_NTH_TRI(sm,id_t1),E_NTH_VERT(e,1));
        T_NTH_NBR(SM_NTH_TRI(sm,id_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,delptr)
   SM *sm;
   LIST *add_list;
   QUADTREE *delptr;

{
    int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next;
    int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid;
    FVECT v0,v1,v2,p,np,v;

    FOR_ALL_EDGES(e)
    {
        t0_id = E_NTH_TRI(e,0);
        t1_id = E_NTH_TRI(e,1);
        if((t0_id==INVALID) || (t1_id==INVALID))
        {
#ifdef DEBUG
            eputs("smFix_edges: Unassigned edge nbr\n");
#endif
            continue;
        }
        e0 = T_WHICH_V(SM_NTH_TRI(sm,t0_id),E_NTH_VERT(e,0));
        e1 = T_WHICH_V(SM_NTH_TRI(sm,t1_id),E_NTH_VERT(-e,0));
        e0_next = (e0+2)%3;
        e1_next = (e1+2)%3;
        v0_id = E_NTH_VERT(e,0);
        v1_id = E_NTH_VERT(e,1);
        v2_id = T_NTH_V(SM_NTH_TRI(sm,t0_id),e0_next);
        p_id = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1_next);

        smDir_in_cone(sm,v0,v0_id);
        smDir_in_cone(sm,v1,v1_id);
        smDir_in_cone(sm,v2,v2_id);
        
        VCOPY(p,SM_NTH_WV(sm,p_id));    
        VSUB(p,p,SM_VIEW_CENTER(sm));
        if(point_in_cone(p,v0,v1,v2))
        {
           smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list,
                            delptr);
            
            FOR_ALL_EDGES_FROM(e,i)
            {
              if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id)
              {
                if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
                  SET_E_NTH_TRI(i,0,t0_nid);
                else
                  SET_E_NTH_TRI(i,0,t1_nid);
              }

              if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id)
              {
                if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
                  SET_E_NTH_TRI(i,1,t0_nid);
                else
                  SET_E_NTH_TRI(i,1,t1_nid);
              }
            }
            t0_id = t0_nid;
            t1_id = t1_nid;
            e_new = eNew_edge();
            SET_E_NTH_VERT(e_new,0,p_id);
            SET_E_NTH_VERT(e_new,1,v2_id);
            SET_E_NTH_TRI(e_new,0,t0_id);
            SET_E_NTH_TRI(e_new,1,t1_id);
        }
    }
    smUpdate_locator(sm,add_list,qtqueryset(*delptr));
}

int
smMesh_remove_vertex(sm,id)
   SM *sm;
   int id;
{
    int t_id;
    LIST *elist,*add_list;
    int cnt,debug;
    QUADTREE delnode;
    /* 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,&delnode);

    if(!elist)
    {
#ifdef DEBUG
      eputs("smMesh_remove_vertex(): Unable to remove vertex");
#endif
      qtfreeleaf(delnode);
      return(FALSE);
    }
    add_list = NULL;
    /* Triangulate spherical polygon */
    if(!smTriangulate(sm,id,elist,&add_list))
    {
      while(add_list)
      {
        t_id = pop_list(&add_list);
        smDelete_tri(sm,t_id);
      }
      qtfreeleaf(delnode);
      return(FALSE);
    }
    /* Fix up new triangles to be Delaunay */
    smFix_edges(sm,add_list,&delnode);

    qtfreeleaf(delnode);
    return(TRUE);
}
   

Revision:	3.6
Committed:	Tue Oct 6 18:16:53 1998 UTC (25 years, 6 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.5:	+286 -159 lines
Log Message:	new triangulate routine added smTestSample to check for occlusion added frustum culling before rebuild changed base quadtree to use octahedron and created new point locate added "sample active" flags and implemented LRU replacement started handling case of too many triangles set sizes are now unbounded changed all quadtree pointers to quadtrees
#	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	gwlarson	3.6	#include "sm_flag.h"
12	gwlarson	3.1	#include "sm_list.h"
13			#include "sm_geom.h"
14	gwlarson	3.6	#include "sm_qtree.h"
15			#include "sm_stree.h"
16	gwlarson	3.1	#include "sm.h"
17
18	gwlarson	3.6	static int Max_edges=200;
19			static EDGE *Edges=NULL;
20	gwlarson	3.1	static int Ecnt=0;
21
22	gwlarson	3.6	#define remove_tri_compress remove_tri
23			remove_tri(qtptr,fptr,tptr)
24	gwlarson	3.3	QUADTREE *qtptr;
25			int *fptr;
26	gwlarson	3.6	int *tptr;
27	gwlarson	3.3	{
28			int n;
29	gwlarson	3.1
30	gwlarson	3.6	if(QT_IS_EMPTY(*qtptr))
31			return;
32			if(QT_LEAF_IS_FLAG(*qtptr))
33			return;
34	gwlarson	3.3
35	gwlarson	3.6	n = QT_SET_CNT(qtqueryset(*qtptr))-1;
36			qtptr = qtdelelem(qtptr,*tptr);
37			if(n == 0)
38			(*fptr) \|= QT_COMPRESS;
39			if(!QT_FLAG_FILL_TRI(*fptr))
40			(*fptr)++;
41	gwlarson	3.3	}
42
43
44	gwlarson	3.6	smLocator_remove_tri(sm,t_id,v0_id,v1_id,v2_id)
45	gwlarson	3.1	SM *sm;
46			int t_id;
47	gwlarson	3.6	int v0_id,v1_id,v2_id;
48	gwlarson	3.1	{
49			STREE *st;
50	gwlarson	3.3	FVECT v0,v1,v2;
51	gwlarson	3.6
52	gwlarson	3.1	st = SM_LOCATOR(sm);
53
54	gwlarson	3.6	VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
55			VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
56			VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
57	gwlarson	3.1
58	gwlarson	3.6	qtClearAllFlags();
59
60			stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,&t_id);
61
62	gwlarson	3.1	}
63
64			smFree_tri(sm,id)
65			SM *sm;
66			int id;
67			{
68			TRI *tri;
69
70			tri = SM_NTH_TRI(sm,id);
71			/* Add to the free_list */
72			T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
73			SM_FREE_TRIS(sm) = id;
74			T_VALID_FLAG(tri) = -1;
75			}
76
77			/* Assumes mesh pointers have been cleaned up appropriately: just deletes from
78			Point location and triangle data structure
79			*/
80			smDelete_tri(sm,t_id)
81			SM *sm;
82			int t_id;
83			{
84
85			/* NOTE: Assumes that a new triangle adjacent to each vertex
86			has been added- before the deletion: replacing
87			the old tri- and therefore dont need to dereference any pointers
88			to id because the vertices can no longer
89			point to tri id as being the first triangle pointer
90			*/
91			if(!SM_IS_NTH_T_BASE(sm,t_id))
92			{
93	gwlarson	3.6	SM_SAMPLE_TRIS(sm)--;
94	gwlarson	3.1	if(SM_IS_NTH_T_NEW(sm,t_id))
95			smNew_tri_cnt--;
96			}
97			smClear_tri_flags(sm,t_id);
98
99			smFree_tri(sm,t_id);
100	gwlarson	3.6	}
101	gwlarson	3.1
102	gwlarson	3.6
103			int
104			eNew_edge()
105			{
106			if(!Edges)
107			if(!(Edges = (EDGE )realloc(NULL,(Max_edges+1)sizeof(EDGE))))
108			goto memerr;
109
110			if(Ecnt >= Max_edges)
111			{
112			if(Max_edges > 10000)
113			error(CONSISTENCY,"Too many edges in vertex loop\n");
114			Max_edges += 100;
115			if(!(Edges = (EDGE )realloc(Edges,(Max_edges+1)sizeof(EDGE))))
116			goto memerr;
117			}
118			return(++Ecnt);
119
120			memerr:
121			error(SYSTEM,"eNew_edge(): Unable to allocate memory");
122	gwlarson	3.1	}
123
124	gwlarson	3.5	LIST
125	gwlarson	3.6	*smVertex_star_polygon(sm,id,delptr)
126	gwlarson	3.1	SM *sm;
127			int id;
128	gwlarson	3.6	QUADTREE *delptr;
129	gwlarson	3.1	{
130			TRI tri,t_next;
131	gwlarson	3.5	LIST elist,end;
132	gwlarson	3.1	int t_id,v_next,t_next_id;
133			int e;
134	gwlarson	3.6	OBJECT del_set[2];
135	gwlarson	3.1
136			elist = end = NULL;
137			/* Get the first triangle adjacent to vertex id */
138			t_id = SM_NTH_VERT(sm,id);
139			tri = SM_NTH_TRI(sm,t_id);
140
141	gwlarson	3.6	if((e = eNew_edge()) == INVALID)
142			return(NULL);
143
144	gwlarson	3.1	v_next = (T_WHICH_V(tri,id)+1)%3;
145			SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next));
146	gwlarson	3.6	SET_E_NTH_TRI(e,0,INVALID);
147	gwlarson	3.1	SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next));
148			v_next = (T_WHICH_V(tri,id)+2)%3;
149			SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next));
150	gwlarson	3.6	elist = add_data_to_circular_list(elist,&end,e);
151	gwlarson	3.1
152			t_next_id = t_id;
153			t_next = tri;
154
155	gwlarson	3.6	del_set[0] =1; del_set[1] = t_id;
156			*delptr = qtnewleaf(del_set);
157	gwlarson	3.1
158	gwlarson	3.6	while((t_next_id = T_NTH_NBR(t_next,v_next)) != t_id)
159	gwlarson	3.1	{
160	gwlarson	3.6	if((e = eNew_edge()) == INVALID)
161			return(NULL);
162
163			t_next = SM_NTH_TRI(sm,t_next_id);
164			v_next = (T_WHICH_V(t_next,id)+1)%3;
165
166			SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next));
167			SET_E_NTH_TRI(e,0,INVALID);
168			SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next));
169			v_next = (T_WHICH_V(t_next,id)+2)%3;
170			SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next));
171			elist = add_data_to_circular_list(elist,&end,e);
172
173
174			if(qtinset(*delptr,t_next_id))
175	gwlarson	3.1	{
176			#ifdef DEBUG
177	gwlarson	3.6	eputs("smVertex_star_polygon(): id already in set\n");
178			#endif
179			free_list(elist);
180			return(NULL);
181	gwlarson	3.1	}
182	gwlarson	3.6	else
183			qtaddelem(*delptr,t_next_id);
184	gwlarson	3.1	}
185			return(elist);
186			}
187
188			int
189			smEdge_intersect_polygon(sm,v0,v1,l)
190			SM *sm;
191			FVECT v0,v1;
192			LIST *l;
193			{
194			FVECT e0,e1;
195			int e,id_e0,id_e1;
196			LIST el,eptr;
197
198			/* Test the edges in l against v0v1 to see if v0v1 intersects
199			any other edges
200			*/
201
202			el = l;
203
204			while(el)
205			{
206			e = (int)LIST_DATA(el);
207			id_e0 = E_NTH_VERT(e,0);
208			id_e1 = E_NTH_VERT(e,1);
209	gwlarson	3.5
210	gwlarson	3.4	VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm));
211			VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm));
212	gwlarson	3.3	if(sedge_intersect(v0,v1,e0,e1))
213	gwlarson	3.1	return(TRUE);
214
215			el = LIST_NEXT(el);
216			if(el == l)
217			break;
218			}
219			return(FALSE);
220			}
221
222			int
223			smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
224			SM *sm;
225			int id0,id1;
226			FVECT v0,v1;
227			LIST *l;
228			{
229			int e,id;
230			LIST *el;
231			FVECT v;
232
233			/* starting with the end of edge at head of l, search sequentially for
234			vertex v such that v0v1v is a convex angle, and the edge v1v does
235			not intersect any other edges
236			*/
237	gwlarson	3.6	id = INVALID;
238	gwlarson	3.1	el = l;
239			while(id != id0)
240			{
241			e = (int)LIST_DATA(el);
242			id = E_NTH_VERT(e,1);
243
244			smDir(sm,v,id);
245
246			if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l))
247			return(id);
248
249			el = LIST_NEXT(el);
250			if(el == l)
251			break;
252			}
253	gwlarson	3.6	return(INVALID);
254	gwlarson	3.1	}
255
256			int
257			split_edge_list(id0,id_new,l,lnew)
258			int id0,id_new;
259			LIST l,lnew;
260			{
261			LIST list,lptr,*end;
262			int e,e1,e2,new_e;
263
264	gwlarson	3.6	e2 = INVALID;
265	gwlarson	3.1	list = lptr = *l;
266
267	gwlarson	3.6	if((new_e = eNew_edge())==INVALID)
268	gwlarson	3.1	{
269			#ifdef DEBUG
270			eputs("split_edge_list():Too many edges\n");
271			#endif
272			return(FALSE);
273			}
274			SET_E_NTH_VERT(new_e,0,id0);
275			SET_E_NTH_VERT(new_e,1,id_new);
276	gwlarson	3.6	SET_E_NTH_TRI(new_e,0,INVALID);
277			SET_E_NTH_TRI(new_e,1,INVALID);
278	gwlarson	3.1
279			while(e2 != id_new)
280			{
281			lptr = LIST_NEXT(lptr);
282			e = (int)LIST_DATA(lptr);
283			e2 = E_NTH_VERT(e,1);
284			if(lptr == list)
285			{
286			#ifdef DEBUG
287			eputs("split_edge_list():cant find vertex\n");
288			#endif
289			*lnew = NULL;
290			return(FALSE);
291			}
292
293			}
294			end = lptr;
295			lptr = LIST_NEXT(lptr);
296			list = add_data_to_circular_list(list,&end,-new_e);
297			*lnew = list;
298
299			/* now follow other cycle */
300
301			list = lptr;
302	gwlarson	3.6	e2 = INVALID;
303	gwlarson	3.1	while(e2 != id0)
304			{
305			lptr = LIST_NEXT(lptr);
306			e = (int)LIST_DATA(lptr);
307			e2 = E_NTH_VERT(e,1);
308			if(lptr == list)
309			{
310			#ifdef DEBUG
311			eputs("split_edge_list():cant find intial vertex\n");
312			#endif
313			*l = NULL;
314			return(FALSE);
315			}
316
317			}
318			end = lptr;
319			list = add_data_to_circular_list(list,&end,new_e);
320			*l = list;
321			return(TRUE);
322			}
323
324
325	gwlarson	3.3	int
326	gwlarson	3.5	smTriangulate_convex(sm,plist,add_ptr)
327	gwlarson	3.1	SM *sm;
328	gwlarson	3.5	LIST plist,*add_ptr;
329	gwlarson	3.1	{
330			int t_id,e_id0,e_id1,e_id2;
331			int v_id0,v_id1,v_id2;
332			LIST *lptr;
333			int cnt;
334
335			lptr = plist;
336			e_id0 = (int)LIST_DATA(lptr);
337			v_id0 = E_NTH_VERT(e_id0,0);
338			lptr = LIST_NEXT(lptr);
339			while(LIST_NEXT(lptr) != plist)
340			{
341			e_id1 = (int)LIST_DATA(lptr);
342			v_id1 = E_NTH_VERT(e_id1,0);
343			v_id2 = E_NTH_VERT(e_id1,1);
344			/* form a triangle for each triple of with v0 as base of star */
345	gwlarson	3.6	t_id = smAdd_tri(sm,v_id0,v_id1,v_id2);
346	gwlarson	3.5	add_ptr = push_data(add_ptr,t_id);
347
348	gwlarson	3.1	/* add which pointer?*/
349
350			lptr = LIST_NEXT(lptr);
351
352			if(LIST_NEXT(lptr) != plist)
353			{
354			e_id2 = eNew_edge();
355			SET_E_NTH_VERT(e_id2,0,v_id2);
356			SET_E_NTH_VERT(e_id2,1,v_id0);
357			}
358			else
359			e_id2 = (int)LIST_DATA(lptr);
360
361			/* set appropriate tri for each edge*/
362			SET_E_NTH_TRI(e_id0,0,t_id);
363			SET_E_NTH_TRI(e_id1,0,t_id);
364			SET_E_NTH_TRI(e_id2,0,t_id);
365
366			e_id0 = -e_id2;
367			}
368			free_list(plist);
369	gwlarson	3.3	return(TRUE);
370	gwlarson	3.1	}
371	gwlarson	3.3	int
372	gwlarson	3.5	smTriangulate_elist(sm,plist,add_ptr)
373	gwlarson	3.1	SM *sm;
374	gwlarson	3.5	LIST plist,*add_ptr;
375	gwlarson	3.1	{
376			LIST l,el1;
377			FVECT v0,v1,v2;
378			int id0,id1,id2,e,id_next;
379			char flipped;
380	gwlarson	3.3	int done;
381	gwlarson	3.1
382			l = plist;
383
384			while(l)
385			{
386			/* get v0,v1,v2 */
387			e = (int)LIST_DATA(l);
388			id0 = E_NTH_VERT(e,0);
389			id1 = E_NTH_VERT(e,1);
390			l = LIST_NEXT(l);
391			e = (int)LIST_DATA(l);
392			id2 = E_NTH_VERT(e,1);
393
394			smDir(sm,v0,id0);
395			smDir(sm,v1,id1);
396			smDir(sm,v2,id2);
397			/* determine if convex (left turn), or concave(right turn) angle */
398			if(convex_angle(v0,v1,v2))
399			{
400			if(l == plist)
401			break;
402			else
403			continue;
404			}
405			/* if concave: add edge and recurse on two sub polygons */
406			id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l));
407	gwlarson	3.6	if(id_next == INVALID)
408	gwlarson	3.1	{
409			#ifdef DEBUG
410			eputs("smTriangulate_elist():Unable to find convex vertex\n");
411			#endif
412	gwlarson	3.3	return(FALSE);
413	gwlarson	3.1	}
414			/* add edge */
415			el1 = NULL;
416			/* Split edge list l into two lists: one from id1-id_next-id1,
417			and the next from id2-id_next-id2
418			*/
419	gwlarson	3.3	split_edge_list(id1,id_next,&l,&el1);
420	gwlarson	3.1	/* Recurse and triangulate the two edge lists */
421	gwlarson	3.5	done = smTriangulate_elist(sm,l,add_ptr);
422	gwlarson	3.3	if(done)
423	gwlarson	3.5	done = smTriangulate_elist(sm,el1,add_ptr);
424	gwlarson	3.3	return(done);
425	gwlarson	3.1	}
426	gwlarson	3.5	done = smTriangulate_convex(sm,plist,add_ptr);
427	gwlarson	3.3	return(done);
428	gwlarson	3.1	}
429
430			int
431	gwlarson	3.6	smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
432	gwlarson	3.1	SM *sm;
433	gwlarson	3.6	int id0,id1,id2,e0,e1,*e2ptr;
434			{
435			int t_id;
436			int e2;
437
438			t_id = smAdd_tri(sm,id0,id1,id2);
439			if(*e2ptr == 0)
440			{
441			e2 = eNew_edge();
442			SET_E_NTH_VERT(e2,0,id2);
443			SET_E_NTH_VERT(e2,1,id0);
444			}
445			else
446			e2 = *e2ptr;
447			/* set appropriate tri for each edge*/
448			SET_E_NTH_TRI(e0,0,t_id);
449			SET_E_NTH_TRI(e1,0,t_id);
450			SET_E_NTH_TRI(e2,0,t_id);
451
452			*e2ptr = e2;
453			return(t_id);
454			}
455			int
456			smTriangulate_elist_new(sm,id,plist,add_ptr)
457			SM *sm;
458			int id;
459	gwlarson	3.5	LIST plist,*add_ptr;
460	gwlarson	3.1	{
461	gwlarson	3.6	LIST l,prev,*t;
462			FVECT v0,v1,v2,n,p;
463			int is_tri,loop,t_id,id0,id1,id2,e2,eprev,enext;
464			double dp;
465
466			smDir(sm,p,id);
467			enext=0;
468			is_tri= loop = FALSE;
469			l = prev = plist;
470			/* get v0,v1,v2 */
471			eprev = (int)LIST_DATA(l);
472			id0 = E_NTH_VERT(eprev,0);
473			id1 = E_NTH_VERT(eprev,1);
474			smDir(sm,v0,id0);
475			smDir(sm,v1,id1);
476			while(l)
477			{
478			l = LIST_NEXT(l);
479			e2 = (int)LIST_DATA(l);
480			id2 = E_NTH_VERT(e2,1);
481			/* Check if have a triangle */
482			if(LIST_NEXT(LIST_NEXT(l)) == prev)
483			{
484			is_tri = TRUE;
485			break;
486			}
487			if(LIST_NEXT(l) == plist)
488			{
489			if(!loop)
490			loop = 1;
491			else
492			loop++;
493			if(loop > 3)
494			break;
495			}
496			smDir(sm,v2,id2);
497			/* determine if convex (left turn), or concave(right turn) angle */
498			if(!convex_angle(v0,v1,v2))
499			{
500			VCOPY(v0,v1);
501			VCOPY(v1,v2);
502			id0 = id1;
503			id1 = id2;
504			prev = l;
505			eprev = e2;
506			continue;
507			}
508			VCROSS(n,v0,v2);
509			dp = DOT(n,p);
510			if(loop <=1 && (!ZERO(dp) && dp < 0.0))
511			{
512			VCOPY(v0,v1);
513			VCOPY(v1,v2);
514			id0 = id1;
515			id1 = id2;
516			eprev = e2;
517			prev = l;
518			continue;
519			}
520			loop = FALSE;
521
522			enext = 0;
523			t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext);
524			add_ptr = push_data(add_ptr,t_id);
525
526			LIST_NEXT(prev) = LIST_NEXT(l);
527			LIST_DATA(prev) = eprev = -enext;
528			LIST_NEXT(l)=NULL;
529			if(l== plist)
530			plist = prev;
531			free_list(l);
532			l = prev;
533			VCOPY(v1,v2);
534			id1 = id2;
535			}
536			if(is_tri)
537			{
538			l = LIST_NEXT(l);
539			enext = (int)LIST_DATA(l);
540			t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext);
541			add_ptr = push_data(add_ptr,t_id);
542			free_list(l);
543			}
544			else
545			{
546			#ifdef DEBUG
547			eputs("smTriangulate_elist()Unable to triangulate\n");
548			#endif
549			return(FALSE);
550			}
551			return(TRUE);
552			}
553
554			int
555			smTriangulate(sm,p_id,plist,add_ptr)
556			SM *sm;
557			int p_id;
558			LIST plist,*add_ptr;
559			{
560	gwlarson	3.1	int e,id_t0,id_t1,e0,e1;
561			int test;
562	gwlarson	3.6
563			test = smTriangulate_elist_new(sm,p_id,plist,add_ptr);
564			#if 0
565	gwlarson	3.5	test = smTriangulate_elist(sm,plist,add_ptr);
566	gwlarson	3.6	#endif
567	gwlarson	3.1
568			if(!test)
569			return(test);
570	gwlarson	3.6
571	gwlarson	3.1	FOR_ALL_EDGES(e)
572			{
573			id_t0 = E_NTH_TRI(e,0);
574			id_t1 = E_NTH_TRI(e,1);
575	gwlarson	3.6	if((id_t0==INVALID) \|\| (id_t1==INVALID))
576	gwlarson	3.1	{
577			#ifdef DEBUG
578	gwlarson	3.3	eputs("smTriangulate(): Unassigned edge neighbor\n");
579	gwlarson	3.1	#endif
580			continue;
581			}
582
583	gwlarson	3.6	e0 = T_WHICH_V(SM_NTH_TRI(sm,id_t0),E_NTH_VERT(e,0));
584			T_NTH_NBR(SM_NTH_TRI(sm,id_t0),e0) = id_t1;
585	gwlarson	3.1
586	gwlarson	3.6	e1 = T_WHICH_V(SM_NTH_TRI(sm,id_t1),E_NTH_VERT(e,1));
587			T_NTH_NBR(SM_NTH_TRI(sm,id_t1),e1) = id_t0;
588	gwlarson	3.1	}
589			return(test);
590			}
591
592			eIn_tri(e,t)
593			int e;
594			TRI *t;
595			{
596
597			if(T_NTH_V(t,0)==E_NTH_VERT(e,0))
598			return(T_NTH_V(t,1)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,2)==E_NTH_VERT(e,1));
599			else
600			if(T_NTH_V(t,1)==E_NTH_VERT(e,0))
601			return(T_NTH_V(t,0)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,2)==E_NTH_VERT(e,1));
602			else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
603			return(T_NTH_V(t,0)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,1)==E_NTH_VERT(e,1));
604			return(FALSE);
605			}
606	gwlarson	3.6
607			smFix_edges(sm,add_list,delptr)
608	gwlarson	3.1	SM *sm;
609	gwlarson	3.5	LIST *add_list;
610	gwlarson	3.6	QUADTREE *delptr;
611
612	gwlarson	3.1	{
613	gwlarson	3.6	int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next;
614			int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid;
615	gwlarson	3.1	FVECT v0,v1,v2,p,np,v;
616	gwlarson	3.5
617	gwlarson	3.1	FOR_ALL_EDGES(e)
618			{
619	gwlarson	3.6	t0_id = E_NTH_TRI(e,0);
620			t1_id = E_NTH_TRI(e,1);
621			if((t0_id==INVALID) \|\| (t1_id==INVALID))
622	gwlarson	3.1	{
623			#ifdef DEBUG
624			eputs("smFix_edges: Unassigned edge nbr\n");
625			#endif
626			continue;
627			}
628	gwlarson	3.6	e0 = T_WHICH_V(SM_NTH_TRI(sm,t0_id),E_NTH_VERT(e,0));
629			e1 = T_WHICH_V(SM_NTH_TRI(sm,t1_id),E_NTH_VERT(-e,0));
630	gwlarson	3.1	e0_next = (e0+2)%3;
631			e1_next = (e1+2)%3;
632	gwlarson	3.6	v0_id = E_NTH_VERT(e,0);
633			v1_id = E_NTH_VERT(e,1);
634			v2_id = T_NTH_V(SM_NTH_TRI(sm,t0_id),e0_next);
635			p_id = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1_next);
636	gwlarson	3.1
637	gwlarson	3.6	smDir_in_cone(sm,v0,v0_id);
638			smDir_in_cone(sm,v1,v1_id);
639			smDir_in_cone(sm,v2,v2_id);
640	gwlarson	3.1
641	gwlarson	3.6	VCOPY(p,SM_NTH_WV(sm,p_id));
642	gwlarson	3.1	VSUB(p,p,SM_VIEW_CENTER(sm));
643			if(point_in_cone(p,v0,v1,v2))
644			{
645	gwlarson	3.6	smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list,
646			delptr);
647	gwlarson	3.1
648			FOR_ALL_EDGES_FROM(e,i)
649			{
650	gwlarson	3.6	if(E_NTH_TRI(i,0)==t0_id \|\| E_NTH_TRI(i,0)==t1_id)
651	gwlarson	3.1	{
652	gwlarson	3.6	if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
653			SET_E_NTH_TRI(i,0,t0_nid);
654	gwlarson	3.1	else
655	gwlarson	3.6	SET_E_NTH_TRI(i,0,t1_nid);
656	gwlarson	3.1	}
657
658	gwlarson	3.6	if(E_NTH_TRI(i,1)==t0_id \|\| E_NTH_TRI(i,1)==t1_id)
659	gwlarson	3.1	{
660	gwlarson	3.6	if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
661			SET_E_NTH_TRI(i,1,t0_nid);
662	gwlarson	3.1	else
663	gwlarson	3.6	SET_E_NTH_TRI(i,1,t1_nid);
664	gwlarson	3.1	}
665			}
666	gwlarson	3.6	t0_id = t0_nid;
667			t1_id = t1_nid;
668	gwlarson	3.1	e_new = eNew_edge();
669	gwlarson	3.6	SET_E_NTH_VERT(e_new,0,p_id);
670			SET_E_NTH_VERT(e_new,1,v2_id);
671			SET_E_NTH_TRI(e_new,0,t0_id);
672			SET_E_NTH_TRI(e_new,1,t1_id);
673	gwlarson	3.1	}
674			}
675	gwlarson	3.6	smUpdate_locator(sm,add_list,qtqueryset(*delptr));
676	gwlarson	3.1	}
677
678			int
679			smMesh_remove_vertex(sm,id)
680			SM *sm;
681			int id;
682			{
683	gwlarson	3.6	int t_id;
684	gwlarson	3.5	LIST elist,add_list;
685	gwlarson	3.1	int cnt,debug;
686	gwlarson	3.6	QUADTREE delnode;
687	gwlarson	3.1	/* generate list of vertices that form the boundary of the
688			star polygon formed by vertex id and all of its adjacent
689			triangles
690			*/
691			eClear_edges();
692	gwlarson	3.6	elist = smVertex_star_polygon(sm,id,&delnode);
693
694	gwlarson	3.1	if(!elist)
695	gwlarson	3.6	{
696			#ifdef DEBUG
697			eputs("smMesh_remove_vertex(): Unable to remove vertex");
698			#endif
699			qtfreeleaf(delnode);
700			return(FALSE);
701			}
702	gwlarson	3.5	add_list = NULL;
703	gwlarson	3.1	/* Triangulate spherical polygon */
704	gwlarson	3.6	if(!smTriangulate(sm,id,elist,&add_list))
705			{
706			while(add_list)
707			{
708			t_id = pop_list(&add_list);
709			smDelete_tri(sm,t_id);
710			}
711			qtfreeleaf(delnode);
712			return(FALSE);
713			}
714	gwlarson	3.1	/* Fix up new triangles to be Delaunay */
715	gwlarson	3.6	smFix_edges(sm,add_list,&delnode);
716	gwlarson	3.1
717	gwlarson	3.6	qtfreeleaf(delnode);
718	gwlarson	3.1	return(TRUE);
719			}
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734