/******************************************************************************
* Trim_aux.c - auxiliary routine to interface to different free from types.   *
*******************************************************************************
* Written by Gershon Elber, July. 90.					      *
******************************************************************************/

#include "trim_loc.h"

#define VEC_FIELD_TRIES	10
#define VEC_FIELD_START_STEP 1e-6

CagdBType _TrimEuclidComposedFromUV = FALSE;

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Returns the parametric domain of a trimmed surface.			     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:   To get its parametric domain.                                 M
*   UMin:      Where to put the minimal U domain's boundary.                 M
*   UMax:      Where to put the maximal U domain's boundary.                 M
*   VMin:      Where to put the minimal V domain's boundary.                 M
*   VMax:      Where to put the maximal V domain's boundary.                 M
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfDomain, domain, parametric domain                                 M
*****************************************************************************/
void TrimSrfDomain(TrimSrfStruct *TrimSrf,
		   CagdRType *UMin,
		   CagdRType *UMax,
		   CagdRType *VMin,
		   CagdRType *VMax)
{
    CagdSrfDomain(TrimSrf -> Srf, UMin, UMax, VMin, VMax);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Given a trimmed surface and parameter values u, v, evaluate the surface at M
* (u, v).								     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf: To evaluate at the given parametric location (u, v).            M
*   u, v:    The parameter values at which TrimSrf is to be evaluated.       M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdRType *: A vector holding all the coefficients of all components     M
*                of surface TrimSrf's point type. If, for example, TrimSrf's M
*                point type is P2, the W, X, and Y will be saved in the      M
*                first three locations of the returned vector. The first     M
*                location (index 0) of the returned vector is reserved for   M
*                the rational coefficient W and XYZ always starts at second  M
*                location of the returned vector (index 1).                  M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfEval, evaluation                                                  M
*****************************************************************************/
CagdRType *TrimSrfEval(TrimSrfStruct *TrimSrf, CagdRType u, CagdRType v)
{
    return CagdSrfEval(TrimSrf -> Srf, u, v);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Returns a new trimmed surface representing the same surface as TrimSrf but M
* with its degree raised by one.					     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:       To raise its degree.                                      M
*                                                                            *
* RETURN VALUE:                                                              M
*   TrimSrfStruct *:  A surface with same geometry as Srf but with one       M
*                     degree higher.                                         M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfDegreeRaise, degree raising                                       M
*****************************************************************************/
TrimSrfStruct *TrimSrfDegreeRaise(TrimSrfStruct *TrimSrf, CagdSrfDirType Dir)
{
    return TrimSrfNew(CagdSrfDegreeRaise(TrimSrf -> Srf, Dir),
		      TrimCrvCopyList(TrimSrf -> TrimCrvList),
		      FALSE);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Given a trimmed surface - subdivides it into two sub-surfaces at given     M
* parametric value t in the given direction Dir.                             M
*    Returns pointer to a list of two trimmed surfaces, at most. It can very M
* well may happen that the subdivided surface is completely trimmed out and  M
* hence nothing is returned for it.					     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:  To subdivide at the prescibed parameter value t.               M
*   t:        The parameter to subdivide the curve Crv at.                   M
*   Dir:      Direction of subdivision. Either U or V.                       M
*                                                                            *
* RETURN VALUE:                                                              M
*   TrimSrfStruct *:  The subdivided surfaces. Usually two, but can have     M
*		      only one, if other is totally trimmed away.            M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfSubdivAtParam, subdivision                                        M
*****************************************************************************/
TrimSrfStruct *TrimSrfSubdivAtParam(TrimSrfStruct *TrimSrf,
				    CagdRType t,
				    CagdSrfDirType Dir)
{
    fprintf(stderr, "TrimSrfSubdivAtParam not implemented\n");
    return NULL;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Given a trimmed surface - extracts a sub-region within the domain          M
* specified by t1 and t2, in the direction Dir.                              M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:   To extract a sub-region from.                                 M
*   t1, t2:    Parametric domain boundaries of sub-region.                   M
*   Dir:       Direction of region extraction. Either U or V.                M
*                                                                            *
* RETURN VALUE:                                                              M
*   TrimSrfStruct *:  Sub-region extracted from TrimSrf from t1 to t2.       M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfRegionFromTrimSrf, regions, subdivision                           M
*****************************************************************************/
TrimSrfStruct *TrimSrfRegionFromTrimSrf(TrimSrfStruct *TrimSrf,
					CagdRType t1,
					CagdRType t2,
					CagdSrfDirType Dir)
{
    CagdRType TMin, TMax, R1, R2;
    TrimSrfStruct *TrimSrfs;
    CagdBType
	OpenEnd = FALSE,
	NewTrimSrf = FALSE;

    if (Dir == CAGD_CONST_U_DIR)
	TrimSrfDomain(TrimSrf, &TMin, &TMax, &R1, &R2);
    else
	TrimSrfDomain(TrimSrf, &R1, &R2, &TMin, &TMax);
    CAGD_DOMAIN_T_VERIFY(t1, TMin, TMax);
    CAGD_DOMAIN_T_VERIFY(t2, TMin, TMax);

    if (t1 > t2)
	SWAP(CagdRType, t1, t2);

    if (!APX_EQ(t1, TMin) || !OpenEnd) {
	TrimSrfs = TrimSrfSubdivAtParam(TrimSrf, t1, Dir);
	TrimSrf = TrimSrfs -> Pnext;
	TrimSrfs -> Pnext = NULL;
	if (TRIM_IS_FIRST_SRF(TrimSrfs))
	    TrimSrfFree(TrimSrfs);		   /* Free the first region. */
	if (TrimSrf == NULL)
	    return NULL;       /* No second region -completely trimmed away. */
	NewTrimSrf = TRUE;
    }

    if (APX_EQ(t2, TMax) && OpenEnd)
	return NewTrimSrf ? TrimSrf : TrimSrfCopy(TrimSrf);
    else {
	TrimSrfs = TrimSrfSubdivAtParam(TrimSrf, t2, Dir);

	if (NewTrimSrf)
	    TrimSrfFree(TrimSrf);

    	if (TrimSrfs -> Pnext != NULL)
	    TrimSrfFree(TrimSrfs -> Pnext);	  /* Free the second region. */
    	TrimSrfs -> Pnext = NULL;
	return TrimSrfs;			/* Returns the first region. */
    }
}
/*****************************************************************************
* DESCRIPTION:                                                               M
* Given a trimmed surface - refines it at the given n knots as defined by    M
* vector t.								     M
*   If Replace is TRUE, the values in t replaces current knot vector.	     M
*   Returns pointer to refined surface (Note a Bezier surface will be        M
* converted into a Bspline surface).                                         M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:   To refine.                                                    M
*   Dir:       Direction of refinement. Either U or V.                       M
*   Replace:   If TRUE, t holds knots in exactly the same length as the      M
*              length of the knot vector of Srf and t simply replaces the    M
*              knot vector.                                                  M
*   t:         Vector of knots with length of n.                             M
*   n:         Length of vector t.                                           M
*                                                                            *
* RETURN VALUE:                                                              M
*   TrimSrfStruct *:  A refined surface of TrimSrf after insertion of all    M
*                     the knots as specified by vector t of length n.        M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfRefineAtParams, refinement, subdivision                           M
*****************************************************************************/
TrimSrfStruct *TrimSrfRefineAtParams(TrimSrfStruct *TrimSrf,
				     CagdSrfDirType Dir,
				     CagdBType Replace,
				     CagdRType *t,
				     int n)
{
    return TrimSrfNew(CagdSrfRefineAtParams(TrimSrf -> Srf, Dir, Replace, t, n),
		      TrimCrvCopyList(TrimSrf -> TrimCrvList), FALSE);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Returns a new trimmed surface that is the reversed surface of TrimSrf by   M
* reversing the control mesh and the knot vector (if Bspline surface) of     M
* TrimSrf in the U direction, as well as its trimming curves. See also	     M
* CagdSrfReverse and BspKnotReverse.      		                     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:       To be reversed.                                           M
*                                                                            *
* RETURN VALUE:                                                              M
*   TrimSrfStruct *:   Reversed surface of TrimSrf.                          M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfReverse, reverse                                                  M
*****************************************************************************/
TrimSrfStruct *TrimSrfReverse(TrimSrfStruct *TrimSrf)
{
    CagdRType UMin, UMax, VMin, VMax;
    TrimCrvStruct *TrimCrv,
	*TrimCrvList = TrimCrvCopyList(TrimSrf -> TrimCrvList);

    TrimSrfDomain(TrimSrf, &UMin, &UMax, &VMin, &VMax);

    for (TrimCrv = TrimCrvList; TrimCrv != NULL; TrimCrv = TrimCrv -> Pnext) {
	TrimCrvSegStruct *TrimCrvSeg;

	for (TrimCrvSeg = TrimCrv -> TrimCrvSegList;
	     TrimCrvSeg != NULL;
	     TrimCrvSeg = TrimCrvSeg -> Pnext) {
	    int i,
		Length = TrimCrvSeg -> UVCrv -> Length;
	    CagdRType
		**Points = TrimCrvSeg -> UVCrv -> Points,
		*UPts = Points[1];

	    if (TrimCrvSeg -> UVCrv -> PType != CAGD_PT_E2_TYPE)
		TRIM_FATAL_ERROR(TRIM_ERR_TRIM_CRV_E2);
	    for (i = 0; i < Length; i++)
		UPts[i] = UMax - (UPts[i] - UMin);
	}
    }

    return TrimSrfNew(CagdSrfReverse(TrimSrf -> Srf), TrimCrvList, FALSE);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Returns a new trimmed surface that is the reversed surface of Srf by       M
* flipping the U and the V directions of the surface, as well as flipping    M
* them in the trimming curves.						     M
* See also BspKnotReverse.		                                     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:       To be reversed.                                           M
*                                                                            *
* RETURN VALUE:                                                              M
*   TrimSrfStruct *:   Reversed surface of TrimSrf.                          M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSrfReverse, reverse                                                  M
*****************************************************************************/
TrimSrfStruct *TrimSrfReverse2(TrimSrfStruct *TrimSrf)
{
    TrimCrvStruct *TrimCrv,
	*TrimCrvList = TrimCrvCopyList(TrimSrf -> TrimCrvList);

    for (TrimCrv = TrimCrvList; TrimCrv != NULL; TrimCrv = TrimCrv -> Pnext) {
	TrimCrvSegStruct *TrimCrvSeg;

	for (TrimCrvSeg = TrimCrv -> TrimCrvSegList;
	     TrimCrvSeg != NULL;
	     TrimCrvSeg = TrimCrvSeg -> Pnext) {
	    int i,
		Length = TrimCrvSeg -> UVCrv -> Length;
	    CagdRType
		**Points = TrimCrvSeg -> UVCrv -> Points,
		*UPts = Points[1],
		*VPts = Points[2];

	    if (TrimCrvSeg -> UVCrv -> PType != CAGD_PT_E2_TYPE)
		TRIM_FATAL_ERROR(TRIM_ERR_TRIM_CRV_E2);
	    for (i = 0; i < Length; i++)
		SWAP(CagdRType, UPts[i], VPts[i]);
	}
    }

    return TrimSrfNew(CagdSrfReverse2(TrimSrf -> Srf), TrimCrvList, FALSE);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Extracts the trimming curves of the given trimmed surface.               M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:       Trimmed surface to extract trimming curves from.          M
*   ParamSpace:    TRUE for curves in parameteric space, FALSE of 3D         M
*		   Euclidean space.					     M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:   List of trimming curves of TrimSrf.                   M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimGetTrimmingCurves, trimming curves                                   M
*****************************************************************************/
CagdCrvStruct *TrimGetTrimmingCurves(TrimSrfStruct *TrimSrf,
				     CagdBType ParamSpace)
{
    CagdCrvStruct
	*NewTrimCrvList = NULL;
    TrimCrvStruct
	*TrimCrvList = TrimSrf -> TrimCrvList;

    for ( ; TrimCrvList != NULL; TrimCrvList = TrimCrvList -> Pnext) {
	TrimCrvSegStruct
	    *TrimCrvSegList = TrimCrvList -> TrimCrvSegList;

	for (;
	     TrimCrvSegList != NULL;
	     TrimCrvSegList = TrimCrvSegList -> Pnext) {
	    CagdCrvStruct *TCrv;

	    if (ParamSpace)
		TCrv = CagdCrvCopy(TrimCrvSegList -> UVCrv);
	    else {
		if (TrimCrvSegList -> EucCrv == NULL) {
		    TrimCrvSegList -> EucCrv =
		        TrimEvalTrimCrvToEuclid(TrimSrf,
						TrimCrvSegList -> UVCrv);
		}
		TCrv = CagdCrvCopy(TrimCrvSegList -> EucCrv);
	    }
	    LIST_PUSH(TCrv, NewTrimCrvList);
	}
    }

    return NewTrimCrvList;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Routine to convert the trimming curves of a trimmed surface to polylines.M
*   Polyline are always E3 of CagdPolylineStruct type.			     M
*   NULL is returned in case of an error, otherwise list of                  M
* CagdPolylineStruct. 							     M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:           To extract isoparametric curves from.                 M
*   ParamSpace:        TRUE for curves in parameteric space, FALSE of 3D     M
*		       Euclidean space.					     M
*   SamplesPerCurve:   Fineness control on piecewise linear curve            M
*                      approximation.                                        M
*   Optimal:	       Use optimal approximation of isocurves.		     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
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimCrvs2Polylines, trimming curves 	                             M
*****************************************************************************/
CagdPolylineStruct *TrimCrvs2Polylines(TrimSrfStruct *TrimSrf,
				       CagdBType ParamSpace,
				       int SamplesPerCurve,
				       int Optimal)
{
    CagdCrvStruct *Crv,
        *Crvs = TrimGetTrimmingCurves(TrimSrf, ParamSpace);
    CagdPolylineStruct *Poly,
	*Polys = NULL;

    for (Crv = Crvs; Crv != NULL; Crv = Crv -> Pnext) {
	Poly = SymbCrv2Polyline(Crv, SamplesPerCurve, Optimal, TRUE);
	Poly -> Pnext = Polys;
	Polys = Poly;
    }

    CagdCrvFreeList(Crvs);
    return Polys;	
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Computes the composed Euclidean curve of TrimSrf(UVCrv).		     M
* The resulting curve is either computed using a piecewise linear            M
* approximation or by symbolically composing it onto the surface.            M
*                                                                            *
* PARAMETERS:                                                                M
*   TrimSrf:    To compute the Euclidean UVCrv for.                          M
*   UVCrv:      A curve in the parametric space of TrimSrf.                  M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:  A Euclidean curve in TrimSrf, following UVCrv.         M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimEvalTrimCrvToEuclid                                                  M
*****************************************************************************/
CagdCrvStruct *TrimEvalTrimCrvToEuclid(TrimSrfStruct *TrimSrf,
				       CagdCrvStruct *UVCrv)
{
    if (_TrimEuclidComposedFromUV) {
	return SymbComposeSrfCrv(TrimSrf -> Srf, UVCrv);
    }
    else {
	int i, j,
	    MaxAxis = CAGD_NUM_OF_PT_COORD(TrimSrf -> Srf -> PType),
	    IsRational = CAGD_IS_RATIONAL_PT(TrimSrf -> Srf -> PType);
	CagdPolylineStruct
	    *UVPoly = SymbCrv2Polyline(UVCrv, _TrimUVSamplesPerCurve,
				              _TrimUVSamplesOptimal, FALSE);
	CagdCrvStruct
	    *EucCrv = CagdCrvNew(UVCrv -> GType, 
				 TrimSrf -> Srf -> PType, 
				 UVPoly -> Length);
	CagdRType
	    **Points = EucCrv -> Points;

	EucCrv -> Order = 2;
	if (CAGD_IS_BSPLINE_CRV(UVCrv)) {
	    EucCrv -> KnotVector = BspKnotUniformOpen(UVPoly -> Length,
						      2, NULL);
	}

	for (i = 0; i < EucCrv -> Length; i++) {
	    CagdRType
		*R = CagdSrfEval(TrimSrf -> Srf, UVPoly -> Polyline[i].Pt[0],
						 UVPoly -> Polyline[i].Pt[1]);

	    for (j = !IsRational; j <= MaxAxis; j++)
	        Points[j][i] = R[j];
	}

	return EucCrv;
    }
}

/*****************************************************************************
* DESCRIPTION:                                                               M
*   Sets the way Euclidean trimming curves are computed from parametric      M
* trimming curves. Either by symbolic composition (TRUE) or by piecewise     M
* linear approximation of trimming curves (FALSE).			     M
*                                                                            *
* PARAMETERS:                                                                M
*   EuclidComposedFromUV:   Do we want symbolic composition for Euclidean    M
*		curves, or should we piecewise linear sample the UV trimming M
*		curves.							     M
*                                                                            *
* RETURN VALUE:                                                              M
*   int:  Old value of way of Euclidean curve's computation                  M
*                                                                            *
* KEYWORDS:                                                                  M
*   TrimSetEuclidComposedFromUV                                              M
*****************************************************************************/
int TrimSetEuclidComposedFromUV(int EuclidComposedFromUV)
{
    int OldEuclidComposedFromUV = _TrimEuclidComposedFromUV;

    _TrimEuclidComposedFromUV = EuclidComposedFromUV;

    return OldEuclidComposedFromUV;
}

