/****************************************************************************** * Cagd2Ply.c - Surfaces to polygons adaptive conversion routines. * ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by Gershon Elber, Mar. 2001. * ******************************************************************************/ #include "cagd_loc.h" #include "geom_lib.h" #define CAGD_RECT_ALLOC_BLOCK 100 #define CAGD_MAX_SUBDIV_ONE_DIR 10 #define CAGD_DISCONT_NORMAL_EPS 1e-6 #define SRF_ADAP_FIX_DISCONT_NRML(SrfPt) \ (SrfPt -> Nrml[0] == IRIT_INFNTY ? NULL : SrfPt -> Nrml) #ifdef DEBUG IRIT_SET_DEBUG_PARAMETER(_DebugDumpSubdivMinSize, FALSE); STATIC_DATA int GlblSubdivMinSize = CAGD2PLY_MAX_SUBDIV_INDEX; #endif /* DEBUG */ STATIC_DATA int CagdSrf2PolyComputeNormals = FALSE, CagdSrf2PolyComputeUV = FALSE; STATIC_DATA VoidPtr GlblSrfPtEvalCache = NULL; STATIC_DATA CagdSrfErrorFuncType CagdSrfAdap2PolyErrFunc = NULL; STATIC_DATA CagdSrfAdapPolyGenFuncType CagdSrfAdapPolyGenFunc = NULL; STATIC_DATA CagdSrfAdapAuxDataFuncType CagdSrfAdapAuxDataFunc = NULL; STATIC_DATA char GlblDiscontUVals[CAGD2PLY_MAX_SUBDIV_INDEX + 1], GlblDiscontVVals[CAGD2PLY_MAX_SUBDIV_INDEX + 1]; STATIC_DATA CagdRType GlblUMin = 0.0, GlblUMax = 0.0, GlblVMin = 0.0, GlblVMax = 0.0, GlblSrfAdapTolerance = 0.01, GlblSubdivUVals[CAGD2PLY_MAX_SUBDIV_INDEX + 1], GlblSubdivVVals[CAGD2PLY_MAX_SUBDIV_INDEX + 1]; STATIC_DATA CagdSrfPtStruct *GlblSrfPtFreeList = NULL, *GlblSrfPtSamples[CAGD2PLY_MAX_SUBDIV_INDEX + 1] [CAGD2PLY_MAX_SUBDIV_INDEX + 1]; STATIC_DATA CagdSrfAdapRectStruct *GlblRectFreeList = NULL, *GlblRectList = NULL; STATIC_DATA CagdSrfStruct *GlblSrf = NULL; static void CagdSrfAdap2PolygonsAux(CagdSrfStruct *Srf, int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData); static void CagdSrfAdap2PolygonsAux2(CagdSrfStruct *Srf, RealType SrfErr, int UVBias, int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData); static CagdPolygonStruct *CagdSrfAdapRect2Polys(CagdSrfStruct *Srf, CagdSrfAdapRectStruct *Rect); static CagdSrfAdapRectStruct *CagdSrfAdap2PolyAllocRect(int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData, CagdRType Err); static void CagdSrfAdap2PolysFlat(CagdSrfStruct *Srf, CagdRType Err, int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData); static void CagdSrfAdapSampleActivate(CagdSrfStruct *Srf, int UIndex, int VIndex, int IsUMin, int IsVMin, CagdRType u, CagdRType v); static CagdRType *EvaluateNormalBlendedUV(CagdRType *UV1, CagdRType *UV2, CagdRType *UV3); static CagdPolygonStruct *CagdGenAdapTriangle(CagdBType ComputeNormals, CagdBType ComputeUV, CagdRType *Pt1, CagdRType *Pt2, CagdRType *Pt3, CagdRType *Nl1, CagdRType *Nl2, CagdRType *Nl3, CagdRType *UV1, CagdRType *UV2, CagdRType *UV3, CagdBType *GenPoly); static CagdPolygonStruct *CagdGenAdapRectangle(CagdBType ComputeNormals, CagdBType ComputeUV, CagdRType *Pt1, CagdRType *Pt2, CagdRType *Pt3, CagdRType *Pt4, CagdRType *Nl1, CagdRType *Nl2, CagdRType *Nl3, CagdRType *Nl4, CagdRType *UV1, CagdRType *UV2, CagdRType *UV3, CagdRType *UV4, CagdBType *GenPoly); static void CorrectUVBoundaries(CagdRType **UVs, int n); /***************************************************************************** * DESCRIPTION: M * Sets the surface approximation error function. The error function M * will return a negative value if this patch is flat enough, and positive M * value if flat enough. M * Either case, the magnitude will equal to the actual error. M * * * PARAMETERS: M * Func: New function to use, NULL to disable. M * * * RETURN VALUE: M * CagdSrfErrorFuncType: Old value of function. M * * * SEE ALSO: M * CagdSrfAdap2Polygons, CagdSrf2PolyAdapSetAuxDataFunc, M * CagdSrf2PolyAdapSetPolyGenFunc M * * * KEYWORDS: M * CagdSrf2PolyAdapSetErrFunc M *****************************************************************************/ CagdSrfErrorFuncType CagdSrf2PolyAdapSetErrFunc(CagdSrfErrorFuncType Func) { CagdSrfErrorFuncType OldFunc = CagdSrfAdap2PolyErrFunc; CagdSrfAdap2PolyErrFunc = Func; return OldFunc; } /***************************************************************************** * DESCRIPTION: M * Sets the surface approximation auxiliary function. This function M * will be invoked on each subdivision step during the approximation process, M * for auxiliary processing that are application specific. M * * * PARAMETERS: M * Func: New function to use, NULL to disable. M * * * RETURN VALUE: M * CagdSrfAdapAuxDataFuncType: Old value of function. M * * * SEE ALSO: M * CagdSrfAdap2Polygons, CagdSrf2PolyAdapSetPolyGenFunc, M * CagdSrf2PolyAdapSetErrFunc M * * * KEYWORDS: M * CagdSrf2PolyAdapSetAuxDataFunc M *****************************************************************************/ CagdSrfAdapAuxDataFuncType CagdSrf2PolyAdapSetAuxDataFunc(CagdSrfAdapAuxDataFuncType Func) { CagdSrfAdapAuxDataFuncType OldFunc = CagdSrfAdapAuxDataFunc; CagdSrfAdapAuxDataFunc = Func; return OldFunc; } /***************************************************************************** * DESCRIPTION: M * Sets the function to convert flat surface rectangle domains into M * polygons. M * * * PARAMETERS: M * Func: New function to use, NULL to disable. M * * * RETURN VALUE: M * CagdSrfAdapPolyGenFuncType: Old value of function. M * * * SEE ALSO: M * CagdSrfAdap2Polygons, CagdSrf2PolyAdapSetAuxDataFunc, M * CagdSrf2PolyAdapSetErrFunc M * * * KEYWORDS: M * CagdSrf2PolyAdapSetPolyGenFunc M *****************************************************************************/ CagdSrfAdapPolyGenFuncType CagdSrf2PolyAdapSetPolyGenFunc(CagdSrfAdapPolyGenFuncType Func) { CagdSrfAdapPolyGenFuncType OldFunc = CagdSrfAdapPolyGenFunc; CagdSrfAdapPolyGenFunc = Func; return OldFunc; } /***************************************************************************** * DESCRIPTION: M * Tolerance evaluation of flatness for given surface. Constructs a plane M * from the four corner points, if possible, and measure distance to rest M * of control points. M * * * PARAMETERS: M * Srf: Surface to test for flatness. M * * * RETURN VALUE: M * CagdRType: Negative value if flat enough, positive if not flat. M * Either case, magnitude will equal to the actual error. M * * * SEE ALSO: M * CagdSrfIsCoplanarCtlMesh, CagdSrfIsLinearBndryCtlMesh, M * CagdSrfAdap2Polygons M * * * KEYWORDS: M * CagdSrfAdap2PolyDefErrFunc M *****************************************************************************/ CagdRType CagdSrfAdap2PolyDefErrFunc(CagdSrfStruct *Srf) { CagdRType R1 = CagdSrfIsCoplanarCtlMesh(Srf), R2 = CagdSrfIsLinearBndryCtlMesh(Srf), R = MAX(R1, R2); return R > GlblSrfAdapTolerance ? R : -R; } /***************************************************************************** * DESCRIPTION: M * evaluate the linearity of the boundary of the control mesh for a given M * surface. M * Constructs a line for each boundary, if possible, and measure distance M * to rest of control points on that boundary. M * * * PARAMETERS: M * Srf: Surface to test for linearity of of its control mesh's boundary. M * * * RETURN VALUE: M * CagdRType: A bound on the distance between the control mesh boundary M * and a linear rectangle connecting the four corners. M * * * SEE ALSO: M * CagdSrfAdap2Polygons, CagdSrfAdap2PolyDefErrFunc M * * * KEYWORDS: M * CagdSrfIsLinearBndryCtlMesh M *****************************************************************************/ CagdRType CagdSrfIsLinearBndryCtlMesh(CagdSrfStruct *Srf) { int i, V1Zero, V2Zero, ULen1 = Srf -> ULength - 1, VLen1 = Srf -> VLength - 1; CagdPointType PType = Srf -> PType; CagdPType Pt, P11, P12, P21, P22; CagdVType V1, V2, VTmp1, VTmp2; CagdRType DSqr, MaxDSqr = 0.0, **Points = Srf -> Points; /* Get the four corner points. */ CagdCoerceToE3(P11, Points, CAGD_MESH_UV(Srf, 0, 0), PType); CagdCoerceToE3(P12, Points, CAGD_MESH_UV(Srf, ULen1, 0), PType); CagdCoerceToE3(P21, Points, CAGD_MESH_UV(Srf, 0, VLen1), PType); CagdCoerceToE3(P22, Points, CAGD_MESH_UV(Srf, ULen1, VLen1), PType); /* UMin/UMax boundary. */ VEC_SUB(V1, P21, P11); V1Zero = PT_APX_EQ_ZERO_EPS(V1, IRIT_UEPS); if (!V1Zero) VEC_NORMALIZE(V1); for (i = 1; i < VLen1; i++) { CagdCoerceToE3(Pt, Points, CAGD_MESH_UV(Srf, 0, i), PType); if (V1Zero) DSqr = PT_PT_DIST_SQR(Pt, P21); else { PT_SUB(VTmp1, Pt, P21); CROSS_PROD(VTmp2, VTmp1, V1); DSqr = DOT_PROD(VTmp2, VTmp2); } MaxDSqr = MAX(MaxDSqr, DSqr); } VEC_SUB(V2, P22, P12); V2Zero = PT_APX_EQ_ZERO_EPS(V2, IRIT_UEPS); if (!V2Zero) VEC_NORMALIZE(V2); for (i = 1; i < VLen1; i++) { CagdCoerceToE3(Pt, Points, CAGD_MESH_UV(Srf, ULen1, i), PType); if (V2Zero) DSqr = PT_PT_DIST_SQR(Pt, P22); else { PT_SUB(VTmp1, Pt, P22); CROSS_PROD(VTmp2, VTmp1, V2); DSqr = DOT_PROD(VTmp2, VTmp2); } MaxDSqr = MAX(MaxDSqr, DSqr); } /* VMin/VMax boundary. */ VEC_SUB(V1, P12, P11); V1Zero = PT_APX_EQ_ZERO_EPS(V1, IRIT_UEPS); if (!V1Zero) VEC_NORMALIZE(V1); for (i = 1; i < ULen1; i++) { CagdCoerceToE3(Pt, Points, CAGD_MESH_UV(Srf, i, 0), PType); if (V1Zero) DSqr = PT_PT_DIST_SQR(Pt, P12); else { PT_SUB(VTmp1, Pt, P12); CROSS_PROD(VTmp2, VTmp1, V1); DSqr = DOT_PROD(VTmp2, VTmp2); } MaxDSqr = MAX(MaxDSqr, DSqr); } VEC_SUB(V2, P22, P21); V2Zero = PT_APX_EQ_ZERO_EPS(V2, IRIT_UEPS); if (!V2Zero) VEC_NORMALIZE(V2); for (i = 1; i < ULen1; i++) { CagdCoerceToE3(Pt, Points, CAGD_MESH_UV(Srf, i, VLen1), PType); if (V2Zero) DSqr = PT_PT_DIST_SQR(Pt, P22); else { PT_SUB(VTmp1, Pt, P22); CROSS_PROD(VTmp2, VTmp1, V2); DSqr = DOT_PROD(VTmp2, VTmp2); } MaxDSqr = MAX(MaxDSqr, DSqr); } return sqrt(MaxDSqr); } /***************************************************************************** * DESCRIPTION: M * evaluate the coplanarity of the control mesh for a given surface. M * Constructs a plane from the four corner points, if possible, and measure M * distance to rest of control points. M * * * PARAMETERS: M * Srf: Surface to test for flatness of its control mesh. M * * * RETURN VALUE: M * CagdRType: A bound on the distance between the control points and the M * plane fitted to the four corners. M * * * SEE ALSO: M * CagdSrfAdap2Polygons, CagdSrfAdap2PolyDefErrFunc M * * * KEYWORDS: M * CagdSrfIsCoplanarCtlMesh M *****************************************************************************/ CagdRType CagdSrfIsCoplanarCtlMesh(CagdSrfStruct *Srf) { int i, ULen = Srf -> ULength, VLen = Srf -> VLength; CagdPointType PType = Srf -> PType; CagdPType P, P11, P12, P21, P22; CagdVType V, V1, V2, V3, V4; CagdRType PlnX, PlnY, PlnZ, PlnW, ErrPos = 0.0, ErrNeg = 0.0, **Points = Srf -> Points, *PtsW = Points[0], *PtsX = Points[1], *PtsY = Points[2], *PtsZ = Points[3]; PlaneType Pln; /* Get the four corner points. */ CagdCoerceToE3(P11, Points, CAGD_MESH_UV(Srf, 0, 0), PType); CagdCoerceToE3(P12, Points, CAGD_MESH_UV(Srf, ULen - 1, 0), PType); CagdCoerceToE3(P21, Points, CAGD_MESH_UV(Srf, 0, VLen - 1), PType); CagdCoerceToE3(P22, Points, CAGD_MESH_UV(Srf, ULen - 1, VLen - 1), PType); /* Construct the plane. */ VEC_SUB(V1, P21, P11); VEC_SUB(V2, P11, P12); VEC_SUB(V3, P12, P22); VEC_SUB(V4, P22, P21); CROSS_PROD(Pln, V1, V2); CROSS_PROD(V, V2, V3); VEC_ADD(Pln, Pln, V); CROSS_PROD(V, V3, V4); VEC_ADD(Pln, Pln, V); CROSS_PROD(V, V4, V1); VEC_ADD(Pln, Pln, V); if (PT_EQ_ZERO(Pln)) return IRIT_INFNTY; VEC_NORMALIZE(Pln); PT_COPY(P, P11); PT_ADD(P, P, P12); PT_ADD(P, P, P21); PT_ADD(P, P, P22); PT_SCALE(P, 0.25); PlnX = Pln[0]; PlnY = Pln[1]; PlnZ = Pln[2]; PlnW = -DOT_PROD(Pln, P); /* Go over all control points and test distance. */ if (CAGD_NUM_OF_PT_COORD(PType) > 3) { PType = CAGD_IS_RATIONAL_PT(PType) ? CAGD_PT_P3_TYPE : CAGD_PT_E3_TYPE; } for (i = ULen * VLen; i > 0 ; i--) { CagdRType d, w; switch (PType) { case CAGD_PT_E1_TYPE: d = *PtsX++ * PlnX + PlnW; break; case CAGD_PT_P1_TYPE: if ((w = *PtsW++) == 0.0) w = IRIT_UEPS; d = *PtsX++ * PlnX / w + PlnW; break; case CAGD_PT_E2_TYPE: d = *PtsX++ * PlnX + *PtsY++ * PlnY + PlnW; break; case CAGD_PT_P2_TYPE: if ((w = *PtsW++) == 0.0) w = IRIT_UEPS; d = (*PtsX++ * PlnX + *PtsY++ * PlnY) / w + PlnW; break; case CAGD_PT_E3_TYPE: d = *PtsX++ * PlnX + *PtsY++ * PlnY + *PtsZ++ * PlnZ + PlnW; break; case CAGD_PT_P3_TYPE: if ((w = *PtsW++) == 0.0) w = IRIT_UEPS; d = (*PtsX++ * PlnX + *PtsY++ * PlnY + *PtsZ++ * PlnZ) / w + PlnW; break; } if (d > 0) ErrPos = MAX(ErrPos, d); else ErrNeg = MIN(ErrNeg, d); } /* Inflection areas will show up as both negative and positive areas. */ /* Penalize more such areas by adding up positive and negative errors. */ ErrPos -= ErrNeg; return ErrPos; } /***************************************************************************** * DESCRIPTION: M * Routine to convert a single surface to set of polygons approximating M * it. M * Tolerance is a tolerance control on result, typically related to the M * the accuracy of the apporximation. A value of 0.1 is a good rough start. M * NULL is returned in case of an error or use of call back function to get M * a hold over the created polygons, otherwise list of CagdPolygonStruct. M * * * PARAMETERS: M * Srf: To approximate into triangles. M * Tolerance: of approximation - a value that depends on the error M * function used. 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 * AuxSrfData: Optional data structure that will be passed to all M * subdivided sub-surfaces, or NULL if not needed. M * See also CagdSrf2PolyAdapSetAuxDataFunc. M * SrfPtEvalCache: Should we update evaluated points into this cache? M * NULL if not. See IritSearch2DInsertElem. 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 or if use of M * call back function to collect the polygons. M * * * SEE ALSO: M * CagdSrf2PolygonSetErrFunc, CagdSrfAdap2PolyDefErrFunc, M * CagdSrf2PolyAdapSetErrFunc, CagdSrf2PolyAdapSetAuxDataFunc M * CagdSrf2PolyAdapSetPolyGenFunc, BzrSrf2Polygons, CagdSrf2Polygons, M * CagdSrf2Polygons, TrimSrf2Polygons, BspC1Srf2Polygons, CagdSrf2Polygons M * * * KEYWORDS: M * CagdSrfAdap2Polygons, polygonization, surface approximation M *****************************************************************************/ CagdPolygonStruct *CagdSrfAdap2Polygons(CagdSrfStruct *Srf, CagdRType Tolerance, CagdBType ComputeNormals, CagdBType FourPerFlat, CagdBType ComputeUV, VoidPtr AuxSrfData, VoidPtr SrfPtEvalCache) { int i, j; CagdBType NewSrf = FALSE; CagdPolygonStruct *Polys = NULL; CagdSrfStruct *TSrf; CagdSrfAdapRectStruct *Rect; if (CagdSrfAdap2PolyErrFunc == NULL) CagdSrfAdap2PolyErrFunc = CagdSrfAdap2PolyDefErrFunc; if (CagdSrfAdapPolyGenFunc == NULL) CagdSrfAdapPolyGenFunc = CagdSrfAdapRectPolyGen; if (_CagdSrfMakeTriFunc == NULL || _CagdSrfMakeRectFunc == NULL) { _CagdSrfMakeTriFunc = CagdMakeTriangle; _CagdSrfMakeRectFunc = CagdMakeRectangle; } GlblSrf = Srf; # ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugDumpSubdivMinSize) GlblSubdivMinSize = CAGD2PLY_MAX_SUBDIV_INDEX; # endif /* DEBUG */ CagdSrf2PolyComputeNormals = ComputeNormals; CagdSrf2PolyComputeUV = ComputeUV; ZAP_MEM(GlblSrfPtSamples, sizeof(GlblSrfPtSamples)); ZAP_MEM(GlblDiscontUVals, sizeof(GlblDiscontUVals)); ZAP_MEM(GlblDiscontVVals, sizeof(GlblDiscontVVals)); ZAP_MEM(GlblSubdivUVals, sizeof(GlblSubdivUVals)); ZAP_MEM(GlblSubdivVVals, sizeof(GlblSubdivVVals)); GlblSrfPtEvalCache = SrfPtEvalCache ? SrfPtEvalCache : NULL; if (CAGD_IS_BEZIER_SRF(Srf)) { NewSrf = TRUE; Srf = CnvrtBezier2BsplineSrf(Srf); } if (CAGD_IS_PERIODIC_SRF(Srf)) { TSrf = CnvrtPeriodic2FloatSrf(Srf); if (NewSrf) CagdSrfFree(Srf); NewSrf = TRUE; Srf = TSrf; } if (!BspSrfHasOpenEC(Srf)) { TSrf = CnvrtFloat2OpenSrf(Srf); if (NewSrf) CagdSrfFree(Srf); NewSrf = TRUE; Srf = TSrf; } GlblRectList = NULL; GlblSrfAdapTolerance = Tolerance; CagdSrfDomain(Srf, &GlblUMin, &GlblUMax, &GlblVMin, &GlblVMax); /* Find the rectangular domains to form polygons from. */ CagdSrfAdap2PolygonsAux(Srf, 0, CAGD2PLY_MAX_SUBDIV_INDEX, 0, CAGD2PLY_MAX_SUBDIV_INDEX, AuxSrfData); # ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugDumpSubdivMinSize) printf("Global minimal binary subdiv size equal %d\n", GlblSubdivMinSize); # endif /* DEBUG */ /* Preserve closed boundary conditions, if closed. */ if (CagdIsClosedSrf(Srf, CAGD_CONST_U_DIR)) { for (j = 0; j <= CAGD2PLY_MAX_SUBDIV_INDEX; j++) { if (GlblSrfPtSamples[0][j] != NULL && GlblSrfPtSamples[CAGD2PLY_MAX_SUBDIV_INDEX][j] == NULL) GlblSrfPtSamples[CAGD2PLY_MAX_SUBDIV_INDEX][j] = CagdSrfPtCopy(GlblSrfPtSamples[0][j]); else if (GlblSrfPtSamples[CAGD2PLY_MAX_SUBDIV_INDEX][j] != NULL && GlblSrfPtSamples[0][j] == NULL) GlblSrfPtSamples[0][j] = CagdSrfPtCopy(GlblSrfPtSamples[CAGD2PLY_MAX_SUBDIV_INDEX][j]); } } if (CagdIsClosedSrf(Srf, CAGD_CONST_V_DIR)) { for (i = 0; i <= CAGD2PLY_MAX_SUBDIV_INDEX; i++) { if (GlblSrfPtSamples[i][0] != NULL && GlblSrfPtSamples[i][CAGD2PLY_MAX_SUBDIV_INDEX] == NULL) GlblSrfPtSamples[i][CAGD2PLY_MAX_SUBDIV_INDEX] = CagdSrfPtCopy(GlblSrfPtSamples[i][0]); else if (GlblSrfPtSamples[i][CAGD2PLY_MAX_SUBDIV_INDEX] != NULL && GlblSrfPtSamples[i][0] == NULL) GlblSrfPtSamples[i][0] = CagdSrfPtCopy(GlblSrfPtSamples[i][CAGD2PLY_MAX_SUBDIV_INDEX]); } } /* Traverse rect. domains and convert to polygons while closing cracks. */ for (Rect = GlblRectList; Rect != NULL; Rect = Rect -> Pnext) { Polys = (CagdPolygonStruct *) CagdListAppend(Polys, CagdSrfAdapRect2Polys(Srf, Rect)); } /* Chain the Rect list to the freed version. */ if (GlblRectList != NULL) { for (Rect = GlblRectList; Rect -> Pnext != NULL; Rect = Rect -> Pnext); Rect -> Pnext = GlblRectFreeList; GlblRectFreeList = GlblRectList; } /* And free the allocated SrfPt structs. */ for (i = 0; i <= CAGD2PLY_MAX_SUBDIV_INDEX; i++) { for (j = 0; j <= CAGD2PLY_MAX_SUBDIV_INDEX; j++) { if (GlblSrfPtSamples[i][j] != NULL) { GlblSrfPtSamples[i][j] -> Pnext = GlblSrfPtFreeList; GlblSrfPtFreeList = GlblSrfPtSamples[i][j]; } } } if (NewSrf) CagdSrfFree(Srf); return Polys; } /***************************************************************************** * DESCRIPTION: * * Auxiliary function of CagdSrfAdap2Polygons. Assumes Bspline srfs only. * * * * PARAMETERS: * * Srf: Bspline surface to approximate into triangles. * * UIndexBase: 2's power index of base of this U parameteric domain. * * UIndexSize: 2's power size of this U parameteric domain. * * VIndexBase: 2's power index of base of this V parameteric domain. * * VIndexSize: 2's power size of this V parameteric domain. * * AuxSrfData: Optional data structure that will be passed to all * * subdivided sub-surfaces, or NULL if not needed. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void CagdSrfAdap2PolygonsAux(CagdSrfStruct *Srf, int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData) { void *AuxSrf1Data = NULL, *AuxSrf2Data = NULL; RealType SrfErr = CagdSrfAdap2PolyErrFunc(Srf); if (UIndexSize <= 2 || VIndexSize <= 2 || SrfErr <= 0.0) { /* Flat enough. */ CagdSrfAdap2PolysFlat(Srf, -SrfErr, UIndexBase, UIndexSize, VIndexBase, VIndexSize, AuxSrfData); } else if (Srf -> ULength > Srf -> UOrder) { CagdBType IgnoreFirst = FALSE, IgnoreSecond = FALSE; CagdRType t = Srf -> UKnotVector[(Srf -> ULength + Srf -> UOrder) >> 1]; CagdSrfStruct *Srf1 = CagdSrfSubdivAtParam(Srf, t, CAGD_CONST_U_DIR), *Srf2 = Srf1 -> Pnext; if (CagdSrfAdapAuxDataFunc != NULL) { CagdSrfAdapAuxDataFunc(Srf, AuxSrfData, t, CAGD_CONST_U_DIR, Srf1, &AuxSrf1Data, Srf2, &AuxSrf2Data); /* If both NULL, proceed as if no AuxSrfData. If one is NULL, */ /* ignore it. */ if (AuxSrf1Data == NULL && AuxSrf2Data != NULL) IgnoreFirst = TRUE; if (AuxSrf2Data == NULL && AuxSrf1Data != NULL) IgnoreSecond = TRUE; } /* Check if this knot location is also a potential C^1 discont. */ if (BspKnotFindMult(Srf -> UKnotVector, Srf -> UOrder, Srf -> ULength, t) >= Srf -> UOrder - 1 && BspSrfIsC1DiscontAt(Srf, CAGD_CONST_U_DIR, t)) GlblDiscontUVals[UIndexBase + (UIndexSize >> 1)]++; if (!IgnoreFirst) CagdSrfAdap2PolygonsAux(Srf1, UIndexBase, UIndexSize >> 1, VIndexBase, VIndexSize, AuxSrf1Data); if (!IgnoreSecond) CagdSrfAdap2PolygonsAux(Srf2, UIndexBase + (UIndexSize >> 1), UIndexSize >> 1, VIndexBase, VIndexSize, AuxSrf2Data); CagdSrfFreeList(Srf1); } else if (Srf -> VLength > Srf -> VOrder) { CagdBType IgnoreFirst = FALSE, IgnoreSecond = FALSE; CagdRType t = Srf -> VKnotVector[(Srf -> VLength + Srf -> VOrder) >> 1]; CagdSrfStruct *Srf1 = CagdSrfSubdivAtParam(Srf, t, CAGD_CONST_V_DIR), *Srf2 = Srf1 -> Pnext; if (CagdSrfAdapAuxDataFunc != NULL) { CagdSrfAdapAuxDataFunc(Srf, AuxSrfData, t, CAGD_CONST_V_DIR, Srf1, &AuxSrf1Data, Srf2, &AuxSrf2Data); /* If both NULL, proceed as if no AuxSrfData. If one is NULL, */ /* ignore it. */ if (AuxSrf1Data == NULL && AuxSrf2Data != NULL) IgnoreFirst = TRUE; if (AuxSrf2Data == NULL && AuxSrf1Data != NULL) IgnoreSecond = TRUE; } /* Check if this knot location is also a potential C^1 discont. */ if (BspKnotFindMult(Srf -> VKnotVector, Srf -> VOrder, Srf -> VLength, t) >= Srf -> VOrder - 1 && BspSrfIsC1DiscontAt(Srf, CAGD_CONST_V_DIR, t)) GlblDiscontVVals[VIndexBase + (VIndexSize >> 1)]++; if (!IgnoreFirst) CagdSrfAdap2PolygonsAux(Srf1, UIndexBase, UIndexSize, VIndexBase, VIndexSize >> 1, AuxSrf1Data); if (!IgnoreSecond) CagdSrfAdap2PolygonsAux(Srf2, UIndexBase, UIndexSize, VIndexBase + (VIndexSize >> 1), VIndexSize >> 1, AuxSrf2Data); CagdSrfFreeList(Srf1); } else CagdSrfAdap2PolygonsAux2(Srf, SrfErr, 0, UIndexBase, UIndexSize, VIndexBase, VIndexSize, AuxSrfData); } /***************************************************************************** * DESCRIPTION: * * Auxiliary function of CagdSrfAdap2Polygons. Assumes Bspline srfs only * * with no C1 discontinuities. * * * * PARAMETERS: * * Srf: Bspline surface with no discontinuities to approximate * * into triangles. * * SrfErr: Already computed error for Srf. * * UVBias: Bias against U-all or V-all subdivisions. * * UIndexBase: 2's power index of base of this U parameteric domain. * * UIndexSize: 2's power size of this U parameteric domain. * * VIndexBase: 2's power index of base of this V parameteric domain. * * VIndexSize: 2's power size of this V parameteric domain. * * AuxSrfData: Optional data structure that will be passed to all * * subdivided sub-surfaces, or NULL if not needed. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void CagdSrfAdap2PolygonsAux2(CagdSrfStruct *Srf, RealType SrfErr, int UVBias, int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData) { if (UIndexSize <= 2 || VIndexSize <= 2 || SrfErr <= 0.0) { /* Flat enough. */ # ifdef DEBUG { IRIT_SET_IF_DEBUG_ON_PARAMETER(_DebugCagd2PlyGridRes, FALSE) { if (UIndexSize <= 2 || VIndexSize <= 2) fprintf(stderr, "Grid max resolution reached.\n"); } } # endif /* DEBUG */ CagdSrfAdap2PolysFlat(Srf, -SrfErr, UIndexBase, UIndexSize, VIndexBase, VIndexSize, AuxSrfData); } else { void *AuxSrf1Data = NULL, *AuxSrf2Data = NULL; CagdBType IgnoreFirst = FALSE, IgnoreSecond = FALSE; CagdRType UMin, UMax, VMin, VMax, ErrUSub1, ErrUSub2, ErrVSub1, ErrVSub2; CagdSrfStruct *Srf1u, *Srf1v; CagdSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax); Srf1u = BspSrfSubdivAtParam(Srf, (UMin + UMax) * 0.5, CAGD_CONST_U_DIR); ErrUSub1 = CagdSrfAdap2PolyErrFunc(Srf1u); ErrUSub2 = CagdSrfAdap2PolyErrFunc(Srf1u -> Pnext); Srf1v = BspSrfSubdivAtParam(Srf, (VMin + VMax) * 0.5, CAGD_CONST_V_DIR); ErrVSub1 = CagdSrfAdap2PolyErrFunc(Srf1v); ErrVSub2 = CagdSrfAdap2PolyErrFunc(Srf1v -> Pnext); if (UVBias > CAGD_MAX_SUBDIV_ONE_DIR) { /* We have CAGD_MAX_SUBDIV_ONE_DIR subdivisions in a row in the */ /* U direction - force one subdivision in the V direction now. */ UVBias = 0; ErrUSub1 = ErrUSub2 = IRIT_INFNTY; } else if (UVBias < -CAGD_MAX_SUBDIV_ONE_DIR) { /* We have CAGD_MAX_SUBDIV_ONE_DIR subdivisions in a row in the */ /* V direction - force one subdivision in the U direction now. */ UVBias = 0; ErrVSub1 = ErrVSub2 = IRIT_INFNTY; } if (MAX(ErrUSub1, ErrUSub2) < MAX(ErrVSub1, ErrVSub1)) { /* U subdivision yields smaller error. */ if (CagdSrfAdapAuxDataFunc != NULL) { CagdSrfAdapAuxDataFunc(Srf, AuxSrfData, (UMin + UMax) * 0.5, CAGD_CONST_U_DIR, Srf1u, &AuxSrf1Data, Srf1u -> Pnext, &AuxSrf2Data); /* If both NULL, proceed as if no AuxSrfData. If one is */ /* NULL, ignore it. */ if (AuxSrf1Data == NULL && AuxSrf2Data != NULL) IgnoreFirst = TRUE; if (AuxSrf2Data == NULL && AuxSrf1Data != NULL) IgnoreSecond = TRUE; } if (!IgnoreFirst) CagdSrfAdap2PolygonsAux2(Srf1u, ErrUSub1, UVBias + 1, UIndexBase, UIndexSize >> 1, VIndexBase, VIndexSize, AuxSrf1Data); if (!IgnoreSecond) CagdSrfAdap2PolygonsAux2(Srf1u -> Pnext, ErrUSub2, UVBias + 1, UIndexBase + (UIndexSize >> 1), UIndexSize >> 1, VIndexBase, VIndexSize, AuxSrf2Data); } else { /* V subdivision yields smaller error. */ if (CagdSrfAdapAuxDataFunc != NULL) { CagdSrfAdapAuxDataFunc(Srf, AuxSrfData, (VMin + VMax) * 0.5, CAGD_CONST_V_DIR, Srf1v, &AuxSrf1Data, Srf1v -> Pnext, &AuxSrf2Data); /* If both NULL, proceed as if no AuxSrfData. If one is */ /* NULL, ignore it. */ if (AuxSrf1Data == NULL && AuxSrf2Data != NULL) IgnoreFirst = TRUE; if (AuxSrf2Data == NULL && AuxSrf1Data != NULL) IgnoreSecond = TRUE; } if (!IgnoreFirst) CagdSrfAdap2PolygonsAux2(Srf1v, ErrVSub1, UVBias - 1, UIndexBase, UIndexSize, VIndexBase, VIndexSize >> 1, AuxSrf1Data); if (!IgnoreSecond) CagdSrfAdap2PolygonsAux2(Srf1v -> Pnext, ErrVSub2, UVBias - 1, UIndexBase, UIndexSize, VIndexBase + (VIndexSize >> 1), VIndexSize >> 1, AuxSrf2Data); } CagdSrfFreeList(Srf1u); CagdSrfFreeList(Srf1v); } } /***************************************************************************** * DESCRIPTION: * * Converts a single rectangular domain into polygons. * * * * PARAMETERS: * * Srf: Bspline surface with no discontinuities to approximate into * * triangles. * * Rect: The rectangular domain to convert to polygons. * * * * RETURN VALUE: * * CagdPolygonStruct *: Constructed polygons. * *****************************************************************************/ static CagdPolygonStruct *CagdSrfAdapRect2Polys(CagdSrfStruct *Srf, CagdSrfAdapRectStruct *Rect) { int i, j, i1 = Rect -> UIndexBase, i2 = Rect -> UIndexBase + Rect -> UIndexSize, j1 = Rect -> VIndexBase, j2 = Rect -> VIndexBase + Rect -> VIndexSize; CagdSrfPtStruct *SrfPtList = GlblSrfPtSamples[i1][j1], *SrfPtLast = SrfPtList; /* Traverse VMin boundary. */ for (i = i1 + 1; i <= i2; i++) { if (GlblSrfPtSamples[i][j1] != NULL) LIST_PUSH(GlblSrfPtSamples[i][j1], SrfPtList); } /* Traverse UMax boundary. */ for (j = j1 + 1; j <= j2; j++) { if (GlblSrfPtSamples[i2][j] != NULL) LIST_PUSH(GlblSrfPtSamples[i2][j], SrfPtList); } /* Traverse VMax boundary. */ for (i = i2 - 1; i >= i1; i--) { if (GlblSrfPtSamples[i][j2] != NULL) LIST_PUSH(GlblSrfPtSamples[i][j2], SrfPtList); } /* Traverse UMin boundary. */ for (j = j2 - 1; j > j1; j--) { if (GlblSrfPtSamples[i1][j] != NULL) LIST_PUSH(GlblSrfPtSamples[i1][j], SrfPtList); } /* Make the list circular. */ SrfPtLast -> Pnext = SrfPtList; /* Convert this (convex!) domain to triangles. */ return CagdSrfAdapPolyGenFunc(Srf, SrfPtList, Rect); } /***************************************************************************** * DESCRIPTION: M * Converts the given circular list of surface points into polygons. M * The list is assumed a convex parametric domain (which ease the process M * of decomposition). M * * * PARAMETERS: M * Srf: Bspline surface with no discontinuities to approximate M * into triangles. M * SrfPtList: Circular list of a convex surface domain to convert to M * triangles. M * Rect: The rectangular domain to convert to polygons. M * * * RETURN VALUE: M * CagdPolygonStruct *: List of polygons out of the closed srf pt list; M * Could be NULL if polygons are call back created. M * * * SEE ALSO: M * CagdSrfAdap2Polygons, CagdSrf2PolygonSetErrFunc, M * CagdSrfAdap2PolyDefErrFunc, CagdSrf2PolyAdapSetErrFunc, M * CagdSrf2PolyAdapSetAuxDataFunc CagdSrf2PolyAdapSetPolyGenFunc M * * * KEYWORDS: M * CagdSrfAdapRectPolyGen, polygonization, surface approximation M *****************************************************************************/ CagdPolygonStruct *CagdSrfAdapRectPolyGen(CagdSrfStruct *Srf, CagdSrfPtStruct *SrfPtList, CagdSrfAdapRectStruct *Rect) { CagdBType Has3ColinearPts; int ListLen, GenPoly; CagdSrfPtStruct *SrfPt, *SrfPtMax, *SrfPtPrev, *SrfPtNext, *S2, *S3; CagdPolygonStruct *Poly, *Polys = NULL; for (SrfPt = SrfPtList -> Pnext, ListLen = 1; SrfPt != NULL && SrfPt != SrfPtList; SrfPt = SrfPt -> Pnext, ListLen++); #ifdef DEBUG { IRIT_SET_IF_DEBUG_ON_PARAMETER(_DebugDumpRectLoops, FALSE) { printf("\n\nRect:\nVertex at u = %g, v = %g\n", SrfPtList -> Uv[0], SrfPtList -> Uv[1]); for (SrfPt = SrfPtList -> Pnext; SrfPt != NULL && SrfPt != SrfPtList; SrfPt = SrfPt -> Pnext) printf("Vertex at u = %g, v = %g\n", SrfPt -> Uv[0], SrfPt -> Uv[1]); } } #endif /* DEBUG */ /* If a simple and planar rectangle, dump as such. */ S2 = SrfPtList -> Pnext; S3 = S2 -> Pnext; if (ListLen == 4) { CagdSrfPtStruct *S4 = S3 -> Pnext; if (_CagdSrfMakeOnlyTri || !GMCoplanar4Pts(SrfPtList -> Pt, S2 -> Pt, S3 -> Pt, S4 -> Pt)) { Poly = CagdGenAdapTriangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtList -> Pt, S2 -> Pt, S3 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtList), SRF_ADAP_FIX_DISCONT_NRML(S2), SRF_ADAP_FIX_DISCONT_NRML(S3), SrfPtList -> Uv, S2 -> Uv, S3 -> Uv, &GenPoly); if (!GenPoly && Poly != NULL) LIST_PUSH(Poly, Polys); Poly = CagdGenAdapTriangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtList -> Pt, S3 -> Pt, S4 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtList), SRF_ADAP_FIX_DISCONT_NRML(S3), SRF_ADAP_FIX_DISCONT_NRML(S4), SrfPtList -> Uv, S3 -> Uv, S4 -> Uv, &GenPoly); if (!GenPoly && Poly != NULL) LIST_PUSH(Poly, Polys); } else { Polys = CagdGenAdapRectangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtList -> Pt, S2 -> Pt, S3 -> Pt, S4 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtList), SRF_ADAP_FIX_DISCONT_NRML(S2), SRF_ADAP_FIX_DISCONT_NRML(S3), SRF_ADAP_FIX_DISCONT_NRML(S4), SrfPtList -> Uv, S2 -> Uv, S3 -> Uv, S4 -> Uv, &GenPoly); if (Polys == NULL && !GenPoly) { /* This rectangle is degenerate - try two triangles. */ Poly = CagdGenAdapTriangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtList -> Pt, S2 -> Pt, S3 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtList), SRF_ADAP_FIX_DISCONT_NRML(S2), SRF_ADAP_FIX_DISCONT_NRML(S3), SrfPtList -> Uv, S2 -> Uv, S3 -> Uv, &GenPoly); if (!GenPoly && Poly != NULL) LIST_PUSH(Poly, Polys); Poly = CagdGenAdapTriangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtList -> Pt, S3 -> Pt, S4 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtList), SRF_ADAP_FIX_DISCONT_NRML(S3), SRF_ADAP_FIX_DISCONT_NRML(S4), SrfPtList -> Uv, S3 -> Uv, S4 -> Uv, &GenPoly); if (!GenPoly && Poly != NULL) LIST_PUSH(Poly, Polys); } } /* Check if call back generated polygon but did not return it. */ if (GenPoly) return NULL; else return Polys; } Has3ColinearPts = TRUE; while (ListLen-- > 3) { /* Look for 3 or more colinear vertices along a parametric line and */ /* cut the end corner of it, at the last colinear vertex. */ if (Has3ColinearPts) { CagdBType SameU, SameV; SrfPtMax = NULL; SrfPtPrev = SrfPtList; SrfPt = SrfPtPrev -> Pnext; SameU = APX_EQ(SrfPtPrev -> Uv[0], SrfPt -> Uv[0]); SameV = APX_EQ(SrfPtPrev -> Uv[1], SrfPt -> Uv[1]); do { SrfPtNext = SrfPt -> Pnext; if (SameU && APX_EQ(SrfPt -> Uv[0], SrfPtNext -> Uv[0]) && !APX_EQ(SrfPtNext -> Uv[0], SrfPtNext -> Pnext -> Uv[0])) { SrfPtMax = SrfPt; break; } else if (SameV && APX_EQ(SrfPt -> Uv[1], SrfPtNext -> Uv[1]) && !APX_EQ(SrfPtNext -> Uv[1], SrfPtNext -> Pnext -> Uv[1])) { SrfPtMax = SrfPt; break; } SameU = APX_EQ(SrfPtNext -> Uv[0], SrfPt -> Uv[0]); SameV = APX_EQ(SrfPtNext -> Uv[1], SrfPt -> Uv[1]); SrfPtPrev = SrfPt; SrfPt = SrfPtNext; } while (SrfPtPrev != SrfPtList); if (SrfPtMax == NULL) { Has3ColinearPts = FALSE; SrfPtMax = SrfPtList; } } else { /* No 3 colinear vertices along param. line. */ /* Look for a most convex vertex as a corner to cut. */ SrfPtMax = SrfPtList; } S2 = SrfPtMax -> Pnext; S3 = S2 -> Pnext; if ((Poly = CagdGenAdapTriangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtMax -> Pt, S2 -> Pt, S3 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtMax), SRF_ADAP_FIX_DISCONT_NRML(S2), SRF_ADAP_FIX_DISCONT_NRML(S3), SrfPtMax -> Uv, S2 -> Uv, S3 -> Uv, &GenPoly)) != NULL) { LIST_PUSH(Poly, Polys); } SrfPtMax -> Pnext = S3; /* Skip S2, effectively skipping triangle. */ SrfPtList = SrfPtMax; /* Make sure SrfPtList points to valid vertex. */ } /* Do the last triangle */ S2 = SrfPtList -> Pnext; S3 = S2 -> Pnext; if ((Poly = CagdGenAdapTriangle(CagdSrf2PolyComputeNormals, CagdSrf2PolyComputeUV, SrfPtList -> Pt, S2 -> Pt, S3 -> Pt, SRF_ADAP_FIX_DISCONT_NRML(SrfPtList), SRF_ADAP_FIX_DISCONT_NRML(S2), SRF_ADAP_FIX_DISCONT_NRML(S3), SrfPtList -> Uv, S2 -> Uv, S3 -> Uv, &GenPoly)) != NULL) { LIST_PUSH(Poly, Polys); } return Polys; } /***************************************************************************** * DESCRIPTION: * * Make sure the normal we provide is indeed the proper one at a point * * on the surface that has C^1 discontinuity. * * * * PARAMETERS: * * Srf: Bspline surface with no discontinuities to approximate into * * triangles. * * SrfPt: Surface point to make sure it provides the right normal * * Rect: The rectangular domain, this point belongs to. * * * * RETURN VALUE: * * CagdRType *: Fixed normal if need, original normal otherwise. * *****************************************************************************/ static CagdRType *CagdSrfAdapFixDiscontNrml(CagdSrfStruct *Srf, CagdSrfPtStruct *SrfPt, CagdSrfAdapRectStruct *Rect) { if (SrfPt -> Nrml[0] == IRIT_INFNTY) return NULL; else return SrfPt -> Nrml; } /***************************************************************************** * DESCRIPTION: * * Allocates a rectangle to convert to polygons later on. * * * * PARAMETERS: * * UIndexBase, UIndexSize: U domain of rectangle. * * VIndexBase, VIndexSize: V domain of rectangle. * * AuxSrfData: Optional data structure that was passed to all * * subdivided sub-surfaces, or NULL if not needed. * * Err: Error of approximation. * * * * RETURN VALUE: * * CagdSrfAdapRectStruct *: Allocated rectangle. * *****************************************************************************/ static CagdSrfAdapRectStruct *CagdSrfAdap2PolyAllocRect(int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData, CagdRType Err) { CagdSrfAdapRectStruct *Rect; # ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugDumpSubdivMinSize) { GlblSubdivMinSize = MIN(GlblSubdivMinSize, UIndexSize); GlblSubdivMinSize = MIN(GlblSubdivMinSize, VIndexSize); } # endif /* DEBUG */ if (GlblRectFreeList == NULL) { int i; CagdSrfAdapRectStruct *Rects; Rects = IritMalloc(sizeof(CagdSrfAdapRectStruct) * CAGD_RECT_ALLOC_BLOCK); GlblRectFreeList = &Rects[0]; /* Allocate a block of CAGD_RECT_ALLOC_BLOCK such structures. */ for (i = 0; i < CAGD_RECT_ALLOC_BLOCK - 1; i++) Rects[i].Pnext = &Rects[i + 1]; Rects[i].Pnext = NULL; } Rect = GlblRectFreeList; GlblRectFreeList = GlblRectFreeList -> Pnext; Rect -> UIndexBase = UIndexBase; Rect -> UIndexSize = UIndexSize; Rect -> VIndexBase = VIndexBase; Rect -> VIndexSize = VIndexSize; Rect -> AuxSrfData = AuxSrfData; Rect -> Err = Err; return Rect; } /***************************************************************************** * DESCRIPTION: * * Converts a flat enough surface into polygons. * * * * PARAMETERS: * * Srf: Flat enough surface to convert to polygons. * * Err: Amount of flatness error measured. * * UIndexBase: 2's power index of base of this U parameteric domain. * * UIndexSize: 2's power size of this U parameteric domain. * * VIndexBase: 2's power index of base of this V parameteric domain. * * VIndexSize: 2's power size of this V parameteric domain. * * AuxSrfData: Optional data structure that will be passed to all * * subdivided sub-surfaces, or NULL if not needed. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void CagdSrfAdap2PolysFlat(CagdSrfStruct *Srf, CagdRType Err, int UIndexBase, int UIndexSize, int VIndexBase, int VIndexSize, VoidPtr AuxSrfData) { CagdRType UMin, UMax, VMin, VMax; CagdSrfAdapRectStruct *Rect; CagdSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax); /* Update the four corners in the global mesh/corner data structs. */ if (UIndexBase + UIndexSize > CAGD2PLY_MAX_SUBDIV_INDEX || VIndexBase + VIndexSize > CAGD2PLY_MAX_SUBDIV_INDEX) CAGD_FATAL_ERROR(CAGD_ERR_INDEX_NOT_IN_MESH); GlblSubdivUVals[UIndexBase] = UMin; GlblSubdivUVals[UIndexBase + UIndexSize] = UMax; GlblSubdivVVals[VIndexBase] = VMin; GlblSubdivVVals[VIndexBase + VIndexSize] = VMax; CagdSrfAdapSampleActivate(Srf, UIndexBase, VIndexBase, TRUE, TRUE, UMin, VMin); CagdSrfAdapSampleActivate(Srf, UIndexBase, VIndexBase + VIndexSize, TRUE, FALSE, UMin, VMax); CagdSrfAdapSampleActivate(Srf, UIndexBase + UIndexSize, VIndexBase, FALSE, TRUE, UMax, VMin); CagdSrfAdapSampleActivate(Srf, UIndexBase + UIndexSize, VIndexBase + VIndexSize, FALSE, FALSE, UMax, VMax); if (CAGD_IS_RATIONAL_SRF(Srf) && Cagd2PolyClipPolysAtPoles(CAGD_QUERY_VALUE) && CagdPointsHasPoles(Srf -> Points, Srf -> ULength * Srf -> VLength)) return; /* We have poles in this small patch - purge it. */ /* Push this rectangular for late evaluation. */ Rect = CagdSrfAdap2PolyAllocRect(UIndexBase, UIndexSize, VIndexBase, VIndexSize, AuxSrfData, Err); LIST_PUSH(Rect, GlblRectList); } /***************************************************************************** * DESCRIPTION: * * Test if this specific surface point was already sampled and if not * * create and sample it now. * * * * PARAMETERS: * * Srf: Surface that was found to be flat enough. * * UIndex, VIndex: Indices of location to update. * * IsVMin, IsVMin: TRUE if is U/V minimum bndry, FALSE if maximum bndry. * * u, v: Parameter values of this location. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void CagdSrfAdapSampleActivate(CagdSrfStruct *Srf, int UIndex, int VIndex, int IsUMin, int IsVMin, CagdRType u, CagdRType v) { CagdBType DiscontPt = GlblDiscontUVals[UIndex] || GlblDiscontVVals[VIndex]; int ULen1, VLen1; RealType **Points; CagdPointType PType; CagdVType V1, V2; CagdSrfPtStruct **SrfPt = &GlblSrfPtSamples[UIndex][VIndex]; if (*SrfPt != NULL) return; /* It is already setup. */ if (GlblSrfPtFreeList != NULL) { *SrfPt = GlblSrfPtFreeList; GlblSrfPtFreeList = GlblSrfPtFreeList -> Pnext; } else *SrfPt = CagdSrfPtNew(); PType = Srf -> PType; Points = Srf -> Points; ULen1 = Srf -> ULength - 1; VLen1 = Srf -> VLength - 1; if (IsUMin) { if (IsVMin) { /* The surface corner to sample is the (0, 0). */ CagdCoerceToE3((*SrfPt) -> Pt, Points, CAGD_MESH_UV(Srf, 0, 0), PType); if (!DiscontPt && CagdSrf2PolyComputeNormals) { CagdCoerceToE3(V1, Points, CAGD_MESH_UV(Srf, 1, 0), PType); CagdCoerceToE3(V2, Points, CAGD_MESH_UV(Srf, 0, 1), PType); } } else { /* The surface corner to sample is the (0, VLen1). */ CagdCoerceToE3((*SrfPt) -> Pt, Points, CAGD_MESH_UV(Srf, 0, VLen1), PType); if (!DiscontPt && CagdSrf2PolyComputeNormals) { CagdCoerceToE3(V1, Points, CAGD_MESH_UV(Srf, 0, VLen1 - 1), PType); CagdCoerceToE3(V2, Points, CAGD_MESH_UV(Srf, 1, VLen1), PType); } } } else { if (IsVMin) { /* The surface corner to sample is the (ULen1, 0). */ CagdCoerceToE3((*SrfPt) -> Pt, Points, CAGD_MESH_UV(Srf, ULen1, 0), PType); if (!DiscontPt && CagdSrf2PolyComputeNormals) { CagdCoerceToE3(V1, Points, CAGD_MESH_UV(Srf, ULen1, 1), PType); CagdCoerceToE3(V2, Points, CAGD_MESH_UV(Srf, ULen1 - 1, 0), PType); } } else { /* The surface corner to sample is the (ULen1, VLen1). */ CagdCoerceToE3((*SrfPt) -> Pt, Points, CAGD_MESH_UV(Srf, ULen1, VLen1), PType); if (!DiscontPt && CagdSrf2PolyComputeNormals) { CagdCoerceToE3(V1, Points, CAGD_MESH_UV(Srf, ULen1 - 1, VLen1), PType); CagdCoerceToE3(V2, Points, CAGD_MESH_UV(Srf, ULen1, VLen1 - 1), PType); } } } if (CagdSrf2PolyComputeNormals) { if (DiscontPt) (*SrfPt) -> Nrml[0] = IRIT_INFNTY; else { RealType R; VEC_SUB(V1, V1, (*SrfPt) -> Pt); VEC_SUB(V2, V2, (*SrfPt) -> Pt); CROSS_PROD((*SrfPt) -> Nrml, V2, V1); if ((R = VEC_LENGTH((*SrfPt) -> Nrml)) < IRIT_UEPS) { CagdVecStruct *N = CagdSrfNormal(Srf, u, v, TRUE); VEC_COPY((*SrfPt) -> Nrml, N -> Vec); } else { R = 1 / R; VEC_SCALE((*SrfPt) -> Nrml, R); } } } (*SrfPt) -> Uv[0] = u; (*SrfPt) -> Uv[1] = v; if (GlblSrfPtEvalCache) IritSearch2DInsertElem(GlblSrfPtEvalCache, u, v, *SrfPt); } /***************************************************************************** * DESCRIPTION: * * Compute the normal to the surface very close to UV1 in the triangle * * defined by UV1/UV2/UV3. * * * * PARAMETERS: * * UV1: To compute the surface normal close to. * * UV2, UV3: Two other UV''s of the triangle. * * * * RETURN VALUE: * * CagdRType *: Computed normal in a static location. Upto 4 normals * * could be satatically saved simultaneously. * *****************************************************************************/ static CagdRType *EvaluateNormalBlendedUV(CagdRType *UV1, CagdRType *UV2, CagdRType *UV3) { static int Idx = -1; static CagdPType Nrmls[4]; CagdRType UV[2]; CagdVecStruct *N; UV[0] = UV1[0] * (1.0 - CAGD_DISCONT_NORMAL_EPS) + (UV2[0] + UV3[0]) * 0.5 * CAGD_DISCONT_NORMAL_EPS; UV[1] = UV1[1] * (1.0 - CAGD_DISCONT_NORMAL_EPS) + (UV2[1] + UV3[1]) * 0.5 * CAGD_DISCONT_NORMAL_EPS; N = CagdSrfNormal(GlblSrf, UV[0], UV[1], TRUE); if (++Idx >= 4) Idx = 0; VEC_COPY(Nrmls[Idx], N -> Vec); return Nrmls[Idx]; } /***************************************************************************** * DESCRIPTION: * * Routine to create one triangular polygon, given its vertices, * * and, optionally, normals and uv coordinates. * * * * PARAMETERS: * * ComputeNormals: If TRUE then use Nl? parameters. Nl? are valid. * * ComputeUV: If TRUE then use UV? parameters. UV? are valid. * * Pt1, Pt2, Pt3: Euclidean locations of vertices. * * Nl1, Nl2, Nl3: Optional Normals of vertices (if ComputeNormals). * * UV1, UV2, UV3: Optional UV parametric location of vertices (if * * ComputeUV). * * GenPoly: Returns TRUE if a polygon was generated, FALSE * * otherwise. Note this function can return NULL and * * still generate a polygon as a call back for * * CagdSrf2Polygons. * * * * RETURN VALUE: * * CagdPolygonStruct *: This call back function ALLWAYS RETURNS NULL. * *****************************************************************************/ static CagdPolygonStruct *CagdGenAdapTriangle(CagdBType ComputeNormals, CagdBType ComputeUV, CagdRType *Pt1, CagdRType *Pt2, CagdRType *Pt3, CagdRType *Nl1, CagdRType *Nl2, CagdRType *Nl3, CagdRType *UV1, CagdRType *UV2, CagdRType *UV3, CagdBType *GenPoly) { /* We need to handle the special case of closed surface where UV */ /* coordinates from end of the UV domain will alias as from beginning. */ if (ComputeUV) { CagdRType *UVs[3]; UVs[0] = UV1; UVs[1] = UV2; UVs[2] = UV3; CorrectUVBoundaries(UVs, 3); } /* Normal could be NULL if on a discontinuity. Evaluate manually then. */ if (ComputeNormals) { if (Nl1 == NULL) Nl1 = EvaluateNormalBlendedUV(UV1, UV2, UV3); if (Nl2 == NULL) Nl2 = EvaluateNormalBlendedUV(UV2, UV1, UV3); if (Nl3 == NULL) Nl3 = EvaluateNormalBlendedUV(UV3, UV2, UV1); } return _CagdSrfMakeTriFunc(ComputeNormals, ComputeUV, Pt1, Pt2, Pt3, Nl1, Nl2, Nl3, UV1, UV2, UV3, GenPoly); } /***************************************************************************** * DESCRIPTION: * * Call back routine to create one rectangular polygon, given its vertices, * * and, optionally, normals and uv coordinates. Places the constructed * * polygon in a global polygonal list. * * * * PARAMETERS: * * ComputeNormals: If TRUE then use Nl? parameters. Nl? are valid. * * ComputeUV: If TRUE then use UV? parameters. UV? are valid. * * Pt1, Pt2, Pt3, Pt4: Euclidean locations of vertices. * * Nl1, Nl2, Nl3, Nl4: Optional Normals of vertices (if ComputeNormals). * * UV1, UV2, UV3, UV4: Optional UV parametric location of vertices (if * * ComputeUV). * * GenPoly: Returns TRUE if a polygon was generated, FALSE * * otherwise. Note this function can return NULL and * * still generate a polygon as a call back for * * CagdSrf2Polygons. * * * * RETURN VALUE: * * CagdPolygonStruct *: This call back function ALLWAYS RETURNS NULL. * *****************************************************************************/ static CagdPolygonStruct *CagdGenAdapRectangle(CagdBType ComputeNormals, CagdBType ComputeUV, CagdRType *Pt1, CagdRType *Pt2, CagdRType *Pt3, CagdRType *Pt4, CagdRType *Nl1, CagdRType *Nl2, CagdRType *Nl3, CagdRType *Nl4, CagdRType *UV1, CagdRType *UV2, CagdRType *UV3, CagdRType *UV4, CagdBType *GenPoly) { /* We need to handle the special case of closed surface where UV */ /* coordinates from end of the UV domain will alias as from beginning. */ if (ComputeUV) { CagdRType *UVs[4]; UVs[0] = UV1; UVs[1] = UV2; UVs[2] = UV3; UVs[3] = UV4; CorrectUVBoundaries(UVs, 4); } /* Normal could be NULL if on a discontinuity. Evaluate manually then. */ if (ComputeNormals) { if (Nl1 == NULL) Nl1 = EvaluateNormalBlendedUV(UV1, UV2, UV3); if (Nl2 == NULL) Nl2 = EvaluateNormalBlendedUV(UV2, UV1, UV3); if (Nl3 == NULL) Nl3 = EvaluateNormalBlendedUV(UV3, UV2, UV4); if (Nl4 == NULL) Nl4 = EvaluateNormalBlendedUV(UV4, UV2, UV3); } return _CagdSrfMakeRectFunc(ComputeNormals, ComputeUV, Pt1, Pt2, Pt3, Pt4, Nl1, Nl2, Nl3, Nl4, UV1, UV2, UV3, UV4, GenPoly); } /***************************************************************************** * DESCRIPTION: * * Corrects UV boundaries of closed surfaces. * * * * PARAMETERS: * * UVs: The UVs to correct. * * n: Number of UVs. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void CorrectUVBoundaries(CagdRType **UVs, int n) { int i, OnUMin = FALSE, OnUMax = FALSE, OnVMin = FALSE, OnVMax = FALSE; for (i = 0; i < n; i++) { if (APX_EQ(UVs[i][0], GlblUMin)) OnUMin = TRUE; if (APX_EQ(UVs[i][0], GlblUMax)) OnUMax = TRUE; if (APX_EQ(UVs[i][1], GlblVMin)) OnVMin = TRUE; if (APX_EQ(UVs[i][1], GlblVMax)) OnVMax = TRUE; } if (OnUMin && OnUMax) { for (i = 0; i < n; i++) { if (APX_EQ(UVs[i][0], GlblUMin)) UVs[i][0] = GlblUMin; else if (APX_EQ(UVs[i][0], GlblUMax)) UVs[i][0] = GlblUMax; } } else if (OnUMin || OnUMax) { for (i = 0; i < n; i++) { if (!APX_EQ(UVs[i][0], GlblUMin) && !APX_EQ(UVs[i][0], GlblUMax)) { OnUMin = (UVs[i][0] - GlblUMin < GlblUMax - UVs[i][0]); break; } } for (i = 0; i < n; i++) { if (APX_EQ(UVs[i][0], GlblUMin) || APX_EQ(UVs[i][0], GlblUMax)) UVs[i][0] = OnUMin ? GlblUMin : GlblUMax; } } if (OnVMin && OnVMax) { for (i = 0; i < n; i++) { if (APX_EQ(UVs[i][1], GlblVMin)) UVs[i][1] = GlblVMin; else if (APX_EQ(UVs[i][1], GlblVMax)) UVs[i][1] = GlblVMax; } } else if (OnVMin || OnVMax) { for (i = 0; i < n; i++) { if (!APX_EQ(UVs[i][1], GlblVMin) && !APX_EQ(UVs[i][1], GlblVMax)) { OnVMin = (UVs[i][1] - GlblVMin < GlblVMax - UVs[i][1]); break; } } for (i = 0; i < n; i++) { if (APX_EQ(UVs[i][1], GlblVMin) || APX_EQ(UVs[i][1], GlblVMax)) UVs[i][1] = OnVMin ? GlblVMin : GlblVMax; } } }