/**************************************************************************** * * 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 * *****************************************************************************/ /***************************************************************************** * addon0.c * * This module was written by Dieter Bayer. * * This module contains functions for initialisation, statistics, previewing, * and other gegeneral purposes. * * 01.03.1994 : Creation * * 29.04.1994 : Version 2.0 * ******************************************************************************/ #include #include "frame.h" #include "vector.h" #include "povproto.h" #include "addon.h" #ifdef DB_CODE #define RED 0 #define GREEN 1 #define BLUE 2 #define NUMBER_OF_TYPES 19 #define TYPE_BICUBIC_PATCH 0 #define TYPE_BLOB 1 #define TYPE_BOX 2 #define TYPE_CONE 3 #define TYPE_CSG_INTERSECTION 4 #define TYPE_CSG_MERGE 5 #define TYPE_CSG_UNION 6 #define TYPE_DISC 7 #define TYPE_ELLIPSOID 8 #define TYPE_HEIGHT_FIELD 9 #define TYPE_LIGHT_SOURCE 10 #define TYPE_PLANE 11 #define TYPE_POLY 12 #define TYPE_POLYGON 13 #define TYPE_QUADRIC 14 #define TYPE_SMOOTH_TRIANGLE 15 #define TYPE_SPHERE 16 #define TYPE_TRIANGLE 17 #define TYPE_UNKNOWN 18 #define NUMBER_OF_FLAGS 7 #define FLAG_SUM 0 #define FLAG_INFINITE 1 #define FLAG_USED_IN_CSG 2 #define FLAG_BOUNDED 3 #define FLAG_CLIPPED 4 #define FLAG_BOUND_OBJECT 5 #define FLAG_CLIP_OBJECT 6 /***************************************************************************** * External variables ******************************************************************************/ extern FRAME Frame; extern unsigned int Options; extern METHODS Ellipsoid_Methods; extern METHODS Sphere_Methods; extern time_t tstart, tstop; extern int Use_Slabs; extern unsigned long Quality_Flags; 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 PROJECT_TREE_NODE *Root_Vista; extern size_t Mem_Polygon; /***************************************************************************** * Global variables ******************************************************************************/ unsigned int Extended_Options = 0; /* Amount of memory occupied by the vista buffer and light buffers */ size_t Mem_Vista_Buffer = 0; size_t Mem_Light_Buffers = 0; size_t Allocated_Memory = 0; /***************************************************************************** * Static variables ******************************************************************************/ static int Point_Counter; static DBL time_used1, time_used2; static long counter[NUMBER_OF_TYPES][NUMBER_OF_FLAGS]; /***************************************************************************** * Static functions ******************************************************************************/ static int Get_Object_Type PARAMS((OBJECT *Object)); static void Print_Object_Info PARAMS((int type)); static void Get_Object_Stats PARAMS((OBJECT *Object, int Csg, int Bound_Object, int Clip_Object)); static void Print_Object_Stats PARAMS((void)); static void Draw_Projection PARAMS((PROJECT *Project, int color)); static void Draw_Vista PARAMS((PROJECT_TREE_NODE *Tree)); /***************************************************************************** * * FUNCTION : VB_malloc * * ARGUMENTS : size - Amount of memory to allocate * * MODIFIED ARGS : none * * RETURN VALUE : void * - Pointer at allocated memory * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Allocate memory for the vista buffer and keep track of the memory allocated. * * CHANGES * * - * ******************************************************************************/ void *VB_malloc(size) size_t size; { Allocated_Memory += size; Mem_Vista_Buffer += size; return(malloc(size)); } /***************************************************************************** * * FUNCTION : LB_malloc * * ARGUMENTS : size - Amount of memory to allocate * * MODIFIED ARGS : none * * RETURN VALUE : void * - Pointer at allocated memory * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Allocate memory for the light buffer and keep track of the memory allocated. * * CHANGES * * - * ******************************************************************************/ void *LB_malloc(size) size_t size; { Allocated_Memory += size; Mem_Light_Buffers += size; return(malloc(size)); } /***************************************************************************** * * FUNCTION : new_malloc * * ARGUMENTS : size - Amount of memory to allocate * * MODIFIED ARGS : none * * RETURN VALUE : void * - Pointer at allocated memory * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Allocate memory and keep track of the memory allocated. * * Use instead of malloc when allocating memory! * * CHANGES * * - * ******************************************************************************/ void *new_malloc(size) size_t size; { Allocated_Memory += size; return(malloc(size)); } /***************************************************************************** * * FUNCTION : new_free * * ARGUMENTS : pointer - Memory to free * size - Amount of memory that will be freed * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Free memory and keep track of the memory allocated. * * Use instead of free when freeing memory! * * CHANGES * * - * ******************************************************************************/ void new_free(pointer, size) void *pointer; size_t size; { Allocated_Memory -= size; free(pointer); } /***************************************************************************** * * FUNCTION : Init_Additional_1 * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Additional initialisation before boundind slabs are build. * * Split union objects and pass bounding objects to the children if they * aren't already bounded (most bounding objects will be removed later). * * CHANGES * * - * ******************************************************************************/ void Init_Additionals_1() { int children_finite; long count; DBL Volume; OBJECT **Object, *Sib, *Last_Sib, *Bound; Print_Quadric_Stats(); if ((Extended_Options & USE_SPLIT_FINITE_UNIONS) || (Extended_Options & USE_SPLIT_INFINITE_UNIONS)) { START_TIME Recompute_Bboxes(); fprintf(stderr, "Splitting union objects"); Begin_Point(); count = 0; for (Object = &Frame.Objects; (*Object) != NULL; ) { children_finite = FALSE; if (Extended_Options & USE_SPLIT_INFINITE_UNIONS) { /* +usi option is used, i.e. split all unions */ children_finite = TRUE; } else { /* Check, if all children of the union have finite bounding boxes */ if ((*Object)->Methods == &CSG_Union_Methods) { children_finite = TRUE; for (Sib = ((CSG *)(*Object))->Children; Sib != NULL; Sib = Sib->Sibling) { BOUNDS_VOLUME(Volume, Sib->Bounds); if (Volume > INFINITE_VOLUME) children_finite = FALSE; } } } /* Split union object, if all children are finite (or tracing slows down!) and the union isn't clipped */ if (((*Object)->Methods == &CSG_Union_Methods) && ((*Object)->Clip == NULL) && (children_finite)) { count++; Print_Point(POINT_MOD); Bound = (*Object)->Bound; if ((Sib = ((CSG *)(*Object))->Children) != NULL) { for (; Sib != NULL; Sib = Sib->Sibling) { /* Set child's bound to father's bound (some peolpe use objects that don't fit in the bounding object. Argh!!! The question is: should this be done or not?) */ if (Sib->Bound == NULL) Sib->Bound = Bound; Last_Sib = Sib; } Last_Sib->Sibling = (*Object)->Sibling; (*Object) = ((CSG *)(*Object))->Children; } else { (*Object) = (*Object)->Sibling; } } else { Object = &(*Object)->Sibling; } } fprintf(stderr, "(%ld split)", count); End_Point(); if (count > 0) { /* Just to be sure */ Recompute_Bboxes(); } STOP_TIME time_used1 = TIME_ELAPSED } else { Recompute_Bboxes(); } } /***************************************************************************** * * FUNCTION : Init_Additionals_2 * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Additional initialisation after boundind slabs have been build. * * - Project objects onto the screen. * - Build the light buffers. * - Remove all unnecessary bounding objects. * - Print a statistic of the scene. * * CHANGES * * - * ******************************************************************************/ void Init_Additionals_2() { DBL time_used; /* If slabs are not used --> vista and light buffer can't be used */ if (!Use_Slabs) { Extended_Options &= ~USE_VISTA_BUFFER; Extended_Options &= ~USE_LIGHT_BUFFER; } /* We don't use shadows so we don't need a light buffer */ if (!(Quality_Flags & Q_SHADOW)) { Extended_Options &= ~USE_LIGHT_BUFFER; } if ((Extended_Options & USE_VISTA_BUFFER) || (Extended_Options & USE_LIGHT_BUFFER)) { START_TIME if (Use_Slabs) { Init_Project_Tree_Queues(); if (Extended_Options & USE_VISTA_BUFFER) { Init_View_Coordinates(); Build_Vista_Tree(); } if (Extended_Options & USE_LIGHT_BUFFER) { Build_Light_Buffers(); } } Remove_Unnecessary_Bounds(); Print_Object_Stats(); STOP_TIME time_used2 = TIME_ELAPSED time_used = time_used1 + time_used2; fprintf(stderr, "Preprocessing time: %.0f seconds\n", time_used); } else { Remove_Unnecessary_Bounds(); } } /***************************************************************************** * * FUNCTION : Get_Object_Type * * ARGUMENTS : Object - Point to an object * * MODIFIED ARGS : none * * RETURN VALUE : int - Type of object * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Returns the type of an object. * * CHANGES * * - * ******************************************************************************/ static int Get_Object_Type(Object) OBJECT *Object; { if (Object->Methods == &Bicubic_Patch_Methods) return(TYPE_BICUBIC_PATCH); if (Object->Methods == &Blob_Methods) return(TYPE_BLOB); if (Object->Methods == &Box_Methods) return(TYPE_BOX); if (Object->Methods == &Cone_Methods) return(TYPE_CONE); if (Object->Methods == &CSG_Intersection_Methods) return(TYPE_CSG_INTERSECTION); if (Object->Methods == &CSG_Merge_Methods) return(TYPE_CSG_MERGE); if (Object->Methods == &CSG_Union_Methods) return(TYPE_CSG_UNION); if (Object->Methods == &Disc_Methods) return(TYPE_DISC); if (Object->Methods == &Ellipsoid_Methods) return(TYPE_ELLIPSOID); if (Object->Methods == &Height_Field_Methods) return(TYPE_HEIGHT_FIELD); if (Object->Methods == &Csg_Height_Field_Methods) return(TYPE_HEIGHT_FIELD); if (Object->Methods == &Light_Source_Methods) return(TYPE_LIGHT_SOURCE); if (Object->Methods == &Plane_Methods) return(TYPE_PLANE); if (Object->Methods == &Poly_Methods) return(TYPE_POLY); if (Object->Methods == &Quadric_Methods) return(TYPE_QUADRIC); if (Object->Methods == &Smooth_Triangle_Methods) return(TYPE_SMOOTH_TRIANGLE); if (Object->Methods == &Sphere_Methods) return(TYPE_SPHERE); if (Object->Methods == &Triangle_Methods) return(TYPE_TRIANGLE); return(TYPE_UNKNOWN); } /***************************************************************************** * * FUNCTION : Get_Object_Stats * * ARGUMENTS : Object - object * csg - Flag if inside a csg object * bound_object - Flag if object is part of a bounding object * clip_object - Flag if object is part of a clipping object * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Get some information about an object and add it to the scene statistic. * * CHANGES * * - * ******************************************************************************/ static void Get_Object_Stats(Object, csg, bound_object, clip_object) OBJECT *Object; int csg, bound_object, clip_object; { int bounded, clipped, infinite, type; DBL Volume; OBJECT *Sib; if (Object == NULL) return; /* Bounded/Clipped object? */ bounded = (Object->Bound != NULL); clipped = (Object->Clip != NULL); /* Don't care about infinite objects if they are inside a CSG object or used as clipping/bounding objects */ if (csg || bound_object || clip_object) { infinite = FALSE; } else { /* Infinte object? */ BOUNDS_VOLUME(Volume, Object->Bounds); infinite = (Volume > INFINITE_VOLUME); } /* Get object type */ type = Get_Object_Type(Object); /* Count bounding objects */ if (Object->Bound != NULL) { for (Sib = Object->Bound; Sib != NULL; Sib = Sib->Sibling) { Get_Object_Stats(Sib, csg, TRUE, clip_object); } } /* Count clipping objects */ if (Object->Clip != NULL) { for (Sib = Object->Clip; Sib != NULL; Sib = Sib->Sibling) { Get_Object_Stats(Sib, csg, bound_object, TRUE); } } if (Object->Type & COMPOUND_OBJECT) { if (Object->Type & LIGHT_SOURCE_OBJECT) { /* Count light source */ counter[type][FLAG_SUM]++; Get_Object_Stats(((LIGHT_SOURCE *)Object)->Children, csg, bound_object, clip_object); } else { /* Count CSG object */ counter[type][FLAG_SUM]++; if (csg) counter[type][FLAG_USED_IN_CSG]++; if (infinite) counter[type][FLAG_INFINITE]++; if (bounded) counter[type][FLAG_BOUNDED]++; if (clipped) counter[type][FLAG_CLIPPED]++; if (bound_object) counter[type][FLAG_BOUND_OBJECT]++; if (clip_object) counter[type][FLAG_CLIP_OBJECT]++; for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling) { Get_Object_Stats(Sib, TRUE, bound_object, clip_object); } } } else { /* Count the primitive object */ counter[type][FLAG_SUM]++; if (csg) counter[type][FLAG_USED_IN_CSG]++; if (infinite) counter[type][FLAG_INFINITE]++; if (bounded) counter[type][FLAG_BOUNDED]++; if (clipped) counter[type][FLAG_CLIPPED]++; if (bound_object) counter[type][FLAG_BOUND_OBJECT]++; if (clip_object) counter[type][FLAG_CLIP_OBJECT]++; } } /***************************************************************************** * * FUNCTION : Print_Object_Info * * ARGUMENTS : type - Object's type * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Print the statistics of one type of object. * * CHANGES * * - * ******************************************************************************/ static void Print_Object_Info(type) int type; { fprintf(stderr, " : %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n", counter[type][FLAG_SUM], counter[type][FLAG_USED_IN_CSG], counter[type][FLAG_INFINITE], counter[type][FLAG_BOUND_OBJECT], counter[type][FLAG_CLIP_OBJECT], counter[type][FLAG_BOUNDED], counter[type][FLAG_CLIPPED]); } /***************************************************************************** * * FUNCTION : Print_Object_Stats * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Collect and print a statistic about the scene. * * CHANGES * * - * ******************************************************************************/ static void Print_Object_Stats() { int i, j; long sum1, sum2, sum3, sum4, sum5, sum6, sum7, frame_level; OBJECT *Sib; /* Initialize counters */ for (i = 0; i < NUMBER_OF_TYPES; i++) { for (j = 0; j < NUMBER_OF_FLAGS; j++) { counter[i][j] = 0; } } frame_level = 0; for (Sib = Frame.Objects; Sib != NULL; Sib = Sib->Sibling) { if (Sib->Type & LIGHT_SOURCE_OBJECT) { if (((LIGHT_SOURCE *)Sib)->Children != NULL) { frame_level++; } } else { frame_level++; } Get_Object_Stats(Sib, FALSE, FALSE, FALSE); } sum1 = sum2 = sum3 = sum4 = sum5 = sum6 = sum7 = 0; for (i = 0; i < NUMBER_OF_TYPES; i++) { sum1 += counter[i][FLAG_SUM]; sum2 += counter[i][FLAG_USED_IN_CSG]; sum3 += counter[i][FLAG_INFINITE]; sum4 += counter[i][FLAG_BOUND_OBJECT]; sum5 += counter[i][FLAG_CLIP_OBJECT]; sum6 += counter[i][FLAG_BOUNDED]; sum7 += counter[i][FLAG_CLIPPED]; } fprintf(stderr, " sum csg infin bound clip bounded clipped KBytes\n"); fprintf(stderr, "Blob "); Print_Object_Info(TYPE_BLOB); fprintf(stderr, "Box "); Print_Object_Info(TYPE_BOX); fprintf(stderr, "Cone/Cylinder "); Print_Object_Info(TYPE_CONE); fprintf(stderr, "Ellipsoid "); Print_Object_Info(TYPE_ELLIPSOID); fprintf(stderr, "Height Field "); Print_Object_Info(TYPE_HEIGHT_FIELD); fprintf(stderr, "Sphere "); Print_Object_Info(TYPE_SPHERE); fprintf(stderr, "Bicubic Patch "); Print_Object_Info(TYPE_BICUBIC_PATCH); fprintf(stderr, "Disc "); Print_Object_Info(TYPE_DISC); fprintf(stderr, "Smooth Triangle "); Print_Object_Info(TYPE_SMOOTH_TRIANGLE); fprintf(stderr, "Triangle "); Print_Object_Info(TYPE_TRIANGLE); fprintf(stderr, "Plane "); Print_Object_Info(TYPE_PLANE); fprintf(stderr, "Poly/Quartic "); Print_Object_Info(TYPE_POLY); fprintf(stderr, "Quadric "); Print_Object_Info(TYPE_QUADRIC); fprintf(stderr, "CSG Intersection"); Print_Object_Info(TYPE_CSG_INTERSECTION); fprintf(stderr, "CSG Merge "); Print_Object_Info(TYPE_CSG_MERGE); fprintf(stderr, "CSG Union "); Print_Object_Info(TYPE_CSG_UNION); fprintf(stderr, "Light Source "); Print_Object_Info(TYPE_LIGHT_SOURCE); fprintf(stderr, "TOTAL : %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n", sum1, sum2, sum3, sum4, sum5, sum6, sum7); fprintf(stderr, "Scene contains %ld frame level objects.\n", frame_level); /* Print amount of allocated memory */ if (Mem_Vista_Buffer) fprintf(stderr, "Vista Buffer : %.2f KBytes\n", (DBL)(Mem_Vista_Buffer) / 1024.0); if (Mem_Light_Buffers) fprintf(stderr, "Light Buffer : %.2f KBytes\n", (DBL)(Mem_Light_Buffers) / 1024.0); if (Allocated_Memory) fprintf(stderr, "Total : %.2f KBytes\n", (DBL)Allocated_Memory / 1024.0); } /***************************************************************************** * * FUNCTION : Clip_Polygon * * ARGUMENTS : Points - polygon's points * PointCnt - Number of points in polygon * VX1, VY1, VX2, VY1 - Normal vectors of the clipping planes * DX1, DY1, DX2, DY2 - Distances of the clipping planes from * the origin * * MODIFIED ARGS : Points, PointCnt * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Clip polygon at the viewing pyramid define by the normal vectors * VX1, VX2, VY1, VY2 and the distances DX1, DX2, DY1, DY2. * * CHANGES * * - * ******************************************************************************/ void Clip_Polygon (Points, PointCnt, VX1, VX2, VY1, VY2, DX1, DX2, DY1, DY2) VECTOR *Points; int *PointCnt; VECTOR *VX1, *VX2, *VY1, *VY2; DBL DX1, DX2, DY1, DY2; { DBL aktd, pred, fird, k; VECTOR aktP, intP, preP, firP, d; int i, pc; VECTOR ClipPoints[MAX_CLIP_POINTS]; /********** clip polygon at "left" plane **********/ pc = 0; firP = Points[0]; fird = VX1->x * firP.x + VX1->y * firP.y + VX1->z * firP.z - DX1; if (fird <= 0.0) ClipPoints[pc++] = firP; aktP = preP = firP; aktd = pred = fird; for (i = 1; i < *PointCnt; i++) { aktP = Points[i]; aktd = VX1->x * aktP.x + VX1->y * aktP.y + VX1->z * aktP.z - DX1; if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0))) { d.x = preP.x - aktP.x; d.y = preP.y - aktP.y; d.z = preP.z - aktP.z; k = -aktd / (VX1->x * d.x + VX1->y * d.y + VX1->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } if (aktd <= 0.0) ClipPoints[pc++] = aktP; preP = aktP; pred = aktd; } if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0))) { d.x = firP.x - aktP.x; d.y = firP.y - aktP.y; d.z = firP.z - aktP.z; k = -aktd / (VX1->x * d.x + VX1->y * d.y + VX1->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } for (i = 0; i < pc; i++) Points[i] = ClipPoints[i]; if ((*PointCnt = pc) == 0) return; /********** clip polygon at "right" plane **********/ pc = 0; firP = Points[0]; fird = VX2->x * firP.x + VX2->y * firP.y + VX2->z * firP.z - DX2; if (fird <= 0.0) ClipPoints[pc++] = firP; aktP = preP = firP; aktd = pred = fird; for (i = 1; i < *PointCnt; i++) { aktP = Points[i]; aktd = VX2->x * aktP.x + VX2->y * aktP.y + VX2->z * aktP.z - DX2; if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0))) { d.x = preP.x - aktP.x; d.y = preP.y - aktP.y; d.z = preP.z - aktP.z; k = -aktd / (VX2->x * d.x + VX2->y * d.y + VX2->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } if (aktd <= 0.0) ClipPoints[pc++] = aktP; preP = aktP; pred = aktd; } if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0))) { d.x = firP.x - aktP.x; d.y = firP.y - aktP.y; d.z = firP.z - aktP.z; k = -aktd / (VX2->x * d.x + VX2->y * d.y + VX2->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } for (i = 0; i < pc; i++) Points[i] = ClipPoints[i]; if ((*PointCnt = pc) == 0) return; /********** clip polygon at "bottom" plane **********/ pc = 0; firP = Points[0]; fird = VY1->x * firP.x + VY1->y * firP.y + VY1->z * firP.z - DY1; if (fird <= 0.0) ClipPoints[pc++] = firP; aktP = preP = firP; aktd = pred = fird; for (i = 1; i < *PointCnt; i++) { aktP = Points[i]; aktd = VY1->x * aktP.x + VY1->y * aktP.y + VY1->z * aktP.z - DY1; if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0))) { d.x = preP.x - aktP.x; d.y = preP.y - aktP.y; d.z = preP.z - aktP.z; k = -aktd / (VY1->x * d.x + VY1->y * d.y + VY1->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } if (aktd <= 0.0) ClipPoints[pc++] = aktP; preP = aktP; pred = aktd; } if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0))) { d.x = firP.x - aktP.x; d.y = firP.y - aktP.y; d.z = firP.z - aktP.z; k = -aktd / (VY1->x * d.x + VY1->y * d.y + VY1->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } for (i = 0; i < pc; i++) Points[i] = ClipPoints[i]; if ((*PointCnt = pc) == 0) return; /********** clip polygon at "top" plane **********/ pc = 0; firP = Points[0]; fird = VY2->x * firP.x + VY2->y * firP.y + VY2->z * firP.z - DY2; if (fird <= 0.0) ClipPoints[pc++] = firP; aktP = preP = firP; aktd = pred = fird; for (i = pc = 0; i < *PointCnt; i++) { aktP = Points[i]; aktd = VY2->x * aktP.x + VY2->y * aktP.y + VY2->z * aktP.z - DY2; if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0))) { d.x = preP.x - aktP.x; d.y = preP.y - aktP.y; d.z = preP.z - aktP.z; k = -aktd / (VY2->x * d.x + VY2->y * d.y + VY2->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } if (aktd <= 0.0) ClipPoints[pc++] = aktP; preP = aktP; pred = aktd; } if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0))) { d.x = firP.x - aktP.x; d.y = firP.y - aktP.y; d.z = firP.z - aktP.z; k = -aktd / (VY2->x * d.x + VY2->y * d.y + VY2->z * d.z); intP.x = aktP.x + k * d.x; intP.y = aktP.y + k * d.y; intP.z = aktP.z + k * d.z; ClipPoints[pc++] = intP; } for (i = 0; i < pc; i++) Points[i] = ClipPoints[i]; *PointCnt = pc; } /***************************************************************************** * * FUNCTION : MInvers * * ARGUMENTS : m - matrix to invert * r - inverted matrix * * MODIFIED ARGS : r * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Invert a 4x4 matrix. * * CHANGES * * - * ******************************************************************************/ void MInvers(r, m) MATRIX *r, *m; { DBL d00, d01, d02, d03; DBL d10, d11, d12, d13; DBL d20, d21, d22, d23; DBL d30, d31, d32, d33; DBL m00, m01, m02, m03; DBL m10, m11, m12, m13; DBL m20, m21, m22, m23; DBL m30, m31, m32, m33; DBL D; m00 = (*m)[0][0]; m01 = (*m)[0][1]; m02 = (*m)[0][2]; m03 = (*m)[0][3]; m10 = (*m)[1][0]; m11 = (*m)[1][1]; m12 = (*m)[1][2]; m13 = (*m)[1][3]; m20 = (*m)[2][0]; m21 = (*m)[2][1]; m22 = (*m)[2][2]; m23 = (*m)[2][3]; m30 = (*m)[3][0]; m31 = (*m)[3][1]; m32 = (*m)[3][2]; m33 = (*m)[3][3]; d00 = m11*m22*m33 + m12*m23*m31 + m13*m21*m32 - m31*m22*m13 - m32*m23*m11 - m33*m21*m12; d01 = m10*m22*m33 + m12*m23*m30 + m13*m20*m32 - m30*m22*m13 - m32*m23*m10 - m33*m20*m12; d02 = m10*m21*m33 + m11*m23*m30 + m13*m20*m31 - m30*m21*m13 - m31*m23*m10 - m33*m20*m11; d03 = m10*m21*m32 + m11*m22*m30 + m12*m20*m31 - m30*m21*m12 - m31*m22*m10 - m32*m20*m11; d10 = m01*m22*m33 + m02*m23*m31 + m03*m21*m32 - m31*m22*m03 - m32*m23*m01 - m33*m21*m02; d11 = m00*m22*m33 + m02*m23*m30 + m03*m20*m32 - m30*m22*m03 - m32*m23*m00 - m33*m20*m02; d12 = m00*m21*m33 + m01*m23*m30 + m03*m20*m31 - m30*m21*m03 - m31*m23*m00 - m33*m20*m01; d13 = m00*m21*m32 + m01*m22*m30 + m02*m20*m31 - m30*m21*m02 - m31*m22*m00 - m32*m20*m01; d20 = m01*m12*m33 + m02*m13*m31 + m03*m11*m32 - m31*m12*m03 - m32*m13*m01 - m33*m11*m02; d21 = m00*m12*m33 + m02*m13*m30 + m03*m10*m32 - m30*m12*m03 - m32*m13*m00 - m33*m10*m02; d22 = m00*m11*m33 + m01*m13*m30 + m03*m10*m31 - m30*m11*m03 - m31*m13*m00 - m33*m10*m01; d23 = m00*m11*m32 + m01*m12*m30 + m02*m10*m31 - m30*m11*m02 - m31*m12*m00 - m32*m10*m01; d30 = m01*m12*m23 + m02*m13*m21 + m03*m11*m22 - m21*m12*m03 - m22*m13*m01 - m23*m11*m02; d31 = m00*m12*m23 + m02*m13*m20 + m03*m10*m22 - m20*m12*m03 - m22*m13*m00 - m23*m10*m02; d32 = m00*m11*m23 + m01*m13*m20 + m03*m10*m21 - m20*m11*m03 - m21*m13*m00 - m23*m10*m01; d33 = m00*m11*m22 + m01*m12*m20 + m02*m10*m21 - m20*m11*m02 - m21*m12*m00 - m22*m10*m01; D = m00*d00 - m01*d01 + m02*d02 - m03*d03; if (fabs(D) < EPSILON) Fatal_Error("Singular matrix in MInvers.\n"); (*r)[0][0] = +d00/D; (*r)[0][1] = -d10/D; (*r)[0][2] = +d20/D; (*r)[0][3] = -d30/D; (*r)[1][0] = -d01/D; (*r)[1][1] = +d11/D; (*r)[1][2] = -d21/D; (*r)[1][3] = +d31/D; (*r)[2][0] = +d02/D; (*r)[2][1] = -d12/D; (*r)[2][2] = +d22/D; (*r)[2][3] = -d32/D; (*r)[3][0] = -d03/D; (*r)[3][1] = +d13/D; (*r)[3][2] = -d23/D; (*r)[3][3] = +d33/D; } /***************************************************************************** * * FUNCTION : Fatal_Error * * ARGUMENTS : str - String to print to stderr * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Print an error message and leave program. * * CHANGES * * - * ******************************************************************************/ void Fatal_Error(str) char *str; { fputs(str, stderr); exit(1); } /***************************************************************************** * * FUNCTION : Fatal_MAError * * ARGUMENTS : str - String to print to stderr after out of memory message * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Print an error message and leave program. Call if memory * allocation fails. * * CHANGES * * - * ******************************************************************************/ void Fatal_MAError(str) char *str; { fprintf(stderr, "Out of memory. Cannot allocate %s.\n", str); exit (1); } /***************************************************************************** * * FUNCTION : Begin_Point * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Print points to stderr and initialize point counter. * * CHANGES * * - * ******************************************************************************/ void Begin_Point() { fprintf(stderr, "..."); Point_Counter = 0; } /***************************************************************************** * * FUNCTION : Print_Point * * ARGUMENTS : Repeat - Determines after how many calls a point will be printed * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Print points to stderr. * * CHANGES * * - * ******************************************************************************/ void Print_Point(Repeat) int Repeat; { if ((Point_Counter % Repeat) == 0) fprintf(stderr, "."); Point_Counter++; } /***************************************************************************** * * FUNCTION : End_Point * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Print newline to stderr. * * CHANGES * * - * ******************************************************************************/ void End_Point() { fprintf(stderr, "\n"); } /***************************************************************************** * * FUNCTION : Draw_Projection * * ARGUMENTS : Project - projection to draw * color - Color to be used * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Draws a projection in the specified color. * * CHANGES * * - * ******************************************************************************/ static void Draw_Projection(Project, color) PROJECT *Project; int color; { int x, y, x1, x2, y1, y2; unsigned short int r, g, b; switch (color) { case RED : r = 255; g = b = 0; break; case GREEN : g = 255; r = b = 0; break; case BLUE : b = 255; r = g = 0; break; default : r = g = b = 255; } x1 = Project->x1; x2 = Project->x2; y1 = Project->y1; y2 = Project->y2; if ((x1 <= x2) && (y1 <= y2)) { if (x1 < 0) x1 = 0; if (x2 < 0) x2 = 0; if (y1 < 0) y1 = 0; if (y2 < 0) y2 = 0; if (x1 >= Frame.Screen_Width) x1 = Frame.Screen_Width - 1; if (x2 >= Frame.Screen_Width) x2 = Frame.Screen_Width - 1; if (y1 >= Frame.Screen_Height) y1 = Frame.Screen_Height - 1; if (y2 >= Frame.Screen_Height) y2 = Frame.Screen_Height - 1; for (x = x1; x <= x2; x++) { display_plot (x, y1, r, g, b); display_plot (x, y2, r, g, b); } for (y = y1; y <= y2; y++) { display_plot (x1, y, r, g, b); display_plot (x2, y, r, g, b); } } } /***************************************************************************** * * FUNCTION : Draw_Vista * * ARGUMENTS : Tree - current node/leaf in the vista tree * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Draws recursively all projections of subnodes in the current node. * * CHANGES * * - * ******************************************************************************/ static void Draw_Vista(Tree) PROJECT_TREE_NODE *Tree; { unsigned short i; PROJECT_TREE_LEAF *Leaf; if (Tree->is_leaf) { Leaf = (PROJECT_TREE_LEAF *)Tree; if (Leaf->Object->Type & COMPOUND_OBJECT) { Draw_Projection(&Leaf->Project, BLUE); } else { Draw_Projection(&Leaf->Project, RED); } } else { for (i = 0; i < Tree->Entries; i++) { Draw_Vista(Tree->Entry[i]); } } /* draw bounding object's vista */ /* Draw_Projection(&Tree->Project, GREEN); */ } /***************************************************************************** * * FUNCTION : Draw_Vista_Tree * * ARGUMENTS : none * * MODIFIED ARGS : none * * RETURN VALUE : none * * AUTHOR : Dieter Bayer, May, 1994 * * DESCRIPTION * * Draw the vista tree. * * CHANGES * * - * ******************************************************************************/ void Draw_Vista_Tree() { if (Extended_Options & USE_VISTA_BUFFER) { Draw_Vista(Root_Vista); } } #endif