hxfclip.c

Lido PXA270平台开发板的最新BSP,包括源代码

/* ************************************************************************* *\
**
**    INTEL Corporation Proprietary Information
**
**    This listing is supplied under the terms of a license
**    agreement with INTEL Corporation and may not be copied
**    nor disclosed except in accordance with the terms of
**    that agreement.
**
**    Copyright (c) 2003 Intel Corporation.
**    All Rights Reserved.
**
** ************************************************************************* **
**	FILE: HXFClip.c
**	DESCRIPTION: Reference C implementations of the fixed point clipper routines.
**
**	AUTHOR: Cian Montgomery
**	CREATED: July 10, 2003
**
 *  $Date: 5/28/04 10:21a $ $Revision: 25 $
 *  $Log: /Intel_Development/Drivers/Marathon/WinCE42/opengles/HXFClip.c $
 * 
 * 25    5/28/04 10:21a Clmontgo
 * Extened 1/w presicion in Clipper
 *
 * 24    5/27/04 8:43a Clmontgo
 *
 * 23    5/21/04 9:59a Clmontgo
 *
 * 22    5/19/04 5:06p Clmontgo
 * Change H Clip space to 0-1 coords
 *
 * 21    5/19/04 9:23a Clmontgo
 * Potential Fix for Clipping
 *
 * 20    5/16/04 12:53p Clmontgo
 *
 * 19    4/05/04 2:19p Clmontgo
 * Fixes for Light w/ w != 0 or 1 and Attenuation > 1.0
 *
 * 18    3/26/04 11:57a Clmontgo
 * Fixes for line clipper.
 *
 * 17    3/25/04 1:27p Clmontgo
 * Optimization of Clip flag generation and VP XForm. Fix for Clipping
 * issue observed in previous version.
\* ************************************************************************* */
#include "HXFLocal.h"
#include "HXFProfiler.h"
#include "XPL.h"

/* ************************************************************************* *\
	General comments about the clipper implementation:

  This clipper is based on Chris Gormans clipper for the Tumalo renderer.

  The basic theory is that we build an initial loop of segments each segment
  represents a vertex in the triangle and the connectivity to the next segment.
  Once the initial list is built we begin testing each segment to determine
  if the associated vertex is in or out. if the vertex is out we need to add
  a new vertex before it on the boundary and a new vertex out of it that is
  on the boundary. (Note: in actual practice more than one segment can be out
  and clipped to the boundary at the same time. When ever a segment is clipped
  it is removed from the list.

  Some important properties of this is that the loop is always closed and the
  loop always forms a convex polygon. (ie we start with a triangle which by
  definition is convex. It is always sliced by a plane. the resulting polygon
  is always convex. because the slicing always adds a straight edge.) When the
  loop crosses a boundary it will always cross the boundary twice. Once exiting
  and once entering again. The exit and entrance segments can be from the same
  segment. (ie. given triangle abc, if ab is in an c is out, bc will be the exit
  segment and ca will be the entering segment. These segments share c which is
  the common out point.)

  Assuming that every line in the triangle crosses 6 boundaries. This means that
  we will need to add at most 6 new vertices during the clip process for each
  line during the clip process. So in a triangle composed of 3 lines that means
  the most vertices we can insert during the clip process is 18.

  As we progress through the clipping process some of the


      X |					      X |
        |						*	|
    *   |							|
        ------------- Y				------------- Y

      *							*          *
           *

  Both have same clip flags.  Now clip to X boundary:

      X |					      X |
        |						 	|
        |						    *
        ------------- Y				------------- Y
        *
        *						    *        *
           *

         (trivial reject)					(still in)
\* ************************************************************************* */

/* ************************************************************************* *\
** ************************************************************************* **
** Local Data types
** ************************************************************************* **
\* ************************************************************************* */

/* ************************************************************************* *\
** ************************************************************************* **
** Local Functions
** ************************************************************************* **
\* ************************************************************************* */

#define START_BOUNDARY 0x0
#define START_MASK (0x01<<START_BOUNDARY)

