/****************************************************************************** * BspKntRm.c - Knot removal for Bspline curves. * ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by: Alon Raviv Vec 0.1, July 1999. * ******************************************************************************/ #include "cagd_lib.h" #include "misc_lib.h" #include "symb_loc.h" #define RM_KNT_INFINITE_NORM 0 #ifdef DEBUG IRIT_SET_DEBUG_PARAMETER(_DebugRemoveKnots, FALSE); #endif /* DEBUG */ typedef struct { int KnotIndex; CagdRType Weight; } RmKntKnotWeightStruct; typedef struct { int *KnotsIndices; int Length; } RmKntRemoveKnotsStruct; static int RmKntKnotWeightComp(VoidPtr Element1, VoidPtr Element2); static int RmKntGetLowestInteriorIndex(CagdCrvStruct *Crv); static int RmKntGetHighestInteriorIndex(CagdCrvStruct *Crv); static int RmKntAreInteriorDifferentExterior(CagdCrvStruct *Crv); static int RmKntIsInteriorKnot(CagdCrvStruct *Crv, int Knot_index); static int RmKntGetInteriorKnotsNum(CagdCrvStruct *Crv); static CagdCtlPtStruct *RmKntAllocateSamplePoints(int SamplesNum, CagdPointType PointType); static int RmKntGetSampleIntervalStart(CagdCrvStruct *Crv); static int RmKntGetSampleIntervalEnd(CagdCrvStruct *Crv); static int RmKntGetKnotMultiplicity(CagdCrvStruct *Crv, int KnotIndex, int IsLeftMultiplicity); static CagdCtlPtStruct *RmKntSample(CagdCrvStruct *Crv, CagdRType *SamplesLocations, int SamplesNum); static CagdRType *RmKntGetSamplingLocations(CagdCrvStruct *Crv, int LocationsNum); static CagdRType *RmKntGetInterpolantKV(CagdCrvStruct *OriginalCrv, int *KnotIndices, int KnotsNum); static CagdCrvStruct *RmKntRefineInterpolant(CagdCrvStruct *Interpolant, CagdRType KnotValue, int Multiplicity); static CagdCrvStruct *RmKntGetCurveAfterRemoval(CagdCrvStruct *OriginalCrv, int KnotIndex, int LeftMult, CagdCtlPtStruct *SamplePoints, CagdRType *SamplesLocations, int SamplesNum); static CagdRType RmKntInfiniteNorm(CagdCrvStruct *Crv1, CagdCrvStruct *Crv2); static CagdRType RmKntComputeNorm(CagdCrvStruct *Crv1, CagdCrvStruct *Crv2, int NormOrder); static int RmKntGetRegionLowIndex(CagdCrvStruct *Crv, int KnotIndex); static int RmKntGetRegionHighIndex(CagdCrvStruct *Crv, int KnotIndex); static CagdRType RmKntGetKnotWeight(CagdCrvStruct *OriginalCrv, int KnotIndex, int NormOrder, int SamplesNum); static IritPriorQue *RmKntSortKnots(CagdCrvStruct *OriginalCrv, int NormOrder, int SamplesNum); static int RmKntInsert(int *RemovedKnots, int RemovedKnotsNum, int Order, RmKntKnotWeightStruct *KnotWeight); static RmKntRemoveKnotsStruct *RmKntGetKnotsToRemove(IritPriorQue **KnotsQueue, int KnotsQueueLength, int HowMuchToRemove, int Order); static int RmKntIsLegalInput(CagdCrvStruct *Crv, int KnotsNumber, int NormOrder, int SamplesNum); static RmKntRemoveKnotsStruct *RmKntGetKnotsUnderMax(IritPriorQue *SortedKnots, CagdRType MaxError); /***************************************************************************** * DESCRIPTION: * * A printing function for printing an IritPriorQue which consists of * * `RmKntKnotWeightStruct` elements. * * * * PARAMETERS: * * Element: A queue element to print. * * * * RETURN VALUE: * * None * *****************************************************************************/ #ifdef DEBUG static void RmKntPrintPQ(VoidPtr Element) { printf("%d %g\n", ((RmKntKnotWeightStruct *) Element) -> KnotIndex, ((RmKntKnotWeightStruct *) Element) -> Weight); } #endif /* DEBUG */ /***************************************************************************** * DESCRIPTION: * * A comparing function for comparing between two elements of an * * IritPriorQue which consists of `RmKntKnotWeightStruct` elements. * * * * PARAMETERS: * * Element1: A queue element. * * Element2: A queue element. * * * * RETURN VALUE: * * int: 1 if Element1 > Element2, -1 if Element1 < Element2, * * 0 otherweise. * *****************************************************************************/ static int RmKntKnotWeightComp(VoidPtr Element1, VoidPtr Element2) { RmKntKnotWeightStruct *Knot1, *Knot2; Knot1 = (RmKntKnotWeightStruct *) Element1; Knot2 = (RmKntKnotWeightStruct *) Element2; if (Knot1 -> Weight > Knot2 -> Weight) return 1; if (Knot1 -> Weight < Knot2 -> Weight) return -1; return 0; } /***************************************************************************** * DESCRIPTION: * * Computes the index of the lowest interior knot of a given curve. * * * * PARAMETERS: * * Crv: A given curve. * * * * RETURN VALUE: * * int: Lowest interior index. * *****************************************************************************/ static int RmKntGetLowestInteriorIndex(CagdCrvStruct *Crv) { return Crv -> Order; } /***************************************************************************** * DESCRIPTION: * * Computes the index of the highest interior knot of a given curve. * * * * PARAMETERS: * * Crv: a given curve. * * * * RETURN VALUE: * * int: Highest interior index. * *****************************************************************************/ static int RmKntGetHighestInteriorIndex(CagdCrvStruct *Crv) { return Crv -> Length - 1; } /***************************************************************************** * DESCRIPTION: * * Checks if the lowest interior knot is bigger than it's exterior neighbor * * and the highest interior knot is smaller than it's exterior neighbor. * * * * PARAMETERS: * * Crv: A given curve to check on. * * * * RETURN VALUE: * * int: TRUE if the check succeeds, FALSE otherwise. * *****************************************************************************/ static int RmKntAreInteriorDifferentExterior(CagdCrvStruct *Crv) { int Lowest, Highest; Lowest = RmKntGetLowestInteriorIndex(Crv); Highest = RmKntGetHighestInteriorIndex(Crv); return Crv -> KnotVector[Lowest] > Crv -> KnotVector[Lowest - 1] && Crv -> KnotVector[Highest] < Crv -> KnotVector[Highest + 1]; } /***************************************************************************** * DESCRIPTION: * * Checks if the given index is an index of an interior knot in the given * * curve. * * * * PARAMETERS: * * Crv: A given curve to check on. * * KnotIndex: Index of knot. * * * * RETURN VALUE: * * int: TRUE if the check succeeds, FALSE otherwise. * *****************************************************************************/ static int RmKntIsInteriorKnot(CagdCrvStruct *Crv, int KnotIndex) { return KnotIndex >= RmKntGetLowestInteriorIndex(Crv) && KnotIndex <= RmKntGetHighestInteriorIndex(Crv); } /***************************************************************************** * DESCRIPTION: * * Computes the number of interior knots of a given curve. * * * * PARAMETERS: * * Crv: A given curve. * * * * RETURN VALUE: * * int: Number of interior knots. * *****************************************************************************/ static int RmKntGetInteriorKnotsNum(CagdCrvStruct *Crv) { return Crv -> Length - Crv -> Order; } /***************************************************************************** * DESCRIPTION: * * Allocates a linked list of 'CagdCtlPtStruct' of the type 'PointType. * * * * PARAMETERS: * * SamplesNum: Number of elements in the allocated list. * * PointType: Type of points. * * * * RETURN VALUE: * * CagdCtlPtStruct *: A list of control points. * *****************************************************************************/ static CagdCtlPtStruct *RmKntAllocateSamplePoints(int SamplesNum, CagdPointType PointType) { int i; CagdCtlPtStruct *Points; Points = (CagdCtlPtStruct *) IritMalloc(SamplesNum * sizeof(CagdCtlPtStruct)); ZAP_MEM(Points, SamplesNum * sizeof(CagdCtlPtStruct)); for (i = 0; i < SamplesNum - 1; i++) { Points[i].Pnext = &Points[i + 1]; Points[i].PtType = PointType; } Points[i].PtType = PointType; return Points; } /***************************************************************************** * DESCRIPTION: * * Returns the index of the knot from which sampling should start. * * * * PARAMETERS: * * Crv: A given curve. * * * * RETURN VALUE: * * int: Index of starting knot. * *****************************************************************************/ static int RmKntGetSampleIntervalStart(CagdCrvStruct *Crv) { return RmKntGetLowestInteriorIndex(Crv) - 1; } /***************************************************************************** * DESCRIPTION: * * Returns the index of the knot at which sampling should end. * * * * PARAMETERS: * * Crv: A given curve. * * * * RETURN VALUE: * * int: Index of ending knot. * *****************************************************************************/ static int RmKntGetSampleIntervalEnd(CagdCrvStruct *Crv) { return RmKntGetHighestInteriorIndex(Crv) + 1; } /***************************************************************************** * DESCRIPTION: * * Returns the multiplicity of the knot whose index is given. * * * * PARAMETERS: * * Crv: A given curve. * * KnotIndex: Index of knot. * * IsLeftMultiplicity: Return left multiplicity if TRUE, right multiplicity * * otherwise. * * * * RETURN VALUE: * * int: Knot multiplicity. * *****************************************************************************/ static int RmKntGetKnotMultiplicity(CagdCrvStruct *Crv, int KnotIndex, int IsLeftMultiplicity) { int Mult, Knot, Direction; if (IsLeftMultiplicity == TRUE) Direction = -1; else Direction = 1; for (Knot = KnotIndex, Mult = 0; (Crv -> KnotVector[Knot] == Crv -> KnotVector[KnotIndex]); Knot += Direction) Mult++; return Mult; } /***************************************************************************** * DESCRIPTION: * * Sample the given curve at the given locations. * * * * PARAMETERS: * * Crv: A given curve to sample. * * SamplesLocations: Sampling locations. * * SamplesNum: Number of locations. * * * * RETURN VALUE: * * CagdCtlPtStruct *: An array of samplings. * *****************************************************************************/ static CagdCtlPtStruct *RmKntSample(CagdCrvStruct *Crv, CagdRType *SamplesLocations, int SamplesNum) { int Sample, CopySize; CagdBType IsRational; CagdCtlPtStruct *SamplePoints; CagdRType *SingleSample; if (SamplesNum <= 0) return 0; IsRational = CAGD_IS_RATIONAL_PT(Crv -> PType); CopySize = (CAGD_NUM_OF_PT_COORD(Crv -> PType) + IsRational) * sizeof(CagdRType); SamplePoints = RmKntAllocateSamplePoints(SamplesNum, Crv -> PType); for (Sample = 0; Sample < SamplesNum; Sample++) { SingleSample = BspCrvEvalAtParam(Crv, SamplesLocations[Sample]); CAGD_GEN_COPY(&SamplePoints[Sample].Coords[!IsRational], &SingleSample[!IsRational], CopySize); } return SamplePoints; } /***************************************************************************** * DESCRIPTION: * * Compute sampling locations for the given curve. * * * * PARAMETERS: * * Crv: A given curve. * * LocationsNum: Number of sampling location. * * * * RETURN VALUE: * * CagdRType *: An array of sampling locations. * *****************************************************************************/ static CagdRType *RmKntGetSamplingLocations(CagdCrvStruct *Crv, int LocationsNum) { int Loc; CagdRType *Locations, t, T0, T1, Step; if (LocationsNum <= 2) return NULL; Locations = (CagdRType *) IritMalloc(LocationsNum * sizeof(CagdRType)); T0 = Crv -> KnotVector[RmKntGetSampleIntervalStart(Crv)]; T1 = Crv -> KnotVector[RmKntGetSampleIntervalEnd(Crv)]; Step = (T1 - T0) / (IRIT_EPS + LocationsNum - 1); for (Loc = 0, t = T0; Loc < LocationsNum; Loc++, t += Step) Locations[Loc] = t; return Locations; } /***************************************************************************** * DESCRIPTION: * * Compute the knot vector of an interpolating curve after removing * * 'KnotsNum' knots. * * * * PARAMETERS: * * OriginalCrv: The original curve. * * KnotIndices: The indices of the knots which should be removed. * * KnotsNum: The number of the knots which should be removed. * * * * RETURN VALUE: * * CagdRType *: The computed knot vector. * *****************************************************************************/ static CagdRType *RmKntGetInterpolantKV(CagdCrvStruct *OriginalCrv, int *KnotIndices, int KnotsNum) { int Length, Knot, Index, StayingKnot; CagdRType *InterpolantKV, *OriginalKV; Length = OriginalCrv -> Order + OriginalCrv -> Length; InterpolantKV = (CagdRType *) IritMalloc((Length - KnotsNum) * sizeof(CagdRType)); for (Knot = StayingKnot = 0, OriginalKV = OriginalCrv -> KnotVector; Knot < Length; Knot++) { for (Index = 0; Index < KnotsNum; Index++) if (Knot == KnotIndices[Index]) break; if (Index >= KnotsNum) { /* Do'nt remove current knot. */ InterpolantKV[StayingKnot++] = OriginalKV[Knot]; } } if (StayingKnot != Length - KnotsNum) { SYMB_FATAL_ERROR(SYMB_ERR_ILLEGAL_PARAMETERS); return NULL; } return InterpolantKV; } /***************************************************************************** * DESCRIPTION: * * Refine the interpolant curve back to the length of the interpolated * * so their norm can be computed. * * * * PARAMETERS: * * Interpolant: The interpolant curve. * * KnotValue: The value of the inserted knot. * * Multiplicity: The multiplicity of the inserted knot. * * * * RETURN VALUE: * * CagdCrvStruct *: The interpolant curve after refinement. * *****************************************************************************/ static CagdCrvStruct *RmKntRefineInterpolant(CagdCrvStruct *Interpolant, CagdRType KnotValue, int Multiplicity) { CagdCrvStruct *Refined; CagdRType *NewKnotsVector; int Knot; NewKnotsVector = (CagdRType *)IritMalloc(Multiplicity * sizeof(CagdRType)); for (Knot = 0; Knot < Multiplicity; Knot++) NewKnotsVector[Knot] = KnotValue; Refined = BspCrvKnotInsertNDiff(Interpolant, FALSE, NewKnotsVector, Multiplicity); IritFree(NewKnotsVector); return Refined; } /***************************************************************************** * DESCRIPTION: * * Remove a knot from a curve. * * * * PARAMETERS: * * OriginalCrv: The original curve. * * KnotIndex: The index of the knot which should be removed. * * LeftMult: The left muliplicity of the knot which should be removed. * * SamplePoints: Samplings of the original curve. * * SamplesLocations: Locations of the samplings. * * SamplesNum: Number of samplings. * * * * RETURN VALUE: * * CagdCrvStruct *: The curve after removal. * *****************************************************************************/ static CagdCrvStruct *RmKntGetCurveAfterRemoval(CagdCrvStruct *OriginalCrv, int KnotIndex, int LeftMult, CagdCtlPtStruct *SamplePoints, CagdRType *SamplesLocations, int SamplesNum) { int *KnotIndices, Knot; CagdCrvStruct *Interpolant, *Refined; CagdRType *InterpolantKV; /* Prepare all the indices of the knots to remove. */ KnotIndices = (int *) IritMalloc(LeftMult * sizeof(int)); for (Knot = 0; Knot < LeftMult; Knot++) KnotIndices[Knot] = KnotIndex - Knot; InterpolantKV = RmKntGetInterpolantKV(OriginalCrv, KnotIndices, LeftMult); Interpolant = BspCrvInterpolate(SamplePoints, SamplesNum, SamplesLocations, InterpolantKV, OriginalCrv -> Length - LeftMult, OriginalCrv -> Order, OriginalCrv -> Periodic); /* Refine so a norm can be computed. */ Refined = RmKntRefineInterpolant(Interpolant, OriginalCrv -> KnotVector[KnotIndex], LeftMult); CagdCrvFree(Interpolant); IritFree(InterpolantKV); IritFree(KnotIndices); return Refined; } /***************************************************************************** * DESCRIPTION: * * Compute an infinite norm of the distance between the control * * coefficients of two curves. * * * * PARAMETERS: * * Crv1, Crv2: Given curves. * * * * RETURN VALUE: * * CagdRType: Norm value. * *****************************************************************************/ static CagdRType RmKntInfiniteNorm(CagdCrvStruct *Crv1, CagdCrvStruct *Crv2) { int Point, Length; CagdRType Norm, Distance, **Points1, **Points2; Length = Crv1 -> Length; Points1 = Crv1 -> Points; Points2 = Crv2 -> Points; for (Point = 0, Norm = 0.0; Point < Length; Point++) { Distance = CagdDistTwoCtlPt(Points1, Point, Points2, Point, Crv1 -> PType); if (Norm < Distance) /* Return maximal distance. */ Norm = Distance; } return Norm; } /***************************************************************************** * DESCRIPTION: * * Compute a finite norm of the distance between the control coefficients * * of two curves. * * * * PARAMETERS: * * Crv1, Crv2: Given curves. * * NormOrder: Order on norm. * * * * RETURN VALUE: * * CagdRType: Norm value. * *****************************************************************************/ static CagdRType RmKntComputeNorm(CagdCrvStruct *Crv1, CagdCrvStruct *Crv2, int NormOrder) { CagdRType Norm, Distance, **Points1, **Points2; int Point, Length; if ((Crv1 -> Length != Crv2 -> Length) || (Crv1 -> PType != Crv2 -> PType)) return -1; if (NormOrder == RM_KNT_INFINITE_NORM) return RmKntInfiniteNorm(Crv1, Crv2); Length = Crv1 -> Length; Points1 = Crv1 -> Points; Points2 = Crv2 -> Points; for (Point = 0, Norm = 0.0; Point < Length; Point++) { Distance = CagdDistTwoCtlPt(Points1, Point, Points2, Point, Crv1 -> PType); Norm += pow(Distance, NormOrder); } Norm = pow(Norm, 1.0 / NormOrder); return Norm / Length; } /***************************************************************************** * DESCRIPTION: * * Return the index of the smallest knot of a curve generated by * * CagdCrvRegionFromCrv(). * * * * PARAMETERS: * * Crv: The original curve from a region curve was generated. * * KnotIndex: The index of the knot around which the regin curve was * * generated. * * * * RETURN VALUE: * * int: Knot index. * *****************************************************************************/ static int RmKntGetRegionLowIndex(CagdCrvStruct *Crv, int KnotIndex) { int Order = Crv -> Order; if (KnotIndex - Order < Order-1) return Order - 1; return KnotIndex - Order; } /***************************************************************************** * DESCRIPTION: * * Return the index of the largest knot of a curve generated by * * CagdCrvRegionFromCrv(). * * * * PARAMETERS: * * Crv: The original curve from a region curve was generated. * * KnotIndex: The index of the knot around which the regin curve was * * generated. * * * * RETURN VALUE: * * int: Knot index. * *****************************************************************************/ static int RmKntGetRegionHighIndex(CagdCrvStruct *Crv, int KnotIndex) { int Order = Crv -> Order; if (KnotIndex + Order > Crv -> Length) return Crv -> Length; return KnotIndex + Order; } /***************************************************************************** * DESCRIPTION: * * Compute the weight of a single knot. * * * * PARAMETERS: * * OriginalCrv: The original curve on which the weight is computed. * * KnotIndex: The index of the knot. * * NormOrder: Order of the norm to compute the eight with. * * SamplesNum: Number of samples to sample the curve. * * * * RETURN VALUE: * * CagdRType: Weight value. * *****************************************************************************/ static CagdRType RmKntGetKnotWeight(CagdCrvStruct *OriginalCrv, int KnotIndex, int NormOrder, int SamplesNum) { int LeftMult, RegionLowIndex, RegionHighIndex; CagdCtlPtStruct *SamplePoints; CagdCrvStruct *Region, *AfterRemoval; CagdRType *SamplesLocations, Weight; if ((RmKntIsInteriorKnot(OriginalCrv, KnotIndex) == FALSE)) return -1.0; LeftMult = RmKntGetKnotMultiplicity(OriginalCrv, KnotIndex, TRUE); RegionLowIndex = RmKntGetRegionLowIndex(OriginalCrv, KnotIndex); RegionHighIndex = RmKntGetRegionHighIndex(OriginalCrv, KnotIndex); Region = CagdCrvRegionFromCrv(OriginalCrv, OriginalCrv -> KnotVector[RegionLowIndex], OriginalCrv -> KnotVector[RegionHighIndex]); /* Recomputing the knot's index in the new region curve. See */ /* CagdCrvRegionFromCrv() description. */ KnotIndex = KnotIndex - RegionLowIndex + OriginalCrv -> Order - RmKntGetKnotMultiplicity(OriginalCrv, RegionLowIndex, FALSE); SamplesLocations = RmKntGetSamplingLocations(Region, SamplesNum); SamplePoints = RmKntSample(Region, SamplesLocations, SamplesNum); AfterRemoval = RmKntGetCurveAfterRemoval(Region, KnotIndex, LeftMult, SamplePoints, SamplesLocations, SamplesNum); Weight = RmKntComputeNorm(Region, AfterRemoval, NormOrder); CagdCrvFree(Region); CagdCrvFree(AfterRemoval); IritFree(SamplesLocations); IritFree(SamplePoints); return Weight; } /***************************************************************************** * DESCRIPTION: * * Sort the knots according to their weights. * * * * PARAMETERS: * * OriginalCrv: The original curve whose knots are sorted. * * NormOrder: Order of the norm to compute the weights of the knots. * * SamplesNum: Number of samples to sample the curve. * * * * RETURN VALUE: * * IritPriorQue *: A priority queue holding the knots according to their * * weights. * *****************************************************************************/ static IritPriorQue *RmKntSortKnots(CagdCrvStruct *OriginalCrv, int NormOrder, int SamplesNum) { int KnotIndex; RmKntKnotWeightStruct *Knot; IritPriorQue *Queue; IritPQInit(&Queue); IritPQCompFunc(RmKntKnotWeightComp); for (KnotIndex = RmKntGetLowestInteriorIndex(OriginalCrv); KnotIndex <= RmKntGetHighestInteriorIndex(OriginalCrv); KnotIndex++) { Knot = (RmKntKnotWeightStruct *) IritMalloc(sizeof(RmKntKnotWeightStruct)); Knot -> KnotIndex = KnotIndex; Knot -> Weight = RmKntGetKnotWeight(OriginalCrv, KnotIndex, NormOrder, SamplesNum); IritPQInsert(&Queue, Knot); } return Queue; } /***************************************************************************** * DESCRIPTION: * * Insert, if possible, the given knot to the 'RemovedKnots' array. * * * * PARAMETERS: * * RemovedKnots: Array of removed knots. * * RemovedKnotsNum: Size of 'RemovedKnots'. * * Order: Curve order. * * KnotWeight: The knot to remove. * * * * RETURN VALUE: * * int: True if knot is inserted, FALSE otherwise. * *****************************************************************************/ static int RmKntInsert(int *RemovedKnots, int RemovedKnotsNum, int Order, RmKntKnotWeightStruct *KnotWeight) { int Knot, CanInsert, KnotIndex; KnotIndex = KnotWeight -> KnotIndex; if (KnotWeight -> Weight < IRIT_EPS) { /* No error, knot can be removed. */ RemovedKnots[RemovedKnotsNum] = KnotIndex; return TRUE; } /* Check if knot is too close to other removed knots. */ /* Too close = less than an 'order' distance. */ for (Knot = 0, CanInsert = TRUE; Knot < RemovedKnotsNum; Knot++) { if ((KnotIndex >= RemovedKnots[Knot] - Order) && (KnotIndex <= RemovedKnots[Knot] + Order)) { CanInsert = FALSE; break; } } if (CanInsert == TRUE) RemovedKnots[RemovedKnotsNum] = KnotIndex; return CanInsert; } /***************************************************************************** * DESCRIPTION: * * Find the indices of the knots that can be removed. * * * * PARAMETERS: * * KnotsQueue: Sorted knots' queue. * * KnotsQueueLength: Size of 'KnotsQueue'. * * HowMuchToRemove: Maximal number of knots to remove. * * Order: Curve order. * * * * RETURN VALUE: * * RmKntRemoveKnotsStruct *: The indices of the knots to remove. * *****************************************************************************/ static RmKntRemoveKnotsStruct *RmKntGetKnotsToRemove(IritPriorQue **KnotsQueue, int KnotsQueueLength, int HowMuchToRemove, int Order) { int *KnotsIndices, RemovedKnotsNum, Knot; RmKntKnotWeightStruct *KnotWeight; RmKntRemoveKnotsStruct *KnotsToRemove; KnotsToRemove = (RmKntRemoveKnotsStruct *) IritMalloc(sizeof(RmKntRemoveKnotsStruct)); KnotsIndices = (int *) IritMalloc(HowMuchToRemove * sizeof(int)); for (Knot = RemovedKnotsNum = 0; Knot < KnotsQueueLength && RemovedKnotsNum < HowMuchToRemove; Knot++) { KnotWeight = (RmKntKnotWeightStruct *) IritPQFirst(KnotsQueue, TRUE); if (RmKntInsert(KnotsIndices, RemovedKnotsNum, Order, KnotWeight) == TRUE) RemovedKnotsNum++; IritFree(KnotWeight); } KnotsToRemove -> Length = RemovedKnotsNum; KnotsToRemove -> KnotsIndices = KnotsIndices; #ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugRemoveKnots) { int k; printf("Removing knots:\n"); for (k = 0; k < RemovedKnotsNum; k++) printf("%d\n", KnotsIndices[k]); } #endif /* DEBUG */ return KnotsToRemove; } /***************************************************************************** * DESCRIPTION: * * Check input parameters. * * * * PARAMETERS: * * Crv: Input curve. * * KnotsNumber: Number of knots to remove. * * NormOrder: Order of norm to compute errors. * * SamplesNum: Number of samples to sample the curves. * * * * RETURN VALUE: * * int: TRUE if input parameters are legal, FALSE otherwise. * *****************************************************************************/ static int RmKntIsLegalInput(CagdCrvStruct *Crv, int KnotsNumber, int NormOrder, int SamplesNum) { if (Crv -> PType < CAGD_PT_BASE && Crv -> PType > CAGD_PT_P9_TYPE) { SYMB_FATAL_ERROR(SYMB_ERR_WRONG_PT_TYPE); return FALSE; } if (NormOrder < RM_KNT_INFINITE_NORM || SamplesNum <= 0 || RmKntAreInteriorDifferentExterior(Crv) == FALSE || KnotsNumber > RmKntGetInteriorKnotsNum(Crv) || KnotsNumber <= 0) { SYMB_FATAL_ERROR(SYMB_ERR_ILLEGAL_PARAMETERS); return FALSE; } return TRUE; } /***************************************************************************** * DESCRIPTION: * * Compute the indices of all the knots whose weight is under an error * * threshold. * * * * PARAMETERS: * * SortedKnots: Knots sorted by weights. * * MaxError: Error threshold. * * * * RETURN VALUE: * * RmKntRemoveKnotsStruct *: Indices of all corresponding knots. * *****************************************************************************/ static RmKntRemoveKnotsStruct *RmKntGetKnotsUnderMax(IritPriorQue *SortedKnots, CagdRType MaxError) { int KnotsNumber, *KnotsIndices; RmKntKnotWeightStruct *KnotWeight, *CompareItem = NULL, *LargerItem = NULL; RmKntRemoveKnotsStruct *KnotsUnderMax; KnotsUnderMax = (RmKntRemoveKnotsStruct *) IritMalloc(sizeof(RmKntRemoveKnotsStruct)); KnotsIndices = (int *) IritMalloc(IritPQSize(SortedKnots) * sizeof(int)); KnotWeight = (RmKntKnotWeightStruct *) IritPQFirst(&SortedKnots, FALSE); for (KnotsNumber = 0; KnotWeight != 0 && KnotWeight -> Weight <= MaxError; KnotWeight = (RmKntKnotWeightStruct *) IritPQNext(SortedKnots, CompareItem, LargerItem), KnotsNumber++) { KnotsIndices[KnotsNumber] = KnotWeight -> KnotIndex; CompareItem = KnotWeight; } KnotsUnderMax -> KnotsIndices = KnotsIndices; KnotsUnderMax -> Length = KnotsNumber; return KnotsUnderMax; } /***************************************************************************** * DESCRIPTION: M * Remove a given number of knots. M * * * PARAMETERS: M * OriginalCrv: Curve to remove from. M * RemoveKnotsNumber: Number of knots to remove. M * MaxInIteration: Maximal number of knots to remove in a single iteration. M * SamplesNum: Number of samples to sample the curves. M * * * RETURN VALUE: M * CagdCrvStruct *: The new curve after removal. M * * * SEE ALSO: M * SymbRmKntBspCrvRemoveKnotsError, SymbRmKntBspCrvCleanKnots M * * * KEYWORDS: M * SymbRmKntBspCrvRemoveKnots M *****************************************************************************/ CagdCrvStruct *SymbRmKntBspCrvRemoveKnots(CagdCrvStruct *OriginalCrv, int RemoveKnotsNumber, int MaxInIteration, int SamplesNum) { CagdCrvStruct *Result, *Crv; IritPriorQue *SortedKnots; RmKntRemoveKnotsStruct *KnotsToRemove; CagdCtlPtStruct *SamplePoints; CagdRType *SamplesLocations, *ResultKV; int HowMuchToRemove; if (RmKntIsLegalInput(OriginalCrv, RemoveKnotsNumber, RM_KNT_INFINITE_NORM, SamplesNum) == FALSE) return NULL; if (MaxInIteration <= 0) MaxInIteration = 1; if (OriginalCrv -> Periodic != TRUE) Crv = OriginalCrv; else Crv = CnvrtFloat2OpenCrv(OriginalCrv); SamplesLocations = RmKntGetSamplingLocations(Crv, SamplesNum); /* While there are still knots to move. */ while (RemoveKnotsNumber > 0) { SortedKnots = RmKntSortKnots(Crv, RM_KNT_INFINITE_NORM, SamplesNum); # ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugRemoveKnots) { /* Print the knots sorted by their weights. */ printf("Knots' indices sorted by the weight of the knots:\n"); IritPQPrint(SortedKnots, RmKntPrintPQ); } # endif /* DEBUG */ HowMuchToRemove = (RemoveKnotsNumber > MaxInIteration) ? MaxInIteration : RemoveKnotsNumber; KnotsToRemove = RmKntGetKnotsToRemove(&SortedKnots, IritPQSize(SortedKnots), HowMuchToRemove, Crv -> Order); ResultKV = RmKntGetInterpolantKV(Crv, KnotsToRemove -> KnotsIndices, KnotsToRemove -> Length); SamplePoints = RmKntSample(Crv, SamplesLocations, SamplesNum); Result = BspCrvInterpolate(SamplePoints, SamplesNum, SamplesLocations, ResultKV, Crv -> Length - KnotsToRemove -> Length, Crv -> Order, Crv -> Periodic); RemoveKnotsNumber -= KnotsToRemove -> Length; IritFree(KnotsToRemove -> KnotsIndices); IritFree(KnotsToRemove); IritFree(ResultKV); IritPQFree(SortedKnots, TRUE); IritFree(SamplePoints); if (Crv != OriginalCrv) CagdCrvFree(Crv); Crv = Result; } IritFree(SamplesLocations); return Result; } /***************************************************************************** * DESCRIPTION: M * Remove knots under a given error threshold. M * * * PARAMETERS: M * OriginalCrv: Curve to remove from. M * MaxError: Error threshold. M * MaxErrorInIteration: A maximal error threshold for a single iteration. M * SamplesNum: Number of samples to sample the curves. M * * * RETURN VALUE: M * CagdCrvStruct *: The new curve after removal. M * * * SEE ALSO: M * SymbRmKntBspCrvRemoveKnots, SymbRmKntBspCrvCleanKnots M * * * KEYWORDS: M * SymbRmKntBspCrvRemoveKnotsError M *****************************************************************************/ CagdCrvStruct *SymbRmKntBspCrvRemoveKnotsError(CagdCrvStruct *OriginalCrv, CagdRType MaxError, CagdRType MaxErrorInIteration, int SamplesNum) { int KnotsUnderMaxNum, KnotsToRemoveNum, MaxInIteration, i, j; IritPriorQue *SortedKnots; CagdCrvStruct *Crv, *Result; RmKntRemoveKnotsStruct *KnotsToRemove, *KnotsUnderMax; if (RmKntIsLegalInput(OriginalCrv, 1, RM_KNT_INFINITE_NORM, SamplesNum) == FALSE) return NULL; if (OriginalCrv -> Periodic != TRUE) Crv = OriginalCrv; else Crv = CnvrtFloat2OpenCrv(OriginalCrv); for (KnotsUnderMaxNum = 1; KnotsUnderMaxNum > 0; ) { SortedKnots = RmKntSortKnots(Crv, RM_KNT_INFINITE_NORM, SamplesNum); KnotsUnderMax = RmKntGetKnotsUnderMax(SortedKnots, MaxError); KnotsUnderMaxNum = KnotsUnderMax -> Length; if (KnotsUnderMaxNum == 0) { if (Crv == OriginalCrv) Result = CagdCrvCopy(Crv); else Result = Crv; IritPQFree(SortedKnots, TRUE); IritFree(KnotsUnderMax -> KnotsIndices); IritFree(KnotsUnderMax); break; } /* Get the knots that can be removed. */ KnotsToRemove = RmKntGetKnotsToRemove(&SortedKnots, IritPQSize(SortedKnots), KnotsUnderMaxNum, Crv -> Order); KnotsToRemoveNum = KnotsToRemove -> Length; /* Check how many of the removable knots are below the 'max_error'. */ for (i = 0; i < KnotsToRemoveNum; i++) { for (j = 0; j < KnotsUnderMaxNum; j++) { if (KnotsToRemove -> KnotsIndices[i] == KnotsUnderMax -> KnotsIndices[j]) break; } /* The next knot to remove is above max error. */ if (j >= KnotsUnderMaxNum) break; } KnotsUnderMaxNum -= i; IritPQFree(SortedKnots, TRUE); IritFree(KnotsUnderMax -> KnotsIndices); IritFree(KnotsUnderMax); IritFree(KnotsToRemove -> KnotsIndices); IritFree(KnotsToRemove); /* Remove only the knots below 'max_error'. */ MaxInIteration = (int) (KnotsUnderMaxNum * (MaxErrorInIteration / MaxError)); Result = SymbRmKntBspCrvRemoveKnots(Crv, i, MaxInIteration, SamplesNum); if (Crv != OriginalCrv) CagdCrvFree(Crv); Crv = Result; } return Result; } /***************************************************************************** * DESCRIPTION: M * Remove only knots which do not change the given curve. M * * * PARAMETERS: M * OriginalCrv: Curve to remove from. M * SamplesNum: Number of samples to sample the curves. M * * * RETURN VALUE: M * CagdCrvStruct *: The new curve after removal. M * * * SEE ALSO: M * SymbRmKntBspCrvRemoveKnots, SymbRmKntBspCrvRemoveKnotsError M * * * KEYWORDS: M * SymbRmKntBspCrvCleanKnots M *****************************************************************************/ CagdCrvStruct *SymbRmKntBspCrvCleanKnots(CagdCrvStruct *OriginalCrv, int SamplesNum) { return SymbRmKntBspCrvRemoveKnotsError(OriginalCrv, IRIT_EPS, IRIT_EPS, SamplesNum); }