ReactOS  0.4.13-dev-73-gcfe54aa
monoTriangulation.h
Go to the documentation of this file.
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 
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  */
52  Int size_queue; /*allocated size*/
53 
54 public:
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  */
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;}
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);
95  //return i such that fron [i+1, end] is strictly U-monotone (left to right
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 
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
void monoTriangulationFun(directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
Real ** getArray()
void processNewVertex(Real v[2], primStream *pStream)
void appendVertex(Real *ptr)
Int findIndexAbove(Real v)
Int findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex)
void monoTriangulationFunBackend(Arc_ptr loop, Int(*compFun)(Real *, Real *), Backend *backend)
GLuint GLuint end
Definition: gl.h:1545
reflexChain(Int size, Int isIncreasing)
void monoTriangulationRecFun(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), primStream *pStream)
Int findIndexStrictBelowGen(Real v, Int startIndex, Int EndIndex)
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
void monoTriangulationRecGenOpt(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
void insert(Real u, Real v)
static PVOID ptr
Definition: dispmode.c:27
Int findIndexBelowGen(Real v, Int startIndex, Int EndIndex)
void outputFan(Real v[2], primStream *pStream)
static clock_t begin
Definition: xmllint.c:466
GLsizeiptr size
Definition: glext.h:5919
void monoTriangulationRecFunGen(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, Int(*compFun)(Real *, Real *), primStream *pStream)
GLdouble s
Definition: gl.h:2039
void monoTriangulationOpt(directedLine *poly, primStream *pStream)
void monoTriangulation2(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)
class Arc * Arc_ptr
Definition: arc.h:50
void monoTriangulationRecOpt(Real *topVertex, Real *botVertex, vertexArray *left_chain, Int left_current, vertexArray *right_chain, Int right_current, primStream *pStream)
void monoTriangulationRecGen(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
const GLdouble * v
Definition: gl.h:2040
void triangulateXYMonoTB(Int n_left, Real **leftVerts, Int n_right, Real **rightVerts, primStream *pStream)
void monoTriangulationRecGenTBOpt(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
GLuint start
Definition: gl.h:1545
float Real
Definition: definitions.h:36
void monoTriangulationRecFunBackend(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), Backend *backend)
Real Real2[2]
Definition: definitions.h:38
Int findDecreaseChainFromEnd(Int begin, Int end)
Int skipEqualityFromStart(Real v, Int start, Int end)
Real * getVertex(Int i)
void monoTriangulation(directedLine *monoPolygon, primStream *pStream)
Int findIndexAboveGen(Real v, Int startIndex, Int EndIndex)
int Int
Definition: definitions.h:37