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

Comparing ray/src/hd/sm.c (file contents):
Revision 3.1 by gwlarson, Wed Aug 19 17:45:23 1998 UTC vs.
Revision 3.5 by gwlarson, Fri Sep 11 11:52:25 1998 UTC

# Line 8 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8   *  sm.c
9   */
10   #include "standard.h"
11 –
12 – #include "object.h"
13 –
11   #include "sm_list.h"
12   #include "sm_geom.h"
13   #include "sm.h"
# Line 20 | Line 17 | SM *smMesh = NULL;
17   double smDist_sum=0;
18   int smNew_tri_cnt=0;
19  
20 + static int smBase_nbrs[4][3] =  { {3,2,1},{3,0,2},{3,1,0},{1,2,0}};
21 +
22   #ifdef TEST_DRIVER
24 – VIEW  View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0};
23   VIEW  Current_View = {0,{0,0,0},{0,0,-1},{0,1,0},60,60,0};
24   int Pick_cnt =0;
25 < int Pick_tri = -1,Picking = FALSE;
25 > int Pick_tri = -1,Picking = FALSE,Pick_samp=-1;
26   FVECT Pick_point[500],Pick_origin,Pick_dir;
27   FVECT  Pick_v0[500], Pick_v1[500], Pick_v2[500];
28   FVECT P0,P1,P2;
# Line 226 | Line 224 | smInit(n)
224   {
225    int max_vertices;
226  
229 –  sleep(10);
230 –  
227    /* If n <=0, Just clear the existing structures */
228    if(n <= 0)
229    {
# Line 260 | Line 256 | smLocator_apply_func(sm,v0,v1,v2,func,arg)
256   SM *sm;
257   FVECT v0,v1,v2;
258   int (*func)();
259 < char *arg;
259 > int *arg;
260   {
261    STREE *st;
262 <  char found;
262 >  int found;
263    FVECT p0,p1,p2;
264  
265    st = SM_LOCATOR(sm);
266  
267 <  point_on_sphere(p0,v0,SM_VIEW_CENTER(sm));
268 <  point_on_sphere(p1,v1,SM_VIEW_CENTER(sm));
269 <  point_on_sphere(p2,v2,SM_VIEW_CENTER(sm));
267 >  VSUB(p0,v0,SM_VIEW_CENTER(sm));
268 >  VSUB(p1,v1,SM_VIEW_CENTER(sm));
269 >  VSUB(p2,v2,SM_VIEW_CENTER(sm));
270  
271    found = stApply_to_tri_cells(st,p0,p1,p2,func,arg);
272  
# Line 279 | Line 275 | char *arg;
275  
276  
277   int
278 + add_tri_expand(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id)
279 + QUADTREE *qtptr;
280 + FVECT q0,q1,q2;
281 + FVECT t0,t1,t2;
282 + int n;
283 + int *arg;
284 + int t_id;
285 + {
286 +    OBJECT tset[QT_MAXSET+1],*optr;    
287 +    int i,id,found;
288 +    FVECT v0,v1,v2;
289 +
290 + #ifdef DEBUG_TEST_DRIVER
291 +    Pick_tri = t_id;
292 +    Picking = TRUE;
293 + #endif    
294 +    
295 +    if(QT_IS_EMPTY(*qtptr))
296 +    {
297 +      *qtptr = qtaddelem(*qtptr,t_id);
298 +      return(TRUE);
299 +    }
300 +    
301 +    optr = qtqueryset(*qtptr);
302 +    if(!inset(optr,t_id))
303 +    {
304 +      if(QT_SET_CNT(optr) < QT_MAXSET)
305 +        *qtptr = qtaddelem(*qtptr,t_id);
306 +      else
307 +        {
308 + #ifdef DEBUG
309 +          eputs("add_tri_expand():no room in set\n");
310 + #endif
311 +          return(FALSE);
312 +        }
313 +    }
314 +    optr = qtqueryset(*qtptr);
315 +    if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
316 +      if (n < QT_MAX_LEVELS)
317 +      {
318 +        qtgetset(tset,*qtptr);
319 +        /* If set size exceeds threshold: subdivide cell and reinsert tris*/
320 +        qtfreeleaf(*qtptr);
321 +        qtSubdivide(qtptr);
322 +
323 +        for(optr = QT_SET_PTR(tset),i=QT_SET_CNT(tset); i > 0; i--)
324 +        {
325 +          id = QT_SET_NEXT_ELEM(optr);
326 +          qtTri_from_id(id,NULL,NULL,NULL,v0,v1,v2,NULL,NULL,NULL);
327 +          found=qtAdd_tri(qtptr,q0,q1,q2,v0,v1,v2,id,n);
328 + #ifdef DEBUG
329 +          if(!found)
330 +            eputs("add_tri_expand():Reinsert\n");
331 + #endif
332 +        }
333 +        return(QT_MODIFIED);
334 +      }
335 +      else
336 +        if(QT_SET_CNT(optr) < QT_MAXSET)
337 +        {
338 + #ifdef DEBUG_TEST_DRIVER              
339 +          eputs("add_tri_expand():too many levels:can't expand\n");
340 + #endif
341 +          return(TRUE);
342 +        }
343 +        else
344 +          {
345 + #ifdef DEBUG          
346 +            eputs("add_tri_expand():too many tris inset:can't add\n");
347 + #endif
348 +            return(FALSE);
349 +          }
350 + }
351 +
352 +
353 + int
354 + add_tri(qtptr,fptr,t_id)
355 +   QUADTREE *qtptr;
356 +   int *fptr;
357 +   int t_id;
358 + {
359 +
360 +  OBJECT *optr;
361 +
362 + #ifdef DEBUG_TEST_DRIVER
363 +    Pick_tri = t_id;
364 +    Picking = TRUE;
365 + #endif    
366 +    if(QT_IS_EMPTY(*qtptr))
367 +    {
368 +        *qtptr = qtaddelem(*qtptr,t_id);
369 +        if(!QT_FLAG_FILL_TRI(*fptr))
370 +          (*fptr)++;
371 +    }
372 +    else
373 +     {
374 +       optr = qtqueryset(*qtptr);
375 +       if(!inset(optr,t_id))
376 +       {
377 +         if(QT_SET_CNT(optr) < QT_MAXSET)
378 +         {
379 +           if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
380 +             (*fptr) |= QT_EXPAND;
381 +           if(!QT_FLAG_FILL_TRI(*fptr))
382 +             (*fptr)++;
383 +           *qtptr = qtaddelem(*qtptr,t_id);
384 +         }
385 +         else
386 +           {
387 + #ifdef DEBUG_TESTDRIVER      
388 +             eputs("add_tri():exceeded set size\n");
389 + #endif
390 +             return(FALSE);
391 +           }
392 +       }
393 +     }
394 +    return(TRUE);
395 + }
396 +
397 +
398 + int
399 + stInsert_tri(st,t_id,t0,t1,t2)
400 +   STREE *st;
401 +   int t_id;
402 +   FVECT t0,t1,t2;
403 + {
404 +    int f;
405 +    FVECT dir;
406 +    
407 +  /* First add all of the leaf cells lying on the triangle perimeter:
408 +     mark all cells seen on the way
409 +   */
410 +    ST_CLEAR_FLAGS(st);
411 +    f = 0;
412 +    VSUB(dir,t1,t0);
413 +    stTrace_edge(st,t0,dir,1.0,add_tri,&f,t_id);
414 +    VSUB(dir,t2,t1);
415 +    stTrace_edge(st,t1,dir,1.0,add_tri,&f,t_id);
416 +    VSUB(dir,t0,t2);
417 +    stTrace_edge(st,t2,dir,1.0,add_tri,&f,t_id);
418 +    /* Now visit interior */
419 +    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
420 +       stVisit_tri_interior(st,t0,t1,t2,add_tri_expand,&f,t_id);
421 + }
422 +
423   smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id)
424   SM *sm;
425   int t_id;
426   int v0_id,v1_id,v2_id;  
427   {
428    STREE *st;
429 <  FVECT p0,p1,p2;
429 >  FVECT v0,v1,v2;
430    
431    st = SM_LOCATOR(sm);
432  
433 <  smDir(sm,p0,v0_id);
434 <  smDir(sm,p1,v1_id);
435 <  smDir(sm,p2,v2_id);
433 >  VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
434 >  VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
435 >  VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
436  
437 <  stAdd_tri(st,t_id,p0,p1,p2);
437 >  stUpdate_tri(st,t_id,v0,v1,v2,add_tri,add_tri_expand);
438  
298 –  return(1);
439   }
440  
441   /* Add a triangle to the base array with vertices v1-v2-v3 */
# Line 343 | Line 483 | TRI **tptr;
483      SM_NTH_VERT(sm,v1_id) = t_id;
484      SM_NTH_VERT(sm,v2_id) = t_id;
485  
346 –    /* Add triangle to the locator */
347 –    smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id);
486      if(t)
487         *tptr = t;
488      /* return initialized triangle */
# Line 385 | Line 523 | double eps;
523             }
524        }
525        else
526 <        if(d1 < d2)
526 >        if(d1 < d0)
527          {
528            if((eps < 0) ||  d1 < eps)
529            {
# Line 393 | Line 531 | double eps;
531              d = d1;
532            }
533          }
534 <      else
397 <         if((eps < 0) ||  d2 < eps)
398 <          {
399 <            closest = v2_id;
400 <            d = d2;
401 <          }
402 <  }
534 >    }
535      if(v2_id != -1)
536      {
537        smDir(sm,v,v2_id);
538        d2 = DIST(p,v);
539        if((eps < 0) ||  d2 < eps)
540 <         if(closest== -1 ||(d2 < d))
540 >         if(closest == -1 ||(d2 < d))
541               return(v2_id);
542      }
543      return(closest);
# Line 428 | Line 560 | FVECT p;
560      
561      VCOPY(v,SM_NTH_WV(sm,v1_id));
562      d1 = DIST(p,v);
563 <    if(d1 < d2)
563 >    if(d1 < d0)
564      {
565        closest = v1_id;
566        d = d1;
# Line 442 | Line 574 | FVECT p;
574   }
575  
576   void
577 < smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
577 > smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add,del)
578     SM *sm;
579     int t_id,t1_id;
580     int e,e1;
581 <   int **tn_id,**tn1_id;
581 >   int *tn_id,*tn1_id;
582 >   LIST **add,**del;
583  
584   {
585      TRI *t,*t1;
# Line 469 | Line 602 | smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
602      verts[enext] = T_NTH_V(t1,e1prev);
603      verts[eprev] = T_NTH_V(t,eprev);
604      ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta);
605 <
605 >    *add = push_data(*add,ta_id);
606      verts[e1] = T_NTH_V(t1,e1);
607      verts[e1next] = T_NTH_V(t,eprev);
608      verts[e1prev] = T_NTH_V(t1,e1prev);
609      tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb);
610 <    
610 >    *add = push_data(*add,tb_id);
611 >
612      /* set the neighbors */
613      T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
614      T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
# Line 495 | Line 629 | smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
629      T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
630  
631      /* Delete two parent triangles */
632 <    smDelete_tri(sm,t_id);
633 <    smDelete_tri(sm,t1_id);
632 >
633 >    *del = push_data(*del,t_id);
634 >    if(SM_IS_NTH_T_NEW(sm,t_id))
635 >      SM_CLEAR_NTH_T_NEW(sm,t_id);
636 >    else
637 >      SM_CLEAR_NTH_T_BASE(sm,t_id);
638 >    *del = push_data(*del,t1_id);
639 >    if(SM_IS_NTH_T_NEW(sm,t1_id))
640 >      SM_CLEAR_NTH_T_NEW(sm,t1_id);
641 >    else
642 >      SM_CLEAR_NTH_T_BASE(sm,t1_id);
643      *tn_id = ta_id;
644      *tn1_id = tb_id;
645   }
646  
647 + smUpdate_locator(sm,add_list,del_list)
648 + SM *sm;
649 + LIST *add_list,*del_list;
650 + {
651 +  int t_id;
652 +  TRI *t;
653 +  while(add_list)
654 +  {
655 +    t_id = pop_list(&add_list);
656 +    if(!SM_IS_NTH_T_NEW(sm,t_id) && !SM_IS_NTH_T_BASE(sm,t_id))
657 +    {
658 +      SM_SET_NTH_T_NEW(sm,t_id);
659 +      smNew_tri_cnt--;
660 +      continue;
661 +    }
662 +    t = SM_NTH_TRI(sm,t_id);
663 +    smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2));
664 +  }
665 +  
666 +  while(del_list)
667 +  {
668 +    t_id = pop_list(&del_list);
669 +    if(SM_IS_NTH_T_NEW(sm,t_id))
670 +    {
671 +      smDelete_tri(sm,t_id);
672 +      continue;
673 +    }
674 +    smLocator_remove_tri(sm,t_id);
675 +    smDelete_tri(sm,t_id);
676 +  }
677 + }
678   /* MUST add check for constrained edges */
679 < char
679 > int
680   smFix_tris(sm,id,tlist)
681   SM *sm;
682   int id;
683   LIST *tlist;
684   {
685      TRI *t,*t_opp;
686 <    FVECT p,p1,np,p2,p3;
687 <    int swapped = 0;
514 <    int e,e1,e_id;
515 <    char debug = 0;
686 >    FVECT p,p1,p2,p3;
687 >    int e,e1,swapped = 0;
688      int t_id,t_opp_id;
689 <    
690 <    VCOPY(p,SM_NTH_WV(sm,id));    
691 <    VSUB(p,p,SM_VIEW_CENTER(sm));
689 >    LIST *add_list,*del_list;
690 >
691 >
692 >    add_list = del_list = NULL;
693 >    VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
694      while(tlist)
695      {
696 <        t_id = (int)pop_list(&tlist);
696 >        t_id = pop_list(&tlist);
697          t = SM_NTH_TRI(sm,t_id);
698          e = (T_WHICH_V(t,id)+1)%3;
699          t_opp_id = T_NTH_NBR(t,e);
# Line 534 | Line 708 | LIST *tlist;
708              e1 = T_NTH_NBR_PTR(t_id,t_opp);
709              /* check list for t_opp and Remove if there */
710              remove_from_list(t_opp_id,&tlist);
711 <
712 <            smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id);
711 >            smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id,
712 >                             &add_list,&del_list);
713              tlist = push_data(tlist,t_id);
714              tlist = push_data(tlist,t_opp_id);
715          }
716      }
717 +    smUpdate_locator(sm,add_list,del_list);
718      return(swapped);
719   }
720  
# Line 572 | Line 747 | int id,nid;
747    
748    T_NTH_V(tri,T_WHICH_V(tri,id)) = nid;
749  
750 <  t_id = smTri_next_ccw_nbr(sm,t,nid);
751 <  while((t= SM_NTH_TRI(sm,t_id)) != tri)
750 >  t_id = smTri_next_ccw_nbr(sm,tri,nid);
751 >  while((t = SM_NTH_TRI(sm,t_id)) != tri)
752    {
753        T_NTH_V(t,T_WHICH_V(t,id)) = nid;
754        t_id = smTri_next_ccw_nbr(sm,t,nid);
# Line 599 | Line 774 | smReplace_vertex(sm,c,dir,p,tri_id,snew_id,type,which)
774     COLR c;
775     FVECT dir,p;
776     int tri_id,snew_id;
777 <   char type,which;
777 >   int type,which;
778   {
779      int n_id,s_id;
780      TRI *tri;
# Line 670 | Line 845 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
845        n_id = smClosest_vertex_in_tri(sm,t0_id,t1_id,t2_id,npt,P_REPLACE_EPS);
846      }
847      t0_id = smAdd_tri(sm,s_id,v0_id,v1_id,&t0);
848 +    /* Add triangle to the locator */
849 +    smLocator_add_tri(sm,t0_id,s_id,v0_id,v1_id);
850 +
851      t1_id = smAdd_tri(sm,s_id,v1_id,v2_id,&t1);
852 +    smLocator_add_tri(sm,t1_id,s_id,v1_id,v2_id);
853      t2_id = smAdd_tri(sm,s_id,v2_id,v0_id,&t2);
854 <        
854 >    smLocator_add_tri(sm,t2_id,s_id,v2_id,v0_id);      
855 >
856      /* Set the neighbor pointers for the new tris */
857      T_NTH_NBR(t0,0) = t2_id;
858      T_NTH_NBR(t0,1) = T_NTH_NBR(tri,0);
# Line 692 | Line 872 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
872      nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2));
873      T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id;
874          
875 +    smLocator_remove_tri(sm,tri_id);
876      smDelete_tri(sm,tri_id);
877          
878      /* Fix up the new triangles*/
# Line 709 | Line 890 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
890      
891  
892   int
893 < smPointLocate(sm,pt,type,which,norm)
893 > smPointLocate(sm,pt,norm)
894   SM *sm;
895   FVECT pt;
896 < char *type,*which;
716 < char norm;
896 > int norm;
897   {
898    STREE *st;
899    int tri;
# Line 722 | Line 902 | char norm;
902    st = SM_LOCATOR(sm);
903    if(norm)
904    {
905 <      point_on_sphere(npt,pt,SM_VIEW_CENTER(sm));
906 <      tri = stPoint_locate(st,npt,type,which);
905 >      VSUB(npt,pt,SM_VIEW_CENTER(sm));
906 >      tri = stPoint_locate(st,npt);
907    }
908    else
909 <     tri = stPoint_locate(st,pt,type,which);
909 >     tri = stPoint_locate(st,pt);
910    return(tri);
911   }
912  
913   QUADTREE
914 < smPointLocateCell(sm,pt,v0,v1,v2,type,which,norm)
914 > smPointLocateCell(sm,pt,norm,v0,v1,v2)
915   SM *sm;
916 < FVECT pt,v0,v1,v2;
917 < char *type,*which;
918 < char norm;
916 > FVECT pt;
917 > int norm;
918 > FVECT v0,v1,v2;
919   {
920    STREE *st;
921 <  QUADTREE qt;
921 >  QUADTREE *qtptr;
922    FVECT npt;
923  
924    st = SM_LOCATOR(sm);
925    if(norm)
926    {
927 <      point_on_sphere(npt,pt,SM_VIEW_CENTER(sm));
927 >      VSUB(npt,pt,SM_VIEW_CENTER(sm));
928    
929 <      qt = stPoint_locate_cell(st,npt,v0,v1,v2,type,which);
929 >      qtptr = stPoint_locate_cell(st,npt,v0,v1,v2);
930    }
931    else
932 <     qt = stPoint_locate_cell(st,pt,v0,v1,v2,type,which);
932 >     qtptr = stPoint_locate_cell(st,pt,v0,v1,v2);
933  
934 <  return(qt);
934 >  if(qtptr)
935 >    return(*qtptr);
936 >  else
937 >    return(EMPTY);
938   }
939  
940   int
# Line 762 | Line 945 | smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
945     int s_id;
946   {
947      int t_id;
765 –    char type,which;
948      double d;
949      FVECT p;
950      
# Line 773 | Line 955 | smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
955          d = DIST(pt,SM_VIEW_CENTER(smMesh));
956          smDist_sum += 1.0/d;
957          /************************************/
958 <        t_id = smPointLocate(smMesh,pt,&type,&which,TRUE);
959 <        if(type==GT_FACE)
958 >        t_id = smPointLocate(smMesh,pt,TRUE);
959 >        if(t_id >= 0)
960             s_id = smInsert_point_in_tri(smMesh,c,dir,pt,s_id,t_id);
779 –        else
780 –           if(type==GT_VERTEX)
781 –              s_id = smReplace_vertex(smMesh,c,dir,pt,t_id,s_id,type,which);
961   #ifdef DEBUG
962             else
963 <              eputs("smAdd_sample_to_mesh(): unrecognized type\n");
963 >             {
964 >               c[0] = 255;c[1]=0;c[2]=0;
965 >               s_id = smAdd_sample_point(sm,c,dir,pt);        
966 >               eputs("smAdd_sample_to_mesh(): not found fg\n");
967 >             }
968   #endif
969      }
970      else if(s_id != -1)
# Line 794 | Line 977 | smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
977              smDist_sum += 1.0/d;
978              /************************************/
979          }
980 <        t_id = smPointLocate(smMesh,p,&type,&which,TRUE);
981 <        if(type==GT_FACE)
980 >        t_id = smPointLocate(smMesh,p,TRUE);
981 >        if(t_id != -1)
982             s_id = smInsert_point_in_tri(smMesh,c,dir,p,s_id,t_id);
800 –        else
801 –           if(type==GT_VERTEX)
802 –              s_id = smReplace_vertex(smMesh,c,dir,p,t_id,s_id,type,which);
983   #ifdef DEBUG
984             else
985 <              eputs("smAdd_sample_to_mesh(): unrecognized type\n");
985 >              eputs("smAdd_sample_to_mesh():not found reinsert\n");
986   #endif
987      }
988      /* Is a BG(sky point) */
989      else
990         {
991 <           t_id = smPointLocate(smMesh,dir,&type,&which,FALSE);
992 <           if(type==GT_FACE)
991 >           t_id = smPointLocate(smMesh,dir,FALSE);
992 >           if(t_id != -1)
993                s_id = smInsert_point_in_tri(smMesh,c,dir,NULL,s_id,t_id);
994 <           else
815 <              if(type==GT_VERTEX)
816 <                 s_id = smReplace_vertex(smMesh,c,dir,NULL,t_id,s_id,type,which);
994 >
995   #ifdef DEBUG
996                else
997 <                 eputs("smAdd_sample_to_mesh(): unrecognized type\n");
997 >                 eputs("smAdd_sample_to_mesh(): not found bg\n");
998   #endif
999         }
1000      return(s_id);
# Line 841 | Line 1019 | FVECT p;
1019  
1020   {
1021      int s_id;
1022 +    int debug=0;
1023      
1024      /* First check if this the first sample: if so initialize mesh */
1025      if(SM_NUM_SAMP(smMesh) == 0)
847 – #ifdef TEST_DRIVER
848 –      smInit_mesh(smMesh,View.vp);
849 – #else
1026        smInit_mesh(smMesh,odev.v.vp);
1027 < #endif
1028 <    s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1);
853 < #if 0
854 < {
855 <  char buff[100];
856 <  sprintf(buff,"Added sample %d\n",s_id);
857 <    eputs(buff);
858 < }
859 < #endif
1027 >    if(!debug)
1028 >       s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1);
1029      return(s_id);
1030      
1031   }    
# Line 930 | Line 1099 | smCreate_base_mesh(sm,type)
1099   SM *sm;
1100   int type;
1101   {
1102 <  int i,id;
1102 >  int i,id,tri_id,nbr_id;
1103    int p[4],ids[4];
1104    int v0_id,v1_id,v2_id;
1105    TRI *tris[4];
# Line 940 | Line 1109 | int type;
1109  
1110    for(i=0; i < 4; i++)
1111    {
1112 <      VADD(cntr,stDefault_base[i],SM_VIEW_CENTER(sm));
1112 >    VCOPY(cntr,stDefault_base[i]);
1113 >    cntr[0] += .01;
1114 >    cntr[1] += .02;
1115 >    cntr[2] += .03;
1116 >      VADD(cntr,cntr,SM_VIEW_CENTER(sm));
1117        point_on_sphere(d,cntr,SM_VIEW_CENTER(sm));
1118        id = smAdd_base_vertex(sm,cntr,d);
1119      /* test to make sure vertex allocated */
# Line 957 | Line 1130 | int type;
1130      v2_id = p[stTri_verts[i][2]];
1131      if((ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&(tris[i])))== -1)
1132       return(0);
1133 +    smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id);
1134    }
1135    /* Set neighbors */
1136  
1137 <  T_NTH_NBR(tris[0],0) = ids[3];
1138 <  T_NTH_NBR(tris[0],1) = ids[2];
1139 <  T_NTH_NBR(tris[0],2) = ids[1];
1137 >  for(tri_id=0;tri_id < 4; tri_id++)
1138 >     for(nbr_id=0; nbr_id < 3; nbr_id++)
1139 >        T_NTH_NBR(tris[tri_id],nbr_id) = smBase_nbrs[tri_id][nbr_id];
1140  
967 –  T_NTH_NBR(tris[1],0) = ids[3];
968 –  T_NTH_NBR(tris[1],1) = ids[0];
969 –  T_NTH_NBR(tris[1],2) = ids[2];
970 –
971 –  T_NTH_NBR(tris[2],0) = ids[3];
972 –  T_NTH_NBR(tris[2],1) = ids[1];
973 –  T_NTH_NBR(tris[2],2) = ids[0];
974 –
975 –  T_NTH_NBR(tris[3],0) = ids[1];
976 –  T_NTH_NBR(tris[3],1) = ids[2];
977 –  T_NTH_NBR(tris[3],2) = ids[0];
1141    return(1);
1142  
1143   }
# Line 984 | Line 1147 | int
1147   smNext_tri_flag_set(sm,i,which,b)
1148       SM *sm;
1149       int i,which;
1150 <     char b;
1150 >     int b;
1151   {
1152  
1153    for(; i < SM_TRI_CNT(sm);i++)
1154    {
992 –    if(!SM_IS_NTH_T_FLAG(sm,i,which))
993 –      continue;
1155  
1156 +      if(!SM_IS_NTH_T_FLAG(sm,i,which))
1157 +         continue;
1158      if(!b)
1159        break;
1160      if((b==1) && !SM_BG_TRI(sm,i))
# Line 1018 | Line 1181 | smNext_valid_tri(sm,i)
1181  
1182  
1183  
1184 < qtTri_verts_from_id(t_id,v0,v1,v2)
1184 > qtTri_from_id(t_id,v0,v1,v2,n0,n1,n2,v0_idp,v1_idp,v2_idp)
1185   int t_id;
1186   FVECT v0,v1,v2;
1187 + FVECT n0,n1,n2;
1188 + int *v0_idp,*v1_idp,*v2_idp;
1189   {
1190    TRI *t;
1191    int v0_id,v1_id,v2_id;
# Line 1030 | Line 1195 | FVECT v0,v1,v2;
1195    v1_id = T_NTH_V(t,1);
1196    v2_id = T_NTH_V(t,2);
1197  
1198 <  smDir(smMesh,v0,v0_id);
1034 <  smDir(smMesh,v1,v1_id);
1035 <  smDir(smMesh,v2,v2_id);
1036 <
1037 < }
1038 <
1039 <
1040 < int
1041 < smIntersectTriSet(sm,t_set,orig,dir,pt)
1042 <   SM *sm;
1043 <   OBJECT *t_set;
1044 <   FVECT orig,dir,pt;
1045 < {
1046 <    OBJECT *optr;
1047 <    int i,t_id,v_id;
1048 <    TRI *tri;
1049 <    FVECT p0,p1,p2;
1050 <    char type,which;
1051 <    int p0_id,p1_id,p2_id;
1052 <    
1053 <    for(optr = QT_SET_PTR(t_set),i = QT_SET_CNT(t_set); i > 0; i--)
1054 <    {
1055 <        t_id = QT_SET_NEXT_ELEM(optr);
1056 <        tri = SM_NTH_TRI(sm,t_id);
1057 <        p0_id = T_NTH_V(tri,0);
1058 <        p1_id = T_NTH_V(tri,1);
1059 <        p2_id = T_NTH_V(tri,2);
1060 <        VCOPY(p0,SM_NTH_WV(sm,p0_id));
1061 <        VCOPY(p1,SM_NTH_WV(sm,p1_id));
1062 <        VCOPY(p2,SM_NTH_WV(sm,p2_id));
1063 <        if(type = ray_intersect_tri(orig,dir,p0,p1,p2,pt,&which))
1064 <        {
1065 <          if(type==GT_VERTEX)
1066 <            return(T_NTH_V(tri,which));
1067 <          v_id = smClosest_vertex_in_w_tri(sm,p0_id,p1_id,p2_id,pt);
1068 <          return(v_id);
1069 <        }
1070 <    }
1071 <    return(-1);
1072 < }
1073 <
1074 < /*
1075 < * int
1076 < * smTraceRay(SM *sm,FVECT orig, FVECT dir,FVECT v0,FVECT v1,FVECT v2,FVECT r)
1077 < *
1078 < *   Intersect the ray with triangle v0v1v2, return intersection point in r
1079 < *
1080 < *    Assumes orig,v0,v1,v2 are in spherical coordinates, and orig is
1081 < *    unit
1082 < */
1083 < char
1084 < smTraceRay(sm,orig,dir,v0,v1,v2,r)
1085 <  SM *sm;
1086 <  FVECT orig,dir;
1087 <  FVECT v0,v1,v2;
1088 <  FVECT r;
1089 < {
1090 <  FVECT n,p[3],d;
1091 <  double pt[3],r_eps;
1092 <  char i;
1093 <  int which;
1094 <
1095 <  /* Find the plane equation for the triangle defined by the edge v0v1 and
1096 <   the view center*/
1097 <  VCROSS(n,v0,v1);
1098 <  /* Intersect the ray with this plane */
1099 <  i = intersect_ray_plane(orig,dir,n,0.0,&(pt[0]),p[0]);
1100 <  if(i)
1101 <    which = 0;
1102 <  else
1103 <    which = -1;
1104 <
1105 <  VCROSS(n,v1,v2);
1106 <  i = intersect_ray_plane(orig,dir,n,0.0,&(pt[1]),p[1]);
1107 <  if(i)
1108 <    if((which==-1) || pt[1] < pt[0])
1109 <      which = 1;
1110 <
1111 <  VCROSS(n,v2,v0);
1112 <  i = intersect_ray_plane(orig,dir,n,0.0,&(pt[2]),p[2]);
1113 <  if(i)
1114 <    if((which==-1) || pt[2] < pt[which])
1115 <      which = 2;
1116 <
1117 <  if(which != -1)
1198 >  if(v0)
1199    {
1200 <      /* Return point that is K*eps along projection of the ray on
1201 <         the sphere to push intersection point p[which] into next cell
1202 <      */
1122 <      normalize(p[which]);
1123 <      /* Calculate the ray perpendicular to the intersection point: approx
1124 <       the direction moved along the sphere a distance of K*epsilon*/
1125 <      r_eps = -DOT(p[which],dir);
1126 <      VSUM(n,dir,p[which],r_eps);
1127 <     /* Calculate the length along ray p[which]-dir needed to move to
1128 <         cause a move along the sphere of k*epsilon
1129 <       */
1130 <       r_eps = DOT(n,dir);
1131 <      VSUM(r,p[which],dir,(20*FTINY)/r_eps);
1132 <      normalize(r);
1133 <      return(TRUE);
1200 >      VCOPY(v0,SM_NTH_WV(smMesh,v0_id));
1201 >      VCOPY(v1,SM_NTH_WV(smMesh,v1_id));
1202 >      VCOPY(v2,SM_NTH_WV(smMesh,v2_id));
1203    }
1204 <  else
1204 >  if(n0)
1205    {
1206 <      /* Unable to find intersection: move along ray and try again */
1207 <      r_eps = -DOT(orig,dir);
1208 <      VSUM(n,dir,orig,r_eps);
1209 <      r_eps = DOT(n,dir);
1141 <      VSUM(r,orig,dir,(20*FTINY)/r_eps);
1142 <      normalize(r);
1143 < #ifdef DEBUG
1144 <      eputs("smTraceRay:Ray does not intersect triangle");
1145 < #endif
1146 <      return(FALSE);
1206 >      smDir(smMesh,n0,v0_id);
1207 >      smDir(smMesh,n1,v1_id);
1208 >      smDir(smMesh,n2,v2_id);
1209 >
1210    }
1211 +  if(v0_idp)
1212 +     {
1213 +         *v0_idp = v0_id;
1214 +         *v1_idp = v1_id;
1215 +         *v2_idp = v2_id;
1216 +     }
1217   }
1218  
1219  
# Line 1160 | Line 1229 | smFindSamp(orig,dir)
1229   FVECT orig,dir;
1230   {
1231    FVECT r,v0,v1,v2,a,b,p;
1232 <  OBJECT os[MAXCSET+1],t_set[MAXSET+1];
1232 >  OBJECT os[QT_MAXCSET+1],t_set[QT_MAXSET+1],*ts;
1233    QUADTREE qt;
1234    int s_id;
1235    double d;
# Line 1184 | Line 1253 | FVECT orig,dir;
1253    d = -DOT(b,dir);
1254    if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0))
1255    {
1256 <      qt = smPointLocateCell(smMesh,dir,v0,v1,v2,NULL,NULL,FALSE);
1256 >      qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL);
1257        /* Test triangles in the set for intersection with Ray:returns
1258           first found
1259        */
1260 <      qtgetset(t_set,qt);
1261 <      s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p);
1262 < #ifdef TEST_DRIVER
1260 >      ts = qtqueryset(qt);
1261 >      s_id = intersect_tri_set(ts,orig,dir,p);
1262 > #ifdef DEBUG_TEST_DRIVER
1263        VCOPY(Pick_point[0],p);
1264   #endif
1265        return(s_id);
# Line 1199 | Line 1268 | FVECT orig,dir;
1268    {
1269        /* Starting with orig, Walk along projection of ray onto sphere */
1270        point_on_sphere(r,orig,SM_VIEW_CENTER(smMesh));
1271 <      qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE);
1203 <      qtgetset(t_set,qt);
1271 >      qt = smPointLocateCell(smMesh,r,FALSE,v0,v1,v2);
1272        /* os will contain all triangles seen thus far */
1273 +      qtgetset(t_set,qt);
1274        setcopy(os,t_set);
1275  
1276        /* Calculate ray perpendicular to dir: when projection ray is // to dir,
# Line 1211 | Line 1280 | FVECT orig,dir;
1280        d = DOT(a,b);
1281        while(d > 0)
1282        {
1283 <          s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p);
1284 < #ifdef TEST_DRIVER
1283 >          s_id = intersect_tri_set(t_set,orig,dir,p);
1284 > #ifdef DEBUG_TEST_DRIVER
1285            VCOPY(Pick_point[0],p);
1286   #endif    
1287            if(s_id != EMPTY)
1288                 return(s_id);
1289            /* Find next cell that projection of ray intersects */
1290 <          smTraceRay(smMesh,r,dir,v0,v1,v2,r);
1291 <          qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE);
1290 >          traceRay(r,dir,v0,v1,v2,r);
1291 >          qt = smPointLocateCell(smMesh,r,FALSE,v0,v1,v2);
1292            qtgetset(t_set,qt);
1293            /* Check triangles in set against those seen so far(os):only
1294               check new triangles for intersection (t_set')
1295            */
1296            check_set(t_set,os);
1297 <          d = DOT(a,r);
1297 >          d = DOT(a,r);
1298        }
1299      }
1300 < #ifdef DEBUG  
1300 > #ifdef DEBUG
1301    eputs("smFindSamp():Pick Ray did not intersect mesh");
1302   #endif
1303    return(EMPTY);
1304   }
1305    
1306  
1307 < smRebuild_mesh(sm,vptr)
1307 > smRebuild_mesh(sm,vp)
1308     SM *sm;
1309 <   VIEW *vptr;
1309 >   FVECT vp;
1310   {
1311      int i;
1312      FVECT dir;
# Line 1245 | Line 1314 | smRebuild_mesh(sm,vptr)
1314      FVECT p,ov;
1315  
1316      /* Clear the mesh- and rebuild using the current sample array */
1248 – #ifdef TEST_DRIVER
1249 –    View = *vptr;
1250 – #endif    
1317  
1318 <    VSUB(ov,vptr->vp,SM_VIEW_CENTER(sm));
1319 <    smInit_mesh(sm,vptr->vp);
1318 >    VSUB(ov,vp,SM_VIEW_CENTER(sm));
1319 >    smInit_mesh(sm,vp);
1320      
1321      SM_FOR_ALL_SAMPLES(sm,i)
1322      {
# Line 1259 | Line 1325 | smRebuild_mesh(sm,vptr)
1325          smAdd_sample_to_mesh(sm,NULL,NULL,NULL,i);      
1326      }
1327   }
1328 +
1329 + int
1330 + intersect_tri_set(t_set,orig,dir,pt)
1331 +   OBJECT *t_set;
1332 +   FVECT orig,dir,pt;
1333 + {
1334 +    OBJECT *optr;
1335 +    int i,t_id,id;
1336 +    int pid0,pid1,pid2;
1337 +    FVECT p0,p1,p2,p;
1338 +    TRI *t;
1339 +    
1340 +    optr = QT_SET_PTR(t_set);
1341 +    for(i = QT_SET_CNT(t_set); i > 0; i--)
1342 +    {
1343 +        t_id = QT_SET_NEXT_ELEM(optr);
1344 +
1345 +        t = SM_NTH_TRI(smMesh,t_id);
1346 +        pid0 = T_NTH_V(t,0);
1347 +        pid1 = T_NTH_V(t,1);
1348 +        pid2 = T_NTH_V(t,2);
1349 +        VCOPY(p0,SM_NTH_WV(smMesh,pid0));
1350 +        VCOPY(p1,SM_NTH_WV(smMesh,pid1));
1351 +        VCOPY(p2,SM_NTH_WV(smMesh,pid2));
1352 +        if(ray_intersect_tri(orig,dir,p0,p1,p2,p))
1353 +        {
1354 +          id = closest_point_in_tri(p0,p1,p2,p,pid0,pid1,pid2);
1355 +
1356 +          if(pt)
1357 +             VCOPY(pt,p);
1358 + #ifdef DEBUG_TEST_DRIVER
1359 +          Pick_tri = t_id;
1360 +          Pick_samp = id;
1361 +          VCOPY(Pick_point[0],p);
1362 + #endif
1363 +          return(id);
1364 +        }
1365 +    }
1366 +    return(-1);
1367 + }
1368 +
1369 + int
1370 + ray_trace_check_set(qtptr,orig,dir,tptr,os)
1371 +   QUADTREE *qtptr;
1372 +   FVECT orig,dir;
1373 +   int *tptr;
1374 +   OBJECT *os;
1375 + {
1376 +    OBJECT tset[QT_MAXSET+1];  
1377 +    double dt,t;
1378 +    int found;
1379 +    FVECT o;
1380 +    
1381 +
1382 +    if(!QT_IS_EMPTY(*qtptr))
1383 +     {
1384 +         VADD(o,orig,SM_VIEW_CENTER(smMesh));
1385 +         qtgetset(tset,*qtptr);
1386 +         /* Check triangles in set against those seen so far(os):only
1387 +            check new triangles for intersection (t_set')
1388 +            */
1389 +         check_set(tset,os);
1390 +         if((found = intersect_tri_set(tset,o,dir,NULL))!= -1)
1391 +         {
1392 +             *tptr = found;
1393 +             return(QT_DONE);
1394 +         }
1395 +       }
1396 +    return(FALSE);
1397 + }
1398 +
1399 + int
1400 + smFindSamp_opt(orig,dir)
1401 + FVECT orig,dir;
1402 + {
1403 +  FVECT b,p,o;
1404 +  OBJECT *ts;
1405 +  QUADTREE qt;
1406 +  int s_id;
1407 +  double d;
1408 +
1409 + /*  r is the normalized vector from the view center to the current
1410 +  *  ray point ( starting with "orig"). Find the cell that r falls in,
1411 +  *  and test the ray against all triangles stored in the cell. If
1412 +  *  the test fails, trace the projection of the ray across to the
1413 +  *  next cell it intersects: iterate until either an intersection
1414 +  *  is found, or the projection ray is // to the direction. The sample
1415 +  *  corresponding to the triangle vertex closest to the intersection
1416 +  *  point is returned.
1417 +  */
1418 +  
1419 +  /* First test if "orig" coincides with the View_center or if "dir" is
1420 +     parallel to r formed by projecting "orig" on the sphere. In
1421 +     either case, do a single test against the cell containing the
1422 +     intersection of "dir" and the sphere
1423 +   */
1424 +  /* orig will be updated-so preserve original value */
1425 +  if(!smMesh)
1426 +     return;
1427 +  point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh));
1428 +  d = -DOT(b,dir);
1429 +  if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0))
1430 +  {
1431 +      qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL);
1432 +      /* Test triangles in the set for intersection with Ray:returns
1433 +         first found
1434 +      */
1435 +      ts = qtqueryset(qt);
1436 +      s_id = intersect_tri_set(ts,orig,dir,p);
1437 + #ifdef DEBUG_TEST_DRIVER
1438 +      VCOPY(Pick_point[0],p);
1439 + #endif
1440 +  }
1441 +  else
1442 +  {
1443 +    OBJECT t_set[QT_MAXCSET+1];
1444 +    /* Test each of the root triangles against point id */
1445 +    QT_CLEAR_SET(t_set);
1446 +    VSUB(o,orig,SM_VIEW_CENTER(smMesh));
1447 +    ST_CLEAR_FLAGS(SM_LOCATOR(smMesh));
1448 +    s_id=stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&s_id,t_set);
1449 + }    
1450 +  return(s_id);
1451 + }
1452 +
1453 +
1454 +
1455 +
1456 +
1457 +
1458 +
1459 +
1460 +
1461 +
1462  
1463  

Diff Legend

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