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 <stdlib.h> 39 //#include <stdio.h> 40 //#include "glimports.h" 41 #include "sampleComp.h" 42 #include "sampleCompTop.h" 43 #include "sampleCompBot.h" 44 #include "sampleCompRight.h" 45 46 47 48 #define max(a,b) ((a>b)? a:b) 49 #define min(a,b) ((a>b)? b:a) 50 51 void sampleConnectedComp(Real* topVertex, Real* botVertex, 52 vertexArray* leftChain, 53 Int leftStartIndex, Int leftEndIndex, 54 vertexArray* rightChain, 55 Int rightStartIndex, Int rightEndIndex, 56 gridBoundaryChain* leftGridChain, 57 gridBoundaryChain* rightGridChain, 58 Int gridIndex1, Int gridIndex2, 59 Int up_leftCornerWhere, 60 Int up_leftCornerIndex, 61 Int up_rightCornerWhere, 62 Int up_rightCornerIndex, 63 Int down_leftCornerWhere, 64 Int down_leftCornerIndex, 65 Int down_rightCornerWhere, 66 Int down_rightCornerIndex, 67 primStream* pStream, 68 rectBlockArray* rbArray 69 ) 70 { 71 72 sampleCompLeft(topVertex, botVertex, 73 leftChain, 74 leftStartIndex, leftEndIndex, 75 rightChain, 76 rightStartIndex, rightEndIndex, 77 leftGridChain, 78 gridIndex1, 79 gridIndex2, 80 up_leftCornerWhere, 81 up_leftCornerIndex, 82 down_leftCornerWhere, 83 down_leftCornerIndex, 84 pStream); 85 86 87 sampleCompRight(topVertex, botVertex, 88 leftChain, 89 leftStartIndex, leftEndIndex, 90 rightChain, 91 rightStartIndex, 92 rightEndIndex, 93 rightGridChain, 94 gridIndex1, gridIndex2, 95 up_rightCornerWhere, 96 up_rightCornerIndex, 97 down_rightCornerWhere, 98 down_rightCornerIndex, 99 pStream); 100 101 102 sampleCompTop(topVertex, 103 leftChain, 104 leftStartIndex, 105 rightChain, 106 rightStartIndex, 107 leftGridChain, 108 rightGridChain, 109 gridIndex1, 110 up_leftCornerWhere, 111 up_leftCornerIndex, 112 up_rightCornerWhere, 113 up_rightCornerIndex, 114 pStream); 115 116 sampleCompBot(botVertex, 117 leftChain, 118 leftEndIndex, 119 rightChain, 120 rightEndIndex, 121 leftGridChain, 122 rightGridChain, 123 gridIndex2, 124 down_leftCornerWhere, 125 down_leftCornerIndex, 126 down_rightCornerWhere, 127 down_rightCornerIndex, 128 pStream); 129 130 131 //the center 132 133 rbArray->insert(new rectBlock(leftGridChain, rightGridChain, gridIndex1, gridIndex2)); 134 135 136 } 137 138 /*notice that we need rightChain because the 139 *corners could be on the rightChain. 140 *here comp means component. 141 */ 142 void sampleCompLeft(Real* topVertex, Real* botVertex, 143 vertexArray* leftChain, 144 Int leftStartIndex, Int leftEndIndex, 145 vertexArray* rightChain, 146 Int rightStartIndex, Int rightEndIndex, 147 gridBoundaryChain* leftGridChain, 148 Int gridIndex1, Int gridIndex2, 149 Int up_leftCornerWhere, 150 Int up_leftCornerIndex, 151 Int down_leftCornerWhere, 152 Int down_leftCornerIndex, 153 primStream* pStream) 154 { 155 /*find out whether there is a trim vertex which is 156 *inbetween the top and bot grid lines or not. 157 */ 158 Int midIndex1; 159 Int midIndex2; 160 Int gridMidIndex1 = 0, gridMidIndex2 = 0; 161 //midIndex1: array[i] <= v, array[i-1] > v 162 //midIndex2: array[i] >= v, array[i+1] < v 163 // v(gridMidIndex1) >= v(midindex1) > v(gridMidIndex1+1) 164 // v(gridMidIndex2-1) >= v(midIndex2) > v(gridMidIndex2) ?? 165 midIndex1 = leftChain->findIndexBelowGen( 166 leftGridChain->get_v_value(gridIndex1), 167 leftStartIndex, 168 leftEndIndex); 169 170 midIndex2 = -1; /*initilization*/ 171 if(midIndex1<= leftEndIndex && gridIndex1<gridIndex2) 172 if(leftChain->getVertex(midIndex1)[1] >= leftGridChain->get_v_value(gridIndex2)) 173 { 174 midIndex2 = leftChain->findIndexAboveGen( 175 leftGridChain->get_v_value(gridIndex2), 176 midIndex1, //midIndex1 <= midIndex2. 177 leftEndIndex); 178 gridMidIndex1 = leftGridChain->lookfor(leftChain->getVertex(midIndex1)[1], 179 gridIndex1, gridIndex2); 180 gridMidIndex2 = 1+leftGridChain->lookfor(leftChain->getVertex(midIndex2)[1], 181 gridMidIndex1, gridIndex2); 182 } 183 184 185 /*to interprete the corner information*/ 186 Real* cornerTop; 187 Real* cornerBot; 188 Int cornerLeftStart; 189 Int cornerLeftEnd; 190 Int cornerRightUpEnd; 191 Int cornerRightDownStart; 192 if(up_leftCornerWhere == 0) /*left corner is on left chain*/ 193 { 194 cornerTop = leftChain->getVertex(up_leftCornerIndex); 195 cornerLeftStart = up_leftCornerIndex+1; 196 cornerRightUpEnd = -1; /*no right*/ 197 } 198 else if(up_leftCornerWhere == 1) /*left corner is on top*/ 199 { 200 cornerTop = topVertex; 201 cornerLeftStart = leftStartIndex; 202 cornerRightUpEnd = -1; /*no right*/ 203 } 204 else /*left corner is on right chain*/ 205 { 206 cornerTop = topVertex; 207 cornerLeftStart = leftStartIndex; 208 cornerRightUpEnd = up_leftCornerIndex; 209 } 210 211 if(down_leftCornerWhere == 0) /*left corner is on left chain*/ 212 { 213 cornerBot = leftChain->getVertex(down_leftCornerIndex); 214 cornerLeftEnd = down_leftCornerIndex-1; 215 cornerRightDownStart = rightEndIndex+1; /*no right*/ 216 } 217 else if(down_leftCornerWhere == 1) /*left corner is on bot*/ 218 { 219 cornerBot = botVertex; 220 cornerLeftEnd = leftEndIndex; 221 cornerRightDownStart = rightEndIndex+1; /*no right*/ 222 } 223 else /*left corner is on the right chian*/ 224 { 225 cornerBot = botVertex; 226 cornerLeftEnd = leftEndIndex; 227 cornerRightDownStart = down_leftCornerIndex; 228 } 229 230 231 232 233 /*sample*/ 234 if(midIndex2 >= 0) /*there is a trim point inbewteen grid lines*/ 235 { 236 237 sampleLeftSingleTrimEdgeRegionGen(cornerTop, leftChain->getVertex(midIndex1), 238 leftChain, 239 cornerLeftStart, 240 midIndex1-1, 241 leftGridChain, 242 gridIndex1, 243 gridMidIndex1, 244 rightChain, 245 rightStartIndex, 246 cornerRightUpEnd, 247 0, //no right down section 248 -1, 249 pStream); 250 251 sampleLeftSingleTrimEdgeRegionGen(leftChain->getVertex(midIndex2), 252 cornerBot, 253 leftChain, 254 midIndex2+1, 255 cornerLeftEnd, 256 leftGridChain, 257 gridMidIndex2, 258 gridIndex2, 259 rightChain, 260 0, //no right up section 261 -1, 262 cornerRightDownStart, 263 rightEndIndex, 264 pStream); 265 266 267 sampleLeftStripRecF(leftChain, 268 midIndex1, 269 midIndex2, 270 leftGridChain, 271 gridMidIndex1, 272 gridMidIndex2, 273 pStream); 274 } 275 else 276 { 277 sampleLeftSingleTrimEdgeRegionGen(cornerTop, cornerBot, 278 leftChain, 279 cornerLeftStart, 280 cornerLeftEnd, 281 leftGridChain, 282 gridIndex1, 283 gridIndex2, 284 rightChain, 285 rightStartIndex, 286 cornerRightUpEnd, 287 cornerRightDownStart, 288 rightEndIndex, 289 pStream); 290 } 291 } 292 293 void sampleLeftSingleTrimEdgeRegionGen(Real topVert[2], Real botVert[2], 294 vertexArray* leftChain, 295 Int leftStart, 296 Int leftEnd, 297 gridBoundaryChain* gridChain, 298 Int gridBeginIndex, 299 Int gridEndIndex, 300 vertexArray* rightChain, 301 Int rightUpBegin, 302 Int rightUpEnd, 303 Int rightDownBegin, 304 Int rightDownEnd, 305 primStream* pStream) 306 { 307 Int i,j,k; 308 309 /*creat an array to store all the up and down secments of the right chain, 310 *and the left end grid points 311 * 312 *although vertex array is a dynamic array, but to gain efficiency, 313 *it is better to initiliza the exact array size 314 */ 315 vertexArray vArray(gridEndIndex-gridBeginIndex+1 + 316 max(0,rightUpEnd - rightUpBegin+1)+ 317 max(0,rightDownEnd - rightDownBegin+1)); 318 319 /*append the vertices on the up section of thr right chain*/ 320 for(i=rightUpBegin; i<= rightUpEnd; i++) 321 vArray.appendVertex(rightChain->getVertex(i)); 322 323 /*append the vertices of the left extremal grid points, 324 *and at the same time, perform triangulation for the stair cases 325 */ 326 vArray.appendVertex(gridChain->get_vertex(gridBeginIndex)); 327 328 for(k=1, i=gridBeginIndex+1; i<=gridEndIndex; i++, k++) 329 { 330 vArray.appendVertex(gridChain->get_vertex(i)); 331 332 /*output the fan of the grid points of the (i)th and (i-1)th grid line. 333 */ 334 if(gridChain->getUlineIndex(i) < gridChain->getUlineIndex(i-1)) 335 { 336 pStream->begin(); 337 pStream->insert(gridChain->get_vertex(i-1)); 338 for(j=gridChain->getUlineIndex(i); j<= gridChain->getUlineIndex(i-1); j++) 339 pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i)); 340 pStream->end(PRIMITIVE_STREAM_FAN); 341 } 342 else if(gridChain->getUlineIndex(i) > gridChain->getUlineIndex(i-1)) 343 { 344 pStream->begin(); 345 pStream->insert(gridChain->get_vertex(i)); 346 for(j=gridChain->getUlineIndex(i); j>= gridChain->getUlineIndex(i-1); j--) 347 pStream->insert(gridChain->getGrid()->get_u_value(j), gridChain->get_v_value(i-1)); 348 pStream->end(PRIMITIVE_STREAM_FAN); 349 } 350 /*otherwisem, the two are equal, so there is no fan to outout*/ 351 } 352 353 /*then append all the vertices on the down section of the right chain*/ 354 for(i=rightDownBegin; i<= rightDownEnd; i++) 355 vArray.appendVertex(rightChain->getVertex(i)); 356 357 monoTriangulationRecGen(topVert, botVert, 358 leftChain, leftStart, leftEnd, 359 &vArray, 0, vArray.getNumElements()-1, 360 pStream); 361 362 } 363 364 365 366 367 368 369 370 371 372