/*
** Copyright 1991, Silicon Graphics, Inc.
** All Rights Reserved.
**
** This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
** the contents of this file may not be disclosed to third parties, copied or
** duplicated in any form, in whole or in part, without the prior written
** permission of Silicon Graphics, Inc.
**
** RESTRICTED RIGHTS LEGEND:
** Use, duplication or disclosure by the Government is subject to restrictions
** as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
** and Computer Software clause at DFARS 252.227-7013, and/or in similar or
** successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
** rights reserved under the Copyright Laws of the United States.
**
** $Revision: 1.16 $
** $Date: 1993/09/23 16:33:23 $
*/
#include "precomp.h"
#pragma hdrstop
#include <fixed.h>

/*
** Clip an input polygon against a clipping plane outputing the new
** vertex pointers in ov and return the number of them.  See the line
** clipping code for an in depth discussion of how "t" is computed.
**
** NOTE: In order to handle non-convex polygons here without dying,
** we count the number of verticies generated by clipping.  If the
** count ever gets to 3, then it must be a non-convex polygon (because
** it means the polygon crossed the clipping plane three times, which is
** impossible for a convex polygon).
*/
static GLint clipToPlane(__GLcontext *gc, __GLvertex **iv, GLint niv,
             __GLvertex **ov, GLuint offs, GLboolean negate)
{
    GLint i, nout, generated;
    __GLvertex *s, *p, *newVertex, *temp;
    __GLfloat pDist, sDist, t;
    PFN_VERTEX_CLIP_PROC clip;
#ifdef GL_WIN_phong_shading
    GLboolean doNormalize = (gc->state.enables.general & 
                             __GL_NORMALIZE_ENABLE);
#endif //GL_WIN_phong_shading

    nout = 0;
    generated = 0;
    temp = gc->transform.nextClipTemp;
    clip = gc->procs.polyClipParam;

    s = iv[niv-1];
    if (negate)
    {
        sDist = s->clip.w - *(__GLfloat *)((GLubyte *)s + offs);
    }
    else
    {
        sDist = *(__GLfloat *)((GLubyte *)s + offs) + s->clip.w;
    }

    for (i = 0; i < niv; i++) {
        p = iv[i];
        if (negate)
        {
            pDist = p->clip.w - *(__GLfloat *)((GLubyte *)p + offs);
        }
        else
        {
            pDist = *(__GLfloat *)((GLubyte *)p + offs) + p->clip.w;
        }

        if (__GL_FLOAT_GEZ(pDist)) {
            /* p is inside the clipping plane half space */
            if (__GL_FLOAT_GEZ(sDist)) {
                /* s is inside the clipping plane half space */
                *ov++ = p;
                nout++;
            } else {
                /* s is outside the clipping plane half space */
                t = pDist / (pDist - sDist);
                newVertex = temp++;
                (*clip)(newVertex, s, p, t);
#ifdef GL_WIN_phong_shading
                if (doNormalize) __glNormalize(&newVertex->normal.x, 
                                               &newVertex->normal.x);
#endif //GL_WIN_phong_shading
#ifndef NT
                // edgeflag is now part of has field.
                newVertex->boundaryEdge = s->boundaryEdge;
#endif
                newVertex->has = s->has;
                newVertex->clipCode = s->clipCode;
                ASSERTOPENGL(newVertex->color ==
                             &newVertex->colors[__GL_FRONTFACE],
                             "Vertex color pointer wrong\n");
                *ov++ = newVertex;
                *ov++ = p;
                nout += 2;
                
                if (++generated >= 3) {
                    /* Toss the non-convex polygon */
                    return 0;
                }
            }
        } else {
            /* p is outside the clipping plane half space */
            if (__GL_FLOAT_GEZ(sDist)) {
                /*
                ** s is inside the clipping plane half space
                **
                ** NOTE: To avoid cracking in polygons with shared
                ** clipped edges we always compute "t" from the out
                ** vertex to the in vertex.  The above clipping code gets
                ** this for free (p is in and s is out).  In this code p
                ** is out and s is in, so we reverse the t computation
                ** and the argument order to __glDoClip.
                */
                t = sDist / (sDist - pDist);
                newVertex = temp++;
                (*clip)(newVertex, p, s, t);
#ifdef GL_WIN_phong_shading
                if (doNormalize) __glNormalize(&newVertex->normal.x, 
                                               &newVertex->normal.x);
#endif //GL_WIN_phong_shading
#ifdef NT
                // edgeflag is now part of has field.
                newVertex->has = s->has | __GL_HAS_EDGEFLAG_BOUNDARY;
                newVertex->clipCode = p->clipCode;
#else
                newVertex->boundaryEdge = GL_TRUE;
                newVertex->has = s->has;
#endif
                ASSERTOPENGL(newVertex->color ==
                             &newVertex->colors[__GL_FRONTFACE],
                             "Vertex color pointer wrong\n");
                *ov++ = newVertex;
                nout++;
                
                if (++generated >= 3) {
                    /* Toss the non-convex polygon */
                    return 0;
                }
            } else {
                /* both points are outside */
            }
        }
        s = p;
        sDist = pDist;
    }
    gc->transform.nextClipTemp = temp;
    return nout;
}

