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;

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

  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
  */
  SM_SAMPLE_TRIS(sm)--;
  if(!SM_IS_NTH_T_BASE(sm,t_id))
  {

#if 0
    if(SM_IS_NTH_T_NEW(sm,t_id))
      smNew_tri_cnt--;
#endif
  }
  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");
}

/* Return list of edges defining polygon formed by boundary of triangles 
adjacent to id. Return set of triangles adjacent to id to delete in delptr
*/
LIST 
*smVertexPolygon(sm,id,del_ptr)
SM *sm;
int id;
LIST **del_ptr;
{
    TRI *tri,*t_next;
    LIST *elist,*end;
    int e,t_id,v_next,t_next_id,b_id,v_id;

    eClear_edges();
    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);

    e = eNew_edge();
    /* Get the  next vertex on the polygon boundary */
    v_id = T_WHICH_V(tri,id);
    b_id = (v_id + 1)%3;
    /* Create an edge */
    SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id));
    SET_E_NTH_TRI(e,0,INVALID);
    SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id));
    v_next = T_NTH_V(tri,(b_id+1)%3);
    SET_E_NTH_VERT(e,1,v_next);
    elist = add_data_to_circular_list(elist,&end,e);
    t_next_id = t_id;
    t_next = tri;

    *del_ptr = push_data(*del_ptr,t_id);
    /* Create a set to hold all of the triangles for deletion later */

    while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id)
    {
      e = eNew_edge();
      t_next = SM_NTH_TRI(sm,t_next_id);
      SET_E_NTH_VERT(e,0,v_next);
      SET_E_NTH_TRI(e,0,INVALID);
      v_id = T_WHICH_V(t_next,id);
      b_id = (v_id + 1)%3;
      SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id));
      v_next = T_NTH_V(t_next,(b_id+1)%3);
      SET_E_NTH_VERT(e,1,v_next);
      elist = add_data_to_circular_list(elist,&end,e);
      *del_ptr = push_data(*del_ptr,t_next_id);
    }
    return(elist);
}


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;

#ifdef DEBUG 
  if(id0 == INVALID || id1==INVALID || id2==INVALID)
    error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n");
#endif
  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
smTriangulateConvex(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;

    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);
        lptr = LIST_NEXT(lptr);

        if(LIST_NEXT(lptr) != plist)    
          e_id2 = 0;
        else
           e_id2 = (int)LIST_DATA(lptr);
        t_id = smTriangulate_add_tri(sm,v_id0,v_id1,v_id2,e_id0,e_id1,&e_id2);
        *add_ptr = push_data(*add_ptr,t_id);
        e_id0 = -e_id2;
    }
    free_list(plist);
    return(TRUE);
}
#ifdef TEST_DRIVER
FVECT Norm[500],B_V[500];
int Ncnt,Bcnt,Del=0;
#endif


/* Triangulate the polygon defined by plist, and generating vertex p_id.
   Return list of added triangles in list add_ptr. Returns TRUE if 
   successful, FALSE otherwise. This is NOT a general triangulation routine,
   assumes polygon star relative to id
*/

int
smTriangulate(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,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew;
    double dp;
    static int debug=0;

    VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
    enew = 0;
    is_convex = TRUE;
    cut = is_tri= FALSE;
    l = prev = plist;

    /* get v0,v1 */
    e1 = (int)LIST_DATA(l);
    id0 = E_NTH_VERT(e1,0);
    id1 = E_NTH_VERT(e1,1);
    VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
    VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));   
#ifdef TEST_DRIVER
    Del = TRUE;
    VCOPY(B_V[0],v0);
    VCOPY(B_V[1],v1);
    Bcnt = 2;
    Ncnt = 0;