/* ************************************************************************* *\
	FUNCTION: HXFClipLine
	DESCRIPTION:

  Internal clip function, that does the actual clipping on the triangle.
  Any triangle that is processed is either all out after progressing partially
  thru the clip routine or clipped into smaller triangles.

\* ************************************************************************* */
HXFState* HXFClipLine(HXFState* pState, HUINT8* pV1, HUINT8* pV2)
{
	HUINT32 boundary = 0;

	HUINT32 mask = START_MASK ;

	HXFClipSegment* pSeg1 = NULL;
	HXFClipSegment* pSeg2 = NULL;
	HXFClipSegment* pSegTmp = NULL;
	HXFClipSegment* pNextFreeSegment = (HXFClipSegment*)pState->pClipSegments;

	HXF_PROFILER_TRANSITION(HXFPROFILE_DRAW_CLIP);

	pSeg1 = pNextFreeSegment++;
	pSeg1->Flags = *pV1;
	pSeg1->pVtx = pState->pOutVertices +
			( (pV1 - pState->pOutClipFlags) * pState->OutVertexSize);

	pSeg2 = pNextFreeSegment++;
	pSeg2->Flags = *pV2;
	pSeg2->pVtx = pState->pOutVertices +
			( (pV2 - pState->pOutClipFlags) * pState->OutVertexSize);

	for(boundary = START_BOUNDARY; boundary < 6; ++boundary)
	{
		// Arrange such that pSeg1 is the closest to the eye
		// can tell by plane violations
		if((pSeg1->Flags & mask) && (pSeg2->Flags & mask))
		{
			// All Out
			return pState;
		}

		// Check if Seg 1 violates this plane
		if(pSeg1->Flags & mask)
		{
			pSegTmp = pNextFreeSegment++;
			pSegTmp->pVtx = pState->pClippedVertices;
			HXF_UPDATE_ITOR(pState->pClippedVertices, pState->OutVertexSize);
			HXFClipInterpolate(pState, pSeg2->pVtx, pSeg1->pVtx, pSegTmp, boundary);
			pSeg1 = pSegTmp;
			pState->NumClippedVertices+=1;
		}

		// Check if Seg 2 violates this plane
		if(pSeg2->Flags & mask)
		{
			pSegTmp = pNextFreeSegment++;
			pSegTmp->pVtx = pState->pClippedVertices;
			HXF_UPDATE_ITOR(pState->pClippedVertices, pState->OutVertexSize);
			HXFClipInterpolate(pState, pSeg1->pVtx, pSeg2->pVtx, pSegTmp, boundary);
			pSeg2 = pSegTmp;
			pState->NumClippedVertices+=1;
		}
		mask <<= 1; //
	}

	// Add the clipped segment to the clip list
	{
		HUINT32 faceidx = 0;
		void** pFace = NULL;
		faceidx = 2 * pState->NumClippedPrimitives;
		pState->NumClippedPrimitives += 1;
		pFace = &(pState->pClippedIndices[faceidx]);
		pFace[0] = pSeg1->pVtx;
		pFace[1] = pSeg2->pVtx;
	}

	HXF_PROFILER_TRANSITION(HXFPROFILE_DRAW_ASSEMBLE);
	return pState;
}

