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;
{
    OBJECT tset[QT_MAXSET+1];   
    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));
}


int
stDelete_tri(st,t_id,t0,t1,t2)
   STREE *st;
   int t_id;
   FVECT t0,t1,t2;
{
    int f;
    FVECT dir;
    
  /* First add all of the leaf cells lying on the triangle perimeter:
     mark all cells seen on the way
   */
    ST_CLEAR_FLAGS(st);
    f = 0;
    VSUB(dir,t1,t0);
    stTrace_edge(st,t0,dir,1.0,remove_tri,&f,t_id);
    VSUB(dir,t2,t1);
    stTrace_edge(st,t1,dir,1.0,remove_tri,&f,t_id);
    VSUB(dir,t0,t2);
    stTrace_edge(st,t2,dir,1.0,remove_tri,&f,t_id);
    /* Now visit interior */
    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
       stVisit_tri_interior(st,t0,t1,t2,remove_tri_compress,&f,t_id);
}


smLocator_remove_tri(sm,t_id)
SM *sm;
int t_id;
{
  STREE *st;
  char found;
  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));
  found = stUpdate_tri(st,t_id,v0,v1,v2,remove_tri,remove_tri_compress);
  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);
      /* NOTE: DO these need to be normalized? Just subtract center? */
      /*
        smDir(sm,e0,id_e0);
        smDir(sm,e1,id_e1);
        */
      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)
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);
    return(TRUE);
}
int
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 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);
      if(done)
        done = smTriangulate_elist(sm,el1);
      return(done);
    }
    done = smTriangulate_convex(sm,plist);
    return(done);
}

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

    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)
   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 */
    smTriangulate(sm,elist);


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