11cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 21cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** License Applicability. Except to the extent portions of this file are 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** made subject to an alternative license as permitted in the SGI Free 41cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Software License B, Version 1.1 (the "License"), the contents of this 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** file are subject only to the provisions of the License. You may not use 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** this file except in compliance with the License. You may obtain a copy 71cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 81cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: 91cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** http://oss.sgi.com/projects/FreeB 111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Note that, as provided in the License, the Software is distributed on an 131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS 141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND 151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A 161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. 171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Original Code. The Original Code is: OpenGL Sample Implementation, 191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, 201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. 211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Copyright in any portions created by third parties is as indicated 221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** elsewhere herein. All Rights Reserved. 231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Additional Notice Provisions: The application programming interfaces 251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** established by SGI in conjunction with the Original Code are The 261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released 271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version 281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X 291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Window System(R) (Version 1.3), released October 19, 1998. This software 301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** was created using the OpenGL(R) version 1.2.1 Sample Implementation 311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** published by SGI, but has not been independently verified as being 321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** compliant with the OpenGL(R) version 1.2.1 Specification. 331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*/ 351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** Author: Eric Veach, July 1994. 371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** 381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** $Date$ $Revision$ 391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** $Header: //depot/main/gfx/lib/glu/libtess/sweep.h#5 $ 401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*/ 411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#ifndef __sweep_h_ 431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define __sweep_h_ 441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "mesh.h" 461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* __gl_computeInterior( tess ) computes the planar arrangement specified 481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * by the given contours, and further subdivides this arrangement 491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * into regions. Each region is marked "inside" if it belongs 501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * to the polygon, according to the rule given by tess->windingRule. 511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Each interior region is guaranteed be monotone. 521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerint __gl_computeInterior( GLUtesselator *tess ); 541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* The following is here *only* for access by debugging routines */ 571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#include "dict.h" 591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* For each pair of adjacent edges crossing the sweep line, there is 611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * an ActiveRegion to represent the region between them. The active 621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * regions are kept in sorted order in a dynamic dictionary. As the 631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * sweep line crosses each vertex, we update the affected regions. 641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger */ 651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 661cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstruct ActiveRegion { 671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLUhalfEdge *eUp; /* upper edge, directed right to left */ 681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger DictNode *nodeUp; /* dictionary node corresponding to eUp */ 691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int windingNumber; /* used to determine which regions are 701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * inside the polygon */ 711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLboolean inside; /* is this region inside the polygon? */ 721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLboolean sentinel; /* marks fake edges at t = +/-infinity */ 731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLboolean dirty; /* marks regions where the upper or lower 741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * edge has changed, but we haven't checked 751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * whether they intersect yet */ 761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GLboolean fixUpperEdge; /* marks temporary edges introduced when 771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * we process a "right vertex" (one without 781cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * any edges leaving to the right) */ 791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger}; 801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define RegionBelow(r) ((ActiveRegion *) dictKey(dictPred((r)->nodeUp))) 821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#define RegionAbove(r) ((ActiveRegion *) dictKey(dictSucc((r)->nodeUp))) 831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger#endif 85