1 /****************************************************************************
4 * This module implements primitives for mesh objects.
6 * This module was written by Dieter Bayer [DB].
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.
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.
24 *****************************************************************************/
26 /****************************************************************************
36 * triangle { <CORNER1>, <CORNER2>, <CORNER3>, texture { NAME } }
37 * smooth_triangle { <CORNER1>, <NORMAL1>, <CORNER2>, <NORMAL2>, <CORNER3>, <NORMAL3>, texture { NAME } }
44 * Feb 1995 : Creation. [DB]
46 *****************************************************************************/
60 /*****************************************************************************
61 * Local preprocessor defines
62 ******************************************************************************/
64 #define DEPTH_TOLERANCE 1e-6
66 #define max3_coordinate(x,y,z) ((x > y) ? ((x > z) ? X : Z) : ((y > z) ? Y : Z))
68 #define HASH_SIZE 1000
70 #define INITIAL_NUMBER_OF_ENTRIES 256
73 /*****************************************************************************
75 ******************************************************************************/
77 typedef struct Hash_Table_Struct HASH_TABLE
;
79 struct Hash_Table_Struct
88 /*****************************************************************************
90 ******************************************************************************/
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
);
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
);
110 static int intersect_bbox_tree (MESH
*Mesh
, RAY
*Ray
, RAY
*Orig_Ray
, DBL len
, ISTACK
*Depth_Stack
);
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
);
115 static int mesh_hash (HASH_TABLE
**Hash_Table
,
116 int *Number
, int *Max
, SNGL_VECT
**Elements
, VECTOR aPoint
);
120 /*****************************************************************************
122 ******************************************************************************/
124 METHODS Mesh_Methods
=
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
133 static HASH_TABLE
**Vertex_Hash_Table
, **Normal_Hash_Table
;
135 static PRIORITY_QUEUE
*Mesh_Queue
;
139 /*****************************************************************************
143 * All_Mesh_Intersections
161 * Feb 1995 : Creation.
163 ******************************************************************************/
165 static int All_Mesh_Intersections(OBJECT
*Object
, RAY
*Ray
, ISTACK
*Depth_Stack
)
167 Increase_Counter(stats
[Ray_Mesh_Tests
]);
169 if (Intersect_Mesh(Ray
, (MESH
*)Object
, Depth_Stack
))
171 Increase_Counter(stats
[Ray_Mesh_Tests_Succeeded
]);
181 /*****************************************************************************
203 * Feb 1995 : Creation.
205 ******************************************************************************/
207 static int Intersect_Mesh(RAY
*Ray
, MESH
*Mesh
, ISTACK
*Depth_Stack
)
214 /* Transform the ray into mesh space. */
216 if (Mesh
->Trans
!= NULL
)
218 MInvTransPoint(New_Ray
.Initial
, Ray
->Initial
, Mesh
->Trans
);
219 MInvTransDirection(New_Ray
.Direction
, Ray
->Direction
, Mesh
->Trans
);
221 VLength(len
, New_Ray
.Direction
);
222 VInverseScaleEq(New_Ray
.Direction
, len
);
233 if (Mesh
->Data
->Tree
== NULL
)
235 /* There's no bounding hierarchy so just step through all elements. */
237 for (i
= 0; i
< Mesh
->Data
->Number_Of_Triangles
; i
++)
239 if (intersect_mesh_triangle(&New_Ray
, Mesh
, &Mesh
->Data
->Triangles
[i
], &t
))
241 if (test_hit(&Mesh
->Data
->Triangles
[i
], Mesh
, Ray
, t
/ len
, Depth_Stack
))
250 /* Use the mesh's bounding hierarchy. */
252 return(intersect_bbox_tree(Mesh
, &New_Ray
, Ray
, len
, Depth_Stack
));
260 /*****************************************************************************
282 * Feb 1995 : Creation.
284 ******************************************************************************/
286 static int Inside_Mesh(VECTOR IPoint
, OBJECT
*Object
)
293 /*****************************************************************************
311 * Return the normalized normal in the given point.
315 * Feb 1995 : Creation.
317 ******************************************************************************/
319 static void Mesh_Normal(VECTOR Result
, OBJECT
*Object
, INTERSECTION
*Inter
)
322 MESH_TRIANGLE
*Triangle
;
323 MESH
*Mesh
= (MESH
*)Object
;
325 Triangle
= (MESH_TRIANGLE
*)Inter
->Pointer
;
327 if (Triangle
->Smooth
)
329 if (Mesh
->Trans
!= NULL
)
331 MInvTransPoint(IPoint
, Inter
->IPoint
, Mesh
->Trans
);
335 Assign_Vector(IPoint
, Inter
->IPoint
);
338 smooth_mesh_normal(Mesh
, Result
, Triangle
, IPoint
);
340 if (Mesh
->Trans
!= NULL
)
342 MTransNormal(Result
, Result
, Mesh
->Trans
);
345 VNormalize(Result
, Result
);
349 Assign_SNGL_Vect(Result
, Mesh
->Data
->Normals
[Triangle
->Normal_Ind
]);
351 if (Mesh
->Trans
!= NULL
)
353 MTransNormal(Result
, Result
, Mesh
->Trans
);
355 VNormalize(Result
, Result
);
362 /*****************************************************************************
380 * Remove the un-normalized normal of a smoothed triangle.
384 * Feb 1995 : Creation. (Derived from TRIANGLE.C)
386 ******************************************************************************/
388 static void smooth_mesh_normal(MESH
*Mesh
, VECTOR Result
, MESH_TRIANGLE
*Triangle
, VECTOR IPoint
)
393 VECTOR PIMinusP1
, N1
, N2
, N3
;
395 get_triangle_normals(Mesh
, Triangle
, N1
, N2
, N3
);
397 VSub(PIMinusP1
, IPoint
, Mesh
->Data
->Vertices
[Triangle
->P1
]);
399 VDot(u
, PIMinusP1
, Triangle
->Perp
);
403 Assign_Vector(Result
, N1
);
407 axis
= Triangle
->vAxis
;
409 k1
= Mesh
->Data
->Vertices
[Triangle
->P1
][axis
];
410 k2
= Mesh
->Data
->Vertices
[Triangle
->P2
][axis
];
411 k3
= Mesh
->Data
->Vertices
[Triangle
->P3
][axis
];
413 v
= (PIMinusP1
[axis
] / u
+ k1
- k2
) / (k3
- k2
);
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
]));
423 /*****************************************************************************
445 * Feb 1995 : Creation.
447 ******************************************************************************/
449 static void Translate_Mesh(OBJECT
*Object
, VECTOR Vector
, TRANSFORM
*Trans
)
451 Transform_Mesh(Object
, Trans
);
456 /*****************************************************************************
478 * Feb 1995 : Creation.
480 ******************************************************************************/
482 static void Rotate_Mesh(OBJECT
*Object
, VECTOR Vector
, TRANSFORM
*Trans
)
484 Transform_Mesh(Object
, Trans
);
489 /*****************************************************************************
511 * Feb 1995 : Creation.
513 ******************************************************************************/
515 static void Scale_Mesh(OBJECT
*Object
, VECTOR Vector
, TRANSFORM
*Trans
)
517 Transform_Mesh(Object
, Trans
);
522 /*****************************************************************************
544 * Feb 1995 : Creation.
546 ******************************************************************************/
548 static void Transform_Mesh(OBJECT
*Object
, TRANSFORM
*Trans
)
551 if (((MESH
*)Object
)->Trans
== NULL
)
553 ((MESH
*)Object
)->Trans
= Create_Transform();
556 Recompute_BBox(&Object
->BBox
, Trans
);
558 Compose_Transforms(((MESH
*)Object
)->Trans
, Trans
);
560 for (i
=0; i
<((MESH
*)Object
)->Data
->Number_Of_Textures
; i
++)
562 Transform_Textures(((MESH
*)Object
)->Data
->Textures
[i
], Trans
);
568 /*****************************************************************************
590 * Feb 1995 : Creation.
592 ******************************************************************************/
594 static void Invert_Mesh(OBJECT
*Object
)
600 /*****************************************************************************
622 * Feb 1995 : Creation.
624 ******************************************************************************/
630 New
= (MESH
*)POV_MALLOC(sizeof(MESH
), "mesh");
632 INIT_OBJECT_FIELDS(New
,MESH_OBJECT
,&Mesh_Methods
)
634 Set_Flag(New
, HIERARCHY_FLAG
);
645 /*****************************************************************************
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.
672 * Feb 1995 : Creation.
674 ******************************************************************************/
676 static MESH
*Copy_Mesh(OBJECT
*Object
)
684 *New
= *((MESH
*)Object
);
686 New
->Trans
= Copy_Transform(New
->Trans
);
688 New
->Data
->References
++;
695 /*****************************************************************************
717 * Feb 1995 : Creation.
719 ******************************************************************************/
721 static void Destroy_Mesh(OBJECT
*Object
)
724 MESH
*Mesh
= (MESH
*)Object
;
726 Destroy_Transform(Mesh
->Trans
);
728 if (--(Mesh
->Data
->References
) == 0)
730 Destroy_BBox_Tree(Mesh
->Data
->Tree
);
732 if (Mesh
->Data
->Normals
!= NULL
)
734 POV_FREE(Mesh
->Data
->Normals
);
737 if (Mesh
->Data
->Vertices
!= NULL
)
739 POV_FREE(Mesh
->Data
->Vertices
);
742 if (Mesh
->Data
->Triangles
!= NULL
)
744 POV_FREE(Mesh
->Data
->Triangles
);
747 if (Mesh
->Data
->Textures
!= NULL
)
749 for (i
= 0; i
< Mesh
->Data
->Number_Of_Textures
; i
++)
751 Destroy_Textures(Mesh
->Data
->Textures
[i
]);
754 POV_FREE(Mesh
->Data
->Textures
);
757 POV_FREE(Mesh
->Data
);
765 /*****************************************************************************
787 * Calculate the bounding box of a triangle.
791 * Feb 1995 : Creation.
793 ******************************************************************************/
795 void Compute_Mesh_BBox(MESH
*Mesh
)
801 Make_Vector(mins
, BOUND_HUGE
, BOUND_HUGE
, BOUND_HUGE
);
802 Make_Vector(maxs
, -BOUND_HUGE
, -BOUND_HUGE
, -BOUND_HUGE
);
804 for (i
= 0; i
< Mesh
->Data
->Number_Of_Triangles
; i
++)
806 get_triangle_vertices(Mesh
, &Mesh
->Data
->Triangles
[i
], P1
, P2
, P3
);
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
]));
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
]));
817 Make_BBox_from_min_max(Mesh
->BBox
, mins
, maxs
);
822 /*****************************************************************************
844 * Feb 1995 : Creation.
846 ******************************************************************************/
848 int Compute_Mesh_Triangle(MESH_TRIANGLE
*Triangle
, int Smooth
, VECTOR P1
, VECTOR P2
, VECTOR P3
, VECTOR S_Normal
)
858 VCross(S_Normal
, V2
, V1
);
860 VLength(Length
, S_Normal
);
862 /* Set up a flag so we can ignore degenerate triangles */
869 /* Normalize the normal vector. */
871 VInverseScaleEq(S_Normal
, Length
);
873 VDot(Triangle
->Distance
, S_Normal
, P1
);
875 Triangle
->Distance
*= -1.0;
877 /* Find triangle's dominant axis. */
879 x
= fabs(S_Normal
[X
]);
880 y
= fabs(S_Normal
[Y
]);
881 z
= fabs(S_Normal
[Z
]);
883 Triangle
->Dominant_Axis
= max3_coordinate(x
, y
, z
);
887 switch (Triangle
->Dominant_Axis
)
891 if ((P2
[Y
] - P3
[Y
])*(P2
[Z
] - P1
[Z
]) < (P2
[Z
] - P3
[Z
])*(P2
[Y
] - P1
[Y
]))
900 if ((P2
[X
] - P3
[X
])*(P2
[Z
] - P1
[Z
]) < (P2
[Z
] - P3
[Z
])*(P2
[X
] - P1
[X
]))
909 if ((P2
[X
] - P3
[X
])*(P2
[Y
] - P1
[Y
]) < (P2
[Y
] - P3
[Y
])*(P2
[X
] - P1
[X
]))
920 Triangle
->P2
= Triangle
->P1
;
923 Assign_Vector(T1
, P1
);
924 Assign_Vector(P1
, P2
);
925 Assign_Vector(P2
, T1
);
930 Triangle
->N2
= Triangle
->N1
;
937 compute_smooth_triangle(Triangle
, P1
, P2
, P3
);
945 /*****************************************************************************
949 * compute_smooth_triangle
967 * Feb 1995 : Creation.
969 ******************************************************************************/
971 static void compute_smooth_triangle(MESH_TRIANGLE
*Triangle
, VECTOR P1
, VECTOR P2
, VECTOR P3
)
973 VECTOR P3MinusP2
, VTemp1
, VTemp2
;
974 DBL x
, y
, z
, uDenominator
, Proj
;
976 Triangle
->Smooth
= TRUE
;
978 VSub(P3MinusP2
, P3
, P2
);
980 x
= fabs(P3MinusP2
[X
]);
981 y
= fabs(P3MinusP2
[Y
]);
982 z
= fabs(P3MinusP2
[Z
]);
984 Triangle
->vAxis
= max3_coordinate(x
, y
, z
);
986 VSub(VTemp1
, P2
, P3
);
988 VNormalize(VTemp1
, VTemp1
);
990 VSub(VTemp2
, P1
, P3
);
992 VDot(Proj
, VTemp2
, VTemp1
);
994 VScaleEq(VTemp1
, Proj
);
996 VSub(Triangle
->Perp
, VTemp1
, VTemp2
);
998 VNormalize(Triangle
->Perp
, Triangle
->Perp
);
1000 VDot(uDenominator
, VTemp2
, Triangle
->Perp
);
1002 VInverseScaleEq(Triangle
->Perp
, -uDenominator
);
1007 /*****************************************************************************
1011 * intersect_mesh_triangle
1029 * Feb 1995 : Creation.
1031 ******************************************************************************/
1033 static int intersect_mesh_triangle(RAY
*Ray
, MESH
*Mesh
, MESH_TRIANGLE
*Triangle
, DBL
*Depth
)
1035 DBL NormalDotOrigin
, NormalDotDirection
;
1037 VECTOR P1
, P2
, P3
, S_Normal
;
1039 Assign_SNGL_Vect(S_Normal
, Mesh
->Data
->Normals
[Triangle
->Normal_Ind
]);
1041 VDot(NormalDotDirection
, S_Normal
, Ray
->Direction
);
1043 if (fabs(NormalDotDirection
) < EPSILON
)
1048 VDot(NormalDotOrigin
, S_Normal
, Ray
->Initial
);
1050 *Depth
= -(Triangle
->Distance
+ NormalDotOrigin
) / NormalDotDirection
;
1052 if ((*Depth
< DEPTH_TOLERANCE
) || (*Depth
> Max_Distance
))
1057 get_triangle_vertices(Mesh
, Triangle
, P1
, P2
, P3
);
1059 switch (Triangle
->Dominant_Axis
)
1063 s
= Ray
->Initial
[Y
] + *Depth
* Ray
->Direction
[Y
];
1064 t
= Ray
->Initial
[Z
] + *Depth
* Ray
->Direction
[Z
];
1066 if ((P2
[Y
] - s
) * (P2
[Z
] - P1
[Z
]) < (P2
[Z
] - t
) * (P2
[Y
] - P1
[Y
]))
1071 if ((P3
[Y
] - s
) * (P3
[Z
] - P2
[Z
]) < (P3
[Z
] - t
) * (P3
[Y
] - P2
[Y
]))
1076 if ((P1
[Y
] - s
) * (P1
[Z
] - P3
[Z
]) < (P1
[Z
] - t
) * (P1
[Y
] - P3
[Y
]))
1085 s
= Ray
->Initial
[X
] + *Depth
* Ray
->Direction
[X
];
1086 t
= Ray
->Initial
[Z
] + *Depth
* Ray
->Direction
[Z
];
1088 if ((P2
[X
] - s
) * (P2
[Z
] - P1
[Z
]) < (P2
[Z
] - t
) * (P2
[X
] - P1
[X
]))
1093 if ((P3
[X
] - s
) * (P3
[Z
] - P2
[Z
]) < (P3
[Z
] - t
) * (P3
[X
] - P2
[X
]))
1098 if ((P1
[X
] - s
) * (P1
[Z
] - P3
[Z
]) < (P1
[Z
] - t
) * (P1
[X
] - P3
[X
]))
1107 s
= Ray
->Initial
[X
] + *Depth
* Ray
->Direction
[X
];
1108 t
= Ray
->Initial
[Y
] + *Depth
* Ray
->Direction
[Y
];
1110 if ((P2
[X
] - s
) * (P2
[Y
] - P1
[Y
]) < (P2
[Y
] - t
) * (P2
[X
] - P1
[X
]))
1115 if ((P3
[X
] - s
) * (P3
[Y
] - P2
[Y
]) < (P3
[Y
] - t
) * (P3
[X
] - P2
[X
]))
1120 if ((P1
[X
] - s
) * (P1
[Y
] - P3
[Y
]) < (P1
[Y
] - t
) * (P1
[X
] - P3
[X
]))
1133 /*****************************************************************************
1151 * Test if a hit is valid and push if on the intersection depth.
1155 * Feb 1995 : Creation.
1157 ******************************************************************************/
1159 static int test_hit(MESH_TRIANGLE
*Triangle
, MESH
*Mesh
, RAY
*Ray
, DBL Depth
, ISTACK
*Depth_Stack
)
1162 OBJECT
*Object
= (OBJECT
*)Mesh
;
1164 VEvaluateRay(IPoint
, Ray
->Initial
, Depth
, Ray
->Direction
);
1166 if (Point_In_Clip(IPoint
, Object
->Clip
))
1168 push_entry_pointer(Depth
, IPoint
, Object
, Triangle
, Depth_Stack
);
1178 /*****************************************************************************
1182 * Init_Mesh_Triangle
1200 * Feb 1995 : Creation.
1202 ******************************************************************************/
1204 void Init_Mesh_Triangle(MESH_TRIANGLE
*Triangle
)
1206 Triangle
->Smooth
= FALSE
;
1208 Triangle
->Dominant_Axis
= 0;
1209 Triangle
->vAxis
= 0;
1215 Triangle
->Normal_Ind
= -1;
1217 Triangle
->Texture
= -1;
1223 Make_Vector(Triangle
->Perp
, 0.0, 0.0, 0.0);
1225 Triangle
->Distance
= 0.0;
1230 /*****************************************************************************
1238 * Triangle - Pointer to triangle
1242 * BBox - Bounding box
1252 * Calculate the bounding box of a triangle.
1256 * Sep 1994 : Creation.
1258 ******************************************************************************/
1260 static void get_triangle_bbox(MESH
*Mesh
, MESH_TRIANGLE
*Triangle
, BBOX
*BBox
)
1265 get_triangle_vertices(Mesh
, Triangle
, P1
, P2
, P3
);
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
]);
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
]);
1275 Make_BBox_from_min_max(*BBox
, Min
, Max
);
1280 /*****************************************************************************
1284 * Build_Mesh_BBox_Tree
1298 * Create the bounding box hierarchy.
1302 * Feb 1995 : Creation. (Derived from the bounding slab creation code)
1304 ******************************************************************************/
1306 void Build_Mesh_BBox_Tree(MESH
*Mesh
)
1308 int i
, nElem
, maxelements
;
1309 BBOX_TREE
**Triangles
;
1311 if (!Test_Flag(Mesh
, HIERARCHY_FLAG
))
1316 nElem
= (int)Mesh
->Data
->Number_Of_Triangles
;
1318 maxelements
= 2 * nElem
;
1320 /* Now allocate an array to hold references to these elements. */
1322 Triangles
= (BBOX_TREE
**)POV_MALLOC(maxelements
*sizeof(BBOX_TREE
*), "mesh bbox tree");
1324 /* Init list with mesh elements. */
1326 for (i
= 0; i
< nElem
; i
++)
1328 Triangles
[i
] = (BBOX_TREE
*)POV_MALLOC(sizeof(BBOX_TREE
), "mesh bbox tree");
1330 Triangles
[i
]->Infinite
= FALSE
;
1331 Triangles
[i
]->Entries
= 0;
1332 Triangles
[i
]->Node
= (BBOX_TREE
**)&Mesh
->Data
->Triangles
[i
];
1334 get_triangle_bbox(Mesh
, &Mesh
->Data
->Triangles
[i
], &Triangles
[i
]->BBox
);
1337 Build_BBox_Tree(&Mesh
->Data
->Tree
, nElem
, Triangles
, 0, NULL
);
1339 /* Get rid of the Triangles array. */
1341 POV_FREE(Triangles
);
1346 /*****************************************************************************
1350 * intersect_bbox_tree
1354 * Mesh - Mesh object
1356 * Orig_Ray - Original, untransformed ray
1357 * len - Length of the transformed ray direction
1361 * Depth_Stack - Stack of intersections
1365 * int - TRUE if an intersection was found
1373 * Intersect a ray with the bounding box tree of a mesh.
1377 * Feb 1995 : Creation.
1379 ******************************************************************************/
1381 static int intersect_bbox_tree(MESH
*Mesh
, RAY
*Ray
, RAY
*Orig_Ray
, DBL len
, ISTACK
*Depth_Stack
)
1386 BBOX_TREE
*Node
, *Root
;
1388 /* Create the direction vectors for this ray. */
1390 Create_Rayinfo(Ray
, &rayinfo
);
1392 /* Start with an empty priority queue. */
1396 Mesh_Queue
->QSize
= 0;
1400 #ifdef BBOX_EXTRA_STATS
1401 Increase_Counter(stats
[totalQueueResets
]);
1404 /* Check top node. */
1406 Root
= Mesh
->Data
->Tree
;
1408 /* Set the root object infinite to avoid a test. */
1410 Check_And_Enqueue(Mesh_Queue
, Root
, &Root
->BBox
, &rayinfo
);
1412 /* Check elements in the priority queue. */
1414 while (Mesh_Queue
->QSize
> 0)
1416 Priority_Queue_Delete(Mesh_Queue
, &Depth
, &Node
);
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.
1429 /* Check current node. */
1433 /* This is a node containing leaves to be checked. */
1435 for (i
= 0; i
< Node
->Entries
; i
++)
1437 Check_And_Enqueue(Mesh_Queue
, Node
->Node
[i
], &Node
->Node
[i
]->BBox
, &rayinfo
);
1442 /* This is a leaf so test the contained triangle. */
1444 if (intersect_mesh_triangle(Ray
, Mesh
, (MESH_TRIANGLE
*)Node
->Node
, &Depth
))
1446 if (test_hit((MESH_TRIANGLE
*)Node
->Node
, Mesh
, Orig_Ray
, Depth
/ len
, Depth_Stack
))
1461 /*****************************************************************************
1469 * aPoint - Normal/Vertex to store
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
1480 * int - Index of normal/vertex into the normals/vertices list
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.
1493 * Feb 1995 : Creation. (With help from Steve Anger's RAW2POV code)
1495 ******************************************************************************/
1497 static int mesh_hash(HASH_TABLE
**Hash_Table
, int *Number
, int *Max
, SNGL_VECT
**Elements
, VECTOR aPoint
)
1503 Assign_SNGL_Vect(P
, aPoint
);
1505 /* Get hash value. */
1507 hash
= (unsigned)((int)(326.0*P
[X
])^(int)(694.7*P
[Y
])^(int)(1423.6*P
[Z
])) % HASH_SIZE
;
1509 /* Try to find normal/vertex. */
1511 for (p
= Hash_Table
[hash
]; p
!= NULL
; p
= p
->Next
)
1515 if ((fabs(D
[X
]) < EPSILON
) && (fabs(D
[Y
]) < EPSILON
) && (fabs(D
[Z
]) < EPSILON
))
1521 if ((p
!= NULL
) && (p
->Index
>= 0))
1526 /* Add new normal/vertex to the list and hash table. */
1528 if ((*Number
) >= (*Max
))
1530 if ((*Max
) >= INT_MAX
/2)
1532 Error("Too many normals/vertices in mesh.\n");
1537 (*Elements
) = (SNGL_VECT
*)POV_REALLOC((*Elements
), (*Max
)*sizeof(SNGL_VECT
), "mesh data");
1540 Assign_SNGL_Vect((*Elements
)[*Number
], P
);
1542 p
= (HASH_TABLE
*)POV_MALLOC(sizeof(HASH_TABLE
), "mesh data");
1544 Assign_SNGL_Vect(p
->P
, P
);
1548 p
->Next
= Hash_Table
[hash
];
1550 Hash_Table
[hash
] = p
;
1552 return((*Number
)++);
1557 /*****************************************************************************
1565 * Vertex - Vertex to store
1569 * Number_Of_Vertices - Number of vertices
1570 * Max_Vertices - Max. number of vertices
1571 * Vertices - List of vertices
1575 * int - Index of vertex into the vertices list
1583 * Try to locate a triangle vertex in the vertex list.
1584 * If the vertex is not found its stored in the vertex list.
1588 * Feb 1995 : Creation. (With help from Steve Anger's RAW2POV code)
1590 ******************************************************************************/
1592 int Mesh_Hash_Vertex(int *Number_Of_Vertices
, int *Max_Vertices
, SNGL_VECT
**Vertices
, VECTOR Vertex
)
1594 return(mesh_hash(Vertex_Hash_Table
, Number_Of_Vertices
, Max_Vertices
, Vertices
, Vertex
));
1599 /*****************************************************************************
1607 * Normal - Normal to store
1611 * Number_Of_Normals - Number of normals
1612 * Max_Normals - Max. number of normals
1613 * Normals - List of normals
1617 * int - Index of normal into the normals list
1625 * Try to locate a triangle normal in the normal list.
1626 * If the normal is not found its stored in the normal list.
1630 * Feb 1995 : Creation. (With help from Steve Anger's RAW2POV code)
1632 ******************************************************************************/
1634 int Mesh_Hash_Normal(int *Number_Of_Normals
, int *Max_Normals
, SNGL_VECT
**Normals
, VECTOR S_Normal
)
1636 return(mesh_hash(Normal_Hash_Table
, Number_Of_Normals
, Max_Normals
, Normals
, S_Normal
));
1641 /*****************************************************************************
1649 * Texture - Texture to store
1653 * Number_Of_Textures - Number of textures
1654 * Max_Textures - Max. number of textures
1655 * Textures - List of textures
1659 * int - Index of texture into the texture list
1667 * Try to locate a texture in the texture list.
1668 * If the texture is not found its stored in the texture list.
1672 * Feb 1995 : Creation.
1674 ******************************************************************************/
1676 int Mesh_Hash_Texture(int *Number_Of_Textures
, int *Max_Textures
, TEXTURE
***Textures
, TEXTURE
*Texture
)
1680 if (Texture
== NULL
)
1685 /* Just do a linear search. */
1687 for (i
= 0; i
< *Number_Of_Textures
; i
++)
1689 if ((*Textures
)[i
] == Texture
)
1695 if (i
== *Number_Of_Textures
)
1697 if ((*Number_Of_Textures
) >= (*Max_Textures
))
1699 if ((*Max_Textures
) >= INT_MAX
/2)
1701 Error("Too many textures in mesh.\n");
1704 (*Max_Textures
) *= 2;
1706 (*Textures
) = (TEXTURE
**)POV_REALLOC((*Textures
), (*Max_Textures
)*sizeof(TEXTURE
*), "mesh data");
1709 (*Textures
)[(*Number_Of_Textures
)++] = Copy_Texture_Pointer(Texture
);
1717 /*****************************************************************************
1721 * Create_Mesh_Hash_Tables
1739 * Feb 1995 : Creation.
1741 ******************************************************************************/
1743 void Create_Mesh_Hash_Tables()
1747 Vertex_Hash_Table
= (HASH_TABLE
**)POV_MALLOC(HASH_SIZE
*sizeof(HASH_TABLE
*), "mesh hash table");
1749 for (i
= 0; i
< HASH_SIZE
; i
++)
1751 Vertex_Hash_Table
[i
] = NULL
;
1754 Normal_Hash_Table
= (HASH_TABLE
**)POV_MALLOC(HASH_SIZE
*sizeof(HASH_TABLE
*), "mesh hash table");
1756 for (i
= 0; i
< HASH_SIZE
; i
++)
1758 Normal_Hash_Table
[i
] = NULL
;
1764 /*****************************************************************************
1768 * Destroy_Mesh_Hash_Tables
1786 * Feb 1995 : Creation.
1788 ******************************************************************************/
1790 void Destroy_Mesh_Hash_Tables()
1795 for (i
= 0; i
< HASH_SIZE
; i
++)
1797 while (Vertex_Hash_Table
[i
] != NULL
)
1799 Temp
= Vertex_Hash_Table
[i
];
1801 Vertex_Hash_Table
[i
] = Temp
->Next
;
1807 POV_FREE(Vertex_Hash_Table
);
1809 for (i
= 0; i
< HASH_SIZE
; i
++)
1811 while (Normal_Hash_Table
[i
] != NULL
)
1813 Temp
= Normal_Hash_Table
[i
];
1815 Normal_Hash_Table
[i
] = Temp
->Next
;
1821 POV_FREE(Normal_Hash_Table
);
1826 /*****************************************************************************
1830 * get_triangle_vertices
1834 * Mesh - Mesh object
1835 * Triangle - Triangle
1841 * P1, P2, P3 - Vertices of the triangle
1853 * Feb 1995 : Creation.
1855 ******************************************************************************/
1857 static void get_triangle_vertices(MESH
*Mesh
, MESH_TRIANGLE
*Triangle
, VECTOR P1
, VECTOR P2
, VECTOR P3
)
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
]);
1866 /*****************************************************************************
1870 * get_triangle_normals
1874 * Mesh - Mesh object
1875 * Triangle - Triangle
1881 * N1, N2, N3 - Normals of the triangle
1893 * Feb 1995 : Creation.
1895 ******************************************************************************/
1897 static void get_triangle_normals(MESH
*Mesh
, MESH_TRIANGLE
*Triangle
, VECTOR N1
, VECTOR N2
, VECTOR N3
)
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
]);
1906 /*****************************************************************************
1914 * P1, P2, P3 - Triangle's vertices
1920 * int - TRUE if degenerate
1928 * Test if a triangle is degenerate.
1932 * Feb 1995 : Creation.
1934 ******************************************************************************/
1936 int Mesh_Degenerate(VECTOR P1
, VECTOR P2
, VECTOR P3
)
1938 VECTOR V1
, V2
, Temp
;
1944 VCross(Temp
, V1
, V2
);
1946 VLength(Length
, Temp
);
1948 return(Length
== 0.0);
1952 /*****************************************************************************
1956 * Initialize_Mesh_Code
1970 * Initialize mesh specific variables.
1974 * Jul 1995 : Creation.
1976 ******************************************************************************/
1978 void Initialize_Mesh_Code()
1980 Mesh_Queue
= Create_Priority_Queue(INITIAL_NUMBER_OF_ENTRIES
);
1985 /*****************************************************************************
1989 * Deinitialize_Mesh_Code
2003 * Deinitialize mesh specific variables.
2007 * Jul 1995 : Creation.
2009 ******************************************************************************/
2011 void Deinitialize_Mesh_Code()
2013 if (Mesh_Queue
!= NULL
)
2015 Destroy_Priority_Queue(Mesh_Queue
);
2023 /*****************************************************************************
2031 * Mesh - Pointer to mesh structure
2045 * Set the opacity flag of the mesh according to the opacity
2046 * of the mesh's texture(s).
2050 * Apr 1996 : Creation.
2052 ******************************************************************************/
2054 void Test_Mesh_Opacity(MESH
*Mesh
)
2058 /* Initialize opacity flag to the opacity of the object's texture. */
2060 if ((Mesh
->Texture
== NULL
) || (Test_Opacity(Mesh
->Texture
)))
2062 Set_Flag(Mesh
, OPAQUE_FLAG
);
2065 if (Test_Flag(Mesh
, MULTITEXTURE_FLAG
))
2067 for (i
= 0; i
< Mesh
->Data
->Number_Of_Textures
; i
++)
2069 if (Mesh
->Data
->Textures
[i
] != NULL
)
2071 /* If component's texture isn't opaque the mesh is neither. */
2073 if (!Test_Opacity(Mesh
->Data
->Textures
[i
]))
2075 Clear_Flag(Mesh
, OPAQUE_FLAG
);