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 */
  32
  33 #ifndef _MONO_TRIANGULATION_H
  34 #define _MONO_TRIANGULATION_H
  35
  36 #include "definitions.h"
  37 #include "primitiveStream.h"
  38 #include "directedLine.h"
  39 #include "arc.h"
  40
  41 class Backend;
  42
  43 class reflexChain{
  44   Real2 *queue;
  45   /*the order of the polygon vertices: either q[0],q[1].., or
  46    * q[n-1], q[n-2], ..., q[0]
  47    *this order determines the interior of the polygon, so it
  48    *also used to determines whether a chain is reflex or convex
  49    */
  50   Int isIncreasing;
  51   Int index_queue;
  52   Int size_queue; /*allocated size*/
  53
  54 public:
  55   reflexChain(Int size, Int isIncreasing);
  56   ~reflexChain();
  57
  58   void insert(Real u, Real v);
  59   void insert(Real v[2]);
  60
  61   void processNewVertex(Real v[2], primStream* pStream);
  62   void outputFan(Real v[2], primStream* pStream);
  63
  64   void processNewVertex(Real v[2], Backend* backend);
  65   void outputFan(Real v[2], Backend* backend);
  66
  67   void print();
  68 };
  69
  70 /*dynamic array of pointers to reals.
  71  *Intended to store an array of (u,v).
  72  *Notice that it doesn't allocate or dealocate the space
  73  *for the (u,v) themselfs. So it assums that someone else
  74  *is taking care of them, while this class only plays with
  75  *the pointers.
  76  */
  77 class vertexArray{
  78   Real** array;
  79   Int index;
  80   Int size;
  81 public:
  82   vertexArray(Int s);
  83   vertexArray(Real vertices[][2], Int nVertices);
  84   ~vertexArray();
  85   void appendVertex(Real* ptr); /*the content (pointed by ptr is NOT copied*/
  86   Real* getVertex(Int i) {return array[i];}
  87   Real** getArray() {return array;}
  88   Int getNumElements() {return index;}
  89   Int findIndexAbove(Real v);
  90   Int findIndexAboveGen(Real v, Int startIndex, Int EndIndex);
  91   Int findIndexBelowGen(Real v, Int startIndex, Int EndIndex);
  92   Int findIndexStrictBelowGen(Real v, Int startIndex, Int EndIndex);
  93   Int findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex);
  94   Int skipEqualityFromStart(Real v, Int start, Int end);
  95   //return i such that fron [i+1, end] is strictly U-monotone (left to right
  96   Int findDecreaseChainFromEnd(Int begin, Int end);
  97   void print();
  98 };
  99
 100 void monoTriangulation(directedLine* monoPolygon, primStream* pStream);
 101
 102 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 103                           vertexArray* inc_chain, Int inc_current,
 104                           vertexArray* dec_chain, Int dec_current,
 105                           primStream* pStream);
 106
 107 void monoTriangulationRec(directedLine* inc_chain, Int inc_index,
 108                           directedLine* dec_chain, Int dec_index,
 109                           directedLine* topVertex, Int top_index,
 110                           directedLine* botVertex,
 111                           primStream* pStream);
 112
 113 /*the chain could be increasing or decreasing, although we use the
 114  * name inc_chain.
 115  *the argument  is_increase_chain indicates whether this chain
 116  *is increasing (left chain in V-monotone case) or decreaing (right chain
 117  *in V-monotone case).
 118  */
 119 void monoTriangulation2(Real* topVertex, Real* botVertex,
 120                         vertexArray* inc_chain, Int inc_smallIndex,
 121                         Int inc_largeIndex,
 122                         Int is_increase_chain,
 123                         primStream* pStream);
 124 void monoTriangulationRecGen(Real* topVertex, Real* botVertex,
 125                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 126                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 127                           primStream* pStream);
 128
 129 void monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex,
 130                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 131                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 132                           primStream* pStream);
 133
 134 void triangulateXYMonoTB(Int n_left, Real** leftVerts,
 135                        Int n_right, Real** rightVerts,
 136                        primStream* pStream);
 137
 138 void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex,
 139                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 140                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 141                           primStream* pStream);
 142
 143 void monoTriangulationRecOpt(Real* topVertex, Real* botVertex,
 144                              vertexArray* left_chain, Int left_current,
 145                              vertexArray* right_chain, Int right_current,
 146                              primStream* pStream);
 147
 148 void monoTriangulationRecFunGen(Real* topVertex, Real* botVertex,
 149                           vertexArray* inc_chain, Int inc_current, Int inc_end,
 150                           vertexArray* dec_chain, Int dec_current, Int dec_end,
 151                           Int  (*compFun)(Real*, Real*),
 152                           primStream* pStream);
 153
 154 void monoTriangulationRecFun(Real* topVertex, Real* botVertex,
 155                           vertexArray* inc_chain, Int inc_current,
 156                           vertexArray* dec_chain, Int dec_current,
 157                            Int (*compFun)(Real*, Real*),
 158                           primStream* pStream);
 159 void monoTriangulationFun(directedLine* monoPolygon,
 160                           Int (*compFun)(Real*, Real*), primStream* pStream);
 161
 162
 163
 164
 165 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 166                           vertexArray* inc_chain, Int inc_current,
 167                           vertexArray* dec_chain, Int dec_current,
 168                           Backend* backend);
 169
 170 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend);
 171
 172 void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
 173                           vertexArray* inc_chain, Int inc_current,
 174                           vertexArray* dec_chain, Int dec_current,
 175                           Int  (*compFun)(Real*, Real*),
 176                           Backend* backend);
 177
 178 void monoTriangulationOpt(directedLine* poly, primStream* pStream);
 179
 180 #endif
 181
 182
 183
 184