#endif
    while(l)
    {
      l = LIST_NEXT(l);
      /* Get v2 */
      e2 = (int)LIST_DATA(l);
      id2 = E_NTH_VERT(e2,1);
      VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
#ifdef TEST_DRIVER
      VCOPY(B_V[Bcnt++],v2);
#endif
      if(LIST_NEXT(LIST_NEXT(l)) == prev)
      {/* Check if have a triangle */
           is_tri = TRUE;       
           break;
      }

      /* determine if v0-v1-v2 is convex:defined clockwise on the sphere-
       so switch orientation
       */
      if(convex_angle(v2,v1,v0))
      {
          /* test if safe to cut off v0-v1-v2 by testing if p lies outside of
         triangle v0-v1-v2: if so, because plist is the star polygon around p,
          the new edge v2-v0 cannot intersect any existing edges
        */
        VCROSS(n,v0,v2);
        dp = DOT(n,p);
        if(dp  <= 0.0)
        {
            /* remove edges e1,e2 and add triangle id0,id1,id2 */
          enew = 0;
          t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
          cut = TRUE;
          *add_ptr = push_data(*add_ptr,t_id);
           /* Insert edge enew into the list, reuse prev list element */
          LIST_NEXT(prev) = LIST_NEXT(l);
          LIST_DATA(prev) = e1 = -enew;
           /* If removing head of list- reset plist pointer */
          if(l== plist)
            plist = prev;
          /* free list element for e2 */
          LIST_NEXT(l)=NULL;
          free_list(l);
          l = prev;
          VCOPY(v1,v2);
          id1 = id2;
          continue;
        }
      }
      else
        is_convex = FALSE;
      VCOPY(v0,v1);
      VCOPY(v1,v2);
      id0 = id1;
      id1 = id2;
      e1 = e2;  
      /* check if gone around circular list without adding any
         triangles: prevent infinite loop */
      if(l == plist)
      {
        if(LIST_NEXT(LIST_NEXT(l)) == prev)
          {/* Check if have a triangle */
            is_tri = TRUE;      
            break;
          }

        if(is_convex)
          break;
        if(!cut)
        {
#ifdef DEBUG
          eputs("smTriangulate():Unable to triangulate\n");
#endif
         free_list(l);
          while(*add_ptr)
          {
            t_id = pop_list(add_ptr);
            smDelete_tri(sm,t_id);
          }
          return(FALSE);
         }
        
        cut = FALSE;
        is_convex = TRUE;
      }
      prev = l;
    }
    if(is_tri)
    {
      l = LIST_NEXT(l);
      enew = (int)LIST_DATA(l);
      t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
      *add_ptr = push_data(*add_ptr,t_id);
      free_list(l);
    }
    else
      if(!smTriangulateConvex(sm,l,add_ptr))
        return(FALSE);

    /* Set triangle adjacencies based on edge adjacencies */ 
    FOR_ALL_EDGES(enew)
    {
      id0 = E_NTH_TRI(enew,0);
      id1 = E_NTH_TRI(enew,1);
        
      e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3;
      T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1;
      
      e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3;
      T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0;
    }
    return(TRUE);
}

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

/* Test the new set of triangles for Delaunay condition. 'Edges' contains
   all of the new edges added. The CCW triangle assoc with each edge is
   tested against the opposite vertex of the CW triangle. If the vertex
   lies inside the circle defined by the CCW triangle- the edge is swapped 
   for the opposite diagonal
*/
smFixEdges(sm,add_list)
   SM *sm;
   LIST *add_list;
{
    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;
    TRI *t0,*t1;

    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
            error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
#endif
        }
        t0 = SM_NTH_TRI(sm,t0_id);
        t1 = SM_NTH_TRI(sm,t1_id);
        e0 = T_NTH_NBR_PTR(t1_id,t0);
        e1 = T_NTH_NBR_PTR(t0_id,t1);

        v0_id = E_NTH_VERT(e,0);
        v1_id = E_NTH_VERT(e,1);
        v2_id = T_NTH_V(t0,e0);
        p_id = T_NTH_V(t1,e1);

        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);
            
           /* Adjust the triangle pointers of the remaining edges to be
              processed
            */
            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);
        }
    }
    /* Add/Delete the appropriate triangles from the stree */
    smUpdate_locator(sm,add_list);
}

/* Remove vertex "id" from the mesh- and retriangulate the resulting
   hole: Returns TRUE if successful, FALSE otherwise.
 */
int
smRemoveVertex(sm,id)
   SM *sm;
   int id;
{
    LIST *b_list,*add_list,*del_list;
    int t_id,i;
    static int cnt=0;
    OBJECT *optr,*os;
    /* generate list of edges that form the boundary of the
       polygon formed by the triangles adjacent to vertex 'id'
     */
    del_list = NULL;
    b_list = smVertexPolygon(sm,id,&del_list);

    add_list = NULL;
    /* Triangulate polygonal hole  */
    if(!smTriangulate(sm,id,b_list,&add_list))
    {
      free_list(del_list);
      return(FALSE);
    }
    else
    {
#ifdef DEBUG
      b_list = del_list;
      while(b_list)
      {
        t_id = LIST_DATA(b_list);
        b_list = LIST_NEXT(b_list);
        T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1;
      }
#endif
      while(del_list)
      {
        t_id = pop_list(&del_list);
        smDelete_tri(sm,t_id);
      }     
    }      
    /* Fix up new triangles to be Delaunay-delnode contains set of
     triangles to delete,add_list is the set of new triangles to add
     */
    smFixEdges(sm,add_list);

    return(TRUE);
}
   