/* 
** Identical to clipToPlane(), except that the clipping is done in eye
** space.
*/
static GLint clipToPlaneEye(__GLcontext *gc, __GLvertex **iv, GLint niv,
                __GLvertex **ov, __GLcoord *plane)
{
    GLint i, nout, generated;
    __GLvertex *s, *p, *newVertex, *temp;
    __GLfloat pDist, sDist, t;
    PFN_VERTEX_CLIP_PROC clip;
#ifdef GL_WIN_phong_shading
    GLboolean doNormalize = (gc->state.enables.general & 
                             __GL_NORMALIZE_ENABLE);
#endif //GL_WIN_phong_shading

    nout = 0;
    generated = 0;
    temp = gc->transform.nextClipTemp;
    clip = gc->procs.polyClipParam;

    s = iv[niv-1];
    sDist = (((POLYDATA *)s)->eye.x * plane->x) +
      (((POLYDATA *)s)->eye.y * plane->y) +
      (((POLYDATA *)s)->eye.z * plane->z) +
      (((POLYDATA *)s)->eye.w * plane->w);
    for (i = 0; i < niv; i++) {
        p = iv[i];
        pDist = (((POLYDATA *)p)->eye.x * plane->x) +
          (((POLYDATA *)p)->eye.y * plane->y) +
          (((POLYDATA *)p)->eye.z * plane->z) +
          (((POLYDATA *)p)->eye.w * plane->w);
        if (__GL_FLOAT_GEZ(pDist)) {
            /* p is inside the clipping plane half space */
            if (__GL_FLOAT_GEZ(sDist)) {
                /* s is inside the clipping plane half space */
                *ov++ = p;
                nout++;
            } else {
                /* s is outside the clipping plane half space */
                t = pDist / (pDist - sDist);
                newVertex = temp++;
                (*clip)(newVertex, s, p, t);
#ifdef GL_WIN_phong_shading
                if (doNormalize) __glNormalize(&newVertex->normal.x, 
                                               &newVertex->normal.x);
#endif //GL_WIN_phong_shading
                ((POLYDATA *)newVertex)->eye.x =
                  t*(((POLYDATA *)s)->eye.x - ((POLYDATA *)p)->eye.x) +
                  ((POLYDATA *)p)->eye.x;
                ((POLYDATA *)newVertex)->eye.y =
                  t*(((POLYDATA *)s)->eye.y - ((POLYDATA *)p)->eye.y) +
                  ((POLYDATA *)p)->eye.y;
                ((POLYDATA *)newVertex)->eye.z =
                  t*(((POLYDATA *)s)->eye.z - ((POLYDATA *)p)->eye.z) +
                  ((POLYDATA *)p)->eye.z;
                ((POLYDATA *)newVertex)->eye.w =
                  t*(((POLYDATA *)s)->eye.w - ((POLYDATA *)p)->eye.w) +
                  ((POLYDATA *)p)->eye.w;
#ifndef NT
                // edgeflag is now part of has field.
                newVertex->boundaryEdge = s->boundaryEdge;
#endif
                newVertex->has = s->has;
                newVertex->clipCode = s->clipCode;
                ASSERTOPENGL(newVertex->color ==
                             &newVertex->colors[__GL_FRONTFACE],
                             "Vertex color pointer wrong\n");
                *ov++ = newVertex;
                *ov++ = p;
                nout += 2;
                
                if (++generated >= 3) {
                    /* Toss the non-convex polygon */
                  return 0;
                }
            }
        } else {
            /* p is outside the clipping plane half space */
            if (__GL_FLOAT_GEZ(sDist)) {
                /*
                ** s is inside the clipping plane half space
                **
                ** NOTE: To avoid cracking in polygons with shared
                ** clipped edges we always compute "t" from the out
                ** vertex to the in vertex.  The above clipping code gets
                ** this for free (p is in and s is out).  In this code p
                ** is out and s is in, so we reverse the t computation
                ** and the argument order to __glDoClip.
                */
                t = sDist / (sDist - pDist);
                newVertex = temp++;
                (*clip)(newVertex, p, s, t);
#ifdef GL_WIN_phong_shading
                if (doNormalize) __glNormalize(&newVertex->normal.x, 
                                               &newVertex->normal.x);
#endif //GL_WIN_phong_shading

                ((POLYDATA *)newVertex)->eye.x =
                  t*(((POLYDATA *)p)->eye.x - ((POLYDATA *)s)->eye.x) +
                  ((POLYDATA *)s)->eye.x;
                ((POLYDATA *)newVertex)->eye.y =
                  t*(((POLYDATA *)p)->eye.y - ((POLYDATA *)s)->eye.y) +
                  ((POLYDATA *)s)->eye.y;
                ((POLYDATA *)newVertex)->eye.z =
                  t*(((POLYDATA *)p)->eye.z - ((POLYDATA *)s)->eye.z) +
                  ((POLYDATA *)s)->eye.z;
                ((POLYDATA *)newVertex)->eye.w =
                  t*(((POLYDATA *)p)->eye.w - ((POLYDATA *)s)->eye.w) +
                  ((POLYDATA *)s)->eye.w;
#ifdef NT
                // edgeflag is now part of has field.
                newVertex->has = s->has | __GL_HAS_EDGEFLAG_BOUNDARY;
                newVertex->clipCode = p->clipCode;
#else
                newVertex->boundaryEdge = GL_TRUE;
                newVertex->has = s->has;
#endif
                ASSERTOPENGL(newVertex->color ==
                             &newVertex->colors[__GL_FRONTFACE],
                             "Vertex color pointer wrong\n");
                *ov++ = newVertex;
                nout++;
                
                if (++generated >= 3) {
                    /* Toss the non-convex polygon */
                  return 0;
                }
            } else {
                /* both points are outside */
            }
        }
        s = p;
        sDist = pDist;
    }
    gc->transform.nextClipTemp = temp;
    return nout;
}

