ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_del.c
(Generate patch)

Comparing ray/src/hd/sm_del.c (file contents):
Revision 3.3 by gwlarson, Fri Sep 11 11:52:25 1998 UTC vs.
Revision 3.6 by gwlarson, Tue Oct 6 18:16:53 1998 UTC

# Line 8 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8   *  sm_del.c
9   */
10   #include "standard.h"
11 <
11 > #include "sm_flag.h"
12   #include "sm_list.h"
13   #include "sm_geom.h"
14 + #include "sm_qtree.h"
15 + #include "sm_stree.h"
16   #include "sm.h"
17  
18 < static EDGE Edges[MAX_EDGES];
18 > static int Max_edges=200;
19 > static EDGE *Edges=NULL;
20   static int Ecnt=0;
21  
22 < int
23 < remove_tri(qtptr,fptr,t_id)
22 > #define remove_tri_compress remove_tri
23 > remove_tri(qtptr,fptr,tptr)
24     QUADTREE *qtptr;
25     int *fptr;
26 <   int t_id;
26 >   int *tptr;
27   {
25 –    OBJECT tset[QT_MAXSET+1];  
28      int n;
29  
30 <   if(QT_IS_EMPTY(*qtptr))
31 <     return(FALSE);
32 <   /* remove id from set */
33 <      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 < }
30 >    if(QT_IS_EMPTY(*qtptr))
31 >      return;
32 >    if(QT_LEAF_IS_FLAG(*qtptr))
33 >      return;
34  
35 < int
36 < remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id)
37 < QUADTREE *qtptr;
38 < FVECT q0,q1,q2;
39 < FVECT t0,t1,t2;
40 < 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));
35 >    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   }
42  
43  
44 <
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 < smLocator_remove_tri(sm,t_id)
44 > smLocator_remove_tri(sm,t_id,v0_id,v1_id,v2_id)
45   SM *sm;
46   int t_id;
47 + int v0_id,v1_id,v2_id;
48   {
49    STREE *st;
92 –  char found;
93 –  TRI *t;
50    FVECT v0,v1,v2;
51 <
51 >  
52    st = SM_LOCATOR(sm);
53  
54 <  t = SM_NTH_TRI(sm,t_id);
54 >  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  
58 <  VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
59 <  VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
60 <  VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
61 <  found = stUpdate_tri(st,t_id,v0,v1,v2,remove_tri,remove_tri_compress);
104 <  return(found);
58 >  qtClearAllFlags();
59 >  
60 >  stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,&t_id);
61 >
62   }
63  
64   smFree_tri(sm,id)
# Line 125 | Line 82 | SM *sm;
82   int t_id;
83   {
84  
128 –
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
# Line 134 | Line 90 | int t_id;
90    */
91    if(!SM_IS_NTH_T_BASE(sm,t_id))
92    {
93 <    SM_NUM_TRIS(sm)--;
93 >    SM_SAMPLE_TRIS(sm)--;
94      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);
144 –
100   }
101  
102  
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 < LIST
111 < *smVertex_star_polygon(sm,id)
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 > }
123 >
124 > LIST
125 > *smVertex_star_polygon(sm,id,delptr)
126   SM *sm;
127   int id;
128 + QUADTREE *delptr;
129   {
130      TRI *tri,*t_next;
131 <    LIST *elist,*end,*tlist;
131 >    LIST *elist,*end;
132      int t_id,v_next,t_next_id;
133      int e;
134 +    OBJECT del_set[2];
135  
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 <    
142 <    if((e = eNew_edge()) == SM_INVALID)
143 <    {
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);
141 >    if((e = eNew_edge()) == INVALID)
142 >      return(NULL);
143 >
144      v_next = (T_WHICH_V(tri,id)+1)%3;
145      SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next));
146 <    SET_E_NTH_TRI(e,0,SM_INVALID);
146 >    SET_E_NTH_TRI(e,0,INVALID);
147      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 +    elist = add_data_to_circular_list(elist,&end,e);
151  
180 –    
152      t_next_id = t_id;
153      t_next = tri;
154  
155 <    tlist = push_data(NULL,t_id);
155 >    del_set[0] =1; del_set[1] = t_id;
156 >    *delptr = qtnewleaf(del_set);
157  
158 <    while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id)
158 >    while((t_next_id = T_NTH_NBR(t_next,v_next)) != t_id)
159      {  
160 <        if((e = eNew_edge()) == SM_INVALID)
160 >      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          {
176   #ifdef DEBUG
177 <            eputs("smVertex_star_polygon():Too many edges\n");
178 < #endif
179 <            return(NULL);
177 >          eputs("smVertex_star_polygon(): id already in set\n");
178 > #endif    
179 >          free_list(elist);
180 >          return(NULL);
181          }
182 <        elist = add_data_to_circular_list(elist,&end,e);
183 <        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);
182 >      else
183 >        qtaddelem(*delptr,t_next_id);
184      }
205 –    while(tlist)
206 –    {
207 –        t_id = (int)pop_list(&tlist);
208 –        /* first remove from point location structure */
209 –        smLocator_remove_tri(sm,t_id);
210 –        smDelete_tri(sm,t_id);
211 –    }
185      return(elist);
186   }
187  
# Line 233 | Line 206 | LIST *l;
206        e = (int)LIST_DATA(el);
207        id_e0 = E_NTH_VERT(e,0);
208        id_e1 = E_NTH_VERT(e,1);
209 <      /* NOTE: DO these need to be normalized? Just subtract center? */
210 <      smDir(sm,e0,id_e0);
211 <      smDir(sm,e1,id_e1);
209 >
210 >      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        if(sedge_intersect(v0,v1,e0,e1))
213          return(TRUE);
214  
# Line 261 | Line 234 | smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
234        vertex v such that v0v1v is a convex angle, and the edge v1v does
235        not intersect any other edges
236     */
237 <    id = SM_INVALID;
237 >    id = INVALID;
238      el = l;
239      while(id != id0)
240      {
# Line 277 | Line 250 | smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
250          if(el == l)
251             break;
252      }
253 <    return(SM_INVALID);
253 >    return(INVALID);
254   }
255  
256   int
# Line 288 | Line 261 | LIST **l,**lnew;
261      LIST *list,*lptr,*end;
262      int e,e1,e2,new_e;
263  
264 <    e2 = SM_INVALID;
264 >    e2 = INVALID;
265      list = lptr = *l;
266  
267 <    if((new_e = eNew_edge())==SM_INVALID)
267 >    if((new_e = eNew_edge())==INVALID)
268       {
269   #ifdef DEBUG
270              eputs("split_edge_list():Too many edges\n");
# Line 300 | Line 273 | LIST **l,**lnew;
273       }
274      SET_E_NTH_VERT(new_e,0,id0);
275      SET_E_NTH_VERT(new_e,1,id_new);
276 <    SET_E_NTH_TRI(new_e,0,SM_INVALID);
277 <    SET_E_NTH_TRI(new_e,1,SM_INVALID);
276 >    SET_E_NTH_TRI(new_e,0,INVALID);
277 >    SET_E_NTH_TRI(new_e,1,INVALID);
278      
279      while(e2 != id_new)
280      {
# Line 326 | Line 299 | LIST **l,**lnew;
299      /* now follow other cycle */
300  
301      list = lptr;
302 <    e2 = SM_INVALID;
302 >    e2 = INVALID;
303      while(e2 != id0)
304      {
305          lptr = LIST_NEXT(lptr);
# Line 350 | Line 323 | LIST **l,**lnew;
323  
324  
325   int
326 < smTriangulate_convex(sm,plist)
326 > smTriangulate_convex(sm,plist,add_ptr)
327   SM *sm;
328 < LIST *plist;
328 > LIST *plist,**add_ptr;
329   {
357 –    TRI *tri;
330      int t_id,e_id0,e_id1,e_id2;
331      int v_id0,v_id1,v_id2;
332      LIST *lptr;
# Line 370 | Line 342 | LIST *plist;
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 <        t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri);
346 <        smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2);
345 >        t_id = smAdd_tri(sm,v_id0,v_id1,v_id2);
346 >        *add_ptr = push_data(*add_ptr,t_id);
347 >
348          /* add which pointer?*/
349  
350          lptr = LIST_NEXT(lptr);
# Line 392 | Line 365 | LIST *plist;
365  
366          e_id0 = -e_id2;
367      }
395 –    
368      free_list(plist);
369      return(TRUE);
370   }
371   int
372 < smTriangulate_elist(sm,plist)
372 > smTriangulate_elist(sm,plist,add_ptr)
373   SM *sm;
374 < LIST *plist;
374 > LIST *plist,**add_ptr;
375   {
376      LIST *l,*el1;
377      FVECT v0,v1,v2;
# Line 432 | Line 404 | LIST *plist;
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 <      if(id_next == SM_INVALID)
407 >      if(id_next == INVALID)
408        {
409   #ifdef DEBUG
410            eputs("smTriangulate_elist():Unable to find convex vertex\n");
# Line 446 | Line 418 | LIST *plist;
418        */
419        split_edge_list(id1,id_next,&l,&el1);
420        /* Recurse and triangulate the two edge lists */
421 <      done = smTriangulate_elist(sm,l);
421 >      done = smTriangulate_elist(sm,l,add_ptr);
422        if(done)
423 <        done = smTriangulate_elist(sm,el1);
423 >        done = smTriangulate_elist(sm,el1,add_ptr);
424        return(done);
425      }
426 <    done = smTriangulate_convex(sm,plist);
426 >    done = smTriangulate_convex(sm,plist,add_ptr);
427      return(done);
428   }
429  
430   int
431 < smTriangulate(sm,plist)
431 > smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
432   SM *sm;
433 < LIST *plist;
433 > 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 + LIST *plist,**add_ptr;
460 + {
461 +    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      int e,id_t0,id_t1,e0,e1;
464 –    TRI *t0,*t1;
561      int test;
466 –    
467 –    test = smTriangulate_elist(sm,plist);
562  
563 +    test = smTriangulate_elist_new(sm,p_id,plist,add_ptr);
564 + #if 0
565 +    test = smTriangulate_elist(sm,plist,add_ptr);
566 + #endif
567 +
568      if(!test)
569         return(test);
570 +
571      FOR_ALL_EDGES(e)
572      {
573          id_t0 = E_NTH_TRI(e,0);
574          id_t1 = E_NTH_TRI(e,1);
575 <        if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
575 >        if((id_t0==INVALID) || (id_t1==INVALID))
576          {
577   #ifdef DEBUG
578             eputs("smTriangulate(): Unassigned edge neighbor\n");
579   #endif
580              continue;
581          }
482 –        t0 = SM_NTH_TRI(sm,id_t0);
483 –        t1 = SM_NTH_TRI(sm,id_t1);
582          
583 <        e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
584 <        T_NTH_NBR(t0,e0) = id_t1;
583 >        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  
586 <        e1 = T_WHICH_V(t1,E_NTH_VERT(e,1));
587 <        T_NTH_NBR(t1,e1) = id_t0;
586 >        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      }
589      return(test);
590   }
# Line 505 | Line 603 | TRI *t;
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 < smFix_edges(sm)
606 >
607 > smFix_edges(sm,add_list,delptr)
608     SM *sm;
609 +   LIST *add_list;
610 +   QUADTREE *delptr;
611 +
612   {
613 <    int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next;
614 <    TRI *t0,*t1,*nt0,*nt1;
513 <    int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1;
613 >    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      FVECT v0,v1,v2,p,np,v;
616 <    LIST *add,*del;
516 <    
517 <    add = del = NULL;
616 >
617      FOR_ALL_EDGES(e)
618      {
619 <        id_t0 = E_NTH_TRI(e,0);
620 <        id_t1 = E_NTH_TRI(e,1);
621 <        if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
619 >        t0_id = E_NTH_TRI(e,0);
620 >        t1_id = E_NTH_TRI(e,1);
621 >        if((t0_id==INVALID) || (t1_id==INVALID))
622          {
623   #ifdef DEBUG
624              eputs("smFix_edges: Unassigned edge nbr\n");
625   #endif
626              continue;
627          }
628 <        t0 = SM_NTH_TRI(sm,id_t0);
629 <        t1 = SM_NTH_TRI(sm,id_t1);
531 <        
532 <        e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
533 <        e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0));
628 >        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          e0_next = (e0+2)%3;
631          e1_next = (e1+2)%3;
632 <        id_v0 = E_NTH_VERT(e,0);
633 <        id_v1 = E_NTH_VERT(e,1);
634 <        id_v2 = T_NTH_V(t0,e0_next);
635 <        id_p = T_NTH_V(t1,e1_next);
632 >        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  
637 <        smDir(sm,v0,id_v0);
638 <        smDir(sm,v1,id_v1);
639 <        smDir(sm,v2,id_v2);
637 >        smDir_in_cone(sm,v0,v0_id);
638 >        smDir_in_cone(sm,v1,v1_id);
639 >        smDir_in_cone(sm,v2,v2_id);
640          
641 <        VCOPY(p,SM_NTH_WV(sm,id_p));    
641 >        VCOPY(p,SM_NTH_WV(sm,p_id));    
642          VSUB(p,p,SM_VIEW_CENTER(sm));
643          if(point_in_cone(p,v0,v1,v2))
644          {
645 <            smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del);
645 >           smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list,
646 >                            delptr);
647              
551 –            nt0 = SM_NTH_TRI(sm,nid_t0);
552 –            nt1 = SM_NTH_TRI(sm,nid_t1);
648              FOR_ALL_EDGES_FROM(e,i)
649              {
650 <              if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1)
650 >              if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id)
651                {
652 <                if(eIn_tri(i,nt0))
653 <                  SET_E_NTH_TRI(i,0,nid_t0);
652 >                if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
653 >                  SET_E_NTH_TRI(i,0,t0_nid);
654                  else
655 <                  SET_E_NTH_TRI(i,0,nid_t1);
655 >                  SET_E_NTH_TRI(i,0,t1_nid);
656                }
657  
658 <              if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1)
658 >              if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id)
659                {
660 <                if(eIn_tri(i,nt0))
661 <                  SET_E_NTH_TRI(i,1,nid_t0);
660 >                if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
661 >                  SET_E_NTH_TRI(i,1,t0_nid);
662                  else
663 <                  SET_E_NTH_TRI(i,1,nid_t1);
663 >                  SET_E_NTH_TRI(i,1,t1_nid);
664                }
665              }
666 <            id_t0 = nid_t0;
667 <            id_t1 = nid_t1;
666 >            t0_id = t0_nid;
667 >            t1_id = t1_nid;
668              e_new = eNew_edge();
669 <            SET_E_NTH_VERT(e_new,0,id_p);
670 <            SET_E_NTH_VERT(e_new,1,id_v2);
671 <            SET_E_NTH_TRI(e_new,0,id_t0);
672 <            SET_E_NTH_TRI(e_new,1,id_t1);
669 >            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          }
674      }
675 <    smUpdate_locator(sm,add,del);
675 >    smUpdate_locator(sm,add_list,qtqueryset(*delptr));
676   }
677  
678   int
# Line 585 | Line 680 | smMesh_remove_vertex(sm,id)
680     SM *sm;
681     int id;
682   {
683 <    int tri;
684 <    LIST *elist;
683 >    int t_id;
684 >    LIST *elist,*add_list;
685      int cnt,debug;
686 +    QUADTREE delnode;
687      /* 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 <    elist = smVertex_star_polygon(sm,id);
597 <    if(!elist)
598 <       return(FALSE);
692 >    elist = smVertex_star_polygon(sm,id,&delnode);
693  
694 +    if(!elist)
695 +    {
696 + #ifdef DEBUG
697 +      eputs("smMesh_remove_vertex(): Unable to remove vertex");
698 + #endif
699 +      qtfreeleaf(delnode);
700 +      return(FALSE);
701 +    }
702 +    add_list = NULL;
703      /* Triangulate spherical polygon */
704 <    smTriangulate(sm,elist);
705 <
706 <
704 >    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      /* Fix up new triangles to be Delaunay */
715 <    smFix_edges(sm);
715 >    smFix_edges(sm,add_list,&delnode);
716  
717 +    qtfreeleaf(delnode);
718      return(TRUE);
719   }
720    
610 – /* Remove point from samples, and from mesh. Delete any triangles
611 –   adjacent to the point and re-triangulate the hole
612 –   Return TRUE is point found , FALSE otherwise
613 – */
614 – int
615 – smDelete_point(sm,id)
616 – SM *sm;
617 – int id;
618 – {
619 –
620 –    /* Remove the corresponding vertex from the mesh */
621 –    smMesh_remove_vertex(sm,id);
622 –    /* Free the sample point */
623 –    smDelete_sample(sm,id);
624 –    return(TRUE);
625 – }
721  
722  
723  

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines