render.c

来自「mesa-6.5-minigui源码」· C语言 代码 · 共 506 行 · 第 1/2 页

/*
** License Applicability. Except to the extent portions of this file are
** made subject to an alternative license as permitted in the SGI Free
** Software License B, Version 1.1 (the "License"), the contents of this
** file are subject only to the provisions of the License. You may not use
** this file except in compliance with the License. You may obtain a copy
** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
** 
** http://oss.sgi.com/projects/FreeB
** 
** Note that, as provided in the License, the Software is distributed on an
** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
** 
** Original Code. The Original Code is: OpenGL Sample Implementation,
** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
** Copyright in any portions created by third parties is as indicated
** elsewhere herein. All Rights Reserved.
** 
** Additional Notice Provisions: The application programming interfaces
** established by SGI in conjunction with the Original Code are The
** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
** Window System(R) (Version 1.3), released October 19, 1998. This software
** was created using the OpenGL(R) version 1.2.1 Sample Implementation
** published by SGI, but has not been independently verified as being
** compliant with the OpenGL(R) version 1.2.1 Specification.
**
*/
/*
** Author: Eric Veach, July 1994.
**
** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
** $Header: /cvs/mesa/Mesa/src/glu/sgi/libtess/render.c,v 1.1 2001/03/17 00:25:41 brianp Exp $
*/

#include "gluos.h"
#include <assert.h>
#include <stddef.h>
#include "mesh.h"
#include "tess.h"
#include "render.h"

#define TRUE 1
#define FALSE 0

/* This structure remembers the information we need about a primitive
 * to be able to render it later, once we have determined which
 * primitive is able to use the most triangles.
 */
struct FaceCount {
  long		size;		/* number of triangles used */
  GLUhalfEdge	*eStart;	/* edge where this primitive starts */
  void		(*render)(GLUtesselator *, GLUhalfEdge *, long);
                                /* routine to render this primitive */
};

static struct FaceCount MaximumFan( GLUhalfEdge *eOrig );
static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig );

static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size );
static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart,
			    long size );

static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig );
static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head );



/************************ Strips and Fans decomposition ******************/

/* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle
 * fans, strips, and separate triangles.  A substantial effort is made
 * to use as few rendering primitives as possible (ie. to make the fans
 * and strips as large as possible).
 *
 * The rendering output is provided as callbacks (see the api).
 */
void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh )
{
  GLUface *f;

  /* Make a list of separate triangles so we can render them all at once */
  tess->lonelyTriList = NULL;

  for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
    f->marked = FALSE;
  }
  for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {

    /* We examine all faces in an arbitrary order.  Whenever we find
     * an unprocessed face F, we output a group of faces including F
     * whose size is maximum.
     */
    if( f->inside && ! f->marked ) {
      RenderMaximumFaceGroup( tess, f );
      assert( f->marked );
    }
  }
  if( tess->lonelyTriList != NULL ) {
    RenderLonelyTriangles( tess, tess->lonelyTriList );
    tess->lonelyTriList = NULL;
  }
}


static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig )
{
  /* We want to find the largest triangle fan or strip of unmarked faces
   * which includes the given face fOrig.  There are 3 possible fans
   * passing through fOrig (one centered at each vertex), and 3 possible
   * strips (one for each CCW permutation of the vertices).  Our strategy
   * is to try all of these, and take the primitive which uses the most
   * triangles (a greedy approach).
   */
  GLUhalfEdge *e = fOrig->anEdge;
  struct FaceCount max, newFace;

  max.size = 1;
  max.eStart = e;
  max.render = &RenderTriangle;

  if( ! tess->flagBoundary ) {
    newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; }
    newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
    newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }

    newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; }
    newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; }
    newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; }
  }
  (*(max.render))( tess, max.eStart, max.size );
}


/* Macros which keep track of faces we have marked temporarily, and allow
 * us to backtrack when necessary.  With triangle fans, this is not
 * really necessary, since the only awkward case is a loop of triangles
 * around a single origin vertex.  However with strips the situation is
 * more complicated, and we need a general tracking method like the
 * one here.
 */
#define Marked(f)	(! (f)->inside || (f)->marked)

#define AddToTrail(f,t)	((f)->trail = (t), (t) = (f), (f)->marked = TRUE)

#define FreeTrail(t)	if( 1 ) { \
			  while( (t) != NULL ) { \
			    (t)->marked = FALSE; t = (t)->trail; \
			  } \
			} else /* absorb trailing semicolon */



static struct FaceCount MaximumFan( GLUhalfEdge *eOrig )
{
  /* eOrig->Lface is the face we want to render.  We want to find the size
   * of a maximal fan around eOrig->Org.  To do this we just walk around
   * the origin vertex as far as possible in both directions.
   */
  struct FaceCount newFace = { 0, NULL, &RenderFan };
  GLUface *trail = NULL;
  GLUhalfEdge *e;

  for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) {
    AddToTrail( e->Lface, trail );
    ++newFace.size;
  }
  for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) {
    AddToTrail( e->Rface, trail );
    ++newFace.size;
  }
  newFace.eStart = e;
  /*LINTED*/
  FreeTrail( trail );
  return newFace;
}


#define IsEven(n)	(((n) & 1) == 0)

static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig )
{
  /* Here we are looking for a maximal strip that contains the vertices
   * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the
   * reverse, such that all triangles are oriented CCW).
   *
   * Again we walk forward and backward as far as possible.  However for
   * strips there is a twist: to get CCW orientations, there must be
   * an *even* number of triangles in the strip on one side of eOrig.
   * We walk the strip starting on a side with an even number of triangles;
   * if both side have an odd number, we are forced to shorten one side.
   */
  struct FaceCount newFace = { 0, NULL, &RenderStrip };
  long headSize = 0, tailSize = 0;
  GLUface *trail = NULL;
  GLUhalfEdge *e, *eTail, *eHead;

  for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) {
    AddToTrail( e->Lface, trail );
    ++tailSize;
    e = e->Dprev;
    if( Marked( e->Lface )) break;
    AddToTrail( e->Lface, trail );
  }
  eTail = e;

  for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) {
    AddToTrail( e->Rface, trail );
    ++headSize;
    e = e->Oprev;
    if( Marked( e->Rface )) break;
    AddToTrail( e->Rface, trail );
  }
  eHead = e;

  newFace.size = tailSize + headSize;
  if( IsEven( tailSize )) {
    newFace.eStart = eTail->Sym;
  } else if( IsEven( headSize )) {
    newFace.eStart = eHead;
  } else {
    /* Both sides have odd length, we must shorten one of them.  In fact,
     * we must start from eHead to guarantee inclusion of eOrig->Lface.
     */
    --newFace.size;
    newFace.eStart = eHead->Onext;
  }
  /*LINTED*/
  FreeTrail( trail );
  return newFace;
}


static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size )
{
  /* Just add the triangle to a triangle list, so we can render all
   * the separate triangles at once.
   */
  assert( size == 1 );
  AddToTrail( e->Lface, tess->lonelyTriList );
}


static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f )
{
  /* Now we render all the separate triangles which could not be