| /*************************************************************************/ |
| /* */ |
| /* Copyright (c) 1994 Stanford University */ |
| /* */ |
| /* All rights reserved. */ |
| /* */ |
| /* Permission is given to use, copy, and modify this software for any */ |
| /* non-commercial purpose as long as this copyright notice is not */ |
| /* removed. All other uses, including redistribution in whole or in */ |
| /* part, are forbidden without prior written permission. */ |
| /* */ |
| /* This software is provided with absolutely no warranty and no */ |
| /* support. */ |
| /* */ |
| /*************************************************************************/ |
| |
| |
| #ifndef _PATCH_H |
| #define _PATCH_H |
| |
| |
| /************************************************************************ |
| * |
| * Constants |
| * |
| *************************************************************************/ |
| |
| #define F_COPLANAR (5.0e-2) /* H(P) < F_COPLANAR then P is on the plane */ |
| #define N_VISIBILITY_TEST_RAYS (10) /* number of "random", "magic" rays fired |
| between patches to test visibility */ |
| |
| #define FF_GEOMETRY_ERROR (1.0) /* FF relative error due to Fdf approx |
| and cosine approx of angle */ |
| #define FF_GEOMETRY_VARIANCE (1.0) /* FF relative varance with in elem */ |
| #define FF_VISIBILITY_ERROR (1.0 / N_VISIBILITY_TEST_RAYS) |
| |
| |
| |
| /************************************************************************ |
| * |
| * Intersection code |
| * |
| *************************************************************************/ |
| |
| #define POINT_POSITIVE_SIDE (1) |
| #define POINT_NEGATIVE_SIDE (2) |
| #define POINT_ON_PLANE (0) |
| |
| #define P1_POSITIVE (1) |
| #define P1_NEGATIVE (2) |
| #define P2_POSITIVE (4) |
| #define P2_NEGATIVE (8) |
| #define P3_POSITIVE (16) |
| #define P3_NEGATIVE (32) |
| #define ANY_POSITIVE (P1_POSITIVE | P2_POSITIVE | P3_POSITIVE) |
| #define ANY_NEGATIVE (P1_NEGATIVE | P2_NEGATIVE | P3_NEGATIVE) |
| #define POSITIVE_SIDE(code) (((code) & ANY_NEGATIVE) == 0) |
| #define NEGATIVE_SIDE(code) (((code) & ANY_POSITIVE) == 0) |
| #define INTERSECTING(code) ( ((code) & ANY_NEGATIVE) \ |
| && ((code) & ANY_POSITIVE) ) |
| #define P1_CODE(code) (code & 3) |
| #define P2_CODE(code) ((code >> 2) & 3) |
| #define P3_CODE(code) ((code >> 4) & 3) |
| |
| /************************************************************************ |
| * |
| * Visibility Testing |
| * |
| *************************************************************************/ |
| |
| #define VISIBILITY_UNDEF ((float)-1.0) |
| #define PATCH_CACHE_SIZE (2) /* The first two cache entries |
| covers about 95% of the total cache hits, so using |
| more doesn't help too much. */ |
| |
| extern float visibility() ; |
| extern void compute_visibility_values() ; |
| extern void visibility_task() ; |
| |
| /************************************************************************ |
| * |
| * Refinement Advice |
| * |
| *************************************************************************/ |
| |
| #define _NO_INTERACTION (1) |
| #define _NO_REFINEMENT_NECESSARY (2) |
| #define _REFINE_PATCH_1 (4) |
| #define _REFINE_PATCH_2 (8) |
| #define _NO_VISIBILITY_NECESSARY (16) |
| |
| #define NO_INTERACTION(c) ((c) & _NO_INTERACTION) |
| #define NO_REFINEMENT_NECESSARY(c) ((c) & _NO_REFINEMENT_NECESSARY) |
| #define REFINE_PATCH_1(c) ((c) & _REFINE_PATCH_1) |
| #define REFINE_PATCH_2(c) ((c) & _REFINE_PATCH_2) |
| #define NO_VISIBILITY_NECESSARY(c) ((c) & _NO_VISIBILITY_NECESSARY) |
| |
| |
| /************************************************************************ |
| * |
| * Vertex - 3D coordinate |
| * |
| *************************************************************************/ |
| |
| typedef struct { |
| float x, y, z ; |
| } Vertex ; |
| |
| |
| extern float vector_length() ; |
| extern float distance() ; |
| extern float normalize_vector() ; |
| extern float inner_product() ; |
| extern void cross_product() ; |
| extern float plane_normal() ; |
| extern void center_point(), four_center_points() ; |
| extern void print_point() ; |
| |
| |
| /************************************************************************ |
| * |
| * Color (R,G,B) |
| * |
| *************************************************************************/ |
| |
| typedef struct { |
| float r, g, b ; |
| } Rgb ; |
| |
| |
| |
| extern void print_rgb() ; |
| |
| |
| |
| /************************************************************************ |
| * |
| * Element Vertex |
| * |
| * ElementVertex represents a vertex of an element. A vertex structure |
| * is shared by those elements which contain the vertex as part of their |
| * vertex list. |
| * |
| *************************************************************************/ |
| |
| typedef struct _elemvertex { |
| Vertex p ; /* Coordinate of the vertex */ |
| Rgb col ; /* Color of the vertex */ |
| float weight ; /* weight */ |
| Shared_Lock *ev_lock ; |
| } ElemVertex ; |
| |
| |
| #define N_ELEMVERTEX_ALLOCATE (16) |
| extern ElemVertex *get_elemvertex() ; |
| extern ElemVertex *create_elemvertex() ; /* Constructor */ |
| extern void init_elemvertex() ; /* Initialize free buffer */ |
| |
| |
| /************************************************************************ |
| * |
| * Edge |
| * |
| * Edge represents each edge of the element. Two adjacent elements |
| * share the same edge. As an element is subdivided, the edge is also |
| * subdivided. The edges form a binary tree, which can be viewed as a |
| * projection of the element subdivision along an edge of the element. |
| * In other words, the edge structure binds elements at the same height. |
| * Note that the vertices may appear in reverse order in the edge structure |
| * with respect to the order in the patch/element definition. |
| * |
| *************************************************************************/ |
| |
| typedef struct _edge { |
| ElemVertex *pa, *pb ; |
| struct _edge *ea, *eb ; /* Edge (A-center) and (center-B) */ |
| Shared_Lock *edge_lock ; /* Use segment0 */ |
| } Edge ; |
| |
| |
| #define N_EDGE_ALLOCATE (16) |
| extern Edge *get_edge() ; |
| extern Edge *create_edge() ; /* Constructor */ |
| extern void subdivide_edge() ; |
| extern void init_edge() ; /* Initialize free buffer */ |
| extern void foreach_leaf_edge() ; |
| |
| #define _LEAF_EDGE(e) ((e)->ea == 0) |
| #define EDGE_REVERSE(e,a,b) ((e)->pa == (b)) |
| |
| |
| /************************************************************************ |
| * |
| * Planar equation |
| * |
| * Plane equation (in implicit form) of the triangle patch. |
| * A point P on the plane satisfies |
| * (N.P) + C = 0 |
| * where N is the normal vector of the patch, C is a constant which |
| * is the distance of the plane from the origin scaled by -|N|. |
| * |
| *************************************************************************/ |
| |
| typedef struct { |
| Vertex n ; /* Normal vector (normalized) */ |
| float c ; /* Constant */ |
| /* Nx*x + Ny*y + Nz*z + C = 0 */ |
| } PlaneEqu ; |
| |
| |
| extern float plane_equ() ; |
| extern float comp_plane_equ() ; |
| extern int point_intersection() ; |
| extern int patch_intersection() ; |
| extern void print_plane_equ() ; |
| |
| |
| /************************************************************************ |
| * |
| * Patch (also a node of the BSP tree) |
| * |
| * The Patch represents a triangular patch (input polygon) of the given |
| * geometric model (i.e., room scene). The Patch contains 'per-patch' |
| * information such as the plane equation, area, and color. The Patch also |
| * serves as a node of the BSP tree which is used to test patch-patch |
| * visibility. The Patch points to the root level of the element quad-tree. |
| * Geometrically speaking, the Patch and the root represent the same |
| * triangle. |
| * Although coordinates of the vertices are given by the Edge structure, |
| * copies are stored in the Patch to allow fast access to the coordinates |
| * during the visibility test. |
| * For cost based task distribution another structure, Patch_Cost, is |
| * also used. This structure is made separate from the Patch structure |
| * since gathering cost statistics is a frequently read/write operation. |
| * If it were in the Patch structure, updating a cost would result in |
| * invalidation of the Patch structure and cause cache misses during |
| * BSP traversal. |
| * |
| *************************************************************************/ |
| |
| struct _element ; |
| |
| typedef struct _patch { |
| ElemVertex *ev1, *ev2, *ev3 ; /* ElemVertecies of the patch */ |
| Edge *e12, *e23, *e31 ; /* Edges of the patch */ |
| Vertex p1, p2, p3 ; /* Vertices of the patch */ |
| PlaneEqu plane_equ ; /* Plane equation H(x,y,z) */ |
| float area ; /* Area of the patch */ |
| Rgb color ; /* Diffuse color of the patch */ |
| /* (reflectance) */ |
| Rgb emittance ; /* Radiant emmitence */ |
| |
| struct _patch *bsp_positive ; /* BSP tree H(x,y,z) >= 0 */ |
| struct _patch *bsp_negative ; /* H(x,y,z) < 0 */ |
| struct _patch *bsp_parent ; /* BSP backpointer to the parent*/ |
| |
| struct _element *el_root ; /* Root of the element tree */ |
| int seq_no ; /* Patch sequence number */ |
| } Patch ; |
| |
| extern void foreach_patch_in_bsp(), foreach_depth_sorted_patch() ; |
| extern void define_patch() ; |
| extern void refine_newpatch() ; |
| extern Patch *get_patch() ; |
| extern void init_patchlist() ; |
| extern void print_patch() ; |
| extern void print_bsp_tree() ; |
| |
| |
| typedef struct { |
| Patch *patch ; |
| Shared_Lock *cost_lock ; /* Cost variable lock */ |
| int n_bsp_node ; /* Number of BSP nodes visited */ |
| int n_total_inter ; /* Total number of interactions */ |
| int cost_estimate ; /* Cost estimate */ |
| int cost_history[11] ; /* Cost history */ |
| } Patch_Cost ; |
| |
| /* Patch cost: |
| Visiting a node in BSP tree: 150 cyc (overall) |
| Gathering ray per interaction: 50 cyc (overall avg) */ |
| |
| #define PATCH_COST(p) ((p)->n_bsp_node * 3 + (p)->n_total_inter) |
| #define PATCH_COST_ESTIMATE(p) ((p)->cost_history[0] \ |
| + ((p)->cost_history[1] >> 1)\ |
| + ((p)->cost_history[2] >> 2) ) |
| |
| |
| /************************************************************************ |
| * |
| * Element |
| * |
| * The Element represents each node of the quad-tree generated by the |
| * hierarchical subdivision. The Element structure consists of: |
| * - pointers to maintain the tree structure |
| * - a linear list of interacting elements |
| * - radiosity value of the element |
| * - pointer to the vertex and edge data structures |
| * |
| * To allow smooth radiosity interpolation across elements, an element |
| * shares edges and vertices with adjacent elements. |
| * |
| *************************************************************************/ |
| |
| struct _interact ; |
| |
| typedef struct _element { |
| Shared_Lock *elem_lock ; /* Element lock variable (seg 1) */ |
| Patch *patch ; /* Original patch of the element */ |
| |
| struct _element *parent ; /* Quad tree (parent) */ |
| struct _element *center ; /* (center triangle) */ |
| struct _element *top ; /* (top) */ |
| struct _element *left ; /* (left) */ |
| struct _element *right ; /* (right) */ |
| |
| struct _interact *interactions ; /* Top of light interaction list */ |
| int n_interactions ; /* Total # of interactions */ |
| struct _interact *vis_undef_inter ; /* Top of visibility undef list */ |
| int n_vis_undef_inter ; /* # of interactions whose visibility |
| is not yet calculated */ |
| Rgb rad ; /* Radiosity of this element |
| (new guess of B) */ |
| Rgb rad_in ; /* Sum of anscestor's radiosity */ |
| Rgb rad_subtree ; /* Area weighted sum of subtree's |
| radiosity (includes this elem) */ |
| int join_counter ; /* # of unfinished subprocesses */ |
| |
| ElemVertex *ev1, *ev2, *ev3 ; /* Vertices of the element */ |
| Edge *e12, *e23, *e31 ; /* Edges of the element */ |
| float area ; /* Area of the element */ |
| } Element ; |
| |
| |
| extern void foreach_element_in_patch(), foreach_leaf_element_in_patch() ; |
| extern void ff_refine_elements() ; |
| extern void subdivide_element() ; |
| extern int element_completely_invisible() ; |
| extern void process_rays() ; |
| extern Element *get_element() ; |
| extern void init_elemlist() ; |
| extern void print_element() ; |
| |
| #define _LEAF_ELEMENT(e) ((e)->center == 0) |
| |
| #if MEM_CONSISTENCY_PROCESSOR |
| #define LEAF_ELEMENT(e) _LEAF_ELEMENT((e)) |
| #endif |
| |
| #if (MEM_CONSISTENCY_RELEASE || MEM_CONSISTENCY_WEAK) |
| extern int leaf_element() ; |
| #define LEAF_ELEMENT(e) (leaf_element((e))) |
| #endif |
| |
| |
| /************************************************************************ |
| * |
| * Interaction |
| * |
| *************************************************************************/ |
| |
| typedef struct _interact { |
| struct _interact *next ; /* Next entry of the list */ |
| Element *destination ; /* Partner of the interaction */ |
| float formfactor_out ; /* Form factor from this patch */ |
| float formfactor_err ; /* Error of FF */ |
| float area_ratio ; /* Area(this) / Area(dest) */ |
| float visibility ; /* Visibility (0 - 1.0) */ |
| } Interaction ; |
| |
| |
| extern void foreach_interaction_in_element() ; |
| extern void compute_interaction(), compute_formfactor() ; |
| extern void insert_interaction(), delete_interaction() ; |
| extern void insert_vis_undef_interaction(), delete_vis_undef_interaction() ; |
| extern void init_interactionlist() ; |
| extern Interaction *get_interaction() ; |
| extern void free_interaction() ; |
| extern void print_interaction() ; |
| |
| #endif |
