/***************************************************************************** * Abstraction of the shadow deternination algorithm, using projective method.* * Use: GatherShadows as algorithm initialization; ShadowLineInit, * * IsInShadow, ShadowLineIncr in order to get pixel shadowness. * ****************************************************************************** * (C) Gershon Elber, Technion, Israel Institute of Technology * ****************************************************************************** * Written by: Bassarab Dmitri & Plavnik Michael Ver 0.2, Apr. 1995 * *****************************************************************************/ #include #include #include #include "program.h" #include "shadow.h" #include "debug.h" #define IS_ABOVE(t, s) ((s)>0 ? (t) >= 0.0 : (t) <= 0.0) #define APX_ABOVE(t) ((t) = fabs(t) < IRIT_EPS ? 0.0 : (t)) #define LT_DELTA(lt) (lt > 0.0 ? -0.05 : 0.05) #define IS_SEPARATE_ON_DIM(d, mn1, mx1, mn2, mx2) \ ((mx1)[(d)] <= (mn2)[(d)] || (mx2)[(d)] <= (mn1)[(d)]) /* ShadowEdges. */ #define POOLADJUST_SIZE 16 #define MINMAX_SCALE 0.07 #define POOL_OPTIMAL_SIZE(NEdges) (9 * (NEdges) / 4) #define POOL_ALLOC_ENTRY(p) ((p) -> PMax > (p) -> PEnd ? (p) -> PEnd++ \ : NULL) #define POOL_FREE_ENTRY(p) (--(p) -> PEnd) #define POOL_RESET(p) ((p) -> PMax = (p) -> Active) #define POOL_SET(p, node) ((p) -> PMax = node) #define POOL_ALWAYS_LIT(p) ((p) -> PEnd = \ (ShadowEdgeStruct *) (&((p) -> PEnd))) #define POOL_SELF_SHADOWED(p) ((p) -> PEnd = (ShadowEdgeStruct *) (p)) #define IS_POOL_ALWAYS_LIT(p) ((p) -> PEnd == \ (ShadowEdgeStruct *) (&((p) -> PEnd))) #define IS_POOL_SELF_SHADOWED(p) ((p) -> PEnd == (ShadowEdgeStruct *) (p)) #define IS_POOL_MARKED(p) (IS_POOL_ALWAYS_LIT(p) || \ IS_POOL_SELF_SHADOWED(p)) #define IS_POOL_VALID(p) ((p) -> Pool != NULL) /***************************************************************************** * DESCRIPTION: * * Macro function which determines if two edges are on the same side of * * the horizontal axes passing throw the common vertex. Assumes that two * * edges are sequential edges in the polygon representation. * * * * PARAMETERS: * * e1: IN, pointer to the first shadow edge object. * * e2: IN, pointer to the second shadow edge object. * * * * RETURN VALUE: * * int: TRUE if edges are on the same side, FALSE otherwise. * *****************************************************************************/ #define IS_SHADOW_EDGE_SAME_SIDE(e1, e2) \ (((e1) -> yMax == (e2) -> yMax) || \ ((e1) -> yMax - (e1) -> dy == (e2) -> yMax - (e2) -> dy)) /* We use list of VertexLink entries to describe intersection of polygon */ /* with plane, that is a sequence of new polygons. Data necessary to obtain */ /* such list is also keeped in that data structure. */ typedef struct VertexLinkStruct { PointType pt; /* Coordinate of the vertex. */ RealType t; /* Parameter in parametric line equation. */ struct VertexLinkStruct *next; struct VertexLinkStruct *back; /* Links to next and previous vertices. */ } VertexLinkStruct; typedef struct { VertexLinkStruct *vPoly, *vPolyEnd; /* Initial polygon range. */ VertexLinkStruct *vAbove, *vAboveEnd;/* Above plane part of the polygon. */ VertexLinkStruct *vCross, *vCrossEnd; /* With plane intersection points. */ FlatStruct *flat; } PolyPlaneSectInfoStruct; typedef void (*ProjectorProcType) (VertexLinkStruct *, RealType, PointType); static ShadowEdgePoolStruct *PoolInit(ShadowEdgePoolStruct *p, size_t num); static ShadowEdgePoolStruct *PoolAdjust(ShadowEdgePoolStruct *p); static void PoolDestruct(ShadowEdgePoolStruct *p); static void PoolActivate(ShadowEdgePoolStruct *p, ShadowEdgeStruct *Node); static void PoolKill(ShadowEdgePoolStruct *p, ShadowEdgeStruct *Node); static ShadowEdgeStruct *ShadowEdgeInit(ShadowEdgeStruct *e, FlatStruct *p, RealType *v0, RealType *v1); static int ShadowEdgeCmp(const void *a1, const void *a2); static ShadowEdgeStruct *ShadowEdgeLeftmost(ShadowEdgeStruct *EMin, ShadowEdgeStruct *e, int XMin); static void ShadowEdgeLeftRightOrder(ShadowEdgeStruct *e1, ShadowEdgeStruct *e2); static int IsPolySelfShadowed(IPPolygonStruct *Poly, RealType lt, LightStruct *l); static void PrspAdjustBBoxAux(unsigned int Dim, PointType PtMin, PointType PtMax); static void PrspSeparationInit(FlatStruct *f, LightStruct *lt); static void ParlSeparationInit(FlatStruct *f, LightStruct *lt); static int IsSeparatedOnSphere(FlatStruct *p, FlatStruct *f); static int IsSeparatedOnPlane(FlatStruct *p, FlatStruct *f); static void PolyCuttingInit(PolyPlaneSectInfoStruct *s, FlatStruct *p, FlatStruct *f); static void PolyCutByPlane(PolyPlaneSectInfoStruct *i, int Side); static int VertexLinkXCmp(const void *a1, const void *a2); static int VertexLinkYCmp(const void *a1, const void *a2); static void PolyAboveSectionProject(PolyPlaneSectInfoStruct *s, RealType lt, PointType l, ProjectorProcType Projector); static void PrspProjector(VertexLinkStruct *j, RealType lt, PointType l); static void ParlProjector(VertexLinkStruct * j, RealType lt, PointType l); static void PolyPrspProject(FlatStruct *p, FlatStruct *f, RealType lt, PointType l); static void PolyParlProject(FlatStruct *p, FlatStruct *f, RealType lt, VectorType l); static void ShadowsEval(FlatStruct *f, LightStruct *l); static int nEdgesTotal = 0; static PolyPlaneSectInfoStruct Sect; /* All zero default initialization. */ /***************************************************************************** * DESCRIPTION: * * Constructs shadow edge pool with maximal number of entries eq. "num". * * Assumes that "pool != NULL". On fail pool is in invalid state, check it * * with IS_POOL_VALID before use. * * * * PARAMETERS: * * Pool: OUT, pool data object. * * Num: IN, maximal pool size. * * * * RETURN VALUE: * * ShadowEdgePoolStruct *: pointer to initialized pool. * *****************************************************************************/ static ShadowEdgePoolStruct *PoolInit(ShadowEdgePoolStruct *Pool, size_t Num) { ShadowEdgeStruct *p; p = MALLOC(ShadowEdgeStruct, Num); ASSERT(p); Pool -> PMax = p + Num; Pool -> Pool = Pool -> Active = Pool -> Waiting = Pool -> PEnd = p; return Pool; } /***************************************************************************** * DESCRIPTION: * * We seized a huge chunk of memory in PoolInit, reallocate pool memory * * layout to free resource. Common case is done without actual moving of * * data in memory and state of the object is unchanged. If we do not use * * memory of the pool for usefull data, pool is assigned invalid state. * * Assumes that "p != NULL" and "PoolInit" is called before. * * * * PARAMETERS: * * p: IN OUT, pointer to the pool object. * * * * RETURN VALUE: * * ShadowEdgePool *: pointer to the updated pool. * *****************************************************************************/ static ShadowEdgePoolStruct *PoolAdjust(ShadowEdgePoolStruct *p) { ASSERT(p); if (p -> PMax - p -> PEnd > POOLADJUST_SIZE) { int Size = p -> PEnd - p -> Pool; if (!Size) PoolDestruct(p); else { ShadowEdgeStruct *t = (ShadowEdgeStruct *) IritRealloc(p -> Pool, (char *) p -> PEnd - (char *) p -> Pool); if (t != p -> Pool) { /* Were memory moves. */ p -> PEnd = t + (p -> PEnd - p -> Pool); p -> Pool = p -> Active = p -> Waiting = t; } } } return p; } /***************************************************************************** * DESCRIPTION: * * Releases resources allocated in PoolInit and invalidates Pool state. * * Assumes that "Pool!=NULL". * * * * PARAMETERS: * * Pool: IN OUT, pointer to the pool object. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PoolDestruct(ShadowEdgePoolStruct *Pool) { ASSERT(Pool); if (!IS_POOL_VALID(Pool)) return; FREE(Pool -> Pool); /* State is invalid after that. */ memset(Pool, 0, sizeof(ShadowEdgePoolStruct)); } /***************************************************************************** * DESCRIPTION: * * Moves edge object "Node" from the waiting to active list of the pool. * * Assumes "Pool!=NULL" and "Node != NULL". * * * * PARAMETERS: * * Pool: IN OUT, pointer to the Pool object. * * Node: IN, pointer to the edge object. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PoolActivate(ShadowEdgePoolStruct *Pool, ShadowEdgeStruct *Node) { ASSERT(Pool && Node); if (Pool -> Waiting != Node) SWAP(ShadowEdgeStruct, *Pool -> Waiting, *Node); ++Pool -> Waiting; } /***************************************************************************** * DESCRIPTION: * * Moves edge object "Node" from the active to the killed list of the pool. * * After that node is inaccessible to algorithms. Assumes "Pool!=NULL" * * and "Node!=NULL" and valid pool. * * * * PARAMETERS: * * Pool: IN OUT, pointer to the pool object. * * Node: IN, pointer to the edge object. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PoolKill(ShadowEdgePoolStruct *Pool, ShadowEdgeStruct *Node) { ASSERT(Pool && Node && IS_POOL_VALID(Pool)); if (Pool -> Active != Node) SWAP(ShadowEdgeStruct, *Pool -> Active, *Node); ++Pool -> Active; } /***************************************************************************** * DESCRIPTION: * * Initializes shadow edge data object, which is a projection of some poly- * * gon on "p" flat-polygon plane. That projection is cutted by minimal and * * maximal scan lines values of "p" and edge is directed downside up. Other * * values necessary for polygon filling algorithm are initialized too. * * * * PARAMETERS: * * e: OUT, pointer to the edge object. * * p: IN, pointer to the flat object the shadow edge above belongs. * * v0: IN, pointer to the edge first coordinates. * * v1: IN, pointer to the edge second coordinates. * * * * RETURN VALUE: * * ShadowEdgeStruct *: pointer to the shadow edge initialized or NULL if * * edge is not a subject for shadowing algorithm. * *****************************************************************************/ static ShadowEdgeStruct *ShadowEdgeInit(ShadowEdgeStruct *e, FlatStruct *p, RealType *v0, RealType *v1) { int YMin, YMax, ax, bx, ay = REAL_TO_INT(v0[Y]), by = REAL_TO_INT(v1[Y]); if (ay == by) /* Skip horizontal edges. */ return NULL; if (ay > by) { SWAP(RealType *, v0, v1); /* v0 has always min y. */ ay = REAL_TO_INT(v0[Y]); by = REAL_TO_INT(v1[Y]); } if (((YMin = p -> yMin) >= by) || ((YMax = p -> yMax) <= ay)) return NULL; ax = REAL_TO_INT(v0[X]); bx = REAL_TO_INT(v1[X]); if (YMax < by) { /* Cut by upper limit. */ bx += REAL_TO_INT((v1[X] - v0[X]) * (YMax - by) / (v1[Y] - v0[Y])); by = YMax; } if (YMin > ay) { /* Cut by lower limit. */ ax += REAL_TO_INT((v1[X] - v0[X]) * (YMin - ay) / (v1[Y] - v0[Y])); ay = YMin; } e -> x = ax; e -> dx = bx - ax; e -> dy = e -> inc = by - ay; e -> yMax = by; return e; } /***************************************************************************** * DESCRIPTION: * * Sort callback function. Compares two shadow edges with respec to their * * cuurent (interpolated) X coordinates. Determines which edge is lefter. * * * * PARAMETERS: * * a1: IN, the first edge. * * a2: IN, the second edge. * * * * RETURN VALUE: * * int: as defined by sort function callback specification. * *****************************************************************************/ static int ShadowEdgeCmp(const void *a1, const void *a2) { return ((ShadowEdgeStruct *) a1) -> x - ((ShadowEdgeStruct *) a2) -> x; } /***************************************************************************** * DESCRIPTION: * * Solves between two edgess which one of them is left and which is right * * with respect to scan line crossing the polygon. * * * * PARAMETERS: * * EMin: IN, pointer to the first edge. * * e: IN, pointer to the second edge. * * XMin: IN, minimal X coordinate value between all vertices of the poly * * * * RETURN VALUE: * * ShadowEdgeStruct *: pointer to leftmost edge (as defined in description) * *****************************************************************************/ static ShadowEdgeStruct *ShadowEdgeLeftmost(ShadowEdgeStruct *EMin, ShadowEdgeStruct *e, int XMin) { if (EMin -> dx != 0) if (MIN(e -> x, e -> x + e -> dx) == XMin) { if (e -> dx == 0) return e; if (IS_SHADOW_EDGE_SAME_SIDE(EMin, e)) if (e -> dy * fabs((double) EMin -> dx) > EMin -> dy * fabs((double) e -> dx)) return e; } return EMin; } /***************************************************************************** * DESCRIPTION: * * For all edges in input sequence sets attribute which says if that edge * * is left edge or right on any scan line under current projection. It is * * used as preprocessor step for scan-line algorithm, make it more effici- * * ent then standard version descibed in Foily and Van Dam. * * Assumes that polygons don't contain intersected edges, e1 < e2. * * * * PARAMETERS: * * e1: IN OUT, points to the start of the edge sequence. * * e2: IN OUT, points to the after last edge of the sequence. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void ShadowEdgeLeftRightOrder(ShadowEdgeStruct *e1, ShadowEdgeStruct *e2) { ShadowEdgeStruct *EMin = e1, *e = e1 + 1; int XMin = MIN(EMin -> x, EMin -> x + EMin -> dx); for (; e < e2; ++e) { /* Choose min X pair. */ int x = MIN(e -> x, e -> x + e -> dx); if (x < XMin) { XMin = x; EMin = e; } } e = (EMin == e1) ? e2 - 1 : EMin - 1; /* Calculate previous. */ EMin = ShadowEdgeLeftmost(EMin, EMin + 1 == e2 ? e1 : EMin + 1, XMin); EMin = ShadowEdgeLeftmost(EMin, e, XMin); EMin -> flag = 1; for (e = EMin + 1; e < e2; ++e) e -> flag = IS_SHADOW_EDGE_SAME_SIDE(e, e - 1) ? -(e - 1) -> flag : (e - 1) -> flag; for (e = EMin - 1; e >= e1; --e) e -> flag = IS_SHADOW_EDGE_SAME_SIDE(e, e + 1) ? -(e + 1) -> flag : (e + 1) -> flag; } /***************************************************************************** * DESCRIPTION: * * Determines whether viewer see the polygon lit by the light otherwise * * polygon casts shadow on itself. Algorithm uses plane equation to get * * determine if viewer and light source are at the same side of the plane. * * If we suspect self shadowing, more accurate check for each vertex normal * * is done to discover partialy lit polygons. * * Assumes that plane equation is updated after all coordinate * * transformations, light is directed to the source. * * * * PARAMETERS: * * Poly: IN, Polygon being tested * * lt: IN, plane equation value for the light source point * * l: IN, pointer to the light source object * * * * RETURN VALUE: * * int: FALSE, if viewer do not see. * *****************************************************************************/ static int IsPolySelfShadowed(IPPolygonStruct *Poly, RealType lt, LightStruct *l) { IPVertexStruct *v; RealType t = IS_VIEWER_POINT() ? PLANE_EQ_EVAL(Poly -> Plane, Context.Viewer) : DOT_PROD(Poly -> Plane, Context.Viewer); ASSERT((l -> type == POINT_LIGHT) || (l -> type == VECTOR_LIGHT)); if ((t < IRIT_EPS) == (lt < IRIT_EPS)) { /* Can`t be self shadowed. */ return FALSE; } /* Check that each vertex of the candidate satisfies. */ if (IS_VIEWER_POINT()) for (v = Poly -> PVertex; v; v = v -> Pnext) { VectorType Sight; VectorType Light; PT_SUB(Sight, Context.Viewer, v -> Coord); /* PT_NORMALIZE(Sight); */ /* We use the direction only. */ if (l -> type == POINT_LIGHT) { PT_SUB(Light, l -> where, v -> Coord); } else PT_COPY(Light, l -> where); if ((DOT_PROD(Sight, v -> Normal) < IRIT_EPS) == (DOT_PROD(Light, v -> Normal) < IRIT_EPS)) return FALSE; } else for (v = Poly -> PVertex; v; v = v -> Pnext) { VectorType Light; if (l -> type == POINT_LIGHT) { PT_SUB(Light, l -> where, v -> Coord); } else PT_COPY(Light, l -> where); if ((DOT_PROD(Context.Viewer, v -> Normal) < IRIT_EPS) == (DOT_PROD(Light, v -> Normal) < IRIT_EPS)) return FALSE; } return TRUE; } /***************************************************************************** * DESCRIPTION: * * Aux. function for PrspSeparationInit. Gets box corner coordinates in * * squared form (x*abs(x)) and determines if projection of that box on * * the unit sphere results in larger box in certain dimension (cause of * * intersection of box edges with coordinate planes). On the last case * * box dimension is updated. * * * * PARAMETERS: * * Dim: IN, dimension to check and update * * ptMin: IN OUT, minimal values of the box dimensions * * ptMax: IN OUT, maximal values of the box dimensions * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PrspAdjustBBoxAux(unsigned int Dim, PointType ptMin, PointType ptMax) { unsigned int Dim1 = (Dim + 1) % 3, /* Get next dimension. */ Dim2 = (Dim + 2) % 3; /* Get prev dimension. */ int FlagAdjustXbyY = ((ptMax[Dim1] < 0.0) != (ptMin[Dim1] < 0.0)), FlagAdjustXbyZ = ((ptMax[Dim2] < 0.0) != (ptMin[Dim2] < 0.0)); if (!FlagAdjustXbyY && !FlagAdjustXbyZ) return; /* Note: all pt... are abs(t) * t values. */ if (FlagAdjustXbyY && FlagAdjustXbyZ) /* Line OX intersect YZ flat. */ if (ptMax[Dim] > 0) { ptMax[Dim] = 1; if (ptMin[Dim] <= 0) ptMin[Dim] = -1; } else /* Maximum is in negative volume, so adjust minimum only. */ ptMin[Dim] = -1; else if (FlagAdjustXbyY) /* Hole box is in one of Z volumes. */ if (ptMin[Dim2] >= 0) /* Hole box is in positive Z volume. */ if (ptMax[Dim] > 0) { ptMax[Dim] /= (ptMax[Dim] + ptMin[Dim2]); if (ptMin[Dim] <= 0) ptMin[Dim] /= (-ptMin[Dim] + ptMin[Dim2]); } else ptMin[Dim] /= (-ptMin[Dim] + ptMin[Dim2]); else if (ptMax[Dim] > 0) { ptMax[Dim] /= (ptMax[Dim] - ptMax[Dim2]); if (ptMin[Dim] <= 0) ptMin[Dim] /= (-ptMin[Dim] - ptMax[Dim2]); } else ptMin[Dim] /= (-ptMin[Dim] - ptMax[Dim2]); else if (ptMin[Dim1] >= 0) /* Hole box is in positive Y volume. */ if (ptMax[Dim] > 0) { ptMax[Dim] /= (ptMax[Dim] + ptMin[Dim1]); if (ptMin[Dim] <= 0) ptMin[Dim] /= (-ptMin[Dim] + ptMin[Dim1]); } else ptMin[Dim] /= (-ptMin[Dim] + ptMin[Dim1]); else if (ptMax[Dim] > 0) { /* Hole box is in negative Y volume. */ ptMax[Dim] /= (ptMax[Dim] - ptMax[Dim1]); if (ptMin[Dim] <= 0) ptMin[Dim] /= (-ptMin[Dim] - ptMax[Dim1]); } else ptMin[Dim] /= (-ptMin[Dim] - ptMax[Dim1]); } /***************************************************************************** * DESCRIPTION: * * Separation is a process which determines for 2 polygons if there exists * * a possibility for the second to cast the shadow on the first. We imple- * * ment that algorithm by two steps - initialization and pairing. That rou- * * tine has Prsp prefix, which stays for POINT_LIGHT light source and con- * * sequently for perspective projection of shadows model. For all polygons * * it detrmines self shadowed or always lit attribute, and bounding box of * * polygon projection on unit sphere in squared coordinates (x*abs(x)). Al- * * gorithm is adopted from "Algorithm for Producing Half Tone Computer Gra- * * phics" in Spring Joint Computer Conference, 1970, p.1-9. * * Assumes light source of POINT_LIGHT type, plane equation updated after * * all coordinate transformations. * * * * PARAMETERS: * * f: IN OUT, list of flat objects (OUT per node in list) * * Light: IN, pointer to Light source * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PrspSeparationInit(FlatStruct *f, LightStruct *Light) { RealType *l = Light -> where; ASSERT(Light -> type == POINT_LIGHT); for (; f != NULL; f = f -> next) { SeparateInfoStruct *i = f -> info; IPPolygonStruct *Poly = f -> poly; if (APX_ZERO(i -> lt = PLANE_EQ_EVAL(Poly -> Plane, l))) POOL_ALWAYS_LIT(f -> vPool); else { IPVertexStruct *v = Poly -> PVertex; RealType *PtMin = i -> ptMin, *PtMax = i -> ptMax; PointType pt; RealType d; /* For efficiency reasons do one step before loop. */ PT_SUB(pt, v -> Coord, l); d = SQR(pt[X]) + SQR(pt[Y]) + SQR(pt[Z]); PtMin[X] = PtMax[X] = fabs(pt[X]) * pt[X] / d; PtMin[Y] = PtMax[Y] = fabs(pt[Y]) * pt[Y] / d; PtMin[Z] = PtMax[Z] = fabs(pt[Z]) * pt[Z] / d; i -> dMax = i -> dMin = d; for (v = v -> Pnext; v; v = v -> Pnext) { PT_SUB(pt, v -> Coord, l); d = SQR(pt[X]) + SQR(pt[Y]) + SQR(pt[Z]); pt[X] = fabs(pt[X]) * pt[X] / d; pt[Y] = fabs(pt[Y]) * pt[Y] / d; pt[Z] = fabs(pt[Z]) * pt[Z] / d; MAXM(PtMax[X], pt[X]); MINM(PtMin[X], pt[X]); MAXM(PtMax[Y], pt[Y]); MINM(PtMin[Y], pt[Y]); MAXM(PtMax[Z], pt[Z]); MINM(PtMin[Z], pt[Z]); MAXM(i -> dMax, d); MINM(i -> dMin, d); } /* Bounding box is determined. */ /* Adjust its size against X, Y, Z dimensions. */ PrspAdjustBBoxAux(X, i -> ptMin, i -> ptMax); PrspAdjustBBoxAux(Y, i -> ptMin, i -> ptMax); PrspAdjustBBoxAux(Z, i -> ptMin, i -> ptMax); /* Mark self shadowed polygons. */ if (IsPolySelfShadowed(Poly, i -> lt, Light)) POOL_SELF_SHADOWED(f -> vPool); } } } /***************************************************************************** * DESCRIPTION: * * Routine for the pairing part of separation process. It uses data built * * in init part (in particular bounding box dimensions) to check for the * * possibility of one bounding box shadow to be casted on the other. * * Assumes PrspSeparationInit was called successfuly on both polygons. * * * * PARAMETERS: * * p: IN, pointer to the first flat object * * f: IN, pointer to the second flat object * * * * RETURN VALUE: * * int: FALSE, if shadow is possible. * *****************************************************************************/ static int IsSeparatedOnSphere(FlatStruct *p, FlatStruct *f) { RealType *PtMinP = p -> info -> ptMin, *PtMaxP = p -> info -> ptMax, *PtMinF = f -> info -> ptMin, *PtMaxF = f -> info -> ptMax; return (p -> info -> dMax <= f -> info -> dMin) || IS_SEPARATE_ON_DIM(X, PtMinP, PtMaxP, PtMinF, PtMaxF) || IS_SEPARATE_ON_DIM(Y, PtMinP, PtMaxP, PtMinF, PtMaxF) || IS_SEPARATE_ON_DIM(Z, PtMinP, PtMaxP, PtMinF, PtMaxF); } /***************************************************************************** * DESCRIPTION: * * Separation is a process which determines for 2 polygons if there exists * * a possibility for the second to cast the shadow on the first. We imple- * * ment that algorithm by two steps - initialization and pairing. That rou- * * tine has Parl prefix, which stays for VECTOR_LIGHT light source and con- * * sequently for parallel projection model of shadows. For all polygons * * it detrmines self shadowed or always lit attribute, and bounding box of * * polygon projection on the plane normal to the light vector. * * Assumes light source of VECTOR_LIGHT type, plane equation updated after * * all coordinate transformations, light direction is to the light source. * * * * PARAMETERS: * * f: IN OUT, list of flat objects (OUT per node in list) * * LtSrc: IN, pointer to light source * * * * RETURN VALUE: * * void * *****************************************************************************/ static void ParlSeparationInit(FlatStruct *f, LightStruct *LtSrc) { PointType mX, mY, mZ; RealType *l = LtSrc -> where, ln = sqrt(SQR(l[X]) + SQR(l[Y])); /* Initialize rotation matrix. */ if (!APX_ZERO(ln)) { mX[X] = l[Y] / ln; mX[Y] = -l[X] / ln; mX[Z] = 0.0; mY[X] = l[X] * l[Z] / ln; mY[Y] = l[Y] * l[Z] / ln; mY[Z] = -ln; mZ[X] = l[X]; mZ[Y] = l[Y]; mZ[Z] = l[Z]; } else { /* Already {0, 0, +-1} - make absolute matrix only. */ mX[X] = l[Z]; mX[Y] = 0.0; mX[Z] = 0.0; mY[X] = 0.0; mY[Y] = l[Z]; mY[Z] = 0.0; mZ[X] = 0.0; mZ[Y] = 0.0; mZ[Z] = l[Z]; } for ( ; f != NULL; f = f -> next) { IPPolygonStruct *Poly = f -> poly; SeparateInfoStruct *i = f -> info; if (APX_ZERO(i -> lt = DOT_PROD(Poly -> Plane, l))) POOL_ALWAYS_LIT(f -> vPool); else { /* Rotate coord.sys. to make <-l> vector (0, 0, 1) */ /* and set bounding box. */ RealType *PtMin = i -> ptMin, *PtMax = i -> ptMax; IPVertexStruct *v; PtMin[X] = PtMin[Y] = PtMin[Z] = IRIT_INFNTY; PtMax[X] = PtMax[Y] = PtMax[Z] = -IRIT_INFNTY; for (v = f -> poly -> PVertex; v; v = v -> Pnext) { RealType x = DOT_PROD(v -> Coord, mX), y = DOT_PROD(v -> Coord, mY), z = DOT_PROD(v -> Coord, mZ); MINM(PtMin[X], x); MAXM(PtMax[X], x); MINM(PtMin[Y], y); MAXM(PtMax[Y], y); MINM(PtMin[Z], z); MAXM(PtMax[Z], z); } /* Mark selfshadowed polygons. */ if (IsPolySelfShadowed(Poly, i -> lt, LtSrc)) { POOL_SELF_SHADOWED(f -> vPool); } } } } /***************************************************************************** * DESCRIPTION: * * Routine for the pairing part of separation process. It uses data built * * in init part (in particular bounding box dimensions) to check for the * * possibility of one bounding box shadow to be casted on the other. * * Assumes ParlSeparationInit was called successfuly on both polygons. * * * * PARAMETERS: * * p: IN, pointer to the first flat object * * f: IN, pointer to the second flat object * * * * RETURN VALUE: * * int: FALSE, if shadow is possible. * *****************************************************************************/ static int IsSeparatedOnPlane(FlatStruct *p, FlatStruct *f) { RealType *PtMinP = p -> info -> ptMin, *PtMaxP = p -> info -> ptMax, *PtMinF = f -> info -> ptMin, *PtMaxF = f -> info -> ptMax; return (PtMinP[Z] >= PtMaxF[Z]) || IS_SEPARATE_ON_DIM(X, PtMinP, PtMaxP, PtMinF, PtMaxF) || IS_SEPARATE_ON_DIM(Y, PtMinP, PtMaxP, PtMinF, PtMaxF); } /***************************************************************************** * DESCRIPTION: * * We implemet algorithm for cutting off non self intersecting polygon by * * plane. That process generaly may produce several new polygons. Implemen- * * tation of the algoritm consists of initialization and cutting routines. * * That one is initialization roitine which constructs PolyPlaneSectInfo * * object to represent cutting of flat f by plane of flat p. * * PARAMETERS: * * s: OUT, pointer to PolyPlaneSectInfo object * * p: IN, pointer to the flat * * f: IN, pointer to the cuttee flat * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PolyCuttingInit(PolyPlaneSectInfoStruct *s, FlatStruct *p, FlatStruct *f) { VertexLinkStruct *i = s -> vPoly; IPVertexStruct *v; for (v = f -> poly -> PVertex; v; v = v -> Pnext, ++i) PT_COPY(i -> pt, v -> Coord); PT_COPY(i -> pt, f -> poly -> PVertex -> Coord); s -> vPolyEnd = i + 1; s -> flat = p; } /***************************************************************************** * DESCRIPTION: * * Sort routine callback comparing two VertexLink objects by X ccordinate. * * Aux. routine for PolyCutByPlane. * * * * PARAMETERS: * * a1: IN, pointer to the VertexLink object * * a2: IN, pointer to the VertexLink object * * * * RETURN VALUE: * * int: as defined for the qsort routine callback * *****************************************************************************/ static int VertexLinkXCmp(const void *a1, const void *a2) { return (int) (((VertexLinkStruct *) a1) -> pt[X] - ((VertexLinkStruct *) a2) -> pt[X]); } /***************************************************************************** * DESCRIPTION: * * Sort routine callback comparing two VertexLink objects by Y cordinate. * * Aux. routine for PolyCutByPlane. * * PARAMETERS: * * a1: IN, pointer to the VertexLink object * * a2: IN, pointer to the VertexLink object * * * * RETURN VALUE: * * int: as defined for the qsort routine callback * *****************************************************************************/ static int VertexLinkYCmp(const void *a1, const void *a2) { return (int) (((VertexLinkStruct *) a1) -> pt[Y] - ((VertexLinkStruct *) a2) -> pt[Y]); } /***************************************************************************** * DESCRIPTION: * * Realy cutting off part of the algorithm. It uses PolyPlaneSectInfo object* * constructed in init part and fills it memory pool with linked lists of * * newly created polygons (results of cutting algorithm) vertices. * * * * PARAMETERS: * * p: IN, cutting plane * * Side: IN, 1 if light is from -side of plane equation, -1 otherwise * * i: IN OUT, pointer to PolyPLaneSectInfo object * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PolyCutByPlane(PolyPlaneSectInfoStruct *i, int Side) { VertexLinkStruct *vp = i -> vPoly, *a = i -> vAbove, *c = i -> vCross; RealType t, *p = i -> flat -> poly -> Plane;/* Get pointer to plane coefficients.*/ int FAbove; PT_COPY(a -> pt, vp -> pt); t = PLANE_EQ_EVAL(p, vp -> pt); a -> t = APX_ABOVE(t); a -> next = NULL; FAbove = IS_ABOVE(a -> t, Side); /* Current is above the plane. */ for (++vp; vp < i -> vPolyEnd; ++vp) { t = PLANE_EQ_EVAL(p, vp -> pt); APX_ABOVE(t); if (IS_ABOVE(t, Side)) if (FAbove) { /* Both vertices are above. */ a -> next = a + 1; /* Get next above vertex link. */ ++a; } else { /* Cross from underneath above. */ RealType Tblend = a -> t / (a -> t - t); PT_BLEND(c -> pt, vp -> pt, a -> pt, Tblend); c++ -> next = a; /* "a" points to the current. */ FAbove = 1; } else if (FAbove) { /* Cross from above underneath. */ RealType Tblend = a -> t / (a -> t - t); PT_BLEND(c -> pt, vp -> pt, a -> pt, Tblend); c -> back = a; c++ -> next = NULL; ++a; FAbove = 0; } PT_COPY(a -> pt, vp -> pt); a -> t = t; a -> next = NULL; } i -> vAboveEnd = (a += FAbove); i -> vCrossEnd = c; if (a - i -> vAbove) { if (i -> vCrossEnd - (c = i -> vCross) > 2) { int fYsort = ABS(c[0].pt[Y] - c[1].pt[Y]) > ABS(c[0].pt[X] - c[1].pt[X]); qsort(c, i -> vCrossEnd - c, sizeof(VertexLinkStruct), fYsort ? VertexLinkYCmp : VertexLinkXCmp); } for (; c < i -> vCrossEnd; c += 2) { if (c -> next) { (c + 1) -> next = c; (c + 1) -> back -> next = (c + 1); } else { c -> next = c + 1; c -> back -> next = c; } } } } /***************************************************************************** * DESCRIPTION: * * Given PolyPlaneSectInfo object iterates on each newly created polygon * * and projects it on the cutting plane. By the way PlaneSectInfo object * * linked list for the polygon is deleted. * * * * PARAMETERS: * * s: IN OUT , pointer to the PolyPlaneSectInfo object * * lt: IN, plane equation value for the light source e * * l: IN, light source coordinates * * Projector: IN, callback for the vertex projector routine. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PolyAboveSectionProject(PolyPlaneSectInfoStruct *s, RealType lt, PointType l, ProjectorProcType Projector) { ShadowEdgePoolStruct *Pool = s -> flat -> vPool; VertexLinkStruct *j, *next; ShadowEdgeStruct *Start; for (j = s -> vAbove; j < s -> vAboveEnd; ++j) { (*Projector) (j, lt, l); MatMultVecby4by4(j -> pt, j -> pt, Context.ViewMat); } for (j = s -> vCross; j < s -> vCrossEnd; ++j) MatMultVecby4by4(j -> pt, j -> pt, Context.ViewMat); for (j = s -> vAbove; j < s -> vAboveEnd;) { for (Start = Pool -> PEnd; j -> next; j = next) { next = j -> next; j -> next = NULL; if (!ShadowEdgeInit(POOL_ALLOC_ENTRY(Pool), s -> flat, j -> pt, next -> pt)) POOL_FREE_ENTRY(Pool); } if (Pool -> PEnd > Start) ShadowEdgeLeftRightOrder(Start, Pool -> PEnd); /* Find beginning of the next polygon. */ for (j = s -> vAbove; (j < s -> vAboveEnd) && (j -> next == NULL); ++j); } } /***************************************************************************** * DESCRIPTION: * * Callback routine for PolyAboveSectionProject. Projects vertex on to the * * plane above which a specific vertex was cutted off. Uses perspective. * * * * PARAMETERS: * * j: IN OUT, pointer to the vertex object * * lt: IN, plane equation value for the light source coordinates * * l: IN, light source coordinates * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PrspProjector(VertexLinkStruct *j, RealType lt, PointType l) { RealType tl = j -> t / (j -> t - lt); j -> pt[X] += tl * (l[X] - j -> pt[X]); j -> pt[Y] += tl * (l[Y] - j -> pt[Y]); j -> pt[Z] += tl * (l[Z] - j -> pt[Z]); } /***************************************************************************** * DESCRIPTION: * * Callback routine for PolyAboveSectionProject. Projects vertex on to the * * plane above which a specific vertex was cutted off. Uses parallel model. * * * * PARAMETERS: * * j: IN OUT, pointer to the vertex object * * lt: IN, plane equation value for the light source coordinates * * l: IN, light source coordinates * * * * RETURN VALUE: * * void * *****************************************************************************/ static void ParlProjector(VertexLinkStruct *j, RealType lt, PointType l) { RealType tl = j -> t / lt; j -> pt[X] += tl * l[X]; j -> pt[Y] += tl * l[Y]; j -> pt[Z] += tl * l[Z]; } /***************************************************************************** * DESCRIPTION: * * Projects using perspective model polygon specified by the flat f onto the* * polygon specified by the flat p. (That is creates shadow describing data * * structure for the p flat). Assumes lt != 0. * * * * PARAMETERS: * * p: IN, pointer to the flat object on which prolection is done. * * f: IN, pointer to flat object which is projected * * lt: IN, polygon p plane equation value for the light source * * l: IN, light source coordinates * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PolyPrspProject(FlatStruct *p, FlatStruct *f, RealType lt, PointType l) { VertexLinkStruct *i, *j, *PNext, *PPolyEnd; RealType D = p -> poly -> Plane[3]; ASSERT(!APX_ZERO(lt)); PolyCuttingInit(&Sect, p, f); p -> poly -> Plane[3] -= lt + LT_DELTA(lt); PolyCutByPlane(&Sect, lt > 0 ? -1 : 1); p -> poly -> Plane[3] = D; for (j = Sect.vAbove, i = Sect.vPoly; j < Sect.vAboveEnd;) { for (; j; j = PNext, ++i) { PT_COPY(i -> pt, j -> pt); i -> next = i + 1; PNext = j -> next; j -> next = NULL; } (i - 1) -> next = NULL; /* Close polygon. */ /* Find beginning of the PNext polygon. */ for (j = Sect.vAbove; (j < Sect.vAboveEnd) && !j -> next; ++j); } PPolyEnd = i; for (i = Sect.vPoly; i < PPolyEnd;) { for (Sect.vPoly = i; i -> next; ++i); /* Find end of the polygon. */ Sect.vPolyEnd = ++i; PolyCutByPlane(&Sect, lt > 0 ? 1 : -1); PolyAboveSectionProject(&Sect, lt, l, PrspProjector); } } /***************************************************************************** * DESCRIPTION: * * Projects using parallel model polygon specified by the flat f onto the * * polygon specified by the flat p. (That is creates shadow describing data * * structure for the p flat). Assumes lt != 0, light vector points to the * * light source direction. * * * * PARAMETERS: * * p: IN, pointer to the flat object on which prolection is done. * * f: IN, pointer to flat object which is projected * * lt: IN, polygon p plane equation value for the light source * * l: IN, light source coordinates * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PolyParlProject(FlatStruct *p, FlatStruct *f, RealType lt, VectorType l) { ASSERT(!APX_ZERO(lt)); PolyCuttingInit(&Sect, p, f); PolyCutByPlane(&Sect, -lt < 0 ? 1 : -1); PolyAboveSectionProject(&Sect, -lt, l, ParlProjector); } /***************************************************************************** * DESCRIPTION: * * For each polygon builds pool of shadows casted by all others. * * Assumes that for each polygon SeparateInfo and ShadowEdgePool are * * allocated. * * * * PARAMETERS: * * Flats: IN, linked list of the flat objects (polygon representation) * * l: IN, pointer to the light source object * * * * RETURN VALUE: * * void * *****************************************************************************/ static void ShadowsEval(FlatStruct *Flats, LightStruct *l) { TestSeparationProcType IsSeparated = l -> descriptor -> IsSeparated; ProjectPolygonProcType ProjectFlat = l -> descriptor -> ProjectPoly; FlatStruct *p, *f; PREPROCESSING_MESSAGE(); (*l -> descriptor -> SeparationInit)(Flats, l); PAIRING_MESSAGE(); /* Loop over shadowed polygons. */ for (p = Flats; p != NULL; p = p -> next) { if (IS_POOL_MARKED(p -> vPool)) continue; PoolInit(p -> vPool, POOL_OPTIMAL_SIZE(nEdgesTotal)); /* Loop over shadow casting polygons. */ for (f = Flats; f != p; f = f -> next) if (!IS_POOL_ALWAYS_LIT(f -> vPool) && !(*IsSeparated)(p, f)) (*ProjectFlat)(p, f, p -> info -> lt, l -> where); /* Skip auto processing and ahead. */ for (f = f -> next; f != NULL; f = f -> next) if (!IS_POOL_ALWAYS_LIT(f -> vPool) && !(*IsSeparated)(p, f)) (*ProjectFlat)(p, f, p -> info -> lt, l -> where); PoolAdjust(p -> vPool); } } /***************************************************************************** * DESCRIPTION: M * For each flat object in the list creates data structures describing M * shadows on it from each light source. M * Assumes maxEdges and lights objects constructed. M * * * PARAMETERS: M * Flats: IN OUT, flat objects linked list. M * * * RETURN VALUE: M * FlatStruct *: the same flat list. M * * * KEYWORDS: M * GatherShadows, shadows M *****************************************************************************/ FlatStruct *GatherShadows(FlatStruct *Flats) { LightStruct *l; FlatStruct *f; if (!Options.Shadows) return Flats; /* Dummy call. */ GATHERING_SHADOWS_MESSAGE(); /* Initialize shadow`s part of the light source descriptor table. */ Context.PointLightDescriptor.SeparationInit = PrspSeparationInit; Context.PointLightDescriptor.IsSeparated = IsSeparatedOnSphere; Context.PointLightDescriptor.ProjectPoly = PolyPrspProject; Context.VectorLightDescriptor.SeparationInit = ParlSeparationInit; Context.VectorLightDescriptor.IsSeparated = IsSeparatedOnPlane; Context.VectorLightDescriptor.ProjectPoly = PolyParlProject; /* Allocate projection algorithm data structures. */ Sect.vPoly = MALLOC(VertexLinkStruct, 8 * (Context.MaxEdges + 1)); Sect.vAbove = Sect.vPoly + 4 * (Context.MaxEdges + 1); Sect.vCross = Sect.vAbove + 2 * (Context.MaxEdges + 1); for (f = Flats; f != NULL; nEdgesTotal += f -> nEdges, f = f -> next) { IPVertexStruct *v; /* Restore vertex coordinate to object space. Actualy */ /* we do not use them later but in that module. */ for (v = f -> poly -> PVertex; v; v = v -> Pnext) MatMultVecby4by4(v -> Coord, v -> Coord, Context.InvMat); f -> info = MALLOC(SeparateInfoStruct, 1); f -> vPool = MALLOC(ShadowEdgePoolStruct, Context.Lights.n); } /* Process with pairing. */ for (l = Context.Lights.src; l < Context.Lights.src+Context.Lights.n; ++l) { if (l -> shadow) ShadowsEval(Flats, l); for (f = Flats; f != NULL; ++f -> vPool, f = f -> next); /* Advance light pool. */ } /* Restore pool pointer. */ for (f = Flats; f != NULL; f -> vPool -= Context.Lights.n, f = f -> next); return Flats; } /***************************************************************************** * DESCRIPTION: M * Determines if shadow is casted on (x, yScanLine) point, using data struc-M * tures evaluated in preprocessing phase. M * Assumes that ShadowLineInit is called before calling that one for every M * new yScanLine value. For the same value of yScanLine shadow pool "PMax" M * and "NInside" fields should be preserved. M * ShadowLineInit and ShadowLineIncr represent brackets for IsInShadow callsM * * * PARAMETERS: M * f: IN, pointer to the testee flat. M * LightIndex: IN, index of the light source we deal with currently. M * x: IN, pixel position on the current yScanLine. M * * * RETURN VALUE: M * int: zero if no shadow is casted on the pixel. M * * * KEYWORDS: M * IsInShadow, GatherShadows, ShadowLineInit, shadows M *****************************************************************************/ int IsInShadow(FlatStruct *f, unsigned int LightIndex, unsigned int x) { ShadowEdgePoolStruct *p = &f -> vPool[LightIndex]; ShadowEdgeStruct *a; ASSERT(Options.Shadows && Context.Lights.src[LightIndex].shadow); if (!IS_POOL_VALID(p) || IS_POOL_ALWAYS_LIT(p)) return 0; if (IS_POOL_SELF_SHADOWED(p)) return 1; for (a = p -> PMax; (a < p -> Waiting) && ((int) x >= (int) a -> x); ++a) p -> NInside += a -> flag; POOL_SET(p, a); return p -> NInside; } /***************************************************************************** * DESCRIPTION: M * Processes the flat shadows data pool containing polygons (represented by M * shadow edges) by activating edges starting at "y" and sorting active sub-M * list by X value. That routine should be called for each successive "y" M * value, as a result "PMax" and "NInside" fields of the flat's pool record M * are initialized for the next scan line processing. M * ShadowLineInit and ShadowLineIncr represent brackets for IsInShadow callsM * * * PARAMETERS: M * f: IN, pointer to the flat object M * y: IN, current scan line number. M * * * RETURN VALUE: M * void M * * * KEYWORDS: M * ShadowLineInit, ShadowLineIncr, shadows M *****************************************************************************/ void ShadowLineInit(FlatStruct *f, unsigned int y) { unsigned int i; for (i = 0; i < Context.Lights.n; ++i) { ShadowEdgePoolStruct *p; ShadowEdgeStruct *e; if (!Context.Lights.src[i].shadow) continue; p = &f -> vPool[i]; if (!IS_POOL_VALID(p) || IS_POOL_ALWAYS_LIT(p) || IS_POOL_SELF_SHADOWED(p)) continue; for (e = p -> Waiting; e < (CPShadowEdgeType) p -> PEnd; ++e) if (e -> yMax - e -> dy <= (int)y) /* y_min starts at y. */ PoolActivate(p, e); qsort(p -> Active, p -> Waiting - p -> Active, sizeof *e, ShadowEdgeCmp); POOL_RESET(p); p -> NInside = 0; } } /***************************************************************************** * DESCRIPTION: M * Deletes all inactive edges (maximal y is less then the y of the next M * scan line) and advances all fields of active edges (interpolation M * data) to the next scan line conformance. M * Assumes ShadowLineInit is called before that one. M * ShadowLineInit and ShadowLineIncr represent brackets for IsInShadow M * calls. M * * * PARAMETERS: M * f: IN, pointer to the flat object containing shadows data sructure M * y: IN, next scan line value. M * * * RETURN VALUE: M * void M * * * KEYWORDS: M * ShadowLineIncr, ShadowLineInit M *****************************************************************************/ void ShadowLineIncr(FlatStruct *f, unsigned int y) { unsigned int i; for (i = 0; i < Context.Lights.n; ++i) { ShadowEdgePoolStruct *p; ShadowEdgeStruct *e; if (!Context.Lights.src[i].shadow) continue; p = &f -> vPool[i]; if (!IS_POOL_VALID(p) || IS_POOL_ALWAYS_LIT(p) || IS_POOL_SELF_SHADOWED(p)) continue; /* ++y later means [ .. ) rule. */ for (e = p -> Active; e < (CPShadowEdgeType) p -> Waiting; ++e) { if (e -> yMax <= (int)y) PoolKill(p, e); else { int Sign = SIGN(e -> dx), Numerator = ABS(e -> dx), Denumerator = e -> dy; if (Numerator < Denumerator) /* Slope > 1. */ e -> inc += Numerator; else { /* Slope <= 1. */ e -> x += e -> dx / Denumerator; e -> inc += Numerator % Denumerator; } if (e -> inc > Denumerator) { e -> x += Sign; e -> inc -= Denumerator; } } } } }