home *** CD-ROM | disk | FTP | other *** search
/ Altsys Virtuoso 2.0K / virtuoso_20k.iso / DemoApps / Graphics / Viewers / raytracers / ohta / Source / initdir.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-08  |  7.0 KB  |  374 lines
  1. #include <math.h>
  2. #include <stdio.h>
  3.  
  4. #include "ray.h"
  5.  
  6. struct circle *dvl;
  7.  
  8. struct dirlist **neighbor;
  9.  
  10. int *markdir;
  11.  
  12. initdir()
  13. {register int o0,o1,d;
  14. register double l;
  15. struct point c0,c1;
  16. register double r0,r1;
  17. struct circle cir;
  18. register struct objlist *ol;
  19. int origins;
  20.     origins=0;
  21.     for(o0=0;o0<maxobj;o0++)
  22.     {    if((objects[o0].flags&RAYORIGIN))
  23.             origins++;
  24.     }
  25.     NRECTS=40;
  26.     if(NRECTS*sqrt((double)origins)>100)
  27.     {    if(origins)
  28.             NRECTS=100/sqrt((double)origins);
  29.         else
  30.             NRECTS=100;
  31.     }
  32.     if(NRECTS<4)
  33.         NRECTS=4;
  34.     DIRECTIONS=6*NRECTS*NRECTS;
  35.     dvl=nalloc(struct circle,DIRECTIONS);
  36.     neighbor=nalloc(struct dirlist *,DIRECTIONS);
  37.     markdir=nalloc(int,DIRECTIONS);
  38.     candidates=nalloc(struct objlist **,maxobj);
  39.     for(o0=0;o0<maxobj;o0++)
  40.     {    if(!(objects[o0].flags&RAYORIGIN))
  41.             continue;;
  42.         candidates[o0]=nalloc(struct objlist *,DIRECTIONS);
  43.     }
  44.     initdvl();
  45.     initneighbor();
  46.     for(d=0;d<DIRECTIONS;d++)
  47.         markdir[d]=0;
  48.     for(o0=0;o0<maxobj;o0++)
  49.     {    if(!(objects[o0].flags&RAYORIGIN))
  50.             continue;;
  51.         for(d=0;d<DIRECTIONS;d++)
  52.             candidates[o0][d]=(struct objlist *)0;
  53.         for(o1=lights+1;o1<maxobj;o1++)
  54.         {    if(o0==o1)
  55.                 continue;
  56.             if(dflag)
  57.                 fprintf(stderr,"object %d to %d\n",o0,o1);
  58.             c0=objects[o0].center;
  59.             r0=objects[o0].radius;
  60.             c1=objects[o1].center;
  61.             r1=objects[o1].radius;
  62.             cir.o.x=c1.x-c0.x;
  63.             cir.o.y=c1.y-c0.y;
  64.             cir.o.z=c1.z-c0.z;
  65.             l=sqrt(cir.o.x*cir.o.x+cir.o.y*cir.o.y+cir.o.z*cir.o.z);
  66.             cir.o.x/=l;
  67.             cir.o.y/=l;
  68.             cir.o.z/=l;
  69.             if(r0+r1>=l)
  70.             {    for(d=0;d<DIRECTIONS;d++)
  71.                 {    if(oflag)
  72.                         ol=alloc(struct objlist);
  73.                     else
  74.                         ol=(struct objlist *)
  75.                             alloc(struct objlist2);
  76.                     ol->obj=o1;
  77.                     ol->next=candidates[o0][d];
  78.                     if(oflag)
  79.                         ol->t=0;
  80.                     candidates[o0][d]=ol;
  81.                 }
  82.             }
  83.             else
  84.             {    cir.s=(r0+r1)/l;
  85.                 cir.c=sqrt(1-cir.s*cir.s);
  86.                 d=dindex(cir.o);
  87.                 if(oflag)
  88.                     ttraverse(d,&cir,o1,
  89.                         candidates[o0],l-r0-r1);
  90.                 else
  91.                     traverse(d,&cir,o1,candidates[o0]);
  92.                 tclear(d);
  93.             }
  94.         }
  95.         if(oflag)
  96.             for(d=0;d<DIRECTIONS;d++)
  97.                 sortlist(candidates[o0][d]);
  98.     }
  99.     if(tflag)
  100.     {int c;
  101.         c=0;
  102.         for(d=0;d<DIRECTIONS;d++)
  103.             for(ol=candidates[0][d];ol;ol=ol->next)
  104.                 c++;
  105.         fprintf(stderr,"Image complexity %g\n",((double)c)/DIRECTIONS);
  106.         for(o0=1;o0<lights+1;o0++)
  107.         {    c=0;
  108.             for(d=0;d<DIRECTIONS;d++)
  109.                 for(ol=candidates[o0][d];ol;ol=ol->next)
  110.                     c++;
  111.             fprintf(stderr,"Shadow complexity for light %d %g\n",
  112.                 o0,((double)c)/DIRECTIONS);
  113.         }
  114.     }
  115. }
  116.  
  117. traverse(d,cir,o,ol)
  118. register int d;
  119. register struct circle *cir;
  120. register int o;
  121. register struct objlist **ol;
  122. {register struct dirlist *dl;
  123. register struct objlist *ol2;
  124.     markdir[d]=1;
  125.     if(!overlap(&dvl[d],cir))
  126.         return;
  127.     ol2=(struct objlist *)alloc(struct objlist2);
  128.     ol2->obj=o;
  129.     ol2->next=ol[d];
  130.     ol[d]=ol2;
  131.     for(dl=neighbor[d];dl;dl=dl->next)
  132.         if(!markdir[dl->dir])
  133.             traverse(dl->dir,cir,o,ol);
  134. }
  135.  
  136. ttraverse(d,cir,o,ol,t)
  137. register int d;
  138. register struct circle *cir;
  139. register int o;
  140. register struct objlist **ol;
  141. register double t;
  142. {register struct dirlist *dl;
  143. register struct objlist *ol2;
  144.     markdir[d]=1;
  145.     if(!overlap(&dvl[d],cir))
  146.         return;
  147.     ol2=alloc(struct objlist);
  148.     ol2->obj=o;
  149.     ol2->next=ol[d];
  150.     ol2->t=t;
  151.     ol[d]=ol2;
  152.     for(dl=neighbor[d];dl;dl=dl->next)
  153.         if(!markdir[dl->dir])
  154.             ttraverse(dl->dir,cir,o,ol,t);
  155. }
  156.  
  157. tclear(d)
  158. register int d;
  159. {register struct dirlist *dl;
  160.     markdir[d]=0;
  161.     for(dl=neighbor[d];dl;dl=dl->next)
  162.         if(markdir[dl->dir])
  163.             tclear(dl->dir);
  164. }
  165.  
  166. overlap(cir0,cir1)
  167. register struct circle *cir0,*cir1;
  168. {    return
  169.         cir0->o.x*cir1->o.x+cir0->o.y*cir1->o.y+cir0->o.z*cir1->o.z
  170.         >
  171.         cir0->c*cir1->c-cir0->s*cir1->s;
  172. }
  173.  
  174. struct circle initdvl2(x,y,z,dx0,dy0,dz0,dx1,dy1,dz1)
  175. double x,y,z,dx0,dy0,dz0,dx1,dy1,dz1;
  176. {int i;
  177. double l,c,minc;
  178. struct vector v[4];
  179. struct circle cir;
  180.     for(i=0;i<4;i++)
  181.     {    v[i].x=x;
  182.         v[i].y=y;
  183.         v[i].z=z;
  184.     }
  185.     v[1].x+=dx0;
  186.     v[1].y+=dy0;
  187.     v[1].z+=dz0;
  188.     v[2].x+=dx0+dx1;
  189.     v[2].y+=dy0+dy1;
  190.     v[2].z+=dz0+dz1;
  191.     v[3].x+=dx1;
  192.     v[3].y+=dy1;
  193.     v[3].z+=dz1;
  194.     cir.o.x=cir.o.y=cir.o.z=0;
  195.     for(i=0;i<4;i++)
  196.     {    cir.o.x+=v[i].x/4;
  197.         cir.o.y+=v[i].y/4;
  198.         cir.o.z+=v[i].z/4;
  199.         l=1/sqrt(v[i].x*v[i].x+v[i].y*v[i].y+v[i].z*v[i].z);
  200.         v[i].x*=l;
  201.         v[i].y*=l;
  202.         v[i].z*=l;
  203.     }
  204.     l=1/sqrt(cir.o.x*cir.o.x+cir.o.y*cir.o.y+cir.o.z*cir.o.z);
  205.     cir.o.x*=l;
  206.     cir.o.y*=l;
  207.     cir.o.z*=l;
  208.     minc=1;
  209.     for(i=0;i<4;i++)
  210.     {    c=cir.o.x*v[i].x+cir.o.y*v[i].y+cir.o.z*v[i].z;
  211.         if(c<minc)
  212.             minc=c;
  213.     }
  214.     cir.c=minc*0.999999;
  215.     cir.s=sqrt(1-cir.c*cir.c);
  216.     return cir;
  217. }
  218.  
  219. initdvl()
  220. {int i,j,d;
  221. double x,y,z,dl;
  222.     dl=2.0/NRECTS;
  223.     d=0;
  224.     x=1;
  225.     z= -1;
  226.     for(i=0;i<NRECTS;i++)
  227.     {    y= -1;
  228.         for(j=0;j<NRECTS;j++)
  229.         {    dvl[d++]=initdvl2(x,y,z,0.0,0.0,dl,0.0,dl,0.0);
  230.             y+=dl;
  231.         }
  232.         z+=dl;
  233.     }
  234.     x= -1;
  235.     z= -1;
  236.     for(i=0;i<NRECTS;i++)
  237.     {    y= -1;
  238.         for(j=0;j<NRECTS;j++)
  239.         {    dvl[d++]=initdvl2(x,y,z,0.0,dl,0.0,0.0,0.0,dl);
  240.             y+=dl;
  241.         }
  242.         z+=dl;
  243.     }
  244.     y=1;
  245.     x= -1;
  246.     for(i=0;i<NRECTS;i++)
  247.     {    z= -1;
  248.         for(j=0;j<NRECTS;j++)
  249.         {    dvl[d++]=initdvl2(x,y,z,dl,0.0,0.0,0.0,0.0,dl);
  250.             z+=dl;
  251.         }
  252.         x+=dl;
  253.     }
  254.     y= -1;
  255.     x= -1;
  256.     for(i=0;i<NRECTS;i++)
  257.     {    z= -1;
  258.         for(j=0;j<NRECTS;j++)
  259.         {    dvl[d++]=initdvl2(x,y,z,0.0,0.0,dl,dl,0.0,0.0);
  260.             z+=dl;
  261.         }
  262.         x+=dl;
  263.     }
  264.     z=1;
  265.     y= -1;
  266.     for(i=0;i<NRECTS;i++)
  267.     {    x= -1;
  268.         for(j=0;j<NRECTS;j++)
  269.         {    dvl[d++]=initdvl2(x,y,z,0.0,dl,0.0,dl,0.0,0.0);
  270.             x+=dl;
  271.         }
  272.         y+=dl;
  273.     }
  274.     z= -1;
  275.     y= -1;
  276.     for(i=0;i<NRECTS;i++)
  277.     {    x= -1;
  278.         for(j=0;j<NRECTS;j++)
  279.         {    dvl[d++]=initdvl2(x,y,z,dl,0.0,0.0,0.0,dl,0.0);
  280.             x+=dl;
  281.         }
  282.         y+=dl;
  283.     }
  284. }
  285.  
  286. struct dirlist *consdir(m,dl)
  287. int m;
  288. struct dirlist *dl;
  289. {struct dirlist *dl2;
  290.     dl2=alloc(struct dirlist);
  291.     dl2->dir=m;
  292.     dl2->next=dl;
  293.     return dl2;
  294. }
  295.  
  296. initneighbor()
  297. {int i;
  298. double d;
  299.     for(i=0;i<DIRECTIONS;i++)
  300.         neighbor[i]=(struct dirlist *)0;
  301.     d=2.0/NRECTS;
  302.     initneighbor2(1.0,-1.0,-1.0,0.0,d,0.0,0.0,0.0,d);
  303.     initneighbor2(-1.0,-1.0,-1.0,0.0,d,0.0,0.0,0.0,d);
  304.     initneighbor2(-1.0,1.0,-1.0,d,0.0,0.0,0.0,0.0,d);
  305.     initneighbor2(-1.0,-1.0,-1.0,d,0.0,0.0,0.0,0.0,d);
  306.     initneighbor2(-1.0,-1.0,1.0,d,0.0,0.0,0.0,d,0.0);
  307.     initneighbor2(-1.0,-1.0,-1.0,d,0.0,0.0,0.0,d,0.0);
  308. }
  309.  
  310. initneighbor2(x,y,z,dx0,dy0,dz0,dx1,dy1,dz1)
  311. double x,y,z,dx0,dy0,dz0,dx1,dy1,dz1;
  312. {int i,j,d;
  313. double x0,y0,z0,x1,y1,z1;
  314.     x0=x+dx0/2+dx1/2;
  315.     y0=y+dy0/2+dy1/2;
  316.     z0=z+dz0/2+dz1/2;
  317.     for(i=0;i<NRECTS;i++)
  318.     {    for(j=0;j<NRECTS;j++)
  319.         {    x1=x0+i*dx0+j*dx1;
  320.             y1=y0+i*dy0+j*dy1;
  321.             z1=z0+i*dz0+j*dz1;
  322.             d=dindex2(x1,y1,z1);
  323.             neighbor[d]=consdir(dindex2(x1+dx0,y1+dy0,z1+dz0),
  324.                 neighbor[d]);
  325.             neighbor[d]=consdir(dindex2(x1-dx0,y1-dy0,z1-dz0),
  326.                 neighbor[d]);
  327.             neighbor[d]=consdir(dindex2(x1+dx1,y1+dy1,z1+dz1),
  328.                 neighbor[d]);
  329.             neighbor[d]=consdir(dindex2(x1-dx1,y1-dy1,z1-dz1),
  330.                 neighbor[d]);
  331.         }
  332.     }
  333. }
  334.  
  335. dindex2(x,y,z)
  336. double x,y,z;
  337. {struct vector v;
  338.     v.x=x;
  339.     v.y=y;
  340.     v.z=z;
  341.     return dindex(v);
  342. }
  343.  
  344. print2(v)
  345. struct vector *v;
  346. {    if(v->z==0)
  347.     {    printf("\tz=0\n");
  348.         return;
  349.     }
  350.     printf("\t%g %g\n",v->x/v->z,v->y/v->z);
  351. }
  352. sortlist(ol)
  353. register struct objlist *ol;
  354. {register struct objlist *ol2,*ol3;
  355. double t;
  356. int obj;
  357.     if(!ol)
  358.         return;
  359.     for(;ol->next;ol=ol->next)
  360.     {    ol3=ol;
  361.         for(ol2=ol->next;ol2;ol2=ol2->next)
  362.             if(ol2->t<ol3->t)
  363.                 ol3=ol2;
  364.         if(ol!=ol3)
  365.         {    t=ol->t;
  366.             ol->t=ol3->t;
  367.             ol3->t=t;
  368.             obj=ol->obj;
  369.             ol->obj=ol3->obj;
  370.             ol3->obj=obj;
  371.         }
  372.     }
  373. }
  374.