/****************************************************************************** * Bzr2Poly.c - Bezier to polygon/polylines conversion routines. * ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by Gershon Elber, Mar. 90. * ******************************************************************************/ #include "cagd_loc.h" #define VEC_FIELD_TRIES 10 #define VEC_FIELD_START_STEP 1e-6 /***************************************************************************** * DESCRIPTION: M * Routine to convert a single Bezier surface to set of triangles M * approximating it. FineNess is a fineness control on result and the larger M t is more triangles may result. A value of 10 is a good start 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 * BspSrf2Polygons, IritSurface2Polygons, IritTrimSrf2Polygons, M * SymbSrf2Polygons, TrimSrf2Polygons, CagdSrf2Polygons M * * * KEYWORDS: M * BzrSrf2Polygons, polygonization, surface approximation M *****************************************************************************/ CagdPolygonStruct *BzrSrf2Polygons(CagdSrfStruct *Srf, int FineNess, CagdBType ComputeNormals, CagdBType FourPerFlat, CagdBType ComputeUV) { int i, j, FineNessU1, FineNessV1, FineNessU, FineNessV, BaseIndex; char *Str; CagdRType t, *Pt, UMin, UMax, VMin, VMax; CagdPointType PType = Srf -> PType; CagdPtStruct PtCenter, *Pt1, *Pt2, *Pt3, *Pt4, *PtMesh, *PtMeshPtr; CagdUVStruct UVCenter, *UVMeshPtr, *UV1 = NULL, *UV2 = NULL, *UV3 = NULL, *UV4 = NULL, *UVMesh = NULL; CagdVecStruct NlCenter, *PtNrmlPtr, *Nl1 = NULL, *Nl2 = NULL, *Nl3 = NULL, *Nl4 = NULL, *PtNrml = NULL; CagdPolygonStruct *Poly, *PolyHead = NULL; if (!CAGD_IS_BEZIER_SRF(Srf)) return NULL; if ((Str = AttrGetStrAttrib(Srf -> Attr, "bsp_domain")) == NULL || #ifdef IRIT_DOUBLE sscanf(Str, "%lf %lf %lf %lf", &UMin, &UMax, &VMin, &VMax) != 4) { #else sscanf(Str, "%f %f %f %f", &UMin, &UMax, &VMin, &VMax) != 4) { #endif /* IRIT_DOUBLE */ UMin = VMin = 0.0; UMax = VMax = 1.0; } /* Simple heuristic to estimate how many samples to compute. */ FineNessU = Srf -> UOrder * FineNess / 10; FineNessV = Srf -> VOrder * FineNess / 10; if ((t = AttrGetRealAttrib(Srf -> Attr, "u_resolution")) < IP_ATTR_BAD_REAL) FineNessU = (int) (FineNessU * t); if ((t = AttrGetRealAttrib(Srf -> Attr, "v_resolution")) < IP_ATTR_BAD_REAL) FineNessV = (int) (FineNessV * t); if (FineNessU < 2) FineNessU = 2; if (FineNessV < 2) FineNessV = 2; switch (_CagdLin2Poly) { case CAGD_REG_POLY_PER_LIN: break; case CAGD_ONE_POLY_PER_LIN: if (Srf -> UOrder == 2) FineNessU = 2; if (Srf -> VOrder == 2) FineNessV = 2; break; case CAGD_ONE_POLY_PER_COLIN: break; } FineNessU1 = FineNessU - 1; FineNessV1 = FineNessV - 1; /* Allocate a mesh to hold all vertices so common vertices need not be */ /* Evaluated twice, and evaluate the surface at these mesh points. */ PtMeshPtr = PtMesh = CagdPtArrayNew(FineNessU * FineNessV); for (i = 0; i < FineNessU; i++) for (j = 0; j < FineNessV; j++) { Pt = BzrSrfEvalAtParam(Srf, ((CagdRType) i) / FineNessU1, ((CagdRType) j) / FineNessV1); CagdCoerceToE3(PtMeshPtr -> Pt, &Pt, -1, PType); PtMeshPtr++; } if (ComputeNormals) { PtNrmlPtr = PtNrml = CagdVecArrayNew(FineNessU * FineNessV); for (i = 0; i < FineNessU; i++) for (j = 0; j < FineNessV; j++) { Nl1 = BzrSrfNormal(Srf, ((CagdRType) i) / FineNessU1, ((CagdRType) j) / FineNessV1, TRUE); if (PT_LENGTH(Nl1 -> Vec) < IRIT_UEPS) { int k = 0; CagdRType U, V, UMin, UMax, VMin, VMax, UMid, VMid, Step = VEC_FIELD_START_STEP; CagdSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax); UMid = (UMin + UMax) / 2; VMid = (VMin + VMax) / 2; U = ((CagdRType) i) / FineNessU1; V = ((CagdRType) j) / FineNessV1; while (PT_LENGTH(Nl1 -> Vec) < IRIT_UEPS && k++ < VEC_FIELD_TRIES) { U += U < UMid ? Step : -Step; V += V < VMid ? Step : -Step; Step *= 2.0; Nl1 = BzrSrfNormal(Srf, U, V, TRUE); } if (k >= VEC_FIELD_TRIES) CAGD_FATAL_ERROR(CAGD_ERR_CANNOT_COMP_VEC_FIELD); } CAGD_COPY_VECTOR(*PtNrmlPtr, *Nl1); PtNrmlPtr++; } } if (ComputeUV) { UVMeshPtr = UVMesh = CagdUVArrayNew(FineNessU * FineNessV); for (i = 0; i < FineNessU; i++) for (j = 0; j < FineNessV; j++) { UVMeshPtr -> UV[0] = UMin + (UMax - UMin) * ((CagdRType) i) / FineNessU1; UVMeshPtr -> UV[1] = VMin + (VMax - VMin) * ((CagdRType) j) / FineNessU1; UVMeshPtr++; } } /* Now that we have the mesh, create the polygons. */ for (i = 0; i < FineNessU1; i++) for (j = 0; j < FineNessV1; j++) { BaseIndex = i * FineNessV + j; Pt1 = &PtMesh[BaseIndex]; /* Cache the four flat corners. */ Pt2 = &PtMesh[BaseIndex + 1]; Pt3 = &PtMesh[BaseIndex + FineNessV + 1]; Pt4 = &PtMesh[BaseIndex + FineNessV]; if (ComputeNormals) { Nl1 = &PtNrml[BaseIndex]; Nl2 = &PtNrml[BaseIndex + 1]; Nl3 = &PtNrml[BaseIndex + FineNessV + 1]; Nl4 = &PtNrml[BaseIndex + FineNessV]; } if (ComputeUV) { UV1 = &UVMesh[BaseIndex]; UV2 = &UVMesh[BaseIndex + 1]; UV3 = &UVMesh[BaseIndex + FineNessV + 1]; UV4 = &UVMesh[BaseIndex + FineNessV]; } if (FourPerFlat) { /* Eval middle point and create 4 triangles. */ Pt = BzrSrfEvalAtParam(Srf, (i + 0.5) / FineNessU1, (j + 0.5) / FineNessV1); CagdCoerceToE3(PtCenter.Pt, &Pt, -1, PType); if (ComputeNormals) { /* Average the four normals to find the middle one. */ CAGD_COPY_VECTOR(NlCenter, *Nl1); CAGD_ADD_VECTOR(NlCenter, *Nl2); CAGD_ADD_VECTOR(NlCenter, *Nl3); CAGD_ADD_VECTOR(NlCenter, *Nl4); CAGD_NORMALIZE_VECTOR(NlCenter); } if (ComputeUV) { UVCenter.UV[0] = (UV1 -> UV[0] + UV2 -> UV[0] + UV3 -> UV[0] + UV4 -> UV[0]) / 4.0; UVCenter.UV[1] = (UV1 -> UV[1] + UV2 -> UV[1] + UV3 -> UV[1] + UV4 -> UV[1]) / 4.0; } Poly = _CagdMakePolygon(ComputeNormals, ComputeUV, Pt1, Pt2, &PtCenter, Nl1, Nl2, &NlCenter, UV1, UV2, &UVCenter); if (Poly) LIST_PUSH(Poly, PolyHead); Poly = _CagdMakePolygon(ComputeNormals, ComputeUV, Pt2, Pt3, &PtCenter, Nl2, Nl3, &NlCenter, UV2, UV3, &UVCenter); if (Poly) LIST_PUSH(Poly, PolyHead); Poly = _CagdMakePolygon(ComputeNormals, ComputeUV, Pt3, Pt4, &PtCenter, Nl3, Nl4, &NlCenter, UV3, UV4, &UVCenter); if (Poly) LIST_PUSH(Poly, PolyHead); Poly = _CagdMakePolygon(ComputeNormals, ComputeUV, Pt4, Pt1, &PtCenter, Nl4, Nl1, &NlCenter, UV4, UV1, &UVCenter); if (Poly) LIST_PUSH(Poly, PolyHead); } else { /* Only two along the diagonal... */ Poly = _CagdMakePolygon(ComputeNormals, ComputeUV, Pt1, Pt2, Pt3, Nl1, Nl2, Nl3, UV1, UV2, UV3); if (Poly) LIST_PUSH(Poly, PolyHead); Poly = _CagdMakePolygon(ComputeNormals, ComputeUV, Pt3, Pt4, Pt1, Nl3, Nl4, Nl1, UV3, UV4, UV1); if (Poly) LIST_PUSH(Poly, PolyHead); } } CagdPtArrayFree(PtMesh, FineNessU * FineNessV); if (ComputeNormals) CagdVecArrayFree(PtNrml, FineNessU * FineNessV); if (ComputeUV) CagdUVArrayFree(UVMesh, FineNessU * FineNessV); return PolyHead; } /***************************************************************************** * DESCRIPTION: M * Routine to convert a single Bezier surface to NumOfIsolines polylines M * in each parametric direction with SamplesPerCurve in each isoparametric M * curve. M * Polyline are always E3 of CagdPolylineStruct type. M * Iso parametric curves are sampled equally spaced in parametric space. M * NULL is returned in case of an error, otherwise list of M * CagdPolylineStruct. M * * * PARAMETERS: M * Srf: Srf to extract isoparametric curves from. M * NumOfIsocurves: To extarct from Srf in each (U or V) direction. M * SamplesPerCurve: Fineness control on piecewise linear curve M * approximation. M * * * RETURN VALUE: M * CagdPolylineStruct *: List of polygons representing a piecewise linear M * approximation of the extracted isoparamteric M * curves or NULL is case of an error. M * * * SEE ALSO: M * BzrCrv2Polyline, BspSrf2Polylines, IritSurface2Polylines, M * IritTrimSrf2Polylines, SymbSrf2Polylines, TrimSrf2Polylines M * CagdSrf2Polylines M * * * KEYWORDS: M * BzrSrf2Polylines, polylines, isoparametric curves M *****************************************************************************/ CagdPolylineStruct *BzrSrf2Polylines(CagdSrfStruct *Srf, int NumOfIsocurves[2], int SamplesPerCurve) { int i; CagdRType t; CagdCrvStruct *Crv; CagdPolylineStruct *Poly, *PolyList = NULL; if (!CAGD_IS_BEZIER_SRF(Srf)) return NULL; /* Make sure requested format is something reasonable. */ if (SamplesPerCurve < 2) SamplesPerCurve = 2; if (NumOfIsocurves[0] < 2) NumOfIsocurves[0] = 2; if (NumOfIsocurves[1] <= 0) NumOfIsocurves[1] = NumOfIsocurves[0]; else if (NumOfIsocurves[1] < 2) NumOfIsocurves[1] = 2; for (i = 0; i < NumOfIsocurves[0]; i++) { t = ((CagdRType) i) / (NumOfIsocurves[0] - 1); if (t > 1.0) t = 1.0; /* In case of round off error. */ Crv = BzrSrfCrvFromSrf(Srf, t, CAGD_CONST_U_DIR); Poly = BzrCrv2Polyline(Crv, SamplesPerCurve); Poly -> Pnext = PolyList; PolyList = Poly; CagdCrvFree(Crv); } for (i = 0; i < NumOfIsocurves[1]; i++) { t = ((CagdRType) i) / (NumOfIsocurves[1] - 1); if (t > 1.0) t = 1.0; /* In case of round off error. */ Crv = BzrSrfCrvFromSrf(Srf, t, CAGD_CONST_V_DIR); Poly = BzrCrv2Polyline(Crv, SamplesPerCurve); Poly -> Pnext = PolyList; PolyList = Poly; CagdCrvFree(Crv); } return PolyList; } /***************************************************************************** * DESCRIPTION: M * Routine to extract from a bezier 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 reach (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 * BzrSrf22Polylines, BspSrf2PCurves, SymbSrf2Curves M * * * KEYWORDS: M * BzrSrf2Curves, curves, isoparametric curves M *****************************************************************************/ CagdCrvStruct *BzrSrf2Curves(CagdSrfStruct *Srf, int NumOfIsocurves[2]) { int i; CagdRType t; CagdCrvStruct *Crv, *CrvList = NULL; if (!CAGD_IS_BEZIER_SRF(Srf)) return NULL; /* Make sure requested format is something reasonable. */ if (NumOfIsocurves[0] < 2) NumOfIsocurves[0] = 2; if (NumOfIsocurves[1] <= 0) NumOfIsocurves[1] = NumOfIsocurves[0]; else if (NumOfIsocurves[1] < 2) NumOfIsocurves[1] = 2; for (i = 0; i < NumOfIsocurves[0]; i++) { t = ((CagdRType) i) / (NumOfIsocurves[0] - 1); if (t > 1.0) t = 1.0; /* In case of round off error. */ Crv = CagdCrvFromSrf(Srf, t, CAGD_CONST_U_DIR); Crv -> Pnext = CrvList; CrvList = Crv; } for (i = 0; i < NumOfIsocurves[1]; i++) { t = ((CagdRType) i) / (NumOfIsocurves[1] - 1); if (t > 1.0) t = 1.0; /* In case of round off error. */ Crv = CagdCrvFromSrf(Srf, t, CAGD_CONST_V_DIR); Crv -> Pnext = CrvList; CrvList = Crv; } return CrvList; } /***************************************************************************** * DESCRIPTION: M * Routine to approx. a single Bezier curve as a polyline with M * SamplesPerCurve samples. Polyline is always E3 CagdPolylineStruct type. M * Curve is sampled equally spaced in parametric space. M * NULL is returned in case of an error, otherwise CagdPolylineStruct. M * * * PARAMETERS: M * Crv: To approximate as a polyline. M * SamplesPerCurve: Number of samples to approximate with. 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, BzrSrf2Polylines, IritCurve2Polylines, M * SymbCrv2Polyline M * * * KEYWORDS: M * BzrCrv2Polyline, piecewise linear approximation, polyline M *****************************************************************************/ CagdPolylineStruct *BzrCrv2Polyline(CagdCrvStruct *Crv, int SamplesPerCurve) { int i, j, IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv), MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType); CagdRType *Polyline[CAGD_MAX_PT_SIZE], Scaler; CagdPolylnStruct *NewPolyline; CagdPolylineStruct *P; if (!CAGD_IS_BEZIER_CRV(Crv)) return NULL; /* Make sure requested format is something reasonable. */ if (SamplesPerCurve < 2 || Crv -> Order == 2) SamplesPerCurve = 2; P = CagdPolylineNew(SamplesPerCurve); NewPolyline = P -> Polyline; /* Allocate temporary memory to hold evaluated curve. */ for (i = 0; i < CAGD_MAX_PT_SIZE; i++) Polyline[i] = (CagdRType *) IritMalloc(sizeof(CagdRType) * SamplesPerCurve); if (MaxCoord > 3) MaxCoord = 3; BzrCrvEvalToPolyline(Crv, SamplesPerCurve, Polyline); for (i = SamplesPerCurve - 1; i >= 0; i--) { /* Convert to E3 polyline. */ if (IsNotRational) Scaler = 1.0; else Scaler = Polyline[0][i]; for (j = 0; j < MaxCoord; j++) NewPolyline[i].Pt[j] = Polyline[j+1][i] / Scaler; for (j = MaxCoord; j < 3; j++) NewPolyline[i].Pt[j] = 0.0; } for (i = 0; i < CAGD_MAX_PT_SIZE; i++) IritFree((VoidPtr) Polyline[i]); return P; }