src/glu/sgi/libtess/sweep.h

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 **
  34 */
  35 /*
  36 ** Author: Eric Veach, July 1994.
  37 **
  38 */
  39
  40 #ifndef __sweep_h_
  41 #define __sweep_h_
  42
  43 #include "mesh.h"
  44
  45 /* __gl_computeInterior( tess ) computes the planar arrangement specified
  46  * by the given contours, and further subdivides this arrangement
  47  * into regions.  Each region is marked "inside" if it belongs
  48  * to the polygon, according to the rule given by tess->windingRule.
  49  * Each interior region is guaranteed be monotone.
  50  */
  51 int __gl_computeInterior( GLUtesselator *tess );
  52
  53
  54 /* The following is here *only* for access by debugging routines */
  55
  56 #include "dict.h"
  57
  58 /* For each pair of adjacent edges crossing the sweep line, there is
  59  * an ActiveRegion to represent the region between them.  The active
  60  * regions are kept in sorted order in a dynamic dictionary.  As the
  61  * sweep line crosses each vertex, we update the affected regions.
  62  */
  63
  64 struct ActiveRegion {
  65   GLUhalfEdge   *eUp;           /* upper edge, directed right to left */
  66   DictNode      *nodeUp;        /* dictionary node corresponding to eUp */
  67   int           windingNumber;  /* used to determine which regions are
  68                                  * inside the polygon */
  69   GLboolean     inside;         /* is this region inside the polygon? */
  70   GLboolean     sentinel;       /* marks fake edges at t = +/-infinity */
  71   GLboolean     dirty;          /* marks regions where the upper or lower
  72                                  * edge has changed, but we haven't checked
  73                                  * whether they intersect yet */
  74   GLboolean     fixUpperEdge;   /* marks temporary edges introduced when
  75                                  * we process a "right vertex" (one without
  76                                  * any edges leaving to the right) */
  77 };
  78
  79 #define RegionBelow(r)  ((ActiveRegion *) dictKey(dictPred((r)->nodeUp)))
  80 #define RegionAbove(r)  ((ActiveRegion *) dictKey(dictSucc((r)->nodeUp)))
  81
  82 #endif