/*
** Each clipping plane can add at most one vertex to a convex polygon (it may
** remove up to all of the verticies).  The clipping will leave a polygon
** convex.  Because of this the maximum number of verticies output from
** the clipToPlane procedure will be total number of clip planes (assuming
** each plane adds one new vertex) plus the original number of verticies
** (3 since this if for triangles).
*/

#ifndef __CLIP_FIX
#define __GL_TOTAL_CLIP_PLANES 20   /*XXX*/
#ifdef NT
#define __GL_MAX_CLIP_VERTEX (__GL_TOTAL_CLIP_PLANES + __GL_MAX_POLYGON_CLIP_SIZE)
#else
#define __GL_MAX_CLIP_VERTEX (__GL_TOTAL_CLIP_PLANES + __GL_NVBUF)
#endif
#endif


void __glDoPolygonClip(__GLcontext *gc, __GLvertex **iv, GLint nout,
                       GLuint allClipCodes)
{
#ifndef __CLIP_FIX 
    __GLvertex *ov[__GL_TOTAL_CLIP_PLANES][__GL_MAX_CLIP_VERTEX];
#endif
    __GLvertex **ivp;
    __GLvertex **ovp;
    __GLvertex *p0, *p1, *p2;
    __GLcoord *plane;
    GLint i;
    __GLviewport *vp;
    __GLfloat one, vpXScale, vpYScale, vpZScale;
    __GLfloat vpXCenter, vpYCenter, vpZCenter;
    PFN_RENDER_TRIANGLE rt;
    __GLfloat llx, lly, urx, ury;
    __GLfloat winx, winy;
    GLuint clipCodes;

    // We have to turn rounding on.  Otherwise, the fast FP-comparison
    // routines below can fail:
    FPU_SAVE_MODE();
    FPU_ROUND_ON_PREC_HI();

    /*
    ** Reset nextClipTemp pointer for any new verticies that are generated
    ** during the clipping.
    */
    gc->transform.nextClipTemp = gc->transform.clipTemp;

    ivp = &iv[0];

    /*
    ** Check each of the clipping planes by examining the allClipCodes
    ** mask. Note that no bits will be set in allClipCodes for clip
    ** planes that are not enabled.
    */
    if (allClipCodes) {
        /* Now clip against the clipping planes */
#ifndef __CLIP_FIX
        ovp = &ov[0][0];
#else
        ovp = &(((__GLGENcontext *)gc)->pwndLocked->buffers->clip_verts[0][0]);
#endif
        /* 
        ** Do user clip planes first, because we will maintain eye coordinates
        ** only while doing user clip planes.  They are ignored for the 
        ** frustum clipping planes.
        */
        clipCodes = allClipCodes >> 6;
        if (clipCodes) {
            plane = &gc->state.transform.eyeClipPlanes[0];
            do {
                if (clipCodes & 1) {
                    nout = clipToPlaneEye(gc, ivp, nout, ovp, plane);
                    ASSERTOPENGL(nout <= __GL_MAX_CLIP_VERTEX,
                                 "Too many clip vertices\n");
                    if (nout < 3) {
                        FPU_RESTORE_MODE();
                        return;
                    }
                    ivp = ovp;
                    ovp += __GL_MAX_CLIP_VERTEX;
                }
                clipCodes >>= 1;
                plane++;
            } while (clipCodes);
        }

        allClipCodes &= __GL_FRUSTUM_CLIP_MASK;
        if (allClipCodes) {
            i = 0;
            do {
                if (allClipCodes & 1) {
                    nout = clipToPlane(gc, ivp, nout, ovp,
                                       __glFrustumOffsets[i],
                                       (GLboolean)(i & 1));
                    ASSERTOPENGL(nout <= __GL_MAX_CLIP_VERTEX,
                                 "Too many clip vertices\n");
                    if (nout < 3) {
                        FPU_RESTORE_MODE();
                        return;
                    }
                    ivp = ovp;
                    ovp += __GL_MAX_CLIP_VERTEX;
                }
                allClipCodes >>= 1;
                i++;
            } while (allClipCodes);
        }

        /*
        ** Calculate final screen coordinates.  Next phase of polygon
        ** processing assumes that window coordinates are already computed.
        */
        vp = &gc->state.viewport;
        vpXCenter = vp->xCenter;
        vpYCenter = vp->yCenter;
        vpZCenter = vp->zCenter;
        vpXScale = vp->xScale;
        vpYScale = vp->yScale;
        vpZScale = vp->zScale;
        ovp = ivp;
        one = __glOne;
        
        llx = vpXCenter - vpXScale;
        urx = vpXCenter + vpXScale;
        if (vpYScale > 0) {
            lly = vpYCenter - vpYScale;
            ury = vpYCenter + vpYScale;
        } else {
            lly = vpYCenter + vpYScale;
            ury = vpYCenter - vpYScale;
        }
        
        for (i = nout; --i >= 0; ) {
            __GLfloat x, y, z, wInv;

            p0 = *ovp++;
            
            // If the clipCode is zero then the window coordinates
            // were computed at the time of clipCode determination
            // Generated vertices' clipCodes are set to the out vertex
            // to ensure that their window coords are computed
            if (p0->clipCode != 0)
            {
#ifdef NT
                /* XXX (mf) prevent divide-by-zero */
                if (__GL_FLOAT_EQZ(p0->clip.w))
                    wInv = __glZero;
                else 
                    wInv = one / p0->clip.w;
#else
                wInv = one / p0->clip.w;
#endif
                x = p0->clip.x; y = p0->clip.y; z = p0->clip.z;
                winx = x * vpXScale * wInv + vpXCenter;
                winy = y * vpYScale * wInv + vpYCenter;
                p0->window.z = z * vpZScale * wInv + vpZCenter;
                p0->window.w = wInv;
                /* 
                ** Check if these window coordinates are legal.  At this 
                ** point, it is quite possible that they are not.  Trivially
                ** pull them into the legal viewport region if necessary.
                */
                if (winx < llx) winx = llx;
                else if (winx > urx) winx = urx;
                if (winy < lly) winy = lly;
                else if (winy > ury) winy = ury;
                p0->window.x = winx;
                p0->window.y = winy;
            }
        }
    }

    // Restore mode before rendering
    FPU_RESTORE_MODE();

#if 0 //def GL_WIN_phong_shading
    if (gc->state.light.shadingModel == GL_PHONG_EXT)
    {
        __GLvertex *minv;
        __GLvertex **cv;
        GLint j, index;

        minv = *ivp; index=0;
        
        //Reorder the vertices so that p0 is the one with the least y and x 
        for (i=0, cv=ivp; i<nout; i++, cv++)
        {
            if (__GL_VERTEX_COMPARE((*cv)->window.y, <, minv->window.y))
            {
                minv = *cv;
                index = i;
            }
            else if (__GL_VERTEX_COMPARE((*cv)->window.y, ==, minv->window.y))
            {
                if (__GL_VERTEX_COMPARE((*cv)->window.x, <, minv->window.x))
                {
                    minv = *cv;
                    index = i;
                }
            }
        }

        DbgPrint ("MinIndex = %d\n", index);
        
        j = index;
        p0 = (__GLvertex *) ivp[j];
        p1 = (__GLvertex *) ivp[(++j)%nout];
        p2 = (__GLvertex *) ivp[(++j)%nout];
        rt = gc->procs.renderTriangle;
        if (nout == 3) 
        {
            (*rt)(gc, p0, p1, p2);
        } 
        else 
        {
            for (i = 0; i < nout - 2; i++) 
            {
                GLuint t1, t2;
                if (i == 0) 
                {
                    /*
                    ** Third edge of first sub-triangle is always non-boundary
                    */
                    // edgeflag is now part of has field.
                    t1 = p2->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                    p2->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                    (*rt)(gc, p0, p1, p2);
                    p2->has |= t1;
                } 
                else
                    if (i == nout - 3) 
                    {
                        /*
                        ** First edge of last sub-triangle is always 
                        ** non-boundary
                        */
                        // edgeflag is now part of has field.
                        t1 = p0->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                        p0->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                        (*rt)(gc, p0, p1, p2);
                        p0->has |= t1;
                    } 
                    else 
                    {
                        /*
                        ** Interior sub-triangles have the first and last edge
                        ** marked non-boundary
                        */
                        // edgeflag is now part of has field.
                        t1 = p0->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                        t2 = p2->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                        p0->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                        p2->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                        (*rt)(gc, p0, p1, p2);
                        p0->has |= t1;
                        p2->has |= t2;
                    }
                p1 = p2;
                p2 = (__GLvertex *) ivp[(++j)%nout];
            }
        }
    }
    else
    {
#endif //GL_WIN_phong_shading

    /*
    ** Subdivide the clipped polygon into triangles.  Only convex polys
    ** are supported so this is okay to do.  Non-convex polys will do
    ** something odd here, but thats the clients fault.
    */
    p0 = *ivp++;
    p1 = *ivp++;
    p2 = *ivp++;
    rt = gc->procs.renderTriangle;
    if (nout == 3) 
    {
        (*rt)(gc, p0, p1, p2);
    } 
    else 
    {
        for (i = 0; i < nout - 2; i++) 
        {
              GLuint t1, t2;
              if (i == 0) 
              {
                  /*
                  ** Third edge of first sub-triangle is always non-boundary
                  */
                  // edgeflag is now part of has field.
                  t1 = p2->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                  p2->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                  (*rt)(gc, p0, p1, p2);
                  p2->has |= t1;
              } 
              else
                  if (i == nout - 3) 
                  {
                      /*
                      ** First edge of last sub-triangle is always 
                      ** non-boundary
                      */
                      // edgeflag is now part of has field.
                      t1 = p0->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                      p0->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                      (*rt)(gc, p0, p1, p2);
                      p0->has |= t1;
                  } 
                  else 
                  {
                      /*
                      ** Interior sub-triangles have the first and last edge
                      ** marked non-boundary
                      */
                      // edgeflag is now part of has field.
                      t1 = p0->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                      t2 = p2->has & __GL_HAS_EDGEFLAG_BOUNDARY;
                      p0->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                      p2->has &= ~__GL_HAS_EDGEFLAG_BOUNDARY;
                      (*rt)(gc, p0, p1, p2);
                      p0->has |= t1;
                      p2->has |= t2;
                  }
              p1 = p2;
              p2 = (__GLvertex *) *ivp++;
        }
    }
#if 0 //def GL_WIN_phong_shading
    }
#endif //GL_WIN_phong_shading
}

