ReactOS  0.4.14-dev-52-g6116262
sampleCompTop.cc
Go to the documentation of this file.
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 <math.h>
41 //#include "zlassert.h"
42 #include "sampleCompTop.h"
43 #include "sampleCompRight.h"
44 
45 #define max(a,b) ((a>b)? a:b)
46 
47 //return : index_small, and index_large,
48 //from [small, large] is strictly U-monotne,
49 //from [large+1, end] is <u
50 //and vertex[large][0] is >= u
51 //if eveybody is <u, the large = start-1.
52 //otherwise both large and small are meaningful and we have start<=small<=large<=end
54  Int leftStart,
55  Int leftEnd,
56  Real u,
57  Int& ret_index_small,
58  Int& ret_index_large
59  )
60 {
61  Int i;
62  assert(leftStart <= leftEnd);
63  for(i=leftEnd; i>= leftStart; i--)
64  {
65  if(leftChain->getVertex(i)[0] >= u)
66  break;
67  }
68  ret_index_large = i;
69  if(ret_index_large >= leftStart)
70  {
71  for(i=ret_index_large; i>leftStart; i--)
72  {
73  if(leftChain->getVertex(i-1)[0] <= leftChain->getVertex(i)[0])
74  break;
75  }
76  ret_index_small = i;
77  }
78 }
79 
81  Int rightStart,
82  Int rightEnd,
83  Real u,
84  Int& ret_index_small,
85  Int& ret_index_large)
86 {
87  Int i;
88  assert(rightStart<=rightEnd);
89  for(i=rightEnd; i>=rightStart; i--)
90  {
91  if(rightChain->getVertex(i)[0] <= u)
92  break;
93  }
94  ret_index_large = i;
95  if(ret_index_large >= rightStart)
96  {
97  for(i=ret_index_large; i>rightStart;i--)
98  {
99  if(rightChain->getVertex(i-1)[0] >= rightChain->getVertex(i)[0])
100  break;
101  }
102  ret_index_small = i;
103  }
104 }
105 
106 
108  vertexArray* rightChain,
109  Int rightStart,
110  Int segIndexSmall,
111  Int segIndexLarge,
112  Int rightEnd,
113  gridWrap* grid,
114  Int gridV,
115  Int leftU,
116  Int rightU,
117  primStream* pStream)
118 {
119  //the possible section which is to the right of rightU
120  if(segIndexLarge < rightEnd)
121  {
122  Real *tempTop;
123  if(segIndexLarge >= rightStart)
124  tempTop = rightChain->getVertex(segIndexLarge);
125  else
126  tempTop = topVertex;
127  Real tempBot[2];
128  tempBot[0] = grid->get_u_value(rightU);
129  tempBot[1] = grid->get_v_value(gridV);
130 monoTriangulationRecGenOpt(tempTop, tempBot,
131  NULL, 1,0,
132  rightChain, segIndexLarge+1, rightEnd,
133  pStream);
134 /*
135  monoTriangulation2(tempTop, tempBot,
136  rightChain,
137  segIndexLarge+1,
138  rightEnd,
139  0, //a decrease chian
140  pStream);
141 */
142 
143  }
144 
145  //the possible section which is strictly Umonotone
146  if(segIndexLarge >= rightStart)
147  {
148  stripOfFanRight(rightChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
149  Real tempBot[2];
150  tempBot[0] = grid->get_u_value(leftU);
151  tempBot[1] = grid->get_v_value(gridV);
152  monoTriangulation2(topVertex, tempBot, rightChain, rightStart, segIndexSmall, 0, pStream);
153  }
154  else //the topVertex forms a fan with the grid points
155  grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
156 }
157 
159  vertexArray* rightChain,
160  Int rightStart,
161  Int rightEnd,
162  gridWrap* grid,
163  Int gridV,
164  Int leftU,
165  Int rightU,
166  primStream* pStream
167  )
168 {
169  //if right chian is empty, then there is only one topVertex with one grid line
170  if(rightEnd < rightStart){
171  grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
172  return;
173  }
174 
175  Int segIndexSmall = 0, segIndexLarge;
176  findTopRightSegment(rightChain,
177  rightStart,
178  rightEnd,
179  grid->get_u_value(rightU),
180  segIndexSmall,
181  segIndexLarge
182  );
183  sampleTopRightWithGridLinePost(topVertex, rightChain,
184  rightStart,
185  segIndexSmall,
186  segIndexLarge,
187  rightEnd,
188  grid,
189  gridV,
190  leftU,
191  rightU,
192  pStream);
193 }
194 
195 
197  vertexArray* leftChain,
198  Int leftStart,
199  Int segIndexSmall,
200  Int segIndexLarge,
201  Int leftEnd,
202  gridWrap* grid,
203  Int gridV,
204  Int leftU,
205  Int rightU,
206  primStream* pStream)
207 {
208  //the possible section which is to the left of leftU
209 
210  if(segIndexLarge < leftEnd)
211  {
212  Real *tempTop;
213  if(segIndexLarge >= leftStart)
214  tempTop = leftChain->getVertex(segIndexLarge);
215  else
216  tempTop = topVertex;
217  Real tempBot[2];
218  tempBot[0] = grid->get_u_value(leftU);
219  tempBot[1] = grid->get_v_value(gridV);
220 
221  monoTriangulation2(tempTop, tempBot,
222  leftChain,
223  segIndexLarge+1,
224  leftEnd,
225  1, //a increase chian
226  pStream);
227  }
228 
229  //the possible section which is strictly Umonotone
230  if(segIndexLarge >= leftStart)
231  {
232  //if there are grid points which are to the right of topV,
233  //then we should use topVertex to form a fan with these points to
234  //optimize the triangualtion
235  int do_optimize=1;
236  if(topVertex[0] >= grid->get_u_value(rightU))
237  do_optimize = 0;
238  else
239  {
240  //we also have to make sure that topVertex are the right most vertex
241  //on the chain.
242  int i;
243  for(i=leftStart; i<=segIndexSmall; i++)
244  if(leftChain->getVertex(i)[0] >= topVertex[0])
245  {
246  do_optimize = 0;
247  break;
248  }
249  }
250 
251  if(do_optimize)
252  {
253  //find midU so that grid->get_u_value(midU) >= topVertex[0]
254  //and grid->get_u_value(midU-1) < topVertex[0]
255  int midU=rightU;
256  while(grid->get_u_value(midU) >= topVertex[0])
257  {
258  midU--;
259  if(midU < leftU)
260  break;
261  }
262  midU++;
263 
264  grid->outputFanWithPoint(gridV, midU, rightU, topVertex, pStream);
265  stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, midU, pStream, 0);
266  Real tempBot[2];
267  tempBot[0] = grid->get_u_value(midU);
268  tempBot[1] = grid->get_v_value(gridV);
269  monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
270  }
271  else //not optimize
272  {
273 
274  stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
275  Real tempBot[2];
276  tempBot[0] = grid->get_u_value(rightU);
277  tempBot[1] = grid->get_v_value(gridV);
278  monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
279  }
280  }
281  else //the topVertex forms a fan with the grid points
282  grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
283 }
284 
285 
287  vertexArray* leftChain,
288  Int leftStart,
289  Int leftEnd,
290  gridWrap* grid,
291  Int gridV,
292  Int leftU,
293  Int rightU,
294  primStream* pStream
295  )
296 {
297  Int segIndexSmall = 0, segIndexLarge;
298  //if left chain is empty, then there is only one top vertex with one grid
299  // line
300  if(leftEnd < leftStart) {
301  grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
302  return;
303  }
304  findTopLeftSegment(leftChain,
305  leftStart,
306  leftEnd,
307  grid->get_u_value(leftU),
308  segIndexSmall,
309  segIndexLarge
310  );
312  leftChain,
313  leftStart,
314  segIndexSmall,
315  segIndexLarge,
316  leftEnd,
317  grid,
318  gridV,
319  leftU,
320  rightU,
321  pStream);
322 }
323 
324 
325 //return 1 if saprator exits, 0 otherwise
327  Int leftStartIndex,
328  Int leftEndIndex,
329  vertexArray* rightChain,
330  Int rightStartIndex,
331  Int rightEndIndex,
332  Int& ret_sep_left,
333  Int& ret_sep_right)
334 {
335 
336  Int oldLeftI, oldRightI, newLeftI, newRightI;
337  Int i,j,k;
338  Real leftMax /*= leftChain->getVertex(leftEndIndex)[0]*/;
339  Real rightMin /*= rightChain->getVertex(rightEndIndex)[0]*/;
340  if(leftChain->getVertex(leftEndIndex)[1] > rightChain->getVertex(rightEndIndex)[1]) //left higher
341  {
342  oldLeftI = leftEndIndex+1;
343  oldRightI = rightEndIndex;
344  leftMax = leftChain->getVertex(leftEndIndex)[0] - Real(1.0); //initilza to left of leftU
345  rightMin = rightChain->getVertex(rightEndIndex)[0];
346  }
347  else
348  {
349  oldLeftI = leftEndIndex;
350  oldRightI = rightEndIndex+1;
351  leftMax = leftChain->getVertex(leftEndIndex)[0];
352  rightMin = rightChain->getVertex(rightEndIndex)[0] + Real(1.0);
353  }
354 
355  //i: the current working leftChain index,
356  //j: the current working rightChain index,
357  //if left(i) is higher than right(j), then the two chains beloew right(j) are separated.
358  //else the two chains below left(i) are separeated.
359  i=leftEndIndex;
360  j=rightEndIndex;
361  while(1)
362  {
363  newLeftI = oldLeftI;
364  newRightI = oldRightI;
365 
366  if(i<leftStartIndex) //left chain is done, go through remining right chain.
367  {
368  for(k=j-1; k>= rightStartIndex; k--)
369  {
370  if(rightChain->getVertex(k)[0] > leftMax) //no conflict
371  {
372  //update oldRightI if necessary
373  if(rightChain->getVertex(k)[0] < rightMin)
374  {
375  rightMin = rightChain->getVertex(k)[0];
376  oldRightI = k;
377  }
378  }
379  else //there is a conflict
380  break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI.
381  }
382  break; //the while loop
383  }
384  else if(j<rightStartIndex) //rightChain is done
385  {
386  for(k=i-1; k>= leftStartIndex; k--)
387  {
388  if(leftChain->getVertex(k)[0] < rightMin) //no conflict
389  {
390  //update oldLeftI if necessary
391  if(leftChain->getVertex(k)[0] > leftMax)
392  {
393  leftMax = leftChain->getVertex(k)[0];
394  oldLeftI = k;
395  }
396  }
397  else //there is a conflict
398  break; //the for loop
399  }
400  break; //the while loop
401  }
402  else if(leftChain->getVertex(i)[1] > rightChain->getVertex(j)[1]) //left hgiher
403  {
404  if(leftChain->getVertex(i)[0] > leftMax) //update leftMax and newLeftI.
405  {
406  leftMax = leftChain->getVertex(i)[0];
407  newLeftI = i;
408  }
409  for(k=j-1; k>= rightStartIndex; k--) //update rightMin and newRightI.
410  {
411  if(rightChain->getVertex(k)[1] > leftChain->getVertex(i)[1])
412  break;
413  if(rightChain->getVertex(k)[0] < rightMin)
414  {
415  rightMin = rightChain->getVertex(k)[0];
416  newRightI = k;
417  }
418  }
419  j = k; //next working j, since j will be higher than i in next loop
420  if(leftMax >= rightMin) //there is a conflict
421  break;
422  else //still no conflict
423  {
424  oldLeftI = newLeftI;
425  oldRightI = newRightI;
426  }
427  }
428  else //right higher
429  {
430  if(rightChain->getVertex(j)[0] < rightMin)
431  {
432  rightMin = rightChain->getVertex(j)[0];
433  newRightI = j;
434  }
435  for(k=i-1; k>= leftStartIndex; k--)
436  {
437  if(leftChain->getVertex(k)[1] > rightChain->getVertex(j)[1])
438  break;
439  if(leftChain->getVertex(k)[0] > leftMax)
440  {
441  leftMax = leftChain->getVertex(k)[0];
442  newLeftI = k;
443  }
444  }
445  i = k; //next working i, since i will be higher than j next loop
446 
447  if(leftMax >= rightMin) //there is a conflict
448  break;
449  else //still no conflict
450  {
451  oldLeftI = newLeftI;
452  oldRightI = newRightI;
453  }
454  }
455  }//end of while loop
456  //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid
457  if(oldLeftI > leftEndIndex || oldRightI > rightEndIndex)
458  return 0;
459  else
460  {
461  ret_sep_left = oldLeftI;
462  ret_sep_right = oldRightI;
463  return 1;
464  }
465 }
466 
467 
468 void sampleCompTop(Real* topVertex,
469  vertexArray* leftChain,
470  Int leftStartIndex,
471  vertexArray* rightChain,
472  Int rightStartIndex,
473  gridBoundaryChain* leftGridChain,
474  gridBoundaryChain* rightGridChain,
475  Int gridIndex1,
476  Int up_leftCornerWhere,
477  Int up_leftCornerIndex,
478  Int up_rightCornerWhere,
479  Int up_rightCornerIndex,
480  primStream* pStream)
481 {
482  if(up_leftCornerWhere == 1 && up_rightCornerWhere == 1) //the top is topVertex with possible grid points
483  {
484  leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex1),
485  leftGridChain->getUlineIndex(gridIndex1),
486  rightGridChain->getUlineIndex(gridIndex1),
487  topVertex,
488  pStream);
489  return;
490  }
491 
492  else if(up_leftCornerWhere != 0)
493  {
494  Real* tempTop;
495  Int tempRightStart;
496  if(up_leftCornerWhere == 1){
497  tempRightStart = rightStartIndex;
498  tempTop = topVertex;
499  }
500  else
501  {
502  tempRightStart = up_leftCornerIndex+1;
503  tempTop = rightChain->getVertex(up_leftCornerIndex);
504  }
505  sampleTopRightWithGridLine(tempTop, rightChain, tempRightStart, up_rightCornerIndex,
506  rightGridChain->getGrid(),
507  leftGridChain->getVlineIndex(gridIndex1),
508  leftGridChain->getUlineIndex(gridIndex1),
509  rightGridChain->getUlineIndex(gridIndex1),
510  pStream);
511  }
512  else if(up_rightCornerWhere != 2)
513  {
514  Real* tempTop;
515  Int tempLeftStart;
516  if(up_rightCornerWhere == 1)
517  {
518  tempLeftStart = leftStartIndex;
519  tempTop = topVertex;
520  }
521  else //0
522  {
523  tempLeftStart = up_rightCornerIndex+1;
524  tempTop = leftChain->getVertex(up_rightCornerIndex);
525  }
526 /*
527  sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex,
528  leftGridChain->getGrid(),
529  leftGridChain->getVlineIndex(gridIndex1),
530  leftGridChain->getUlineIndex(gridIndex1),
531  rightGridChain->getUlineIndex(gridIndex1),
532  pStream);
533 */
534  sampleCompTopSimple(topVertex,
535  leftChain,
536  leftStartIndex,
537  rightChain,
538  rightStartIndex,
539  leftGridChain,
540  rightGridChain,
541  gridIndex1,
542  up_leftCornerWhere,
543  up_leftCornerIndex,
544  up_rightCornerWhere,
545  up_rightCornerIndex,
546  pStream);
547  }
548  else //up_leftCornerWhere == 0, up_rightCornerWhere == 2.
549  {
550  sampleCompTopSimple(topVertex,
551  leftChain,
552  leftStartIndex,
553  rightChain,
554  rightStartIndex,
555  leftGridChain,
556  rightGridChain,
557  gridIndex1,
558  up_leftCornerWhere,
559  up_leftCornerIndex,
560  up_rightCornerWhere,
561  up_rightCornerIndex,
562  pStream);
563  return;
564 #ifdef NOT_REACHABLE //code is not reachable, for test purpose only
565  //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C:
566  Int sep_left, sep_right;
567  if(findTopSeparator(leftChain,
568  leftStartIndex,
569  up_leftCornerIndex,
570  rightChain,
571  rightStartIndex,
572  up_rightCornerIndex,
573  sep_left,
574  sep_right)
575  ) //separator exists
576  {
577 
578  if( leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1) &&
579  rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
580  {
581  Int gridSep;
582  Int segLeftSmall, segLeftLarge, segRightSmall, segRightLarge;
583  Int valid=1; //whether the gridStep is valid or not.
584  findTopLeftSegment(leftChain,
585  sep_left,
586  up_leftCornerIndex,
587  leftGridChain->get_u_value(gridIndex1),
588  segLeftSmall,
589  segLeftLarge);
590  findTopRightSegment(rightChain,
591  sep_right,
592  up_rightCornerIndex,
593  rightGridChain->get_u_value(gridIndex1),
594  segRightSmall,
595  segRightLarge);
596  if(leftChain->getVertex(segLeftSmall)[1] >= rightChain->getVertex(segRightSmall)[1])
597  {
598  gridSep = rightGridChain->getUlineIndex(gridIndex1);
599  while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftSmall)[0])
600  gridSep--;
601  if(segLeftSmall<segLeftLarge)
602  if(leftGridChain->getGrid()->get_u_value(gridSep) < leftChain->getVertex(segLeftSmall+1)[0])
603  {
604  valid = 0;
605  }
606  }
607  else
608  {
609  gridSep = leftGridChain->getUlineIndex(gridIndex1);
610  while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightSmall)[0])
611  gridSep++;
612  if(segRightSmall<segRightLarge)
613  if(leftGridChain->getGrid()->get_u_value(gridSep) > rightChain->getVertex(segRightSmall+1)[0])
614  {
615  valid = 0;
616  }
617  }
618 
619  if(! valid)
620  {
621  sampleCompTopSimple(topVertex,
622  leftChain,
623  leftStartIndex,
624  rightChain,
625  rightStartIndex,
626  leftGridChain,
627  rightGridChain,
628  gridIndex1,
629  up_leftCornerWhere,
630  up_leftCornerIndex,
631  up_rightCornerWhere,
632  up_rightCornerIndex,
633  pStream);
634  }
635  else
636  {
637  sampleTopLeftWithGridLinePost(leftChain->getVertex(segLeftSmall),
638  leftChain,
639  segLeftSmall+1,
640  segLeftSmall+1,
641  segLeftLarge,
642  up_leftCornerIndex,
643  leftGridChain->getGrid(),
644  leftGridChain->getVlineIndex(gridIndex1),
645  leftGridChain->getUlineIndex(gridIndex1),
646  gridSep,
647  pStream);
648  sampleTopRightWithGridLinePost(rightChain->getVertex(segRightSmall),
649  rightChain,
650  segRightSmall+1,
651  segRightSmall+1,
652  segRightLarge,
653  up_rightCornerIndex,
654  leftGridChain->getGrid(),
655  leftGridChain->getVlineIndex(gridIndex1),
656  gridSep,
657  rightGridChain->getUlineIndex(gridIndex1),
658  pStream);
659  Real tempBot[2];
660  tempBot[0] = leftGridChain->getGrid()->get_u_value(gridSep);
661  tempBot[1] = leftGridChain->get_v_value(gridIndex1);
662  monoTriangulationRecGen(topVertex, tempBot,
663  leftChain, leftStartIndex, segLeftSmall,
664  rightChain, rightStartIndex, segRightSmall,
665  pStream);
666  }
667  }//end if both sides have vetices inside the gridboundary points
668  else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1)) //left is in, right is nout
669  {
670 
671  Int segLeftSmall, segLeftLarge;
672  findTopLeftSegment(leftChain,
673  sep_left,
674  up_leftCornerIndex,
675  leftGridChain->get_u_value(gridIndex1),
676  segLeftSmall,
677  segLeftLarge);
678  assert(segLeftLarge >= sep_left);
679  monoTriangulation2(leftChain->getVertex(segLeftLarge),
680  leftGridChain->get_vertex(gridIndex1),
681  leftChain,
682  segLeftLarge+1,
683  up_leftCornerIndex,
684  1, //a increase chain,
685  pStream);
686 
687  stripOfFanLeft(leftChain, segLeftLarge, segLeftSmall,
688  leftGridChain->getGrid(),
689  leftGridChain->getVlineIndex(gridIndex1),
690  leftGridChain->getUlineIndex(gridIndex1),
691  rightGridChain->getUlineIndex(gridIndex1),
692  pStream, 0);
693 
694 
695  monoTriangulationRecGen(topVertex, rightGridChain->get_vertex(gridIndex1),
696  leftChain, leftStartIndex, segLeftSmall,
697  rightChain, rightStartIndex, up_rightCornerIndex,
698  pStream);
699  }//end left in right out
700  else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
701  {
702  Int segRightSmall, segRightLarge;
703  findTopRightSegment(rightChain,
704  sep_right,
705  up_rightCornerIndex,
706  rightGridChain->get_u_value(gridIndex1),
707  segRightSmall,
708  segRightLarge);
709  assert(segRightLarge>=sep_right);
710  monoTriangulation2(rightChain->getVertex(segRightLarge),
711  rightGridChain->get_vertex(gridIndex1),
712  rightChain,
713  segRightLarge+1,
714  up_rightCornerIndex,
715  0, //a decrease chain
716  pStream);
717  stripOfFanRight(rightChain, segRightLarge, segRightSmall,
718  rightGridChain->getGrid(),
719  rightGridChain->getVlineIndex(gridIndex1),
720  leftGridChain->getUlineIndex(gridIndex1),
721  rightGridChain->getUlineIndex(gridIndex1),
722  pStream, 0);
723 
724 
725  monoTriangulationRecGen(topVertex, leftGridChain->get_vertex(gridIndex1),
726  leftChain, leftStartIndex, up_leftCornerIndex,
727  rightChain, rightStartIndex,segRightSmall,
728  pStream);
729 
730  }//end left out rigth in
731  else //left out , right out
732  {
733 
734  sampleCompTopSimple(topVertex,
735  leftChain,
736  leftStartIndex,
737  rightChain,
738  rightStartIndex,
739  leftGridChain,
740  rightGridChain,
741  gridIndex1,
742  up_leftCornerWhere,
743  up_leftCornerIndex,
744  up_rightCornerWhere,
745  up_rightCornerIndex,
746  pStream);
747  }//end leftout, right out
748  }//end if separator exixts.
749  else //no separator
750  {
751 
752  sampleCompTopSimple(topVertex,
753  leftChain,
754  leftStartIndex,
755  rightChain,
756  rightStartIndex,
757  leftGridChain,
758  rightGridChain,
759  gridIndex1,
760  up_leftCornerWhere,
761  up_leftCornerIndex,
762  up_rightCornerWhere,
763  up_rightCornerIndex,
764  pStream);
765  }
766 #endif
767  }//end if 0,2
768 }//end if the function
769 
770 
772  Int gridV,
773  Real* topVertex, Real* botVertex,
774  vertexArray* inc_chain, Int inc_current, Int inc_end,
775  vertexArray* dec_chain, Int dec_current, Int dec_end,
776  primStream* pStream)
777 {
778  if(gridV <= 0 || dec_end<dec_current || inc_end <inc_current)
779  {
780  monoTriangulationRecGenOpt(topVertex, botVertex,
781  inc_chain, inc_current, inc_end,
782  dec_chain, dec_current, dec_end,
783  pStream);
784  return;
785  }
786  if(grid->get_v_value(gridV+1) >= topVertex[1])
787  {
788  monoTriangulationRecGenOpt(topVertex, botVertex,
789  inc_chain, inc_current, inc_end,
790  dec_chain, dec_current, dec_end,
791  pStream);
792  return;
793  }
794  Int i,j,k;
795  Real currentV = grid->get_v_value(gridV+1);
796  if(inc_chain->getVertex(inc_end)[1] <= currentV &&
797  dec_chain->getVertex(dec_end)[1] < currentV)
798  {
799  //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV,
800  //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV
801  for(i=inc_end; i >= inc_current; i--)
802  {
803  if(inc_chain->getVertex(i)[1] > currentV)
804  break;
805  }
806  i++;
807  for(j=dec_end; j >= dec_current; j--)
808  {
809  if(dec_chain->getVertex(j)[1] >= currentV)
810  break;
811  }
812  j++;
813  if(inc_chain->getVertex(i)[1] <= dec_chain->getVertex(j)[1])
814  {
815  //find the k so that dec_chain[k][1] < inc_chain[i][1]
816  for(k=j; k<=dec_end; k++)
817  {
818  if(dec_chain->getVertex(k)[1] < inc_chain->getVertex(i)[1])
819  break;
820  }
821  //we know that dec_chain[j][1] >= inc_chian[i][1]
822  //we know that dec_chain[k-1][1]>=inc_chain[i][1]
823  //we know that dec_chian[k][1] < inc_chain[i][1]
824  //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to
825  // inc_chain[i]
826  int l;
827  Real tempI = Real(j);
828  Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
829  for(l=j+1; l<= k-1; l++)
830  {
831  if(fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0])
832  <= tempMin)
833  {
834  tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]);
835  tempI = (Real)l;
836  }
837  }
838  //inc_chain[i] and dec_chain[tempI] are connected.
839  monoTriangulationRecGenOpt(dec_chain->getVertex((int)tempI),
840  botVertex,
841  inc_chain, i, inc_end,
842  dec_chain, (int)(tempI+1), dec_end,
843  pStream);
844  //recursively do the rest
846  gridV+1,
847  topVertex, inc_chain->getVertex(i),
848  inc_chain, inc_current, i-1,
849  dec_chain, dec_current, (int)tempI,
850  pStream);
851  }
852  else
853  {
854  //find the k so that inc_chain[k][1] <= dec_chain[j][1]
855  for(k=i; k<=inc_end; k++)
856  {
857  if(inc_chain->getVertex(k)[1] <= dec_chain->getVertex(j)[1])
858  break;
859  }
860  //we know that inc_chain[i] > dec_chain[j]
861  //we know that inc_chain[k-1][1] > dec_chain[j][1]
862  //we know that inc_chain[k][1] <= dec_chain[j][1]
863  //so we find l between [i,k-1] so that
864  //inc_chain[l][0] is the closet to dec_chain[j][0]
865  int tempI = i;
866  int l;
867  Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
868  for(l=i+1; l<=k-1; l++)
869  {
870  if(fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]) <= tempMin)
871  {
872  tempMin = (Real)fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]);
873  tempI = l;
874  }
875  }
876 
877  //inc_chain[tempI] and dec_chain[j] are connected
878 
879  monoTriangulationRecGenOpt(inc_chain->getVertex(tempI),
880  botVertex,
881  inc_chain, tempI+1, inc_end,
882  dec_chain, j, dec_end,
883  pStream);
884 
885  //recurvesily do the rest
886  sampleCompTopSimpleOpt(grid, gridV+1,
887  topVertex, dec_chain->getVertex(j),
888  inc_chain, inc_current, tempI,
889  dec_chain, dec_current, j-1,
890  pStream);
891  }
892  }
893  else //go to the next higher gridV
894  {
896  gridV+1,
897  topVertex, botVertex,
898  inc_chain, inc_current, inc_end,
899  dec_chain, dec_current, dec_end,
900  pStream);
901  }
902 }
903 
904 void sampleCompTopSimple(Real* topVertex,
905  vertexArray* leftChain,
906  Int leftStartIndex,
907  vertexArray* rightChain,
908  Int rightStartIndex,
909  gridBoundaryChain* leftGridChain,
910  gridBoundaryChain* rightGridChain,
911  Int gridIndex1,
912  Int up_leftCornerWhere,
913  Int up_leftCornerIndex,
914  Int up_rightCornerWhere,
915  Int up_rightCornerIndex,
916  primStream* pStream)
917 {
918  //the plan is to use monotriangulation algortihm.
919  Int i,k;
920  Real* ActualTop;
921  Real* ActualBot;
922  Int ActualLeftStart, ActualLeftEnd;
923  Int ActualRightStart, ActualRightEnd;
924 
925  //creat an array to store the points on the grid line
926  gridWrap* grid = leftGridChain->getGrid();
927  Int gridV = leftGridChain->getVlineIndex(gridIndex1);
928  Int gridLeftU = leftGridChain->getUlineIndex(gridIndex1);
929  Int gridRightU = rightGridChain->getUlineIndex(gridIndex1);
930 
931  Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1));
932  assert(gridPoints);
933 
934  for(k=0, i=gridRightU; i>= gridLeftU; i--, k++)
935  {
936  gridPoints[k][0] = grid->get_u_value(i);
937  gridPoints[k][1] = grid->get_v_value(gridV);
938  }
939 
940  if(up_leftCornerWhere != 2)
941  ActualRightStart = rightStartIndex;
942  else
943  ActualRightStart = up_leftCornerIndex+1; //up_leftCornerIndex will be the ActualTop
944 
945  if(up_rightCornerWhere != 2) //right corner is not on right chain
946  ActualRightEnd = rightStartIndex-1; //meaning that there is no actual rigth section
947  else
948  ActualRightEnd = up_rightCornerIndex;
949 
950  vertexArray ActualRightChain(max(0, ActualRightEnd-ActualRightStart+1) + gridRightU-gridLeftU+1);
951 
952  for(i=ActualRightStart; i<= ActualRightEnd; i++)
953  ActualRightChain.appendVertex(rightChain->getVertex(i));
954  for(i=0; i<gridRightU-gridLeftU+1; i++)
955  ActualRightChain.appendVertex(gridPoints[i]);
956 
957  //determine ActualLeftEnd
958  if(up_leftCornerWhere != 0)
959  ActualLeftEnd = leftStartIndex-1;
960  else
961  ActualLeftEnd = up_leftCornerIndex;
962 
963  if(up_rightCornerWhere != 0)
964  ActualLeftStart = leftStartIndex;
965  else
966  ActualLeftStart = up_rightCornerIndex+1; //up_rightCornerIndex will be the actual top
967 
968  if(up_leftCornerWhere == 0)
969  {
970  if(up_rightCornerWhere == 0)
971  ActualTop = leftChain->getVertex(up_rightCornerIndex);
972  else
973  ActualTop = topVertex;
974  }
975  else if(up_leftCornerWhere == 1)
976  ActualTop = topVertex;
977  else //up_leftCornerWhere == 2
978  ActualTop = rightChain->getVertex(up_leftCornerIndex);
979 
980  ActualBot = gridPoints[gridRightU - gridLeftU];
981 
982 
983 
984 
985  if(leftChain->getVertex(ActualLeftEnd)[1] == ActualBot[1])
986  {
987 /*
988  monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd),
989  leftChain,
990  ActualLeftStart, ActualLeftEnd-1,
991  &ActualRightChain,
992  0,
993  ActualRightChain.getNumElements()-1,
994  pStream);
995 */
996 
997  sampleCompTopSimpleOpt(grid, gridV,
998  ActualTop, leftChain->getVertex(ActualLeftEnd),
999  leftChain,
1000  ActualLeftStart, ActualLeftEnd-1,
1001  &ActualRightChain,
1002  0,
1003  ActualRightChain.getNumElements()-1,
1004  pStream);
1005 
1006  }
1007  else
1008  {
1009 /*
1010  monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain,
1011  ActualLeftStart, ActualLeftEnd,
1012  &ActualRightChain,
1013  0, ActualRightChain.getNumElements()-2, //the last is the bot.
1014  pStream);
1015 */
1016 
1017  sampleCompTopSimpleOpt(grid, gridV,
1018  ActualTop, ActualBot, leftChain,
1019  ActualLeftStart, ActualLeftEnd,
1020  &ActualRightChain,
1021  0, ActualRightChain.getNumElements()-2, //the last is the bot.
1022  pStream);
1023 
1024 
1025  }
1026 
1027  free(gridPoints);
1028 
1029 }
1030 
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
Int getVlineIndex(Int i)
Definition: gridWrap.h:119
#define max(a, b)
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)
void sampleTopLeftWithGridLine(Real *topVertex, vertexArray *leftChain, Int leftStart, Int leftEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
void appendVertex(Real *ptr)
#define free
Definition: debug_ros.c:5
#define assert(x)
Definition: debug.h:53
void sampleTopLeftWithGridLinePost(Real *topVertex, vertexArray *leftChain, Int leftStart, Int segIndexSmall, Int segIndexLarge, Int leftEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
void sampleTopRightWithGridLine(Real *topVertex, vertexArray *rightChain, Int rightStart, Int rightEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
Int findTopSeparator(vertexArray *leftChain, Int leftStartIndex, Int leftEndIndex, vertexArray *rightChain, Int rightStartIndex, Int rightEndIndex, Int &ret_sep_left, Int &ret_sep_right)
Real get_v_value(Int j)
Definition: gridWrap.h:83
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
Real * get_vertex(Int i)
Definition: gridWrap.h:127
Real get_u_value(Int i)
Definition: gridWrap.h:78
smooth NULL
Definition: ftsmooth.c:416
void findTopLeftSegment(vertexArray *leftChain, Int leftStart, Int leftEnd, Real u, Int &ret_index_small, Int &ret_index_large)
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 GLint GLint j
Definition: glfuncs.h:250
r l[0]
Definition: byte_order.h:167
void sampleCompTopSimple(Real *topVertex, vertexArray *leftChain, Int leftStartIndex, vertexArray *rightChain, Int rightStartIndex, gridBoundaryChain *leftGridChain, gridBoundaryChain *rightGridChain, Int gridIndex1, Int up_leftCornerWhere, Int up_leftCornerIndex, Int up_rightCornerWhere, Int up_rightCornerIndex, primStream *pStream)
Int getUlineIndex(Int i)
Definition: gridWrap.h:120
void sampleCompTop(Real *topVertex, vertexArray *leftChain, Int leftStartIndex, vertexArray *rightChain, Int rightStartIndex, gridBoundaryChain *leftGridChain, gridBoundaryChain *rightGridChain, Int gridIndex1, Int up_leftCornerWhere, Int up_leftCornerIndex, Int up_rightCornerWhere, Int up_rightCornerIndex, primStream *pStream)
gridWrap * getGrid()
Definition: gridWrap.h:128
Real get_v_value(Int i)
Definition: gridWrap.h:122
Real get_u_value(Int i)
Definition: gridWrap.h:121
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)
_Check_return_ _CRT_JIT_INTRINSIC double __cdecl fabs(_In_ double x)
void findTopRightSegment(vertexArray *rightChain, Int rightStart, Int rightEnd, Real u, Int &ret_index_small, Int &ret_index_large)
float Real
Definition: definitions.h:36
void stripOfFanRight(vertexArray *rightChain, Int largeIndex, Int smallIndex, gridWrap *grid, Int vlineIndex, Int ulineSmallIndex, Int ulineLargeIndex, primStream *pStream, Int gridLineUp)
void sampleTopRightWithGridLinePost(Real *topVertex, vertexArray *rightChain, Int rightStart, Int segIndexSmall, Int segIndexLarge, Int rightEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
#define malloc
Definition: debug_ros.c:4
Real Real2[2]
Definition: definitions.h:38
void monoTriangulation2(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)
Real * getVertex(Int i)
void outputFanWithPoint(Int v, Int uleft, Int uright, Real vert[2], primStream *pStream)
Definition: gridWrap.cc:137
int k
Definition: mpi.c:3369
int Int
Definition: definitions.h:37
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
static void sampleCompTopSimpleOpt(gridWrap *grid, Int gridV, 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 stripOfFanLeft(vertexArray *leftChain, Int largeIndex, Int smallIndex, gridWrap *grid, Int vlineIndex, Int ulineSmallIndex, Int ulineLargeIndex, primStream *pStream, Int gridLineUp)