/******************************************************************************
* CagdCMrg.c - Curve/Point merging routines.				      *
*******************************************************************************
* Written by Gershon Elber, May 91.					      *
******************************************************************************/

#include "string.h"
#include "cagd_loc.h"

static void CopyCrvOnCrv(CagdCrvStruct *DestCrv,
			 int Index,
			 CagdCrvStruct *SrcCrv);
static void InterpolateLinearSeg(CagdCrvStruct *Crv, int Index1, int Index2);

/*****************************************************************************
* DESCRIPTION:                                                               M
* Merges two curves by connecting the end of Crv1 to the beginning of Crv2.  M
*  If the end of Crv1 is identical to the beginning of Crv2 then the result  M
* is as expected. However, if the curves do not meet their end points are    M
* linearly interpolated if InterpolateDiscont is TRUE or simply blended out  M
* in a freeform shape if If InterpolateDiscont is FALSE.                     M
*                                                                            *
* PARAMETERS:                                                                M
*   Crv1:                 To connect to Crv1's starting location at its end. M
*   Crv2:                 To connect to Crv2's end location at its start.    M
*   InterpolateDiscont:   If TRUE, linearly interpolate discontinuity.       M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:     The merged curve.                                   M
*                                                                            *
* KEYWORDS:                                                                  M
*   CagdMergeCrvCrv, merge                                                   M
*****************************************************************************/
CagdCrvStruct *CagdMergeCrvCrv(CagdCrvStruct *Crv1,
			       CagdCrvStruct *Crv2,
			       int InterpolateDiscont)
{
    CagdBType CrvsSharePt;
    int Length, Order, Len1, Len2;
    CagdRType E3Pt1[3], E3Pt2[3];
    CagdPointType CrvPType;
    CagdCrvStruct *Crv;

    if (CAGD_IS_PERIODIC_CRV(Crv1) || CAGD_IS_PERIODIC_CRV(Crv2)) {
	Crv1 = CnvrtPeriodic2FloatCrv(Crv1);
	Crv2 = CnvrtPeriodic2FloatCrv(Crv2);
    }
    else {
	Crv1 = CagdCrvCopy(Crv1);
	Crv2 = CagdCrvCopy(Crv2);
    }

    CagdMakeCrvsCompatible(&Crv1, &Crv2, TRUE, FALSE);
    Order = Crv1 -> Order;
    Len1 = Crv1 -> Length;
    Len2 = Crv2 -> Length;

    /* Verify curve geometric types. */
    switch (Crv1 -> GType) {
	case CAGD_CBEZIER_TYPE:
	    Crv = CnvrtBezier2BsplineCrv(Crv1);
	    CagdCrvFree(Crv1);
	    Crv1 = Crv;
	    break;
	case CAGD_CBSPLINE_TYPE:
	    break;
	case CAGD_CPOWER_TYPE:
	    CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
	    break;
	default:
	    CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
	    break;
    }

    switch (Crv2 -> GType) {
	case CAGD_CBEZIER_TYPE:
	    Crv = CnvrtBezier2BsplineCrv(Crv2);
	    CagdCrvFree(Crv2);
	    Crv2 = Crv;
	    break;
	case CAGD_CBSPLINE_TYPE:
	    break;
	case CAGD_CPOWER_TYPE:
	    CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
	    break;
	default:
	    CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
	    break;
    }

    /* Compute curve point types. */
    CrvPType = Crv1 -> PType;

    /* Figure out if end point of Crv1 is equal to start point of Crv2 and   */
    /* Compute the length of the resulting curve accordingly.		     */
    /* If the same point, then the result can omit one copy and therefore    */
    /* has Len1 + Len2 - 1 Ctl points. If however a linear segment should be */
    /* introduced between the two curves, it should hold Order colinear pts  */
    /* including 2 end points shared with curves or Order - 2 new pts.       */
    CagdCoerceToE3(E3Pt1, Crv1 -> Points, Len1 - 1, Crv1 -> PType);
    CagdCoerceToE3(E3Pt2, Crv2 -> Points, 0, Crv2 -> PType);
    CrvsSharePt = PT_APX_EQ(E3Pt1, E3Pt2);
    Length = CrvsSharePt ? Len1 + Len2 - 1
			 : InterpolateDiscont ? Len1 + Len2 + Order - 2
					      : Len1 + Len2;

    Crv = BspCrvNew(Length, Order, CrvPType);
    CopyCrvOnCrv(Crv, 0, Crv1);
    CopyCrvOnCrv(Crv, Length - Len2, Crv2);
    InterpolateLinearSeg(Crv, Len1 - 1, Length - Len2);

    /* Update the knot vector. We assume open end condition here... */
    CAGD_GEN_COPY(Crv -> KnotVector, Crv1 -> KnotVector,
		  (Len1 + Order - 1) * sizeof(CagdRType));
    if (CrvsSharePt) {
	CAGD_GEN_COPY(&Crv -> KnotVector[Len1 + Order - 1],
		      &Crv2 -> KnotVector[Order],
		      Len2 * sizeof(CagdRType));
	BspKnotAffineTrans(&Crv -> KnotVector[Len1 + Order - 1],
			   Len2,
			   Crv -> KnotVector[Len1 + Order - 2] -
			   Crv2 -> KnotVector[0],
			   1.0);
    }
    else if (InterpolateDiscont) {
	CAGD_GEN_COPY(&Crv -> KnotVector[Len1 + Order - 1],
		      &Crv2 -> KnotVector[1],
		      (Len2 + Order - 1) * sizeof(CagdRType));
	BspKnotAffineTrans(&Crv -> KnotVector[Len1 + Order - 1],
			   Len2 + Order - 1,
			   Crv -> KnotVector[Len1 + Order - 2] -
			   Crv -> KnotVector[Len1 + Order - 1] + 1.0,
			   1.0);
    }
    else {
	CAGD_GEN_COPY(&Crv -> KnotVector[Len1 + Order - 1],
		      &Crv2 -> KnotVector[Order - 1],
		      (Len2 + 1) * sizeof(CagdRType));
	BspKnotAffineTrans(&Crv -> KnotVector[Len1 + Order - 1],
			   Len2 + 1,
			   Crv -> KnotVector[Len1 + Order - 2] -
			   Crv -> KnotVector[Len1 + Order - 1],
			   1.0);
   
    }

    CagdCrvFree(Crv1);
    CagdCrvFree(Crv2);

    return Crv;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Merges a list of curves by connecting the end of one curve to the begining M
* of the next. See also CagdMergeCrvCrv.                                     M
*                                                                            *
* PARAMETERS:                                                                M
*   CrvList:              To connect into one curve.                         M
*   InterpolateDiscont:   If TRUE, linearly interpolate discontinuity.       M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:     The merged curve.                                   M
*                                                                            *
* KEYWORDS:                                                                  M
*   CagdMergeCrvList, merge                                                  M
*****************************************************************************/
CagdCrvStruct *CagdMergeCrvList(CagdCrvStruct *CrvList, int InterpDiscont)
{
    if (CrvList != NULL && CrvList -> Pnext != NULL) {
	CagdCrvStruct
	    *MergedCrv = CrvList;

	for (CrvList = CrvList -> Pnext;
	     CrvList != NULL;
	     CrvList = CrvList -> Pnext) {
	    CagdCrvStruct
		*TmpCrv = CagdMergeCrvCrv(MergedCrv, CrvList,
					  InterpDiscont);

	    CagdCrvFree(MergedCrv);
	    MergedCrv = TmpCrv;
	}
	return MergedCrv;
    }
    else
	return CrvList ? CagdCrvCopy(CrvList) : NULL;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Merges a curve and a point by connecting the end of Crv to Pt, using a     M
* linear segment.                                                            M
*                                                                            *
* PARAMETERS:                                                                M
*   Crv:          To connect to Pt its end.				     M
*   Pt:           To connect to Crv's end point.			     M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:     The merged curve.                                   M
*                                                                            M
* KEYWORDS:                                                                  M
*   CagdMergeCrvPt, merge                                                    M
*****************************************************************************/
CagdCrvStruct *CagdMergeCrvPt(CagdCrvStruct *Crv, CagdPtStruct *Pt)
{
    CagdBType
	CrvNew = FALSE,
	IsRational = CAGD_IS_RATIONAL_CRV(Crv);
    int i, NewLen, NewMaxCoord, Len,
	Order = Crv -> Order,
	PtMaxCoord = APX_EQ(Pt -> Pt[2], 0.0) ? 2 : 3,
	MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
    CagdPointType CrvPType;
    CagdRType t, **Points;
    CagdCrvStruct *NewCrv, *TCrv;

    if (CAGD_IS_PERIODIC_CRV(Crv)) {
	Crv = CnvrtPeriodic2FloatCrv(Crv);
	CrvNew = TRUE;
    }
    Len = Crv -> Length;

    switch (Crv -> GType) {
	case CAGD_CBEZIER_TYPE:
	    TCrv = CnvrtBezier2BsplineCrv(Crv);
	    if (CrvNew)
		CagdCrvFree(Crv);
	    Crv = TCrv;
	    CrvNew = TRUE;
	    break;
	case CAGD_CBSPLINE_TYPE:
	    break;
	case CAGD_CPOWER_TYPE:
	    CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
	    break;
	default:
	    CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
	    break;
    }

    /* Compute curve point types. */
    NewMaxCoord = MAX(PtMaxCoord, MaxCoord);
    CrvPType = CAGD_MAKE_PT_TYPE(IsRational, NewMaxCoord);

    /* A linear segment is added at the end with Order colinear pts.        */
    /* However since first point is curve last point, only Order - 1 new.   */
    NewLen = Len + Order - 1;

    NewCrv = BspCrvNew(NewLen, Order, CrvPType);
    Points = NewCrv -> Points;

    CopyCrvOnCrv(NewCrv, 0, Crv);
    for (i = 1; i <= NewMaxCoord; i++)
	Points[i][NewLen - 1] = Pt -> Pt[i - 1];
    if (IsRational)
	Points[W][NewLen - 1] = 1.0;
    InterpolateLinearSeg(NewCrv, Len - 1, NewLen - 1);

    /* Update the knot vector. We assume open end condition here... */
    CAGD_GEN_COPY(NewCrv -> KnotVector, Crv -> KnotVector,
		  (Len + Order - 1) * sizeof(CagdRType));
    t = Crv -> KnotVector[Len + Order - 1] + 1.0;
    for (i = Len + Order - 1; i < NewLen + Order; i++)
	NewCrv -> KnotVector[i] = t;

    if (CrvNew)
	CagdCrvFree(Crv);

    return NewCrv;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Merges a point and a curve by connecting Pt to the starting point of Crv,  M
* using a linear segment.                                                    M
*                                                                            *
* PARAMETERS:                                                                M
*   Pt:           To connect to Crv's starting point.			     M
*   Crv:          To connect to Pt its starting point.			     M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:     The merged curve.                                   M
*                                                                            M
* KEYWORDS:                                                                  M
*   CagdMergePtCrv, merge                                                    M
*****************************************************************************/
CagdCrvStruct *CagdMergePtCrv(CagdPtStruct *Pt, CagdCrvStruct *Crv)
{
    CagdBType
	CrvNew = FALSE,
	IsRational = CAGD_IS_RATIONAL_CRV(Crv);
    int i, NewLen, NewMaxCoord, Len,
	Order = Crv -> Order,
	PtMaxCoord = APX_EQ(Pt -> Pt[2], 0.0) ? 2 : 3,
	MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
    CagdPointType
	CrvPType = CAGD_PT_E2_TYPE;
    CagdRType t, **Points;
    CagdCrvStruct *NewCrv, *TCrv;

    if (CAGD_IS_PERIODIC_CRV(Crv)) {
	Crv = CnvrtPeriodic2FloatCrv(Crv);
	CrvNew = TRUE;
    }
    Len = Crv -> Length;

    switch (Crv -> GType) {
	case CAGD_CBEZIER_TYPE:
	    TCrv = CnvrtBezier2BsplineCrv(Crv);
	    if (CrvNew)
		CagdCrvFree(Crv);
	    Crv = TCrv;
	    CrvNew = TRUE;
	    break;
	case CAGD_CBSPLINE_TYPE:
	    break;
	case CAGD_CPOWER_TYPE:
	    CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
	    break;
	default:
	    CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
	    break;
    }

    /* Compute curve point types. */
    NewMaxCoord = MAX(PtMaxCoord, MaxCoord);
    CrvPType = CAGD_MAKE_PT_TYPE(IsRational, NewMaxCoord);

    /* A linear segment is added at the end with Order colinear pts.        */
    /* However since first point is curve last point, only Order - 1 new.   */
    NewLen = Len + Order - 1;

    NewCrv = BspCrvNew(NewLen, Order, CrvPType);
    Points = NewCrv -> Points;

    CopyCrvOnCrv(NewCrv, Order - 1, Crv);
    for (i = 1; i <= NewMaxCoord; i++)
	Points[i][0] = Pt -> Pt[i - 1];
    if (IsRational)
	Points[W][0] = 1.0;
    InterpolateLinearSeg(NewCrv, 0, Order - 1);

    /* Update the knot vector. We assume open end condition here... */
    CAGD_GEN_COPY(&NewCrv -> KnotVector[Order], &Crv -> KnotVector[1],
		  (Len + Order - 1) * sizeof(CagdRType));
    t = Crv -> KnotVector[0] - 1.0;
    for (i = 0; i < Order; i++)
	NewCrv -> KnotVector[i] = t;

    if (CrvNew)
	CagdCrvFree(Crv);

    return NewCrv;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Merges two points by connecting Pt1 to Pt2, using a linear segment.        M
*                                                                            *
* PARAMETERS:                                                                M
*   Pt1, Pt2:     Two points to connect using a linear segment.              M
*                                                                            *
* RETURN VALUE:                                                              M
*   CagdCrvStruct *:     The merged curve.                                   M
*                                                                            M
* KEYWORDS:                                                                  M
*   CagdMergePtPt, merge                                                     M
*****************************************************************************/
CagdCrvStruct *CagdMergePtPt(CagdPtStruct *Pt1, CagdPtStruct *Pt2)
{
    CagdPointType
	CrvPType = APX_EQ(Pt1 -> Pt[2], 0.0) && APX_EQ(Pt2 -> Pt[2], 0.0) ?
					CAGD_PT_E2_TYPE : CAGD_PT_E3_TYPE;
    CagdCrvStruct
	*Crv = BzrCrvNew(2, CrvPType);
    CagdRType
	**Points = Crv -> Points;

    Points[X][0] = Pt1 -> Pt[0];
    Points[X][1] = Pt2 -> Pt[0];
    Points[Y][0] = Pt1 -> Pt[1];
    Points[Y][1] = Pt2 -> Pt[1];
    if (CrvPType == CAGD_PT_E3_TYPE) {
    	Points[Z][0] = Pt1 -> Pt[2];
    	Points[Z][1] = Pt2 -> Pt[2];
    }

    return Crv;
}


/*****************************************************************************
* DESCRIPTION:                                                               *
* Copies SrcCrv into DestCrv at point index Index.			     *
*   DestCrv PType is assumed to hold Src PType.				     *
*                                                                            *
* PARAMETERS:                                                                *
*   DestCrv:    Where the copied control points should go to.                *
*   Index:      Index into DestCrv's control polygon.                        *
*   SrcCrv:     Where the copied control points should come from.            *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void CopyCrvOnCrv(CagdCrvStruct *DestCrv,
			 int Index,
			 CagdCrvStruct *SrcCrv)
{
    CagdBType
	IsNotRational = !CAGD_IS_RATIONAL_CRV(SrcCrv);
    int i, j,
	Len = SrcCrv -> Length,
	MaxCoord = CAGD_NUM_OF_PT_COORD(SrcCrv -> PType);
    CagdRType
	**SrcPoints = SrcCrv -> Points,
	**DestPoints = DestCrv -> Points;

    for (i = IsNotRational; i <= MaxCoord; i++)
	CAGD_GEN_COPY(&DestPoints[i][Index], SrcPoints[i],
		      Len * sizeof(CagdRType));

    /* Fix the weights if source did not have them. */
    if (IsNotRational && CAGD_IS_RATIONAL_CRV(DestCrv))
	for (i = Index; i < Index + Len; i++)
	    DestPoints[W][i] = 1.0;

    /* Fix the higher coordinates (by coercing them to zero.) */
    for (i = MaxCoord + 1; i <= CAGD_NUM_OF_PT_COORD(DestCrv -> PType); i++)
	for (j = Index; j < Index + Len; j++)
	    DestPoints[i][j] = 0.0;
}

/*****************************************************************************
* DESCRIPTION:                                                               *
* Linearly interpolates between the Crv points indices Index1 and Index2     *
*                                                                            *
* PARAMETERS:                                                                *
*   Crv:            To add a linear segment between points of Index1 and     *
*                   Index2.						     *
*   Index1, Index2: Indices of first and last points that form the linear    *
*                   segment.                                                 *
*                                                                            *
* RETURN VALUE:                                                              *
*   void                                                                     *
*****************************************************************************/
static void InterpolateLinearSeg(CagdCrvStruct *Crv, int Index1, int Index2)
{
    CagdBType
	IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
    int i, j,
	DIndex = Index2 - Index1,
	MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
    CagdRType
	**Points = Crv -> Points;

    if (DIndex < 2)
	return;				     /* No middle points to interp. */

    for (i = Index1 + 1; i < Index2; i++) {
	CagdRType
	    t1 = ((CagdRType) (i - Index1)) / DIndex,
	    t2 = 1.0 - t1;

	for (j = IsNotRational; j <= MaxCoord; j++)
	    Points[j][i] = t2 * Points[j][Index1] + t1 * Points[j][Index2];
    }
}
