1 /****************************************************************************
2 * lbuffer.cpp
3 *
4 * This module implements functions that implement the light buffer.
5 *
6 * This module was written by Dieter Bayer [DB].
7 *
8 * from Persistence of Vision(tm) Ray Tracer version 3.6.
9 * Copyright 1991-2003 Persistence of Vision Team
10 * Copyright 2003-2004 Persistence of Vision Raytracer Pty. Ltd.
11 *---------------------------------------------------------------------------
12 * NOTICE: This source code file is provided so that users may experiment
13 * with enhancements to POV-Ray and to port the software to platforms other
14 * than those supported by the POV-Ray developers. There are strict rules
15 * regarding how you are permitted to use this file. These rules are contained
16 * in the distribution and derivative versions licenses which should have been
17 * provided with this file.
18 *
19 * These licences may be found online, linked from the end-user license
20 * agreement that is located at http://www.povray.org/povlegal.html
21 *---------------------------------------------------------------------------
22 * This program is based on the popular DKB raytracer version 2.12.
23 * DKBTrace was originally written by David K. Buck.
24 * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
25 *---------------------------------------------------------------------------
26 *
27 *===========================================================================
28 * This file is part of MegaPOV, a modified and unofficial version of POV-Ray
29 * For more information on MegaPOV visit our website:
30 * http://megapov.inetart.net/
31 *===========================================================================
32 *
33 * $RCSfile: lbuffer.cpp,v $
34 * $Revision: 1.15 $
35 * $Author: chris $
36 *
37 *****************************************************************************/
38
39 #include "frame.h"
40 #include "vector.h"
41 #include "point.h"
42 #include "povray.h"
43 #include "bbox.h"
44 #include "lbuffer.h"
45 #include "objects.h"
46 #include "triangle.h"
47 #include "vlbuffer.h"
48 #include "optout.h"
49 #include "lightgrp.h"
50 #include "povmsend.h"
51
52 #include <algorithm>
53
54 BEGIN_POV_NAMESPACE
55
56 /*****************************************************************************
57 * Global variabls
58 ******************************************************************************/
59
60 extern PRIORITY_QUEUE *VLBuffer_Queue; // GLOBAL VARIABLE
61 extern PROJECT_QUEUE *Node_Queue; // GLOBAL VARIABLE
62
63
64 /*****************************************************************************
65 * Local preprocessor defines
66 ******************************************************************************/
67
68
69
70 /*****************************************************************************
71 * Local typedefs
72 ******************************************************************************/
73
74
75
76 /*****************************************************************************
77 * Local variabls
78 ******************************************************************************/
79
80 /*YS 29 april 2000 bugfix*/
81 static bool BuffersInit=false; // GLOBAL VARIABLE
82 /*YS 29 april 2000 bugfix*/
83
84 /* Planes for 3d-clipping. */
85
86 const VECTOR VIEW_VX1 = {-0.7071067812, 0.0, -0.7071067812};
87 const VECTOR VIEW_VX2 = { 0.7071067812, 0.0, -0.7071067812};
88 const VECTOR VIEW_VY1 = {0.0, -0.7071067812, -0.7071067812};
89 const VECTOR VIEW_VY2 = {0.0, 0.7071067812, -0.7071067812};
90 static DBL VIEW_DX1 = 0.0; // GLOBAL VARIABLE
91 static DBL VIEW_DX2 = 0.0; // GLOBAL VARIABLE
92 static DBL VIEW_DY1 = 0.0; // GLOBAL VARIABLE
93 static DBL VIEW_DY2 = 0.0; // GLOBAL VARIABLE
94
95
96
97 /*****************************************************************************
98 * Static functions
99 ******************************************************************************/
100
101 static void calc_points (int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR Origin);
102
103 static int bbox_invisible (int Axis, BBOX *BBox, VECTOR Origin);
104
105 static void project_rectangle (PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible);
106 static void project_triangle (PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible);
107 static void project_bbox (PROJECT *Project, VECTOR *P, int *visible);
108 static void project_object (PROJECT *Project, OBJECT *Object, int Axis, VECTOR Origin, int proj_thru, PROJECT *proj_proj);
109 static int intersect_projects( PROJECT *Project1, PROJECT *Project2 );
110
111 static void project_bounding_slab (int Axis, VECTOR Origin,
112 PROJECT *Project, PROJECT_TREE_NODE **Entry, BBOX_TREE *Node, int proj_thru, PROJECT *proj_proj);
113
114
115
intersect_projects(PROJECT * Project1,PROJECT * Project2)116 int intersect_projects( PROJECT *Project1, PROJECT *Project2 ) {
117
118 /* 1 is empty */
119 if ( Project1->x1 > Project1->x2 ) return 0;
120 if ( Project1->y1 > Project1->y2 ) return 0;
121 /* 2 is empty */
122 if ( Project2->x1 > Project2->x2 ) return 0;
123 if ( Project2->y1 > Project2->y2 ) return 0;
124 /* 1 is to the left of 2 */
125 if ( Project1->x2 < Project2->x1 ) return 0;
126 /* 1 is above 2 */
127 if ( Project1->y2 < Project2->y1 ) return 0;
128 /* 1 is to the right of 2 */
129 if ( Project1->x1 > Project2->x2 ) return 0;
130 /* 1 is below 2 */
131 if ( Project1->y1 > Project2->y2 ) return 0;
132 /* At this point, the rectangles overlap in some way */
133 return 1;
134 }
135
136 /*****************************************************************************
137 *
138 * FUNCTION
139 *
140 * calc_points
141 *
142 * INPUT
143 *
144 * Axis - Axis along the objects will be projected
145 * Object - Object
146 * Number - Number of points to project
147 * Points - Points to project
148 * Origin - Origin of current light source
149 *
150 * OUTPUT
151 *
152 * Number, Points
153 *
154 * RETURNS
155 *
156 * AUTHOR
157 *
158 * Dieter Bayer
159 *
160 * DESCRIPTION
161 *
162 * Calculate the points to project depending on the object type,
163 * the light source position and the axis. Note that only three
164 * points are used for triangles and eight for all other objects.
165 *
166 * CHANGES
167 *
168 * May 1994 : Creation.
169 *
170 ******************************************************************************/
171
calc_points(int Axis,OBJECT * Object,int * Number,VECTOR * Points,VECTOR Origin)172 static void calc_points(int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR Origin)
173 {
174 register int i;
175 DBL Direction;
176 VECTOR H[8];
177
178 /* Get points depending on object's type */
179
180 if ((Object->Methods != &Triangle_Methods) &&
181 (Object->Methods != &Smooth_Triangle_Methods))
182 {
183 *Number = 8;
184
185 for (i = 0; i < 8; i++)
186 {
187 H[i][X] = ((i & 1) ? Object->BBox.Lengths[X] : 0.0) + Object->BBox.Lower_Left[X];
188 H[i][Y] = ((i & 2) ? Object->BBox.Lengths[Y] : 0.0) + Object->BBox.Lower_Left[Y];
189 H[i][Z] = ((i & 4) ? Object->BBox.Lengths[Z] : 0.0) + Object->BBox.Lower_Left[Z];
190 }
191 }
192 else
193 {
194 if (Object->Methods == &Triangle_Methods)
195 {
196 *Number = 3;
197
198 Assign_Vector(H[0], ((TRIANGLE *)Object)->P1);
199 Assign_Vector(H[1], ((TRIANGLE *)Object)->P2);
200 Assign_Vector(H[2], ((TRIANGLE *)Object)->P3);
201 }
202
203 if (Object->Methods == &Smooth_Triangle_Methods)
204 {
205 *Number = 3;
206
207 Assign_Vector(H[0], ((SMOOTH_TRIANGLE *)Object)->P1);
208 Assign_Vector(H[1], ((SMOOTH_TRIANGLE *)Object)->P2);
209 Assign_Vector(H[2], ((SMOOTH_TRIANGLE *)Object)->P3);
210 }
211 }
212
213 /* Modify points so that the new z direction is the projection axis. */
214
215 if ((Axis == XaxisP) || (Axis == YaxisP) || (Axis == ZaxisP))
216 {
217 Direction = 1.0;
218 }
219 else
220 {
221 Direction = -1.0;
222 }
223
224 switch (Axis)
225 {
226 case XaxisP :
227 case XaxisM :
228
229 for (i = 0; i < *Number; i++)
230 {
231 Points[i][X] = (H[i][Y] - Origin[Y]);
232 Points[i][Y] = (H[i][Z] - Origin[Z]);
233 Points[i][Z] = (H[i][X] - Origin[X]) * Direction;
234 }
235
236 break;
237
238 case YaxisP :
239 case YaxisM :
240
241 for (i = 0; i < *Number; i++)
242 {
243 Points[i][X] = (H[i][X] - Origin[X]);
244 Points[i][Y] = (H[i][Z] - Origin[Z]);
245 Points[i][Z] = (H[i][Y] - Origin[Y]) * Direction;
246 }
247
248 break;
249
250 case ZaxisP :
251 case ZaxisM :
252
253 for (i = 0; i < *Number; i++)
254 {
255 Points[i][X] = (H[i][X] - Origin[X]);
256 Points[i][Y] = (H[i][Y] - Origin[Y]);
257 Points[i][Z] = (H[i][Z] - Origin[Z]) * Direction;
258 }
259
260 break;
261
262 default : Error("Illegal axis in module calc_points() in lbuffer.c.");
263 }
264 }
265
266
267
268 /*****************************************************************************
269 *
270 * FUNCTION
271 *
272 * bbox_invisible
273 *
274 * INPUT
275 *
276 * Axis - Axis along the objects will be projected
277 * BBox - Bounding box to test
278 * Origin - Origin of current light source
279 *
280 * OUTPUT
281 *
282 * RETURNS
283 *
284 * int - Flag if bounding box is totally invisble
285 *
286 * AUTHOR
287 *
288 * Dieter Bayer
289 *
290 * DESCRIPTION
291 *
292 * Do a quick test if a bounding box is totally invisble from the
293 * current light source in the specified axis direction.
294 *
295 * CHANGES
296 *
297 * May 1994 : Creation.
298 *
299 ******************************************************************************/
300
bbox_invisible(int Axis,BBOX * BBox,VECTOR Origin)301 static int bbox_invisible(int Axis, BBOX *BBox, VECTOR Origin)
302 {
303 DBL x1, y1, z1, x2, y2, z2, x, y, z;
304
305 switch (Axis)
306 {
307 case XaxisP :
308
309 /* Bounding box behind light source? */
310
311 if ((x = BBox->Lower_Left[X] + BBox->Lengths[X] - Origin[X]) <= 0.0)
312 {
313 return(true);
314 }
315
316 /* Bounding box on the right/left side? */
317
318 y1 = BBox->Lower_Left[Y] - Origin[Y];
319 y2 = y1 + BBox->Lengths[Y];
320
321 if (((y1 > 0.0) && (y1 > x)) || ((y2 < 0.0) && (-y2 > x)))
322 {
323 return(true);
324 }
325
326 /* Bounding box on the bottom/top side? */
327
328 z1 = BBox->Lower_Left[Z] - Origin[Z];
329 z2 = z1 + BBox->Lengths[Z];
330
331 if (((z1 > 0.0) && (z1 > x)) || ((z2 < 0.0) && (-z2 > x)))
332 {
333 return(true);
334 }
335
336 break;
337
338 case XaxisM :
339
340 /* Bounding box behind light source? */
341
342 if ((x = BBox->Lower_Left[X] - Origin[X]) >= 0.0)
343 {
344 return(true);
345 }
346
347 /* Bounding box on the right/left side? */
348
349 y1 = BBox->Lower_Left[Y] - Origin[Y];
350 y2 = y1 + BBox->Lengths[Y];
351
352 if (((y1 > 0.0) && (y1 > -x)) || ((y2 < 0.0) && (y2 < x)))
353 {
354 return(true);
355 }
356
357 /* Bounding box on the bottom/top side? */
358
359 z1 = BBox->Lower_Left[Z] - Origin[Z];
360 z2 = z1 + BBox->Lengths[Z];
361
362 if (((z1 > 0.0) && (z1 > -x)) || ((z2 < 0.0) && (z2 < x)))
363 {
364 return(true);
365 }
366
367 break;
368
369 case YaxisP :
370
371 /* Bounding box behind light source? */
372
373 if ((y = BBox->Lower_Left[Y] + BBox->Lengths[Y] - Origin[Y]) <= 0.0)
374 {
375 return(true);
376 }
377
378 /* Bounding box on the right/left side? */
379
380 x1 = BBox->Lower_Left[X] - Origin[X];
381 x2 = x1 + BBox->Lengths[X];
382
383 if (((x1 > 0.0) && (x1 > y)) || ((x2 < 0.0) && (-x2 > y)))
384 {
385 return(true);
386 }
387
388 /* Bounding box on the bottom/top side? */
389
390 z1 = BBox->Lower_Left[Z] - Origin[Z];
391 z2 = z1 + BBox->Lengths[Z];
392
393 if (((z1 > 0.0) && (z1 > y)) || ((z2 < 0.0) && (-z2 > y)))
394 {
395 return(true);
396 }
397
398 break;
399
400 case YaxisM :
401
402 /* Bounding box behind light source? */
403
404 if ((y = BBox->Lower_Left[Y] - Origin[Y]) >= 0.0)
405 {
406 return(true);
407 }
408
409 /* Bounding box on the right/left side? */
410
411 x1 = BBox->Lower_Left[X] - Origin[X];
412 x2 = x1 + BBox->Lengths[X];
413
414 if (((x1 > 0.0) && (x1 > -y)) || ((x2 < 0.0) && (x2 < y)))
415 {
416 return(true);
417 }
418
419 /* Bounding box on the bottom/top side? */
420
421 z1 = BBox->Lower_Left[Z] - Origin[Z];
422 z2 = z1 + BBox->Lengths[Z];
423
424 if (((z1 > 0.0) && (z1 > -y)) || ((z2 < 0.0) && (z2 < y)))
425 {
426 return(true);
427 }
428
429 break;
430
431 case ZaxisP :
432
433 /* Bounding box behind light source? */
434
435 if ((z = BBox->Lower_Left[Z] + BBox->Lengths[Z] - Origin[Z]) <= 0.0)
436 {
437 return(true);
438 }
439
440 /* Bounding box on the right/left side? */
441
442 x1 = BBox->Lower_Left[X] - Origin[X];
443 x2 = x1 + BBox->Lengths[X];
444
445 if (((x1 > 0.0) && (x1 > z)) || ((x2 < 0.0) && (-x2 > z)))
446 {
447 return(true);
448 }
449
450 /* Bounding box on the bottom/top side? */
451
452 y1 = BBox->Lower_Left[Y] - Origin[Y];
453 y2 = y1 + BBox->Lengths[Y];
454
455 if (((y1 > 0.0) && (y1 > z)) || ((y2 < 0.0) && (-y2 > z)))
456 {
457 return(true);
458 }
459
460 break;
461
462 case ZaxisM :
463
464 /* Bounding box behind light source? */
465
466 if ((z = BBox->Lower_Left[Z] - Origin[Z]) >= 0.0)
467 {
468 return(true);
469 }
470
471 /* Bounding box on the right/left side? */
472
473 x1 = BBox->Lower_Left[X] - Origin[X];
474 x2 = x1 + BBox->Lengths[X];
475
476 if (((x1 > 0.0) && (x1 > -z)) || ((x2 < 0.0) && (x2 < z)))
477 {
478 return(true);
479 }
480
481 /* Bounding box on the bottom/top side? */
482
483 y1 = BBox->Lower_Left[Y] - Origin[Y];
484 y2 = y1 + BBox->Lengths[Y];
485
486 if (((y1 > 0.0) && (y1 > -z)) || ((y2 < 0.0) && (y2 < z)))
487 {
488 return(true);
489 }
490
491 break;
492
493 default :
494
495 Error("Illegal axis in bbox_invisible() in lbuffer.c.");
496 }
497
498 return(false);
499 }
500
501
502
503 /*****************************************************************************
504 *
505 * FUNCTION
506 *
507 * project_rectangle
508 *
509 * INPUT
510 *
511 * Project - Rectangle's projection
512 * P1, P2, P3, P4 - Rectangle's edges
513 * visible - Flag if rectangle is visible
514 *
515 * OUTPUT
516 *
517 * Project, visible
518 *
519 * RETURNS
520 *
521 * AUTHOR
522 *
523 * Dieter Bayer
524 *
525 * DESCRIPTION
526 *
527 * Project a rectangle onto a light source.
528 *
529 * CHANGES
530 *
531 * May 1994 : Creation.
532 *
533 ******************************************************************************/
534
project_rectangle(PROJECT * Project,VECTOR P1,VECTOR P2,VECTOR P3,VECTOR P4,int * visible)535 static void project_rectangle(PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible)
536 {
537 VECTOR Points[MAX_CLIP_POINTS];
538 int i, number;
539 int x, y;
540
541 Assign_Vector(Points[0], P1);
542 Assign_Vector(Points[1], P2);
543 Assign_Vector(Points[2], P3);
544 Assign_Vector(Points[3], P4);
545
546 number = 4;
547
548 Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
549 VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
550
551 if (number)
552 {
553 for (i = 0; i < number; i++)
554 {
555 if (Points[i][Z] < EPSILON)
556 {
557 Points[i][X] = Points[i][Y] = 0.0;
558 }
559 else
560 {
561 Points[i][X] /= Points[i][Z];
562 Points[i][Y] /= Points[i][Z];
563
564 if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
565 if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
566 }
567
568 x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
569 y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
570
571 if (x < Project->x1) Project->x1 = x;
572 if (x > Project->x2) Project->x2 = x;
573 if (y < Project->y1) Project->y1 = y;
574 if (y > Project->y2) Project->y2 = y;
575 }
576
577 *visible = true;
578 }
579 }
580
581
582
583
584 /*****************************************************************************
585 *
586 * FUNCTION
587 *
588 * project_triangle
589 *
590 * INPUT
591 *
592 * Project - Triangle's projection
593 * P1, P2, P3 - Triangles's edges
594 * visible - Flag if triangle is visible
595 *
596 * OUTPUT
597 *
598 * Project, visible
599 *
600 * RETURNS
601 *
602 * AUTHOR
603 *
604 * Dieter Bayer
605 *
606 * DESCRIPTION
607 *
608 * Project a triangle onto a light source.
609 *
610 * CHANGES
611 *
612 * May 1994 : Creation.
613 *
614 ******************************************************************************/
615
project_triangle(PROJECT * Project,VECTOR P1,VECTOR P2,VECTOR P3,int * visible)616 static void project_triangle(PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible)
617 {
618 VECTOR Points[MAX_CLIP_POINTS];
619 int i, number;
620 int x, y, clip;
621
622 clip = true;
623
624 /* Check if all points lie "in front" of the light source. */
625
626 if ((P1[Z] > 0.0) && (P2[Z] > 0.0) && (P3[Z] > 0.0))
627 {
628 /* Check if all points lie inside the "viewing pyramid". */
629
630 if ((fabs(P1[X]) <= P1[Z]) && (fabs(P2[X]) <= P2[Z]) && (fabs(P3[X]) <= P3[Z]) &&
631 (fabs(P1[Y]) <= P1[Z]) && (fabs(P2[Y]) <= P2[Z]) && (fabs(P3[Y]) <= P3[Z]))
632 {
633 /* No clipping is needed. Just project the points. */
634
635 clip = false;
636 }
637 else
638 {
639 /* Check if all points lie on the "right side". */
640
641 if ((P1[X] > 0.0) && (P1[X] > P1[Z]) &&
642 (P2[X] > 0.0) && (P2[X] > P2[Z]) &&
643 (P3[X] > 0.0) && (P3[X] > P3[Z]))
644 {
645 return;
646 }
647
648 /* Check if all points lie on the "left side". */
649
650 if ((P1[X] < 0.0) && (-P1[X] > P1[Z]) &&
651 (P2[X] < 0.0) && (-P2[X] > P2[Z]) &&
652 (P3[X] < 0.0) && (-P3[X] > P3[Z]))
653 {
654 return;
655 }
656
657 /* Check if all points lie above the "top side". */
658
659 if ((P1[Y] > 0.0) && (P1[Y] > P1[Z]) &&
660 (P2[Y] > 0.0) && (P2[Y] > P2[Z]) &&
661 (P3[Y] > 0.0) && (P3[Y] > P3[Z]))
662 {
663 return;
664 }
665
666 /* Check if all points lie below the "bottom side". */
667
668 if ((P1[Y] < 0.0) && (-P1[Y] > P1[Z]) &&
669 (P2[Y] < 0.0) && (-P2[Y] > P2[Z]) &&
670 (P3[Y] < 0.0) && (-P3[Y] > P3[Z]))
671 {
672 return;
673 }
674 }
675 }
676
677 Assign_Vector(Points[0], P1);
678 Assign_Vector(Points[1], P2);
679 Assign_Vector(Points[2], P3);
680
681 number = 3;
682
683 if (clip)
684 {
685 Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
686 VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
687 }
688
689 if (number)
690 {
691 for (i = 0; i < number; i++)
692 {
693 if (fabs(Points[i][Z]) < EPSILON)
694 {
695 Points[i][X] = Points[i][Y] = 0.0;
696 }
697 else
698 {
699 Points[i][X] /= Points[i][Z];
700 Points[i][Y] /= Points[i][Z];
701
702 if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
703 if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
704 }
705
706 x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
707 y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
708
709 if (x < Project->x1) Project->x1 = x;
710 if (x > Project->x2) Project->x2 = x;
711 if (y < Project->y1) Project->y1 = y;
712 if (y > Project->y2) Project->y2 = y;
713 }
714
715 *visible = true;
716 }
717 }
718
719
720
721
722 /*****************************************************************************
723 *
724 * FUNCTION
725 *
726 * Project_BBox
727 *
728 * INPUT
729 *
730 * Project - Box's projection
731 * P - Box's edges
732 * visible - Flag if box is visible
733 *
734 * OUTPUT
735 *
736 * Project, visible
737 *
738 * RETURNS
739 *
740 * AUTHOR
741 *
742 * Dieter Bayer
743 *
744 * DESCRIPTION
745 *
746 * Project an axis-aligned box onto a light source.
747 *
748 * CHANGES
749 *
750 * May 1994 : Creation.
751 *
752 ******************************************************************************/
753
project_bbox(PROJECT * Project,VECTOR * P,int * visible)754 static void project_bbox(PROJECT *Project, VECTOR *P, int *visible)
755 {
756 int i, x, y;
757
758 /* Check if all points lie "in front" of the light source. */
759
760 if ((P[0][Z] > 0.0) && (P[1][Z] > 0.0) && (P[2][Z] > 0.0) && (P[3][Z] > 0.0) &&
761 (P[4][Z] > 0.0) && (P[5][Z] > 0.0) && (P[6][Z] > 0.0) && (P[7][Z] > 0.0))
762 {
763 /* Check if all points lie inside the "viewing pyramid". */
764
765 if ((fabs(P[0][X]) <= P[0][Z]) && (fabs(P[1][X]) <= P[1][Z]) &&
766 (fabs(P[2][X]) <= P[2][Z]) && (fabs(P[3][X]) <= P[3][Z]) &&
767 (fabs(P[4][X]) <= P[4][Z]) && (fabs(P[5][X]) <= P[5][Z]) &&
768 (fabs(P[6][X]) <= P[6][Z]) && (fabs(P[7][X]) <= P[7][Z]) &&
769 (fabs(P[0][Y]) <= P[0][Z]) && (fabs(P[1][Y]) <= P[1][Z]) &&
770 (fabs(P[2][Y]) <= P[2][Z]) && (fabs(P[3][Y]) <= P[3][Z]) &&
771 (fabs(P[4][Y]) <= P[4][Z]) && (fabs(P[5][Y]) <= P[5][Z]) &&
772 (fabs(P[6][Y]) <= P[6][Z]) && (fabs(P[7][Y]) <= P[7][Z]))
773 {
774 /* No clipping is needed. Just project the points. */
775
776 for (i = 0; i < 8; i++)
777 {
778 if (P[i][Z] < EPSILON)
779 {
780 P[i][X] = P[i][Y] = 0.0;
781 }
782 else
783 {
784 P[i][X] /= P[i][Z];
785 P[i][Y] /= P[i][Z];
786
787 if (fabs(P[i][X]) < EPSILON) P[i][X] = 0.0;
788 if (fabs(P[i][Y]) < EPSILON) P[i][Y] = 0.0;
789 }
790
791 x = (int)(MAX_BUFFER_ENTRY * P[i][X]);
792 y = (int)(MAX_BUFFER_ENTRY * P[i][Y]);
793
794 if (x < Project->x1) Project->x1 = x;
795 if (x > Project->x2) Project->x2 = x;
796 if (y < Project->y1) Project->y1 = y;
797 if (y > Project->y2) Project->y2 = y;
798 }
799
800 *visible = true;
801
802 return;
803 }
804 else
805 {
806 /* Check if all points lie on the "right side". */
807
808 for (i = 0; i < 8; i++)
809 {
810 if ((P[i][X] < 0.0) || (P[i][X] <= P[i][Z])) break;
811 }
812
813 if (i == 8) return;
814
815 /* Check if all points lie on the "left side". */
816
817 for (i = 0; i < 8; i++)
818 {
819 if ((P[i][X] > 0.0) || (-P[i][X] <= P[i][Z])) break;
820 }
821
822 if (i == 8) return;
823
824 /* Check if all points lie above the "top side". */
825
826 for (i = 0; i < 8; i++)
827 {
828 if ((P[i][Y] < 0.0) || (P[i][Y] <= P[i][Z])) break;
829 }
830
831 if (i == 8) return;
832
833 /* Check if all points lie below the "bottom side". */
834
835 for (i = 0; i < 8; i++)
836 {
837 if ((P[i][Y] > 0.0) || (-P[i][Y] <= P[i][Z])) break;
838 }
839
840 if (i == 8) return;
841 }
842 }
843
844 project_rectangle(Project, P[0], P[1], P[3], P[2], visible);
845 project_rectangle(Project, P[4], P[5], P[7], P[6], visible);
846 project_rectangle(Project, P[0], P[1], P[5], P[4], visible);
847 project_rectangle(Project, P[2], P[3], P[7], P[6], visible);
848 project_rectangle(Project, P[1], P[3], P[7], P[5], visible);
849 project_rectangle(Project, P[0], P[2], P[6], P[4], visible);
850 }
851
852
853
854 /*****************************************************************************
855 *
856 * FUNCTION
857 *
858 * project_object
859 *
860 * INPUT
861 *
862 * Object - Object to project
863 * Project - Projection
864 *
865 * OUTPUT
866 *
867 * Project
868 *
869 * RETURNS
870 *
871 * AUTHOR
872 *
873 * Dieter Bayer
874 *
875 * DESCRIPTION
876 *
877 * Get the projection of a single object onto a light source.
878 *
879 * CHANGES
880 *
881 * May 1994 : Creation.
882 *
883 ******************************************************************************/
884
project_object(PROJECT * Project,OBJECT * Object,int Axis,VECTOR Origin,int proj_thru,PROJECT * proj_proj)885 static void project_object(PROJECT *Project, OBJECT *Object, int Axis, VECTOR Origin, int proj_thru, PROJECT *proj_proj)
886 {
887 int visible, Number;
888 VECTOR Points[8];
889
890 /* Do not project infinite objects (always visible!) */
891
892 if (Test_Flag(Object, INFINITE_FLAG))
893 {
894 Project->x1 = Project->y1 = MIN_BUFFER_ENTRY;
895 Project->x2 = Project->y2 = MAX_BUFFER_ENTRY;
896
897 return;
898 }
899
900 /* Get points to project */
901
902 calc_points(Axis, Object, &Number, Points, Origin);
903
904 visible = false;
905
906 Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
907 Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
908
909 if (Number == 3)
910 {
911 project_triangle(Project, Points[0], Points[1], Points[2], &visible);
912 }
913 else
914 {
915 project_bbox(Project, Points, &visible);
916 }
917
918 if ( visible && proj_thru ) {
919 visible = intersect_projects( Project, proj_proj );
920 if ( visible ) {
921 if (Project->x1 < proj_proj->x1 ) Project->x1 = proj_proj->x1;
922 if (Project->x2 > proj_proj->x2 ) Project->x2 = proj_proj->x2;
923 if (Project->y1 < proj_proj->y1 ) Project->y1 = proj_proj->y1;
924 if (Project->y2 > proj_proj->y2 ) Project->y2 = proj_proj->y2;
925 }
926 }
927
928 if (!visible)
929 {
930 /* Object is invisible */
931
932 Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
933 Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
934 }
935 else
936 {
937 /* We don't want to miss something */
938
939 Project->x1 -= 2;
940 Project->x2 += 2;
941 Project->y1 -= 2;
942 Project->y2 += 2;
943 }
944 }
945
946
947
948 /*****************************************************************************
949 *
950 * FUNCTION
951 *
952 * project_bounding_slab
953 *
954 * INPUT
955 *
956 * Axis - Axis along the objects will be projected
957 * Origin - Origin of current light source
958 * Project - Projection
959 * Tree - Current node/leaf
960 * Object - Node/leaf in bounding slab hierarchy
961 *
962 * OUTPUT
963 *
964 * Project, Tree
965 *
966 * RETURNS
967 *
968 * AUTHOR
969 *
970 * Dieter Bayer
971 *
972 * DESCRIPTION
973 *
974 * Project the bounding slab hierarchy onto a light source and thus create
975 * the light buffer hierarchy for this light source.
976 *
977 * CHANGES
978 *
979 * May 1994 : Creation.
980 *
981 ******************************************************************************/
982
project_bounding_slab(int Axis,VECTOR Origin,PROJECT * Project,PROJECT_TREE_NODE ** Tree,BBOX_TREE * Node,int proj_thru,PROJECT * proj_proj)983 static void project_bounding_slab(int Axis, VECTOR Origin, PROJECT *Project, PROJECT_TREE_NODE **Tree, BBOX_TREE *Node, int proj_thru, PROJECT *proj_proj)
984 {
985 short int i;
986 PROJECT Temp;
987 PROJECT_TREE_LEAF *Leaf;
988 PROJECT_TREE_NODE New;
989
990 Do_Cooperate(1);
991
992 /* If the node is totally invisible we are ready. */
993
994 if (bbox_invisible(Axis, &Node->BBox, Origin))
995 {
996 return;
997 }
998
999 if (Node->Entries)
1000 {
1001 /* Current object is a bounding object, i.e. a node in the slab tree. */
1002
1003 /* First, Init new entry. */
1004
1005 New.Entries = 0;
1006
1007 New.Node = Node;
1008
1009 New.Project.x1 = New.Project.y1 = MAX_BUFFER_ENTRY;
1010 New.Project.x2 = New.Project.y2 = MIN_BUFFER_ENTRY;
1011
1012 /* Allocate temporary memory for node/leaf entries. */
1013
1014 New.Entry = (PROJECT_TREE_NODE **)POV_MALLOC(Node->Entries*sizeof(PROJECT_TREE_NODE *), "temporary tree entry");
1015
1016 /* This is no leaf, it's a node. */
1017
1018 New.is_leaf = false;
1019
1020 /* Second, Get new entry, i.e. project bounding slab's entries. */
1021
1022 for (i = 0; i < Node->Entries; i++)
1023 {
1024 New.Entry[i] = NULL;
1025
1026 project_bounding_slab(Axis, Origin, &Temp, &New.Entry[New.Entries], Node->Node[i], proj_thru, proj_proj);
1027
1028 /* Use only visible entries. */
1029
1030 if (New.Entry[New.Entries] != NULL)
1031 {
1032 New.Project.x1 = min(New.Project.x1, Temp.x1);
1033 New.Project.x2 = max(New.Project.x2, Temp.x2);
1034 New.Project.y1 = min(New.Project.y1, Temp.y1);
1035 New.Project.y2 = max(New.Project.y2, Temp.y2);
1036
1037 New.Entries++;
1038 }
1039 }
1040
1041 /* If there are any visible entries, we'll use them. */
1042
1043 if (New.Entries > 0)
1044 {
1045 /* If there's only one entry, we won't need a new node. */
1046
1047 if (New.Entries == 1)
1048 {
1049 *Tree = New.Entry[0];
1050 *Project = New.Project;
1051 }
1052 else
1053 {
1054 /* Allocate memory for new node in the light tree. */
1055
1056 *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_NODE), "light tree node");
1057
1058 **Tree = New;
1059
1060 /* Allocate memory for node/leaf entries. */
1061
1062 (*Tree)->Entry = (PROJECT_TREE_NODE **)POV_MALLOC(New.Entries*sizeof(PROJECT_TREE_NODE *), "light tree node");
1063
1064 POV_MEMCPY((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *));
1065
1066 *Project = New.Project;
1067 }
1068 }
1069
1070 /* Get rid of temporary node/leaf entries. */
1071
1072 POV_FREE(New.Entry);
1073 }
1074 else
1075 {
1076 /* Current object is a normal object, i.e. a leaf in the slab tree. */
1077
1078 /* If object doesn't cast shadows we can skip it. */
1079
1080 if (!Test_Flag((OBJECT *)Node->Node, NO_SHADOW_FLAG))
1081 {
1082 /* Project object onto light source. */
1083
1084 project_object(Project, (OBJECT *)Node->Node, Axis, Origin, proj_thru, proj_proj);
1085
1086 /* Is the object visible? */
1087
1088 if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
1089 {
1090 /* Allocate memory for new leaf in the light tree. */
1091
1092 *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_LEAF), "light tree leaf");
1093
1094 /* Init new leaf. */
1095
1096 Leaf = (PROJECT_TREE_LEAF *)(*Tree);
1097
1098 Leaf->Node = Node;
1099
1100 Leaf->Project = *Project;
1101
1102 /* Yes, this is a leaf. */
1103
1104 Leaf->is_leaf = true;
1105 }
1106 }
1107 }
1108 }
1109
1110
1111
1112 /*****************************************************************************
1113 *
1114 * FUNCTION
1115 *
1116 * Build_Light_Buffers
1117 *
1118 * INPUT
1119 *
1120 * OUTPUT
1121 *
1122 * RETURNS
1123 *
1124 * AUTHOR
1125 *
1126 * Dieter Bayer
1127 *
1128 * DESCRIPTION
1129 *
1130 * Build the light buffers, i.e. the 2d representations of the bounding slab
1131 * hierarchy seen from the light sources.
1132 *
1133 * CHANGES
1134 *
1135 * May 1994 : Creation.
1136 *
1137 ******************************************************************************/
1138
Build_Light_Buffers()1139 void Build_Light_Buffers()
1140 {
1141 int Axis;
1142 PROJECT Project;
1143 LIGHT_SOURCE *Light;
1144 int proj_thru;
1145 PROJECT proj_proj;
1146
1147 if (!(opts.Quality_Flags & Q_SHADOW) || (!opts.Use_Slabs))
1148 {
1149 opts.Options &= ~USE_LIGHT_BUFFER;
1150 }
1151
1152 if (opts.Options & USE_LIGHT_BUFFER)
1153 {
1154 Send_Progress("Creating light buffers", PROGRESS_CREATE_LIGHT_BUFFERS);
1155 /*YS 29 april 2000 bugfix*/
1156 BuffersInit=true;
1157 /*YS 29 april 2000 bugfix*/
1158 /* Build the light buffer for all point(!) light sources */
1159
1160 for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
1161 {
1162 if ((!Light->Area_Light) && (Light->Light_Type!=FILL_LIGHT_SOURCE) &&
1163 !(Light->Parallel))
1164 {
1165 Send_ProgressUpdate(PROGRESS_CREATE_LIGHT_BUFFERS);
1166
1167 /* Project bounding slabs on all six sides */
1168 for (Axis = 0; Axis < 6; Axis++)
1169 {
1170 if ( Light->Projected_Through_Object ) {
1171 proj_thru=1;
1172 project_object (&proj_proj, Light->Projected_Through_Object, Axis, Light->Center, 0, NULL);
1173 }
1174 else {
1175 proj_thru=0;
1176 }
1177 Light->Light_Buffer[Axis] = NULL;
1178 if ( !proj_thru || ((proj_proj.x1 <= proj_proj.x2) && (proj_proj.y1 <= proj_proj.y2))) {
1179 project_bounding_slab(Axis, Light->Center, &Project,
1180 &Light->Light_Buffer[Axis], Root_Object, proj_thru, &proj_proj);
1181 }
1182 }
1183 }
1184 }
1185 }
1186 }
1187
1188
1189
1190 /*****************************************************************************
1191 *
1192 * FUNCTION
1193 *
1194 * Destroy_Light_Buffers
1195 *
1196 * INPUT
1197 *
1198 * OUTPUT
1199 *
1200 * RETURNS
1201 *
1202 * AUTHOR
1203 *
1204 * Dieter Bayer
1205 *
1206 * DESCRIPTION
1207 *
1208 * Destroy the light buffers.
1209 *
1210 * CHANGES
1211 *
1212 * Sep 1994 : Creation.
1213 *
1214 ******************************************************************************/
1215
Destroy_Light_Buffers()1216 void Destroy_Light_Buffers()
1217 {
1218 int Axis;
1219 LIGHT_SOURCE *Light;
1220
1221 /*YS 29 april 2000 bugfix*/
1222 if (opts.Options & USE_LIGHT_BUFFER && BuffersInit==true)
1223 /*YS 29 april 2000 bugfix*/
1224 {
1225 for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
1226 {
1227 if ((!Light->Area_Light) && (Light->Light_Type!=FILL_LIGHT_SOURCE))
1228 {
1229 for (Axis = 0; Axis < 6; Axis++)
1230 {
1231 if (Light->Light_Buffer[Axis] != NULL)
1232 {
1233 Destroy_Project_Tree(Light->Light_Buffer[Axis]);
1234 }
1235
1236 Light->Light_Buffer[Axis] = NULL;
1237 }
1238 }
1239 }
1240 }
1241 /*YS 29 april 2000 bugfix*/
1242 BuffersInit=false;
1243 /*YS 29 april 2000 bugfix*/
1244 }
1245
1246
1247
1248 /*****************************************************************************
1249 *
1250 * FUNCTION
1251 *
1252 * Intersect_Light_Tree
1253 *
1254 * INPUT
1255 *
1256 * Ray - Shadow ray
1257 * Tree - Light tree's top-node
1258 * x - X-coordinate of the shadow ray
1259 * y - Y-coordinate of the shadow ray
1260 * Best_Intersection - Intersection found
1261 * Best_Object - Object found
1262 *
1263 * OUTPUT
1264 *
1265 * Best_Intersection, Best_Object
1266 *
1267 * RETURNS
1268 *
1269 * AUTHOR
1270 *
1271 * Dieter Bayer
1272 *
1273 * DESCRIPTION
1274 *
1275 * Intersect a shadow ray with the light tree
1276 * (same as for the vista tree but without pruning).
1277 *
1278 * CHANGES
1279 *
1280 * May 1994 : Creation.
1281 *
1282 ******************************************************************************/
1283
Intersect_Light_Tree(RAY * Ray,PROJECT_TREE_NODE * Tree,int x,int y,INTERSECTION * Best_Intersection,OBJECT ** Best_Object,LIGHT_SOURCE *)1284 int Intersect_Light_Tree(RAY *Ray, PROJECT_TREE_NODE *Tree, int x, int y, INTERSECTION *Best_Intersection, OBJECT **Best_Object, LIGHT_SOURCE * /*Light_Source*/)
1285 {
1286 INTERSECTION New_Intersection;
1287 unsigned short i;
1288 int Found;
1289 RAYINFO rayinfo;
1290 DBL key;
1291 BBOX_TREE *BBox_Node;
1292 PROJECT_TREE_NODE *Node;
1293
1294 /* If there's no vista tree then return. */
1295
1296 if (Tree == NULL)
1297 {
1298 return(false);
1299 }
1300
1301 /* Start with an empty priority queue */
1302
1303 New_Intersection.Object = NULL;
1304
1305 VLBuffer_Queue->QSize = 0;
1306
1307 Found = false;
1308
1309 #ifdef BBOX_EXTRA_STATS
1310 Increase_Counter(stats[totalQueueResets]);
1311 #endif
1312
1313 /* Traverse the tree. */
1314
1315 Node_Queue->QSize = 0;
1316
1317 /* Create the direction vectors for this ray */
1318
1319 Create_Rayinfo(Ray, &rayinfo);
1320
1321 /* Fill the priority queue with all possible candidates */
1322
1323 /* Check root */
1324
1325 Increase_Counter(stats[LBuffer_Tests]);
1326
1327 if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
1328 (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
1329 {
1330 Increase_Counter(stats[LBuffer_Tests_Succeeded]);
1331
1332 Node_Queue->Queue[(Node_Queue->QSize)++] = Tree;
1333 }
1334
1335 /* Loop until queue is empty. */
1336
1337 while (Node_Queue->QSize > 0)
1338 {
1339 Tree = Node_Queue->Queue[--(Node_Queue->QSize)];
1340
1341 if (Tree->is_leaf)
1342 {
1343 /* Leaf --> test object's bounding box in 3d */
1344
1345 Check_And_Enqueue(VLBuffer_Queue,
1346 ((PROJECT_TREE_LEAF *)Tree)->Node,
1347 &((PROJECT_TREE_LEAF *)Tree)->Node->BBox, &rayinfo);
1348 }
1349 else
1350 {
1351 /* Check siblings of the node in 2d */
1352
1353 for (i = 0; i < Tree->Entries; i++)
1354 {
1355 Node = Tree->Entry[i];
1356
1357 Increase_Counter(stats[LBuffer_Tests]);
1358
1359 if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
1360 (y >= Node->Project.y1) && (y <= Node->Project.y2))
1361 {
1362 Increase_Counter(stats[LBuffer_Tests_Succeeded]);
1363
1364 /* Reallocate queues if they're too small. */
1365
1366 Reinitialize_VLBuffer_Code();
1367
1368 /* Add node to node queue */
1369
1370 Node_Queue->Queue[(Node_Queue->QSize)++] = Node;
1371 }
1372 }
1373 }
1374 }
1375
1376 /* Now test the candidates in the priority queue */
1377
1378 while (VLBuffer_Queue->QSize > 0)
1379 {
1380 Priority_Queue_Delete(VLBuffer_Queue, &key, &BBox_Node);
1381
1382 if (key > Best_Intersection->Depth)
1383 {
1384 break;
1385 }
1386
1387 if (Intersection(&New_Intersection, (OBJECT *)BBox_Node->Node, Ray))
1388 {
1389 if (New_Intersection.Depth < Best_Intersection->Depth &&
1390 /* NK Feb 6, 2000 - bugfix */
1391 New_Intersection.Depth > Small_Tolerance)
1392 {
1393 *Best_Intersection = New_Intersection;
1394
1395 *Best_Object = (OBJECT *)BBox_Node->Node;
1396
1397 Found = true;
1398 }
1399 }
1400 }
1401
1402 return(Found);
1403 }
1404
1405 END_POV_NAMESPACE
1406