gfx/povray/octree.c

   1 /****************************************************************************
   2 *                   octree.c
   3 *
   4 *  This module contains all oct-tree functions for radiosity.
   5 *
   6 *  This file was written by Jim McElhiney.
   7 *
   8 *  from Persistence of Vision(tm) Ray Tracer
   9 *  Copyright 1996,1999 Persistence of Vision Team
  10 *---------------------------------------------------------------------------
  11 *  NOTICE: This source code file is provided so that users may experiment
  12 *  with enhancements to POV-Ray and to port the software to platforms other
  13 *  than those supported by the POV-Ray Team.  There are strict rules under
  14 *  which you are permitted to use this file.  The rules are in the file
  15 *  named POVLEGAL.DOC which should be distributed with this file.
  16 *  If POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17 *  Team Coordinator by email to team-coord@povray.org or visit us on the web at
  18 *  http://www.povray.org. The latest version of POV-Ray may be found at this site.
  19 *
  20 * This program is based on the popular DKB raytracer version 2.12.
  21 * DKBTrace was originally written by David K. Buck.
  22 * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23 *
  24 * Modifications by Thomas Willhalm, March 1999, used with permission
  25 *
  26 *****************************************************************************/
  27
  28 /************************************************************************
  29 *  Oct-tree routines.  Used by Radiosity calculation routies.
  30 *
  31 *  To understand the relationship between an ot_id (x,y,z,size) and
  32 *  a place in model space, you have to scale the integer values:
  33 *  The nominal space occupied is given as follows:
  34 *      fsize = pow(2,size-127);
  35 *      lox = (float)x *fsize; loy = (float)y * fsize; loz = (float)z * fsize;
  36 *      hix = lox + fsize;  hiy = loy + fsize;  hiz = loz + fsize;
  37 *  All elements within this node are guaranteed to stick outside of the
  38 *  nominal box by a distance of less than fsize/2 in x, y, and/or z.
  39 *  Therefore, the following box is guaranteed to contain all of the
  40 *  elements:
  41 *      minx = lox - fsize/2.;  miny = loy - fsize/2.;  minz = loz - fsize/2.;
  42 *      maxx = lox + fsize/2.;  maxy = loy + fsize/2.;  maxz = loz + fsize/2.;
  43 *  Implemented by and (c) 1994-6 Jim McElhiney, mcelhiney@acm.org  or 71201,1326
  44 *  All standard POV distribution rights granted.  All other rights reserved.
  45 *************************************************************************/
  46
  47 #include "frame.h"
  48 #include "vector.h"
  49 #include "povproto.h"
  50 #include "povray.h"
  51 #include "octree.h"
  52 #include "radiosit.h"
  53
  54
  55
  56 /*****************************************************************************
  57 * Local preprocessor defines
  58 ******************************************************************************/
  59
  60 #define SAFE_METHOD 1
  61 /* #define OT_DEBUG 1 */
  62
  63
  64
  65 /*****************************************************************************
  66 * Local typedefs
  67 ******************************************************************************/
  68
  69
  70
  71 /*****************************************************************************
  72 * Local variables
  73 ******************************************************************************/
  74
  75 #ifdef RADSTATS
  76 long ot_inscount = 0;
  77 long ot_nodecount = 0;
  78 long ot_blockcount = 0;
  79 long ot_minsize = 1000;
  80 long ot_maxsize = 0;
  81 #endif
  82
  83 #ifdef RADSTATS
  84 long overflows = 0;
  85 long thisloops = 0;
  86 long totloops = 0;
  87 long minloops = 1000;
  88 long maxloops = 0;
  89 #endif
  90
  91
  92
  93 /*****************************************************************************
  94 * Static functions
  95 ******************************************************************************/
  96
  97 long ot_save_node (VECTOR point, OT_ID *node);
  98 long ot_traverse (OT_NODE *subtree, long (*function)(OT_BLOCK *block, void * handle1), void * handle2);
  99 long ot_free_subtree (OT_NODE *node);
 100
 101
 102
 103
 104
 105 /*****************************************************************************
 106 *
 107 * FUNCTION
 108 *
 109 *   ot_ins
 110 *
 111 * INPUT
 112 *
 113 * OUTPUT
 114 *
 115 * RETURNS
 116 *
 117 * AUTHOUR
 118 *
 119 *   Jim McElhiney
 120 *
 121 * DESCRIPTION
 122 *
 123 *   Called with a pointer to the root pointer, because this routine can
 124 *   create a new root block higher up.
 125 *
 126 * CHANGES
 127 *
 128 *   --- 1994 : Creation.
 129 *
 130 ******************************************************************************/
 131 /* The data to store */
 132 /* The oct-tree node id at which to store */
 133 void ot_ins(OT_NODE **root_ptr, OT_BLOCK *new_block, OT_ID *new_id)
 134 {
 135   long target_size, dx, dy, dz, index;
 136   OT_NODE *temp_node, *this_node;
 137   OT_ID temp_id;
 138
 139 #ifdef RADSTATS
 140   ot_inscount++;
 141 #endif
 142
 143   /* If there is no root yet, create one.  This is a first-time-through */
 144
 145   if (*root_ptr == NULL)
 146   {
 147     *root_ptr = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
 148
 149 #ifdef RADSTATS
 150     ot_nodecount = 1;
 151 #endif
 152
 153     /* Might as well make it the right size for our first data block */
 154
 155     (*root_ptr)->Id = *new_id;
 156   }
 157
 158   /*
 159    * What if the thing we're inserting is bigger than the biggest node in the
 160    * existing tree?  Add a new top to the tree till it's big enough.
 161    */
 162
 163   while ((*root_ptr)->Id.Size < new_id->Size)
 164   {
 165     /* root too small */
 166
 167     ot_newroot(root_ptr);
 168   }
 169
 170   /*
 171    * What if the new block is the right size, but for an area of space which
 172    * does not overlap with the current tree?  New bigger root, until the
 173    * areas overlap.
 174    */
 175
 176   /* Build a temp id, like a cursor to move around with */
 177
 178   temp_id = *new_id;
 179
 180   /* First, find the parent of our new node which is as big as root */
 181
 182   while (temp_id.Size < (*root_ptr)->Id.Size)
 183   {
 184     ot_parent(&temp_id, &temp_id);
 185   }
 186
 187   while((temp_id.x != (*root_ptr)->Id.x) ||
 188         (temp_id.y != (*root_ptr)->Id.y) ||
 189         (temp_id.z != (*root_ptr)->Id.z))
 190   {
 191     /* while separate subtrees... */
 192
 193     ot_newroot(root_ptr);       /* create bigger root */
 194
 195     ot_parent(&temp_id, &temp_id);      /* and move cursor up one, too */
 196   }
 197
 198   /*
 199    * At this point, the new node is known to fit under the current tree
 200    * somewhere.  Go back down the tree to the right level, making new nodes
 201    * as you go.
 202    */
 203
 204   this_node = *root_ptr;        /* start at the root */
 205
 206   while (this_node->Id.Size > new_id->Size)
 207   {
 208     /* First, pick the node id of the child we are talking about */
 209
 210     target_size = this_node->Id.Size - 1;       /* this is the size we want */
 211
 212     temp_id = *new_id;  /* start with the new one */
 213
 214     while (temp_id.Size < target_size)
 215     {
 216       ot_parent(&temp_id, &temp_id);    /* climb up till one below here */
 217     }
 218
 219     /* Now we have to pick which child number we are talking about */
 220
 221     dx = (temp_id.x & 1) * 4;
 222     dy = (temp_id.y & 1) * 2;
 223     dz = (temp_id.z & 1);
 224
 225     index = dx + dy + dz;
 226
 227     if (this_node->Kids[index] == NULL)
 228     {
 229       /* Next level down doesn't exist yet, so create it */
 230       temp_node = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
 231
 232 #ifdef RADSTATS
 233       ot_nodecount++;
 234 #endif
 235
 236       /* Fill in the data */
 237       temp_node->Id = temp_id;
 238
 239       /* Add it onto the tree */
 240       this_node->Kids[index] = temp_node;
 241     }
 242
 243     /* Now follow it down and repeat */
 244     this_node = this_node->Kids[index];
 245   }
 246
 247   /* Finally, we're in the right place, so insert the new value */
 248   ot_list_insert(&(this_node->Values), new_block);
 249 }
 250
 251
 252
 253 /*****************************************************************************
 254 *
 255 * FUNCTION
 256 *
 257 *   ot_list_insert
 258 *
 259 * INPUT
 260 *
 261 * OUTPUT
 262 *
 263 * RETURNS
 264 *
 265 * AUTHOUR
 266 *
 267 *   Jim McElhiney
 268 *
 269 * DESCRIPTION
 270 *
 271 *   -
 272 *
 273 * CHANGES
 274 *
 275 *   --- 1994 : Creation.
 276 *
 277 ******************************************************************************/
 278
 279 void ot_list_insert(OT_BLOCK **list_head, OT_BLOCK *new_block)
 280 {
 281   new_block->next = *list_head; /* copy addr of old first block */
 282
 283   *list_head = new_block;
 284 }
 285
 286
 287
 288 /*****************************************************************************
 289 *
 290 * FUNCTION
 291 *
 292 *   ot_newroot
 293 *
 294 * INPUT
 295 *
 296 * OUTPUT
 297 *
 298 * RETURNS
 299 *
 300 * AUTHOUR
 301 *
 302 *   Jim McElhiney
 303 *
 304 * DESCRIPTION
 305 *
 306 *   Modify a tree so that it has a bigger root, owning the old root passed in.
 307 *   Note that this function is called with a POINTER TO the root pointer,
 308 *   since the root pointer will be changed.
 309 *
 310 * CHANGES
 311 *
 312 *   --- 1994 : Creation.
 313 *
 314 ******************************************************************************/
 315
 316 void ot_newroot(OT_NODE **root_ptr)
 317 {
 318   OT_NODE *newroot;
 319   long dx, dy, dz, index;
 320
 321   newroot = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
 322
 323 #ifdef RADSTATS
 324   ot_nodecount++;
 325 #endif
 326   ot_parent(&newroot->Id, &((*root_ptr)->Id));  /* sets the x/y/z/size id */
 327
 328   /*
 329    * Function:  decide which child of the new root the old root is. Theory:
 330    * x,y,z values are measured in block sizes, and are a factor of 2 smaller
 331    * at each level higher.  The parent of both (3,4,5,k) and (2,5,4,k) is
 332    * (1,2,2,k+1), so the oddness of the child's ordinates determines which
 333    * child it is, and hence the value of the index into the parent's array of
 334    * children.  First half of array (4 entries) is kids with low/even x;
 335    * First half of those is kids with low/even y (2 entries), and the very
 336    * first entry is the one with low/even everything.
 337    */
 338   dx = ((*root_ptr)->Id.x & 1) * 4;
 339   dy = ((*root_ptr)->Id.y & 1) * 2;
 340   dz = ((*root_ptr)->Id.z & 1);
 341   index = dx + dy + dz;
 342   newroot->Kids[index] = *root_ptr;
 343   *root_ptr = newroot;
 344 }
 345
 346
 347
 348 /*****************************************************************************
 349 *
 350 * FUNCTION
 351 *
 352 *   ot_dist_traverse
 353 *
 354 * INPUT
 355 *
 356 * OUTPUT
 357 *
 358 * RETURNS
 359 *
 360 * AUTHOUR
 361 *
 362 *   Jim McElhiney
 363 *
 364 * DESCRIPTION
 365 *
 366 *   Call "function(&node, handle)" for every node which is less than a node
 367 *   width from the test point. Post traverse = small stuff first = the kids
 368 *   before this node. "function(*node, handle)" must return true/false on
 369 *   whether or not to continue with further processing.  Returns 0 if
 370 *   execution was halted this way, 1 otherwise;
 371 *
 372 * CHANGES
 373 *
 374 *   --- 1994 : Creation.
 375 *
 376 ******************************************************************************/
 377
 378 long ot_dist_traverse(OT_NODE *subtree, VECTOR point, int bounce_depth, long (*function)(OT_BLOCK *block, void *handle1), void *handle)
 379 /* only those nodes with this recur depth */
 380 {
 381 #ifdef RADSTATS
 382   extern long ot_seenodecount, ot_seeblockcount;
 383
 384 #endif
 385   long i, oksofar;
 386   OT_NODE *this_node;
 387   OT_BLOCK *this_block;
 388
 389 #ifdef RADSTATS
 390   ot_seenodecount++;
 391 #endif
 392
 393   /* First, recurse to the child nodes */
 394   oksofar = 1;
 395   for (i = 0; i < 8 && oksofar; i++)
 396   {     /* for each potential kid */
 397     this_node = subtree->Kids[i];
 398     if (this_node != NULL)
 399     {   /* ...which exists */
 400       if (ot_point_in_node(point, &this_node->Id))
 401       { /* ...and in range */
 402         oksofar = ot_dist_traverse(this_node, point, bounce_depth,
 403                                    function, handle);
 404       }
 405     }
 406   }
 407
 408   /*
 409    * Now, call the specified routine for each data block hung off this tree
 410    * node
 411    */
 412
 413   /* if ( ot_point_in_node(point, &subtree->Id) ) { */
 414   {
 415     this_block = subtree->Values;
 416     while (oksofar && (this_block != NULL))
 417     {
 418 #ifdef RADSTATS
 419       if (subtree->Id.Size < 100 || subtree->Id.Size > 140 )
 420       {
 421         Debug_Info("bounds error, unreasonable size %d\n", subtree->Id.Size);
 422       }
 423       ot_seeblockcount++;
 424 #endif
 425       if ((int)this_block->Bounce_Depth == bounce_depth)
 426       {
 427         oksofar = (*function) (this_block, handle);
 428       }
 429       this_block = this_block->next;
 430     }
 431   }
 432
 433   return oksofar;
 434 }
 435
 436
 437 /*****************************************************************************
 438 *
 439 * FUNCTION
 440 *
 441 *   ot_traverse - call a function for every block in the tree.
 442 *
 443 * INPUT
 444 *
 445 * OUTPUT
 446 *
 447 * RETURNS
 448 *
 449 * AUTHOUR
 450 *
 451 *   Jim McElhiney
 452 *
 453 * DESCRIPTION
 454 *
 455 * Call "function(&block, handle)" for every block hanging off every node.
 456 *   Post traverse = small stuff first = the kids before this node.
 457 *   "function(*node, handle)" must return true/false on whether or not to
 458 *   Continue with further processing.  Returns 0 if execution
 459 *   was halted this way, 1 otherwise;
 460 *
 461 * CHANGES
 462 *
 463 *   --- Jan 1996 : Creation.
 464 *
 465 ******************************************************************************/
 466 long
 467 ot_traverse(OT_NODE *subtree, long (*function)(OT_BLOCK * bl, void * handle1), void *handle)
 468 /* Call "function(&block, handle)" for every block hanging off every node.
 469    Post traverse = small stuff first = the kids before this node.
 470    "function(*node, handle)" must return true/false on whether or not to
 471    Continue with further processing.  Returns 0 if execution
 472    was halted this way, 1 otherwise;
 473 */
 474 {
 475   long i, oksofar;
 476   OT_NODE *this_node;
 477   OT_BLOCK *this_block;
 478
 479
 480   /* First, recurse to the child nodes */
 481   oksofar = 1;
 482   if (subtree!=NULL)
 483   {
 484
 485     for (i=0; i<8 && oksofar; i++ )     /* for each potential kid */
 486     {
 487       this_node = subtree->Kids[i];
 488       if ( this_node != NULL )          /* ...which exists */
 489       {
 490         oksofar = ot_traverse(this_node, function, handle);
 491       }
 492     }
 493
 494     /* Now, call the specified routine for each data block hung off
 495        this tree node */
 496     this_block = subtree->Values;
 497     while ( oksofar  &&  (this_block != NULL) )
 498     {
 499       oksofar = (*function)(this_block, handle);
 500       this_block = this_block->next;
 501     }
 502   }
 503
 504   return oksofar;
 505 }
 506
 507
 508
 509 /*****************************************************************************
 510 *
 511 * FUNCTION
 512 *
 513 *   ot_point_in_node
 514 *
 515 * INPUT
 516 *
 517 * OUTPUT
 518 *
 519 * RETURNS
 520 *
 521 * AUTHOUR
 522 *
 523 *   Jim McElhiney
 524 *
 525 * DESCRIPTION
 526 *
 527 *   Returns true if the specified point is inside the max extent of the node
 528 *   with the specified ID.
 529 *
 530 * CHANGES
 531 *
 532 *   --- 1994 : Creation.
 533 *
 534 ******************************************************************************/
 535
 536 long ot_point_in_node(VECTOR point, OT_ID *id)
 537 {
 538   DBL sized, minx, miny, minz, lox, loy, loz, hix, hiy, hiz;
 539
 540   union
 541   {
 542     float f;
 543     long l;
 544   }
 545   size;                         /* MUST be float, NOT DBL */
 546
 547   size.l = id->Size << 23;
 548   sized = (DBL) size.f;
 549   minx = (DBL) id->x * sized - OT_BIAS;
 550   miny = (DBL) id->y * sized - OT_BIAS;
 551   minz = (DBL) id->z * sized - OT_BIAS;
 552
 553   lox = minx - sized * .5;
 554   hix = minx + sized * 1.5;
 555   loy = miny - sized * .5;
 556   hiy = miny + sized * 1.5;
 557   loz = minz - sized * .5;
 558   hiz = minz + sized * 1.5;
 559
 560   return(point[X] >= lox && point[X] < hix &&
 561          point[Y] >= loy && point[Y] < hiy &&
 562          point[Z] >= loz && point[Z] < hiz);
 563 }
 564
 565
 566
 567 /*****************************************************************************
 568 *
 569 * FUNCTION
 570 *
 571 *   ot_index_sphere
 572 *
 573 * INPUT
 574 *
 575 * OUTPUT
 576 *
 577 * RETURNS
 578 *
 579 * AUTHOUR
 580 *
 581 *   Jim McElhiney
 582 *
 583 * DESCRIPTION
 584 *
 585 *   Return the oct-tree index for an object with the specified bounding
 586 *   sphere. This is the smallest box in the tree that this object fits in with
 587 *   a maximum 50% hand-over in any (or all) directions. For example, an object
 588 *   at (.49, .49, 49) of radius 1 fits in the box (0,0,0) size 127 (length 1).
 589 *
 590 * CHANGES
 591 *
 592 *   --- 1994 : Creation.
 593 *
 594 ******************************************************************************/
 595
 596 void ot_index_sphere(VECTOR point, DBL radius, OT_ID *id)
 597 {
 598   VECTOR min_point, max_point;
 599
 600   min_point[X] = point[X] - radius;
 601   min_point[Y] = point[Y] - radius;
 602   min_point[Z] = point[Z] - radius;
 603   max_point[X] = point[X] + radius;
 604   max_point[Y] = point[Y] + radius;
 605   max_point[Z] = point[Z] + radius;
 606
 607   ot_index_box(min_point, max_point, id);
 608
 609 #ifdef RADSTATS
 610   if (id->Size < ot_minsize)
 611   {
 612     ot_minsize = id->Size;
 613   }
 614   if (id->Size > ot_maxsize)
 615   {
 616     ot_maxsize = id->Size;
 617   }
 618 #endif
 619 }
 620
 621
 622
 623
 624 /*****************************************************************************
 625 *
 626 * FUNCTION
 627 *
 628 *   ot_index_box
 629 *
 630 * INPUT
 631 *
 632 * OUTPUT
 633 *
 634 * RETURNS
 635 *
 636 * AUTHOUR
 637 *
 638 *   Jim McElhiney
 639 *
 640 * DESCRIPTION
 641 *
 642 *   Return the oct-tree index for an object with the specified bounding box.
 643 *   near_point is lox, loy, loz; far_point is hix, hiy, hiz. This is the
 644 *   smallest box in the tree that this object fits in with a maximum 50%
 645 *   hang-over in any (or all) directions. For example, an object with extent
 646 *   (-.49, -.49, -49) to (1.49, 1.49, 1.49) is the largest that fits in the
 647 *   box (0,0,0) with size 127 (length 1).
 648 *
 649 *   PORTABILITY WARNING:  this function REQUIRES IEEE single precision floating
 650 *   point format to work.  This is true of most common systems except VAXen,
 651 *   Crays, and Alpha AXP in VAX compatibility mode.  Local "float" variables
 652 *   can NOT be made double precision "double" or "DBL".
 653 *
 654 * CHANGES
 655 *
 656 *   --- 1994 : Creation.
 657 *
 658 ******************************************************************************/
 659
 660 void ot_index_box(VECTOR min_point, VECTOR max_point, OT_ID *id)
 661 {
 662   long done, idx, idy, idz;
 663   float dx, dy, dz, maxdel;     /* MUST BE "float" NOT "DBL" */
 664   DBL bsized, maxord;
 665   union
 666   {
 667     float f;
 668     long l;
 669   }
 670   convert;
 671   OT_ID base_id, test_id;
 672
 673   dx = (float) (max_point[X] - min_point[X]);
 674   dy = (float) (max_point[Y] - min_point[Y]);
 675   dz = (float) (max_point[Z] - min_point[Z]);
 676   maxdel = MAX3(dx, dy, dz);
 677
 678   /*
 679    * This hex operation does a floor to next lower power of 2, by clearing
 680    * all of the mantissa bits.  Works only on IEEE single precision floats
 681    */
 682   convert.f = maxdel;
 683   convert.l &= 0xff800000;
 684   bsized = (DBL) convert.f;
 685
 686 #ifdef SAFE_METHOD
 687
 688   /*
 689    * This block checks for the case where the node id would cause integer
 690    * overflow, since it is a small buffer far away
 691    */
 692   maxord = MAX3(fabs(min_point[X]), fabs(min_point[Y]), fabs(min_point[Z]));
 693   maxord += OT_BIAS;
 694   while (maxord / bsized > 1000000000.)
 695   {
 696 #ifdef RADSTATS
 697     overflows++;
 698 #endif
 699     bsized *= 2.;
 700   }
 701 #endif
 702
 703   /* calculate the smallest possible node that the item might fit into */
 704   base_id.x = (long) floor((min_point[X] + OT_BIAS) / bsized);
 705   base_id.y = (long) floor((min_point[Y] + OT_BIAS) / bsized);
 706   base_id.z = (long) floor((min_point[Z] + OT_BIAS) / bsized);
 707
 708   /*
 709    * This magic hex operation extracts the exponent, which gives us an
 710    * integer number suitable for labelling a range of a power of 2.  In IEEE
 711    * format, value = pow(2,exponent-127). Therefore, if our index is, say,
 712    * 129, then the item has a maximum extent of (2 to the (129-127)), or
 713    * about 4 space units.
 714    */
 715   convert.f = (float) bsized;
 716   base_id.Size = (convert.l & 0x7f800000) >> 23;
 717
 718   /* Now increase the node size until it fits for sure */
 719 #ifdef RADSTATS
 720   thisloops = 0;
 721 #endif
 722   done = 0;
 723   while (!done)
 724   {
 725     test_id.Size = base_id.Size;
 726     for (idx = 0; idx < 2 && !done; idx++)
 727     {
 728       for (idy = 0; idy < 2 && !done; idy++)
 729       {
 730         for (idz = 0; idz < 2 && !done; idz++)
 731         {
 732           test_id.x = base_id.x + idx;
 733           test_id.y = base_id.y + idy;
 734           test_id.z = base_id.z + idz;
 735           if (ot_point_in_node(min_point, &test_id) &&
 736               ot_point_in_node(max_point, &test_id))
 737           {
 738             done = 1;
 739           }
 740         }
 741       }
 742     }
 743
 744     /*
 745      * Debug_Info("looping %d,%d,%d,%d  min=%d, max=%d\n", test_id.x, test_id.y,
 746      * test_id.z, test_id.Size, ot_point_in_node(min_point, &test_id),
 747      * ot_point_in_node(max_point, &test_id));
 748      */
 749     ot_parent(&base_id, &base_id);
 750 #ifdef RADSTATS
 751     totloops++;
 752     thisloops++;
 753 #endif
 754   }
 755 #ifdef RADSTATS
 756   if (thisloops < minloops)
 757     minloops = thisloops;
 758   if (thisloops > maxloops)
 759     maxloops = thisloops;
 760 #endif
 761   *id = test_id;
 762
 763 #ifdef OT_DEBUG
 764   if (id->Size > 139)
 765   {
 766     Debug_Info("unusually large id, maxdel=%.4f, bsized=%.4f, isize=%d\n",
 767            maxdel, bsized, id->Size);
 768   }
 769 #endif
 770 }
 771
 772
 773
 774 /*****************************************************************************
 775 *
 776 * FUNCTION
 777 *
 778 *   ot_parent
 779 *
 780 * INPUT
 781 *
 782 * OUTPUT
 783 *
 784 * RETURNS
 785 *
 786 * AUTHOUR
 787 *
 788 *   Jim McElhiney
 789 *
 790 * DESCRIPTION
 791 *
 792 *   Set the x/y/z/size block ID info of dad = the parent ID of kid
 793 *
 794 * CHANGES
 795 *
 796 *   --- 1994 : Creation.
 797 *
 798 ******************************************************************************/
 799
 800 void ot_parent(OT_ID *dad_id, OT_ID  *kid_id)
 801 {
 802   dad_id->Size = kid_id->Size + 1;
 803   dad_id->x = (kid_id->x > 0) ? (kid_id->x >> 1) : (kid_id->x - 1) / 2;
 804   dad_id->y = (kid_id->y > 0) ? (kid_id->y >> 1) : (kid_id->y - 1) / 2;
 805   dad_id->z = (kid_id->z > 0) ? (kid_id->z >> 1) : (kid_id->z - 1) / 2;
 806 }
 807
 808
 809
 810 /*****************************************************************************
 811 *
 812 * FUNCTION
 813 *
 814 *   ot_save_tree
 815 *
 816 * INPUT
 817 *
 818 * OUTPUT
 819 *
 820 * RETURNS 1 for success, 0 for failure.
 821 *
 822 * AUTHOUR
 823 *
 824 *   Jim McElhiney
 825 *
 826 * DESCRIPTION
 827 *
 828 *   Given the root pointer of the in-memory cache tree, and a file descriptor
 829 *   of a file you want to write to, write the whole tree to that file.
 830 *
 831 * CHANGES
 832 *
 833 *   Jan 1996 : Creation by JDM.
 834 *
 835 * TO DO
 836 *
 837 *  Code must be written which turns Radiosity_File_*  flags on and off.
 838 *  These flags should be in the opts structure.
 839 *
 840 ******************************************************************************/
 841 long
 842 ot_save_tree(OT_NODE *root, FILE *fd)
 843 {
 844   long retval = 0;
 845
 846   if ( fd != NULL ) {
 847     retval = ot_traverse(root, ot_write_block, (void *)fd);
 848   }
 849   else
 850   {
 851     Warning(0.0, "bad radiosity cache file handle\n");
 852   }
 853
 854   return retval;
 855 }
 856
 857
 858
 859 /*****************************************************************************
 860 *
 861 * FUNCTION
 862 *
 863 *   ot_write_block
 864 *
 865 * INPUT
 866 *
 867 * OUTPUT
 868 *
 869 * RETURNS
 870 *
 871 * AUTHOUR
 872 *
 873 *   Jim McElhiney
 874 *
 875 * DESCRIPTION
 876 *
 877 *   Write one block (not a node) from the memory cache to the cache file.
 878 *
 879 * CHANGES
 880 *
 881 *   --- Jan 1996 : Creation.
 882 *
 883 ******************************************************************************/
 884 long
 885 ot_write_block/* must be passed as void * for compatibility */(OT_BLOCK *bl, void *fd)
 886 {
 887
 888   if ( bl->Bounce_Depth == 1 )
 889   {
 890     fprintf((FILE *)fd, "C%ld\t%g\t%g\t%g\t%02lx%02lx%02lx\t%.4f\t%.4f\t%.4f\t%g\t%g\t%02lx%02lx%02lx\n", /* tw */
 891       (long)bl->Bounce_Depth,
 892
 893       bl->Point[X], bl->Point[Y], bl->Point[Z],
 894       (long)((bl->S_Normal[X]+1.)*.5*254.+.499999),
 895       (long)((bl->S_Normal[Y]+1.)*.5*254.+.499999),
 896       (long)((bl->S_Normal[Z]+1.)*.5*254.+.499999),
 897
 898       bl->Illuminance[X], bl->Illuminance[Y], bl->Illuminance[Z],
 899       bl->Harmonic_Mean_Distance,
 900
 901       bl->Nearest_Distance,
 902       (long)((bl->To_Nearest_Surface[X]+1.)*.5*254.+.499999),
 903       (long)((bl->To_Nearest_Surface[Y]+1.)*.5*254.+.499999),
 904       (long)((bl->To_Nearest_Surface[Z]+1.)*.5*254.+.499999)
 905     );
 906   }
 907   return 1;
 908 }
 909
 910
 911 /*****************************************************************************
 912 *
 913 * FUNCTION
 914 *
 915 *   ot_free_tree() - get rid of the entire in-memory radiosity cache tree,
 916 *   and zero the pointer to its root.
 917 *
 918 * INPUT - pointer to the tree root pointer.
 919 *
 920 * RETURNS - success 1, failure 0
 921 *
 922 * AUTHOUR
 923 *
 924 *   Jim McElhiney
 925 *
 926 * DESCRIPTION
 927 *
 928 *   Free a complete radiosity cache tree, and all of its nodes and blocks.
 929 *   NOTE parameter is a pointer to the tree pointer...tree pointer will get zeroed.
 930 *   Example call:
 931 *      ot_free_tree(&ot_root);
 932 *   Returns 1 for success, 0 for failure.
 933 *
 934 * CHANGES
 935 *
 936 *   --- Jan 1996 : Creation.
 937 *
 938 ******************************************************************************/
 939 long
 940 ot_free_tree(OT_NODE **ppRoot)
 941 /* Free a complete radiosity cache tree, and all of its nodes and blocks.
 942    Note parameter is a pointer to the tree pointer...tree pointer will get zeroed.
 943    Example call:
 944       ot_free_tree(&ot_root);
 945    Returns 1 for success, 0 for failure.
 946 */
 947 {
 948   long all_ok;
 949
 950   all_ok = ot_free_subtree(*ppRoot);
 951   *ppRoot = NULL;
 952
 953   return all_ok;
 954 }
 955
 956
 957 /*****************************************************************************
 958 *
 959 * FUNCTION
 960 *
 961 *   ot_free_subtree - free every node from this node downwards, and all blocks
 962 *   hanging off those nodes, and then free the node which was passed.
 963 *
 964 * INPUT
 965 *
 966 * OUTPUT
 967 *
 968 * RETURNS
 969 *
 970 * AUTHOUR
 971 *
 972 *   Jim McElhiney
 973 *
 974 * DESCRIPTION
 975 *
 976 *   Set the x/y/z/size block ID info of dad = the parent ID of kid
 977 *
 978 * CHANGES
 979 *
 980 *   --- Jan 1996 : Creation.
 981 *
 982 ******************************************************************************/
 983 long
 984 ot_free_subtree(OT_NODE *subtree)
 985 /* Free this subtree.  That is, free all of its daughters, then
 986    free all of the blocks hanging off this node, then free this node itself.
 987
 988    Returns 0 if problems were encountered anywhere in the tree.
 989    Currently, this code assumes success.  If called with an invalid tree pointer,
 990    it would probably crash with a memory protection error.
 991 */
 992 {
 993   long i, oksofar;
 994   OT_NODE *this_node;
 995   OT_BLOCK *this_block, *next_block;
 996
 997   /* First, recurse to the child nodes */
 998   oksofar = 1;
 999   for (i=0; i<8 && oksofar; i++ )   /* for each potential kid */
1000   {
1001     this_node = subtree->Kids[i];
1002     if ( this_node != NULL ) {      /* ...which exists */
1003       oksofar &= ot_free_subtree(this_node);
1004     }
1005   }
1006
1007   /* Now, free each block hanging off this node. */
1008   this_block = subtree->Values;
1009   while ( this_block != NULL )
1010   {
1011     next_block = this_block->next;
1012     POV_FREE(this_block);
1013     this_block = next_block;
1014   }
1015
1016   /* Finally, free this block itself */
1017   POV_FREE(subtree);
1018
1019   return oksofar;
1020 }
1021
1022
1023 /*****************************************************************************
1024 *
1025 * FUNCTION
1026 *
1027 *   ot_read_file
1028 *
1029 * INPUT
1030 *   file descriptor handle of file (already opened) to read into memory.
1031 *
1032 * OUTPUT
1033 *
1034 * RETURNS - Success 1 / failure 0
1035 *
1036 * AUTHOUR
1037 *
1038 *   Jim McElhiney
1039 *
1040 * DESCRIPTION
1041 *
1042 *   Read in a radiosity cache file, building a tree from its values.
1043 *   If there is an existing tree, these values are added to it.
1044 *
1045 * CHANGES
1046 *
1047 *   --- Jan 1996 : Creation.
1048 *
1049 ******************************************************************************/
1050 long
1051 ot_read_file(FILE *fd)
1052 /* Read in a radiosity cache file, building a tree from its values.
1053    If there is an existing tree, these values are added to it.
1054 */
1055 {
1056   long retval, line_num, tempdepth, tx, ty, tz, goodreads;
1057   int count, goodparse, readret;
1058   DBL brightness;
1059   OT_BLOCK bl, *new_block;
1060   OT_ID id;
1061   char normal_string[30], to_nearest_string[30], line[101];
1062
1063   memset(&bl, 0, sizeof(OT_BLOCK));
1064
1065   if ( fd != NULL )
1066   {
1067     line_num = 0;
1068
1069     Make_Colour(Radiosity_Gather_Total, 0., 0., 0.);
1070     Radiosity_Gather_Total_Count = 0;
1071
1072     goodparse = 1;
1073     goodreads = 0;
1074
1075     while ( ((readret = fscanf(fd, "%99[^\n]\n", line)) == 1) && goodparse )
1076     {
1077       switch ( line[0] )
1078       {
1079         case 'B':    /* the file contains the old radiosity_brightness value */
1080         {
1081           if ( sscanf(line, "B%lf\n", &brightness) == 1 )
1082           {
1083             opts.Radiosity_Brightness = brightness;
1084           }
1085           break;
1086         }
1087         case 'P':    /* the file made it to the point that the Preview was done */
1088         {
1089           opts.Radiosity_Preview_Done = 1;
1090           break;
1091         }
1092         case 'C':
1093         {
1094           count = sscanf(line, "C%ld %lf %lf %lf %s %f %f %f %f %f %s\n", /* tw */
1095                      &tempdepth,      /* since you can't scan a short */
1096                      &bl.Point[X], &bl.Point[Y], &bl.Point[Z],
1097                      normal_string,
1098                      &bl.Illuminance[X], &bl.Illuminance[Y], &bl.Illuminance[Z],
1099                      &bl.Harmonic_Mean_Distance,
1100                      &bl.Nearest_Distance, to_nearest_string );
1101           if ( count == 11 )
1102           {
1103             bl.Bounce_Depth = (short)tempdepth;
1104
1105             /* normals aren't very critical for direction precision, so they are packed */
1106             sscanf(normal_string, "%02lx%02lx%02lx", &tx, &ty, &tz);
1107             bl.S_Normal[X] = ((double)tx * (1./ 254.))*2.-1.;
1108             bl.S_Normal[Y] = ((double)ty * (1./ 254.))*2.-1.;
1109             bl.S_Normal[Z] = ((double)tz * (1./ 254.))*2.-1.;
1110             VNormalizeEq(bl.S_Normal);
1111
1112             sscanf(to_nearest_string, "%02lx%02lx%02lx", &tx, &ty, &tz);
1113             bl.To_Nearest_Surface[X] = ((double)tx * (1./ 254.))*2.-1.;
1114             bl.To_Nearest_Surface[Y] = ((double)ty * (1./ 254.))*2.-1.;
1115             bl.To_Nearest_Surface[Z] = ((double)tz * (1./ 254.))*2.-1.;
1116             VNormalizeEq(bl.To_Nearest_Surface);
1117
1118             line_num++;
1119
1120             new_block = (OT_BLOCK *)POV_MALLOC(sizeof (OT_BLOCK), "octree node from file");
1121             if ( new_block != NULL )
1122             {
1123               memcpy(new_block, &bl, sizeof (OT_BLOCK));
1124
1125               ot_index_sphere(bl.Point, bl.Harmonic_Mean_Distance * opts.Radiosity_Error_Bound, &id);
1126               ot_ins(&ot_root, new_block, &id);
1127               goodreads++;
1128             }
1129             else
1130             {
1131               goodparse = 0;    /* allocation error, better stop now */
1132             }
1133           }
1134           break;
1135         }
1136
1137         default:
1138         {
1139           /* wrong leading character on line, just try again on next line */
1140         }
1141
1142       }   /* end switch */
1143     }     /* end while-reading loop */
1144
1145     if ( (readret != EOF)  ||  !goodparse ) {
1146       Status_Info("\nError processing the radiosity cache file at line %ld", (long)line);
1147       retval = 0;
1148     }
1149     else
1150     {
1151       if ( goodreads > 0 )
1152       {
1153         Status_Info("\nReloaded %ld values from radiosity cache file.", goodreads);
1154       }
1155       else
1156       {
1157         Status_Info("\nUnable to read any values from the radiosity cache file.");
1158       }
1159       retval = 1;
1160     }
1161   }
1162   else
1163   {
1164     retval = 0;
1165   }
1166
1167   return retval;
1168 }