gfx/povray/mesh.c

   1 /****************************************************************************
   2 *                mesh.c
   3 *
   4 *  This module implements primitives for mesh objects.
   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 *****************************************************************************/
  25
  26 /****************************************************************************
  27 *
  28 *  Explanation:
  29 *
  30 *    -
  31 *
  32 *  Syntax:
  33 *
  34 *    mesh
  35 *    {
  36 *      triangle { <CORNER1>, <CORNER2>, <CORNER3>, texture { NAME } }
  37 *      smooth_triangle { <CORNER1>, <NORMAL1>, <CORNER2>, <NORMAL2>, <CORNER3>, <NORMAL3>, texture { NAME } }
  38 *      ...
  39 *      [ hierarchy FLAG ]
  40 *    }
  41 *
  42 *  ---
  43 *
  44 *  Feb 1995 : Creation. [DB]
  45 *
  46 *****************************************************************************/
  47
  48 #include "frame.h"
  49 #include "vector.h"
  50 #include "povproto.h"
  51 #include "bbox.h"
  52 #include "matrices.h"
  53 #include "objects.h"
  54 #include "mesh.h"
  55 #include "texture.h"
  56 #include "povray.h"
  57
  58
  59
  60 /*****************************************************************************
  61 * Local preprocessor defines
  62 ******************************************************************************/
  63
  64 #define DEPTH_TOLERANCE 1e-6
  65
  66 #define max3_coordinate(x,y,z) ((x > y) ? ((x > z) ? X : Z) : ((y > z) ? Y : Z))
  67
  68 #define HASH_SIZE 1000
  69
  70 #define INITIAL_NUMBER_OF_ENTRIES 256
  71
  72
  73 /*****************************************************************************
  74 * Local typedefs
  75 ******************************************************************************/
  76
  77 typedef struct Hash_Table_Struct HASH_TABLE;
  78
  79 struct Hash_Table_Struct
  80 {
  81   int Index;
  82   SNGL_VECT P;
  83   HASH_TABLE *Next;
  84 };
  85
  86
  87
  88 /*****************************************************************************
  89 * Static functions
  90 ******************************************************************************/
  91
  92 static int Intersect_Mesh  (RAY *Ray, MESH *Mesh, ISTACK *Depth_Stack);
  93 static int All_Mesh_Intersections  (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  94 static int Inside_Mesh  (VECTOR IPoint, OBJECT *Object);
  95 static void Mesh_Normal  (VECTOR Result, OBJECT *Object, INTERSECTION *Inter);
  96 static MESH *Copy_Mesh  (OBJECT *Object);
  97 static void Translate_Mesh  (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  98 static void Rotate_Mesh  (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  99 static void Scale_Mesh  (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
 100 static void Transform_Mesh  (OBJECT *Object, TRANSFORM *Trans);
 101 static void Invert_Mesh  (OBJECT *Object);
 102 static void Destroy_Mesh  (OBJECT *Object);
 103
 104 static void compute_smooth_triangle (MESH_TRIANGLE *Triangle, VECTOR P1, VECTOR P2, VECTOR P3);
 105 static int intersect_mesh_triangle (RAY *Ray, MESH *Mesh, MESH_TRIANGLE *Triangle, DBL *Depth);
 106 static int test_hit (MESH_TRIANGLE *Triangle, MESH *Mesh, RAY *Ray, DBL Depth, ISTACK *Depth_Stack);
 107 static void smooth_mesh_normal (MESH *Mesh, VECTOR Result, MESH_TRIANGLE *Triangle, VECTOR IPoint);
 108 static void get_triangle_bbox (MESH *Mesh, MESH_TRIANGLE *Triangle, BBOX *BBox);
 109
 110 static int intersect_bbox_tree (MESH *Mesh, RAY *Ray, RAY *Orig_Ray, DBL len, ISTACK *Depth_Stack);
 111
 112 static void get_triangle_vertices (MESH *Mesh, MESH_TRIANGLE *Triangle, VECTOR P1, VECTOR P2, VECTOR P3);
 113 static void get_triangle_normals (MESH *Mesh, MESH_TRIANGLE *Triangle, VECTOR N1, VECTOR N2, VECTOR N3);
 114
 115 static int mesh_hash (HASH_TABLE **Hash_Table,
 116   int *Number, int *Max, SNGL_VECT **Elements, VECTOR aPoint);
 117
 118
 119
 120 /*****************************************************************************
 121 * Local variables
 122 ******************************************************************************/
 123
 124 METHODS Mesh_Methods =
 125 {
 126   All_Mesh_Intersections,
 127   Inside_Mesh, Mesh_Normal,
 128   (COPY_METHOD)Copy_Mesh,
 129   Translate_Mesh, Rotate_Mesh,
 130   Scale_Mesh, Transform_Mesh, Invert_Mesh, Destroy_Mesh
 131 };
 132
 133 static HASH_TABLE **Vertex_Hash_Table, **Normal_Hash_Table;
 134
 135 static PRIORITY_QUEUE *Mesh_Queue;
 136
 137
 138
 139 /*****************************************************************************
 140 *
 141 * FUNCTION
 142 *
 143 *   All_Mesh_Intersections
 144 *
 145 * INPUT
 146 *
 147 * OUTPUT
 148 *
 149 * RETURNS
 150 *
 151 * AUTHOR
 152 *
 153 *   Dieter Bayer
 154 *
 155 * DESCRIPTION
 156 *
 157 *   -
 158 *
 159 * CHANGES
 160 *
 161 *   Feb 1995 : Creation.
 162 *
 163 ******************************************************************************/
 164
 165 static int All_Mesh_Intersections(OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
 166 {
 167   Increase_Counter(stats[Ray_Mesh_Tests]);
 168
 169   if (Intersect_Mesh(Ray, (MESH *)Object, Depth_Stack))
 170   {
 171     Increase_Counter(stats[Ray_Mesh_Tests_Succeeded]);
 172
 173     return(TRUE);
 174   }
 175
 176   return(FALSE);
 177 }
 178
 179
 180
 181 /*****************************************************************************
 182 *
 183 * FUNCTION
 184 *
 185 *   Intersect_Mesh
 186 *
 187 * INPUT
 188 *
 189 * OUTPUT
 190 *
 191 * RETURNS
 192 *
 193 * AUTHOR
 194 *
 195 *   Dieter Bayer
 196 *
 197 * DESCRIPTION
 198 *
 199 *   -
 200 *
 201 * CHANGES
 202 *
 203 *   Feb 1995 : Creation.
 204 *
 205 ******************************************************************************/
 206
 207 static int Intersect_Mesh(RAY *Ray, MESH *Mesh, ISTACK *Depth_Stack)
 208 {
 209   int i;
 210   unsigned found;
 211   DBL len, t;
 212   RAY New_Ray;
 213
 214   /* Transform the ray into mesh space. */
 215
 216   if (Mesh->Trans != NULL)
 217   {
 218     MInvTransPoint(New_Ray.Initial, Ray->Initial, Mesh->Trans);
 219     MInvTransDirection(New_Ray.Direction, Ray->Direction, Mesh->Trans);
 220
 221     VLength(len, New_Ray.Direction);
 222     VInverseScaleEq(New_Ray.Direction, len);
 223   }
 224   else
 225   {
 226     New_Ray = *Ray;
 227
 228     len = 1.0;
 229   }
 230
 231   found = FALSE;
 232
 233   if (Mesh->Data->Tree == NULL)
 234   {
 235     /* There's no bounding hierarchy so just step through all elements. */
 236
 237     for (i = 0; i < Mesh->Data->Number_Of_Triangles; i++)
 238     {
 239       if (intersect_mesh_triangle(&New_Ray, Mesh, &Mesh->Data->Triangles[i], &t))
 240       {
 241         if (test_hit(&Mesh->Data->Triangles[i], Mesh, Ray, t / len, Depth_Stack))
 242         {
 243           found = TRUE;
 244         }
 245       }
 246     }
 247   }
 248   else
 249   {
 250     /* Use the mesh's bounding hierarchy. */
 251
 252     return(intersect_bbox_tree(Mesh, &New_Ray, Ray, len, Depth_Stack));
 253   }
 254
 255   return(found);
 256 }
 257
 258
 259
 260 /*****************************************************************************
 261 *
 262 * FUNCTION
 263 *
 264 *   Inside_Mesh
 265 *
 266 * INPUT
 267 *
 268 * OUTPUT
 269 *
 270 * RETURNS
 271 *
 272 * AUTHOR
 273 *
 274 *   Dieter Bayer
 275 *
 276 * DESCRIPTION
 277 *
 278 *   -
 279 *
 280 * CHANGES
 281 *
 282 *   Feb 1995 : Creation.
 283 *
 284 ******************************************************************************/
 285
 286 static int Inside_Mesh(VECTOR IPoint, OBJECT *Object)
 287 {
 288   return(FALSE);
 289 }
 290
 291
 292
 293 /*****************************************************************************
 294 *
 295 * FUNCTION
 296 *
 297 *   Mesh_Normal
 298 *
 299 * INPUT
 300 *
 301 * OUTPUT
 302 *
 303 * RETURNS
 304 *
 305 * AUTHOR
 306 *
 307 *   Dieter Bayer
 308 *
 309 * DESCRIPTION
 310 *
 311 *   Return the normalized normal in the given point.
 312 *
 313 * CHANGES
 314 *
 315 *   Feb 1995 : Creation.
 316 *
 317 ******************************************************************************/
 318
 319 static void Mesh_Normal(VECTOR Result, OBJECT *Object, INTERSECTION *Inter)
 320 {
 321   VECTOR IPoint;
 322   MESH_TRIANGLE *Triangle;
 323   MESH *Mesh = (MESH *)Object;
 324
 325   Triangle = (MESH_TRIANGLE *)Inter->Pointer;
 326
 327   if (Triangle->Smooth)
 328   {
 329     if (Mesh->Trans != NULL)
 330     {
 331       MInvTransPoint(IPoint, Inter->IPoint, Mesh->Trans);
 332     }
 333     else
 334     {
 335       Assign_Vector(IPoint, Inter->IPoint);
 336     }
 337
 338     smooth_mesh_normal(Mesh, Result, Triangle, IPoint);
 339
 340     if (Mesh->Trans != NULL)
 341     {
 342       MTransNormal(Result, Result, Mesh->Trans);
 343     }
 344
 345     VNormalize(Result, Result);
 346   }
 347   else
 348   {
 349     Assign_SNGL_Vect(Result, Mesh->Data->Normals[Triangle->Normal_Ind]);
 350
 351     if (Mesh->Trans != NULL)
 352     {
 353       MTransNormal(Result, Result, Mesh->Trans);
 354
 355       VNormalize(Result, Result);
 356     }
 357   }
 358 }
 359
 360
 361
 362 /*****************************************************************************
 363 *
 364 * FUNCTION
 365 *
 366 *   smooth_mesh_normal
 367 *
 368 * INPUT
 369 *
 370 * OUTPUT
 371 *
 372 * RETURNS
 373 *
 374 * AUTHOR
 375 *
 376 *   Dieter Bayer
 377 *
 378 * DESCRIPTION
 379 *
 380 *   Remove the un-normalized normal of a smoothed triangle.
 381 *
 382 * CHANGES
 383 *
 384 *   Feb 1995 : Creation. (Derived from TRIANGLE.C)
 385 *
 386 ******************************************************************************/
 387
 388 static void smooth_mesh_normal(MESH *Mesh, VECTOR Result, MESH_TRIANGLE *Triangle, VECTOR  IPoint)
 389 {
 390   int axis;
 391   DBL u, v;
 392   DBL k1, k2, k3;
 393   VECTOR PIMinusP1, N1, N2, N3;
 394
 395   get_triangle_normals(Mesh, Triangle, N1, N2, N3);
 396
 397   VSub(PIMinusP1, IPoint, Mesh->Data->Vertices[Triangle->P1]);
 398
 399   VDot(u, PIMinusP1, Triangle->Perp);
 400
 401   if (u < EPSILON)
 402   {
 403     Assign_Vector(Result, N1);
 404   }
 405   else
 406   {
 407     axis = Triangle->vAxis;
 408
 409     k1 = Mesh->Data->Vertices[Triangle->P1][axis];
 410     k2 = Mesh->Data->Vertices[Triangle->P2][axis];
 411     k3 = Mesh->Data->Vertices[Triangle->P3][axis];
 412
 413     v = (PIMinusP1[axis] / u + k1 - k2) / (k3 - k2);
 414
 415     Result[X] = N1[X] + u * (N2[X] - N1[X] + v * (N3[X] - N2[X]));
 416     Result[Y] = N1[Y] + u * (N2[Y] - N1[Y] + v * (N3[Y] - N2[Y]));
 417     Result[Z] = N1[Z] + u * (N2[Z] - N1[Z] + v * (N3[Z] - N2[Z]));
 418   }
 419 }
 420
 421
 422
 423 /*****************************************************************************
 424 *
 425 * FUNCTION
 426 *
 427 *   Translate_Mesh
 428 *
 429 * INPUT
 430 *
 431 * OUTPUT
 432 *
 433 * RETURNS
 434 *
 435 * AUTHOR
 436 *
 437 *   Dieter Bayer
 438 *
 439 * DESCRIPTION
 440 *
 441 *   -
 442 *
 443 * CHANGES
 444 *
 445 *   Feb 1995 : Creation.
 446 *
 447 ******************************************************************************/
 448
 449 static void Translate_Mesh(OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
 450 {
 451   Transform_Mesh(Object, Trans);
 452 }
 453
 454
 455
 456 /*****************************************************************************
 457 *
 458 * FUNCTION
 459 *
 460 *   Rotate_Mesh
 461 *
 462 * INPUT
 463 *
 464 * OUTPUT
 465 *
 466 * RETURNS
 467 *
 468 * AUTHOR
 469 *
 470 *   Dieter Bayer
 471 *
 472 * DESCRIPTION
 473 *
 474 *   -
 475 *
 476 * CHANGES
 477 *
 478 *   Feb 1995 : Creation.
 479 *
 480 ******************************************************************************/
 481
 482 static void Rotate_Mesh(OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
 483 {
 484   Transform_Mesh(Object, Trans);
 485 }
 486
 487
 488
 489 /*****************************************************************************
 490 *
 491 * FUNCTION
 492 *
 493 *   Scale_Mesh
 494 *
 495 * INPUT
 496 *
 497 * OUTPUT
 498 *
 499 * RETURNS
 500 *
 501 * AUTHOR
 502 *
 503 *   Dieter Bayer
 504 *
 505 * DESCRIPTION
 506 *
 507 *   -
 508 *
 509 * CHANGES
 510 *
 511 *   Feb 1995 : Creation.
 512 *
 513 ******************************************************************************/
 514
 515 static void Scale_Mesh(OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
 516 {
 517   Transform_Mesh(Object, Trans);
 518 }
 519
 520
 521
 522 /*****************************************************************************
 523 *
 524 * FUNCTION
 525 *
 526 *   Transfrom_Mesh
 527 *
 528 * INPUT
 529 *
 530 * OUTPUT
 531 *
 532 * RETURNS
 533 *
 534 * AUTHOR
 535 *
 536 *   Dieter Bayer
 537 *
 538 * DESCRIPTION
 539 *
 540 *   -
 541 *
 542 * CHANGES
 543 *
 544 *   Feb 1995 : Creation.
 545 *
 546 ******************************************************************************/
 547
 548 static void Transform_Mesh(OBJECT *Object, TRANSFORM *Trans)
 549 {
 550   int i;
 551   if (((MESH *)Object)->Trans == NULL)
 552   {
 553     ((MESH *)Object)->Trans = Create_Transform();
 554   }
 555
 556   Recompute_BBox(&Object->BBox, Trans);
 557
 558   Compose_Transforms(((MESH *)Object)->Trans, Trans);
 559
 560   for (i=0; i<((MESH *)Object)->Data->Number_Of_Textures; i++)
 561   {
 562     Transform_Textures(((MESH *)Object)->Data->Textures[i], Trans);
 563   }
 564 }
 565
 566
 567
 568 /*****************************************************************************
 569 *
 570 * FUNCTION
 571 *
 572 *   Invert_Mesh
 573 *
 574 * INPUT
 575 *
 576 * OUTPUT
 577 *
 578 * RETURNS
 579 *
 580 * AUTHOR
 581 *
 582 *   Dieter Bayer
 583 *
 584 * DESCRIPTION
 585 *
 586 *   -
 587 *
 588 * CHANGES
 589 *
 590 *   Feb 1995 : Creation.
 591 *
 592 ******************************************************************************/
 593
 594 static void Invert_Mesh(OBJECT *Object)
 595 {
 596 }
 597
 598
 599
 600 /*****************************************************************************
 601 *
 602 * FUNCTION
 603 *
 604 *   Create_Mesh
 605 *
 606 * INPUT
 607 *
 608 * OUTPUT
 609 *
 610 * RETURNS
 611 *
 612 * AUTHOR
 613 *
 614 *   Dieter Bayer
 615 *
 616 * DESCRIPTION
 617 *
 618 *   -
 619 *
 620 * CHANGES
 621 *
 622 *   Feb 1995 : Creation.
 623 *
 624 ******************************************************************************/
 625
 626 MESH *Create_Mesh()
 627 {
 628   MESH *New;
 629
 630   New = (MESH *)POV_MALLOC(sizeof(MESH), "mesh");
 631
 632   INIT_OBJECT_FIELDS(New,MESH_OBJECT,&Mesh_Methods)
 633
 634   Set_Flag(New, HIERARCHY_FLAG);
 635
 636   New->Trans = NULL;
 637
 638   New->Data = NULL;
 639
 640   return(New);
 641 }
 642
 643
 644
 645 /*****************************************************************************
 646 *
 647 * FUNCTION
 648 *
 649 *   Copy_Mesh
 650 *
 651 * INPUT
 652 *
 653 * OUTPUT
 654 *
 655 * RETURNS
 656 *
 657 * AUTHOR
 658 *
 659 *   Dieter Bayer
 660 *
 661 * DESCRIPTION
 662 *
 663 *   Copy a mesh.
 664 *
 665 *   NOTE: The components are not copied, only the number of references is
 666 *         counted, so that Destroy_Mesh() knows if they can be destroyed.
 667 *
 668 *   -
 669 *
 670 * CHANGES
 671 *
 672 *   Feb 1995 : Creation.
 673 *
 674 ******************************************************************************/
 675
 676 static MESH *Copy_Mesh(OBJECT *Object)
 677 {
 678   MESH *New;
 679
 680   New = Create_Mesh();
 681
 682   /* Copy mesh. */
 683
 684   *New = *((MESH *)Object);
 685
 686   New->Trans = Copy_Transform(New->Trans);
 687
 688   New->Data->References++;
 689
 690   return(New);
 691 }
 692
 693
 694
 695 /*****************************************************************************
 696 *
 697 * FUNCTION
 698 *
 699 *   Destroy_Mesh
 700 *
 701 * INPUT
 702 *
 703 * OUTPUT
 704 *
 705 * RETURNS
 706 *
 707 * AUTHOR
 708 *
 709 *   Dieter Bayer
 710 *
 711 * DESCRIPTION
 712 *
 713 *   -
 714 *
 715 * CHANGES
 716 *
 717 *   Feb 1995 : Creation.
 718 *
 719 ******************************************************************************/
 720
 721 static void Destroy_Mesh(OBJECT *Object)
 722 {
 723   int i;
 724   MESH *Mesh = (MESH *)Object;
 725
 726   Destroy_Transform(Mesh->Trans);
 727
 728   if (--(Mesh->Data->References) == 0)
 729   {
 730     Destroy_BBox_Tree(Mesh->Data->Tree);
 731
 732     if (Mesh->Data->Normals != NULL)
 733     {
 734       POV_FREE(Mesh->Data->Normals);
 735     }
 736
 737     if (Mesh->Data->Vertices != NULL)
 738     {
 739       POV_FREE(Mesh->Data->Vertices);
 740     }
 741
 742     if (Mesh->Data->Triangles != NULL)
 743     {
 744       POV_FREE(Mesh->Data->Triangles);
 745     }
 746
 747     if (Mesh->Data->Textures != NULL)
 748     {
 749       for (i = 0; i < Mesh->Data->Number_Of_Textures; i++)
 750       {
 751         Destroy_Textures(Mesh->Data->Textures[i]);
 752       }
 753
 754       POV_FREE(Mesh->Data->Textures);
 755     }
 756
 757     POV_FREE(Mesh->Data);
 758   }
 759
 760   POV_FREE(Object);
 761 }
 762
 763
 764
 765 /*****************************************************************************
 766 *
 767 * FUNCTION
 768 *
 769 *   Compute_Mesh_BBox
 770 *
 771 * INPUT
 772 *
 773 *   Mesh - Mesh
 774 *
 775 * OUTPUT
 776 *
 777 *   Mesh
 778 *
 779 * RETURNS
 780 *
 781 * AUTHOR
 782 *
 783 *   Dieter Bayer
 784 *
 785 * DESCRIPTION
 786 *
 787 *   Calculate the bounding box of a triangle.
 788 *
 789 * CHANGES
 790 *
 791 *   Feb 1995 : Creation.
 792 *
 793 ******************************************************************************/
 794
 795 void Compute_Mesh_BBox(MESH *Mesh)
 796 {
 797   int i;
 798   VECTOR P1, P2, P3;
 799   VECTOR mins, maxs;
 800
 801   Make_Vector(mins, BOUND_HUGE, BOUND_HUGE, BOUND_HUGE);
 802   Make_Vector(maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
 803
 804   for (i = 0; i < Mesh->Data->Number_Of_Triangles; i++)
 805   {
 806     get_triangle_vertices(Mesh, &Mesh->Data->Triangles[i], P1, P2, P3);
 807
 808     mins[X] = min(mins[X], min3(P1[X], P2[X], P3[X]));
 809     mins[Y] = min(mins[Y], min3(P1[Y], P2[Y], P3[Y]));
 810     mins[Z] = min(mins[Z], min3(P1[Z], P2[Z], P3[Z]));
 811
 812     maxs[X] = max(maxs[X], max3(P1[X], P2[X], P3[X]));
 813     maxs[Y] = max(maxs[Y], max3(P1[Y], P2[Y], P3[Y]));
 814     maxs[Z] = max(maxs[Z], max3(P1[Z], P2[Z], P3[Z]));
 815   }
 816
 817   Make_BBox_from_min_max(Mesh->BBox, mins, maxs);
 818 }
 819
 820
 821
 822 /*****************************************************************************
 823 *
 824 * FUNCTION
 825 *
 826 *   Compute_Mesh
 827 *
 828 * INPUT
 829 *
 830 * OUTPUT
 831 *
 832 * RETURNS
 833 *
 834 * AUTHOR
 835 *
 836 *   Dieter Bayer
 837 *
 838 * DESCRIPTION
 839 *
 840 *   -
 841 *
 842 * CHANGES
 843 *
 844 *   Feb 1995 : Creation.
 845 *
 846 ******************************************************************************/
 847
 848 int Compute_Mesh_Triangle(MESH_TRIANGLE *Triangle, int Smooth, VECTOR P1, VECTOR  P2, VECTOR  P3, VECTOR  S_Normal)
 849 {
 850   int temp, swap;
 851   DBL x, y, z;
 852   VECTOR V1, V2, T1;
 853   DBL Length;
 854
 855   VSub(V1, P2, P1);
 856   VSub(V2, P3, P1);
 857
 858   VCross(S_Normal, V2, V1);
 859
 860   VLength(Length, S_Normal);
 861
 862   /* Set up a flag so we can ignore degenerate triangles */
 863
 864   if (Length == 0.0)
 865   {
 866     return(FALSE);
 867   }
 868
 869   /* Normalize the normal vector. */
 870
 871   VInverseScaleEq(S_Normal, Length);
 872
 873   VDot(Triangle->Distance, S_Normal, P1);
 874
 875   Triangle->Distance *= -1.0;
 876
 877   /* Find triangle's dominant axis. */
 878
 879   x = fabs(S_Normal[X]);
 880   y = fabs(S_Normal[Y]);
 881   z = fabs(S_Normal[Z]);
 882
 883   Triangle->Dominant_Axis = max3_coordinate(x, y, z);
 884
 885   swap = FALSE;
 886
 887   switch (Triangle->Dominant_Axis)
 888   {
 889     case X:
 890
 891       if ((P2[Y] - P3[Y])*(P2[Z] - P1[Z]) < (P2[Z] - P3[Z])*(P2[Y] - P1[Y]))
 892       {
 893         swap = TRUE;
 894       }
 895
 896       break;
 897
 898     case Y:
 899
 900       if ((P2[X] - P3[X])*(P2[Z] - P1[Z]) < (P2[Z] - P3[Z])*(P2[X] - P1[X]))
 901       {
 902         swap = TRUE;
 903       }
 904
 905       break;
 906
 907     case Z:
 908
 909       if ((P2[X] - P3[X])*(P2[Y] - P1[Y]) < (P2[Y] - P3[Y])*(P2[X] - P1[X]))
 910       {
 911         swap = TRUE;
 912       }
 913
 914       break;
 915   }
 916
 917   if (swap)
 918   {
 919     temp = Triangle->P2;
 920     Triangle->P2 = Triangle->P1;
 921     Triangle->P1 = temp;
 922
 923     Assign_Vector(T1, P1);
 924     Assign_Vector(P1, P2);
 925     Assign_Vector(P2, T1);
 926
 927     if (Smooth)
 928     {
 929       temp = Triangle->N2;
 930       Triangle->N2 = Triangle->N1;
 931       Triangle->N1 = temp;
 932     }
 933   }
 934
 935   if (Smooth)
 936   {
 937     compute_smooth_triangle(Triangle, P1, P2, P3);
 938   }
 939
 940   return(TRUE);
 941 }
 942
 943
 944
 945 /*****************************************************************************
 946 *
 947 * FUNCTION
 948 *
 949 *   compute_smooth_triangle
 950 *
 951 * INPUT
 952 *
 953 * OUTPUT
 954 *
 955 * RETURNS
 956 *
 957 * AUTHOR
 958 *
 959 *   Dieter Bayer
 960 *
 961 * DESCRIPTION
 962 *
 963 *   -
 964 *
 965 * CHANGES
 966 *
 967 *   Feb 1995 : Creation.
 968 *
 969 ******************************************************************************/
 970
 971 static void compute_smooth_triangle(MESH_TRIANGLE *Triangle, VECTOR P1, VECTOR  P2, VECTOR  P3)
 972 {
 973   VECTOR P3MinusP2, VTemp1, VTemp2;
 974   DBL x, y, z, uDenominator, Proj;
 975
 976   Triangle->Smooth = TRUE;
 977
 978   VSub(P3MinusP2, P3, P2);
 979
 980   x = fabs(P3MinusP2[X]);
 981   y = fabs(P3MinusP2[Y]);
 982   z = fabs(P3MinusP2[Z]);
 983
 984   Triangle->vAxis = max3_coordinate(x, y, z);
 985
 986   VSub(VTemp1, P2, P3);
 987
 988   VNormalize(VTemp1, VTemp1);
 989
 990   VSub(VTemp2, P1, P3);
 991
 992   VDot(Proj, VTemp2, VTemp1);
 993
 994   VScaleEq(VTemp1, Proj);
 995
 996   VSub(Triangle->Perp, VTemp1, VTemp2);
 997
 998   VNormalize(Triangle->Perp, Triangle->Perp);
 999
1000   VDot(uDenominator, VTemp2, Triangle->Perp);
1001
1002   VInverseScaleEq(Triangle->Perp, -uDenominator);
1003 }
1004
1005
1006
1007 /*****************************************************************************
1008 *
1009 * FUNCTION
1010 *
1011 *   intersect_mesh_triangle
1012 *
1013 * INPUT
1014 *
1015 * OUTPUT
1016 *
1017 * RETURNS
1018 *
1019 * AUTHOR
1020 *
1021 *   Dieter Bayer
1022 *
1023 * DESCRIPTION
1024 *
1025 *   -
1026 *
1027 * CHANGES
1028 *
1029 *   Feb 1995 : Creation.
1030 *
1031 ******************************************************************************/
1032
1033 static int intersect_mesh_triangle(RAY *Ray, MESH *Mesh, MESH_TRIANGLE *Triangle, DBL *Depth)
1034 {
1035   DBL NormalDotOrigin, NormalDotDirection;
1036   DBL s, t;
1037   VECTOR P1, P2, P3, S_Normal;
1038
1039   Assign_SNGL_Vect(S_Normal, Mesh->Data->Normals[Triangle->Normal_Ind]);
1040
1041   VDot(NormalDotDirection, S_Normal, Ray->Direction);
1042
1043   if (fabs(NormalDotDirection) < EPSILON)
1044   {
1045     return(FALSE);
1046   }
1047
1048   VDot(NormalDotOrigin, S_Normal, Ray->Initial);
1049
1050   *Depth = -(Triangle->Distance + NormalDotOrigin) / NormalDotDirection;
1051
1052   if ((*Depth < DEPTH_TOLERANCE) || (*Depth > Max_Distance))
1053   {
1054     return(FALSE);
1055   }
1056
1057   get_triangle_vertices(Mesh, Triangle, P1, P2, P3);
1058
1059   switch (Triangle->Dominant_Axis)
1060   {
1061     case X:
1062
1063       s = Ray->Initial[Y] + *Depth * Ray->Direction[Y];
1064       t = Ray->Initial[Z] + *Depth * Ray->Direction[Z];
1065
1066       if ((P2[Y] - s) * (P2[Z] - P1[Z]) < (P2[Z] - t) * (P2[Y] - P1[Y]))
1067       {
1068         return(FALSE);
1069       }
1070
1071       if ((P3[Y] - s) * (P3[Z] - P2[Z]) < (P3[Z] - t) * (P3[Y] - P2[Y]))
1072       {
1073         return(FALSE);
1074       }
1075
1076       if ((P1[Y] - s) * (P1[Z] - P3[Z]) < (P1[Z] - t) * (P1[Y] - P3[Y]))
1077       {
1078         return(FALSE);
1079       }
1080
1081       return(TRUE);
1082
1083     case Y:
1084
1085       s = Ray->Initial[X] + *Depth * Ray->Direction[X];
1086       t = Ray->Initial[Z] + *Depth * Ray->Direction[Z];
1087
1088       if ((P2[X] - s) * (P2[Z] - P1[Z]) < (P2[Z] - t) * (P2[X] - P1[X]))
1089       {
1090         return(FALSE);
1091       }
1092
1093       if ((P3[X] - s) * (P3[Z] - P2[Z]) < (P3[Z] - t) * (P3[X] - P2[X]))
1094       {
1095         return(FALSE);
1096       }
1097
1098       if ((P1[X] - s) * (P1[Z] - P3[Z]) < (P1[Z] - t) * (P1[X] - P3[X]))
1099       {
1100         return(FALSE);
1101       }
1102
1103       return(TRUE);
1104
1105     case Z:
1106
1107       s = Ray->Initial[X] + *Depth * Ray->Direction[X];
1108       t = Ray->Initial[Y] + *Depth * Ray->Direction[Y];
1109
1110       if ((P2[X] - s) * (P2[Y] - P1[Y]) < (P2[Y] - t) * (P2[X] - P1[X]))
1111       {
1112         return(FALSE);
1113       }
1114
1115       if ((P3[X] - s) * (P3[Y] - P2[Y]) < (P3[Y] - t) * (P3[X] - P2[X]))
1116       {
1117         return(FALSE);
1118       }
1119
1120       if ((P1[X] - s) * (P1[Y] - P3[Y]) < (P1[Y] - t) * (P1[X] - P3[X]))
1121       {
1122         return(FALSE);
1123       }
1124
1125       return(TRUE);
1126   }
1127
1128   return(FALSE);
1129 }
1130
1131
1132
1133 /*****************************************************************************
1134 *
1135 * FUNCTION
1136 *
1137 *   test_hit
1138 *
1139 * INPUT
1140 *
1141 * OUTPUT
1142 *
1143 * RETURNS
1144 *
1145 * AUTHOR
1146 *
1147 *   Dieter Bayer
1148 *
1149 * DESCRIPTION
1150 *
1151 *   Test if a hit is valid and push if on the intersection depth.
1152 *
1153 * CHANGES
1154 *
1155 *   Feb 1995 : Creation.
1156 *
1157 ******************************************************************************/
1158
1159 static int test_hit(MESH_TRIANGLE *Triangle, MESH *Mesh, RAY *Ray, DBL Depth, ISTACK *Depth_Stack)
1160 {
1161   VECTOR IPoint;
1162   OBJECT *Object = (OBJECT *)Mesh;
1163
1164   VEvaluateRay(IPoint, Ray->Initial, Depth, Ray->Direction);
1165
1166   if (Point_In_Clip(IPoint, Object->Clip))
1167   {
1168     push_entry_pointer(Depth, IPoint, Object, Triangle, Depth_Stack);
1169
1170     return(TRUE);
1171   }
1172
1173   return(FALSE);
1174 }
1175
1176
1177
1178 /*****************************************************************************
1179 *
1180 * FUNCTION
1181 *
1182 *   Init_Mesh_Triangle
1183 *
1184 * INPUT
1185 *
1186 * OUTPUT
1187 *
1188 * RETURNS
1189 *
1190 * AUTHOR
1191 *
1192 *   Dieter Bayer
1193 *
1194 * DESCRIPTION
1195 *
1196 *   -
1197 *
1198 * CHANGES
1199 *
1200 *   Feb 1995 : Creation.
1201 *
1202 ******************************************************************************/
1203
1204 void Init_Mesh_Triangle(MESH_TRIANGLE *Triangle)
1205 {
1206   Triangle->Smooth = FALSE;
1207
1208   Triangle->Dominant_Axis = 0;
1209   Triangle->vAxis         = 0;
1210
1211   Triangle->P1 =
1212   Triangle->P2 =
1213   Triangle->P3 = -1;
1214
1215   Triangle->Normal_Ind = -1;
1216
1217   Triangle->Texture = -1;
1218
1219   Triangle->N1 =
1220   Triangle->N2 =
1221   Triangle->N3 = -1;
1222
1223   Make_Vector(Triangle->Perp, 0.0, 0.0, 0.0);
1224
1225   Triangle->Distance = 0.0;
1226 }
1227
1228
1229
1230 /*****************************************************************************
1231 *
1232 * FUNCTION
1233 *
1234 *   get_triangle_bbox
1235 *
1236 * INPUT
1237 *
1238 *   Triangle - Pointer to triangle
1239 *
1240 * OUTPUT
1241 *
1242 *   BBox     - Bounding box
1243 *
1244 * RETURNS
1245 *
1246 * AUTHOR
1247 *
1248 *   Dieter Bayer
1249 *
1250 * DESCRIPTION
1251 *
1252 *   Calculate the bounding box of a triangle.
1253 *
1254 * CHANGES
1255 *
1256 *   Sep 1994 : Creation.
1257 *
1258 ******************************************************************************/
1259
1260 static void get_triangle_bbox(MESH *Mesh, MESH_TRIANGLE *Triangle, BBOX *BBox)
1261 {
1262   VECTOR P1, P2, P3;
1263   VECTOR Min, Max;
1264
1265   get_triangle_vertices(Mesh, Triangle, P1, P2, P3);
1266
1267   Min[X] = min3(P1[X], P2[X], P3[X]);
1268   Min[Y] = min3(P1[Y], P2[Y], P3[Y]);
1269   Min[Z] = min3(P1[Z], P2[Z], P3[Z]);
1270
1271   Max[X] = max3(P1[X], P2[X], P3[X]);
1272   Max[Y] = max3(P1[Y], P2[Y], P3[Y]);
1273   Max[Z] = max3(P1[Z], P2[Z], P3[Z]);
1274
1275   Make_BBox_from_min_max(*BBox, Min, Max);
1276 }
1277
1278
1279
1280 /*****************************************************************************
1281 *
1282 * FUNCTION
1283 *
1284 *   Build_Mesh_BBox_Tree
1285 *
1286 * INPUT
1287 *
1288 * OUTPUT
1289 *
1290 * RETURNS
1291 *
1292 * AUTHOR
1293 *
1294 *   Dieter Bayer
1295 *
1296 * DESCRIPTION
1297 *
1298 *   Create the bounding box hierarchy.
1299 *
1300 * CHANGES
1301 *
1302 *   Feb 1995 : Creation. (Derived from the bounding slab creation code)
1303 *
1304 ******************************************************************************/
1305
1306 void Build_Mesh_BBox_Tree(MESH *Mesh)
1307 {
1308   int i, nElem, maxelements;
1309   BBOX_TREE **Triangles;
1310
1311   if (!Test_Flag(Mesh, HIERARCHY_FLAG))
1312   {
1313     return;
1314   }
1315
1316   nElem = (int)Mesh->Data->Number_Of_Triangles;
1317
1318   maxelements = 2 * nElem;
1319
1320   /* Now allocate an array to hold references to these elements. */
1321
1322   Triangles = (BBOX_TREE **)POV_MALLOC(maxelements*sizeof(BBOX_TREE *), "mesh bbox tree");
1323
1324   /* Init list with mesh elements. */
1325
1326   for (i = 0; i < nElem; i++)
1327   {
1328     Triangles[i] = (BBOX_TREE *)POV_MALLOC(sizeof(BBOX_TREE), "mesh bbox tree");
1329
1330     Triangles[i]->Infinite = FALSE;
1331     Triangles[i]->Entries  = 0;
1332     Triangles[i]->Node     = (BBOX_TREE **)&Mesh->Data->Triangles[i];
1333
1334     get_triangle_bbox(Mesh, &Mesh->Data->Triangles[i], &Triangles[i]->BBox);
1335   }
1336
1337   Build_BBox_Tree(&Mesh->Data->Tree, nElem, Triangles, 0, NULL);
1338
1339   /* Get rid of the Triangles array. */
1340
1341   POV_FREE(Triangles);
1342 }
1343
1344
1345
1346 /*****************************************************************************
1347 *
1348 * FUNCTION
1349 *
1350 *   intersect_bbox_tree
1351 *
1352 * INPUT
1353 *
1354 *   Mesh     - Mesh object
1355 *   Ray      - Current ray
1356 *   Orig_Ray - Original, untransformed ray
1357 *   len      - Length of the transformed ray direction
1358 *
1359 * OUTPUT
1360 *
1361 *   Depth_Stack - Stack of intersections
1362 *
1363 * RETURNS
1364 *
1365 *   int - TRUE if an intersection was found
1366 *
1367 * AUTHOR
1368 *
1369 *   Dieter Bayer
1370 *
1371 * DESCRIPTION
1372 *
1373 *   Intersect a ray with the bounding box tree of a mesh.
1374 *
1375 * CHANGES
1376 *
1377 *   Feb 1995 : Creation.
1378 *
1379 ******************************************************************************/
1380
1381 static int intersect_bbox_tree(MESH *Mesh, RAY *Ray, RAY  *Orig_Ray, DBL len, ISTACK *Depth_Stack)
1382 {
1383   int i, found;
1384   DBL Best, Depth;
1385   RAYINFO rayinfo;
1386   BBOX_TREE *Node, *Root;
1387
1388   /* Create the direction vectors for this ray. */
1389
1390   Create_Rayinfo(Ray, &rayinfo);
1391
1392   /* Start with an empty priority queue. */
1393
1394   found = 0;
1395
1396   Mesh_Queue->QSize = 0;
1397
1398   Best = BOUND_HUGE;
1399
1400 #ifdef BBOX_EXTRA_STATS
1401   Increase_Counter(stats[totalQueueResets]);
1402 #endif
1403
1404   /* Check top node. */
1405
1406   Root = Mesh->Data->Tree;
1407
1408   /* Set the root object infinite to avoid a test. */
1409
1410   Check_And_Enqueue(Mesh_Queue, Root, &Root->BBox, &rayinfo);
1411
1412   /* Check elements in the priority queue. */
1413
1414   while (Mesh_Queue->QSize > 0)
1415   {
1416     Priority_Queue_Delete(Mesh_Queue, &Depth, &Node);
1417
1418     /*
1419      * If current intersection is larger than the best intersection found
1420      * so far our task is finished, because all other bounding boxes in
1421      * the priority queue are further away.
1422      */
1423
1424     if (Depth > Best)
1425     {
1426       break;
1427     }
1428
1429     /* Check current node. */
1430
1431     if (Node->Entries)
1432     {
1433       /* This is a node containing leaves to be checked. */
1434
1435       for (i = 0; i < Node->Entries; i++)
1436       {
1437         Check_And_Enqueue(Mesh_Queue, Node->Node[i], &Node->Node[i]->BBox, &rayinfo);
1438       }
1439     }
1440     else
1441     {
1442       /* This is a leaf so test the contained triangle. */
1443
1444       if (intersect_mesh_triangle(Ray, Mesh, (MESH_TRIANGLE *)Node->Node, &Depth))
1445       {
1446         if (test_hit((MESH_TRIANGLE *)Node->Node, Mesh, Orig_Ray, Depth / len, Depth_Stack))
1447         {
1448           found = TRUE;
1449
1450           Best = Depth;
1451         }
1452       }
1453     }
1454   }
1455
1456   return(found);
1457 }
1458
1459
1460
1461 /*****************************************************************************
1462 *
1463 * FUNCTION
1464 *
1465 *   mesh_hash
1466 *
1467 * INPUT
1468 *
1469 *   aPoint - Normal/Vertex to store
1470 *
1471 * OUTPUT
1472 *
1473 *   Hash_Table - Normal/Vertex hash table
1474 *   Number     - Number of normals/vertices
1475 *   Max        - Max. number of normals/vertices
1476 *   Elements   - List of normals/vertices
1477 *
1478 * RETURNS
1479 *
1480 *   int - Index of normal/vertex into the normals/vertices list
1481 *
1482 * AUTHOR
1483 *
1484 *   Dieter Bayer
1485 *
1486 * DESCRIPTION
1487 *
1488 *   Try to locate a triangle normal/vertex in the normal/vertex list.
1489 *   If the vertex is not found its stored in the normal/vertex list.
1490 *
1491 * CHANGES
1492 *
1493 *   Feb 1995 : Creation. (With help from Steve Anger's RAW2POV code)
1494 *
1495 ******************************************************************************/
1496
1497 static int mesh_hash(HASH_TABLE **Hash_Table, int *Number, int  *Max, SNGL_VECT **Elements, VECTOR aPoint)
1498 {
1499   int hash;
1500   SNGL_VECT D, P;
1501   HASH_TABLE *p;
1502
1503   Assign_SNGL_Vect(P, aPoint);
1504
1505   /* Get hash value. */
1506
1507   hash = (unsigned)((int)(326.0*P[X])^(int)(694.7*P[Y])^(int)(1423.6*P[Z])) % HASH_SIZE;
1508
1509   /* Try to find normal/vertex. */
1510
1511   for (p = Hash_Table[hash]; p != NULL; p = p->Next)
1512   {
1513     VSub(D, p->P, P);
1514
1515     if ((fabs(D[X]) < EPSILON) && (fabs(D[Y]) < EPSILON) && (fabs(D[Z]) < EPSILON))
1516     {
1517       break;
1518     }
1519   }
1520
1521   if ((p != NULL) && (p->Index >= 0))
1522   {
1523     return(p->Index);
1524   }
1525
1526   /* Add new normal/vertex to the list and hash table. */
1527
1528   if ((*Number) >= (*Max))
1529   {
1530     if ((*Max) >= INT_MAX/2)
1531     {
1532       Error("Too many normals/vertices in mesh.\n");
1533     }
1534
1535     (*Max) *= 2;
1536
1537     (*Elements) = (SNGL_VECT *)POV_REALLOC((*Elements), (*Max)*sizeof(SNGL_VECT), "mesh data");
1538   }
1539
1540   Assign_SNGL_Vect((*Elements)[*Number], P);
1541
1542   p = (HASH_TABLE *)POV_MALLOC(sizeof(HASH_TABLE), "mesh data");
1543
1544   Assign_SNGL_Vect(p->P, P);
1545
1546   p->Index = *Number;
1547
1548   p->Next = Hash_Table[hash];
1549
1550   Hash_Table[hash] = p;
1551
1552   return((*Number)++);
1553 }
1554
1555
1556
1557 /*****************************************************************************
1558 *
1559 * FUNCTION
1560 *
1561 *   Mesh_Hash_Vertex
1562 *
1563 * INPUT
1564 *
1565 *   Vertex - Vertex to store
1566 *
1567 * OUTPUT
1568 *
1569 *   Number_Of_Vertices - Number of vertices
1570 *   Max_Vertices       - Max. number of vertices
1571 *   Vertices           - List of vertices
1572 *
1573 * RETURNS
1574 *
1575 *   int - Index of vertex into the vertices list
1576 *
1577 * AUTHOR
1578 *
1579 *   Dieter Bayer
1580 *
1581 * DESCRIPTION
1582 *
1583 *   Try to locate a triangle vertex in the vertex list.
1584 *   If the vertex is not found its stored in the vertex list.
1585 *
1586 * CHANGES
1587 *
1588 *   Feb 1995 : Creation. (With help from Steve Anger's RAW2POV code)
1589 *
1590 ******************************************************************************/
1591
1592 int Mesh_Hash_Vertex(int *Number_Of_Vertices, int  *Max_Vertices, SNGL_VECT **Vertices, VECTOR Vertex)
1593 {
1594   return(mesh_hash(Vertex_Hash_Table, Number_Of_Vertices, Max_Vertices, Vertices, Vertex));
1595 }
1596
1597
1598
1599 /*****************************************************************************
1600 *
1601 * FUNCTION
1602 *
1603 *   Mesh_Hash_Normal
1604 *
1605 * INPUT
1606 *
1607 *   Normal - Normal to store
1608 *
1609 * OUTPUT
1610 *
1611 *   Number_Of_Normals - Number of normals
1612 *   Max_Normals       - Max. number of normals
1613 *   Normals           - List of normals
1614 *
1615 * RETURNS
1616 *
1617 *   int - Index of normal into the normals list
1618 *
1619 * AUTHOR
1620 *
1621 *   Dieter Bayer
1622 *
1623 * DESCRIPTION
1624 *
1625 *   Try to locate a triangle normal in the normal list.
1626 *   If the normal is not found its stored in the normal list.
1627 *
1628 * CHANGES
1629 *
1630 *   Feb 1995 : Creation. (With help from Steve Anger's RAW2POV code)
1631 *
1632 ******************************************************************************/
1633
1634 int Mesh_Hash_Normal(int *Number_Of_Normals, int  *Max_Normals, SNGL_VECT **Normals, VECTOR S_Normal)
1635 {
1636   return(mesh_hash(Normal_Hash_Table, Number_Of_Normals, Max_Normals, Normals, S_Normal));
1637 }
1638
1639
1640
1641 /*****************************************************************************
1642 *
1643 * FUNCTION
1644 *
1645 *   Mesh_Hash_Texture
1646 *
1647 * INPUT
1648 *
1649 *   Texture - Texture to store
1650 *
1651 * OUTPUT
1652 *
1653 *   Number_Of_Textures - Number of textures
1654 *   Max_Textures       - Max. number of textures
1655 *   Textures           - List of textures
1656 *
1657 * RETURNS
1658 *
1659 *   int - Index of texture into the texture list
1660 *
1661 * AUTHOR
1662 *
1663 *   Dieter Bayer
1664 *
1665 * DESCRIPTION
1666 *
1667 *   Try to locate a texture in the texture list.
1668 *   If the texture is not found its stored in the texture list.
1669 *
1670 * CHANGES
1671 *
1672 *   Feb 1995 : Creation.
1673 *
1674 ******************************************************************************/
1675
1676 int Mesh_Hash_Texture(int *Number_Of_Textures, int  *Max_Textures, TEXTURE ***Textures, TEXTURE  *Texture)
1677 {
1678   int i;
1679
1680   if (Texture == NULL)
1681   {
1682     return(-1);
1683   }
1684
1685   /* Just do a linear search. */
1686
1687   for (i = 0; i < *Number_Of_Textures; i++)
1688   {
1689     if ((*Textures)[i] == Texture)
1690     {
1691       break;
1692     }
1693   }
1694
1695   if (i == *Number_Of_Textures)
1696   {
1697     if ((*Number_Of_Textures) >= (*Max_Textures))
1698     {
1699       if ((*Max_Textures) >= INT_MAX/2)
1700       {
1701         Error("Too many textures in mesh.\n");
1702       }
1703
1704       (*Max_Textures) *= 2;
1705
1706       (*Textures) = (TEXTURE **)POV_REALLOC((*Textures), (*Max_Textures)*sizeof(TEXTURE *), "mesh data");
1707     }
1708
1709     (*Textures)[(*Number_Of_Textures)++] = Copy_Texture_Pointer(Texture);
1710   }
1711
1712   return(i);
1713 }
1714
1715
1716
1717 /*****************************************************************************
1718 *
1719 * FUNCTION
1720 *
1721 *   Create_Mesh_Hash_Tables
1722 *
1723 * INPUT
1724 *
1725 * OUTPUT
1726 *
1727 * RETURNS
1728 *
1729 * AUTHOR
1730 *
1731 *   Dieter Bayer
1732 *
1733 * DESCRIPTION
1734 *
1735 *   -
1736 *
1737 * CHANGES
1738 *
1739 *   Feb 1995 : Creation.
1740 *
1741 ******************************************************************************/
1742
1743 void Create_Mesh_Hash_Tables()
1744 {
1745   int i;
1746
1747   Vertex_Hash_Table = (HASH_TABLE **)POV_MALLOC(HASH_SIZE*sizeof(HASH_TABLE *), "mesh hash table");
1748
1749   for (i = 0; i < HASH_SIZE; i++)
1750   {
1751     Vertex_Hash_Table[i] = NULL;
1752   }
1753
1754   Normal_Hash_Table = (HASH_TABLE **)POV_MALLOC(HASH_SIZE*sizeof(HASH_TABLE *), "mesh hash table");
1755
1756   for (i = 0; i < HASH_SIZE; i++)
1757   {
1758     Normal_Hash_Table[i] = NULL;
1759   }
1760 }
1761
1762
1763
1764 /*****************************************************************************
1765 *
1766 * FUNCTION
1767 *
1768 *   Destroy_Mesh_Hash_Tables
1769 *
1770 * INPUT
1771 *
1772 * OUTPUT
1773 *
1774 * RETURNS
1775 *
1776 * AUTHOR
1777 *
1778 *   Dieter Bayer
1779 *
1780 * DESCRIPTION
1781 *
1782 *   -
1783 *
1784 * CHANGES
1785 *
1786 *   Feb 1995 : Creation.
1787 *
1788 ******************************************************************************/
1789
1790 void Destroy_Mesh_Hash_Tables()
1791 {
1792   int i;
1793   HASH_TABLE *Temp;
1794
1795   for (i = 0; i < HASH_SIZE; i++)
1796   {
1797     while (Vertex_Hash_Table[i] != NULL)
1798     {
1799       Temp = Vertex_Hash_Table[i];
1800
1801       Vertex_Hash_Table[i] = Temp->Next;
1802
1803       POV_FREE(Temp);
1804     }
1805   }
1806
1807   POV_FREE(Vertex_Hash_Table);
1808
1809   for (i = 0; i < HASH_SIZE; i++)
1810   {
1811     while (Normal_Hash_Table[i] != NULL)
1812     {
1813       Temp = Normal_Hash_Table[i];
1814
1815       Normal_Hash_Table[i] = Temp->Next;
1816
1817       POV_FREE(Temp);
1818     }
1819   }
1820
1821   POV_FREE(Normal_Hash_Table);
1822 }
1823
1824
1825
1826 /*****************************************************************************
1827 *
1828 * FUNCTION
1829 *
1830 *   get_triangle_vertices
1831 *
1832 * INPUT
1833 *
1834 *   Mesh     - Mesh object
1835 *   Triangle - Triangle
1836 *
1837 * OUTPUT
1838 *
1839 * RETURNS
1840 *
1841 *   P1, P2, P3 - Vertices of the triangle
1842 *
1843 * AUTHOR
1844 *
1845 *   Dieter Bayer
1846 *
1847 * DESCRIPTION
1848 *
1849 *   -
1850 *
1851 * CHANGES
1852 *
1853 *   Feb 1995 : Creation.
1854 *
1855 ******************************************************************************/
1856
1857 static void get_triangle_vertices(MESH *Mesh, MESH_TRIANGLE *Triangle, VECTOR P1, VECTOR  P2, VECTOR  P3)
1858 {
1859   Assign_SNGL_Vect(P1, Mesh->Data->Vertices[Triangle->P1]);
1860   Assign_SNGL_Vect(P2, Mesh->Data->Vertices[Triangle->P2]);
1861   Assign_SNGL_Vect(P3, Mesh->Data->Vertices[Triangle->P3]);
1862 }
1863
1864
1865
1866 /*****************************************************************************
1867 *
1868 * FUNCTION
1869 *
1870 *   get_triangle_normals
1871 *
1872 * INPUT
1873 *
1874 *   Mesh     - Mesh object
1875 *   Triangle - Triangle
1876 *
1877 * OUTPUT
1878 *
1879 * RETURNS
1880 *
1881 *   N1, N2, N3 - Normals of the triangle
1882 *
1883 * AUTHOR
1884 *
1885 *   Dieter Bayer
1886 *
1887 * DESCRIPTION
1888 *
1889 *   -
1890 *
1891 * CHANGES
1892 *
1893 *   Feb 1995 : Creation.
1894 *
1895 ******************************************************************************/
1896
1897 static void get_triangle_normals(MESH *Mesh, MESH_TRIANGLE *Triangle, VECTOR N1, VECTOR  N2, VECTOR  N3)
1898 {
1899   Assign_SNGL_Vect(N1, Mesh->Data->Normals[Triangle->N1]);
1900   Assign_SNGL_Vect(N2, Mesh->Data->Normals[Triangle->N2]);
1901   Assign_SNGL_Vect(N3, Mesh->Data->Normals[Triangle->N3]);
1902 }
1903
1904
1905
1906 /*****************************************************************************
1907 *
1908 * FUNCTION
1909 *
1910 *   Mesh_Degenerate
1911 *
1912 * INPUT
1913 *
1914 *   P1, P2, P3 - Triangle's vertices
1915 *
1916 * OUTPUT
1917 *
1918 * RETURNS
1919 *
1920 *   int - TRUE if degenerate
1921 *
1922 * AUTHOR
1923 *
1924 *   Dieter Bayer
1925 *
1926 * DESCRIPTION
1927 *
1928 *   Test if a triangle is degenerate.
1929 *
1930 * CHANGES
1931 *
1932 *   Feb 1995 : Creation.
1933 *
1934 ******************************************************************************/
1935
1936 int Mesh_Degenerate(VECTOR P1, VECTOR  P2, VECTOR  P3)
1937 {
1938   VECTOR V1, V2, Temp;
1939   DBL Length;
1940
1941   VSub(V1, P1, P2);
1942   VSub(V2, P3, P2);
1943
1944   VCross(Temp, V1, V2);
1945
1946   VLength(Length, Temp);
1947
1948   return(Length == 0.0);
1949 }
1950
1951
1952 /*****************************************************************************
1953 *
1954 * FUNCTION
1955 *
1956 *   Initialize_Mesh_Code
1957 *
1958 * INPUT
1959 *
1960 * OUTPUT
1961 *
1962 * RETURNS
1963 *
1964 * AUTHOR
1965 *
1966 *   Dieter Bayer
1967 *
1968 * DESCRIPTION
1969 *
1970 *   Initialize mesh specific variables.
1971 *
1972 * CHANGES
1973 *
1974 *   Jul 1995 : Creation.
1975 *
1976 ******************************************************************************/
1977
1978 void Initialize_Mesh_Code()
1979 {
1980   Mesh_Queue = Create_Priority_Queue(INITIAL_NUMBER_OF_ENTRIES);
1981 }
1982
1983
1984
1985 /*****************************************************************************
1986 *
1987 * FUNCTION
1988 *
1989 *   Deinitialize_Mesh_Code
1990 *
1991 * INPUT
1992 *
1993 * OUTPUT
1994 *
1995 * RETURNS
1996 *
1997 * AUTHOR
1998 *
1999 *   Dieter Bayer
2000 *
2001 * DESCRIPTION
2002 *
2003 *   Deinitialize mesh specific variables.
2004 *
2005 * CHANGES
2006 *
2007 *   Jul 1995 : Creation.
2008 *
2009 ******************************************************************************/
2010
2011 void Deinitialize_Mesh_Code()
2012 {
2013   if (Mesh_Queue != NULL)
2014   {
2015     Destroy_Priority_Queue(Mesh_Queue);
2016   }
2017
2018   Mesh_Queue = NULL;
2019 }
2020
2021
2022
2023 /*****************************************************************************
2024 *
2025 * FUNCTION
2026 *
2027 *   Test_Mesh_Opacity
2028 *
2029 * INPUT
2030 *
2031 *   Mesh - Pointer to mesh structure
2032 *
2033 * OUTPUT
2034 *
2035 *   Mesh
2036 *
2037 * RETURNS
2038 *
2039 * AUTHOR
2040 *
2041 *   Dieter Bayer
2042 *
2043 * DESCRIPTION
2044 *
2045 *   Set the opacity flag of the mesh according to the opacity
2046 *   of the mesh's texture(s).
2047 *
2048 * CHANGES
2049 *
2050 *   Apr 1996 : Creation.
2051 *
2052 ******************************************************************************/
2053
2054 void Test_Mesh_Opacity(MESH *Mesh)
2055 {
2056   int i;
2057
2058   /* Initialize opacity flag to the opacity of the object's texture. */
2059
2060   if ((Mesh->Texture == NULL) || (Test_Opacity(Mesh->Texture)))
2061   {
2062     Set_Flag(Mesh, OPAQUE_FLAG);
2063   }
2064
2065   if (Test_Flag(Mesh, MULTITEXTURE_FLAG))
2066   {
2067     for (i = 0; i < Mesh->Data->Number_Of_Textures; i++)
2068     {
2069       if (Mesh->Data->Textures[i] != NULL)
2070       {
2071         /* If component's texture isn't opaque the mesh is neither. */
2072
2073         if (!Test_Opacity(Mesh->Data->Textures[i]))
2074         {
2075           Clear_Flag(Mesh, OPAQUE_FLAG);
2076         }
2077       }
2078     }
2079   }
2080 }
2081
2082
2083