/****************************************************************************** * 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 CagdBType GlblTightBBox = FALSE; static CagdRType *GlblNewKVs = NULL; /***************************************************************************** * DESCRIPTION: M * Computes a bounding box for a freeform curve. M * * * PARAMETERS: M * TightBBox: TRUE for tight bbox on freeform curves and surfaces, FALSE M * for loose bbox that is derived using the control poly/mesh. M * * * RETURN VALUE: M * int: old value. M * * * SEE ALSO: M * CagdCrvBBox, CagdSrfBBox 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 * 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 M * * * KEYWORDS: M * CagdCrvBBox, bbox, bounding box M *****************************************************************************/ void CagdCrvBBox(CagdCrvStruct *Crv, CagdBBoxStruct *BBox) { int Length; CagdCrvStruct *E3Crv; 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); } E3Crv = CagdCoerceCrvTo(Crv, CAGD_PT_E3_TYPE); Length = E3Crv -> Length; CagdPointsBBox(E3Crv -> Points, Length, BBox); CagdCrvFree(E3Crv); 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 M * * * KEYWORDS: M * CagdSrfBBox, bbox, bounding box M *****************************************************************************/ void CagdSrfBBox(CagdSrfStruct *Srf, CagdBBoxStruct *BBox) { int Length; CagdSrfStruct *E3Srf; 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); } E3Srf = CagdCoerceSrfTo(Srf, CAGD_PT_E3_TYPE); Length = E3Srf -> ULength * E3Srf -> VLength; CagdPointsBBox(E3Srf -> Points, Length, BBox); CagdSrfFree(E3Srf); 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) { int i; CAGD_RESET_BBOX(BBox); for (i = 0; i < Length; i++) { if (BBox -> Min[0] > Points[X][i]) BBox -> Min[0] = Points[X][i]; if (BBox -> Min[1] > Points[Y][i]) BBox -> Min[1] = Points[Y][i]; if (BBox -> Min[2] > Points[Z][i]) BBox -> Min[2] = Points[Z][i]; if (BBox -> Max[0] < Points[X][i]) BBox -> Max[0] = Points[X][i]; if (BBox -> Max[1] < Points[Y][i]) BBox -> Max[1] = Points[Y][i]; if (BBox -> Max[2] < Points[Z][i]) BBox -> Max[2] = Points[Z][i]; } } /***************************************************************************** * 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; } }