Tclip.c

Go to the documentation of this file.

/****************************************************************************************/
/*  TClip                                                                               */
/*                                                                                      */
/*  Author: Mike Sandige & Charles Bloom                                                */
/*  Description: Triangle Clipping to the screen rectangle                              */
/*                                                                                      */
/*  The contents of this file are subject to the Genesis3D Public License               */
/*  Version 1.01 (the "License"); you may not use this file except in                   */
/*  compliance with the License. You may obtain a copy of the License at                */
/*  http://www.genesis3d.com                                                            */
/*                                                                                      */
/*  Software distributed under the License is distributed on an "AS IS"                 */
/*  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See                */
/*  the License for the specific language governing rights and limitations              */
/*  under the License.                                                                  */
/*                                                                                      */
/*  The Original Code is Genesis3D, released March 25, 1999.                            */
/*  Copyright (C) 1996-1999 Eclipse Entertainment, L.L.C. All Rights Reserved           */
/*                                                                                      */
/****************************************************************************************/

//#define DO_TIMER

/*********

Cbloom Jan 18
TClip gained 2-3 fps
(not counting the gains already from _SetTexture)

I reorganized the TClip_Triangle function flow to early-out 
for triangles all-in or all-out.  The old code considered this
case, but was not as lean as possible for these most-common cases.

To solve these problems, flow was changed to :
        1. do all compares and accumulated the 3 out bits for each of the five faces
                (so we have 15 bit-flags)
        2. then do clips while more clips remain.
        3. as a free benefit, the new structure means that Rasterize is only called once
                        in TClip_Triangle, so it was inlined.

Step two results in very fast exiting when no clipping remains.


If/When we get the Intel compiler that can optimize ?: to CMOV, speed will improve
even more!

-----------------------------------

Timer profiling shows:
(with D3DDrv, in ActView, viewing dema.act)
times are seconds per frame

default pose : 58.6 fps
TClip_New            : 0.006749
TClip_Rasterize      : 0.006149

default pose : 52.9 fps
TClip_Old            : 0.007230 : 1.$ %
TClip_Rasterize      : 0.006183 : 1.$ %

***********/

// TClip.c
//  Fast Triangle Clipping
/*}{***********************/

#include <assert.h>
#include <string.h>

#include "TClip.h"
#include "engine.h"
#include "bitmap._h"

#include "list.h"
#include "ram.h"  

#include "timer.h"

TIMER_VARS(TClip_Triangle);

//#define ONE_OVER_Z_PIPELINE   // this has more accuracy, but the slowness of doing 1/ divides

typedef enum 
{       
        BACK_CLIPPING_PLANE = 0,
        LEFT_CLIPPING_PLANE,
        RIGHT_CLIPPING_PLANE,
        TOP_CLIPPING_PLANE,
        BOTTOM_CLIPPING_PLANE,
        NUM_CLIPPING_PLANES
} geTClip_ClippingPlane;

// 3 bits for V_IN/OUT flags
#define V_ALL_IN (0)
#define V0_OUT  (1)
#define V1_OUT  (2)
#define V2_OUT  (4)

        // at a=0, result is l;  at a=1, result is h
#define LINEAR_INTERPOLATE(a,l,h)     ((l)+(((h)-(l))*(a)))
 
#define RASTERIZECC 
typedef void (RASTERIZECC *geTClip_Rasterize_FuncPtr) (const GE_LVertex * TriVtx);

typedef struct geTClip_StaticsType
{
        geFloat LeftEdge;
        geFloat RightEdge;
        geFloat TopEdge;
        geFloat BottomEdge;
        geFloat BackEdge;

        DRV_Driver * Driver;
        geEngine        *Engine;
        const geBitmap *Bitmap;
        geRDriver_THandle * THandle;

        geTClip_Rasterize_FuncPtr RasterizeFunc;

        uint32 RenderFlags;             // LA

} geTClip_StaticsType;

/*}{************ Protos ***********/

static void RASTERIZECC geTClip_Rasterize_Tex(const GE_LVertex * TriVtx);
static void RASTERIZECC geTClip_Rasterize_Gou(const GE_LVertex * TriVtx);
static void GENESISCC geTClip_Split(GE_LVertex *NewVertex,const GE_LVertex *V1,const GE_LVertex *V2,int ClippingPlane);
static void GENESISCC geTClip_TrianglePlane(const GE_LVertex * zTriVertex,geTClip_ClippingPlane ClippingPlane);
static void GENESISCC geTClip_TrianglePlane_Old(const GE_LVertex * zTriVertex,geTClip_ClippingPlane ClippingPlane);

