examples/parallel_for/tachyon/src/objbound.cpp

   1 /*
   2     Copyright (c) 2005-2017 Intel Corporation
   3
   4     Licensed under the Apache License, Version 2.0 (the "License");
   5     you may not use this file except in compliance with the License.
   6     You may obtain a copy of the License at
   7
   8         http://www.apache.org/licenses/LICENSE-2.0
   9
  10     Unless required by applicable law or agreed to in writing, software
  11     distributed under the License is distributed on an "AS IS" BASIS,
  12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13     See the License for the specific language governing permissions and
  14     limitations under the License.
  15
  16
  17
  18
  19 */
  20
  21 /*
  22     The original source for this example is
  23     Copyright (c) 1994-2008 John E. Stone
  24     All rights reserved.
  25
  26     Redistribution and use in source and binary forms, with or without
  27     modification, are permitted provided that the following conditions
  28     are met:
  29     1. Redistributions of source code must retain the above copyright
  30        notice, this list of conditions and the following disclaimer.
  31     2. Redistributions in binary form must reproduce the above copyright
  32        notice, this list of conditions and the following disclaimer in the
  33        documentation and/or other materials provided with the distribution.
  34     3. The name of the author may not be used to endorse or promote products
  35        derived from this software without specific prior written permission.
  36
  37     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  38     OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  39     WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  40     ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  41     DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  42     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  43     OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  44     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  45     LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  46     OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  47     SUCH DAMAGE.
  48 */
  49
  50 /*
  51  * objbound.cpp - This file contains the functions to find bounding boxes
  52  *              for the various primitives
  53  */
  54
  55 #include "machine.h"
  56 #include "types.h"
  57 #include "macros.h"
  58 #include "bndbox.h"
  59
  60 #define OBJBOUND_PRIVATE
  61 #include "objbound.h"
  62
  63 static void globalbound(object ** rootlist, vector * gmin, vector * gmax) {
  64   vector min, max;
  65   object * cur;
  66
  67   if (*rootlist == NULL)  /* don't bound non-existant objects */
  68     return;
  69
  70   gmin->x =  FHUGE;   gmin->y =  FHUGE;   gmin->z =  FHUGE;
  71   gmax->x = -FHUGE;   gmax->y = -FHUGE;   gmax->z = -FHUGE;
  72
  73   cur=*rootlist;
  74   while (cur != NULL)  {  /* Go! */
  75     min.x = -FHUGE; min.y = -FHUGE; min.z = -FHUGE;
  76     max.x =  FHUGE; max.y =  FHUGE; max.z =  FHUGE;
  77
  78     cur->methods->bbox((void *) cur, &min, &max);
  79
  80     gmin->x = MYMIN( gmin->x , min.x);
  81     gmin->y = MYMIN( gmin->y , min.y);
  82     gmin->z = MYMIN( gmin->z , min.z);
  83
  84     gmax->x = MYMAX( gmax->x , max.x);
  85     gmax->y = MYMAX( gmax->y , max.y);
  86     gmax->z = MYMAX( gmax->z , max.z);
  87
  88     cur=(object *)cur->nextobj;
  89   }
  90 }
  91
  92 static int objinside(object * obj, vector * min, vector * max) {
  93   vector omin, omax;
  94
  95   if (obj == NULL)  /* non-existant object, shouldn't get here */
  96     return 0;
  97
  98   if (obj->methods->bbox((void *) obj, &omin, &omax)) {
  99     if ((min->x <= omin.x) && (min->y <= omin.y) && (min->z <= omin.z) &&
 100         (max->x >= omax.x) && (max->y >= omax.y) && (max->z >= omax.z)) {
 101       return 1;
 102     }
 103   }
 104   return 0;
 105 }
 106
 107 static int countobj(object * root) {
 108   object * cur;     /* counts the number of objects on a list */
 109   int numobj;
 110
 111   numobj=0;
 112   cur=root;
 113
 114   while (cur != NULL) {
 115     cur=(object *)cur->nextobj;
 116     numobj++;
 117   }
 118   return numobj;
 119 }
 120
 121 static void movenextobj(object * thisobj, object ** root) {
 122   object * cur, * tmp;
 123
 124   /* move the object after thisobj to the front of the object list  */
 125   /*   headed by root */
 126   if (thisobj != NULL) {
 127     if (thisobj->nextobj != NULL) {
 128       cur=(object *)thisobj->nextobj;            /* the object to be moved    */
 129       thisobj->nextobj = cur->nextobj; /* link around the moved obj */
 130       tmp=*root;                       /* store the root node       */
 131       cur->nextobj=tmp;                /* attach root to cur        */
 132       *root=cur;                       /* make cur, the new root    */
 133     }
 134   }
 135 }
 136
 137 static void octreespace(object ** rootlist, int maxoctnodes) {
 138   object * cur;
 139   vector gmin, gmax, gctr;
 140   vector cmin1, cmin2, cmin3, cmin4, cmin5, cmin6, cmin7, cmin8;
 141   vector cmax1, cmax2, cmax3, cmax4, cmax5, cmax6, cmax7, cmax8;
 142   bndbox * box1, * box2, * box3, * box4;
 143   bndbox * box5, * box6, * box7, * box8;
 144   int skipobj;
 145
 146   if (*rootlist == NULL)  /* don't subdivide non-existant data */
 147     return;
 148
 149   skipobj=0;
 150   globalbound(rootlist, &gmin, &gmax);  /* find global min and max */
 151
 152   gctr.x = ((gmax.x - gmin.x) / 2.0) + gmin.x;
 153   gctr.y = ((gmax.y - gmin.y) / 2.0) + gmin.y;
 154   gctr.z = ((gmax.z - gmin.z) / 2.0) + gmin.z;
 155
 156   cmin1=gmin;
 157   cmax1=gctr;
 158   box1 = newbndbox(cmin1, cmax1);
 159
 160   cmin2=gmin;
 161   cmin2.x=gctr.x;
 162   cmax2=gmax;
 163   cmax2.y=gctr.y;
 164   cmax2.z=gctr.z;
 165   box2 = newbndbox(cmin2, cmax2);
 166
 167   cmin3=gmin;
 168   cmin3.y=gctr.y;
 169   cmax3=gmax;
 170   cmax3.x=gctr.x;
 171   cmax3.z=gctr.z;
 172   box3 = newbndbox(cmin3, cmax3);
 173
 174   cmin4=gmin;
 175   cmin4.x=gctr.x;
 176   cmin4.y=gctr.y;
 177   cmax4=gmax;
 178   cmax4.z=gctr.z;
 179   box4 = newbndbox(cmin4, cmax4);
 180
 181   cmin5=gmin;
 182   cmin5.z=gctr.z;
 183   cmax5=gctr;
 184   cmax5.z=gmax.z;
 185   box5 = newbndbox(cmin5, cmax5);
 186
 187   cmin6=gctr;
 188   cmin6.y=gmin.y;
 189   cmax6=gmax;
 190   cmax6.y=gctr.y;
 191   box6 = newbndbox(cmin6, cmax6);
 192
 193   cmin7=gctr;
 194   cmin7.x=gmin.x;
 195   cmax7=gctr;
 196   cmax7.y=gmax.y;
 197   cmax7.z=gmax.z;
 198   box7 = newbndbox(cmin7, cmax7);
 199
 200   cmin8=gctr;
 201   cmax8=gmax;
 202   box8 = newbndbox(cmin8, cmax8);
 203
 204   cur = *rootlist;
 205   while (cur != NULL)  {
 206     if (objinside((object *)cur->nextobj, &cmin1, &cmax1)) {
 207       movenextobj(cur, &box1->objlist);
 208     }
 209     else if (objinside((object *)cur->nextobj, &cmin2, &cmax2)) {
 210       movenextobj(cur, &box2->objlist);
 211     }
 212     else if (objinside((object *)cur->nextobj, &cmin3, &cmax3)) {
 213       movenextobj(cur, &box3->objlist);
 214     }
 215     else if (objinside((object *)cur->nextobj, &cmin4, &cmax4)) {
 216       movenextobj(cur, &box4->objlist);
 217     }
 218     else if (objinside((object *)cur->nextobj, &cmin5, &cmax5)) {
 219       movenextobj(cur, &box5->objlist);
 220     }
 221     else if (objinside((object *)cur->nextobj, &cmin6, &cmax6)) {
 222       movenextobj(cur, &box6->objlist);
 223     }
 224     else if (objinside((object *)cur->nextobj, &cmin7, &cmax7)) {
 225       movenextobj(cur, &box7->objlist);
 226     }
 227     else if (objinside((object *)cur->nextobj, &cmin8, &cmax8)) {
 228       movenextobj(cur, &box8->objlist);
 229     }
 230     else {
 231       skipobj++;
 232       cur=(object *)cur->nextobj;
 233     }
 234   }
 235
 236 /* new scope, for redefinition of cur, and old */
 237   { bndbox * cur, * old;
 238   old=box1;
 239   cur=box2;
 240   if (countobj(cur->objlist) > 0) {
 241      old->nextobj=cur;
 242      globalbound(&cur->objlist, &cur->min, &cur->max);
 243      old=cur;
 244   }
 245   cur=box3;
 246   if (countobj(cur->objlist) > 0) {
 247      old->nextobj=cur;
 248      globalbound(&cur->objlist, &cur->min, &cur->max);
 249      old=cur;
 250   }
 251   cur=box4;
 252   if (countobj(cur->objlist) > 0) {
 253      old->nextobj=cur;
 254      globalbound(&cur->objlist, &cur->min, &cur->max);
 255      old=cur;
 256   }
 257   cur=box5;
 258   if (countobj(cur->objlist) > 0) {
 259      old->nextobj=cur;
 260      globalbound(&cur->objlist, &cur->min, &cur->max);
 261      old=cur;
 262   }
 263   cur=box6;
 264   if (countobj(cur->objlist) > 0) {
 265      old->nextobj=cur;
 266      globalbound(&cur->objlist, &cur->min, &cur->max);
 267      old=cur;
 268   }
 269   cur=box7;
 270   if (countobj(cur->objlist) > 0) {
 271      old->nextobj=cur;
 272      globalbound(&cur->objlist, &cur->min, &cur->max);
 273      old=cur;
 274   }
 275   cur=box8;
 276   if (countobj(cur->objlist) > 0) {
 277      old->nextobj=cur;
 278      globalbound(&cur->objlist, &cur->min, &cur->max);
 279      old=cur;
 280   }
 281
 282   old->nextobj=*rootlist;
 283
 284   if (countobj(box1->objlist) > 0) {
 285     globalbound(&box1->objlist, &box1->min, &box1->max);
 286     *rootlist=(object *) box1;
 287   }
 288   else {
 289     *rootlist=(object *) box1->nextobj;
 290   }
 291
 292   } /**** end of special cur and old scope */
 293
 294   if (countobj(box1->objlist) > maxoctnodes) {
 295     octreespace(&box1->objlist, maxoctnodes);
 296   }
 297   if (countobj(box2->objlist) > maxoctnodes) {
 298     octreespace(&box2->objlist, maxoctnodes);
 299   }
 300   if (countobj(box3->objlist) > maxoctnodes) {
 301     octreespace(&box3->objlist, maxoctnodes);
 302   }
 303   if (countobj(box4->objlist) > maxoctnodes) {
 304     octreespace(&box4->objlist, maxoctnodes);
 305   }
 306   if (countobj(box5->objlist) > maxoctnodes) {
 307     octreespace(&box5->objlist, maxoctnodes);
 308   }
 309   if (countobj(box6->objlist) > maxoctnodes) {
 310     octreespace(&box6->objlist, maxoctnodes);
 311   }
 312   if (countobj(box7->objlist) > maxoctnodes) {
 313     octreespace(&box7->objlist, maxoctnodes);
 314   }
 315   if (countobj(box8->objlist) > maxoctnodes) {
 316     octreespace(&box8->objlist, maxoctnodes);
 317   }
 318 }
 319
 320 void dividespace(int maxoctnodes, object **toplist) {
 321   bndbox * gbox;
 322   vector gmin, gmax;
 323
 324   if (countobj(*toplist) > maxoctnodes) {
 325     globalbound(toplist, &gmin, &gmax);
 326
 327     octreespace(toplist, maxoctnodes);
 328
 329     gbox = newbndbox(gmin, gmax);
 330     gbox->objlist = NULL;
 331     gbox->tex = NULL;
 332     gbox->nextobj=NULL;
 333     gbox->objlist=*toplist;
 334     *toplist=(object *) gbox;
 335   }
 336 }