Revision:	3.9
Committed:	Tue Jan 5 16:52:37 1999 UTC (25 years, 3 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.8:	+4 -16 lines
Log Message:	fixed logic in smTest to handle nearby and coincident points, added base tris to rendering, made list of new triangles to speed up rendering
#	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			smFree_tri(sm,id)
23			SM *sm;
24			int id;
25			{
26	gwlarson	3.8	TRI tri,t;
27	gwlarson	3.1
28			tri = SM_NTH_TRI(sm,id);
29			/* Add to the free_list */
30	gwlarson	3.8
31	gwlarson	3.1	T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
32			SM_FREE_TRIS(sm) = id;
33			T_VALID_FLAG(tri) = -1;
34			}
35
36			/* Assumes mesh pointers have been cleaned up appropriately: just deletes from
37			Point location and triangle data structure
38			*/
39			smDelete_tri(sm,t_id)
40			SM *sm;
41			int t_id;
42			{
43
44			/* NOTE: Assumes that a new triangle adjacent to each vertex
45			has been added- before the deletion: replacing
46			the old tri- and therefore dont need to dereference any pointers
47			to id because the vertices can no longer
48			point to tri id as being the first triangle pointer
49			*/
50	gwlarson	3.9	SM_SAMPLE_TRIS(sm)--;
51	gwlarson	3.1	if(!SM_IS_NTH_T_BASE(sm,t_id))
52			{
53	gwlarson	3.9
54			#if 0
55	gwlarson	3.1	if(SM_IS_NTH_T_NEW(sm,t_id))
56			smNew_tri_cnt--;
57	gwlarson	3.9	#endif
58	gwlarson	3.1	}
59			smClear_tri_flags(sm,t_id);
60
61			smFree_tri(sm,t_id);
62	gwlarson	3.6	}
63	gwlarson	3.1
64	gwlarson	3.6
65			int
66			eNew_edge()
67			{
68			if(!Edges)
69			if(!(Edges = (EDGE )realloc(NULL,(Max_edges+1)sizeof(EDGE))))
70			goto memerr;
71
72			if(Ecnt >= Max_edges)
73			{
74			if(Max_edges > 10000)
75			error(CONSISTENCY,"Too many edges in vertex loop\n");
76			Max_edges += 100;
77			if(!(Edges = (EDGE )realloc(Edges,(Max_edges+1)sizeof(EDGE))))
78			goto memerr;
79			}
80			return(++Ecnt);
81
82			memerr:
83			error(SYSTEM,"eNew_edge(): Unable to allocate memory");
84	gwlarson	3.1	}
85
86	gwlarson	3.7	/* Return list of edges defining polygon formed by boundary of triangles
87			adjacent to id. Return set of triangles adjacent to id to delete in delptr
88			*/
89	gwlarson	3.5	LIST
90	gwlarson	3.8	*smVertexPolygon(sm,id,del_ptr)
91	gwlarson	3.1	SM *sm;
92			int id;
93	gwlarson	3.8	LIST **del_ptr;
94	gwlarson	3.1	{
95			TRI tri,t_next;
96	gwlarson	3.5	LIST elist,end;
97	gwlarson	3.7	int e,t_id,v_next,t_next_id,b_id,v_id;
98	gwlarson	3.1
99	gwlarson	3.7	eClear_edges();
100	gwlarson	3.1	elist = end = NULL;
101	gwlarson	3.7
102	gwlarson	3.1	/* Get the first triangle adjacent to vertex id */
103			t_id = SM_NTH_VERT(sm,id);
104			tri = SM_NTH_TRI(sm,t_id);
105
106	gwlarson	3.7	e = eNew_edge();
107			/* Get the next vertex on the polygon boundary */
108			v_id = T_WHICH_V(tri,id);
109			b_id = (v_id + 1)%3;
110			/* Create an edge */
111			SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id));
112	gwlarson	3.6	SET_E_NTH_TRI(e,0,INVALID);
113	gwlarson	3.7	SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id));
114			v_next = T_NTH_V(tri,(b_id+1)%3);
115			SET_E_NTH_VERT(e,1,v_next);
116	gwlarson	3.6	elist = add_data_to_circular_list(elist,&end,e);
117	gwlarson	3.1	t_next_id = t_id;
118			t_next = tri;
119
120	gwlarson	3.8	del_ptr = push_data(del_ptr,t_id);
121	gwlarson	3.7	/* Create a set to hold all of the triangles for deletion later */
122	gwlarson	3.1
123	gwlarson	3.7	while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id)
124			{
125			e = eNew_edge();
126	gwlarson	3.6	t_next = SM_NTH_TRI(sm,t_next_id);
127	gwlarson	3.7	SET_E_NTH_VERT(e,0,v_next);
128	gwlarson	3.6	SET_E_NTH_TRI(e,0,INVALID);
129	gwlarson	3.7	v_id = T_WHICH_V(t_next,id);
130			b_id = (v_id + 1)%3;
131			SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id));
132			v_next = T_NTH_V(t_next,(b_id+1)%3);
133			SET_E_NTH_VERT(e,1,v_next);
134	gwlarson	3.6	elist = add_data_to_circular_list(elist,&end,e);
135	gwlarson	3.8	del_ptr = push_data(del_ptr,t_next_id);
136	gwlarson	3.1	}
137			return(elist);
138			}
139
140	gwlarson	3.7
141	gwlarson	3.1	int
142	gwlarson	3.7	smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
143	gwlarson	3.1	SM *sm;
144	gwlarson	3.7	int id0,id1,id2,e0,e1,*e2ptr;
145	gwlarson	3.1	{
146	gwlarson	3.7	int t_id;
147			int e2;
148	gwlarson	3.1
149	gwlarson	3.7	#ifdef DEBUG
150			if(id0 == INVALID \|\| id1==INVALID \|\| id2==INVALID)
151			error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n");
152	gwlarson	3.1	#endif
153	gwlarson	3.7	t_id = smAdd_tri(sm,id0,id1,id2);
154			if(*e2ptr == 0)
155			{
156			e2 = eNew_edge();
157			SET_E_NTH_VERT(e2,0,id2);
158			SET_E_NTH_VERT(e2,1,id0);
159			}
160			else
161			e2 = *e2ptr;
162			/* set appropriate tri for each edge*/
163			SET_E_NTH_TRI(e0,0,t_id);
164			SET_E_NTH_TRI(e1,0,t_id);
165			SET_E_NTH_TRI(e2,0,t_id);
166	gwlarson	3.1
167	gwlarson	3.7	*e2ptr = e2;
168			return(t_id);
169	gwlarson	3.1	}
170
171	gwlarson	3.3	int
172	gwlarson	3.7	smTriangulateConvex(sm,plist,add_ptr)
173	gwlarson	3.1	SM *sm;
174	gwlarson	3.5	LIST plist,*add_ptr;
175	gwlarson	3.1	{
176			int t_id,e_id0,e_id1,e_id2;
177			int v_id0,v_id1,v_id2;
178			LIST *lptr;
179
180			lptr = plist;
181			e_id0 = (int)LIST_DATA(lptr);
182			v_id0 = E_NTH_VERT(e_id0,0);
183			lptr = LIST_NEXT(lptr);
184			while(LIST_NEXT(lptr) != plist)
185			{
186			e_id1 = (int)LIST_DATA(lptr);
187			v_id1 = E_NTH_VERT(e_id1,0);
188			v_id2 = E_NTH_VERT(e_id1,1);
189			lptr = LIST_NEXT(lptr);
190
191	gwlarson	3.7	if(LIST_NEXT(lptr) != plist)
192			e_id2 = 0;
193	gwlarson	3.1	else
194			e_id2 = (int)LIST_DATA(lptr);
195	gwlarson	3.7	t_id = smTriangulate_add_tri(sm,v_id0,v_id1,v_id2,e_id0,e_id1,&e_id2);
196			add_ptr = push_data(add_ptr,t_id);
197	gwlarson	3.1	e_id0 = -e_id2;
198			}
199			free_list(plist);
200	gwlarson	3.3	return(TRUE);
201	gwlarson	3.1	}
202	gwlarson	3.7	#ifdef TEST_DRIVER
203			FVECT Norm[500],B_V[500];
204			int Ncnt,Bcnt,Del=0;
205	gwlarson	3.1	#endif
206
207	gwlarson	3.6
208	gwlarson	3.7	/* Triangulate the polygon defined by plist, and generating vertex p_id.
209			Return list of added triangles in list add_ptr. Returns TRUE if
210			successful, FALSE otherwise. This is NOT a general triangulation routine,
211			assumes polygon star relative to id
212			*/
213	gwlarson	3.6
214			int
215	gwlarson	3.7	smTriangulate(sm,id,plist,add_ptr)
216	gwlarson	3.6	SM *sm;
217			int id;
218	gwlarson	3.5	LIST plist,*add_ptr;
219	gwlarson	3.1	{
220	gwlarson	3.6	LIST l,prev,*t;
221			FVECT v0,v1,v2,n,p;
222	gwlarson	3.7	int is_tri,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew;
223	gwlarson	3.6	double dp;
224	gwlarson	3.8	static int debug=0;
225	gwlarson	3.6
226	gwlarson	3.7	VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
227			enew = 0;
228			is_convex = TRUE;
229			cut = is_tri= FALSE;
230	gwlarson	3.6	l = prev = plist;
231	gwlarson	3.7
232			/* get v0,v1 */
233			e1 = (int)LIST_DATA(l);
234			id0 = E_NTH_VERT(e1,0);
235			id1 = E_NTH_VERT(e1,1);
236			VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
237			VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));
238			#ifdef TEST_DRIVER
239			Del = TRUE;
240			VCOPY(B_V[0],v0);
241			VCOPY(B_V[1],v1);
242			Bcnt = 2;
243			Ncnt = 0;
244			#endif
245	gwlarson	3.6	while(l)
246			{
247			l = LIST_NEXT(l);
248	gwlarson	3.7	/* Get v2 */
249	gwlarson	3.6	e2 = (int)LIST_DATA(l);
250			id2 = E_NTH_VERT(e2,1);
251	gwlarson	3.7	VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
252			#ifdef TEST_DRIVER
253			VCOPY(B_V[Bcnt++],v2);
254			#endif
255	gwlarson	3.6	if(LIST_NEXT(LIST_NEXT(l)) == prev)
256	gwlarson	3.7	{/* Check if have a triangle */
257			is_tri = TRUE;
258			break;
259			}
260
261			/* determine if v0-v1-v2 is convex:defined clockwise on the sphere-
262			so switch orientation
263			*/
264			if(convex_angle(v2,v1,v0))
265	gwlarson	3.6	{
266	gwlarson	3.7	/* test if safe to cut off v0-v1-v2 by testing if p lies outside of
267			triangle v0-v1-v2: if so, because plist is the star polygon around p,
268			the new edge v2-v0 cannot intersect any existing edges
269			*/
270			VCROSS(n,v0,v2);
271			dp = DOT(n,p);
272			if(dp <= 0.0)
273			{
274			/* remove edges e1,e2 and add triangle id0,id1,id2 */
275			enew = 0;
276			t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
277			cut = TRUE;
278			add_ptr = push_data(add_ptr,t_id);
279			/* Insert edge enew into the list, reuse prev list element */
280			LIST_NEXT(prev) = LIST_NEXT(l);
281			LIST_DATA(prev) = e1 = -enew;
282			/* If removing head of list- reset plist pointer */
283			if(l== plist)
284			plist = prev;
285			/* free list element for e2 */
286			LIST_NEXT(l)=NULL;
287			free_list(l);
288			l = prev;
289			VCOPY(v1,v2);
290			id1 = id2;
291			continue;
292			}
293	gwlarson	3.6	}
294	gwlarson	3.7	else
295			is_convex = FALSE;
296			VCOPY(v0,v1);
297			VCOPY(v1,v2);
298			id0 = id1;
299			id1 = id2;
300			e1 = e2;
301			/* check if gone around circular list without adding any
302			triangles: prevent infinite loop */
303			if(l == plist)
304	gwlarson	3.6	{
305	gwlarson	3.7	if(LIST_NEXT(LIST_NEXT(l)) == prev)
306			{/* Check if have a triangle */
307			is_tri = TRUE;
308			break;
309			}
310
311			if(is_convex)
312	gwlarson	3.6	break;
313	gwlarson	3.7	if(!cut)
314			{
315			#ifdef DEBUG
316			eputs("smTriangulate():Unable to triangulate\n");
317			#endif
318	gwlarson	3.8	free_list(l);
319	gwlarson	3.7	while(*add_ptr)
320			{
321			t_id = pop_list(add_ptr);
322			smDelete_tri(sm,t_id);
323			}
324			return(FALSE);
325	gwlarson	3.8	}
326
327	gwlarson	3.7	cut = FALSE;
328			is_convex = TRUE;
329	gwlarson	3.6	}
330	gwlarson	3.7	prev = l;
331	gwlarson	3.6	}
332			if(is_tri)
333			{
334			l = LIST_NEXT(l);
335	gwlarson	3.7	enew = (int)LIST_DATA(l);
336			t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
337	gwlarson	3.6	add_ptr = push_data(add_ptr,t_id);
338			free_list(l);
339	gwlarson	3.7	}
340	gwlarson	3.6	else
341	gwlarson	3.7	if(!smTriangulateConvex(sm,l,add_ptr))
342	gwlarson	3.6	return(FALSE);
343
344	gwlarson	3.7	/* Set triangle adjacencies based on edge adjacencies */
345			FOR_ALL_EDGES(enew)
346	gwlarson	3.1	{
347	gwlarson	3.7	id0 = E_NTH_TRI(enew,0);
348			id1 = E_NTH_TRI(enew,1);
349	gwlarson	3.1
350	gwlarson	3.7	e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3;
351			T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1;
352
353			e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3;
354			T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0;
355	gwlarson	3.1	}
356	gwlarson	3.7	return(TRUE);
357	gwlarson	3.1	}
358
359			eIn_tri(e,t)
360			int e;
361			TRI *t;
362			{
363
364			if(T_NTH_V(t,0)==E_NTH_VERT(e,0))
365			return(T_NTH_V(t,1)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,2)==E_NTH_VERT(e,1));
366			else
367			if(T_NTH_V(t,1)==E_NTH_VERT(e,0))
368			return(T_NTH_V(t,0)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,2)==E_NTH_VERT(e,1));
369			else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
370			return(T_NTH_V(t,0)==E_NTH_VERT(e,1)\|\|T_NTH_V(t,1)==E_NTH_VERT(e,1));
371	gwlarson	3.7
372	gwlarson	3.1	return(FALSE);
373			}
374	gwlarson	3.6
375	gwlarson	3.7	/* Test the new set of triangles for Delaunay condition. 'Edges' contains
376			all of the new edges added. The CCW triangle assoc with each edge is
377			tested against the opposite vertex of the CW triangle. If the vertex
378			lies inside the circle defined by the CCW triangle- the edge is swapped
379			for the opposite diagonal
380			*/
381	gwlarson	3.8	smFixEdges(sm,add_list)
382	gwlarson	3.1	SM *sm;
383	gwlarson	3.5	LIST *add_list;
384	gwlarson	3.1	{
385	gwlarson	3.6	int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next;
386			int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid;
387	gwlarson	3.1	FVECT v0,v1,v2,p,np,v;
388	gwlarson	3.7	TRI t0,t1;
389	gwlarson	3.5
390	gwlarson	3.1	FOR_ALL_EDGES(e)
391			{
392	gwlarson	3.6	t0_id = E_NTH_TRI(e,0);
393			t1_id = E_NTH_TRI(e,1);
394			if((t0_id==INVALID) \|\| (t1_id==INVALID))
395	gwlarson	3.1	{
396			#ifdef DEBUG
397	gwlarson	3.7	error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
398	gwlarson	3.1	#endif
399			}
400	gwlarson	3.7	t0 = SM_NTH_TRI(sm,t0_id);
401			t1 = SM_NTH_TRI(sm,t1_id);
402			e0 = T_NTH_NBR_PTR(t1_id,t0);
403			e1 = T_NTH_NBR_PTR(t0_id,t1);
404
405	gwlarson	3.6	v0_id = E_NTH_VERT(e,0);
406			v1_id = E_NTH_VERT(e,1);
407	gwlarson	3.7	v2_id = T_NTH_V(t0,e0);
408			p_id = T_NTH_V(t1,e1);
409	gwlarson	3.1
410	gwlarson	3.6	smDir_in_cone(sm,v0,v0_id);
411			smDir_in_cone(sm,v1,v1_id);
412			smDir_in_cone(sm,v2,v2_id);
413	gwlarson	3.1
414	gwlarson	3.6	VCOPY(p,SM_NTH_WV(sm,p_id));
415	gwlarson	3.1	VSUB(p,p,SM_VIEW_CENTER(sm));
416			if(point_in_cone(p,v0,v1,v2))
417			{
418	gwlarson	3.8	smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list);
419	gwlarson	3.1
420	gwlarson	3.7	/* Adjust the triangle pointers of the remaining edges to be
421			processed
422			*/
423	gwlarson	3.1	FOR_ALL_EDGES_FROM(e,i)
424			{
425	gwlarson	3.6	if(E_NTH_TRI(i,0)==t0_id \|\| E_NTH_TRI(i,0)==t1_id)
426	gwlarson	3.1	{
427	gwlarson	3.6	if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
428			SET_E_NTH_TRI(i,0,t0_nid);
429	gwlarson	3.1	else
430	gwlarson	3.6	SET_E_NTH_TRI(i,0,t1_nid);
431	gwlarson	3.1	}
432
433	gwlarson	3.6	if(E_NTH_TRI(i,1)==t0_id \|\| E_NTH_TRI(i,1)==t1_id)
434	gwlarson	3.1	{
435	gwlarson	3.6	if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
436			SET_E_NTH_TRI(i,1,t0_nid);
437	gwlarson	3.1	else
438	gwlarson	3.6	SET_E_NTH_TRI(i,1,t1_nid);
439	gwlarson	3.1	}
440			}
441	gwlarson	3.6	t0_id = t0_nid;
442			t1_id = t1_nid;
443	gwlarson	3.1	e_new = eNew_edge();
444	gwlarson	3.6	SET_E_NTH_VERT(e_new,0,p_id);
445			SET_E_NTH_VERT(e_new,1,v2_id);
446			SET_E_NTH_TRI(e_new,0,t0_id);
447			SET_E_NTH_TRI(e_new,1,t1_id);
448	gwlarson	3.1	}
449			}
450	gwlarson	3.7	/* Add/Delete the appropriate triangles from the stree */
451	gwlarson	3.8	smUpdate_locator(sm,add_list);
452	gwlarson	3.1	}
453
454	gwlarson	3.7	/* Remove vertex "id" from the mesh- and retriangulate the resulting
455			hole: Returns TRUE if successful, FALSE otherwise.
456			*/
457	gwlarson	3.1	int
458	gwlarson	3.7	smRemoveVertex(sm,id)
459	gwlarson	3.1	SM *sm;
460			int id;
461			{
462	gwlarson	3.8	LIST b_list,add_list,*del_list;
463			int t_id,i;
464			static int cnt=0;
465			OBJECT optr,os;
466	gwlarson	3.7	/* generate list of edges that form the boundary of the
467			polygon formed by the triangles adjacent to vertex 'id'
468	gwlarson	3.1	*/
469	gwlarson	3.8	del_list = NULL;
470			b_list = smVertexPolygon(sm,id,&del_list);
471	gwlarson	3.6
472	gwlarson	3.5	add_list = NULL;
473	gwlarson	3.7	/* Triangulate polygonal hole */
474			if(!smTriangulate(sm,id,b_list,&add_list))
475	gwlarson	3.6	{
476	gwlarson	3.8	free_list(del_list);
477	gwlarson	3.6	return(FALSE);
478			}
479	gwlarson	3.8	else
480			{
481			#ifdef DEBUG
482			b_list = del_list;
483			while(b_list)
484			{
485			t_id = LIST_DATA(b_list);
486			b_list = LIST_NEXT(b_list);
487			T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1;
488			}
489			#endif
490			while(del_list)
491			{
492			t_id = pop_list(&del_list);
493			smDelete_tri(sm,t_id);
494			}
495			}
496	gwlarson	3.7	/* Fix up new triangles to be Delaunay-delnode contains set of
497			triangles to delete,add_list is the set of new triangles to add
498			*/
499	gwlarson	3.8	smFixEdges(sm,add_list);
500	gwlarson	3.7
501	gwlarson	3.1	return(TRUE);
502			}
503
504
505
506	gwlarson	3.8
507	gwlarson	3.1
508
509
510
511
512
513
514
515
516
517