/*
 * $Id: hclip.c,v 1.1.1.1 2000/04/07 19:44:51 hfrieden Exp $
 *
 * $Date: 2000/04/07 19:44:51 $
 * $Revision: 1.1.1.1 $
 *
 * (C) 1999 by Hyperion
 * All rights reserved
 *
 * This file is part of the MiniGL library project
 * See the file Licence.txt for more details
 *
 */

static char rcsid[] = "$Id: hclip.c,v 1.1.1.1 2000/04/07 19:44:51 hfrieden Exp $";

#include "sysinc.h"
#include <math.h>

#define DUMP_VERTEX(vert) \
 mykprintf("x:%6.3f y:%6.3f z:%6.3f w:%6.3f\nR:%6.3f G:%6.3f B:%6.3f A:%6.3f\nU:%6.3f V:%6.3f\noutcode=0x%X\n",\
         (vert).bx, (vert).by, (vert).bz, (vert).bw,                                                                                      \
         (vert).v.color.r, (vert).v.color.g, (vert).v.color.b, (vert).v.color.a,                                                          \
         (vert).v.u, (vert).v.v, (vert).outcode)


#define LERP(t,a,b) \
    (a) + (float)t * ( (b) - (a) )

#define INTERPOLATE(res,t,a,b) \
    res->bx = LERP(t,a->bx, b->bx); \
    res->by = LERP(t,a->by, b->by); \
    res->bz = LERP(t,a->bz, b->bz); \
    res->bw = LERP(t,a->bw, b->bw); \
    res->v.color.a = LERP(t,a->v.color.a, b->v.color.a); \
    res->v.color.r = LERP(t,a->v.color.r, b->v.color.r); \
    res->v.color.g = LERP(t,a->v.color.g, b->v.color.g); \
    res->v.color.b = LERP(t,a->v.color.b, b->v.color.b); \
    res->v.u = LERP(t,a->v.u, b->v.u); \
    res->v.v = LERP(t,a->v.v, b->v.v);

#define CLIP_EPS (1e-7)

void hc_CodePoint(MGLVertex *v)
{
    float w = v->bw;
    v->outcode = 0;

    if (v->bw < CLIP_EPS )
    {
        v->outcode |= MGL_CLIP_NEGW;
    }

    if (-w > v->bx)
    {
        v->outcode |= MGL_CLIP_LEFT;
    }
    else
    if (v->bx > w)
    {
        v->outcode |= MGL_CLIP_RIGHT;
    }

    if (-w > v->by)
    {
        v->outcode |= MGL_CLIP_BOTTOM;
    }
    else
    if (v->by > w)
    {
        v->outcode |= MGL_CLIP_TOP;
    }

    if (-w > v->bz)
    {
        v->outcode |= MGL_CLIP_BACK;
    }
    else
    if (v->bz > w)
    {
        v->outcode |= MGL_CLIP_FRONT;
    }
}

#define x1 (a->bx)
#define y1 (a->by)
#define z1 (a->bz)
#define w1 (a->bw)

#define x2 (b->bx)
#define y2 (b->by)
#define z2 (b->bz)
#define w2 (b->bw)