/*}{************ The State Statics ***********/

static Link * geTClip_Link = NULL;
static geTClip_StaticsType geTClip_Statics;
static uint32 ActiveRenderFlags = 0;    // LA

/*}{************ Functions ***********/

// LA
void GENESISCC geTClip_SetRenderFlags(uint32 newflags)
{
        geTClip_Statics.RenderFlags = newflags;
        ActiveRenderFlags = newflags;
        return;
}

geBoolean GENESISCC geTClip_Push(void)
{
geTClip_StaticsType * TCI;

        geTClip_Statics.RenderFlags = ActiveRenderFlags; // LA

        if ( ! geTClip_Link )
        {
                List_Start();
                geTClip_Link = Link_Create();
                if ( ! geTClip_Link ) 
                        return GE_FALSE;
        }

        TCI = geRam_Allocate(sizeof(geTClip_StaticsType));
        if ( ! TCI )
                return GE_FALSE;
        memcpy(TCI,&geTClip_Statics,sizeof(geTClip_StaticsType));

        Link_Push( geTClip_Link , TCI );

        geTClip_Statics.RenderFlags = 0;        // LA, this is needed to set RF = 0 for default after any _Push
        
        return GE_TRUE;
}

geBoolean GENESISCC geTClip_Pop(void)
{
geTClip_StaticsType * TCI;
        if ( ! geTClip_Link )
                return GE_FALSE;
        TCI = Link_Pop( geTClip_Link );
        if ( ! TCI )
                return GE_FALSE;
        memcpy(&geTClip_Statics,TCI,sizeof(geTClip_StaticsType));
        geRam_Free(TCI);

        if ( ! Link_Peek(geTClip_Link) )
        {
                Link_Destroy(geTClip_Link);
                geTClip_Link = NULL;
                List_Stop();
        }

        ActiveRenderFlags = geTClip_Statics.RenderFlags; // LA, set ARF from newly pop'd statics
        
        return GE_TRUE;
}

geBoolean GENESISCC geTClip_SetTexture(const geBitmap * Bitmap)
{
        geTClip_Statics.Bitmap = Bitmap;
        if ( Bitmap )
        {
                geTClip_Statics.THandle = geBitmap_GetTHandle(Bitmap);
                assert(geTClip_Statics.THandle);
                geTClip_Statics.RasterizeFunc = geTClip_Rasterize_Tex;
        }
        else
        {
                geTClip_Statics.THandle = NULL;
                geTClip_Statics.RasterizeFunc = geTClip_Rasterize_Gou;
        }
return GE_TRUE;
}

void GENESISCC geTClip_SetupEdges(
        geEngine *Engine,
        geFloat LeftEdge, 
        geFloat RightEdge,
        geFloat TopEdge ,
        geFloat BottomEdge,
        geFloat BackEdge)
{ 
        assert(Engine);
        memset(&geTClip_Statics,0,sizeof(geTClip_Statics));
        geTClip_Statics.Engine          = Engine;
        geTClip_Statics.Driver          = Engine->DriverInfo.RDriver; //Engine_GetRDriver(Engine);
        geTClip_Statics.LeftEdge        = LeftEdge;
        geTClip_Statics.RightEdge       = RightEdge;
        geTClip_Statics.TopEdge         = TopEdge;
        geTClip_Statics.BottomEdge      = BottomEdge;
        geTClip_Statics.BackEdge        = BackEdge;
}

void geTClip_Done(void)
{
        TIMER_REPORT(TClip_Triangle);
}

void GENESISCC geTClip_Triangle(const GE_LVertex TriVertex[3])
{

        TIMER_P(TClip_Triangle);

#if 1
        geTClip_TrianglePlane(TriVertex,BACK_CLIPPING_PLANE);
        //geTClip_TrianglePlane(TriVertex,LEFT_CLIPPING_PLANE);
#else
        geTClip_TrianglePlane_Old(TriVertex,BACK_CLIPPING_PLANE);
#endif

        TIMER_Q(TClip_Triangle);
}

/*}{************ TClip_Rasterize ***********/

static void RASTERIZECC geTClip_Rasterize_Tex(const GE_LVertex * TriVtx)
{
        geTClip_Statics.Driver->RenderMiscTexturePoly((DRV_TLVertex *)TriVtx,
                3,geTClip_Statics.THandle, ActiveRenderFlags); // LA
}

