gfx/povray/vbuffer.c

   1 /****************************************************************************
   2 *                   vbuffer.c
   3 *
   4 *  This module implements functions that implement the vista buffer.
   5 *
   6 *  This module was written by Dieter Bayer [DB].
   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 *
  30 *  Explanation:
  31 *
  32 *    -
  33 *
  34 *  ---
  35 *
  36 *  Mar 1994 : Creation.
  37 *
  38 *****************************************************************************/
  39
  40 #include "frame.h"
  41 #include "vector.h"
  42 #include "povproto.h"
  43 #include "bbox.h"
  44 #include "boxes.h"
  45 #include "hfield.h"
  46 #include "lighting.h"
  47 #include "matrices.h"
  48 #include "objects.h"
  49 #include "povray.h"
  50 #include "render.h"
  51 #include "triangle.h"
  52 #include "vbuffer.h"
  53 #include "vlbuffer.h"
  54 #include "userio.h"
  55
  56
  57
  58 /*****************************************************************************
  59 * Local preprocessor defines
  60 ******************************************************************************/
  61
  62
  63
  64 /*****************************************************************************
  65 * Local typedefs
  66 ******************************************************************************/
  67
  68
  69
  70 /*****************************************************************************
  71 * Local variables
  72 ******************************************************************************/
  73
  74 static DBL Distance;
  75 static MATRIX WC2VC, WC2VCinv;
  76 static VECTOR gO, gU, gV, gW;
  77
  78
  79 /* Planes for 3d-clipping. */
  80
  81 static VECTOR VIEW_VX1 = {-0.8944271910, 0.0, -0.4472135955};
  82 static VECTOR VIEW_VX2 = { 0.8944271910, 0.0, -0.4472135955};
  83 static VECTOR VIEW_VY1 = {0.0, -0.8944271910, -0.4472135955};
  84 static VECTOR VIEW_VY2 = {0.0,  0.8944271910, -0.4472135955};
  85 static DBL VIEW_DX1 = 0.4472135955;
  86 static DBL VIEW_DX2 = 0.4472135955;
  87 static DBL VIEW_DY1 = 0.4472135955;
  88 static DBL VIEW_DY2 = 0.4472135955;
  89
  90 static PROJECT_TREE_NODE *Root_Vista;
  91
  92
  93
  94 /*****************************************************************************
  95 * Static functions
  96 ******************************************************************************/
  97
  98 static void init_view_coordinates (void);
  99
 100 static void project_raw_rectangle (PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible);
 101 static void project_raw_triangle (PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible);
 102
 103 static void project_bbox (PROJECT *Project, VECTOR *P, int *visible);
 104 static void project_bounds (PROJECT *Project, BBOX *BBox, int *visible);
 105
 106 static void get_perspective_projection (OBJECT *Object, PROJECT *Project, int infinite);
 107 static void get_orthographic_projection (OBJECT *Object, PROJECT *Project, int infinite);
 108
 109 static void project_object (OBJECT *Object, PROJECT *Project);
 110
 111 static void project_box (PROJECT *Project, OBJECT *Object, int *visible);
 112 static void project_hfield (PROJECT *Project, OBJECT *Object, int *visible);
 113 static void project_triangle (PROJECT *Project, OBJECT *Object, int *visible);
 114 static void project_smooth_triangle (PROJECT *Project, OBJECT *Object, int *visible);
 115
 116 static void transform_point (VECTOR P);
 117
 118 static void project_bounding_slab (PROJECT *Project, PROJECT_TREE_NODE **Tree, BBOX_TREE *Node);
 119
 120 static int intersect_vista_tree (RAY *Ray, PROJECT_TREE_NODE *Tree, int x, INTERSECTION *Best_Intersection);
 121
 122 static void draw_projection (PROJECT *Project, int color, int *BigRed, int *BigBlue);
 123 static void draw_vista (PROJECT_TREE_NODE *Tree, int *BigRed, int *BigBlue);
 124
 125 /*****************************************************************************
 126 *
 127 * FUNCTION
 128 *
 129 *   Prune_Vista_Tree
 130 *
 131 * INPUT
 132 *
 133 *   y - Current scanline number
 134 *
 135 * OUTPUT
 136 *
 137 * RETURNS
 138 *
 139 * AUTHOR
 140 *
 141 *   Dieter Bayer
 142 *
 143 * DESCRIPTION
 144 *
 145 *   Prune vista tree, i.e. mark all nodes not on the current line inactive.
 146 *
 147 * CHANGES
 148 *
 149 *   May 1994 : Creation.
 150 *
 151 ******************************************************************************/
 152
 153 void Prune_Vista_Tree(int y)
 154 {
 155   unsigned short i;
 156   PROJECT_TREE_NODE *Node, *Sib;
 157
 158   /* If there's no vista tree then return. */
 159
 160   if (Root_Vista == NULL)
 161   {
 162     return;
 163   }
 164
 165   Node_Queue->QSize = 0;
 166
 167   Increase_Counter(stats[VBuffer_Tests]);
 168
 169   if ((y < Root_Vista->Project.y1) || (y > Root_Vista->Project.y2))
 170   {
 171     /* Root doesn't lie on current line --> prune root */
 172
 173     Root_Vista->is_leaf |= PRUNE_TEMPORARY;
 174   }
 175   else
 176   {
 177     /* Root lies on current line --> unprune root */
 178
 179     Increase_Counter(stats[VBuffer_Tests_Succeeded]);
 180
 181     Root_Vista->is_leaf &= ~PRUNE_TEMPORARY;
 182
 183     Node_Queue->Queue[(Node_Queue->QSize)++] = Root_Vista;
 184   }
 185
 186   while (Node_Queue->QSize > 0)
 187   {
 188     Node = Node_Queue->Queue[--(Node_Queue->QSize)];
 189
 190     if (Node->is_leaf & TRUE)
 191     {
 192       Increase_Counter(stats[VBuffer_Tests]);
 193
 194       if ((y < Node->Project.y1) || (y > Node->Project.y2))
 195       {
 196         /* Leaf doesn't lie on current line --> prune leaf */
 197
 198         Node->is_leaf |= PRUNE_TEMPORARY;
 199       }
 200       else
 201       {
 202         /* Leaf lies on current line --> unprune leaf */
 203
 204         Increase_Counter(stats[VBuffer_Tests_Succeeded]);
 205
 206         Node->is_leaf &= ~PRUNE_TEMPORARY;
 207       }
 208     }
 209     else
 210     {
 211       /* Check siblings of the node */
 212
 213       for (i = 0; i < Node->Entries; i++)
 214       {
 215         Sib = Node->Entry[i];
 216
 217         Increase_Counter(stats[VBuffer_Tests]);
 218
 219         if ((y < Sib->Project.y1) || (y > Sib->Project.y2))
 220         {
 221           /* Sibling doesn't lie on current line --> prune sibling */
 222
 223           Sib->is_leaf |= PRUNE_TEMPORARY;
 224         }
 225         else
 226         {
 227           /* Sibling lies on current line --> unprune sibling */
 228
 229           Increase_Counter(stats[VBuffer_Tests_Succeeded]);
 230
 231           Sib->is_leaf &= ~PRUNE_TEMPORARY;
 232
 233           /* Add sibling to list */
 234
 235           /* Reallocate queue if it's too small. */
 236
 237           Reinitialize_VLBuffer_Code();
 238
 239           Node_Queue->Queue[(Node_Queue->QSize)++] = Sib;
 240         }
 241       }
 242     }
 243   }
 244 }
 245
 246
 247
 248 /*****************************************************************************
 249 *
 250 * FUNCTION
 251 *
 252 *   Trace_Primary_Ray
 253 *
 254 * INPUT
 255 *
 256 *   Ray    - Current ray
 257 *   Colour - Ray's colour
 258 *   x      - Current x-coordinate
 259 *
 260 * OUTPUT
 261 *
 262 *   colour
 263 *
 264 * RETURNS
 265 *
 266 * AUTHOR
 267 *
 268 *   Dieter Bayer
 269 *
 270 * DESCRIPTION
 271 *
 272 *   Trace a primary ray using the vista tree.
 273 *
 274 * CHANGES
 275 *
 276 *   May 1994 : Creation.
 277 *
 278 *   Nov 1994 : Rearranged calls to Fog, Ranibow and Skyblend.
 279 *              Added call to Atmosphere for atmospheric effects. [DB]
 280 *
 281 *   Jan 1995 : Set intersection depth to Max_Distance for infinte rays. [DB]
 282 *   Jul 1995 : Added code to support alpha channel. [DB]
 283 *
 284 ******************************************************************************/
 285
 286 void Trace_Primary_Ray (RAY *Ray, COLOUR Colour, DBL Weight, int x)
 287 {
 288   int i, Intersection_Found, all_hollow;
 289   INTERSECTION Best_Intersection;
 290
 291   COOPERATE_0
 292   Increase_Counter(stats[Number_Of_Rays]);
 293
 294   /* Transmittance has to be 1 to make alpha channel output to work. [DB] */
 295
 296   Make_ColourA(Colour, 0.0, 0.0, 0.0, 0.0, 1.0);
 297
 298   if ((Trace_Level > Max_Trace_Level) || (Weight < ADC_Bailout))
 299   {
 300     if (Weight < ADC_Bailout)
 301     {
 302       Increase_Counter(stats[ADC_Saves]);
 303     }
 304
 305     return;
 306   }
 307
 308   if (Trace_Level > Highest_Trace_Level)
 309   {
 310     Highest_Trace_Level = Trace_Level;
 311   }
 312
 313   Best_Intersection.Depth = BOUND_HUGE;
 314
 315   /* What objects does this ray intersect? */
 316
 317   Intersection_Found = intersect_vista_tree(Ray, Root_Vista, x, &Best_Intersection);
 318
 319   if (Intersection_Found)
 320   {
 321     Determine_Apparent_Colour(&Best_Intersection, Colour, Ray, 1.0);
 322   }
 323   else
 324   {
 325       /* Infinite ray, set intersection distance. */
 326
 327       Best_Intersection.Depth = Max_Distance;
 328
 329       Do_Infinite_Atmosphere(Ray, Colour);
 330   }
 331
 332   /* Test if all contained objects are hollow. */
 333
 334   all_hollow = TRUE;
 335
 336   if (Ray->Index > -1)
 337   {
 338     for (i = 0; i <= Ray->Index; i++)
 339     {
 340       if (!Ray->Interiors[i]->hollow)
 341       {
 342         all_hollow = FALSE;
 343
 344         break;
 345       }
 346     }
 347   }
 348
 349   /* Apply finite atmospheric effects. */
 350   if (all_hollow && (opts.Quality_Flags & Q_VOLUME))
 351   {
 352     Do_Finite_Atmosphere(Ray, &Best_Intersection, Colour, FALSE);
 353   }
 354 }
 355
 356
 357
 358 /*****************************************************************************
 359 *
 360 * FUNCTION
 361 *
 362 *   intersect_vista_tree
 363 *
 364 * INPUT
 365 *
 366 *   Ray               - Primary ray
 367 *   Tree              - Vista tree's top-node
 368 *   x                 - Current x-coordinate
 369 *   Best_Intersection - Intersection found
 370 *
 371 * OUTPUT
 372 *
 373 *   Best_Intersection
 374 *
 375 * RETURNS
 376 *
 377 * AUTHOR
 378 *
 379 *   Dieter Bayer
 380 *
 381 * DESCRIPTION
 382 *
 383 *   Intersect a PRIMARY ray with the vista tree
 384 *   (tree pruning is used can be primary ray!!!).
 385 *
 386 * CHANGES
 387 *
 388 *   May 1994 : Creation.
 389 *
 390 ******************************************************************************/
 391
 392 static int intersect_vista_tree(RAY *Ray, PROJECT_TREE_NODE *Tree, int x, INTERSECTION *Best_Intersection)
 393 {
 394   INTERSECTION New_Intersection;
 395   unsigned short i;
 396   /* unsigned size; */ /* tw, mtg */
 397   int Found;
 398   RAYINFO rayinfo;
 399   DBL key;
 400   BBOX_TREE *BBox_Node;
 401   PROJECT_TREE_NODE *Node;
 402
 403   /* If there's no vista tree then return. */
 404
 405   if (Tree == NULL)
 406   {
 407     return(FALSE);
 408   }
 409
 410   /* Start with an empty priority queue */
 411
 412   VLBuffer_Queue->QSize = 0;
 413
 414   Found = FALSE;
 415
 416 #ifdef BBOX_EXTRA_STATS
 417   Increase_Counter(stats[totalQueueResets]);
 418 #endif
 419
 420   /* Descend tree. */
 421
 422   Node_Queue->QSize = 0;
 423
 424   /* Create the direction vectors for this ray */
 425
 426   Create_Rayinfo(Ray, &rayinfo);
 427
 428   /* Fill the priority queue with all possible candidates */
 429
 430   /* Check root */
 431
 432   Increase_Counter(stats[VBuffer_Tests]);
 433
 434   if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
 435   {
 436     Increase_Counter(stats[VBuffer_Tests_Succeeded]);
 437
 438     Node_Queue->Queue[(Node_Queue->QSize)++] = Tree;
 439   }
 440
 441   while (Node_Queue->QSize > 0)
 442   {
 443     Tree = Node_Queue->Queue[--(Node_Queue->QSize)];
 444
 445     switch (Tree->is_leaf)
 446     {
 447       case FALSE:
 448
 449         /* Check siblings of the unpruned node in 2d */
 450
 451         for (i = 0; i < Tree->Entries; i++)
 452         {
 453           Node = Tree->Entry[i];
 454
 455           /* Check unpruned siblings only */
 456
 457           if (Node->is_leaf < PRUNE_CHECK)
 458           {
 459             Increase_Counter(stats[VBuffer_Tests]);
 460
 461             if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
 462             {
 463               /* Add node to node queue. */
 464
 465               Increase_Counter(stats[VBuffer_Tests_Succeeded]);
 466
 467               /* Reallocate queue if it's too small. */
 468
 469               Reinitialize_VLBuffer_Code();
 470
 471               Node_Queue->Queue[(Node_Queue->QSize)++] = Node;
 472             }
 473           }
 474         }
 475
 476     break;
 477
 478       case TRUE:
 479
 480         /* Unpruned leaf --> test object's bounding box in 3d */
 481
 482         Check_And_Enqueue(VLBuffer_Queue,
 483           ((PROJECT_TREE_LEAF *)Tree)->Node,
 484           &(((PROJECT_TREE_LEAF *)Tree)->Node->BBox),
 485           &rayinfo);
 486
 487         break;
 488
 489    /* default:
 490
 491         The node/leaf is pruned and needn't be checked */
 492
 493     }
 494   }
 495
 496   /* Now test the candidates in the priority queue */
 497
 498   while (VLBuffer_Queue->QSize > 0)
 499   {
 500     Priority_Queue_Delete(VLBuffer_Queue, &key, &BBox_Node);
 501
 502     if (key > Best_Intersection->Depth)
 503       break;
 504
 505     if (Intersection(&New_Intersection, (OBJECT *)BBox_Node->Node, Ray))
 506     {
 507       if (New_Intersection.Depth < Best_Intersection->Depth)
 508       {
 509         *Best_Intersection = New_Intersection;
 510         Found = TRUE;
 511       }
 512     }
 513   }
 514
 515   return(Found);
 516 }
 517
 518
 519
 520 /*****************************************************************************
 521 *
 522 * FUNCTION
 523 *
 524 *   project_raw_triangle
 525 *
 526 * INPUT
 527 *
 528 *   Project    - Triangle's projection
 529 *   P1, P2, P3 - Triangle's edges
 530 *   visible    - Flag if triangle is visible
 531 *
 532 * OUTPUT
 533 *
 534 *   Project, visible
 535 *
 536 * RETURNS
 537 *
 538 * AUTHOR
 539 *
 540 *   Dieter Bayer
 541 *
 542 * DESCRIPTION
 543 *
 544 *   Project a triangle onto the screen.
 545 *
 546 * CHANGES
 547 *
 548 *   May 1994 : Creation.
 549 *
 550 ******************************************************************************/
 551
 552 static void project_raw_triangle (PROJECT *Project, VECTOR P1, VECTOR  P2, VECTOR  P3, int *visible)
 553 {
 554   VECTOR Points[MAX_CLIP_POINTS];
 555   int i, number;
 556   int x, y;
 557
 558   Assign_Vector(Points[0], P1);
 559   Assign_Vector(Points[1], P2);
 560   Assign_Vector(Points[2], P3);
 561
 562   number = 3;
 563
 564   /* Clip triangle only if some quick tests say it's necessary.
 565      Assuming that only a few triangles need clipping this saves some time.
 566      (I don't need to write fabs(1+P?[Z]) since the tests succeed anyway if
 567       P?[Z] < -1. Hope the compiler doesn't change the tests' order!) */
 568
 569   if ((P1[Z] < -1.0) || (P2[Z] < -1.0) || (P3[Z] < -1.0) ||
 570       (fabs(P1[X]) > 0.5*(1.0+P1[Z])) || (fabs(P1[Y]) > 0.5*(1.0+P1[Z])) ||
 571       (fabs(P2[X]) > 0.5*(1.0+P2[Z])) || (fabs(P2[Y]) > 0.5*(1.0+P2[Z])) ||
 572       (fabs(P3[X]) > 0.5*(1.0+P3[Z])) || (fabs(P3[Y]) > 0.5*(1.0+P3[Z])))
 573   {
 574     Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
 575                                   VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
 576   }
 577
 578   if (number)
 579   {
 580     for (i = 0; i < number; i++)
 581     {
 582       if (Points[i][Z] < -1.0 + EPSILON)
 583       {
 584         Points[i][X] = Points[i][Y] = 0.0;
 585       }
 586       else
 587       {
 588         Points[i][X] /= 1.0 + Points[i][Z];
 589         Points[i][Y] /= 1.0 + Points[i][Z];
 590       }
 591
 592       x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * Points[i][X]);
 593       y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * Points[i][Y]);
 594
 595       if (x < Project->x1) Project->x1 = x;
 596       if (x > Project->x2) Project->x2 = x;
 597       if (y < Project->y1) Project->y1 = y;
 598       if (y > Project->y2) Project->y2 = y;
 599     }
 600
 601     *visible = TRUE;
 602   }
 603 }
 604
 605
 606
 607 /*****************************************************************************
 608 *
 609 * FUNCTION
 610 *
 611 *   project_raw_rectangle
 612 *
 613 * INPUT
 614 *
 615 *   Project        - Rectangle's projection
 616 *   P1, P2, P3, P4 - Rectangle's edges
 617 *   visible        - Flag if rectangle is visible
 618 *
 619 * OUTPUT
 620 *
 621 *   Project, visible
 622 *
 623 * RETURNS
 624 *
 625 * AUTHOR
 626 *
 627 *   Dieter Bayer
 628 *
 629 * DESCRIPTION
 630 *
 631 *   Project a rectangle onto the screen.
 632 *
 633 * CHANGES
 634 *
 635 *   May 1994 : Creation.
 636 *
 637 ******************************************************************************/
 638
 639 static void project_raw_rectangle(PROJECT *Project, VECTOR P1, VECTOR  P2, VECTOR  P3, VECTOR  P4, int *visible)
 640 {
 641   VECTOR Points[MAX_CLIP_POINTS];
 642   int i, number;
 643   int x, y;
 644
 645   Assign_Vector(Points[0], P1);
 646   Assign_Vector(Points[1], P2);
 647   Assign_Vector(Points[2], P3);
 648   Assign_Vector(Points[3], P4);
 649
 650   number = 4;
 651
 652   Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
 653                                 VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
 654
 655   if (number)
 656   {
 657     for (i = 0; i < number; i++)
 658     {
 659       if (Points[i][Z] < -1.0 + EPSILON)
 660       {
 661         Points[i][X] = Points[i][Y] = 0.0;
 662       }
 663       else
 664       {
 665         Points[i][X] /= 1.0 + Points[i][Z];
 666         Points[i][Y] /= 1.0 + Points[i][Z];
 667       }
 668
 669       x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * Points[i][X]);
 670       y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * Points[i][Y]);
 671
 672       if (x < Project->x1) Project->x1 = x;
 673       if (x > Project->x2) Project->x2 = x;
 674       if (y < Project->y1) Project->y1 = y;
 675       if (y > Project->y2) Project->y2 = y;
 676     }
 677
 678     *visible = TRUE;
 679   }
 680 }
 681
 682
 683
 684
 685 /*****************************************************************************
 686 *
 687 * FUNCTION
 688 *
 689 *   project_bbox
 690 *
 691 * INPUT
 692 *
 693 *   Project - Box's projection
 694 *   P       - Box's edges
 695 *   visible - Flag if box is visible
 696 *
 697 * OUTPUT
 698 *
 699 *   Project, visible
 700 *
 701 * RETURNS
 702 *
 703 * AUTHOR
 704 *
 705 *   Dieter Bayer
 706 *
 707 * DESCRIPTION
 708 *
 709 *   Project a box onto the screen.
 710 *
 711 * CHANGES
 712 *
 713 *   May 1994 : Creation.
 714 *
 715 ******************************************************************************/
 716
 717 static void project_bbox(PROJECT *Project, VECTOR *P, int *visible)
 718 {
 719   int vis, i, x, y;
 720   PROJECT New;
 721
 722   New.x1 = MAX_BUFFER_ENTRY;
 723   New.x2 = MIN_BUFFER_ENTRY;
 724   New.y1 = MAX_BUFFER_ENTRY;
 725   New.y2 = MIN_BUFFER_ENTRY;
 726
 727   vis = FALSE;
 728
 729   /* Check if all points lie "in front" of the viewer. */
 730
 731   if ((P[0][Z] > -1.0) && (P[1][Z] > -1.0) && (P[2][Z] > -1.0) && (P[3][Z] > -1.0) &&
 732       (P[4][Z] > -1.0) && (P[5][Z] > -1.0) && (P[6][Z] > -1.0) && (P[7][Z] > -1.0))
 733   {
 734     /* Check if all points lie inside the "viewing pyramid". */
 735
 736     if ((fabs(P[0][X]) <= 0.5*(1.0+P[0][Z])) && (fabs(P[1][X]) <= 0.5*(1.0+P[1][Z])) &&
 737         (fabs(P[2][X]) <= 0.5*(1.0+P[2][Z])) && (fabs(P[3][X]) <= 0.5*(1.0+P[3][Z])) &&
 738         (fabs(P[4][X]) <= 0.5*(1.0+P[4][Z])) && (fabs(P[5][X]) <= 0.5*(1.0+P[5][Z])) &&
 739         (fabs(P[6][X]) <= 0.5*(1.0+P[6][Z])) && (fabs(P[7][X]) <= 0.5*(1.0+P[7][Z])) &&
 740         (fabs(P[0][Y]) <= 0.5*(1.0+P[0][Z])) && (fabs(P[1][Y]) <= 0.5*(1.0+P[1][Z])) &&
 741         (fabs(P[2][Y]) <= 0.5*(1.0+P[2][Z])) && (fabs(P[3][Y]) <= 0.5*(1.0+P[3][Z])) &&
 742         (fabs(P[4][Y]) <= 0.5*(1.0+P[4][Z])) && (fabs(P[5][Y]) <= 0.5*(1.0+P[5][Z])) &&
 743         (fabs(P[6][Y]) <= 0.5*(1.0+P[6][Z])) && (fabs(P[7][Y]) <= 0.5*(1.0+P[7][Z])))
 744     {
 745       /* No clipping is needed. Just project the points. */
 746
 747       vis = TRUE;
 748
 749       for (i = 0; i < 8; i++)
 750       {
 751         if (P[i][Z] < -1.0 + EPSILON)
 752         {
 753           P[i][X] = P[i][Y] = 0.0;
 754         }
 755         else
 756         {
 757           P[i][X] /= 1.0 + P[i][Z];
 758           P[i][Y] /= 1.0 + P[i][Z];
 759         }
 760
 761         x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * P[i][X]);
 762         y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * P[i][Y]);
 763
 764         if (x < New.x1) New.x1 = x;
 765         if (x > New.x2) New.x2 = x;
 766         if (y < New.y1) New.y1 = y;
 767         if (y > New.y2) New.y2 = y;
 768       }
 769     }
 770   }
 771
 772   if (!vis)
 773   {
 774     project_raw_rectangle(&New, P[0], P[1], P[3], P[2], &vis);
 775     project_raw_rectangle(&New, P[4], P[5], P[7], P[6], &vis);
 776     project_raw_rectangle(&New, P[0], P[1], P[5], P[4], &vis);
 777     project_raw_rectangle(&New, P[2], P[3], P[7], P[6], &vis);
 778     project_raw_rectangle(&New, P[1], P[3], P[7], P[5], &vis);
 779     project_raw_rectangle(&New, P[0], P[2], P[6], P[4], &vis);
 780   }
 781
 782   if (vis)
 783   {
 784     if (New.x1 > Project->x1) Project->x1 = New.x1;
 785     if (New.x2 < Project->x2) Project->x2 = New.x2;
 786     if (New.y1 > Project->y1) Project->y1 = New.y1;
 787     if (New.y2 < Project->y2) Project->y2 = New.y2;
 788     *visible = TRUE;
 789   }
 790 }
 791
 792
 793
 794 /*****************************************************************************
 795 *
 796 * FUNCTION
 797 *
 798 *   project_bounds
 799 *
 800 * INPUT
 801 *
 802 *   Project - Bounding box's projection
 803 *   BBox    - Bounding box
 804 *   visible - Flag if bounding box is visible
 805 *
 806 * OUTPUT
 807 *
 808 *   Project, visible
 809 *
 810 * RETURNS
 811 *
 812 * AUTHOR
 813 *
 814 *   Dieter Bayer
 815 *
 816 * DESCRIPTION
 817 *
 818 *   Project a bounding box onto the screen.
 819 *
 820 * CHANGES
 821 *
 822 *   May 1994 : Creation.
 823 *
 824 ******************************************************************************/
 825
 826 static void project_bounds(PROJECT *Project, BBOX *BBox, int *visible)
 827 {
 828   int i;
 829   VECTOR P[8];
 830
 831   for (i = 0; i<8; i++)
 832   {
 833     P[i][X] = ((i & 1) ? BBox->Lengths[X] : 0.0) + BBox->Lower_Left[X];
 834     P[i][Y] = ((i & 2) ? BBox->Lengths[Y] : 0.0) + BBox->Lower_Left[Y];
 835     P[i][Z] = ((i & 4) ? BBox->Lengths[Z] : 0.0) + BBox->Lower_Left[Z];
 836
 837     transform_point(P[i]);
 838   }
 839
 840   project_bbox(Project, P, visible);
 841 }
 842
 843
 844
 845 /*****************************************************************************
 846 *
 847 * FUNCTION
 848 *
 849 *   project_box
 850 *
 851 * INPUT
 852 *
 853 *   Project - Projection
 854 *   Object  - Object
 855 *   visible - Flag if object is visible
 856 *
 857 * OUTPUT
 858 *
 859 *   Project, visible
 860 *
 861 * RETURNS
 862 *
 863 * AUTHOR
 864 *
 865 *   Dieter Bayer
 866 *
 867 * DESCRIPTION
 868 *
 869 *   Project a box onto the screen.
 870 *
 871 * CHANGES
 872 *
 873 *   May 1994 : Creation.
 874 *
 875 ******************************************************************************/
 876
 877 static void project_box(PROJECT *Project, OBJECT *Object, int *visible)
 878 {
 879   int i;
 880   VECTOR P[8];
 881   BOX *box;
 882
 883   box = (BOX *)Object;
 884
 885   for (i = 0; i<8; i++)
 886   {
 887     P[i][X] = (i & 1) ? box->bounds[1][X] : box->bounds[0][X];
 888     P[i][Y] = (i & 2) ? box->bounds[1][Y] : box->bounds[0][Y];
 889     P[i][Z] = (i & 4) ? box->bounds[1][Z] : box->bounds[0][Z];
 890
 891     if (box->Trans != NULL)
 892     {
 893       MTransPoint(P[i], P[i], box->Trans);
 894     }
 895
 896     transform_point(P[i]);
 897   }
 898
 899   project_bbox(Project, P, visible);
 900 }
 901
 902
 903
 904 /*****************************************************************************
 905 *
 906 * FUNCTION
 907 *
 908 *   project_hfield
 909 *
 910 * INPUT
 911 *
 912 *   Project - Projection
 913 *   Object  - Object
 914 *   visible - Flag if object is visible
 915 *
 916 * OUTPUT
 917 *
 918 *   Project, visible
 919 *
 920 * RETURNS
 921 *
 922 * AUTHOR
 923 *
 924 *   Dieter Bayer
 925 *
 926 * DESCRIPTION
 927 *
 928 *   Project the bounding box of a height field onto the screen.
 929 *
 930 * CHANGES
 931 *
 932 *   May 1994 : Creation.
 933 *
 934 ******************************************************************************/
 935
 936 static void project_hfield(PROJECT *Project, OBJECT *Object, int *visible)
 937 {
 938   int i;
 939   VECTOR P[8];
 940   HFIELD *hfield;
 941
 942   hfield = (HFIELD *)Object;
 943
 944   for (i = 0; i<8; i++)
 945   {
 946     Assign_Vector(P[i], hfield->bounding_box->bounds[0]);
 947
 948     P[i][X] = (i & 1) ? hfield->bounding_box->bounds[1][X] : hfield->bounding_box->bounds[0][X];
 949     P[i][Y] = (i & 2) ? hfield->bounding_box->bounds[1][Y] : hfield->bounding_box->bounds[0][Y];
 950     P[i][Z] = (i & 4) ? hfield->bounding_box->bounds[1][Z] : hfield->bounding_box->bounds[0][Z];
 951
 952     if (hfield->Trans != NULL)
 953     {
 954       MTransPoint(P[i], P[i], hfield->Trans);
 955     }
 956
 957     transform_point(P[i]);
 958   }
 959
 960   project_bbox(Project, P, visible);
 961 }
 962
 963
 964
 965 /*****************************************************************************
 966 *
 967 * FUNCTION
 968 *
 969 *   project_triangle
 970 *
 971 * INPUT
 972 *
 973 *   Project - Projection
 974 *   Object  - Object
 975 *   visible - Flag if object is visible
 976 *
 977 * OUTPUT
 978 *
 979 *   Project, visible
 980 *
 981 * RETURNS
 982 *
 983 * AUTHOR
 984 *
 985 *   Dieter Bayer
 986 *
 987 * DESCRIPTION
 988 *
 989 *   Project a triangle onto the screen.
 990 *
 991 * CHANGES
 992 *
 993 *   May 1994 : Creation.
 994 *
 995 ******************************************************************************/
 996
 997 static void project_triangle(PROJECT *Project, OBJECT *Object, int *visible)
 998 {
 999   int i, vis;
1000   VECTOR P[3];
1001   PROJECT New;
1002
1003   New.x1 = MAX_BUFFER_ENTRY;
1004   New.x2 = MIN_BUFFER_ENTRY;
1005   New.y1 = MAX_BUFFER_ENTRY;
1006   New.y2 = MIN_BUFFER_ENTRY;
1007
1008   Assign_Vector(P[0], ((TRIANGLE *)Object)->P1);
1009   Assign_Vector(P[1], ((TRIANGLE *)Object)->P2);
1010   Assign_Vector(P[2], ((TRIANGLE *)Object)->P3);
1011
1012   for (i = 0; i < 3; i++)
1013   {
1014     transform_point(P[i]);
1015   }
1016
1017   vis = FALSE;
1018
1019   project_raw_triangle(&New, P[0], P[1], P[2], &vis);
1020
1021   if (vis)
1022   {
1023     if (New.x1 > Project->x1) Project->x1 = New.x1;
1024     if (New.x2 < Project->x2) Project->x2 = New.x2;
1025     if (New.y1 > Project->y1) Project->y1 = New.y1;
1026     if (New.y2 < Project->y2) Project->y2 = New.y2;
1027
1028     *visible = TRUE;
1029   }
1030 }
1031
1032
1033
1034 /*****************************************************************************
1035 *
1036 * FUNCTION
1037 *
1038 *   project_smooth_triangle
1039 *
1040 * INPUT
1041 *
1042 *   Project - Projection
1043 *   Object  - Object
1044 *   visible - Flag if object is visible
1045 *
1046 * OUTPUT
1047 *
1048 *   Project, visible
1049 *
1050 * RETURNS
1051 *
1052 * AUTHOR
1053 *
1054 *   Dieter Bayer
1055 *
1056 * DESCRIPTION
1057 *
1058 *   Project a smooth triangle onto the screen.
1059 *
1060 * CHANGES
1061 *
1062 *   May 1994 : Creation.
1063 *
1064 ******************************************************************************/
1065
1066 static void project_smooth_triangle(PROJECT *Project, OBJECT *Object, int *visible)
1067 {
1068   int i, vis;
1069   VECTOR P[3];
1070   PROJECT New;
1071
1072   New.x1 = MAX_BUFFER_ENTRY;
1073   New.x2 = MIN_BUFFER_ENTRY;
1074   New.y1 = MAX_BUFFER_ENTRY;
1075   New.y2 = MIN_BUFFER_ENTRY;
1076
1077   Assign_Vector(P[0], ((SMOOTH_TRIANGLE *)Object)->P1);
1078   Assign_Vector(P[1], ((SMOOTH_TRIANGLE *)Object)->P2);
1079   Assign_Vector(P[2], ((SMOOTH_TRIANGLE *)Object)->P3);
1080
1081   for (i = 0; i < 3; i++)
1082   {
1083     transform_point(P[i]);
1084   }
1085
1086   vis = FALSE;
1087
1088   project_raw_triangle(&New, P[0], P[1], P[2], &vis);
1089
1090   if (vis)
1091   {
1092     if (New.x1 > Project->x1) Project->x1 = New.x1;
1093     if (New.x2 < Project->x2) Project->x2 = New.x2;
1094     if (New.y1 > Project->y1) Project->y1 = New.y1;
1095     if (New.y2 < Project->y2) Project->y2 = New.y2;
1096
1097     *visible = TRUE;
1098   }
1099 }
1100
1101
1102
1103 /*****************************************************************************
1104 *
1105 * FUNCTION
1106 *
1107 *   transform_point
1108 *
1109 * INPUT
1110 *
1111 *   P - Point to transform
1112 *
1113 * OUTPUT
1114 *
1115 *   P
1116 *
1117 * RETURNS
1118 *
1119 * AUTHOR
1120 *
1121 *   Dieter Bayer
1122 *
1123 * DESCRIPTION
1124 *
1125 *   Transform a point from the world coordinate system to the viewer's
1126 *   coordinate system.
1127 *
1128 * CHANGES
1129 *
1130 *   May 1994 : Creation.
1131 *
1132 ******************************************************************************/
1133
1134 static void transform_point(VECTOR P)
1135 {
1136   DBL x,y,z;
1137
1138   x = P[X] - gO[X];
1139   y = P[Y] - gO[Y];
1140   z = P[Z] - gO[Z];
1141
1142   P[X] = gU[X] * x + gU[Y] * y + gU[Z] * z;
1143   P[Y] = gV[X] * x + gV[Y] * y + gV[Z] * z;
1144   P[Z] = gW[X] * x + gW[Y] * y + gW[Z] * z;
1145 }
1146
1147
1148
1149 /*****************************************************************************
1150 *
1151 * FUNCTION
1152 *
1153 *   Init_View_Coordinates
1154 *
1155 * INPUT
1156 *
1157 * OUTPUT
1158 *
1159 * RETURNS
1160 *
1161 * AUTHOR
1162 *
1163 *   Dieter Bayer
1164 *
1165 * DESCRIPTION
1166 *
1167 *   Init the matrices and vectors used to transform a point from
1168 *   the world coordinate system to the viewer's coordinate system.
1169 *
1170 * CHANGES
1171 *
1172 *   May 1994 : Creation.
1173 *
1174 ******************************************************************************/
1175
1176 static void init_view_coordinates()
1177 {
1178   DBL k1, k2, k3, up_length, right_length;
1179   MATRIX A, B;
1180
1181   Assign_Vector(gU, Frame.Camera->Right);
1182   Assign_Vector(gV, Frame.Camera->Up);
1183   Assign_Vector(gW, Frame.Camera->Direction);
1184
1185   VAdd (gO, Frame.Camera->Location, Frame.Camera->Direction);
1186
1187   VNormalize(gU,gU);
1188   VNormalize(gV,gV);
1189   VNormalize(gW,gW);
1190
1191   VDot(k1, gU, gV);
1192   VDot(k2, gU, gW);
1193   VDot(k3, gV, gW);
1194
1195   if ((fabs(k1) > EPSILON) || (fabs(k2) > EPSILON) || (fabs(k3) > EPSILON))
1196   {
1197     Error("Cannot use non-perpendicular camera vectors with vista buffer.\n");
1198   }
1199
1200   VLength (Distance, Frame.Camera->Direction);
1201
1202   VLength (up_length, Frame.Camera->Up);
1203   VLength (right_length, Frame.Camera->Right);
1204
1205   VScaleEq (gU, 1.0/right_length);
1206   VScaleEq (gV, 1.0/up_length);
1207   VScaleEq (gW, 1.0/Distance);
1208
1209   A[0][0] = gU[X]; A[0][1] = gU[Y]; A[0][2] = gU[Z]; A[0][3] = 0.0;
1210   A[1][0] = gV[X]; A[1][1] = gV[Y]; A[1][2] = gV[Z]; A[1][3] = 0.0;
1211   A[2][0] = gW[X]; A[2][1] = gW[Y]; A[2][2] = gW[Z]; A[2][3] = 0.0;
1212   A[3][0] = 0.0;  A[3][1] = 0.0;  A[3][2] = 0.0;  A[3][3] = 1.0;
1213
1214   B[0][0] = 1.0; B[0][1] = 0.0; B[0][2] = 0.0; B[0][3] = -gO[X];
1215   B[1][0] = 0.0; B[1][1] = 1.0; B[1][2] = 0.0; B[1][3] = -gO[Y];
1216   B[2][0] = 0.0; B[2][1] = 0.0; B[2][2] = 1.0; B[2][3] = -gO[Z];
1217   B[3][0] = 0.0; B[3][1] = 0.0; B[3][2] = 0.0; B[3][3] = 1.0;
1218
1219   MTimes(WC2VC, A, B);
1220   MInvers(WC2VCinv, WC2VC);
1221 }
1222
1223
1224
1225 /*****************************************************************************
1226 *
1227 * FUNCTION
1228 *
1229 *   get_perspective_projection
1230 *
1231 * INPUT
1232 *
1233 *   Object   - Object to project
1234 *   Project  - Projection
1235 *   infinite - Flag if object is infinite
1236 *
1237 * OUTPUT
1238 *
1239 *   Project
1240 *
1241 * RETURNS
1242 *
1243 * AUTHOR
1244 *
1245 *   Dieter Bayer
1246 *
1247 * DESCRIPTION
1248 *
1249 *   Get the perspective projection of a single object, i.e.
1250 *   the smallest rectangle enclosing the object's image on the screen.
1251 *
1252 * CHANGES
1253 *
1254 *   May 1994 : Creation.
1255 *
1256 ******************************************************************************/
1257
1258 static void get_perspective_projection(OBJECT *Object, PROJECT *Project, int infinite)
1259 {
1260   int visible;
1261   METHODS *Methods;
1262
1263   visible = FALSE;
1264
1265   Methods = Object->Methods;
1266
1267   /* If the object is infinite, there's no sense of projecting */
1268
1269   if (!infinite)
1270   {
1271     if ((Methods == &Box_Methods) ||
1272         (Methods == &Smooth_Triangle_Methods) ||
1273         (Methods == &Triangle_Methods) ||
1274         (Methods == &HField_Methods))
1275     {
1276       if (Methods == &Box_Methods)
1277         project_box(Project, Object, &visible);
1278
1279       if (Methods == &HField_Methods)
1280         project_hfield(Project, Object, &visible);
1281
1282       if (Methods == &Smooth_Triangle_Methods)
1283         project_smooth_triangle(Project, Object, &visible);
1284
1285       if (Methods == &Triangle_Methods)
1286         project_triangle(Project, Object, &visible);
1287     }
1288     else
1289     {
1290       project_bounds(Project, &Object->BBox, &visible);
1291     }
1292   }
1293
1294   if (visible)
1295   {
1296     if (opts.Options & ANTIALIAS)
1297     {
1298       /* Increase the rectangle to make sure that nothing will be missed.
1299          For anti-aliased images increase by a larger amount. */
1300
1301       Project->x1 = max (0,                     Project->x1 - 2);
1302       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 2);
1303       Project->y1 = max (-1,                    Project->y1 - 2);
1304       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 2);
1305     }
1306     else
1307     {
1308       /* Increase the rectangle to make sure that nothing will be missed. */
1309
1310       Project->x1 = max (0,                     Project->x1 - 1);
1311       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 1);
1312       Project->y1 = max (0,                     Project->y1 - 1);
1313       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 1);
1314     }
1315   }
1316   else
1317   {
1318     if (!infinite)
1319     {
1320       /* Object is invisible (the camera can't see it) */
1321
1322       Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
1323       Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
1324     }
1325   }
1326 }
1327
1328
1329
1330 /*****************************************************************************
1331 *
1332 * FUNCTION
1333 *
1334 *   get_orthographic_projection
1335 *
1336 * INPUT
1337 *
1338 *   Object   - Object to project
1339 *   Project  - Projection
1340 *   infinite - Flag if object is infinite
1341 *
1342 * OUTPUT
1343 *
1344 *   Project
1345 *
1346 * RETURNS
1347 *
1348 * AUTHOR
1349 *
1350 *   Dieter Bayer
1351 *
1352 * DESCRIPTION
1353 *
1354 *   Get the orthographic projection of a single object, i.e.
1355 *   the smallest rectangle enclosing the object's image on the screen.
1356 *
1357 * CHANGES
1358 *
1359 *   May 1994 : Creation.
1360 *
1361 ******************************************************************************/
1362
1363 static void get_orthographic_projection(OBJECT *Object, PROJECT *Project, int infinite)
1364 {
1365   int visible, i, x, y;
1366   VECTOR P[8];
1367
1368   visible = FALSE;
1369
1370   /* If the object is infinite, there's no sense of projecting */
1371
1372   if (!infinite)
1373   {
1374     /* The following could be done better but since only a minority of all
1375        objects in a scene are partially visible I don't think it's worth it. */
1376
1377     for (i = 0; i < 8; i++)
1378     {
1379       P[i][X] = ((i & 1) ? Object->BBox.Lengths[X] : 0.0) + Object->BBox.Lower_Left[X];
1380       P[i][Y] = ((i & 2) ? Object->BBox.Lengths[Y] : 0.0) + Object->BBox.Lower_Left[Y];
1381       P[i][Z] = ((i & 4) ? Object->BBox.Lengths[Z] : 0.0) + Object->BBox.Lower_Left[Z];
1382
1383       transform_point(P[i]);
1384
1385       /* Check if bounding box is visible */
1386
1387       if (P[i][Z] >= 0.0) visible = TRUE;
1388     }
1389
1390     /* Now get the projection */
1391
1392     if (visible)
1393     {
1394       Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
1395       Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
1396
1397       for (i = 0; i < 8; i++)
1398       {
1399         /* The visible area is -0.5...+0.5/-0.5...+0.5 */
1400
1401         if (P[i][X] < -0.5) P[i][X] = -0.5;
1402         if (P[i][X] >  0.5) P[i][X] =  0.5;
1403         if (P[i][Y] < -0.5) P[i][Y] = -0.5;
1404         if (P[i][Y] >  0.5) P[i][Y] =  0.5;
1405
1406         x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * P[i][X]);
1407         y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * P[i][Y]);
1408
1409         if (x < Project->x1) Project->x1 = x;
1410         if (x > Project->x2) Project->x2 = x;
1411         if (y < Project->y1) Project->y1 = y;
1412         if (y > Project->y2) Project->y2 = y;
1413       }
1414     }
1415   }
1416
1417   if (visible)
1418   {
1419     if (opts.Options & ANTIALIAS)
1420     {
1421       /* Increase the rectangle to make sure that nothing will be missed.
1422          For anti-aliased images decrease the lower borders. */
1423
1424       Project->x1 = max (0,                     Project->x1 - 2);
1425       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 1);
1426       Project->y1 = max (-1,                    Project->y1 - 2);
1427       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 1);
1428     }
1429     else
1430     {
1431       /* Increase the rectangle to make sure that nothing will be missed. */
1432
1433       Project->x1 = max (0,                     Project->x1 - 1);
1434       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 1);
1435       Project->y1 = max (0,                     Project->y1 - 1);
1436       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 1);
1437     }
1438   }
1439   else
1440   {
1441     if (!infinite)
1442     {
1443       /* Object is invisible (the camera can't see it) */
1444
1445       Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
1446       Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
1447     }
1448   }
1449 }
1450
1451
1452
1453 /*****************************************************************************
1454 *
1455 * FUNCTION
1456 *
1457 *   project_object
1458 *
1459 * INPUT
1460 *
1461 *   Object   - Object to project
1462 *   Project  - Projection
1463 *
1464 * OUTPUT
1465 *
1466 *   Project
1467 *
1468 * RETURNS
1469 *
1470 * AUTHOR
1471 *
1472 *   Dieter Bayer
1473 *
1474 * DESCRIPTION
1475 *
1476 *   Get the projection of a single object depending on the camera
1477 *   used (perspective/orthographic).
1478 *
1479 * CHANGES
1480 *
1481 *   May 1994 : Creation.
1482 *
1483 ******************************************************************************/
1484
1485 static void project_object(OBJECT *Object, PROJECT *Project)
1486 {
1487   int infinite;
1488
1489   /* Init project fields, assuming the object is visible! */
1490
1491   Project->x1 = Project->y1 = MIN_BUFFER_ENTRY;
1492   Project->x2 = Project->y2 = MAX_BUFFER_ENTRY;
1493
1494   infinite = Test_Flag(Object, INFINITE_FLAG);
1495
1496   switch (Frame.Camera->Type)
1497   {
1498     case PERSPECTIVE_CAMERA:
1499
1500       get_perspective_projection(Object, Project, infinite);
1501       break;
1502
1503     case ORTHOGRAPHIC_CAMERA:
1504
1505       get_orthographic_projection(Object, Project, infinite);
1506       break;
1507
1508     default:
1509
1510       Error("Wrong camera type in project_object().\n");
1511       break;
1512   }
1513 }
1514
1515
1516
1517 /*****************************************************************************
1518 *
1519 * FUNCTION
1520 *
1521 *   project_bounding_slab
1522 *
1523 * INPUT
1524 *
1525 *   Project  - Projection
1526 *   Tree     - Current node/leaf
1527 *   Object   - Node/leaf in bounding slab hierarchy
1528 *
1529 * OUTPUT
1530 *
1531 *   Project, Tree
1532 *
1533 * RETURNS
1534 *
1535 * AUTHOR
1536 *
1537 *   Dieter Bayer
1538 *
1539 * DESCRIPTION
1540 *
1541 *   Project the bounding slab hierarchy onto the screen and thus create
1542 *   the vista buffer hierarchy.
1543 *
1544 * CHANGES
1545 *
1546 *   May 1994 : Creation.
1547 *
1548 ******************************************************************************/
1549
1550 static void project_bounding_slab(PROJECT *Project, PROJECT_TREE_NODE **Tree, BBOX_TREE *Node)
1551 {
1552   short int i;
1553   PROJECT Temp;
1554   PROJECT_TREE_LEAF *Leaf;
1555   PROJECT_TREE_NODE New;
1556
1557   if (Node->Entries)
1558   {
1559     /* Current object is a bounding object, i.e. a node in the slab tree. */
1560
1561     /* First, init new entry. */
1562
1563     New.Entries = 0;
1564
1565     New.Node = Node;
1566
1567     New.Project.x1 = New.Project.y1 = MAX_BUFFER_ENTRY;
1568     New.Project.x2 = New.Project.y2 = MIN_BUFFER_ENTRY;
1569
1570     /* Allocate temporary memory for node/leaf entries. */
1571
1572     New.Entry = (PROJECT_TREE_NODE **)POV_MALLOC(Node->Entries*sizeof(PROJECT_TREE_NODE *), "temporary tree entry");
1573
1574     /* This is no leaf, it's a node. */
1575
1576     New.is_leaf = FALSE;
1577
1578     /* Second, get new entry, i.e. project node's entries. */
1579
1580     for (i = 0; i < Node->Entries; i++)
1581     {
1582       New.Entry[i] = NULL;
1583
1584       project_bounding_slab(&Temp, &New.Entry[New.Entries], Node->Node[i]);
1585
1586       /* Use only visible entries. */
1587
1588       if (New.Entry[New.Entries] != NULL)
1589       {
1590         New.Project.x1 = min(New.Project.x1, Temp.x1);
1591         New.Project.x2 = max(New.Project.x2, Temp.x2);
1592         New.Project.y1 = min(New.Project.y1, Temp.y1);
1593         New.Project.y2 = max(New.Project.y2, Temp.y2);
1594
1595         New.Entries++;
1596       }
1597     }
1598
1599     /* If there are any visible entries, we'll use them. */
1600
1601     if (New.Entries > 0)
1602     {
1603       /* If there's only one entry, we won't need a new node. */
1604
1605       if (New.Entries == 1)
1606       {
1607         *Tree    = New.Entry[0];
1608         *Project = New.Project;
1609       }
1610       else
1611       {
1612         /* Allocate memory for new node in the vista tree. */
1613
1614         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_NODE), "vista tree node");
1615
1616         **Tree = New;
1617
1618         /* Allocate memory for node/leaf entries. */
1619
1620         (*Tree)->Entry = (PROJECT_TREE_NODE **)POV_MALLOC(New.Entries*sizeof(PROJECT_TREE_NODE *), "vista tree node");
1621
1622         memcpy((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *));
1623
1624         *Project = New.Project;
1625       }
1626     }
1627
1628     /* Get rid of temporary node/leaf entries. */
1629
1630     POV_FREE(New.Entry);
1631   }
1632   else
1633   {
1634     COOPERATE_0
1635
1636     /* Current object is a normal object, i.e. a leaf in the slab tree. */
1637
1638     /* Get object's projection. */
1639
1640     project_object((OBJECT *)Node->Node, Project);
1641
1642     /* Is the object visible? */
1643
1644     if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
1645     {
1646       /* Allocate memory for new leaf in the vista tree.  */
1647
1648       *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_LEAF), "vista tree leaf");
1649
1650       /* Init new leaf. */
1651
1652       Leaf = (PROJECT_TREE_LEAF *)(*Tree);
1653
1654       Leaf->Node = Node;
1655
1656       Leaf->Project = *Project;
1657
1658       /* Yes, this is a leaf. */
1659
1660       Leaf->is_leaf = TRUE;
1661     }
1662   }
1663 }
1664
1665
1666
1667 /*****************************************************************************
1668 *
1669 * FUNCTION
1670 *
1671 *   Build_Vista_Buffer
1672 *
1673 * INPUT
1674 *
1675 * OUTPUT
1676 *
1677 * RETURNS
1678 *
1679 * AUTHOR
1680 *
1681 *   Dieter Bayer
1682 *
1683 * DESCRIPTION
1684 *
1685 *   Build the vista tree, i.e. the 2d representation of the bounding slab
1686 *   hierarchy in image space.
1687 *
1688 *   This only works for perspective and orthographic cameras.
1689 *
1690 * CHANGES
1691 *
1692 *   May 1994 : Creation.
1693 *
1694 ******************************************************************************/
1695
1696 void Build_Vista_Buffer()
1697 {
1698   PROJECT Project;
1699
1700   Root_Vista = NULL;
1701
1702   /* Check if vista buffer can be used. */
1703
1704   if ((!opts.Use_Slabs) ||
1705       (Frame.Camera->Tnormal != NULL) ||
1706       ((Frame.Camera->Type != PERSPECTIVE_CAMERA) && (Frame.Camera->Type != ORTHOGRAPHIC_CAMERA)) ||
1707       ((Frame.Camera->Aperture != 0.0) && (Frame.Camera->Blur_Samples > 0)))
1708   {
1709     opts.Options &= ~USE_VISTA_BUFFER;
1710   }
1711
1712   if (opts.Options & USE_VISTA_BUFFER)
1713   {
1714     Status_Info("\nCreating vista buffer.");
1715
1716     init_view_coordinates();
1717
1718     project_bounding_slab(&Project, &Root_Vista, Root_Object);
1719   }
1720 }
1721
1722
1723
1724 /*****************************************************************************
1725 *
1726 * FUNCTION
1727 *
1728 *   Destroy_Vista_Buffer
1729 *
1730 * INPUT
1731 *
1732 * OUTPUT
1733 *
1734 * RETURNS
1735 *
1736 * AUTHOR
1737 *
1738 *   Dieter Bayer
1739 *
1740 * DESCRIPTION
1741 *
1742 *   Destroy the vista tree.
1743 *
1744 * CHANGES
1745 *
1746 *   Sep 1994 : Creation.
1747 *
1748 ******************************************************************************/
1749
1750 void Destroy_Vista_Buffer()
1751 {
1752   if ((opts.Options & USE_VISTA_BUFFER) && (Root_Vista != NULL))
1753   {
1754     Destroy_Project_Tree(Root_Vista);
1755
1756     Root_Vista = NULL;
1757   }
1758 }
1759
1760
1761
1762 /*****************************************************************************
1763 *
1764 * FUNCTION
1765 *
1766 *   draw_projection
1767 *
1768 * INPUT
1769 *
1770 *   Project - projection to draw
1771 *   color   - Color to be used
1772 *
1773 * OUTPUT
1774 *
1775 * RETURNS
1776 *
1777 * AUTHOR
1778 *
1779 *   Dieter Bayer
1780 *
1781 * DESCRIPTION
1782 *
1783 *   Draws a projection in the specified color.
1784 *
1785 * CHANGES
1786 *
1787 *   May 1994 : Creation.
1788 *   Jul 1996 : Draw boxes in white when doing grayscale preview
1789 *
1790 ******************************************************************************/
1791
1792 static void draw_projection(PROJECT *Project, int color, int  *BigRed, int  *BigBlue)
1793 {
1794   int x1, x2, y1, y2, draw_it;
1795   unsigned char r, g, b, gray;
1796   unsigned char a=0;
1797
1798   gray = (opts.PaletteOption == GREY) ? 255 : 0;
1799
1800   switch (color)
1801   {
1802     case RED   : r = 255; g = b = gray; break;
1803     case GREEN : g = 255; r = b = gray; break;
1804     case BLUE  : b = 255; r = g = gray; break;
1805     default    : r = g = b = 255;
1806   }
1807
1808   x1 = Project->x1;
1809   x2 = Project->x2;
1810   y1 = Project->y1;
1811   y2 = Project->y2;
1812
1813   if ((x1 <= x2) && (y1 <= y2))
1814   {
1815     if (x1 < 0) x1 = 0;
1816     if (x2 < 0) x2 = 0;
1817     if (y1 < 0) y1 = 0;
1818     if (y2 < 0) y2 = 0;
1819
1820     if (x1 >= Frame.Screen_Width)  x1 = Frame.Screen_Width - 1;
1821     if (x2 >= Frame.Screen_Width)  x2 = Frame.Screen_Width - 1;
1822     if (y1 >= Frame.Screen_Height) y1 = Frame.Screen_Height - 1;
1823     if (y2 >= Frame.Screen_Height) y2 = Frame.Screen_Height - 1;
1824
1825     /* Check for full-screen rectangle. */
1826
1827     draw_it = TRUE;
1828
1829     if ((x1 == 0) && (x2 == Frame.Screen_Width - 1) &&
1830         (y1 == 0) && (y2 == Frame.Screen_Height - 1))
1831     {
1832       draw_it = FALSE;
1833
1834       switch (color)
1835       {
1836         case RED   : if (!(*BigRed))  { *BigRed  = draw_it = TRUE; } break;
1837         case BLUE  : if (!(*BigBlue)) { *BigBlue = draw_it = TRUE; } break;
1838       }
1839     }
1840
1841     if (draw_it)
1842     {
1843       POV_DISPLAY_PLOT_BOX(x1,y1,x2,y2,r,g,b,a);
1844     }
1845   }
1846 }
1847
1848
1849
1850 /*****************************************************************************
1851 *
1852 * FUNCTION
1853 *
1854 *   draw_vista
1855 *
1856 * INPUT
1857 *
1858 *   Tree - current node/leaf in the vista tree
1859 *
1860 * OUTPUT
1861 *
1862 * RETURNS
1863 *
1864 * AUTHOR
1865 *
1866 *   Dieter Bayer
1867 *
1868 * DESCRIPTION
1869 *
1870 *   Draws recursively all projections of subnodes in the current node.
1871 *
1872 * CHANGES
1873 *
1874 *   May 1994 : Creation.
1875 *
1876 ******************************************************************************/
1877
1878 static void draw_vista(PROJECT_TREE_NODE *Tree, int  *BigRed, int *BigBlue)
1879 {
1880   unsigned short i;
1881   PROJECT_TREE_LEAF *Leaf;
1882
1883   if (Tree->is_leaf)
1884   {
1885     Leaf = (PROJECT_TREE_LEAF *)Tree;
1886
1887     COOPERATE_1
1888
1889     if (((OBJECT *)Leaf->Node->Node)->Type & COMPOUND_OBJECT)
1890     {
1891       draw_projection(&Leaf->Project, BLUE, BigRed, BigBlue);
1892     }
1893     else
1894     {
1895       draw_projection(&Leaf->Project, RED, BigRed, BigBlue);
1896     }
1897   }
1898   else
1899   {
1900     for (i = 0; i < Tree->Entries; i++)
1901     {
1902       draw_vista(Tree->Entry[i], BigRed, BigBlue);
1903     }
1904   }
1905
1906   /* draw bounding object's vista */
1907
1908 /*
1909   draw_projection(&Tree->Project, GREEN);
1910 */
1911 }
1912
1913
1914
1915 /*****************************************************************************
1916 *
1917 * FUNCTION
1918 *
1919 *   Draw_Vista_Buffer
1920 *
1921 * INPUT
1922 *
1923 * OUTPUT
1924 *
1925 * RETURNS
1926 *
1927 * AUTHOR
1928 *
1929 *   Dieter Bayer
1930 *
1931 * DESCRIPTION
1932 *
1933 *   Draw the vista tree.
1934 *
1935 * CHANGES
1936 *
1937 *   May 1994 : Creation.
1938 *
1939 ******************************************************************************/
1940
1941 void Draw_Vista_Buffer()
1942 {
1943   int BigRed, BigBlue;
1944
1945   BigRed = BigBlue = FALSE;
1946
1947   if ((Root_Vista != NULL) && (opts.Options & USE_VISTA_DRAW))
1948   {
1949     draw_vista(Root_Vista, &BigRed, &BigBlue);
1950   }
1951 }