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.1 by gwlarson, Wed Aug 19 17:45:24 1998 UTC vs.
Revision 3.5 by gwlarson, Wed Sep 16 18:16:28 1998 UTC

# Line 16 | Line 16 | static char SCCSid[] = "$SunId$ SGI";
16   static EDGE Edges[MAX_EDGES];
17   static int Ecnt=0;
18  
19 + int
20 + remove_tri(qtptr,fptr,t_id)
21 +   QUADTREE *qtptr;
22 +   int *fptr;
23 +   int t_id;
24 + {
25 +    int n;
26  
27 +   if(QT_IS_EMPTY(*qtptr))
28 +     return(FALSE);
29 +   /* remove id from set */
30 +      else
31 +      {
32 +         if(!qtinset(*qtptr,t_id))
33 +           return(FALSE);
34 +         n = QT_SET_CNT(qtqueryset(*qtptr))-1;
35 +         *qtptr = qtdelelem(*qtptr,t_id);
36 +          if(n  == 0)
37 +             (*fptr) |= QT_COMPRESS;
38 +        if(!QT_FLAG_FILL_TRI(*fptr))
39 +          (*fptr)++;
40 +      }
41 +    return(TRUE);
42 + }
43 +
44 + int
45 + remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id)
46 + QUADTREE *qtptr;
47 + FVECT q0,q1,q2;
48 + FVECT t0,t1,t2;
49 + int n;
50 + int *arg;
51 + int t_id;
52 + {
53 +    int f = 0;
54 +    /* NOTE compress */
55 +    return(remove_tri(qtptr,&f,t_id));
56 + }
57 +
58 +
59   smLocator_remove_tri(sm,t_id)
60   SM *sm;
61   int t_id;
62   {
63    STREE *st;
25 –  char found;
64    TRI *t;
65 <  FVECT p0,p1,p2;
65 >  FVECT v0,v1,v2;
66  
67    st = SM_LOCATOR(sm);
68  
69    t = SM_NTH_TRI(sm,t_id);
70  
71 <  smDir(sm,p0,T_NTH_V(t,0));
72 <  smDir(sm,p1,T_NTH_V(t,1));
73 <  smDir(sm,p2,T_NTH_V(t,2));
74 <
37 <  found = stRemove_tri(st,t_id,p0,p1,p2);
38 <
39 <  return(found);
71 >  VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
72 >  VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
73 >  VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
74 >  stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,t_id,NULL);
75   }
76  
77   smFree_tri(sm,id)
# Line 60 | Line 95 | SM *sm;
95   int t_id;
96   {
97  
63 –    /* first remove from point location structure */
64 –    smLocator_remove_tri(sm,t_id);
98  
99    /* NOTE: Assumes that a new triangle adjacent to each vertex
100       has been added- before the deletion: replacing
# Line 82 | Line 115 | int t_id;
115   }
116  
117  
118 <
119 < LIST
87 < *smVertex_star_polygon(sm,id)
118 > LIST
119 > *smVertex_star_polygon(sm,id,del_set)
120   SM *sm;
121   int id;
122 + OBJECT *del_set;
123   {
124      TRI *tri,*t_next;
125 <    LIST *elist,*end,*tlist;
125 >    LIST *elist,*end;
126      int t_id,v_next,t_next_id;
127      int e;
128  
# Line 118 | Line 151 | int id;
151      t_next_id = t_id;
152      t_next = tri;
153  
154 <    tlist = push_data(NULL,t_id);
154 >    insertelem(del_set,t_id);
155  
156      while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id)
157      {  
# Line 137 | Line 170 | int id;
170          SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next));
171          v_next = (T_WHICH_V(t_next,id)+2)%3;
172          SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next));
173 <        tlist = push_data(tlist,t_next_id);
173 >        insertelem(del_set,t_next_id);
174      }
142 –    while(tlist)
143 –    {
144 –        t_id = (int)pop_list(&tlist);
145 –        smDelete_tri(sm,t_id);
146 –    }
175      return(elist);
176   }
177  
# Line 169 | Line 197 | LIST *l;
197        id_e0 = E_NTH_VERT(e,0);
198        id_e1 = E_NTH_VERT(e,1);
199  
200 <      smDir(sm,e0,id_e0);
201 <      smDir(sm,e1,id_e1);
202 <      if(spherical_polygon_edge_intersect(v0,v1,e0,e1))
200 >      VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm));
201 >      VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm));
202 >      if(sedge_intersect(v0,v1,e0,e1))
203          return(TRUE);
204  
205        el = LIST_NEXT(el);
# Line 284 | Line 312 | LIST **l,**lnew;
312   }
313  
314  
315 <
316 < LIST
289 < *smTriangulate_convex(sm,plist)
315 > int
316 > smTriangulate_convex(sm,plist,add_ptr)
317   SM *sm;
318 < LIST *plist;
318 > LIST *plist,**add_ptr;
319   {
320      TRI *tri;
321      int t_id,e_id0,e_id1,e_id2;
# Line 307 | Line 334 | LIST *plist;
334          v_id2 = E_NTH_VERT(e_id1,1);
335          /* form a triangle for each triple of with v0 as base of star */
336          t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri);
337 +        *add_ptr = push_data(*add_ptr,t_id);
338 +
339          /* add which pointer?*/
340  
341          lptr = LIST_NEXT(lptr);
# Line 328 | Line 357 | LIST *plist;
357          e_id0 = -e_id2;
358      }
359      free_list(plist);
360 +    return(TRUE);
361   }
362 <
363 < smTriangulate_elist(sm,plist)
362 > int
363 > smTriangulate_elist(sm,plist,add_ptr)
364   SM *sm;
365 < LIST *plist;
365 > LIST *plist,**add_ptr;
366   {
367      LIST *l,*el1;
368      FVECT v0,v1,v2;
369      int id0,id1,id2,e,id_next;
370      char flipped;
371 <    int debug = TRUE;
371 >    int done;
372  
373      l = plist;
374      
# Line 370 | Line 400 | LIST *plist;
400   #ifdef DEBUG
401            eputs("smTriangulate_elist():Unable to find convex vertex\n");
402   #endif
403 <          return;
403 >          return(FALSE);
404        }
405        /* add edge */
406        el1 = NULL;
407        /* Split edge list l into two lists: one from id1-id_next-id1,
408           and the next from id2-id_next-id2
409        */
410 <      debug = split_edge_list(id1,id_next,&l,&el1);
410 >      split_edge_list(id1,id_next,&l,&el1);
411        /* Recurse and triangulate the two edge lists */
412 <      if(debug)
413 <        debug = smTriangulate_elist(sm,l);
414 <      if(debug)
415 <        debug = smTriangulate_elist(sm,el1);
386 <
387 <      return(debug);
412 >      done = smTriangulate_elist(sm,l,add_ptr);
413 >      if(done)
414 >        done = smTriangulate_elist(sm,el1,add_ptr);
415 >      return(done);
416      }
417 <    smTriangulate_convex(sm,plist);
418 <    return(TRUE);
417 >    done = smTriangulate_convex(sm,plist,add_ptr);
418 >    return(done);
419   }
420  
421   int
422 < smTriangulate_polygon(sm,plist)
422 > smTriangulate(sm,plist,add_ptr)
423   SM *sm;
424 < LIST *plist;
424 > LIST *plist,**add_ptr;
425   {
426      int e,id_t0,id_t1,e0,e1;
427      TRI *t0,*t1;
428      int test;
429      
430 <    test = smTriangulate_elist(sm,plist,NULL);
430 >    test = smTriangulate_elist(sm,plist,add_ptr);
431  
432      if(!test)
433         return(test);
# Line 410 | Line 438 | LIST *plist;
438          if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
439          {
440   #ifdef DEBUG
441 <           eputs("smTriangulate_polygon(): Unassigned edge neighbor\n");
441 >           eputs("smTriangulate(): Unassigned edge neighbor\n");
442   #endif
443              continue;
444          }
# Line 440 | Line 468 | TRI *t;
468        return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1));
469    return(FALSE);
470   }
471 < smFix_edges(sm)
471 > smFix_edges(sm,add_list,del_set)
472     SM *sm;
473 +   LIST *add_list;
474 +   OBJECT *del_set;
475   {
476      int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next;
477      TRI *t0,*t1,*nt0,*nt1;
# Line 471 | Line 501 | smFix_edges(sm)
501          id_v2 = T_NTH_V(t0,e0_next);
502          id_p = T_NTH_V(t1,e1_next);
503  
504 <        smDir(sm,v0,id_v0);
505 <        smDir(sm,v1,id_v1);
506 <        smDir(sm,v2,id_v2);
504 >        smDir_in_cone(sm,v0,id_v0);
505 >        smDir_in_cone(sm,v1,id_v1);
506 >        smDir_in_cone(sm,v2,id_v2);
507          
508          VCOPY(p,SM_NTH_WV(sm,id_p));    
509          VSUB(p,p,SM_VIEW_CENTER(sm));
510          if(point_in_cone(p,v0,v1,v2))
511          {
512 <            smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1);
512 >           smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add_list,
513 >                            del_set);
514              
515              nt0 = SM_NTH_TRI(sm,nid_t0);
516              nt1 = SM_NTH_TRI(sm,nid_t1);
# Line 510 | Line 541 | smFix_edges(sm)
541              SET_E_NTH_TRI(e_new,1,id_t1);
542          }
543      }
544 <
544 >    smUpdate_locator(sm,add_list,del_set);
545   }
546  
547   int
# Line 519 | Line 550 | smMesh_remove_vertex(sm,id)
550     int id;
551   {
552      int tri;
553 <    LIST *elist;
553 >    LIST *elist,*add_list;
554      int cnt,debug;
555 +    OBJECT del_set[QT_MAXSET +1];
556 +    
557      /* generate list of vertices that form the boundary of the
558         star polygon formed by vertex id and all of its adjacent
559         triangles
560       */
561      eClear_edges();
562 <    elist = smVertex_star_polygon(sm,id);
562 >    QT_CLEAR_SET(del_set);
563 >    elist = smVertex_star_polygon(sm,id,del_set);
564      if(!elist)
565         return(FALSE);
566  
567 +    add_list = NULL;
568      /* Triangulate spherical polygon */
569 <    debug = smTriangulate_polygon(sm,elist);
569 >    smTriangulate(sm,elist,&add_list);
570  
571  
572      /* Fix up new triangles to be Delaunay */
573 <    if(debug)
539 <       smFix_edges(sm);
573 >    smFix_edges(sm,add_list,del_set);
574  
575      return(TRUE);
576   }

Diff Legend

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