static void RASTERIZECC geTClip_Rasterize_Gou(const GE_LVertex * TriVtx)
{
        geTClip_Statics.Driver->RenderGouraudPoly((DRV_TLVertex *)TriVtx,3,ActiveRenderFlags); // LA
}

static void GENESISCC geTClip_Rasterize(const GE_LVertex * TriVtx)
{

// we require GE_LVertex == DRV_TLVertex == GE_TLVertex
//      this is a silly point because the TClip inputs should really be GE_TLVertex anyway !!!!

        if ( geTClip_Statics.THandle )
        {
                geTClip_Statics.Driver->RenderMiscTexturePoly((DRV_TLVertex *)TriVtx,
                        3,geTClip_Statics.THandle,ActiveRenderFlags);   // LA
        }
        else
        {
                geTClip_Statics.Driver->RenderGouraudPoly((DRV_TLVertex *)TriVtx,
                        3,ActiveRenderFlags); // LA
        }
}

/*}{************ TClip_Split ***********/

static void GENESISCC geTClip_Split(GE_LVertex *NewVertex,const GE_LVertex *V1,const GE_LVertex *V2,int ClippingPlane)
{
        geFloat Ratio=0.0f;
        geFloat OneOverZ1,OneOverZ2;
        
        #ifdef ONE_OVER_Z_PIPELINE
                // in here ->Z is really (one over z)
        OneOverZ1 = V1->Z;
        OneOverZ2 = V2->Z;
        #else
        OneOverZ1 = 1.0f/V1->Z;
        OneOverZ2 = 1.0f/V2->Z;
        #endif

        switch (ClippingPlane)
        {
                case (BACK_CLIPPING_PLANE):
                        assert((V2->Z - V1->Z)!=0.0f);
                        Ratio = ((1.0f/geTClip_Statics.BackEdge) - OneOverZ2)/( OneOverZ1 - OneOverZ2 );

                        NewVertex->X = LINEAR_INTERPOLATE(Ratio,(V2->X),(V1->X));
                        NewVertex->Y = LINEAR_INTERPOLATE(Ratio,(V2->Y),(V1->Y));
                        #ifdef ONE_OVER_Z_PIPELINE
                        NewVertex->Z = 1.0f/ geTClip_Statics.BackEdge;
                        #else
                        NewVertex->Z = geTClip_Statics.BackEdge;
                        #endif
                
                        break;
                case (LEFT_CLIPPING_PLANE):
                        assert((V2->X - V1->X)!=0.0f);
                        Ratio = (geTClip_Statics.LeftEdge - V2->X)/( V1->X - V2->X);

                        NewVertex->X = geTClip_Statics.LeftEdge;
                        NewVertex->Y = LINEAR_INTERPOLATE(Ratio,(V2->Y),(V1->Y));
                        #ifdef ONE_OVER_Z_PIPELINE
                        NewVertex->Z = LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #else
                        NewVertex->Z = 1.0f/LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #endif
        
                        break;
                case (RIGHT_CLIPPING_PLANE):
                        assert((V2->X - V1->X)!=0.0f);
                        Ratio = (geTClip_Statics.RightEdge - V2->X)/( V1->X - V2->X);

                        NewVertex->X = geTClip_Statics.RightEdge;
                        NewVertex->Y = LINEAR_INTERPOLATE(Ratio,(V2->Y),(V1->Y));
                        #ifdef ONE_OVER_Z_PIPELINE
                        NewVertex->Z = LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #else
                        NewVertex->Z = 1.0f/LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #endif

                        break;
                case (TOP_CLIPPING_PLANE):
                        assert((V2->Y - V1->Y)!=0.0f);
                        Ratio = (geTClip_Statics.TopEdge - V2->Y)/( V1->Y - V2->Y);

                        NewVertex->X = LINEAR_INTERPOLATE(Ratio,(V2->X),(V1->X));
                        NewVertex->Y = geTClip_Statics.TopEdge;
                        #ifdef ONE_OVER_Z_PIPELINE
                        NewVertex->Z = LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #else
                        NewVertex->Z = 1.0f/LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #endif
                        
                        break;
                case (BOTTOM_CLIPPING_PLANE):
                        assert((V2->Y - V1->Y)!=0.0f);
                        Ratio = (geTClip_Statics.BottomEdge - V2->Y)/( V1->Y - V2->Y);

                        NewVertex->X = LINEAR_INTERPOLATE(Ratio,(V2->X),(V1->X));
                        NewVertex->Y = geTClip_Statics.BottomEdge;
                        #ifdef ONE_OVER_Z_PIPELINE
                        NewVertex->Z = LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #else
                        NewVertex->Z = 1.0f/LINEAR_INTERPOLATE(Ratio,OneOverZ2,OneOverZ1);
                        #endif

                        break;
        }

        
        {
        geFloat OneOverZ1_Ratio;
        geFloat OneOverZ2_Ratio;
                #ifdef ONE_OVER_Z_PIPELINE
                OneOverZ1 *= 1.0f / NewVertex->Z;
                OneOverZ2 *= 1.0f / NewVertex->Z;
                #else
                OneOverZ1 *= NewVertex->Z;
                OneOverZ2 *= NewVertex->Z;
                #endif
                OneOverZ1_Ratio = OneOverZ1 * Ratio;
                OneOverZ2_Ratio = OneOverZ2 * Ratio;

                //  the following is optimized to get rid of a handfull of multiplies. Read:
                //      NewVertex->r = LINEAR_INTERPOLATE(Ratio,(V2->r * OneOverZ2),(V1->r * OneOverZ1));

                NewVertex->r =(V2->r * OneOverZ2) + (V1->r * OneOverZ1_Ratio) - (V2->r * OneOverZ2_Ratio);
                NewVertex->g =(V2->g * OneOverZ2) + (V1->g * OneOverZ1_Ratio) - (V2->g * OneOverZ2_Ratio);
                NewVertex->b =(V2->b * OneOverZ2) + (V1->b * OneOverZ1_Ratio) - (V2->b * OneOverZ2_Ratio);
                NewVertex->a =(V2->a * OneOverZ2) + (V1->a * OneOverZ1_Ratio) - (V2->a * OneOverZ2_Ratio);
                NewVertex->u =(V2->u * OneOverZ2) + (V1->u * OneOverZ1_Ratio) - (V2->u * OneOverZ2_Ratio);
                NewVertex->v =(V2->v * OneOverZ2) + (V1->v * OneOverZ1_Ratio) - (V2->v * OneOverZ2_Ratio);
        }

}


