src/glu/sgi/libnurbs/nurbtess/monoTriangulation.h

   1 /*
   2  * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
   3  * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice including the dates of first publication and
  13  * either this permission notice or a reference to
  14  * http://oss.sgi.com/projects/FreeB/
  15  * shall be included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  20  * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  21  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  22  * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  23  * SOFTWARE.
  24  *
  25  * Except as contained in this notice, the name of Silicon Graphics, Inc.
  26  * shall not be used in advertising or otherwise to promote the sale, use or
  27  * other dealings in this Software without prior written authorization from
  28  * Silicon Graphics, Inc.
  29  */
  30 /*
  31 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.h,v 1.1 2001/03/17 00:25:41 brianp Exp $
  32 */
  33
  34 #ifndef _MONO_TRIANGULATION_H
  35 #define _MONO_TRIANGULATION_H
  36
  37 #include "definitions.h"
  38 #include "primitiveStream.h"
  39 #include "directedLine.h"
  40 #include "arc.h"
  41
  42 class Backend;
  43
  44 class reflexChain{
  45   Real2 *queue;
  46   /*the order of the polygon vertices: either q[0],q[1].., or
  47    * q[n-1], q[n-2], ..., q[0]
  48    *this order determines the interior of the polygon, so it
  49    *also used to determines whether a chain is reflex or convex
  50    */
  51   Int isIncreasing;
  52   Int index_queue;
  53   Int size_queue; /*allocated size*/
  54
  55 public:
  56   reflexChain(Int size, Int isIncreasing);
  57   ~reflexChain();
  58
  59   void insert(Real u, Real v);
  60   void insert(Real v[2]);
  61
  62   void processNewVertex(Real v[2], primStream* pStream);
  63   void outputFan(Real v[2], primStream* pStream);
  64
  65   void processNewVertex(Real v[2], Backend* backend);
  66   void outputFan(Real v[2], Backend* backend);
  67
  68   void print();
  69 };
  70
  71 /*dynamic array of pointers to reals.
  72  *Intended to store an array of (u,v).
  73  *Notice that it doesn't allocate or dealocate the space
  74  *for the (u,v) themselfs. So it assums that someone else
  75  *is taking care of them, while this class only plays with
  76  *the pointers.
  77  */
  78 class vertexArray{
  79   Real** array;
  80   Int index;
  81   Int size;
  82 public:
  83   vertexArray(Int s);
  84   vertexArray(Real vertices[][2], Int nVertices);
  85   ~vertexArray();
  86   void appendVertex(Real* ptr); /*the content (pointed by ptr is NOT copied*/
  87   Real* getVertex(Int i) {return array[i];}
  88   Real** getArray() {return array;}
  89   Int getNumElements() {return index;}
  90   Int findIndexAbove(Real v);
  91   Int findIndexAboveGen(Real v, Int startIndex, Int EndIndex);
  92   Int findIndexBelowGen(Real v, Int startIndex, Int EndIndex);
  93   Int findIndexStrictBelowGen(Real v, Int startIndex, Int EndIndex);
  94   Int findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex);
  95   Int skipEqualityFromStart(Real v, Int start, Int end);
  96   //return i such that fron [i+1, end] is strictly U-monotone (left to right
  97   Int findDecreaseChainFromEnd(Int begin, Int end);
  98   void print();
  99 };
 100
 101 void monoTriangulation(directedLine* monoPolygon, primStream* pStream);
 102
 103 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 104                           vertexArray* inc_chain, Int inc_current,
 105                           vertexArray* dec_chain, Int dec_current,
 106                           primStream* pStream);
 107
 108 void monoTriangulationRec(directedLine* inc_chain, Int inc_index,
 109                           directedLine* dec_chain, Int dec_index,
 110                           directedLine* topVertex, Int top_index,
 111                           directedLine* botVertex,
 112                           primStream* pStream);
 113
 114 /*the chain could be increasing or decreasing, although we use the
 115  * name inc_chain.
 116  *the argument  is_increase_chain indicates whether this chain
 117  *is increasing (left chain in V-monotone case) or decreaing (right chain
 118  *in V-monotone case).
 119  */
 120 void monoTriangulation2(Real* topVertex, Real* botVertex,
 121                         vertexArray* inc_chain, Int inc_smallIndex,
 122                         Int inc_largeIndex,
 123                         Int is_increase_chain,
 124                         primStream* pStream);
 125 void monoTriangulationRecGen(Real* topVertex, Real* botVertex,
 126                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 127                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 128                           primStream* pStream);
 129
 130 void monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex,
 131                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 132                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 133                           primStream* pStream);
 134
 135 void triangulateXYMonoTB(Int n_left, Real** leftVerts,
 136                        Int n_right, Real** rightVerts,
 137                        primStream* pStream);
 138
 139 void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex,
 140                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 141                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 142                           primStream* pStream);
 143
 144 void monoTriangulationRecOpt(Real* topVertex, Real* botVertex,
 145                              vertexArray* left_chain, Int left_current,
 146                              vertexArray* right_chain, Int right_current,
 147                              primStream* pStream);
 148
 149 void monoTriangulationRecFunGen(Real* topVertex, Real* botVertex,
 150                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 151                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 152                           Int  (*compFun)(Real*, Real*),
 153                           primStream* pStream);
 154
 155 void monoTriangulationRecFun(Real* topVertex, Real* botVertex,
 156                           vertexArray* inc_chain, Int inc_current,
 157                           vertexArray* dec_chain, Int dec_current,
 158                            Int (*compFun)(Real*, Real*),
 159                           primStream* pStream);
 160 void monoTriangulationFun(directedLine* monoPolygon,
 161                           Int (*compFun)(Real*, Real*), primStream* pStream);
 162
 163
 164
 165
 166 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 167                           vertexArray* inc_chain, Int inc_current,
 168                           vertexArray* dec_chain, Int dec_current,
 169                           Backend* backend);
 170
 171 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend);
 172
 173 void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
 174                           vertexArray* inc_chain, Int inc_current,
 175                           vertexArray* dec_chain, Int dec_current,
 176                           Int  (*compFun)(Real*, Real*),
 177                           Backend* backend);
 178
 179 void monoTriangulationOpt(directedLine* poly, primStream* pStream);
 180
 181 #endif
 182
 183
 184
 185