#ifdef GLNDEBUG
#define DEBUG_CLIP(name,code) code
#else
#define DEBUG_CLIP(name,code) \
    mykprintf("%s: t=%f\n", #name, t);\
    DUMP_VERTEX(*a); \
    DUMP_VERTEX(*b); \
    code             \
    DUMP_VERTEX(*r);
#endif

static void hc_ClipWZero(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (CLIP_EPS-w1)/(w2-w1);
    r->bx = LERP(t,a->bx, b->bx);
    r->by = LERP(t,a->by, b->by);
    r->bz = LERP(t,a->bz, b->bz);
    r->bw = CLIP_EPS;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

static void hc_ClipTop(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (w1-y1)/((w1-y1)-(w2-y2));
    r->bx = LERP(t,a->bx, b->bx);
    r->bz = LERP(t,a->bz, b->bz);
    r->bw = LERP(t,a->bw, b->bw);
    r->by = r->bw;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

static void hc_ClipBottom(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (w1+y1)/((w1+y1)-(w2+y2));
    r->bx = LERP(t,a->bx, b->bx);
    r->bz = LERP(t,a->bz, b->bz);
    r->bw = LERP(t,a->bw, b->bw);
    r->by = -r->bw;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

static void hc_ClipLeft(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (w1+x1)/((w1+x1)-(w2+x2));
    r->by = LERP(t,a->by, b->by);
    r->bz = LERP(t,a->bz, b->bz);
    r->bw = LERP(t,a->bw, b->bw);
    r->bx = -r->bw;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

static void hc_ClipRight(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (w1-x1)/((w1-x1)-(w2-x2));
    r->by = LERP(t,a->by, b->by);
    r->bz = LERP(t,a->bz, b->bz);
    r->bw = LERP(t,a->bw, b->bw);
    r->bx = r->bw;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

static void hc_ClipFront(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (w1-z1)/((w1-z1)-(w2-z2));
    r->bx = LERP(t,a->bx, b->bx);
    r->by = LERP(t,a->by, b->by);
    r->bw = LERP(t,a->bw, b->bw);
    r->bz = r->bw;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

static void hc_ClipBack(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
    float t = (w1+z1)/((w1+z1)-(w2+z2));
    r->bx = LERP(t,a->bx, b->bx);
    r->by = LERP(t,a->by, b->by);
    r->bw = LERP(t,a->bw, b->bw);
    r->bz = -r->bw;
    r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
    r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
    r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
    r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
    r->v.u = LERP(t,a->v.u, b->v.u);
    r->v.v = LERP(t,a->v.v, b->v.v);
    hc_CodePoint(r);
}

#undef x1
#undef y1
#undef z1
#undef w1
#undef x2
#undef y2
#undef z2
#undef w2

GLboolean hc_DecideFrontface(GLcontext context, MGLVertex *a, MGLVertex *b, MGLVertex *c, GLubyte outcode)
{
    GLboolean front;
    float a1,a2,b1,b2,r;
    float aw,bw,cw;

    if (context->CullFace_State == GL_FALSE) return GL_TRUE;
    if (context->CurrentCullFace == GL_FRONT_AND_BACK) return GL_FALSE;

    /*
    ** The following line returns GL_TRUE if one or more of the vertices lie beyond the
    ** camera plane. This is of course a wrong assumption, but those will be culled at
    ** the clipping stage after the negative W coordinates have been removed.
    */
    if (outcode&MGL_CLIP_NEGW) return GL_TRUE;

    aw = 1.0 / a->bw;
    bw = 1.0 / b->bw;
    cw = 1.0 / c->bw;

    #define EPSILON 1e-5

    a1 = a->bx*aw - b->bx*bw;
    a2 = a->by*aw - b->by*bw;
    b1 = c->bx*cw - b->bx*bw;
    b2 = c->by*cw - b->by*bw;
    r  = a1*b2-a2*b1;

    if (fabs(a1) < EPSILON && fabs(a2) < EPSILON)
    {
        return GL_TRUE;
    }

    if (fabs(b1) < EPSILON && fabs(b2) < EPSILON)
    {
        return GL_TRUE;
    }


    if ((r < 0.0 && context->CurrentFrontFace == GL_CCW) ||
        (r > 0.0 && context->CurrentFrontFace == GL_CW))
    {
        front = GL_TRUE;
    }
    else
    {
        front = GL_FALSE;
    }

    if (context->CurrentCullFace == GL_BACK)
    {
        return front;
    }
    else
    {
        return !front;
    }
}

void GLFrontFace(GLcontext context, GLenum mode)
{
    if (mode == GL_CW || mode == GL_CCW)
    {
        context->CurrentFrontFace = mode;
    }
    else
    {
        GLFlagError(context, 1, GL_INVALID_ENUM);
    }
}

void GLCullFace(GLcontext context, GLenum mode)
{
    if (mode == GL_FRONT || mode == GL_FRONT_AND_BACK || mode == GL_BACK)
    {
        context->CurrentCullFace = mode;
    }
    else
    {
        GLFlagError(context, 1, GL_INVALID_ENUM);
    }
}

/*
** Complicated clipping macro stuff.
*/

#define VERTP(i) &(context->VertexBuffer[a->verts[i]])
#define VERT(i) context->VertexBuffer[a->verts[i]]
#define POLYSWAP \
    if (b->numverts == 0) return; \
    temp=a; a=b; b=temp; \

#define DOCLIP(edge, routine)                                           \
    if (or_codes & edge)                                                 \
    {                                                                     \
        b->numverts = 0;                                                   \
        prev = a->numverts-1;                                               \
        for (i=0; i<a->numverts; i++)                                        \
        {                                                                     \
            /* Case 1 and 4*/                                                  \
            if (!(VERT(prev).outcode & edge))                                   \
            {                                                                    \
                b->verts[b->numverts] = a->verts[prev];                           \
                b->numverts++;                                                     \
            }                                                                       \
            /* Case 3 and 4 */                                                       \
            if ((VERT(prev).outcode ^ VERT(i).outcode) & edge)                        \
            {                                                                          \
                hc_##routine (VERTP(prev), VERTP(i), &(context->VertexBuffer[free]));   \
                b->verts[b->numverts]=free++;                                            \
                b->numverts++;                                                            \
            }                                                                              \
            prev = i;                                                                       \
        }                                                                                    \
        POLYSWAP                                                                              \
    }                                                                                          \


extern void dh_DrawPoly(GLcontext context, MGLPolygon *poly);
extern void dh_DrawPolyFF(GLcontext context, MGLPolygon *poly);

#ifndef GLNDEBUG
void hc_DumpPolygon(GLcontext context, MGLPolygon *poly, char *string, int clipcode)
{
    int i;
    mykprintf("--- %s (0x%X) -- (%d vertices)\n", string,clipcode, poly->numverts);
    for (i=0; i<poly->numverts; i++)
    {
        DUMP_VERTEX(context->VertexBuffer[poly->verts[i]]);
    }
    mykprintf("-------------------------\n");
}

#define CLIPDBG(string,code) \
    hc_DumpPolygon(context,a,#string,code);

#else

#define CLIPDBG(string,code)

#endif


void hc_ClipAndDrawPoly(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
{
    /*
    ** Sutherland-Hodgeman clipping algorithm (almost)
    **
    ** This clipping algorithm sucessively clips against each of the six
    ** clipping planes (additional client-defined clipping planes would
    ** be possible, those would be added to the back of this).
    ** Vertices are copied from a to b and swapped at the end.
    ** Output occurs within the clipping region:
    **
    **                | b
    **               i|/|
    **               /| |
    **              / | |c
    **            a/  |/
    **             | /|j
    **             |/ |
    **            d/  |
    **                |clip plane
    **
    ** In the above figure, the algorithm first consideres edge d-a. Since it
    ** does not cross the clipping plane, it outputs d and proceeds to edge
    ** a-b. Since it crosses, it outputs a, calculates intersection i and outputs it.
    ** No output occurs while b-c is considered, since it lies outside the frustum
    ** and does not cross it. Finally, edge c-d yields output j.
    **
    ** The result is d-a-i-j
    **
    ** Classification of edges are divided into four cases:
    ** Case 1: Edge is completely inside -> two vertices
    ** Case 2: Edge is completely outside -> no output
    ** Case 3: Edge enters the frustum -> one output
    ** Case 4: Edge leaves frustum -> two outputs
    **
    ** At any stage, if the output polygon has zero vertices, return immediately.
    */

    MGLPolygon output;
    MGLPolygon *a, *b, *temp;
    int i,j;
    int prev;
    int free = context->VertexBufferPointer;
    GLboolean flag;
    GLubyte original_or_codes = or_codes;

    a = poly; b=&output;

    CLIPDBG(ClipWZero, MGL_CLIP_NEGW)
    DOCLIP(MGL_CLIP_NEGW, ClipWZero);

    for (j=0;j<a->numverts; j++) or_codes |= context->VertexBuffer[a->verts[j]].outcode;

    CLIPDBG(ClipLeft, MGL_CLIP_LEFT)
    DOCLIP(MGL_CLIP_LEFT, ClipLeft)

    CLIPDBG(ClipRight, MGL_CLIP_RIGHT)
    DOCLIP(MGL_CLIP_RIGHT, ClipRight)

    CLIPDBG(ClipFront, MGL_CLIP_FRONT)
    DOCLIP(MGL_CLIP_FRONT, ClipFront)

    CLIPDBG(ClipBack, MGL_CLIP_BACK)
    DOCLIP(MGL_CLIP_BACK, ClipBack)

    CLIPDBG(ClipTop, MGL_CLIP_TOP)
    DOCLIP(MGL_CLIP_TOP, ClipTop)

    CLIPDBG(ClipBottom, MGL_CLIP_BOTTOM)
    DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)

    CLIPDBG(Final,0)
    if ((original_or_codes & MGL_CLIP_NEGW) && a->numverts>2)
    {
        flag = hc_DecideFrontface(context,
            &(context->VertexBuffer[a->verts[0]]),
            &(context->VertexBuffer[a->verts[1]]),
            &(context->VertexBuffer[a->verts[2]]), 0);
        if (flag == GL_FALSE)
            return;
    }

    // If we get here, there are vertices left...
    dh_DrawPoly(context, a);
}

void hc_ClipAndDrawPolyFF(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
{
    MGLPolygon output;
    MGLPolygon *a, *b, *temp;
    int i,j;
    int prev;
    int free = context->VertexBufferPointer;

    a = poly; b=&output;

    CLIPDBG(ClipWZero, MGL_CLIP_NEGW)
    DOCLIP(MGL_CLIP_NEGW, ClipWZero);

    for (j=0;j<a->numverts; j++) or_codes |= context->VertexBuffer[a->verts[j]].outcode;

    CLIPDBG(ClipLeft, MGL_CLIP_LEFT)
    DOCLIP(MGL_CLIP_LEFT, ClipLeft)

    CLIPDBG(ClipRight, MGL_CLIP_RIGHT)
    DOCLIP(MGL_CLIP_RIGHT, ClipRight)

    CLIPDBG(ClipFront, MGL_CLIP_FRONT)
    DOCLIP(MGL_CLIP_FRONT, ClipFront)

    CLIPDBG(ClipBack, MGL_CLIP_BACK)
    DOCLIP(MGL_CLIP_BACK, ClipBack)

    CLIPDBG(ClipTop, MGL_CLIP_TOP)
    DOCLIP(MGL_CLIP_TOP, ClipTop)

    CLIPDBG(ClipBottom, MGL_CLIP_BOTTOM)
    DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)

    CLIPDBG(Final,0)

    // If we get here, there are vertices left...
    dh_DrawPolyFF(context, a);
}