/****************************************************************************** * CagdBbox.c - Handle freeform cuves and surfaces bounding boxes. * ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by Gershon Elber, Jan. 92. * ******************************************************************************/ #include "cagd_loc.h" #define BBOX_CRV_KNOTS 20 #define BBOX_SRF_KNOTS 20 STATIC_DATA CagdBType GlblIgnoreNonPosWeightBBox = FALSE, GlblTightBBox = FALSE; STATIC_DATA CagdRType *GlblNewKVs = NULL; /***************************************************************************** * DESCRIPTION: M * Enforce the computation of a tighter bounding box for a freeform. M * * * PARAMETERS: M * TightBBox: TRUE for tight bbox on freeforms, FALSE for, simpler, M * looser bbox that is derived using the control poly/mesh. M * * * RETURN VALUE: M * CagdBType: old value. M * * * SEE ALSO: M * CagdCrvBBox, CagdSrfBBox, CagdIgnoreNonPosWeightBBox M * * * KEYWORDS: M * CagdTightBBox, bbox, bounding box M *****************************************************************************/ CagdBType CagdTightBBox(CagdBType TightBBox) { CagdBType OldVal = GlblTightBBox; GlblTightBBox = TightBBox; if (TightBBox && GlblNewKVs == NULL) GlblNewKVs = (CagdRType *) IritMalloc(MAX(BBOX_CRV_KNOTS, BBOX_SRF_KNOTS) * sizeof(CagdRType)); return OldVal; } /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a freeform curve. M * * * PARAMETERS: M * IgnoreNonPosWeightBBox: TRUE to ignore negative and zero weight M * control points in the bounding box computation. M * * * RETURN VALUE: M * CagdBType: old value. M * * * SEE ALSO: M * CagdCrvBBox, CagdSrfBBox, CagdTightBBox M * * * KEYWORDS: M * CagdIgnoreNonPositiveWeightBBox, bbox, bounding box M *****************************************************************************/ CagdBType CagdIgnoreNonPosWeightBBox(CagdBType IgnoreNonPosWeightBBox) { CagdBType OldVal = GlblIgnoreNonPosWeightBBox; GlblIgnoreNonPosWeightBBox = IgnoreNonPosWeightBBox; return OldVal; } /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a freeform curve. M * * * PARAMETERS: M * Crv: To compute a bounding box for. M * BBox: Where bounding information is to be saved. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * CagdCrvListBBox, CagdSrfBBox, CagdTightBBox, CagdIgnoreNonPosWeightBBox M * * * KEYWORDS: M * CagdCrvBBox, bbox, bounding box M *****************************************************************************/ void CagdCrvBBox(CagdCrvStruct *Crv, CagdBBoxStruct *BBox) { if (GlblTightBBox && Crv -> Order > 2) { /* Refine crv before bbox test. */ CagdRType TMin, TMax, *KV = Crv -> KnotVector; int i, l = 0, KVLen = Crv -> Length + Crv -> Order; CagdCrvDomain(Crv, &TMin, &TMax); for (i = 0; i < BBOX_CRV_KNOTS; i++) { int j; CagdRType t = TMin + i * (TMax - TMin) / (BBOX_CRV_KNOTS - 1); if (CAGD_IS_BSPLINE_CRV(Crv)) { j = BspKnotLastIndexLE(KV, KVLen, t); if (!APX_EQ(KV[j], t)) GlblNewKVs[l++] = t; } else { GlblNewKVs[l++] = t; } } Crv = CagdCrvRefineAtParams(Crv, FALSE, GlblNewKVs, l); } CagdPointsBBox(Crv -> Points, Crv -> Length, BBox); if (GlblTightBBox && Crv -> Order > 2) CagdCrvFree(Crv); } /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a list of freeform curves. M * * * PARAMETERS: M * Crvs: To compute a bounding box for. M * BBox: Where bounding information is to be saved. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * CagdCrvBBox, CagdSrfBBox, CagdTightBBox M * * * KEYWORDS: M * CagdCrvListBBox, bbox, bounding box M *****************************************************************************/ void CagdCrvListBBox(CagdCrvStruct *Crvs, CagdBBoxStruct *BBox) { CAGD_RESET_BBOX(BBox); for ( ; Crvs != NULL; Crvs = Crvs -> Pnext) { CagdBBoxStruct TmpBBox; CagdCrvBBox(Crvs, &TmpBBox); CagdMergeBBox(BBox, &TmpBBox); } } /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a freeform surface. M * * * PARAMETERS: M * Srf: To compute a bounding box for. M * BBox: Where bounding information is to be saved. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * CagdCrvBBox, CagdSrfListBBox, CagdTightBBox, CagdIgnoreNonPosWeightBBox M * * * KEYWORDS: M * CagdSrfBBox, bbox, bounding box M *****************************************************************************/ void CagdSrfBBox(CagdSrfStruct *Srf, CagdBBoxStruct *BBox) { if (GlblTightBBox) { /* Refine the surface before bbox testing. */ CagdRType UMin, UMax, VMin, VMax, *KV = Srf -> UKnotVector; int i, l, KVLen = Srf -> ULength + Srf -> UOrder; CagdSrfStruct *AuxSrf; CagdSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax); for (i = l = 0; i < BBOX_SRF_KNOTS; i++) { int j; CagdRType u = UMin + i * (UMax - UMin) / (BBOX_SRF_KNOTS - 1); if (CAGD_IS_BSPLINE_SRF(Srf)) { j = BspKnotLastIndexLE(KV, KVLen, u); if (!APX_EQ(KV[j], u)) GlblNewKVs[l++] = u; } else { GlblNewKVs[l++] = u; } } AuxSrf = CagdSrfRefineAtParams(Srf, CAGD_CONST_U_DIR, FALSE, GlblNewKVs, l); KV = Srf -> VKnotVector; KVLen = Srf -> VLength + Srf -> VOrder; for (i = l = 0; i < BBOX_SRF_KNOTS; i++) { int j; CagdRType v = VMin + i * (VMax - VMin) / (BBOX_SRF_KNOTS - 1); if (CAGD_IS_BSPLINE_SRF(Srf)) { j = BspKnotLastIndexLE(KV, KVLen, v); if (!APX_EQ(KV[j], v)) GlblNewKVs[l++] = v; } else { GlblNewKVs[l++] = v; } } Srf = CagdSrfRefineAtParams(AuxSrf, CAGD_CONST_V_DIR, FALSE, GlblNewKVs, l); CagdSrfFree(AuxSrf); } CagdPointsBBox(Srf -> Points, Srf -> ULength * Srf -> VLength, BBox); if (GlblTightBBox) CagdSrfFree(Srf); } /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a list of freeform surfaces. M * * * PARAMETERS: M * Srfs: To compute a bounding box for. M * BBox: Where bounding information is to be saved. M * * * RETURN VALUE: M * void M * * * SEE ALSO: M * CagdCrvBBox, CagdSrfBBox, CagdTightBBox M * * * KEYWORDS: M * CagdSrfListBBox, bbox, bounding box M *****************************************************************************/ void CagdSrfListBBox(CagdSrfStruct *Srfs, CagdBBoxStruct *BBox) { CAGD_RESET_BBOX(BBox); for ( ; Srfs != NULL; Srfs = Srfs -> Pnext) { CagdBBoxStruct TmpBBox; CagdSrfBBox(Srfs, &TmpBBox); CagdMergeBBox(BBox, &TmpBBox); } } /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a set of control points. M * * * PARAMETERS: M * Points: To compute bounding box for. M * Length: Length of vectors of Points array. M * BBox: Where bounding information is to be saved. M * * * RETURN VALUE: M * void M * * * KEYWORDS: M * CagdPointsBBox, bbox, bounding box M *****************************************************************************/ void CagdPointsBBox(CagdRType **Points, int Length, CagdBBoxStruct *BBox) { CagdBType MixedWeightsSign = FALSE, FirstNegativeWeight = TRUE; int i, l; CAGD_RESET_BBOX(BBox); if (Points[0] != NULL) { for (l = 0; l < 3; l++) { CagdRType *R = Points[l + 1], *WR = Points[0]; if (R != NULL) { CagdRType Min = BBox -> Min[l], Max = BBox -> Max[l]; for (i = 0; i < Length; i++) { CagdRType RTmp; if (*WR <= 0.0) { if (FirstNegativeWeight) { /* Have both positive and negative weights? */ int j; CagdBType Positive = FALSE, Negative = FALSE; CagdRType *Weights = Points[0]; for (j = 0; j < Length; j++, Weights++) { if (*Weights > 0) Positive = TRUE; if (*Weights < 0) Negative = TRUE; } MixedWeightsSign = Positive && Negative; FirstNegativeWeight = FALSE; } if (*WR == 0.0 && *R != 0.0) { if (!GlblIgnoreNonPosWeightBBox) { if (*R > 0.0) Max = IRIT_INFNTY; else Min = -IRIT_INFNTY; } WR++; R++; continue; } if (*WR == 0.0 && *R == 0.0) { WR++; R++; continue; } else if (*WR < 0.0) { if (MixedWeightsSign) { /* Negative weights can explode! */ if (!GlblIgnoreNonPosWeightBBox) { Max = IRIT_LARGE; Min = -Max; } WR++; R++; continue; } else { /* Continue - all weights are negative! */ } } } RTmp = *R++ / *WR++; if (Min > RTmp) Min = RTmp; if (Max < RTmp) Max = RTmp; } BBox -> Min[l] = Min; BBox -> Max[l] = Max; } else { /* Points[l + 1] is not defined. */ BBox -> Min[l] = BBox -> Max[l] = 0.0; } } } else { for (l = 0; l < 3; l++) { CagdRType *R = Points[l + 1]; if (R != NULL) { CagdRType Min, Max; Min = Max = *R++; for (i = 1; i < Length; i++, R++) { if (Min > *R) Min = *R; if (Max < *R) Max = *R; } BBox -> Min[l] = Min; BBox -> Max[l] = Max; } else { /* Points[l + 1] is not defined. */ BBox -> Min[l] = BBox -> Max[l] = 0.0; } } } } /***************************************************************************** * DESCRIPTION: M * Merges (union) two bounding boxes into one, in place. M * * * PARAMETERS: M * DestBBox: One BBox operand as well as the result. M * SrcBBox: Second BBox operand. M * * * RETURN VALUE: M * void M * * * KEYWORDS: M * CagdMergeBBox, bbox, bounding box M *****************************************************************************/ void CagdMergeBBox(CagdBBoxStruct *DestBBox, CagdBBoxStruct *SrcBBox) { int i; for (i = 0; i < 3; i++) { if (DestBBox -> Min[i] > SrcBBox -> Min[i]) DestBBox -> Min[i] = SrcBBox -> Min[i]; if (DestBBox -> Max[i] < SrcBBox -> Max[i]) DestBBox -> Max[i] = SrcBBox -> Max[i]; } } /***************************************************************************** * DESCRIPTION: M * Computes a min max bound on a curve in a given axis. M * The curve is not coerced to anything and the given axis is tested M * directly where 0 is the W axis and 1, 2, 3 are the X, Y, Z etc. M * * * PARAMETERS: M * Crv: To test for minimum/maximum. M * Axis: 0 for W, 1 for X, 2 for Y etc. M * Min: Where minimum found value should be place. M * Max: Where maximum found value should be place. M * * * RETURN VALUE: M * void M * * * KEYWORDS: M * CagdCrvMinMax, bbox, bounding box, minimum, maximum M *****************************************************************************/ void CagdCrvMinMax(CagdCrvStruct *Crv, int Axis, CagdRType *Min, CagdRType *Max) { CagdBType IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv); int i, Length = Crv -> Length, MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType); CagdRType *Pts = Crv -> Points[Axis], *WPts = IsNotRational ? NULL : Crv -> Points[0]; if ((Axis == 0 && IsNotRational) || (Axis > MaxCoord)) CAGD_FATAL_ERROR(CAGD_ERR_WRONG_CRV); for (i = 0, *Min = IRIT_INFNTY, *Max = -IRIT_INFNTY; i < Length; i++) { CagdRType V = WPts ? Pts[i] / WPts[i] : Pts[i]; if (*Max < V) *Max = V; if (*Min > V) *Min = V; } } /***************************************************************************** * DESCRIPTION: M * Computes a min max bound on a surface in a given axis. M * The surface is not coerced to anything and the given axis is tested M * directly where 0 is the W axis and 1, 2, 3 are the X, Y, Z etc. M * * * PARAMETERS: M * Srf: To test for minimum/maximum. M * Axis: 0 for W, 1 for X, 2 for Y etc. M * Min: Where minimum found value should be place. M * Max: Where maximum found value should be place. M * * * RETURN VALUE: M * void M * * * KEYWORDS: M * CagdSrfMinMax, bbox, bounding box, minimum, maximum M *****************************************************************************/ void CagdSrfMinMax(CagdSrfStruct *Srf, int Axis, CagdRType *Min, CagdRType *Max) { CagdBType IsNotRational = !CAGD_IS_RATIONAL_SRF(Srf); int i, Length = Srf -> ULength * Srf -> VLength, MaxCoord = CAGD_NUM_OF_PT_COORD(Srf -> PType); CagdRType *Pts = Srf -> Points[Axis], *WPts = IsNotRational ? NULL : Srf -> Points[0]; if ((Axis == 0 && IsNotRational) || (Axis > MaxCoord)) CAGD_FATAL_ERROR(CAGD_ERR_WRONG_SRF); for (i = 0, *Min = IRIT_INFNTY, *Max = -IRIT_INFNTY; i < Length; i++) { CagdRType V = WPts ? Pts[i] / WPts[i] : Pts[i]; if (*Max < V) *Max = V; if (*Min > V) *Min = V; } }