ReactOS  r74227
monoChain.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 "gluos.h"
39 //#include <stdlib.h>
40 //#include <stdio.h>
41 //#include <GL/gl.h>
42 
43 //#include "glimports.h"
44 #include "zlassert.h"
45 
46 #include "monoChain.h"
47 #include "quicksort.h"
48 #include "searchTree.h"
49 #include "polyUtil.h"
50 
51 #ifndef max
52 #define max(a,b) ((a>b)? a:b)
53 #endif
54 #ifndef min
55 #define min(a,b) ((a>b)? b:a)
56 #endif
57 
58 extern Int isCusp(directedLine *v);
59 extern Int deleteRepeatDiagonals(Int num_diagonals, directedLine** diagonal_vertices, directedLine** new_vertices);
60 
61 //for debug purpose only
62 #if 0 // UNUSED
63 static void drawDiagonals(Int num_diagonals, directedLine** diagonal_vertices)
64 {
65  Int i;
66  for(i=0; i<num_diagonals; i++)
67  {
69  glVertex2fv(diagonal_vertices[2*i]->head());
70  glVertex2fv(diagonal_vertices[2*i+1]->head());
71  glEnd();
72  }
73 }
74 #endif
75 
76 /*given (x_1, y_1) and (x_2, y_2), and y
77  *return x such that (x,y) is on the line
78  */
80 {
81  return ((y2==y1)? (x1+x2)*0.5 : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
82 }
83 
84 //compare the heads of the two chains
85 static int compChainHeadInY(monoChain* mc1, monoChain* mc2)
86 {
87  return compV2InY(mc1->getHead()->head(), mc2->getHead()->head());
88 }
89 
91 {
92  chainHead = cHead;
93  chainTail = cTail;
94  next = this;
95  prev = this;
96 
97  nextPolygon = NULL;
98 
99  //compute bounding box
101  minX = maxX = chainTail->head()[0];
102  minY = maxY = chainTail->head()[1];
103 
104  for(temp=chainHead; temp!=cTail; temp = temp->getNext())
105  {
106  if(temp->head()[0] < minX)
107  minX = temp->head()[0];
108  if(temp->head()[0] > maxX)
109  maxX = temp->head()[0];
110 
111  if(temp->head()[1] < minY)
112  minY = temp->head()[1];
113  if(temp->head()[1] > maxY)
114  maxY = temp->head()[1];
115  }
116 
117  //check whether the chain is increasing or decreasing
118  if(chainHead->compInY(chainTail) <0)
119  isIncrease = 1;
120  else
121  isIncrease = 0;
122 
123  //initilize currrent, this is used for accelerating search
124  if(isIncrease)
125  current = chainHead;
126  else
127  current = chainTail;
128 
129  isKey = 0;
130  keyY = 0;
131 }
132 
133 //insert a new line between prev and this
135 {
136  nc->next = this;
137  nc->prev = prev;
138  prev->next = nc;
139  prev = nc;
140 }
141 
143 {
144  monoChain *temp, *tempNext;
145  prev->next = NULL;
146  for(temp=this; temp != NULL; temp = tempNext)
147  {
148  tempNext = temp->next;
149  delete temp;
150  }
151 }
152 
154 {
155  monoChain *temp, *tempNext;
156  for(temp=this; temp != NULL; temp = tempNext)
157  {
158  tempNext = temp->nextPolygon;
159  temp->deleteLoop();
160  }
161 }
162 
164 {
165  monoChain *temp;
166  array[index++] = this;
167  for(temp = next; temp != this; temp = temp->next)
168  {
169  array[index++] = temp;
170  }
171  return index;
172 }
173 
175 {
176  num_chains = numChainsAllLoops();
177  monoChain **ret = (monoChain**) malloc(sizeof(monoChain*) * num_chains);
178  assert(ret);
179  monoChain *temp;
180  Int index = 0;
181  for(temp = this; temp != NULL; temp=temp->nextPolygon){
182  index = temp->toArraySingleLoop(ret, index);
183  }
184  return ret;
185 }
186 
188 {
189  Int ret=0;
190  monoChain* temp;
191  if(next == this) return 1;
192  ret = 1;
193  for(temp=next; temp != this; temp = temp->next)
194  ret++;
195  return ret;
196 }
197 
199 {
200  Int ret=0;
201  monoChain *temp;
202  for(temp =this; temp != NULL; temp = temp->nextPolygon)
203  ret += temp->numChainsSingleLoop();
204  return ret;
205 }
206 
207 //update 'current'
209 {
211  if(isIncrease)
212  {
213  for(temp= current; temp != chainTail; temp = temp->getNext())
214  {
215  if(temp->head()[1] > y)
216  break;
217  }
218  current = temp->getPrev();
219  }
220  else
221  {
222  for(temp = current; temp != chainHead; temp = temp->getPrev())
223  {
224  if(temp->head()[1] > y)
225  break;
226  }
227  current = temp->getNext();
228  }
229  return intersectHoriz(current->head()[0], current->head()[1], current->tail()[0], current->tail()[1], y);
230 }
231 
233 {
235  monoChain *ret=NULL;
236 
237  //find the first cusp
238  directedLine *prevCusp=NULL;
239  directedLine *firstCusp;
240 
241  if(isCusp(loop))
242  prevCusp = loop;
243  else
244  {
245  for(temp = loop->getNext(); temp != loop; temp = temp->getNext())
246  if(isCusp(temp))
247  break;
248  prevCusp = temp;
249  }
250  firstCusp = prevCusp;
251 //printf("first cusp is (%f,%f), (%f,%f), (%f,%f)\n", prevCusp->getPrev()->head()[0], prevCusp->getPrev()->head()[1], prevCusp->head()[0], prevCusp->head()[1], prevCusp->tail()[0], prevCusp->tail()[1]);
252 
253  for(temp = prevCusp->getNext(); temp != loop; temp = temp->getNext())
254  {
255  if(isCusp(temp))
256  {
257 //printf("the cusp is (%f,%f), (%f,%f), (%f,%f)\n", temp->getPrev()->head()[0], temp->getPrev()->head()[1], temp->head()[0], temp->head()[1], temp->tail()[0], temp->tail()[1]);
258  if(ret == NULL)
259  {
260  ret = new monoChain(prevCusp, temp);
261  }
262  else
263  ret->insert(new monoChain(prevCusp, temp));
264  prevCusp = temp;
265  }
266  }
267  assert(ret);
268  ret->insert(new monoChain(prevCusp, firstCusp));
269 
270  return ret;
271 }
272 
274 {
276  monoChain* mc;
277  monoChain* mcEnd;
279  mcEnd = mc;
280  for(temp = list->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
281  {
283  mcEnd->setNextPolygon(newLoop);
284  mcEnd = newLoop;
285  }
286  return mc;
287 }
288 
289 /*compare two edges of a polygon.
290  *edge A < edge B if there is a horizontal line so that the intersection
291  *with A is to the left of the intersection with B.
292  *This function is used in sweepY for the dynamic search tree insertion to
293  *order the edges.
294  * Implementation: (x_1,y_1) and (x_2, y_2)
295  */
297 {
298  Real* head1 = e1->head();
299  Real* tail1 = e1->tail();
300  Real* head2 = e2->head();
301  Real* tail2 = e2->tail();
302 /*
303  Real h10 = head1[0];
304  Real h11 = head1[1];
305  Real t10 = tail1[0];
306  Real t11 = tail1[1];
307  Real h20 = head2[0];
308  Real h21 = head2[1];
309  Real t20 = tail2[0];
310  Real t21 = tail2[1];
311 */
312  Real e1_Ymax, e1_Ymin, e2_Ymax, e2_Ymin;
313 /*
314  if(h11>t11) {
315  e1_Ymax= h11;
316  e1_Ymin= t11;
317  }
318  else{
319  e1_Ymax = t11;
320  e1_Ymin = h11;
321  }
322 
323  if(h21>t21) {
324  e2_Ymax= h21;
325  e2_Ymin= t21;
326  }
327  else{
328  e2_Ymax = t21;
329  e2_Ymin = h21;
330  }
331 */
332 
333  if(head1[1]>tail1[1]) {
334  e1_Ymax= head1[1];
335  e1_Ymin= tail1[1];
336  }
337  else{
338  e1_Ymax = tail1[1];
339  e1_Ymin = head1[1];
340  }
341 
342  if(head2[1]>tail2[1]) {
343  e2_Ymax= head2[1];
344  e2_Ymin= tail2[1];
345  }
346  else{
347  e2_Ymax = tail2[1];
348  e2_Ymin = head2[1];
349  }
350 
351 
352  /*Real e1_Ymax = max(head1[1], tail1[1]);*/ /*max(e1->head()[1], e1->tail()[1]);*/
353  /*Real e1_Ymin = min(head1[1], tail1[1]);*/ /*min(e1->head()[1], e1->tail()[1]);*/
354  /*Real e2_Ymax = max(head2[1], tail2[1]);*/ /*max(e2->head()[1], e2->tail()[1]);*/
355  /*Real e2_Ymin = min(head2[1], tail2[1]);*/ /*min(e2->head()[1], e2->tail()[1]);*/
356 
357  Real Ymax = min(e1_Ymax, e2_Ymax);
358  Real Ymin = max(e1_Ymin, e2_Ymin);
359 
360  Real y = 0.5*(Ymax + Ymin);
361 
362 /* Real x1 = intersectHoriz(e1->head()[0], e1->head()[1], e1->tail()[0], e1->tail()[1], y);
363  Real x2 = intersectHoriz(e2->head()[0], e2->head()[1], e2->tail()[0], e2->tail()[1], y);
364 */
365 /*
366  Real x1 = intersectHoriz(h10, h11, t10, t11, y);
367  Real x2 = intersectHoriz(h20, h21, t20, t21, y);
368 */
369  Real x1 = intersectHoriz(head1[0], head1[1], tail1[0], tail1[1], y);
370  Real x2 = intersectHoriz(head2[0], head2[1], tail2[0], tail2[1], y);
371 
372  if(x1<= x2) return -1;
373  else return 1;
374 }
375 
377 {
378  Real y;
379  assert(mc1->isKey || mc2->isKey);
380  if(mc1->isKey)
381  y = mc1->keyY;
382  else
383  y = mc2->keyY;
384  directedLine *d1 = mc1->find(y);
385  directedLine *d2 = mc2->find(y);
386  mc2->find(y);
387 // Real x1 = mc1->chainIntersectHoriz(y);
388 // Real x2 = mc2->chainIntersectHoriz(y);
389  return compEdges(d1, d2);
390 }
391 
392 //this function modifies current for efficiency
394 {
395  directedLine *ret;
397  assert(current->head()[1] <= y);
398  if(isIncrease)
399  {
400  assert(chainTail->head()[1] >=y);
401  for(temp=current; temp!=chainTail; temp = temp->getNext())
402  {
403  if(temp->head()[1] > y)
404  break;
405  }
406  current = temp->getPrev();
407  ret = current;
408  }
409  else
410  {
411  for(temp=current; temp != chainHead; temp = temp->getPrev())
412  {
413  if(temp->head()[1] > y)
414  break;
415  }
416  current = temp->getNext();
417  ret = temp;
418  }
419  return ret;
420 }
421 
423 {
425  for(temp = chainHead; temp != chainTail; temp = temp->getNext())
426  {
427  printf("(%f,%f) ", temp->head()[0], temp->head()[1]);
428  }
429  printf("(%f,%f) \n", chainTail->head()[0], chainTail->head()[1]);
430 }
431 
433 {
434  monoChain* temp;
435  this->printOneChain();
436  for(temp = next; temp != this; temp = temp->next)
437  {
438  temp->printOneChain();
439  }
440  printf("\n");
441 }
442 
444 {
445  monoChain* temp;
446  for(temp=this; temp != NULL; temp = temp->nextPolygon)
447  temp->printChainLoop();
448 }
449 
450 //return 1 if error occures
451 Int MC_sweepY(Int nVertices, monoChain** sortedVertices, sweepRange** ret_ranges)
452 {
453  Int i;
454  Real keyY;
455  Int errOccur=0;
456 //printf("enter MC_sweepY\n");
457 //printf("nVertices=%i\n", nVertices);
458  /*for each vertex in the sorted list, update the binary search tree.
459  *and store the range information for each vertex.
460  */
461  treeNode* searchTree = NULL;
462 //printf("nVertices=%i\n", nVertices);
463  for(i=0; i<nVertices; i++)
464  {
465  monoChain* vert = sortedVertices[i];
466  keyY = vert->getHead()->head()[1]; //the sweep line
467  directedLine *dline = vert->getHead();
468  directedLine *dlinePrev = dline->getPrev();
469  if(isBelow(dline, dline) && isBelow(dline, dlinePrev))
470  {
471 //printf("case 1\n");
472  //this<v and prev < v
473  //delete both edges
474  vert->isKey = 1;
475  vert->keyY = keyY;
476  treeNode* thisNode = TreeNodeFind(searchTree, vert, (Int (*) (void *, void *))compChains);
477  vert->isKey = 0;
478 
479  vert->getPrev()->isKey = 1;
480  vert->getPrev()->keyY = keyY;
481  treeNode* prevNode = TreeNodeFind(searchTree, vert->getPrev(), (Int (*) (void *, void *))compChains);
482  vert->getPrev()->isKey = 0;
483 
484  if(cuspType(dline) == 1)//interior cusp
485  {
486 
487  treeNode* leftEdge = TreeNodePredecessor(prevNode);
488  treeNode* rightEdge = TreeNodeSuccessor(thisNode);
489  if(leftEdge == NULL || rightEdge == NULL)
490  {
491  errOccur = 1;
492  goto JUMP_HERE;
493  }
494 
495  directedLine* leftEdgeDline = ((monoChain* ) leftEdge->key)->find(keyY);
496 
497 
498 
499  directedLine* rightEdgeDline = ((monoChain* ) rightEdge->key)->find(keyY);
500 
501  ret_ranges[i] = sweepRangeMake(leftEdgeDline, 1, rightEdgeDline, 1);
502  }
503  else /*exterior cusp*/
504  {
505  ret_ranges[i] = sweepRangeMake( dline, 1, dlinePrev, 1);
506  }
507 
508  searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
509  searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
510 
511  }
512  else if(isAbove(dline, dline) && isAbove(dline, dlinePrev))
513  {
514 //printf("case 2\n");
515  //insert both edges
516  treeNode* thisNode = TreeNodeMake(vert);
517  treeNode* prevNode = TreeNodeMake(vert->getPrev());
518 
519  vert->isKey = 1;
520  vert->keyY = keyY;
521  searchTree = TreeNodeInsert(searchTree, thisNode, (Int (*) (void *, void *))compChains);
522  vert->isKey = 0;
523 
524  vert->getPrev()->isKey = 1;
525  vert->getPrev()->keyY = keyY;
526  searchTree = TreeNodeInsert(searchTree, prevNode, (Int (*) (void *, void *))compChains);
527  vert->getPrev()->isKey = 0;
528 
529  if(cuspType(dline) == 1) //interior cusp
530  {
531 //printf("cuspType is 1\n");
532  treeNode* leftEdge = TreeNodePredecessor(thisNode);
533  treeNode* rightEdge = TreeNodeSuccessor(prevNode);
534  if(leftEdge == NULL || rightEdge == NULL)
535  {
536  errOccur = 1;
537  goto JUMP_HERE;
538  }
539 //printf("leftEdge is %i, rightEdge is %i\n", leftEdge, rightEdge);
540  directedLine* leftEdgeDline = ((monoChain*) leftEdge->key)->find(keyY);
541  directedLine* rightEdgeDline = ((monoChain*) rightEdge->key)->find(keyY);
542  ret_ranges[i] = sweepRangeMake( leftEdgeDline, 1, rightEdgeDline, 1);
543  }
544  else //exterior cusp
545  {
546 //printf("cuspType is not 1\n");
547  ret_ranges[i] = sweepRangeMake(dlinePrev, 1, dline, 1);
548  }
549  }
550  else
551  {
552 //printf("%i,%i\n", isAbove(dline, dline), isAbove(dline, dlinePrev));
553  errOccur = 1;
554  goto JUMP_HERE;
555 
556  fprintf(stderr, "error in MC_sweepY\n");
557  exit(1);
558  }
559  }
560 
561  JUMP_HERE:
562  //finally clean up space: delete the search tree
563  TreeNodeDeleteWholeTree(searchTree);
564  return errOccur;
565 }
566 
567 void MC_findDiagonals(Int total_num_edges, monoChain** sortedVertices,
568  sweepRange** ranges, Int& num_diagonals,
569  directedLine** diagonal_vertices)
570 {
571  Int i,j,k;
572  k=0;
573  //reset 'current' of all the monoChains
574  for(i=0; i<total_num_edges; i++)
575  sortedVertices[i]->resetCurrent();
576 
577  for(i=0; i<total_num_edges; i++)
578  {
579  directedLine* vert = sortedVertices[i]->getHead();
580  directedLine* thisEdge = vert;
581  directedLine* prevEdge = vert->getPrev();
582  if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
583  {
584  //this is an upward interior cusp
585  diagonal_vertices[k++] = vert;
586 
587  directedLine* leftEdge = ranges[i]->left;
588  directedLine* rightEdge = ranges[i]->right;
589 
590  directedLine* leftVert = leftEdge;
591  directedLine* rightVert = rightEdge->getNext();
592  assert(leftVert->head()[1] >= vert->head()[1]);
593  assert(rightVert->head()[1] >= vert->head()[1]);
594  directedLine* minVert = (leftVert->head()[1] <= rightVert->head()[1])?leftVert:rightVert;
595  Int found = 0;
596  for(j=i+1; j<total_num_edges; j++)
597  {
598  if(sortedVertices[j]->getHead()->head()[1] > minVert->head()[1])
599  break;
600 
601  if(sweepRangeEqual(ranges[i], ranges[j]))
602  {
603  found = 1;
604  break;
605  }
606  }
607 
608  if(found)
609  diagonal_vertices[k++] = sortedVertices[j]->getHead();
610  else
611  diagonal_vertices[k++] = minVert;
612  }
613  else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
614  {
615  //downward interior cusp
616  diagonal_vertices[k++] = vert;
617  directedLine* leftEdge = ranges[i]->left;
618  directedLine* rightEdge = ranges[i]->right;
619  directedLine* leftVert = leftEdge->getNext();
620  directedLine* rightVert = rightEdge;
621  assert(leftVert->head()[1] <= vert->head()[1]);
622  assert(rightVert->head()[1] <= vert->head()[1]);
623  directedLine* maxVert = (leftVert->head()[1] > rightVert->head()[1])? leftVert:rightVert;
624  Int found=0;
625  for(j=i-1; j>=0; j--)
626  {
627  if(sortedVertices[j]->getHead()->head()[1] < maxVert->head()[1])
628  break;
629  if(sweepRangeEqual(ranges[i], ranges[j]))
630  {
631  found = 1;
632  break;
633  }
634  }
635  if(found)
636  diagonal_vertices[k++] = sortedVertices[j]->getHead();
637  else
638  diagonal_vertices[k++] = maxVert;
639  }
640  }
641  num_diagonals = k/2;
642 }
643 
644 
645 
646 
647 directedLine* MC_partitionY(directedLine *polygons, sampledLine **retSampledLines)
648 {
649 //printf("enter mc_partitionY\n");
650  Int total_num_chains = 0;
652  monoChain** array = loopList->toArrayAllLoops(total_num_chains);
653 
654  if(total_num_chains<=2) //there is just one single monotone polygon
655  {
656  loopList->deleteLoopList();
657  free(array);
658  *retSampledLines = NULL;
659  return polygons;
660  }
661 
662 //loopList->printAllLoops();
663 //printf("total_num_chains=%i\n", total_num_chains);
664  quicksort( (void**)array, 0, total_num_chains-1, (Int (*)(void*, void*))compChainHeadInY);
665 //printf("after quicksort\n");
666 
667  sweepRange** ranges = (sweepRange**)malloc(sizeof(sweepRange*) * (total_num_chains));
668  assert(ranges);
669 
670  if(MC_sweepY(total_num_chains, array, ranges))
671  {
672  loopList->deleteLoopList();
673  free(array);
674  *retSampledLines = NULL;
675  return NULL;
676  }
677 //printf("after MC_sweepY\n");
678 
679 
680  Int num_diagonals;
681  /*number diagonals is < total_num_edges*total_num_edges*/
682  directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_chains*2/*total_num_edges*/);
683  assert(diagonal_vertices);
684 
685 //printf("before call MC_findDiagonales\n");
686 
687  MC_findDiagonals(total_num_chains, array, ranges, num_diagonals, diagonal_vertices);
688 //printf("after call MC_findDia, num_diagnla=%i\n", num_diagonals);
689 
690  directedLine* ret_polygons = polygons;
691  sampledLine* newSampledLines = NULL;
692  Int i,k;
693 
694  num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
695 
696 
697 
698 //drawDiagonals(num_diagonals, diagonal_vertices);
699 //printf("diagoanls are \n");
700 //for(i=0; i<num_diagonals; i++)
701 // {
702 // printf("(%f,%f)\n", diagonal_vertices[2*i]->head()[0], diagonal_vertices[2*i]->head()[1]);
703 // printf("**(%f,%f)\n", diagonal_vertices[2*i+1]->head()[0], diagonal_vertices[2*i+1]->head()[1]);
704 // }
705 
706  Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals);
707  for(i=0; i<num_diagonals; i++)
708  removedDiagonals[i] = 0;
709 // printf("first pass\n");
710 
711 
712  for(i=0,k=0; i<num_diagonals; i++,k+=2)
713  {
714 
715 
716  directedLine* v1=diagonal_vertices[k];
717  directedLine* v2=diagonal_vertices[k+1];
718  directedLine* ret_p1;
719  directedLine* ret_p2;
720 
721  /*we ahve to determine whether v1 and v2 belong to the same polygon before
722  *their structure are modified by connectDiagonal().
723  */
724 /*
725  directedLine *root1 = v1->findRoot();
726  directedLine *root2 = v2->findRoot();
727  assert(root1);
728  assert(root2);
729 */
730 
731 directedLine* root1 = v1->rootLinkFindRoot();
732 directedLine* root2 = v2->rootLinkFindRoot();
733 
734  if(root1 != root2)
735  {
736 
737  removedDiagonals[i] = 1;
738  sampledLine* generatedLine;
739 
740 
741 
742  v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
743 
744 
745 
746  newSampledLines = generatedLine->insert(newSampledLines);
747 /*
748  ret_polygons = ret_polygons->cutoffPolygon(root1);
749 
750  ret_polygons = ret_polygons->cutoffPolygon(root2);
751  ret_polygons = ret_p1->insertPolygon(ret_polygons);
752 root1->rootLinkSet(ret_p1);
753 root2->rootLinkSet(ret_p1);
754 ret_p1->rootLinkSet(NULL);
755 ret_p2->rootLinkSet(ret_p1);
756 */
757  ret_polygons = ret_polygons->cutoffPolygon(root2);
758 
759 
760 
761 root2->rootLinkSet(root1);
762 ret_p1->rootLinkSet(root1);
763 ret_p2->rootLinkSet(root1);
764 
765  /*now that we have connected the diagonal v1 and v2,
766  *we have to check those unprocessed diagonals which
767  *have v1 or v2 as an end point. Notice that the head of v1
768  *has the same coodinates as the head of v2->prev, and the head of
769  *v2 has the same coordinate as the head of v1->prev.
770  *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid
771  *diagonal, then x should be on the left hand side of the directed line: *v1->prev->head -- v1->head -- v1->tail. Otherwise, (v1,x) should be
772  *replaced by (v2->prev, x), that is, x is on the left of
773  * v2->prev->prev->head, v2->prev->head, v2->prev->tail.
774  */
775  Int ii, kk;
776  for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2)
777  if( removedDiagonals[ii]==0)
778  {
779  directedLine* d1=diagonal_vertices[kk];
780  directedLine* d2=diagonal_vertices[kk+1];
781  /*check d1, and replace diagonal_vertices[kk] if necessary*/
782  if(d1 == v1) {
783  /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/
784  if(! pointLeft2Lines(v1->getPrev()->head(),
785  v1->head(), v1->tail(), d2->head()))
786  {
787 /*
788  assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
789  v2->getPrev()->head(),
790  v2->getPrev()->tail(), d2->head()));
791 */
792  diagonal_vertices[kk] = v2->getPrev();
793  }
794  }
795  if(d1 == v2) {
796  /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/
797  if(! pointLeft2Lines(v2->getPrev()->head(),
798  v2->head(), v2->tail(), d2->head()))
799  {
800 /*
801  assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
802  v1->getPrev()->head(),
803  v1->getPrev()->tail(), d2->head()));
804 */
805  diagonal_vertices[kk] = v1->getPrev();
806  }
807  }
808  /*check d2 and replace diagonal_vertices[k+1] if necessary*/
809  if(d2 == v1) {
810  /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/
811  if(! pointLeft2Lines(v1->getPrev()->head(),
812  v1->head(), v1->tail(), d1->head()))
813  {
814 /* assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
815  v2->getPrev()->head(),
816  v2->getPrev()->tail(), d1->head()));
817 */
818  diagonal_vertices[kk+1] = v2->getPrev();
819  }
820  }
821  if(d2 == v2) {
822  /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/
823  if(! pointLeft2Lines(v2->getPrev()->head(),
824  v2->head(), v2->tail(), d1->head()))
825  {
826 /* assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
827  v1->getPrev()->head(),
828  v1->getPrev()->tail(), d1->head()));
829 */
830  diagonal_vertices[kk+1] = v1->getPrev();
831  }
832  }
833  }
834 }/*end if (root1 not equal to root 2)*/
835 }
836 
837  /*second pass, now all diagoals should belong to the same polygon*/
838 //printf("second pass: \n");
839 
840 // for(i=0; i<num_diagonals; i++)
841 // printf("%i ", removedDiagonals[i]);
842 
843 
844  for(i=0,k=0; i<num_diagonals; i++, k += 2)
845  if(removedDiagonals[i] == 0)
846  {
847 
848 
849  directedLine* v1=diagonal_vertices[k];
850  directedLine* v2=diagonal_vertices[k+1];
851 
852 
853 
854  directedLine* ret_p1;
855  directedLine* ret_p2;
856 
857  /*we ahve to determine whether v1 and v2 belong to the same polygon before
858  *their structure are modified by connectDiagonal().
859  */
860  directedLine *root1 = v1->findRoot();
861 /*
862  directedLine *root2 = v2->findRoot();
863 
864 
865 
866  assert(root1);
867  assert(root2);
868  assert(root1 == root2);
869  */
870  sampledLine* generatedLine;
871 
872 
873 
874  v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
875  newSampledLines = generatedLine->insert(newSampledLines);
876 
877  ret_polygons = ret_polygons->cutoffPolygon(root1);
878 
879  ret_polygons = ret_p1->insertPolygon(ret_polygons);
880 
881  ret_polygons = ret_p2->insertPolygon(ret_polygons);
882 
883 
884 
885  for(Int j=i+1; j<num_diagonals; j++)
886  {
887  if(removedDiagonals[j] ==0)
888  {
889 
890  directedLine* temp1=diagonal_vertices[2*j];
891  directedLine* temp2=diagonal_vertices[2*j+1];
892  if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2)
893  if(! temp1->samePolygon(temp1, temp2))
894  {
895  /*if temp1 and temp2 are in different polygons,
896  *then one of them must be v1 or v2.
897  */
898 
899 
900 
901  assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2);
902  if(temp1==v1)
903  {
904  diagonal_vertices[2*j] = v2->getPrev();
905  }
906  if(temp2==v1)
907  {
908  diagonal_vertices[2*j+1] = v2->getPrev();
909  }
910  if(temp1==v2)
911  {
912  diagonal_vertices[2*j] = v1->getPrev();
913  }
914  if(temp2==v2)
915  {
916  diagonal_vertices[2*j+1] = v1->getPrev();
917  }
918  }
919  }
920  }
921 
922  }
923 
924 
925  //clean up
926  loopList->deleteLoopList();
927  free(array);
928  free(ranges);
929  free(diagonal_vertices);
930  free(removedDiagonals);
931 
932  *retSampledLines = newSampledLines;
933  return ret_polygons;
934 }
935 
936 
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG y1
Definition: winddi.h:3706
treeNode * TreeNodeMake(void *key)
Definition: searchTree.cc:46
monoChain * getPrev()
Definition: monoChain.h:65
directedLine * right
Definition: partitionY.h:73
void connectDiagonal(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, sampledLine **generatedLine, directedLine *list)
void deleteLoop()
Definition: monoChain.cc:142
GLenum GLclampf GLint GLenum GLuint GLenum GLenum GLsizei GLenum const GLvoid GLfloat GLfloat GLfloat GLfloat GLclampd GLint 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 GLboolean GLboolean GLboolean GLint GLenum GLsizei const GLvoid GLenum GLint GLenum GLint GLint GLsizei GLint GLenum GLint GLint GLint GLint GLsizei GLenum GLsizei const GLuint GLboolean GLenum GLenum GLint GLsizei GLenum GLsizei GLenum const GLvoid GLboolean const GLboolean GLenum const GLdouble const GLfloat const GLdouble const GLfloat GLenum GLint GLint GLint GLint GLint GLint j
Definition: glfuncs.h:98
monoChain * next
Definition: monoChain.h:44
void rootLinkSet(directedLine *r)
Definition: directedLine.h:155
Int numChainsAllLoops()
Definition: monoChain.cc:198
Real * head()
VARIANT loop
void GLAPIENTRY glEnd(void)
Definition: apistubs.c:2246
struct outqueuenode * head
Definition: adnsresfilter.c:66
static int compChainHeadInY(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:85
monoChain * directedLineLoopToMonoChainLoop(directedLine *loop)
Definition: monoChain.cc:232
Real minY
Definition: monoChain.h:50
#define free
Definition: debug_ros.c:5
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
Int isBelow(directedLine *v, directedLine *e)
Definition: partitionY.cc:73
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: monoChain.cc:296
void quicksort(void *v[], int left, int right, int(*comp)(void *, void *))
Definition: quicksort.cc:62
#define assert(x)
Definition: debug.h:53
void printChainLoop()
Definition: monoChain.cc:432
sampledLine * insert(sampledLine *nline)
Definition: sampledLine.cc:53
monoChain * prev
Definition: monoChain.h:45
Real keyY
Definition: monoChain.h:83
void GLAPIENTRY glBegin(GLenum mode)
Definition: apistubs.c:2066
Int samePolygon(directedLine *v1, directedLine *v2)
Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
Definition: monoChain.cc:79
directedLine * getPrev()
Definition: directedLine.h:73
Int isIncrease
Definition: monoChain.h:51
Int compV2InY(Real A[2], Real B[2])
Int isKey
Definition: monoChain.h:82
GLenum GLclampf GLint i
Definition: glfuncs.h:14
directedLine * insertPolygon(directedLine *newpolygon)
monoChain * directedLineLoopListToMonoChainLoopList(directedLine *list)
Definition: monoChain.cc:273
directedLine * current
Definition: monoChain.h:55
directedLine * getNext()
Definition: directedLine.h:74
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
Real maxX
Definition: monoChain.h:50
#define GL_LINE
Definition: gl.h:266
Real maxY
Definition: monoChain.h:50
sweepRange * sweepRangeMake(directedLine *left, Int leftType, directedLine *right, Int rightType)
Definition: partitionY.cc:150
Int numChainsSingleLoop()
Definition: monoChain.cc:187
smooth NULL
Definition: ftsmooth.c:464
void MC_findDiagonals(Int total_num_edges, monoChain **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
Definition: monoChain.cc:567
Int compInY(directedLine *nl)
GLuint index
Definition: glext.h:6031
void printAllLoops()
Definition: monoChain.cc:443
#define max(a, b)
Definition: monoChain.cc:52
monoChain * nextPolygon
Definition: monoChain.h:46
directedLine * rootLinkFindRoot()
void * key
Definition: searchTree.h:37
treeNode * TreeNodePredecessor(treeNode *node)
Definition: searchTree.cc:266
directedLine * chainTail
Definition: monoChain.h:43
void deleteLoopList()
Definition: monoChain.cc:153
Int compChains(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:376
directedLine * chainHead
Definition: monoChain.h:42
Real chainIntersectHoriz(Real y)
Definition: monoChain.cc:208
int ret
#define exit(n)
Definition: config.h:212
#define index(s, c)
Definition: various.h:29
Int cuspType(directedLine *v)
Definition: partitionY.cc:142
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
Int MC_sweepY(Int nVertices, monoChain **sortedVertices, sweepRange **ret_ranges)
Definition: monoChain.cc:451
Int isAbove(directedLine *v, directedLine *e)
Definition: partitionY.cc:89
directedLine * find(Real y)
Definition: monoChain.cc:393
Definition: _list.h:228
static stack_node_t temp
Definition: rpn.c:18
Int isCusp(directedLine *v)
Definition: partitionY.cc:100
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG _In_ LONG y2
Definition: winddi.h:3706
Int deleteRepeatDiagonals(Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
Definition: partitionY.cc:386
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
Real * tail()
Real minX
Definition: monoChain.h:50
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
Int pointLeft2Lines(Real A[2], Real B[2], Real C[2], Real P[2])
Definition: polyUtil.cc:78
const GLdouble * v
Definition: gl.h:2040
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
directedLine * left
Definition: partitionY.h:71
Int toArraySingleLoop(monoChain **array, Int index)
Definition: monoChain.cc:163
directedLine * getHead()
Definition: monoChain.h:66
#define min(a, b)
Definition: monoChain.cc:55
monoChain(directedLine *cHead, directedLine *cTail)
Definition: monoChain.cc:90
float Real
Definition: definitions.h:36
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG x2
Definition: winddi.h:3706
void insert(monoChain *nc)
Definition: monoChain.cc:134
FILE * stderr
directedLine * cutoffPolygon(directedLine *p)
#define malloc
Definition: debug_ros.c:4
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62
void setNextPolygon(monoChain *np)
Definition: monoChain.h:63
directedLine * findRoot()
INT INT y
Definition: msvc.h:62
GLfloat GLfloat v1
Definition: glext.h:6062
Int sweepRangeEqual(sweepRange *src1, sweepRange *src2)
Definition: partitionY.cc:167
int k
Definition: mpi.c:3369
treeNode * TreeNodeInsert(treeNode *root, treeNode *newnode, int(*compkey)(void *, void *))
Definition: searchTree.cc:106
monoChain ** toArrayAllLoops(Int &num_chains)
Definition: monoChain.cc:174
directedLine * getNextPolygon()
Definition: directedLine.h:75
void GLAPIENTRY glVertex2fv(const GLfloat *v)
Definition: apistubs.c:2676
#define printf
Definition: config.h:213
void printOneChain()
Definition: monoChain.cc:422
int Int
Definition: definitions.h:37
directedLine * MC_partitionY(directedLine *polygons, sampledLine **retSampledLines)
Definition: monoChain.cc:647