/******************************************************************************
* Bzr2Poly.c - Bezier to polygon/polylines conversion routines.		      *
*******************************************************************************
* 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
*                                                                            *
* 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;
    CagdRType *Pt;
    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;

    /* Simple heuristic to estimate how many samples to compute. */
    FineNessU = Srf -> UOrder * FineNess / 10;
    FineNessV = Srf -> VOrder * FineNess / 10;

    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);

		if (PT_LENGTH(Nl1 -> Vec) < IRIT_EPSILON) {
		    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_EPSILON &&
			   k++ < VEC_FIELD_TRIES) {
			U += U < UMid ? Step : -Step;
			V += V < VMid ? Step : -Step;
			Step *= 2.0;

			Nl1 = BzrSrfNormal(Srf, U, V);
		    }
		    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] = ((CagdRType) i) / FineNessU1;
		UVMeshPtr -> UV[1] = ((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
*                                                                            *
* 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
*                                                                            *
* 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
*                                                                            *
* 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;
}