void FASTCALL __glClipPolygon(__GLcontext *gc, __GLvertex *v0, GLint nv)
{
#ifdef NT
    __GLvertex *iv[__GL_MAX_POLYGON_CLIP_SIZE];
#else
    __GLvertex *iv[__GL_NVBUF];
#endif
    __GLvertex **ivp;
    GLint i;
    GLuint andCodes, orCodes;

    gc->vertex.provoking = v0;

    /*
    ** Generate array of addresses of the verticies.  And all the
    ** clip codes together while we are at it.
    */
    ivp = &iv[0];
    andCodes = (GLuint)(-1);
    orCodes = 0;
    for (i = nv; --i >= 0; ) {
    andCodes &= v0->clipCode;
    orCodes |= v0->clipCode;
    *ivp++ = v0++;
    }

    if (andCodes != 0) {
    /*
    ** Trivially reject the polygon.  If andCodes is non-zero then
    ** every vertex in the polygon is outside of the same set of
    ** clipping planes (at least one).
    */
    return;
    }
    __glDoPolygonClip(gc, &iv[0], nv, orCodes);
}

void FASTCALL __glClipTriangle(__GLcontext *gc, __GLvertex *a, __GLvertex *b,
              __GLvertex *c, GLuint orCodes)
{
    __GLvertex *iv[3];

    iv[0] = a;
    iv[1] = b;
    iv[2] = c;

    __glDoPolygonClip(gc, &iv[0], 3, orCodes);
}