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*/ 37 38#include "monoTriangulation.h" 39#include "polyUtil.h" 40#include "backend.h" 41#include "arc.h" 42 43void reflexChain::outputFan(Real v[2], Backend* backend) 44{ 45 Int i; 46 /* 47 TrimVertex trimVert; 48 */ 49 backend->bgntfan(); 50 51 /* 52 trimVert.param[0]=v[0]; 53 trimVert.param[1]=v[1]; 54 backend->tmeshvert(&trimVert); 55 */ 56 backend->tmeshvert(v[0], v[1]); 57 58 if(isIncreasing) { 59 for(i=0; i<index_queue; i++) 60 { 61 /* 62 trimVert.param[0]=queue[i][0]; 63 trimVert.param[1]=queue[i][1]; 64 backend->tmeshvert(&trimVert); 65 */ 66 backend->tmeshvert(queue[i][0], queue[i][1]); 67 } 68 } 69 else { 70 for(i=index_queue-1; i>=0; i--) 71 { 72 /* 73 trimVert.param[0]=queue[i][0]; 74 trimVert.param[1]=queue[i][1]; 75 backend->tmeshvert(&trimVert); 76 */ 77 backend->tmeshvert(queue[i][0], queue[i][1]); 78 } 79 } 80 backend->endtfan(); 81} 82 83void reflexChain::processNewVertex(Real v[2], Backend* backend) 84{ 85 Int i,j,k; 86 Int isReflex; 87 /*TrimVertex trimVert;*/ 88 /*if there are at most one vertex in the queue, then simply insert 89 */ 90 if(index_queue <=1){ 91 insert(v); 92 return; 93 } 94 95 /*there are at least two vertices in the queue*/ 96 j=index_queue-1; 97 98 for(i=j; i>=1; i--) { 99 if(isIncreasing) { 100 isReflex = (area(queue[i-1], queue[i], v) <= 0.0); 101 } 102 else /*decreasing*/{ 103 isReflex = (area(v, queue[i], queue[i-1]) <= 0.0); 104 } 105 if(isReflex) { 106 break; 107 } 108 } 109 110 /* 111 *if i<j then vertices: i+1--j are convex 112 * output triangle fan: 113 * v, and queue[i], i+1, ..., j 114 */ 115 if(i<j) 116 { 117 backend->bgntfan(); 118 /* 119 trimVert.param[0]=v[0]; 120 trimVert.param[1]=v[1]; 121 backend->tmeshvert(& trimVert); 122 */ 123 backend->tmeshvert(v[0], v[1]); 124 125 if(isIncreasing) { 126 for(k=i; k<=j; k++) 127 { 128 /* 129 trimVert.param[0]=queue[k][0]; 130 trimVert.param[1]=queue[k][1]; 131 backend->tmeshvert(& trimVert); 132 */ 133 backend->tmeshvert(queue[k][0], queue[k][1]); 134 } 135 } 136 else { 137 for(k=j; k>=i; k--) 138 { 139 /* 140 trimVert.param[0]=queue[k][0]; 141 trimVert.param[1]=queue[k][1]; 142 backend->tmeshvert(& trimVert); 143 */ 144 backend->tmeshvert(queue[k][0], queue[k][1]); 145 } 146 } 147 148 backend->endtfan(); 149 } 150 151 /*delete vertices i+1--j from the queue*/ 152 index_queue = i+1; 153 /*finally insert v at the end of the queue*/ 154 insert(v); 155 156} 157 158 159void monoTriangulationRec(Real* topVertex, Real* botVertex, 160 vertexArray* inc_chain, Int inc_current, 161 vertexArray* dec_chain, Int dec_current, 162 Backend* backend) 163{ 164 assert( inc_chain != NULL && dec_chain != NULL); 165 assert( ! (inc_current>=inc_chain->getNumElements() && 166 dec_current>=dec_chain->getNumElements())); 167 Int inc_nVertices; 168 Int dec_nVertices; 169 Real** inc_array ; 170 Real** dec_array ; 171 Int i; 172 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); 173 174 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/ 175 { 176 177 dec_array = dec_chain->getArray(); 178 dec_nVertices = dec_chain->getNumElements(); 179 reflexChain rChain(20,0); 180 /*put the top vertex into the reflex chain*/ 181 rChain.processNewVertex(topVertex, backend); 182 /*process all the vertices on the dec_chain*/ 183 for(i=dec_current; i<dec_nVertices; i++){ 184 rChain.processNewVertex(dec_array[i], backend); 185 } 186 /*process the bottom vertex*/ 187 rChain.processNewVertex(botVertex, backend); 188 189 } 190 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/ 191 { 192 inc_array = inc_chain->getArray(); 193 inc_nVertices= inc_chain->getNumElements(); 194 reflexChain rChain(20,1); 195 /*put the top vertex into the reflex chain*/ 196 rChain.processNewVertex(topVertex, backend); 197 /*process all the vertices on the inc_chain*/ 198 for(i=inc_current; i<inc_nVertices; i++){ 199 rChain.processNewVertex(inc_array[i], backend); 200 } 201 /*process the bottom vertex*/ 202 rChain.processNewVertex(botVertex, backend); 203 } 204 else /*neither chain is empty*/ 205 { 206 inc_array = inc_chain -> getArray(); 207 dec_array = dec_chain -> getArray(); 208 inc_nVertices= inc_chain->getNumElements(); 209 dec_nVertices= dec_chain->getNumElements(); 210 /*if top of inc_chain is 'lower' than top of dec_chain, process all the 211 *vertices on the dec_chain which are higher than top of inc_chain 212 */ 213 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0) 214 { 215 216 reflexChain rChain(20, 0); 217 rChain.processNewVertex(topVertex, backend); 218 for(i=dec_current; i<dec_nVertices; i++) 219 { 220 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0) 221 rChain.processNewVertex(dec_array[i], backend); 222 else 223 break; 224 } 225 rChain.outputFan(inc_array[inc_current], backend); 226 monoTriangulationRec(dec_array[i-1], botVertex, 227 inc_chain, inc_current, 228 dec_chain, i, 229 backend); 230 } 231 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/ 232 { 233 234 reflexChain rChain(20, 1); 235 rChain.processNewVertex(topVertex, backend); 236 for(i=inc_current; i<inc_nVertices; i++) 237 { 238 if(compV2InY(inc_array[i], dec_array[dec_current]) >0) 239 rChain.processNewVertex(inc_array[i], backend); 240 else 241 break; 242 } 243 rChain.outputFan(dec_array[dec_current], backend); 244 monoTriangulationRec(inc_array[i-1], botVertex, 245 inc_chain, i, 246 dec_chain, dec_current, 247 backend); 248 } 249 }/*end case neither is empty*/ 250} 251 252 253void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend) 254{ 255 Int i; 256 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain, 257 *then call monoTriangulationRec 258 */ 259 Arc_ptr tempV; 260 Arc_ptr topV; 261 Arc_ptr botV; 262 topV = botV = loop; 263 for(tempV = loop->next; tempV != loop; tempV = tempV->next) 264 { 265 if(compFun(topV->tail(), tempV->tail())<0) { 266 topV = tempV; 267 } 268 if(compFun(botV->tail(), tempV->tail())>0) { 269 botV = tempV; 270 } 271 } 272 273 /*creat increase and decrease chains*/ 274 vertexArray inc_chain(20); /*this is a dynamic array*/ 275 for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/ 276 inc_chain.appendVertex(topV->pwlArc->pts[i].param); 277 } 278 for(tempV = topV->next; tempV != botV; tempV = tempV->next) 279 { 280 for(i=0; i<=tempV->pwlArc->npts-2; i++){ 281 inc_chain.appendVertex(tempV->pwlArc->pts[i].param); 282 } 283 } 284 285 vertexArray dec_chain(20); 286 for(tempV = topV->prev; tempV != botV; tempV = tempV->prev) 287 { 288 for(i=tempV->pwlArc->npts-2; i>=0; i--){ 289 dec_chain.appendVertex(tempV->pwlArc->pts[i].param); 290 } 291 } 292 for(i=botV->pwlArc->npts-2; i>=1; i--){ 293 dec_chain.appendVertex(tempV->pwlArc->pts[i].param); 294 } 295 296 monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend); 297 298} 299 300/*if compFun == compV2InY, top to bottom: V-monotone 301 *if compFun == compV2InX, right to left: U-monotone 302 */ 303void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex, 304 vertexArray* inc_chain, Int inc_current, 305 vertexArray* dec_chain, Int dec_current, 306 Int (*compFun)(Real*, Real*), 307 Backend* backend) 308{ 309 assert( inc_chain != NULL && dec_chain != NULL); 310 assert( ! (inc_current>=inc_chain->getNumElements() && 311 dec_current>=dec_chain->getNumElements())); 312 Int inc_nVertices; 313 Int dec_nVertices; 314 Real** inc_array ; 315 Real** dec_array ; 316 Int i; 317 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL))); 318 319 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/ 320 { 321 322 dec_array = dec_chain->getArray(); 323 dec_nVertices = dec_chain->getNumElements(); 324 reflexChain rChain(20,0); 325 /*put the top vertex into the reflex chain*/ 326 rChain.processNewVertex(topVertex, backend); 327 /*process all the vertices on the dec_chain*/ 328 for(i=dec_current; i<dec_nVertices; i++){ 329 rChain.processNewVertex(dec_array[i], backend); 330 } 331 /*process the bottom vertex*/ 332 rChain.processNewVertex(botVertex, backend); 333 334 } 335 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/ 336 { 337 inc_array = inc_chain->getArray(); 338 inc_nVertices= inc_chain->getNumElements(); 339 reflexChain rChain(20,1); 340 /*put the top vertex into the reflex chain*/ 341 rChain.processNewVertex(topVertex, backend); 342 /*process all the vertices on the inc_chain*/ 343 for(i=inc_current; i<inc_nVertices; i++){ 344 rChain.processNewVertex(inc_array[i], backend); 345 } 346 /*process the bottom vertex*/ 347 rChain.processNewVertex(botVertex, backend); 348 } 349 else /*neither chain is empty*/ 350 { 351 inc_array = inc_chain -> getArray(); 352 dec_array = dec_chain -> getArray(); 353 inc_nVertices= inc_chain->getNumElements(); 354 dec_nVertices= dec_chain->getNumElements(); 355 /*if top of inc_chain is 'lower' than top of dec_chain, process all the 356 *vertices on the dec_chain which are higher than top of inc_chain 357 */ 358 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0) 359 { 360 361 reflexChain rChain(20, 0); 362 rChain.processNewVertex(topVertex, backend); 363 for(i=dec_current; i<dec_nVertices; i++) 364 { 365 if(compFun(inc_array[inc_current], dec_array[i]) <= 0) 366 rChain.processNewVertex(dec_array[i], backend); 367 else 368 break; 369 } 370 rChain.outputFan(inc_array[inc_current], backend); 371 monoTriangulationRecFunBackend(dec_array[i-1], botVertex, 372 inc_chain, inc_current, 373 dec_chain, i, 374 compFun, 375 backend); 376 } 377 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/ 378 { 379 380 reflexChain rChain(20, 1); 381 rChain.processNewVertex(topVertex, backend); 382 for(i=inc_current; i<inc_nVertices; i++) 383 { 384 if(compFun(inc_array[i], dec_array[dec_current]) >0) 385 rChain.processNewVertex(inc_array[i], backend); 386 else 387 break; 388 } 389 rChain.outputFan(dec_array[dec_current], backend); 390 monoTriangulationRecFunBackend(inc_array[i-1], botVertex, 391 inc_chain, i, 392 dec_chain, dec_current, 393 compFun, 394 backend); 395 } 396 }/*end case neither is empty*/ 397} 398