/**************************************************************************** * * ATTENTION!!! * * THIS FILE HAS BEEN MODIFIED!!! IT IS NOT PART OF THE OFFICAL * POV-RAY 2.2 DISTRIBUTION!!! * * THIS FILE IS PART OF "FASTER THAN POV-RAY" (VERSION 2.2), * A SPED-UP VERSION OF POV-RAY 2.2. USE AT YOUR OWN RISK!!!!!! * * New files: addon0.c, addon1.c, addon2.c, addon3.c, addon.h * * The additional modules were written by Dieter Bayer. * * Send comments, suggestions, bugs, ideas ... to: * * e-mail: dieter@cip.e-technik.uni-erlangen.de * CIS: 100255.3074 * * All changed/added lines are enclosed in #ifdef DB_CODE ... #endif * * The vista projection was taken from: * * A. Hashimoto, T. Akimoto, K. Mase, and Y. Suenaga, * "Vista Ray-Tracing: High Speed Ray Tracing Using Perspective * Projection Image", New Advances in Computer Graphics, Proceedings * of CG International '89, R. A. Earnshaw, B. Wyvill (Eds.), * Springer, ..., pp. 549-560 * * The idea for the light buffer was taken from: * * E. Haines and D. Greenberg, "The Light Buffer: A Shadow-Testing * Accelerator", IEEE CG&A, Vol. 6, No. 9, Sept. 1986, pp. 6-16 * *****************************************************************************/ /**************************************************************************** * addon2.c * * This module was written by Dieter Bayer. * * This module contains functions used only for the light buffer. * * 01.03.1994 : Creation * * 29.04.1994 : Creation * ******************************************************************************/ #include "frame.h" #include "vector.h" #include "povproto.h" #include "addon.h" #ifdef DB_CODE /***************************************************************************** * External variables ******************************************************************************/ extern FRAME Frame; extern unsigned long Quality_Flags; extern unsigned int Options, Extended_Options; extern METHODS Bicubic_Patch_Methods; extern METHODS Blob_Methods; extern METHODS Box_Methods; extern METHODS Cone_Methods; extern METHODS Csg_Height_Field_Methods; extern METHODS CSG_Intersection_Methods; extern METHODS CSG_Merge_Methods; extern METHODS CSG_Union_Methods; extern METHODS Disc_Methods; extern METHODS Ellipsoid_Methods; extern METHODS Height_Field_Methods; extern METHODS Light_Source_Methods; extern METHODS Plane_Methods; extern METHODS Poly_Methods; extern METHODS Quadric_Methods; extern METHODS Smooth_Triangle_Methods; extern METHODS Sphere_Methods; extern METHODS Triangle_Methods; extern OBJECT *Root_Object; extern size_t Mem_Light_Buffers; /***************************************************************************** * static variabls ******************************************************************************/ static VECTOR VIEW_VX1 = {-0.7071067812, 0.0, -0.7071067812}; static VECTOR VIEW_VX2 = { 0.7071067812, 0.0, -0.7071067812}; static VECTOR VIEW_VY1 = {0.0, -0.7071067812, -0.7071067812}; static VECTOR VIEW_VY2 = {0.0, 0.7071067812, -0.7071067812}; static DBL VIEW_DX1 = 0.0; static DBL VIEW_DX2 = 0.0; static DBL VIEW_DY1 = 0.0; static DBL VIEW_DY2 = 0.0; /***************************************************************************** * static functions ******************************************************************************/ static void Calc_Points PARAMS((int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR *Origin)); static int BBox_Invisible PARAMS((int Axis, BBOX *Bounds, VECTOR *Origin)); static void Project_rectangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible)); static void Project_triangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible)); static void Project_Bbox PARAMS((PROJECT *Project, VECTOR *Points, int *visible)); static void Project_Object PARAMS((PROJECT *Project, OBJECT *Object, int Axis, VECTOR *Origin)); static void Project_Bounding_Slab PARAMS((int Axis, VECTOR *Origin, PROJECT *Project, PROJECT_TREE_NODE **Entry, OBJECT *Object)); /***************************************************************************** * * FUNCTION : Calc_Points * * ARGUMENTS : Axis - Axis along the objects will be projected * Object - Object * Number - Number of points to project * Points - Points to project * Origin - Origin of current light source * * MODIFIED ARGS : Number, Points * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Calculate the points to project depending on the object type, * the light source position and the axis. * * CHANGES * * - * ******************************************************************************/ static void Calc_Points(Axis, Object, Number, Points, Origin) int Axis; OBJECT *Object; int *Number; VECTOR *Points, *Origin; { register int i; DBL Direction; VECTOR P[8]; /* Get points depending on object's type */ if ((Object->Methods == &Triangle_Methods) || (Object->Methods == &Smooth_Triangle_Methods)) { if (Object->Methods == &Triangle_Methods) { *Number = 3; P[0] = ((TRIANGLE *)Object)->P1; P[1] = ((TRIANGLE *)Object)->P2; P[2] = ((TRIANGLE *)Object)->P3; } if (Object->Methods == &Smooth_Triangle_Methods) { *Number = 3; P[0] = ((SMOOTH_TRIANGLE *)Object)->P1; P[1] = ((SMOOTH_TRIANGLE *)Object)->P2; P[2] = ((SMOOTH_TRIANGLE *)Object)->P3; } } else { *Number = 8; for (i = 0; i < *Number; i++) { P[i] = Object->Bounds.Lower_Left; P[i].x += ((i & 1) ? Object->Bounds.Lengths.x : 0.0); P[i].y += ((i & 2) ? Object->Bounds.Lengths.y : 0.0); P[i].z += ((i & 4) ? Object->Bounds.Lengths.z : 0.0); } } /* The points' coordinates need to be relative to the light source */ for (i = 0; i < *Number; i++) { P[i].x -= Origin->x; P[i].y -= Origin->y; P[i].z -= Origin->z; } /* Switch axes so that the specified axis becomes the +Z-axis */ if ((Axis == XaxisP) || (Axis == YaxisP) || (Axis == ZaxisP)) { Direction = +1.0; } else { Direction = -1.0; } /* Modify points so that the new z direction is the projection axis */ switch (Axis) { case XaxisP : case XaxisM : for (i = 0; i < *Number; i++) { Points[i].x = P[i].y; Points[i].y = P[i].z; Points[i].z = P[i].x * Direction; } break; case YaxisP : case YaxisM : for (i = 0; i < *Number; i++) { Points[i].x = P[i].x; Points[i].y = P[i].z; Points[i].z = P[i].y * Direction; } break; case ZaxisP : case ZaxisM : for (i = 0; i < *Number; i++) { Points[i].x = P[i].x; Points[i].y = P[i].y; Points[i].z = P[i].z * Direction; } break; default : Fatal_Error("Illegal axis in module addon2.\n"); } } /***************************************************************************** * * FUNCTION : BBox_Invisible * * ARGUMENTS : Axis - Axis along the objects will be projected * Bounds - Bounding box to test * Origin - Origin of current light source * * MODIFIED ARGS : none * * RETURN VALUE : int - Flag if bounding box is totally invisble * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Do a quick test if a bounding box is totally invisble from the * current light source in the specified axis direction. * * CHANGES * * - * ******************************************************************************/ static int BBox_Invisible(Axis, Bounds, Origin) int Axis; BBOX *Bounds; VECTOR *Origin; { switch (Axis) { case XaxisP : if (Bounds->Lower_Left.x + Bounds->Lengths.x < Origin->x) return(TRUE); break; case XaxisM : if (Bounds->Lower_Left.x > Origin->x) return(TRUE); break; case YaxisP : if (Bounds->Lower_Left.y + Bounds->Lengths.y < Origin->y) return(TRUE); break; case YaxisM : if (Bounds->Lower_Left.y > Origin->y) return(TRUE); break; case ZaxisP : if (Bounds->Lower_Left.z + Bounds->Lengths.z < Origin->z) return(TRUE); break; case ZaxisM : if (Bounds->Lower_Left.z > Origin->z) return(TRUE); break; default : Fatal_Error("Illegal axis in module addon2.\n"); } return(FALSE); } /***************************************************************************** * * FUNCTION : Project_rectangle * * ARGUMENTS : Project - Rectangle's projection * P1, P2, P3, P4 - Rectangle's edges * visible - Flag if rectangle is visible * * MODIFIED ARGS : Project, visible * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Project a rectangle onto a light source. * * CHANGES * * - * ******************************************************************************/ static void Project_rectangle(Project, P1, P2, P3, P4, visible) PROJECT *Project; VECTOR P1, P2, P3, P4; int *visible; { VECTOR Points[MAX_CLIP_POINTS]; int i, number; int x, y; /* Square totally invisible? */ if ((P1.z <= 0.0) && (P2.z <= 0.0) && (P3.z <= 0.0) && (P4.z <= 0.0)) return; Points[0] = P1; Points[1] = P2; Points[2] = P3; Points[3] = P4; number = 4; /* Clip square only if some quick tests say it's necessary. Assuming that only a few squares need clipping this saves some time. (I don't need to write fabs(P?.z) since the tests succeed anyway if P?.z < 0. Hope the compiler doesn't change the tests' order!) */ if ((P1.z < 0.0) || (P2.z < 0.0) || (P3.z < 0.0) || (P4.z < 0.0) || (fabs(P1.x) > (P1.z)) || (fabs(P1.y) > (P1.z)) || (fabs(P2.x) > (P2.z)) || (fabs(P2.y) > (P2.z)) || (fabs(P3.x) > (P3.z)) || (fabs(P3.y) > (P3.z)) || (fabs(P4.x) > (P4.z)) || (fabs(P4.y) > (P4.z))) { Clip_Polygon(Points, &number, &VIEW_VX1, &VIEW_VX2, &VIEW_VY1, &VIEW_VY2, VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2); } if (!number) return; for (i = 0; i < number; i++) { if (Points[i].z < EPSILON) { Points[i].x = Points[i].y = 0.0; } else { Points[i].x = Points[i].x / Points[i].z; Points[i].y = Points[i].y / Points[i].z; if (fabs(Points[i].x) < EPSILON) Points[i].x = 0.0; if (fabs(Points[i].y) < EPSILON) Points[i].y = 0.0; } x = (int)(MAX_LB_ENTRY * Points[i].x); y = (int)(MAX_LB_ENTRY * Points[i].y); if (x < Project->x1) Project->x1 = x; if (x > Project->x2) Project->x2 = x; if (y < Project->y1) Project->y1 = y; if (y > Project->y2) Project->y2 = y; } *visible = TRUE; } /***************************************************************************** * * FUNCTION : Project_triangle * * ARGUMENTS : Project - Triangle's projection * P1, P2, P3 - Triangles's edges * visible - Flag if triangle is visible * * MODIFIED ARGS : Project, visible * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Project a triangle onto a light source. * * CHANGES * * - * ******************************************************************************/ static void Project_triangle(Project, P1, P2, P3, visible) PROJECT *Project; VECTOR P1, P2, P3; int *visible; { VECTOR Points[MAX_CLIP_POINTS]; int i, number; int x, y; /* Triangle totally invisible? */ if ((P1.z <= 0.0) && (P2.z <= 0.0) && (P3.z <= 0.0)) return; Points[0] = P1; Points[1] = P2; Points[2] = P3; number = 3; /* Clip triangle only if some quick tests say it's necessary. Assuming that only a few triangles need clipping this saves some time. (I don't need to write fabs(P?.z) since the tests succeed anyway if P?.z < 0. Hope the compiler doesn't change the tests' order!) */ if ((P1.z < 0.0) || (P2.z < 0.0) || (P3.z < 0.0) || (fabs(P1.x) > (P1.z)) || (fabs(P1.y) > (P1.z)) || (fabs(P2.x) > (P2.z)) || (fabs(P2.y) > (P2.z)) || (fabs(P3.x) > (P3.z)) || (fabs(P3.y) > (P3.z))) { Clip_Polygon(Points, &number, &VIEW_VX1, &VIEW_VX2, &VIEW_VY1, &VIEW_VY2, VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2); } if (!number) return; for (i = 0; i < number; i++) { if (fabs(Points[i].z) < EPSILON) { Points[i].x = Points[i].y = 0.0; } else { Points[i].x = Points[i].x / Points[i].z; Points[i].y = Points[i].y / Points[i].z; if (fabs(Points[i].x) < EPSILON) Points[i].x = 0.0; if (fabs(Points[i].y) < EPSILON) Points[i].y = 0.0; } x = (int)(MAX_LB_ENTRY * Points[i].x); y = (int)(MAX_LB_ENTRY * Points[i].y); if (x < Project->x1) Project->x1 = x; if (x > Project->x2) Project->x2 = x; if (y < Project->y1) Project->y1 = y; if (y > Project->y2) Project->y2 = y; } *visible = TRUE; } /***************************************************************************** * * FUNCTION : Project_BBox * * ARGUMENTS : Project - Box's projection * Points - Box's edges * visible - Flag if box is visible * * MODIFIED ARGS : Project, visible * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Project a box onto a light source. * * CHANGES * * - * ******************************************************************************/ static void Project_Bbox(Project, Points, visible) PROJECT *Project; VECTOR *Points; int *visible; { Project_rectangle(Project, Points[0], Points[1], Points[3], Points[2], visible); Project_rectangle(Project, Points[4], Points[5], Points[7], Points[6], visible); Project_rectangle(Project, Points[0], Points[1], Points[5], Points[4], visible); Project_rectangle(Project, Points[2], Points[3], Points[7], Points[6], visible); Project_rectangle(Project, Points[1], Points[3], Points[7], Points[5], visible); Project_rectangle(Project, Points[0], Points[2], Points[6], Points[4], visible); } /***************************************************************************** * * FUNCTION : Project_Object * * ARGUMENTS : Object - Object to project * Project - Projection * * MODIFIED ARGS : Project * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Get the projection of a single object onto a light source. * * CHANGES * * - * ******************************************************************************/ static void Project_Object(Project, Object, Axis, Origin) PROJECT *Project; OBJECT *Object; int Axis; VECTOR *Origin; { int visible, Number; DBL Volume; VECTOR Points[8]; /* Do not project infinite objects (always visible!) */ BOUNDS_VOLUME(Volume, Object->Bounds); if (Volume > INFINITE_VOLUME) { Project->x1 = Project->y1 = MIN_LB_ENTRY; Project->x2 = Project->y2 = MAX_LB_ENTRY; return; } /* Get points to project */ Calc_Points(Axis, Object, &Number, &Points[0], Origin); visible = FALSE; Project->x1 = Project->y1 = MAX_LB_ENTRY; Project->x2 = Project->y2 = MIN_LB_ENTRY; if (Number == 3) { Project_triangle(Project, Points[0], Points[1], Points[2], &visible); } else { Project_Bbox(Project, &Points[0], &visible); } if (!visible) { /* Object is invisible */ Project->x1 = Project->y1 = MAX_LB_ENTRY; Project->x2 = Project->y2 = MIN_LB_ENTRY; } else { /* We don't want to miss something */ Project->x1--; Project->x2++; Project->y1--; Project->y2++; } Print_Point(6 * POINT_MOD); } /***************************************************************************** * * FUNCTION : Project_Bounding_Slab * * ARGUMENTS : Axis - Axis along the objects will be projected * Origin - Origin of current light source * Project - Projection * Tree - Current node/leaf * Object - Node/leaf in bounding slab hierarchy * * MODIFIED ARGS : Project, Tree * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Project the bounding slab hierarchy onto a light source and thus create * the light buffer hierarchy for this light source. * * CHANGES * * - * ******************************************************************************/ static void Project_Bounding_Slab(Axis, Origin, Project, Tree, Object) int Axis; VECTOR *Origin; PROJECT *Project; PROJECT_TREE_NODE **Tree; OBJECT *Object; { unsigned short int i; COMPOSITE *Comp; PROJECT Temp; PROJECT_TREE_LEAF *Leaf; PROJECT_TREE_NODE New; /* If the node is totally invisible we are ready */ if (BBox_Invisible(Axis, &Object->Bounds, Origin)) { return; } if (Object->Type & BOUNDING_OBJECT) { /* Current object is a bounding object, i.e. a node in the slab tree */ Comp = (COMPOSITE *)Object; /* Init new entry */ New.Entries = 0; New.Object = Object; New.Project.x1 = New.Project.y1 = MAX_VB_ENTRY; New.Project.x2 = New.Project.y2 = MIN_VB_ENTRY; /* Allocate temporary memory for node/leaf entries. */ if ((New.Entry = (PROJECT_TREE_NODE **)malloc(Comp->Entries*sizeof(PROJECT_TREE_NODE *))) == NULL) { Fatal_Error("temporary tree entry"); } /* This is no leaf */ New.is_leaf = FALSE; /* Get new entry, i.e. project bounding slab's entries */ for (i = 0; i < Comp->Entries; i++) { New.Entry[i] = NULL; Project_Bounding_Slab(Axis, Origin, &Temp, &New.Entry[New.Entries], Comp->Objects[i]); /* Use only visible entries */ if (New.Entry[New.Entries] != NULL) { New.Project.x1 = min(New.Project.x1, Temp.x1); New.Project.x2 = max(New.Project.x2, Temp.x2); New.Project.y1 = min(New.Project.y1, Temp.y1); New.Project.y2 = max(New.Project.y2, Temp.y2); New.Entries++; } } /* If there are any visible entries, we'll use them. */ if (New.Entries > 0) { /* If there's only one entry, we won't need a new node. */ if (New.Entries == 1) { *Tree = New.Entry[0]; *Project = New.Project; } else { /* Allocate memory for new node in the light tree (never freed!) */ *Tree = (PROJECT_TREE_NODE *)LB_malloc(sizeof(PROJECT_TREE_NODE)); if (*Tree == NULL) { Fatal_MAError("light tree node"); } **Tree = New; /* Allocate memory for node/leaf entries. */ (*Tree)->Entry = (PROJECT_TREE_NODE **)VB_malloc(New.Entries*sizeof(PROJECT_TREE_NODE *)); if ((*Tree)->Entry == NULL) { Fatal_MAError("vista tree node"); } memcpy((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *)); *Project = New.Project; } } } else { /* Current object is a normal object, i.e. a leaf in the slab tree */ /* Project object onto light source */ Project_Object(Project, Object, Axis, Origin); /* Is the object visible? */ if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2)) { /* Allocate memory for new leaf in the light tree (never freed!) */ *Tree = (PROJECT_TREE_NODE *)LB_malloc(sizeof(PROJECT_TREE_LEAF)); if (*Tree == NULL) { Fatal_MAError("light tree leaf"); } /* Init new leaf */ Leaf = (PROJECT_TREE_LEAF *)(*Tree); Leaf->Object = Object; Leaf->Project = *Project; /* Yes, this is a leaf */ Leaf->is_leaf = TRUE; } } } /***************************************************************************** * * FUNCTION : Build_Light_Buffers * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May 1994 * * DESCRIPTION * * Build the light buffers, i.e. the 2d representations of the bounding slab * hierarchy seen from the light sources. * * CHANGES * * - * ******************************************************************************/ void Build_Light_Buffers() { int i = 0, Axis; PROJECT Project; LIGHT_SOURCE *Light; /* Shadows aren't calculated --> return */ if (!(Quality_Flags & Q_SHADOW)) return; /* We don't want a light buffer --> return */ if (!(Extended_Options & USE_LIGHT_BUFFER)) return; /* Build the light buffer for all point(!) light sources */ for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source) { if (!Light->Area_Light) { fprintf(stderr, "Building light buffer %d", ++i); Begin_Point(); /* Project bounding slabs on all six sides */ for (Axis = 0; Axis < 6; Axis++) { Light->Light_Buffer[Axis] = NULL; Project_Bounding_Slab(Axis, &Light->Center, &Project, &Light->Light_Buffer[Axis], Root_Object); } End_Point(); } } } #endif