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.6 by gwlarson, Mon Sep 14 10:33:46 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 +    TRI *tri;
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 +          tri = SM_NTH_TRI(smMesh,id);
327 +          VSUB(v0,SM_T_NTH_WV(smMesh,tri,0),SM_VIEW_CENTER(smMesh));
328 +          VSUB(v1,SM_T_NTH_WV(smMesh,tri,1),SM_VIEW_CENTER(smMesh));
329 +          VSUB(v2,SM_T_NTH_WV(smMesh,tri,2),SM_VIEW_CENTER(smMesh));
330 +          found = qtAdd_tri(qtptr,q0,q1,q2,v0,v1,v2,id,n);
331 + #ifdef DEBUG
332 +          if(!found)
333 +            eputs("add_tri_expand():Reinsert\n");
334 + #endif
335 +        }
336 +        return(QT_MODIFIED);
337 +      }
338 +      else
339 +        if(QT_SET_CNT(optr) < QT_MAXSET)
340 +        {
341 + #ifdef DEBUG_TEST_DRIVER              
342 +          eputs("add_tri_expand():too many levels:can't expand\n");
343 + #endif
344 +          return(TRUE);
345 +        }
346 +        else
347 +          {
348 + #ifdef DEBUG          
349 +            eputs("add_tri_expand():too many tris inset:can't add\n");
350 + #endif
351 +            return(FALSE);
352 +          }
353 + }
354 +
355 +
356 + int
357 + add_tri(qtptr,fptr,t_id)
358 +   QUADTREE *qtptr;
359 +   int *fptr;
360 +   int t_id;
361 + {
362 +
363 +  OBJECT *optr;
364 +
365 + #ifdef DEBUG_TEST_DRIVER
366 +    Pick_tri = t_id;
367 +    Picking = TRUE;
368 + #endif    
369 +    if(QT_IS_EMPTY(*qtptr))
370 +    {
371 +        *qtptr = qtaddelem(*qtptr,t_id);
372 +        if(!QT_FLAG_FILL_TRI(*fptr))
373 +          (*fptr)++;
374 +    }
375 +    else
376 +     {
377 +       optr = qtqueryset(*qtptr);
378 +       if(!inset(optr,t_id))
379 +       {
380 +         if(QT_SET_CNT(optr) < QT_MAXSET)
381 +         {
382 +           if(QT_SET_CNT(optr) >= QT_SET_THRESHOLD)
383 +             (*fptr) |= QT_EXPAND;
384 +           if(!QT_FLAG_FILL_TRI(*fptr))
385 +             (*fptr)++;
386 +           *qtptr = qtaddelem(*qtptr,t_id);
387 +         }
388 +         else
389 +           {
390 + #ifdef DEBUG_TESTDRIVER      
391 +             eputs("add_tri():exceeded set size\n");
392 + #endif
393 +             return(FALSE);
394 +           }
395 +       }
396 +     }
397 +    return(TRUE);
398 + }
399 +
400 +
401 + int
402 + stInsert_tri(st,t_id,t0,t1,t2)
403 +   STREE *st;
404 +   int t_id;
405 +   FVECT t0,t1,t2;
406 + {
407 +    int f;
408 +    FVECT dir;
409 +    
410 +  /* First add all of the leaf cells lying on the triangle perimeter:
411 +     mark all cells seen on the way
412 +   */
413 +    ST_CLEAR_FLAGS(st);
414 +    f = 0;
415 +    VSUB(dir,t1,t0);
416 +    stTrace_edge(st,t0,dir,1.0,add_tri,&f,t_id);
417 +    VSUB(dir,t2,t1);
418 +    stTrace_edge(st,t1,dir,1.0,add_tri,&f,t_id);
419 +    VSUB(dir,t0,t2);
420 +    stTrace_edge(st,t2,dir,1.0,add_tri,&f,t_id);
421 +    /* Now visit interior */
422 +    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
423 +       stVisit_tri_interior(st,t0,t1,t2,add_tri_expand,&f,t_id);
424 + }
425 +
426   smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id)
427   SM *sm;
428   int t_id;
429   int v0_id,v1_id,v2_id;  
430   {
431    STREE *st;
432 <  FVECT p0,p1,p2;
432 >  FVECT v0,v1,v2;
433    
434    st = SM_LOCATOR(sm);
435  
436 <  smDir(sm,p0,v0_id);
437 <  smDir(sm,p1,v1_id);
438 <  smDir(sm,p2,v2_id);
436 >  VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
437 >  VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
438 >  VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
439  
440 <  stAdd_tri(st,t_id,p0,p1,p2);
440 >  stUpdate_tri(st,t_id,v0,v1,v2,add_tri,add_tri_expand);
441  
298 –  return(1);
442   }
443  
444   /* Add a triangle to the base array with vertices v1-v2-v3 */
# Line 343 | Line 486 | TRI **tptr;
486      SM_NTH_VERT(sm,v1_id) = t_id;
487      SM_NTH_VERT(sm,v2_id) = t_id;
488  
346 –    /* Add triangle to the locator */
347 –    smLocator_add_tri(sm,t_id,v0_id,v1_id,v2_id);
489      if(t)
490         *tptr = t;
491      /* return initialized triangle */
# Line 385 | Line 526 | double eps;
526             }
527        }
528        else
529 <        if(d1 < d2)
529 >        if(d1 < d0)
530          {
531            if((eps < 0) ||  d1 < eps)
532            {
# Line 393 | Line 534 | double eps;
534              d = d1;
535            }
536          }
537 <      else
397 <         if((eps < 0) ||  d2 < eps)
398 <          {
399 <            closest = v2_id;
400 <            d = d2;
401 <          }
402 <  }
537 >    }
538      if(v2_id != -1)
539      {
540        smDir(sm,v,v2_id);
541        d2 = DIST(p,v);
542        if((eps < 0) ||  d2 < eps)
543 <         if(closest== -1 ||(d2 < d))
543 >         if(closest == -1 ||(d2 < d))
544               return(v2_id);
545      }
546      return(closest);
# Line 428 | Line 563 | FVECT p;
563      
564      VCOPY(v,SM_NTH_WV(sm,v1_id));
565      d1 = DIST(p,v);
566 <    if(d1 < d2)
566 >    if(d1 < d0)
567      {
568        closest = v1_id;
569        d = d1;
# Line 442 | Line 577 | FVECT p;
577   }
578  
579   void
580 < smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
580 > smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id,add,del)
581     SM *sm;
582     int t_id,t1_id;
583     int e,e1;
584 <   int **tn_id,**tn1_id;
584 >   int *tn_id,*tn1_id;
585 >   LIST **add,**del;
586  
587   {
588      TRI *t,*t1;
# Line 469 | Line 605 | smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
605      verts[enext] = T_NTH_V(t1,e1prev);
606      verts[eprev] = T_NTH_V(t,eprev);
607      ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta);
608 <
608 >    *add = push_data(*add,ta_id);
609      verts[e1] = T_NTH_V(t1,e1);
610      verts[e1next] = T_NTH_V(t,eprev);
611      verts[e1prev] = T_NTH_V(t1,e1prev);
612      tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb);
613 <    
613 >    *add = push_data(*add,tb_id);
614 >
615      /* set the neighbors */
616      T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
617      T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
# Line 495 | Line 632 | smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
632      T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
633  
634      /* Delete two parent triangles */
635 <    smDelete_tri(sm,t_id);
636 <    smDelete_tri(sm,t1_id);
635 >
636 >    *del = push_data(*del,t_id);
637 >    T_VALID_FLAG(t) = -1;
638 >    *del = push_data(*del,t1_id);
639 >    T_VALID_FLAG(t1) = -1;
640      *tn_id = ta_id;
641      *tn1_id = tb_id;
642   }
643  
644 + smUpdate_locator(sm,add_list,del_list)
645 + SM *sm;
646 + LIST *add_list,*del_list;
647 + {
648 +  int t_id;
649 +  TRI *t;
650 +  while(add_list)
651 +  {
652 +    t_id = pop_list(&add_list);
653 +    t = SM_NTH_TRI(sm,t_id);
654 +    if(!T_IS_VALID(t))
655 +    {
656 +      T_VALID_FLAG(t) = 1;
657 +      continue;
658 +    }
659 +    smLocator_add_tri(sm,t_id,T_NTH_V(t,0),T_NTH_V(t,1),T_NTH_V(t,2));
660 +  }
661 +  
662 +  while(del_list)
663 +  {
664 +    t_id = pop_list(&del_list);
665 +    t = SM_NTH_TRI(sm,t_id);
666 +    if(!T_IS_VALID(t))
667 +    {
668 +      smLocator_remove_tri(sm,t_id);
669 +    }
670 +    smDelete_tri(sm,t_id);
671 +  }
672 + }
673   /* MUST add check for constrained edges */
674 < char
675 < smFix_tris(sm,id,tlist)
674 > int
675 > smFix_tris(sm,id,tlist,add_list,del_list)
676   SM *sm;
677   int id;
678   LIST *tlist;
679 + LIST *add_list,*del_list;
680   {
681      TRI *t,*t_opp;
682 <    FVECT p,p1,np,p2,p3;
683 <    int swapped = 0;
514 <    int e,e1,e_id;
515 <    char debug = 0;
682 >    FVECT p,p1,p2,p3;
683 >    int e,e1,swapped = 0;
684      int t_id,t_opp_id;
685 <    
686 <    VCOPY(p,SM_NTH_WV(sm,id));    
687 <    VSUB(p,p,SM_VIEW_CENTER(sm));
685 >
686 >
687 >    VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
688      while(tlist)
689      {
690 <        t_id = (int)pop_list(&tlist);
690 >        t_id = pop_list(&tlist);
691          t = SM_NTH_TRI(sm,t_id);
692          e = (T_WHICH_V(t,id)+1)%3;
693          t_opp_id = T_NTH_NBR(t,e);
694          t_opp = SM_NTH_TRI(sm,t_opp_id);
695 <
695 >        /*
696 >        VSUB(p1,SM_T_NTH_WV(sm,t_opp,0),SM_VIEW_CENTER(sm));
697 >        VSUB(p2,SM_T_NTH_WV(sm,t_opp,1),SM_VIEW_CENTER(sm));
698 >        VSUB(p3,SM_T_NTH_WV(sm,t_opp,2),SM_VIEW_CENTER(sm));
699 >        */
700          smDir(sm,p1,T_NTH_V(t_opp,0));
701          smDir(sm,p2,T_NTH_V(t_opp,1));
702          smDir(sm,p3,T_NTH_V(t_opp,2));
# Line 534 | Line 706 | LIST *tlist;
706              e1 = T_NTH_NBR_PTR(t_id,t_opp);
707              /* check list for t_opp and Remove if there */
708              remove_from_list(t_opp_id,&tlist);
709 <
710 <            smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id);
709 >            smTris_swap_edge(sm,t_id,t_opp_id,e,e1,&t_id,&t_opp_id,
710 >                             &add_list,&del_list);
711              tlist = push_data(tlist,t_id);
712              tlist = push_data(tlist,t_opp_id);
713          }
714      }
715 +    smUpdate_locator(sm,add_list,del_list);
716      return(swapped);
717   }
718  
# Line 572 | Line 745 | int id,nid;
745    
746    T_NTH_V(tri,T_WHICH_V(tri,id)) = nid;
747  
748 <  t_id = smTri_next_ccw_nbr(sm,t,nid);
749 <  while((t= SM_NTH_TRI(sm,t_id)) != tri)
748 >  t_id = smTri_next_ccw_nbr(sm,tri,nid);
749 >  while((t = SM_NTH_TRI(sm,t_id)) != tri)
750    {
751        T_NTH_V(t,T_WHICH_V(t,id)) = nid;
752        t_id = smTri_next_ccw_nbr(sm,t,nid);
# Line 599 | Line 772 | smReplace_vertex(sm,c,dir,p,tri_id,snew_id,type,which)
772     COLR c;
773     FVECT dir,p;
774     int tri_id,snew_id;
775 <   char type,which;
775 >   int type,which;
776   {
777      int n_id,s_id;
778      TRI *tri;
# Line 648 | Line 821 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
821      TRI *tri,*t0,*t1,*t2,*nbr;
822      int v0_id,v1_id,v2_id,n_id;
823      int t0_id,t1_id,t2_id;
824 <    LIST *tlist;
824 >    LIST *tlist,*add_list,*del_list;
825      FVECT npt;
826  
827 +    add_list = del_list = NULL;
828      if(s_id == SM_INVALID)
829         s_id = smAdd_sample_point(sm,c,dir,p);
830      
# Line 670 | Line 844 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
844        n_id = smClosest_vertex_in_tri(sm,t0_id,t1_id,t2_id,npt,P_REPLACE_EPS);
845      }
846      t0_id = smAdd_tri(sm,s_id,v0_id,v1_id,&t0);
847 +    /* Add triangle to the locator */
848 +    
849 +    add_list = push_data(add_list,t0_id);
850 +
851      t1_id = smAdd_tri(sm,s_id,v1_id,v2_id,&t1);
852 +    add_list = push_data(add_list,t1_id);
853 +
854      t2_id = smAdd_tri(sm,s_id,v2_id,v0_id,&t2);
855 <        
855 >    add_list = push_data(add_list,t2_id);
856 >
857      /* Set the neighbor pointers for the new tris */
858      T_NTH_NBR(t0,0) = t2_id;
859      T_NTH_NBR(t0,1) = T_NTH_NBR(tri,0);
# Line 692 | Line 873 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
873      nbr = SM_NTH_TRI(sm,T_NTH_NBR(tri,2));
874      T_NTH_NBR(nbr,T_NTH_NBR_PTR(tri_id,nbr)) = t2_id;
875          
876 <    smDelete_tri(sm,tri_id);
877 <        
876 >    del_list = push_data(del_list,tri_id);
877 >    T_VALID_FLAG(tri) = -1;
878 >
879      /* Fix up the new triangles*/
880      tlist = push_data(NULL,t0_id);
881      tlist = push_data(tlist,t1_id);
882      tlist = push_data(tlist,t2_id);
883  
884 <    smFix_tris(sm,s_id,tlist);
884 >    smFix_tris(sm,s_id,tlist,add_list,del_list);
885  
886      if(n_id != -1)
887         smDelete_point(sm,n_id);
# Line 709 | Line 891 | smInsert_point_in_tri(sm,c,dir,p,s_id,tri_id)
891      
892  
893   int
894 < smPointLocate(sm,pt,type,which,norm)
894 > smPointLocate(sm,pt,norm)
895   SM *sm;
896   FVECT pt;
897 < char *type,*which;
716 < char norm;
897 > int norm;
898   {
899    STREE *st;
900    int tri;
# Line 722 | Line 903 | char norm;
903    st = SM_LOCATOR(sm);
904    if(norm)
905    {
906 <      point_on_sphere(npt,pt,SM_VIEW_CENTER(sm));
907 <      tri = stPoint_locate(st,npt,type,which);
906 >      VSUB(npt,pt,SM_VIEW_CENTER(sm));
907 >      tri = stPoint_locate(st,npt);
908    }
909    else
910 <     tri = stPoint_locate(st,pt,type,which);
910 >     tri = stPoint_locate(st,pt);
911    return(tri);
912   }
913  
914   QUADTREE
915 < smPointLocateCell(sm,pt,v0,v1,v2,type,which,norm)
915 > smPointLocateCell(sm,pt,norm,v0,v1,v2)
916   SM *sm;
917 < FVECT pt,v0,v1,v2;
918 < char *type,*which;
919 < char norm;
917 > FVECT pt;
918 > int norm;
919 > FVECT v0,v1,v2;
920   {
921    STREE *st;
922 <  QUADTREE qt;
922 >  QUADTREE *qtptr;
923    FVECT npt;
924  
925    st = SM_LOCATOR(sm);
926    if(norm)
927    {
928 <      point_on_sphere(npt,pt,SM_VIEW_CENTER(sm));
928 >      VSUB(npt,pt,SM_VIEW_CENTER(sm));
929    
930 <      qt = stPoint_locate_cell(st,npt,v0,v1,v2,type,which);
930 >      qtptr = stPoint_locate_cell(st,npt,v0,v1,v2);
931    }
932    else
933 <     qt = stPoint_locate_cell(st,pt,v0,v1,v2,type,which);
933 >     qtptr = stPoint_locate_cell(st,pt,v0,v1,v2);
934  
935 <  return(qt);
935 >  if(qtptr)
936 >    return(*qtptr);
937 >  else
938 >    return(EMPTY);
939   }
940  
941   int
# Line 762 | Line 946 | smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
946     int s_id;
947   {
948      int t_id;
765 –    char type,which;
949      double d;
950      FVECT p;
951      
# Line 773 | Line 956 | smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
956          d = DIST(pt,SM_VIEW_CENTER(smMesh));
957          smDist_sum += 1.0/d;
958          /************************************/
959 <        t_id = smPointLocate(smMesh,pt,&type,&which,TRUE);
960 <        if(type==GT_FACE)
959 >        t_id = smPointLocate(smMesh,pt,TRUE);
960 >        if(t_id >= 0)
961             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);
962   #ifdef DEBUG
963             else
964 <              eputs("smAdd_sample_to_mesh(): unrecognized type\n");
964 >             {
965 >               c[0] = 255;c[1]=0;c[2]=0;
966 >               s_id = smAdd_sample_point(sm,c,dir,pt);        
967 >               eputs("smAdd_sample_to_mesh(): not found fg\n");
968 >             }
969   #endif
970      }
971      else if(s_id != -1)
# Line 794 | Line 978 | smAdd_sample_to_mesh(sm,c,dir,pt,s_id)
978              smDist_sum += 1.0/d;
979              /************************************/
980          }
981 <        t_id = smPointLocate(smMesh,p,&type,&which,TRUE);
982 <        if(type==GT_FACE)
981 >        t_id = smPointLocate(smMesh,p,TRUE);
982 >        if(t_id != -1)
983             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);
984   #ifdef DEBUG
985             else
986 <              eputs("smAdd_sample_to_mesh(): unrecognized type\n");
986 >              eputs("smAdd_sample_to_mesh():not found reinsert\n");
987   #endif
988      }
989      /* Is a BG(sky point) */
990      else
991         {
992 <           t_id = smPointLocate(smMesh,dir,&type,&which,FALSE);
993 <           if(type==GT_FACE)
992 >           t_id = smPointLocate(smMesh,dir,FALSE);
993 >           if(t_id != -1)
994                s_id = smInsert_point_in_tri(smMesh,c,dir,NULL,s_id,t_id);
995 <           else
815 <              if(type==GT_VERTEX)
816 <                 s_id = smReplace_vertex(smMesh,c,dir,NULL,t_id,s_id,type,which);
995 >
996   #ifdef DEBUG
997                else
998 <                 eputs("smAdd_sample_to_mesh(): unrecognized type\n");
998 >                 eputs("smAdd_sample_to_mesh(): not found bg\n");
999   #endif
1000         }
1001      return(s_id);
# Line 841 | Line 1020 | FVECT p;
1020  
1021   {
1022      int s_id;
1023 +    int debug=0;
1024      
1025      /* First check if this the first sample: if so initialize mesh */
1026      if(SM_NUM_SAMP(smMesh) == 0)
847 – #ifdef TEST_DRIVER
848 –      smInit_mesh(smMesh,View.vp);
849 – #else
1027        smInit_mesh(smMesh,odev.v.vp);
1028 < #endif
1029 <    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
1028 >    if(!debug)
1029 >       s_id = smAdd_sample_to_mesh(smMesh,c,dir,p,-1);
1030      return(s_id);
1031      
1032   }    
# Line 930 | Line 1100 | smCreate_base_mesh(sm,type)
1100   SM *sm;
1101   int type;
1102   {
1103 <  int i,id;
1103 >  int i,id,tri_id,nbr_id;
1104    int p[4],ids[4];
1105    int v0_id,v1_id,v2_id;
1106    TRI *tris[4];
# Line 940 | Line 1110 | int type;
1110  
1111    for(i=0; i < 4; i++)
1112    {
1113 <      VADD(cntr,stDefault_base[i],SM_VIEW_CENTER(sm));
1114 <      point_on_sphere(d,cntr,SM_VIEW_CENTER(sm));
1115 <      id = smAdd_base_vertex(sm,cntr,d);
1113 >    VCOPY(cntr,stDefault_base[i]);
1114 >    cntr[0] += .01;
1115 >    cntr[1] += .02;
1116 >    cntr[2] += .03;
1117 >    VADD(cntr,cntr,SM_VIEW_CENTER(sm));
1118 >    /* WONT use dir */
1119 >    point_on_sphere(d,cntr,SM_VIEW_CENTER(sm));
1120 >    id = smAdd_base_vertex(sm,cntr,d);
1121      /* test to make sure vertex allocated */
1122      if(id != -1)
1123        p[i] = id;
# Line 957 | Line 1132 | int type;
1132      v2_id = p[stTri_verts[i][2]];
1133      if((ids[i] = smAdd_tri(sm, v0_id,v1_id,v2_id,&(tris[i])))== -1)
1134       return(0);
1135 +    smLocator_add_tri(sm,ids[i],v0_id,v1_id,v2_id);
1136    }
1137    /* Set neighbors */
1138  
1139 <  T_NTH_NBR(tris[0],0) = ids[3];
1140 <  T_NTH_NBR(tris[0],1) = ids[2];
1141 <  T_NTH_NBR(tris[0],2) = ids[1];
1139 >  for(tri_id=0;tri_id < 4; tri_id++)
1140 >     for(nbr_id=0; nbr_id < 3; nbr_id++)
1141 >        T_NTH_NBR(tris[tri_id],nbr_id) = smBase_nbrs[tri_id][nbr_id];
1142  
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];
1143    return(1);
1144  
1145   }
# Line 984 | Line 1149 | int
1149   smNext_tri_flag_set(sm,i,which,b)
1150       SM *sm;
1151       int i,which;
1152 <     char b;
1152 >     int b;
1153   {
1154  
1155    for(; i < SM_TRI_CNT(sm);i++)
1156    {
992 –    if(!SM_IS_NTH_T_FLAG(sm,i,which))
993 –      continue;
1157  
1158 +      if(!SM_IS_NTH_T_FLAG(sm,i,which))
1159 +         continue;
1160      if(!b)
1161        break;
1162      if((b==1) && !SM_BG_TRI(sm,i))
# Line 1018 | Line 1183 | smNext_valid_tri(sm,i)
1183  
1184  
1185  
1186 < qtTri_verts_from_id(t_id,v0,v1,v2)
1186 > qtTri_from_id(t_id,v0,v1,v2,n0,n1,n2,v0_idp,v1_idp,v2_idp)
1187   int t_id;
1188   FVECT v0,v1,v2;
1189 + FVECT n0,n1,n2;
1190 + int *v0_idp,*v1_idp,*v2_idp;
1191   {
1192    TRI *t;
1193    int v0_id,v1_id,v2_id;
# Line 1030 | Line 1197 | FVECT v0,v1,v2;
1197    v1_id = T_NTH_V(t,1);
1198    v2_id = T_NTH_V(t,2);
1199  
1200 <  smDir(smMesh,v0,v0_id);
1201 <  smDir(smMesh,v1,v1_id);
1202 <  smDir(smMesh,v2,v2_id);
1200 >  if(v0)
1201 >  {
1202 >      VCOPY(v0,SM_NTH_WV(smMesh,v0_id));
1203 >      VCOPY(v1,SM_NTH_WV(smMesh,v1_id));
1204 >      VCOPY(v2,SM_NTH_WV(smMesh,v2_id));
1205 >  }
1206 >  if(n0)
1207 >  {
1208 >      smDir(smMesh,n0,v0_id);
1209 >      smDir(smMesh,n1,v1_id);
1210 >      smDir(smMesh,n2,v2_id);
1211  
1212 < }
1212 >  }
1213 >  if(v0_idp)
1214 >     {
1215 >         *v0_idp = v0_id;
1216 >         *v1_idp = v1_id;
1217 >         *v2_idp = v2_id;
1218 >     }
1219 > }
1220  
1221  
1222 < int
1223 < smIntersectTriSet(sm,t_set,orig,dir,pt)
1222 > /*
1223 > * int
1224 > * smFindSamp(FVECT orig, FVECT dir)
1225 > *
1226 > * Find the closest sample to the given ray.  Returns sample id, -1 on failure.
1227 > * "dir" is assumed to be normalized
1228 > */
1229 >
1230 >  
1231 >
1232 > smRebuild_mesh(sm,vp)
1233     SM *sm;
1234 +   FVECT vp;
1235 + {
1236 +    int i;
1237 +    FVECT dir;
1238 +    COLR c;
1239 +    FVECT p,ov;
1240 +
1241 +    /* Clear the mesh- and rebuild using the current sample array */
1242 +
1243 +    VSUB(ov,vp,SM_VIEW_CENTER(sm));
1244 +    smInit_mesh(sm,vp);
1245 +    
1246 +    SM_FOR_ALL_SAMPLES(sm,i)
1247 +    {
1248 +        if(SM_NTH_W_DIR(sm,i)==-1)
1249 +           VADD(SM_NTH_WV(sm,i),SM_NTH_WV(sm,i),ov);        
1250 +        smAdd_sample_to_mesh(sm,NULL,NULL,NULL,i);      
1251 +    }
1252 + }
1253 +
1254 + int
1255 + intersect_tri_set(t_set,orig,dir,pt)
1256     OBJECT *t_set;
1257     FVECT orig,dir,pt;
1258   {
1259      OBJECT *optr;
1260 <    int i,t_id,v_id;
1261 <    TRI *tri;
1262 <    FVECT p0,p1,p2;
1263 <    char type,which;
1051 <    int p0_id,p1_id,p2_id;
1260 >    int i,t_id,id;
1261 >    int pid0,pid1,pid2;
1262 >    FVECT p0,p1,p2,p;
1263 >    TRI *t;
1264      
1265 <    for(optr = QT_SET_PTR(t_set),i = QT_SET_CNT(t_set); i > 0; i--)
1265 >    optr = QT_SET_PTR(t_set);
1266 >    for(i = QT_SET_CNT(t_set); i > 0; i--)
1267      {
1268          t_id = QT_SET_NEXT_ELEM(optr);
1269 <        tri = SM_NTH_TRI(sm,t_id);
1270 <        p0_id = T_NTH_V(tri,0);
1271 <        p1_id = T_NTH_V(tri,1);
1272 <        p2_id = T_NTH_V(tri,2);
1273 <        VCOPY(p0,SM_NTH_WV(sm,p0_id));
1274 <        VCOPY(p1,SM_NTH_WV(sm,p1_id));
1275 <        VCOPY(p2,SM_NTH_WV(sm,p2_id));
1276 <        if(type = ray_intersect_tri(orig,dir,p0,p1,p2,pt,&which))
1269 >
1270 >        t = SM_NTH_TRI(smMesh,t_id);
1271 >        pid0 = T_NTH_V(t,0);
1272 >        pid1 = T_NTH_V(t,1);
1273 >        pid2 = T_NTH_V(t,2);
1274 >        VCOPY(p0,SM_NTH_WV(smMesh,pid0));
1275 >        VCOPY(p1,SM_NTH_WV(smMesh,pid1));
1276 >        VCOPY(p2,SM_NTH_WV(smMesh,pid2));
1277 >        if(ray_intersect_tri(orig,dir,p0,p1,p2,p))
1278          {
1279 <          if(type==GT_VERTEX)
1280 <            return(T_NTH_V(tri,which));
1281 <          v_id = smClosest_vertex_in_w_tri(sm,p0_id,p1_id,p2_id,pt);
1282 <          return(v_id);
1279 >          id = closest_point_in_tri(p0,p1,p2,p,pid0,pid1,pid2);
1280 >
1281 >          if(pt)
1282 >             VCOPY(pt,p);
1283 > #ifdef DEBUG_TEST_DRIVER
1284 >          Pick_tri = t_id;
1285 >          Pick_samp = id;
1286 >          VCOPY(Pick_point[0],p);
1287 > #endif
1288 >          return(id);
1289          }
1290      }
1291      return(-1);
1292   }
1293  
1294 < /*
1295 < * int
1296 < * smTraceRay(SM *sm,FVECT orig, FVECT dir,FVECT v0,FVECT v1,FVECT v2,FVECT r)
1297 < *
1298 < *   Intersect the ray with triangle v0v1v2, return intersection point in r
1299 < *
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;
1294 > int
1295 > ray_trace_check_set(qtptr,orig,dir,tptr,os)
1296 >   QUADTREE *qtptr;
1297 >   FVECT orig,dir;
1298 >   int *tptr;
1299 >   OBJECT *os;
1300   {
1301 <  FVECT n,p[3],d;
1302 <  double pt[3],r_eps;
1303 <  char i;
1304 <  int which;
1305 <
1306 <  /* Find the plane equation for the triangle defined by the edge v0v1 and
1307 <   the view center*/
1308 <  VCROSS(n,v0,v1);
1309 <  /* Intersect the ray with this plane */
1310 <  i = intersect_ray_plane(orig,dir,n,0.0,&(pt[0]),p[0]);
1311 <  if(i)
1312 <    which = 0;
1313 <  else
1314 <    which = -1;
1315 <
1316 <  VCROSS(n,v1,v2);
1317 <  i = intersect_ray_plane(orig,dir,n,0.0,&(pt[1]),p[1]);
1318 <  if(i)
1319 <    if((which==-1) || pt[1] < pt[0])
1320 <      which = 1;
1321 <
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)
1118 <  {
1119 <      /* Return point that is K*eps along projection of the ray on
1120 <         the sphere to push intersection point p[which] into next cell
1121 <      */
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);
1134 <  }
1135 <  else
1136 <  {
1137 <      /* Unable to find intersection: move along ray and try again */
1138 <      r_eps = -DOT(orig,dir);
1139 <      VSUM(n,dir,orig,r_eps);
1140 <      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);
1147 <  }
1301 >    OBJECT tset[QT_MAXSET+1];  
1302 >    double dt,t;
1303 >    int found;
1304 >    FVECT o;
1305 >    
1306 >
1307 >    if(!QT_IS_EMPTY(*qtptr))
1308 >     {
1309 >         VADD(o,orig,SM_VIEW_CENTER(smMesh));
1310 >         qtgetset(tset,*qtptr);
1311 >         /* Check triangles in set against those seen so far(os):only
1312 >            check new triangles for intersection (t_set')
1313 >            */
1314 >         check_set(tset,os);
1315 >         if((found = intersect_tri_set(tset,o,dir,NULL))!= -1)
1316 >         {
1317 >             *tptr = found;
1318 >             return(QT_DONE);
1319 >         }
1320 >       }
1321 >    return(FALSE);
1322   }
1323  
1150 –
1151 – /*
1152 – * int
1153 – * smFindSamp(FVECT orig, FVECT dir)
1154 – *
1155 – * Find the closest sample to the given ray.  Returns sample id, -1 on failure.
1156 – * "dir" is assumed to be normalized
1157 – */
1324   int
1325   smFindSamp(orig,dir)
1326   FVECT orig,dir;
1327   {
1328 <  FVECT r,v0,v1,v2,a,b,p;
1329 <  OBJECT os[MAXCSET+1],t_set[MAXSET+1];
1328 >  FVECT b,p,o;
1329 >  OBJECT *ts;
1330    QUADTREE qt;
1331    int s_id;
1332    double d;
# Line 1180 | Line 1346 | FVECT orig,dir;
1346       either case, do a single test against the cell containing the
1347       intersection of "dir" and the sphere
1348     */
1349 +  /* orig will be updated-so preserve original value */
1350 +  if(!smMesh)
1351 +     return;
1352    point_on_sphere(b,orig,SM_VIEW_CENTER(smMesh));
1353    d = -DOT(b,dir);
1354    if(EQUAL_VEC3(orig,SM_VIEW_CENTER(smMesh)) || EQUAL(fabs(d),1.0))
1355    {
1356 <      qt = smPointLocateCell(smMesh,dir,v0,v1,v2,NULL,NULL,FALSE);
1356 >      qt = smPointLocateCell(smMesh,dir,FALSE,NULL,NULL,NULL);
1357        /* Test triangles in the set for intersection with Ray:returns
1358           first found
1359        */
1360 <      qtgetset(t_set,qt);
1361 <      s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p);
1362 < #ifdef TEST_DRIVER
1360 >      ts = qtqueryset(qt);
1361 >      s_id = intersect_tri_set(ts,orig,dir,p);
1362 > #ifdef DEBUG_TEST_DRIVER
1363        VCOPY(Pick_point[0],p);
1364   #endif
1196 –      return(s_id);
1365    }
1366    else
1367    {
1368 <      /* Starting with orig, Walk along projection of ray onto sphere */
1369 <      point_on_sphere(r,orig,SM_VIEW_CENTER(smMesh));
1370 <      qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE);
1371 <      qtgetset(t_set,qt);
1372 <      /* os will contain all triangles seen thus far */
1373 <      setcopy(os,t_set);
1374 <
1375 <      /* Calculate ray perpendicular to dir: when projection ray is // to dir,
1208 <         the dot product will become negative.
1209 <       */
1210 <      VSUM(a,b,dir,d);
1211 <      d = DOT(a,b);
1212 <      while(d > 0)
1213 <      {
1214 <          s_id = smIntersectTriSet(smMesh,t_set,orig,dir,p);
1215 < #ifdef TEST_DRIVER
1216 <          VCOPY(Pick_point[0],p);
1217 < #endif    
1218 <          if(s_id != EMPTY)
1219 <               return(s_id);
1220 <          /* Find next cell that projection of ray intersects */
1221 <          smTraceRay(smMesh,r,dir,v0,v1,v2,r);
1222 <          qt = smPointLocateCell(smMesh,r,v0,v1,v2,NULL,NULL,FALSE);
1223 <          qtgetset(t_set,qt);
1224 <          /* Check triangles in set against those seen so far(os):only
1225 <             check new triangles for intersection (t_set')
1226 <          */
1227 <          check_set(t_set,os);
1228 <          d = DOT(a,r);
1229 <      }
1230 <    }
1231 < #ifdef DEBUG  
1232 <  eputs("smFindSamp():Pick Ray did not intersect mesh");
1233 < #endif
1234 <  return(EMPTY);
1368 >    OBJECT t_set[QT_MAXCSET+1];
1369 >    /* Test each of the root triangles against point id */
1370 >    QT_CLEAR_SET(t_set);
1371 >    VSUB(o,orig,SM_VIEW_CENTER(smMesh));
1372 >    ST_CLEAR_FLAGS(SM_LOCATOR(smMesh));
1373 >    s_id=stTrace_ray(SM_LOCATOR(smMesh),o,dir,ray_trace_check_set,&s_id,t_set);
1374 > }    
1375 >  return(s_id);
1376   }
1236 –  
1377  
1238 – smRebuild_mesh(sm,vptr)
1239 –   SM *sm;
1240 –   VIEW *vptr;
1241 – {
1242 –    int i;
1243 –    FVECT dir;
1244 –    COLR c;
1245 –    FVECT p,ov;
1378  
1247 –    /* Clear the mesh- and rebuild using the current sample array */
1248 – #ifdef TEST_DRIVER
1249 –    View = *vptr;
1250 – #endif    
1379  
1380 <    VSUB(ov,vptr->vp,SM_VIEW_CENTER(sm));
1381 <    smInit_mesh(sm,vptr->vp);
1382 <    
1383 <    SM_FOR_ALL_SAMPLES(sm,i)
1384 <    {
1385 <        if(SM_NTH_W_DIR(sm,i)==-1)
1386 <           VADD(SM_NTH_WV(sm,i),SM_NTH_WV(sm,i),ov);        
1259 <        smAdd_sample_to_mesh(sm,NULL,NULL,NULL,i);      
1260 <    }
1261 < }
1380 >
1381 >
1382 >
1383 >
1384 >
1385 >
1386 >
1387  
1388  

Diff Legend

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