/* ************************************************************************* *\
	FUNCTION: HXFClipTriangle
	DESCRIPTION:

  Internal clip function, that does the actual clipping on the triangle.
  Any triangle that is processed is either all out after progressing partially
  thru the clip routine or clipped into smaller triangles.

\* ************************************************************************* */
HXFState* HXFClipTriangle(HXFState* pState, HUINT8* pV1, HUINT8* pV2, HUINT8* pV3)
{
	HUINT32 boundary = 0;
	// Set the free segment list to the segment buffer
	HXFClipSegment* pNextFreeSegment = (HXFClipSegment*)pState->pClipSegments;

	HXFClipSegment* pStartSeg = NULL; // List of all allocated segments
	HXFClipSegment* pSeg1 = NULL;
	HXFClipSegment* pSeg2 = NULL;

	HXFClipSegment* pInSeg = NULL;
	HXFClipSegment* pOutSeg = NULL;

	HXFClipSegment* pTmpSeg = NULL;

	HUINT32 mask = START_MASK;
	HBOOL allOut = 0;
	HUINT32 faceidx  = 0;

	HUINT32 OriginalAccumulator = 0;

	HXF_PROFILER_START(HXFPROFILE_DRAW_CLIP);

	// Create Initial Segment list
	pSeg2 = pNextFreeSegment++;
	pSeg2->Flags = *pV1;
	pSeg2->pVtx = pState->pOutVertices +
			( (pV1 - pState->pOutClipFlags) * pState->OutVertexSize);
	pSeg2->pNext = NULL;

	pSeg1 = pNextFreeSegment++;
	pSeg1->Flags = *pV2;
	pSeg1->pVtx = pState->pOutVertices +
			( (pV2 - pState->pOutClipFlags) * pState->OutVertexSize);
	pSeg1->pNext = pSeg2;

	pStartSeg = pNextFreeSegment++;
	pStartSeg->Flags = *pV3;
	pStartSeg->pVtx = pState->pOutVertices +
			( (pV3 - pState->pOutClipFlags) * pState->OutVertexSize);
	pStartSeg->pNext = pSeg1;
	pSeg2->pNext = pStartSeg;

	/* Start testing the nodes against all of the boundaries
		3 basic cases that can happen
		1) all out wrt(with respect to) this boundry.
			- case shown in comment at the begining of the file
		2) all in wrt this boundary
			- do nothing
		3) this boundary is spaned.
			- calculate new segments
    */
	for(boundary = START_BOUNDARY; boundary < 6; ++boundary)
	{
		// Look for segment that needs to be clipped
		// Start at the beginning of the list and find the first "in"
		// We are guaranteed at least one "in" because of the trivial reject
		// test that occured before this function was called.
		pInSeg = pStartSeg;
		allOut = HTRUE;
		do
		{
			if (0 == (pInSeg->Flags & mask))
			{
				pOutSeg = pInSeg->pNext;
				pStartSeg = pInSeg;
				// This node is "in" - advance until we find a node that is out
				while( (pOutSeg != pStartSeg)
						&& 0 == (pOutSeg->Flags & mask) )
				{
					pInSeg = pOutSeg;
					pOutSeg = pOutSeg->pNext;
				}

				allOut = HFALSE;
				if(pOutSeg == pStartSeg)
				{	// Could not find a segment outside this boundary
					// also an nice conflict in == out.
					pOutSeg = NULL;
				}
				break;
			}
			pInSeg = pInSeg->pNext;
		} while (pInSeg != pStartSeg);


		if (allOut)
		{	//  case 1: All out -- See trivial reject comments in file header
			return pState;
		}

		else if(NULL != pOutSeg)
		// Case 3: This Boundary spanned
		{
			// pInSeg = Last in Segment
			// pOutSeg = First Out Seg

			// Walk until next segment is in - we are sure to find one
			// since we know that a boundary is spaned due to the first loop
			while(pOutSeg->pNext->Flags & mask)
			{
				pOutSeg = pOutSeg->pNext;
			}

			// We know that pInSeg->pNext and  pOutSeg are outside this
			// boundary and pInSeg and pOutSeg->pNext are in side this
			// boundary.

			// Now add new node between pInSeg and pInSeg->pNext
			pSeg1 = pNextFreeSegment++;
			// pSeg1->Flags -- Set in the interpolate function
			pSeg1->pVtx = pState->pClippedVertices;
			HXF_UPDATE_ITOR(pState->pClippedVertices, pState->OutVertexSize);
			pSeg1->pNext = pNextFreeSegment; // will be allocated just below
			HXFClipInterpolate(pState, pInSeg->pVtx, pInSeg->pNext->pVtx, pSeg1, boundary);
			pInSeg->pNext = pSeg1;

			// Now add new node between pOutSeg(out) and pOutSeg->pNext(In)
			pSeg2 = pNextFreeSegment++;
			// pSeg2->Flags -- Set in the interpolate function
			pSeg2->pVtx = pState->pClippedVertices;
			HXF_UPDATE_ITOR(pState->pClippedVertices, pState->OutVertexSize);
			pSeg2->pNext = pOutSeg->pNext;

			HXFClipInterpolate(pState, pOutSeg->pNext->pVtx, pOutSeg->pVtx, pSeg2, boundary);
			HXFASSERT((HXF_CLIP_VTX_SPACE - pState->NumClippedVertices) >=2);
			pState->NumClippedVertices+=2; // Always add two vertices

			// we know the pStartSegment was valid because it was set to an in
			// node in the first loop if any in nodes were found.
		}
		// else // Case 2: All in wrt this boundary -- nothing to do.

		mask <<= 1; //
	}

	//2 Create Faces - All of the vertices are "in"
	// pick pStartSeg as the base of the triangle fan
	faceidx = 3 * pState->NumClippedPrimitives;
	pSeg2 = pStartSeg->pNext;
	pSeg1 = pSeg2->pNext;

	// If we are culling then check to see if

	if( pState->StorageLR[0] & HXF_PA_CULL_ENABLE)
	{
		do
		{
			void** pFace = &(pState->pClippedIndices[faceidx]);

			// Form a face from pStartSeg, pSeg2, pSeg1