/*}{************ TClip_TrianglePlane ***********/

static void GENESISCC geTClip_TrianglePlane(const GE_LVertex * TriVertex,
                                                                                        geTClip_ClippingPlane ClippingPlane)
{
uint32 OutBits = 0;

        switch(ClippingPlane)
        {
        case BACK_CLIPPING_PLANE:

                OutBits |= (TriVertex[0].Z < geTClip_Statics.BackEdge) ? V0_OUT : 0;
                OutBits |= (TriVertex[1].Z < geTClip_Statics.BackEdge) ? V1_OUT : 0;
                OutBits |= (TriVertex[2].Z < geTClip_Statics.BackEdge) ? V2_OUT : 0;

        case LEFT_CLIPPING_PLANE:

                OutBits |= (TriVertex[0].X < geTClip_Statics.LeftEdge)  ? (V0_OUT<<3) : 0;
                OutBits |= (TriVertex[1].X < geTClip_Statics.LeftEdge)  ? (V1_OUT<<3) : 0;
                OutBits |= (TriVertex[2].X < geTClip_Statics.LeftEdge)  ? (V2_OUT<<3) : 0;

        case RIGHT_CLIPPING_PLANE:

                OutBits |= (TriVertex[0].X > geTClip_Statics.RightEdge) ? (V0_OUT<<6) : 0;
                OutBits |= (TriVertex[1].X > geTClip_Statics.RightEdge) ? (V1_OUT<<6) : 0;
                OutBits |= (TriVertex[2].X > geTClip_Statics.RightEdge) ? (V2_OUT<<6) : 0;

        case TOP_CLIPPING_PLANE:

                OutBits |= (TriVertex[0].Y < geTClip_Statics.TopEdge) ? (V0_OUT<<9) : 0;
                OutBits |= (TriVertex[1].Y < geTClip_Statics.TopEdge) ? (V1_OUT<<9) : 0;
                OutBits |= (TriVertex[2].Y < geTClip_Statics.TopEdge) ? (V2_OUT<<9) : 0;

        case BOTTOM_CLIPPING_PLANE:

                OutBits |= (TriVertex[0].Y > geTClip_Statics.BottomEdge) ?  (V0_OUT<<12) : 0;
                OutBits |= (TriVertex[1].Y > geTClip_Statics.BottomEdge) ?  (V1_OUT<<12) : 0;
                OutBits |= (TriVertex[2].Y > geTClip_Statics.BottomEdge) ?  (V2_OUT<<12) : 0;

        case NUM_CLIPPING_PLANES:
                break;
        }

        if ( OutBits )
        {
        GE_LVertex NewTriVertex[3];

        memset(NewTriVertex, '\0',sizeof(GE_LVertex)*(3));

                ClippingPlane = 0;
                for(;;)
                {
                        assert(ClippingPlane < NUM_CLIPPING_PLANES);

                        switch ( OutBits & 7 )
                        {
                                case (V_ALL_IN):  //NOT CLIPPED
                                        OutBits >>= 3;
                                        ClippingPlane ++;
                                        continue;

                                // these all return:

                                case (V0_OUT):
                                        NewTriVertex[0] = TriVertex[2];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+0,TriVertex+2,ClippingPlane);
                                        NewTriVertex[2] = TriVertex[1];

                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1);

                                        NewTriVertex[0] = NewTriVertex[1];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+0,TriVertex+1,ClippingPlane);

                                        //<> could gain a little speed like this, but who cares?
                                        //      if ( ! (OutBits>>3) )
                                        //              goto Rasterize
                                        //      else
                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1); 
                                        return;

                                case (V1_OUT):
                                        NewTriVertex[0] = TriVertex[0];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+0,TriVertex+1,ClippingPlane);
                                        NewTriVertex[2] = TriVertex[2];

                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1);

                                        NewTriVertex[0] = NewTriVertex[1];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+1,TriVertex+2,ClippingPlane);
                                        
                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1); 
                                        return;

                                case (V0_OUT + V1_OUT):
                                        NewTriVertex[0] = TriVertex[2];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+0,TriVertex+2,ClippingPlane);
                                        geTClip_Split(&(NewTriVertex[2]),TriVertex+1,TriVertex+2,ClippingPlane);
                                
                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1); 
                                        return;

                                case (V2_OUT):
                                        NewTriVertex[0] = TriVertex[1];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+1,TriVertex+2,ClippingPlane);
                                        NewTriVertex[2] = TriVertex[0];

                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1);

                                        NewTriVertex[0] = NewTriVertex[1];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+0,TriVertex+2,ClippingPlane);

                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1);
                                        return;

                                case (V2_OUT + V0_OUT):
                                        NewTriVertex[0] = TriVertex[1];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+1,TriVertex+2,ClippingPlane);
                                        geTClip_Split(&(NewTriVertex[2]),TriVertex+0,TriVertex+1,ClippingPlane);

                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1);
                                        return;

                                case (V2_OUT + V1_OUT):
                                        NewTriVertex[0] = TriVertex[0];
                                        geTClip_Split(&(NewTriVertex[1]),TriVertex+0,TriVertex+1,ClippingPlane);
                                        geTClip_Split(&(NewTriVertex[2]),TriVertex+0,TriVertex+2,ClippingPlane);

                                        geTClip_TrianglePlane(NewTriVertex,ClippingPlane+1);
                                        return;

                                case (V2_OUT + V1_OUT + V0_OUT):
                                        /* TOTALLY CLIPPED */
                                        return;
                        }
                }
        }

#if 0 // {

        // this eliminates an 'if' , but doesn't seem to help :^(
        // presumably because it's a predictable branch
        geTClip_Statics.RasterizeFunc(TriVertex);

#else //}{

        if ( geTClip_Statics.THandle )
        {
                geTClip_Statics.Driver->RenderMiscTexturePoly((DRV_TLVertex *)TriVertex,
                        3,geTClip_Statics.THandle,ActiveRenderFlags); // LA
        }
        else
        {
                geTClip_Statics.Driver->RenderGouraudPoly((DRV_TLVertex *)TriVertex,3,ActiveRenderFlags); // LA
        }

#endif //}

}

// LA - this is for completely onscreen-only triangles
void GENESISCC geTClip_UnclippedTriangle(const GE_LVertex TriVertex[3])
{
        if ( geTClip_Statics.THandle )
        {
                geTClip_Statics.Driver->RenderMiscTexturePoly((DRV_TLVertex *)TriVertex,
                        3,geTClip_Statics.THandle,ActiveRenderFlags);
        }
        else
        {
                geTClip_Statics.Driver->RenderGouraudPoly((DRV_TLVertex *)TriVertex,3,ActiveRenderFlags);
        }
        return;
}

/*}{*********** EOF ************/

---