/****************************************************************************** * SymbPoly.c - Generic Curve/Surface to polygon/polylines conversion routines.* ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by Gershon Elber, July. 90. * ******************************************************************************/ #include "symb_loc.h" #include "dist_pts.h" #include "geomat3d.h" #define CURVE_PTS_DIST_RESOLUTION 10 static CagdCrvStruct *GlblDeriv1MagSqrCrv = NULL, *GlblCrvtrCrv = NULL; static CagdRType GlblCrvtrCrvTMin, GlblCrvtrCrvTMax; static CagdPolylineStruct *SymbCrv2OptiTlrncPolyline(CagdCrvStruct *Crv, CagdRType Tolerance); static CagdPtStruct *SymbCrv2OptiTlrncPolyAux(CagdCrvStruct *Crv, CagdRType Tolerance, CagdBType AddFirstPt); static CagdPolylineStruct *SymbCrv2OptiCrvtrPolyline(CagdCrvStruct *Crv, int SamplesPerCurve); static RealType CrvCurvatureEvalFunc(RealType t); /***************************************************************************** * DESCRIPTION: M * Routine to convert a single surface to set of triangles approximating it. M * FineNess is a fineness control on result and the larger it is more M * triangles may result. M * A value of 10 is a good starting value. M * NULL is returned in case of an error, otherwise list of CagdPolygonStruct. M * * * PARAMETERS: M * Srf: To approximate into triangles. M * FineNess: Control on accuracy, the higher the finer. M * ComputeNormals: If TRUE, normal information is also computed. M * FourPerFlat: If TRUE, four triangles are created per flat surface. M * If FALSE, only 2 triangles are created. M * ComputeUV: If TRUE, UV values are stored and returned as well. M * * * RETURN VALUE: M * CagdPolygonStruct *: A list of polygons with optional normal and/or M * UV parametric information. M * NULL is returned in case of an error. M * * * SEE ALSO: M * BzrSrf2Polygons, IritSurface2Polygons, IritTrimSrf2Polygons, M * BspSrf2Polygons, TrimSrf2Polygons M * * * KEYWORDS: M * SymbSrf2Polygons, polygonization, surface approximation M *****************************************************************************/ CagdPolygonStruct *SymbSrf2Polygons(CagdSrfStruct *Srf, int FineNess, CagdBType ComputeNormals, CagdBType FourPerFlat, CagdBType ComputeUV) { /* Make sure we do not deal with constant surfaces. */ if (Srf -> UOrder < 2 || Srf -> VOrder < 2) { SYMB_FATAL_ERROR(SYMB_ERR_POLY_CONST_SRF); return NULL; } switch (Srf -> GType) { case CAGD_SBEZIER_TYPE: return BzrSrf2Polygons(Srf, FineNess, ComputeNormals, FourPerFlat, ComputeUV); case CAGD_SBSPLINE_TYPE: return BspSrf2Polygons(Srf, FineNess, ComputeNormals, FourPerFlat, ComputeUV); case CAGD_SPOWER_TYPE: SYMB_FATAL_ERROR(SYMB_ERR_POWER_NO_SUPPORT); return NULL; default: SYMB_FATAL_ERROR(SYMB_ERR_UNDEF_SRF); return NULL; } } /***************************************************************************** * DESCRIPTION: M * Routine to convert a single surface to NumOfIsolines polylines in each M * parametric direction with SamplesPerCurve in each isoparametric curve. M * Polyline are always E3 of CagdPolylineStruct type. M * NULL is returned in case of an error, otherwise list of M * CagdPolylineStruct. Attempt is made to extract isolines along C1 M * discontinuities first. M * * * PARAMETERS: M * Srf: Srf to extract isoparametric curves from. M * NumOfIsocurves: To extarct from Srf in each (U or V) direction. M * TolSamples: Tolerance of approximation error (Method = 2) or M * Number of samples to compute on polyline (Method = 0, 1). M * Method: 0 - TolSamples are set uniformly in parametric space, M * 1 - TolSamples are set optimally, considering the M * isocurve's curvature. M * 2 - TolSamples sets the maximum error allowed between the M * piecewise linear approximation and original curve. M * * * RETURN VALUE: M * CagdPolylineStruct *: List of polylines representing a piecewise linear M * approximation of the extracted isoparamteric M * curves or NULL is case of an error. M * * * SEE ALSO: M * BspSrf2Polylines, BzrSrf2Polylines, IritSurface2Polylines, M * IritTrimSrf2Polylines, TrimSrf2Polylines M * * * KEYWORDS: M * SymbSrf2Polylines, polylines, isoparametric curves M *****************************************************************************/ CagdPolylineStruct *SymbSrf2Polylines(CagdSrfStruct *Srf, int NumOfIsocurves[2], CagdRType TolSamples, SymbCrvApproxMethodType Method) { CagdCrvStruct *Crv, *Crvs; CagdPolylineStruct *Poly, *Polys; switch (Method) { case SYMB_CRV_APPROX_TOLERANCE: case SYMB_CRV_APPROX_CURVATURE: Crvs = SymbSrf2Curves(Srf, NumOfIsocurves); Polys = NULL; for (Crv = Crvs; Crv != NULL; Crv = Crv -> Pnext) { if (Method == SYMB_CRV_APPROX_TOLERANCE) { Poly = SymbCrv2OptiTlrncPolyline(Crv, TolSamples); } else { Poly = SymbCrv2OptiCrvtrPolyline(Crv, (int) TolSamples); } Poly -> Pnext = Polys; Polys = Poly; } CagdCrvFreeList(Crvs); return Polys; default: case SYMB_CRV_APPROX_UNIFORM: switch (Srf -> GType) { case CAGD_SBEZIER_TYPE: return BzrSrf2Polylines(Srf, NumOfIsocurves, (int) TolSamples); case CAGD_SBSPLINE_TYPE: return BspSrf2Polylines(Srf, NumOfIsocurves, (int) TolSamples); case CAGD_SPOWER_TYPE: SYMB_FATAL_ERROR(SYMB_ERR_POWER_NO_SUPPORT); return NULL; default: SYMB_FATAL_ERROR(SYMB_ERR_UNDEF_SRF); return NULL; } } } /***************************************************************************** * DESCRIPTION: M * Routine to extract from a surface NumOfIsoline isocurve list M * in each param. direction. M * Iso parametric curves are sampled equally spaced in parametric space. M * NULL is returned in case of an error, otherwise list of CagdCrvStruct. M * * * PARAMETERS: M * Srf: To extract isoparametric curves from. M * NumOfIsocurves: In each (U or V) direction. M * * * RETURN VALUE: M * CagdCrvStruct *: List of extracted isoparametric curves. These curves M * inherit the order and continuity of the original Srf. M * NULL is returned in case of an error. M * * * SEE ALSO: M * BspSrf2PCurves, BzrSrf2Curves M * * * KEYWORDS: M * SymbSrf2Curves, curves, isoparametric curves M *****************************************************************************/ CagdCrvStruct *SymbSrf2Curves(CagdSrfStruct *Srf, int NumOfIsocurves[2]) { switch (Srf -> GType) { case CAGD_SBEZIER_TYPE: return BzrSrf2Curves(Srf, NumOfIsocurves); case CAGD_SBSPLINE_TYPE: return BspSrf2Curves(Srf, NumOfIsocurves); case CAGD_SPOWER_TYPE: SYMB_FATAL_ERROR(SYMB_ERR_POWER_NO_SUPPORT); return NULL; default: SYMB_FATAL_ERROR(SYMB_ERR_UNDEF_SRF); return NULL; } } /***************************************************************************** * DESCRIPTION: M * Routine to approx. a single curve as a polyline with TolSamples M * samples/tolerance. Polyline is always E3 CagdPolylineStruct type. M * NULL is returned in case of an error, otherwise CagdPolylineStruct. M * * * PARAMETERS: M * Crv: To approximate as a polyline. M * TolSamples: Tolerance of approximation error (Method = 2) or M * Number of samples to compute on polyline (Method = 0, 1). M * Method: 0 - TolSamples are set uniformly in parametric space, M * 1 - TolSamples are set optimally, considering the M * isocurve's curvature. M * 2 - TolSamples sets the maximum error allowed between the M * piecewise linear approximation and original curve. M * OptiLin: If TRUE, optimize linear curves. M * * * RETURN VALUE: M * CagdPolylineStruct *: A polyline representing the piecewise linear M * approximation from, or NULL in case of an error. M * * * SEE ALSO: M * BspCrv2Polyline, BzrCrv2Polyline, IritCurve2Polylines M * * * KEYWORDS: M * SymbCrv2Polyline, piecewise linear approximation, polyline M *****************************************************************************/ CagdPolylineStruct *SymbCrv2Polyline(CagdCrvStruct *Crv, CagdRType TolSamples, SymbCrvApproxMethodType Method, CagdBType OptiLin) { switch (Method) { case SYMB_CRV_APPROX_TOLERANCE: return SymbCrv2OptiTlrncPolyline(Crv, TolSamples); case SYMB_CRV_APPROX_CURVATURE: if (Crv -> Order > 2) return SymbCrv2OptiCrvtrPolyline(Crv, (int) TolSamples); /* else do uniform sampling on linear curves. */ default: case SYMB_CRV_APPROX_UNIFORM: switch (Crv -> GType) { case CAGD_CBEZIER_TYPE: return BzrCrv2Polyline(Crv, (int) TolSamples); case CAGD_CBSPLINE_TYPE: return BspCrv2Polyline(Crv, (int) TolSamples, NULL, OptiLin); case CAGD_CPOWER_TYPE: SYMB_FATAL_ERROR(SYMB_ERR_POWER_NO_SUPPORT); return NULL; default: SYMB_FATAL_ERROR(SYMB_ERR_UNDEF_CRV); return NULL; } } } /***************************************************************************** * DESCRIPTION: * * Routine to convert a single curve to piecewise linear polyline. * * Polyline is always E3 of CagdPolylineStruct type. * * Curve is adaptively sampled and result is guaranteed to be within * * Tolerance from the real curve. * NULL is returned in case of an error, otherwise CagdPolylineStruct. * * * * PARAMETERS: * * Crv: To approximate as a polyline. * * Tolerance: Maximal distance between the curve and its piecewise * * linear approximation. * * * * RETURN VALUE: * * CagdPolylineStruct *: A polyline close within Tolerance to Crv. * *****************************************************************************/ static CagdPolylineStruct *SymbCrv2OptiTlrncPolyline(CagdCrvStruct *Crv, CagdRType Tolerance) { CagdCrvStruct *OpenEndCrv = CAGD_IS_BSPLINE_CRV(Crv) && !BspCrvHasOpenEC(Crv) ? BspCrvOpenEnd(Crv) : Crv; CagdPtStruct *Pt, *PtList = SymbCrv2OptiTlrncPolyAux(OpenEndCrv, Tolerance, TRUE); int PtListLen = CagdListLength(PtList); CagdPolylineStruct *Poly = PtListLen == 0 ? NULL : CagdPolylineNew(PtListLen + 1); if (Poly != NULL) { int i; for (Pt = PtList, i = 0; Pt != NULL; Pt = Pt -> Pnext, i++) { PT_COPY(Poly -> Polyline[i].Pt, Pt -> Pt); } CagdPtFreeList(PtList); /* Add the last point */ CagdCoerceToE3(Poly -> Polyline[PtListLen].Pt, OpenEndCrv -> Points, OpenEndCrv -> Length - 1, OpenEndCrv -> PType); } if (OpenEndCrv != Crv) CagdCrvFree(OpenEndCrv); return Poly; } /***************************************************************************** * DESCRIPTION: * * Auxiliary function of SymbCrv2OptiTlrncPolyline. * * Gets a curve and test if a line from first point to last point is close * * enough (less than Tolerance) to all other control points. Otherwise, * * the curve is subdivided and this function recurses on the two sub curves. * * Last point of curve is never concatenated onto the returned list. * * * * PARAMETERS: * * Crv: To approximate as a polyline. * * Tolerance: Maximal distance between the curve and its piecewise * * linear approximation. * * AddFirstPt: If TRUE, first point on curve is also added. * * * RETURN VALUE: * * CagdPtStruct *: A list of points approximating Crv to within Tolerance. * *****************************************************************************/ static CagdPtStruct *SymbCrv2OptiTlrncPolyAux(CagdCrvStruct *Crv, CagdRType Tolerance, CagdBType AddFirstPt) { CagdPType LineOrigin, CtlPt; CagdVType LineDir; CagdCrvStruct *E3Crv = CagdCoerceCrvTo(Crv, CAGD_PT_E3_TYPE); CagdRType **Points = E3Crv -> Points; int i, Len = Crv -> Length; CagdPtStruct *RetPtList = AddFirstPt ? CagdPtNew() : NULL; for (i = 1; i <= 3; i++) { int i1 = i - 1; LineOrigin[i1] = Points[i][0]; LineDir[i1] = Points[i][Len - 1] - LineOrigin[i1]; } if (AddFirstPt) PT_COPY(RetPtList -> Pt, LineOrigin); if (PT_SQR_LENGTH(LineDir) < Tolerance) { /* Any direction would do... */ PT_RESET(LineDir); LineDir[2] = 1.0; } for (i = 1; i < Len - 1; i++) { CtlPt[0] = Points[1][i]; CtlPt[1] = Points[2][i]; CtlPt[2] = Points[3][i]; if (CGDistPointLine(CtlPt, LineOrigin, LineDir) > Tolerance) break; } CagdCrvFree(E3Crv); if (i < Len - 1) { /* Tolerance has not been met. */ CagdCrvStruct *Crv1, *Crv2; CagdRType t; CagdPtStruct *RetPtList1, *RetPtList2; if (CAGD_IS_BSPLINE_CRV(Crv) && Crv -> Length > Crv -> Order) { t = Crv -> KnotVector[(Crv -> Length + Crv -> Order) / 2]; } else { CagdRType TMin, TMax; CagdCrvDomain(Crv, &TMin, &TMax); t = (TMin + TMax) / 2.0; } Crv1 = CagdCrvSubdivAtParam(Crv, t); Crv2 = Crv1 -> Pnext; Crv1 -> Pnext = NULL; RetPtList1 = SymbCrv2OptiTlrncPolyAux(Crv1, Tolerance, FALSE); RetPtList2 = SymbCrv2OptiTlrncPolyAux(Crv2, Tolerance, TRUE); if (RetPtList == NULL) RetPtList = CagdListAppend(RetPtList1, RetPtList2); else RetPtList -> Pnext = CagdListAppend(RetPtList1, RetPtList2); CagdCrvFree(Crv1); CagdCrvFree(Crv2); } return RetPtList; } /***************************************************************************** * DESCRIPTION: * * Routine to convert a single curve to polyline with SamplesPerCurve * * samples, using the curvature field of the curve. * * Polyline is always E3 of CagdPolylineStruct type. * * Curve is sampled at optimal locations as to minimize the L-infinity * * error between the curve and its polyline approximation. * * NULL is returned in case of an error, otherwise CagdPolylineStruct. * * * * PARAMETERS: * * Crv: To approiximate as a polyline. * * SamplesPerCurve: Number of samples one can take off the curve. * * * * RETURN VALUE: * * CagdPolylineStruct *: A polyline with SamplesPerCurve samples that * * approixmates Crv. * *****************************************************************************/ static CagdPolylineStruct *SymbCrv2OptiCrvtrPolyline(CagdCrvStruct *Crv, int SamplesPerCurve) { int i; CagdRType *TVals; CagdPolylineStruct *P = CagdPolylineNew(SamplesPerCurve); CagdCrvStruct *CTmp; CagdPolylnStruct *NewPolyline = P -> Polyline; GlblCrvtrCrv = SymbCrv3DCurvatureSqr(Crv); CTmp = CagdCrvDerive(Crv); GlblDeriv1MagSqrCrv = SymbCrvDotProd(CTmp, CTmp); CagdCrvDomain(Crv, &GlblCrvtrCrvTMin, &GlblCrvtrCrvTMax); TVals = DistPoint1DWithEnergy(SamplesPerCurve, GlblCrvtrCrvTMin, GlblCrvtrCrvTMax, CURVE_PTS_DIST_RESOLUTION, CrvCurvatureEvalFunc); for (i = 0; i < SamplesPerCurve; i++) { /* Convert to E3 polyline. */ RealType *R = CagdCrvEval(Crv, TVals[i]); CagdCoerceToE3(NewPolyline[i].Pt, &R, -1, Crv -> PType); } CagdCrvFree(GlblCrvtrCrv); CagdCrvFree(GlblDeriv1MagSqrCrv); IritFree((VoidPtr) TVals); return P; } /***************************************************************************** * DESCRIPTION: * * Evaluation function of curvature square. This function should return the * * square root of the curvature, scaled by the arclength using GlblCrvtrCrv * * GlblDeriv1MagSqrCrv that contain curvature square and arclength sqaure. * * * * PARAMETERS: * * t: Parameter at which to evalate the global curvature field. * * * * RETURN VALUE: * * RealType: Rstimated curvature square. * *****************************************************************************/ static RealType CrvCurvatureEvalFunc(RealType t) { CagdRType CrvtrSqr, MagSqr, *R; if (t < GlblCrvtrCrvTMin) t = GlblCrvtrCrvTMin; if (t > GlblCrvtrCrvTMax) t = GlblCrvtrCrvTMax; R = CagdCrvEval(GlblCrvtrCrv, t); CrvtrSqr = fabs( R[1] / R[0] ); R = CagdCrvEval(GlblDeriv1MagSqrCrv, t); MagSqr = GlblDeriv1MagSqrCrv -> PType == CAGD_PT_E1_TYPE ? R[1] : R[1] / R[0]; return sqrt( sqrt( CrvtrSqr ) * MagSqr ); }