home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / raytrace / radiance / simplerd.lha / simplerad / FinalFTP / Light / adj.c next >
Encoding:
C/C++ Source or Header  |  1992-05-21  |  16.6 KB  |  478 lines
  1. /**********************************************************************/
  2. /* adj.c:                                                             */
  3. /*                                                                    */
  4. /* Calculate vertex and patch / element adjacency and "group"         */
  5. /* together patches, elements and meshes that are "close" to each     */
  6. /* other. Also routines to perform bilinar subdivision.               */
  7. /*                                                                    */
  8. /* Copyright (C) 1992, Bernard Kwok                                   */
  9. /* All rights reserved.                                               */
  10. /* Revision 1.0                                                       */
  11. /* May, 1992                                                          */
  12. /**********************************************************************/
  13. #include <stdio.h>
  14. #include <string.h>
  15. #include <math.h>
  16. #include "geo.h"
  17. #include "struct.h"
  18. #include "io.h"
  19. #include "rad.h"
  20. #include "adj.h"
  21.  
  22. extern OptionType Option;
  23. extern RadParams ReadLog;
  24.  
  25. Vertex_tree *vtree = 0;              /* global vertex octree          */
  26. unsigned long vtree_size = 0;        /* Number of vertices in tree    */
  27. Vertex_list *vlist = 0;              
  28. Vertex_list *vlist_tail = 0;         
  29. unsigned long vlist_size = 0; 
  30. extern RadParams ReadLog;            /* Radiosity parameters          */
  31.  
  32. /**********************************************************************/
  33. /* If we run out of memory... */
  34. /**********************************************************************/
  35. void MemError()
  36. { fprintf(stderr,"No more space to allocate\n"); exit(1); }
  37.  
  38. /*====================================================================*/
  39. /* Vertex octree routines                                             */
  40. /*====================================================================*/
  41. /**********************************************************************/
  42. /* Create dummy vertex tree root as "center of the world"             */
  43. /**********************************************************************/
  44. Vertex_tree *VTree_Create(params)
  45.      RadParams params;
  46. {
  47.   int s;
  48.   Vertex_tree *optr;
  49.  
  50.   if ((optr = (Vertex_tree *) malloc(sizeof(Vertex_tree))) == 0)
  51.     MemError();
  52.   if ((optr->vtx = (Vertex *) malloc(sizeof(Vertex))) == 0)
  53.     MemError();
  54.  
  55.   /* Vertex is at the center of the world */
  56.   optr->vtx->pos = *vmiddle(¶ms.worldbox.min, ¶ms.worldbox.max);
  57.   optr->vtx->id = -1;
  58.   optr->vtx->name = "World Center";
  59.   
  60.   /* No polys for imaginary vertex */
  61.   optr->vtx->polylist = optr->vtx->polyhead.front = 
  62.     optr->vtx->polyhead.front = 0;
  63.   optr->vtx->polyhead.num_polys = 0;
  64.  
  65.   for (s=0;s<num_octants;s++)
  66.     optr->child[s] = 0;
  67.  
  68.   return optr;
  69. }
  70.  
  71. /*************************************************************************/
  72. /* Create vertex tree node with center of octant = vertex                */
  73. /*************************************************************************/
  74. Vertex_tree *VTree_NodeCreate(v,father)
  75.      Vertex *v;
  76.      Vertex_tree *father;
  77. {
  78.   int i;
  79.   Vertex_tree *new_vtptr;
  80.  
  81.   if ((new_vtptr = (Vertex_tree *) malloc(sizeof(Vertex_tree))) == 0)
  82.     MemError();
  83.   new_vtptr->vtx = v;
  84.   for (i=0;i<num_octants;i++) 
  85.     new_vtptr->child[i] = 0;
  86.   new_vtptr->father = father;    
  87.  
  88.   vtree_size++;
  89.   return (new_vtptr);
  90. }
  91.  
  92. /**********************************************************************/
  93. /* Add child to appropriate octant of a vertex-tree node              */
  94. /**********************************************************************/
  95. void VTree_NodeAddChild(vtx,father,octant)
  96.      Vertex *vtx;
  97.      Vertex_tree *father;
  98.      int octant;
  99. {
  100.   Vertex_tree *new_vtptr;
  101.  
  102.   /* Allocate space for new vertex tree node */
  103.   new_vtptr = VTree_NodeCreate(vtx,father);
  104.   father->child[octant] = new_vtptr;
  105. }
  106.  
  107. /**********************************************************************/
  108. /* Find which octant of a given tree node, a vector belongs to */
  109. /* and which octants a cube, centered around the vector */
  110. /* and within distance (VTX_TOLERANCE) of the vector, belongs to */
  111. /**********************************************************************/
  112. int Vtree_VectorOctant(vptr,mid,octants)
  113.      Vector *vptr;
  114.      Vector *mid;
  115.      int octants[num_octants];
  116. {
  117.   int i,j,k;
  118.   float u,v,w;
  119.   Vector tolerance_cube[num_octants];
  120.   int octant;
  121.  
  122.   u = -1; v = -1; w = -1;
  123.   for(i=0;i<2;i++) {
  124.     for(j=0;j<2;j++) {
  125.       for(k=0;k<2;k++) {
  126.     tolerance_cube[(4*i+2*j+k)].x = vptr->x + u * VTX_TOLERANCE;
  127.     tolerance_cube[(4*i+2*j+k)].y = vptr->y + v * VTX_TOLERANCE;
  128.     tolerance_cube[(4*i+2*j+k)].z = vptr->z + w * VTX_TOLERANCE;
  129.     u = -u;
  130.       }
  131.       v = -v;
  132.     }
  133.     w = -w;
  134.   }
  135.  
  136.   /* Find octants that intersect tolerance cube for vertex */
  137.   for(i=0;i<num_octants;i++) {
  138.     octant = 0; octants[i] = 0;
  139.     if (tolerance_cube[i].x > mid->x) octant++;
  140.     if (tolerance_cube[i].z < mid->z) octant += 2;
  141.     if (tolerance_cube[i].y < mid->y) octant += 4;
  142.     octants[octant] = 1;
  143.   }
  144.   /* Find octant vertex belongs to */
  145.   octant = 0;
  146.   if (vptr->x > mid->x) octant++;
  147.   if (vptr->z < mid->z) octant += 2;
  148.   if (vptr->y < mid->y) octant += 4;
  149.   octants[octant] = 1;
  150.   return octant;
  151. }
  152.  
  153. /**********************************************************************/
  154. /* Find if vertex exist in tree, if does return tree node found in,   */
  155. /* else return not found, and tree node to create */
  156. /**********************************************************************/
  157. int VTree_NodeFind(v,vt,pptr,vertex_num)
  158.      Vector v;
  159.      Vertex_tree *vt;
  160.      Polygon *pptr;
  161.      int vertex_num;
  162. {
  163.   int octants[num_octants];            /* vertex cube octants to search */
  164.   int voctant;                         /* octant of vertex to search    */
  165.   int i, found;
  166.  
  167.   if (vsame(&(vt->vtx->pos), &v, VTX_TOLERANCE)) {
  168.     /* Vertex already exists, just link poly to vertex, and 
  169.        vertex to poly */
  170.     LinkPoly_ToVertex(vt->vtx, pptr);
  171.     pptr->vert[vertex_num] = vt->vtx;
  172.     return 1;
  173.     
  174.   } else {
  175.     /* Find which octants to traverse */
  176.     voctant = Vtree_VectorOctant(&v,&(vt->vtx->pos),octants);
  177.     
  178.     found = 0; i=0;
  179.     while((i<num_octants) && (found == 0)) {
  180.  
  181.       /* Search path of vertex -- not used */
  182.       /* if (vt->child[voctant] != 0)      
  183.      found = VTree_NodeFind(v,vt->child[voctant],pptr,vertex_num);
  184.      else if (found == 0) {              
  185.      pptr->vert[vertex_num] = Vertex_Create(v,pptr);
  186.      VTree_NodeAddChild(pptr->vert[vertex_num],vt,voctant);
  187.      return 1;
  188.      }
  189.      */
  190.     
  191.       /* Search path of vertex tolerance cube */
  192.       if (!found && octants[i]) {
  193.     if (vt->child[i] != 0)      
  194.       found = VTree_NodeFind(v,vt->child[i],pptr,vertex_num);
  195.     else if (found == 0) {              /* If NOT found, create ONCE */
  196.       pptr->vert[vertex_num] = Vertex_Create(v,pptr);
  197.       VTree_NodeAddChild(pptr->vert[vertex_num],vt,i);
  198.       return 1;
  199.     }
  200.       }
  201.       i++;
  202.     }
  203.   }
  204.   return(found);
  205. }
  206.  
  207. /**********************************************************************/
  208. /* Create new vertex structure, associate a polygon with it */
  209. /**********************************************************************/
  210. Vertex *Vertex_Create(position, adjpoly)
  211.      Vector position;
  212.      Polygon *adjpoly;
  213. {
  214.   Vertex *v;
  215.   
  216.   if ((v = (Vertex *) malloc(sizeof(Vertex))) == 0)
  217.     MemError();
  218.   if ((v->polylist = (PolyList *) malloc(sizeof(PolyList))) == 0)
  219.     MemError();
  220.   
  221.   v->id = vlist_size;
  222.   v->name = "Vertex";
  223.   v->pos = position;
  224.   v->polylist->patch = adjpoly;
  225.   v->polyhead.num_polys = 1;
  226.   v->polyhead.front = v->polyhead.back = v->polylist;
  227.   v->polylist->next = 0;
  228.   return(v);
  229. }
  230.  
  231. /**********************************************************************/
  232. /* Create new polygon for poly list of vertex, update back of list */
  233. /**********************************************************************/
  234. void LinkPoly_ToVertex(v, p)
  235.      Vertex *v;
  236.      Polygon *p;
  237. {
  238.   PolyList *pl;
  239.  
  240.   if ((pl = (PolyList *) malloc(sizeof(PolyList))) == 0)
  241.     MemError();
  242.   pl->patch = p;
  243.   pl->next = 0;
  244.   v->polyhead.back->next = pl;
  245.   v->polyhead.num_polys++;
  246.   v->polyhead.back = pl;
  247. }
  248.  
  249. /**********************************************************************/
  250. /* Vertex v belongs to patch p in position vnum */
  251. /**********************************************************************/
  252. void LinkVertex_ToPoly(p, v, vnum)
  253.      Polygon *p;
  254.      Vertex *v;
  255.      int vnum;
  256. { p->vert[vnum] = v; }
  257.               
  258. /*====================================================================*/
  259. /* Bilinear subdivision code */
  260. /*====================================================================*/
  261. /**********************************************************************/
  262. /* Create children for current poly, and assign appropriate values    */
  263. /* and pointers                                                       */
  264. /**********************************************************************/
  265. void Create_Children(p)
  266.      Polygon *p;
  267. {
  268.   int i,j,k;
  269.   Polygon *ch;
  270.   char *str = "                                              ";
  271.  
  272.   for(i=0;i<MAX_PATCH_CHILDREN;i++) {
  273.     ReadLog.totpoly++;
  274.     if ((p->child[i] = (Polygon *) malloc(sizeof(Polygon))) == 0)
  275.       MemError();
  276.     ch = p->child[i];
  277.     ch->id = ReadLog.totpoly;
  278.     sprintf(str,"%s_child", p->name);
  279.     ch->name = str;
  280.     ch->class = p->class;          /* Preserve shape */
  281.     for(j=0;j<MAX_PATCH_VTX;j++) {
  282.       ch->vert[j] = (Vertex *)NULL;
  283.       ch->normal[j] = p->normal[j];
  284.     }
  285.     ch->changingNormal = 0;
  286.     ch->area = p->area /           /* Assume that area is divided 
  287.                       evenly. */
  288.       (double)(MAX_PATCH_CHILDREN);
  289.     ch->numVert = p->numVert;
  290.     for(k=0;k<MAX_PATCH_CHILDREN;k++) 
  291.       ch->child[k] = (Polygon *)NULL;
  292.     ch->d = p->d;                  /* On same plane */
  293.     ch->level = p->level+1;        /* Push down 1 level */
  294.     ch->Mfather = p->Mfather;      /* Same mesh */
  295.     if (p->Pfather != NULL)        /* Check if root poly or not */
  296.       ch->Pfather = p->Pfather;
  297.     else
  298.       ch->Pfather = p;
  299.     ch->Links = (PolyList *)NULL; /* No form factor links */
  300.     ch->polyhead.front = ch->polyhead.back = ch->Links;
  301.     ch->polyhead.num_polys = 0;
  302.     ch->next = (Polygon *)NULL;
  303.   }
  304. }
  305.  
  306. /**********************************************************************/
  307. /* Create four new points created by subdivision of quad or triangle  */
  308. /* Assume counter clockwise ordering of vertices, from lower left     */
  309. /**********************************************************************/
  310. void Create_Subdivision_Points(v,nv,num_vert)
  311.      Vector v[4];              /* Poly vertitces */
  312.      Vector nv[5];             /* New poly child vertices */
  313.      int num_vert;
  314. {
  315.   int i;
  316.  
  317.   if (num_vert == 4) { /* bilinear subdivide a rectangle */
  318.     /* 4 side midpoints, counter-clockwise, and then middle point */
  319.     for(i=0;i<num_vert;i++)
  320.       nv[i] = *vmiddle(&v[i], &v[(i + 1) % 4]);
  321.     nv[num_vert] = *vmiddle(vmiddle(&nv[0], &nv[2]), 
  322.                 vmiddle(&nv[1], &nv[3])); 
  323.  
  324.   } else { /* bilinearly subdivide a triangle */
  325.     /* 3 side midpoints, counter-clockwise */
  326.     for(i=0;i<num_vert;i++)
  327.       nv[i] = *vmiddle(&v[i], &v[(i + 1) % 3]);
  328.   }
  329. }
  330.  
  331. /**********************************************************************/
  332. /* Create children for patch, assign vertices, and adjacency info,    */
  333. /* set radiosity values per vertex and patch */
  334. /**********************************************************************/
  335. void Subdivide_Polygon(p)
  336.      Polygon *p;
  337. {
  338.   int c,s,v,vv;
  339.   int num_vert;
  340.   Vector vert[MAX_PATCH_VTX];        /* Poly vertices */
  341.   Vector new_vert[5];                /* New poly child vertices */
  342.   Spectra corner_B[MAX_PATCH_VTX];
  343.   Spectra new_B[5];
  344.   static int dud = 0;
  345.  
  346.   num_vert = p->numVert;
  347.  
  348.   /* Create new children */
  349.   Create_Children(p);
  350.  
  351.   /* Assign radiosity values for new children: Patch 
  352.      (total and unshot) and vertex (total) radiosities. */
  353.   for (s=0;s<MAX_SPECTRA_SAMPLES;s++)
  354.     new_B[num_vert].samples[s] = 0.0;
  355.   for(v=0;v<num_vert;v++) {
  356.     vv = (v+1) % num_vert;
  357.     for (s=0;s<MAX_SPECTRA_SAMPLES;s++) {
  358.       corner_B[v].samples[s] = p->vtx_B[v].samples[s];
  359.       new_B[v].samples[s] = (corner_B[v].samples[s] + 
  360.                  p->vtx_B[vv].samples[s]) / 2.0;
  361.       new_B[num_vert].samples[s] += (corner_B[v].samples[s] / num_vert);
  362.     }
  363.   }
  364.   for (c=0;c<MAX_PATCH_CHILDREN;c++) {
  365.     for (s=0;s<MAX_SPECTRA_SAMPLES;s++) {
  366.       p->child[c]->unshot_B.samples[s] = p->unshot_B.samples[s];
  367.       p->child[c]->B.samples[s] = p->B.samples[s];
  368.     }
  369.   }
  370.   if (p->class == PATCH)
  371.     for (s=0;s<MAX_SPECTRA_SAMPLES;s++) {
  372.       p->child[0]->vtx_B[0].samples[s] = corner_B[0].samples[s];
  373.       p->child[0]->vtx_B[1].samples[s] = new_B[0].samples[s];
  374.       p->child[0]->vtx_B[2].samples[s] = new_B[4].samples[s];
  375.       p->child[0]->vtx_B[3].samples[s] = new_B[3].samples[s];
  376.  
  377.       p->child[1]->vtx_B[0].samples[s] = new_B[0].samples[s];
  378.       p->child[1]->vtx_B[1].samples[s] = corner_B[1].samples[s];
  379.       p->child[1]->vtx_B[2].samples[s] = new_B[1].samples[s];
  380.       p->child[1]->vtx_B[3].samples[s] = new_B[4].samples[s];
  381.  
  382.       p->child[2]->vtx_B[0].samples[s] = new_B[4].samples[s];
  383.       p->child[2]->vtx_B[1].samples[s] = new_B[1].samples[s];
  384.       p->child[2]->vtx_B[2].samples[s] = corner_B[2].samples[s];
  385.       p->child[2]->vtx_B[3].samples[s] = new_B[2].samples[s];
  386.  
  387.       p->child[3]->vtx_B[0].samples[s] = new_B[3].samples[s];
  388.       p->child[3]->vtx_B[1].samples[s] = new_B[4].samples[s];
  389.       p->child[3]->vtx_B[2].samples[s] = new_B[2].samples[s];
  390.       p->child[3]->vtx_B[3].samples[s] = corner_B[3].samples[s];
  391.     }
  392.   else           /* Is a triangle */
  393.     for (s=0;s<MAX_SPECTRA_SAMPLES;s++) {
  394.       p->child[0]->vtx_B[0].samples[s] = corner_B[0].samples[s];
  395.       p->child[0]->vtx_B[1].samples[s] = new_B[0].samples[s];
  396.       p->child[0]->vtx_B[2].samples[s] = new_B[2].samples[s];
  397.  
  398.       p->child[1]->vtx_B[0].samples[s] = new_B[0].samples[s];
  399.       p->child[1]->vtx_B[1].samples[s] = new_B[1].samples[s];
  400.       p->child[1]->vtx_B[2].samples[s] = new_B[2].samples[s];
  401.  
  402.       p->child[2]->vtx_B[0].samples[s] = new_B[0].samples[s];
  403.       p->child[2]->vtx_B[1].samples[s] = corner_B[1].samples[s];
  404.       p->child[2]->vtx_B[2].samples[s] = new_B[1].samples[s];
  405.  
  406.       p->child[3]->vtx_B[0].samples[s] = new_B[2].samples[s];
  407.       p->child[3]->vtx_B[1].samples[s] = new_B[1].samples[s];
  408.       p->child[3]->vtx_B[2].samples[s] = corner_B[2].samples[s];
  409.     }
  410.  
  411.   /* Find points to subdivide along */
  412.   for (v=0;v<num_vert;v++)
  413.     vert[v] = (p->vert[v]->pos);  
  414.   Create_Subdivision_Points(vert,new_vert,p->numVert);
  415.  
  416.   if (p->class == PATCH) { /* is a quad */
  417.     /* Child 0 */
  418.     if (vtree == 0) { /* Empty vertex tree */
  419.       p->child[0]->vert[0] = Vertex_Create(vert[0],p->child[0]);
  420.       vtree = VTree_NodeCreate(p->child[0]->vert[0],(Vertex_tree *)NULL);
  421.     } else {
  422.       (void) VTree_NodeFind(vert[0],vtree,p->child[0],0);
  423.     }
  424.     (void) VTree_NodeFind(new_vert[0],vtree,p->child[0],1);
  425.     (void) VTree_NodeFind(new_vert[4],vtree,p->child[0],2);
  426.     (void) VTree_NodeFind(new_vert[3],vtree,p->child[0],3);
  427.  
  428.     /* Child 1 */
  429.     (void) VTree_NodeFind(new_vert[0],vtree,p->child[1],0);
  430.     (void) VTree_NodeFind(    vert[1],vtree,p->child[1],1);
  431.     (void) VTree_NodeFind(new_vert[1],vtree,p->child[1],2);
  432.     (void) VTree_NodeFind(new_vert[4],vtree,p->child[1],3);
  433.  
  434.     /* Child 2 */
  435.     (void) VTree_NodeFind(new_vert[4],vtree,p->child[2],0);
  436.     (void) VTree_NodeFind(new_vert[1],vtree,p->child[2],1);
  437.     (void) VTree_NodeFind(    vert[2],vtree,p->child[2],2);
  438.     (void) VTree_NodeFind(new_vert[2],vtree,p->child[2],3);
  439.  
  440.     /* Child 3 */
  441.     (void) VTree_NodeFind(new_vert[3],vtree,p->child[3],0);
  442.     (void) VTree_NodeFind(new_vert[4],vtree,p->child[3],1);
  443.     (void) VTree_NodeFind(new_vert[2],vtree,p->child[3],2);
  444.     (void) VTree_NodeFind(    vert[3],vtree,p->child[3],3);
  445.  
  446.   } else { /* is a triangle */
  447.  
  448.     /* Child 0 */
  449.     if (vtree == 0) { /* Empty vertex tree */
  450.       p->child[0]->vert[0] = Vertex_Create(vert[0],p->child[0]);
  451.       vtree = VTree_NodeCreate(p->child[0]->vert[0],(Vertex_tree *)NULL);
  452.     } else {
  453.       (void) VTree_NodeFind(vert[0],vtree,p->child[0],0);
  454.     }
  455.     /* (void) VTree_NodeFind(vert[0],vtree,p->child[0],0); */
  456.     (void) VTree_NodeFind(new_vert[0],vtree,p->child[0],1);
  457.     (void) VTree_NodeFind(new_vert[2],vtree,p->child[0],2);
  458.  
  459.     /* Child 1 */
  460.     (void) VTree_NodeFind(new_vert[0],vtree,p->child[1],0);
  461.     (void) VTree_NodeFind(new_vert[1],vtree,p->child[1],1);
  462.     (void) VTree_NodeFind(new_vert[2],vtree,p->child[1],2);
  463.  
  464.     /* Child 2 */
  465.     (void) VTree_NodeFind(new_vert[0],vtree,p->child[2],0);
  466.     (void) VTree_NodeFind(    vert[1],vtree,p->child[2],1);
  467.     (void) VTree_NodeFind(new_vert[1],vtree,p->child[2],2);
  468.  
  469.     /* Child 3 */
  470.     (void) VTree_NodeFind(new_vert[2],vtree,p->child[3],0);
  471.     (void) VTree_NodeFind(new_vert[1],vtree,p->child[3],1);
  472.     (void) VTree_NodeFind(    vert[2],vtree,p->child[3],2);
  473.   }
  474.  
  475.   dud++;
  476. }
  477.  
  478.