ReactOS  0.4.13-dev-99-g7e18b6d
subdivider.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  * subdivider.cxx
37  *
38  */
39 
40 //#include "glimports.h"
41 //#include "myassert.h"
42 //#include "mystdio.h"
43 #include "subdivider.h"
44 //#include "arc.h"
45 #include "bezierarc.h"
46 //#include "bin.h"
47 #include "renderhints.h"
48 #include "backend.h"
49 //#include "mapdesc.h"
50 #include "quilt.h"
51 #include "patchlist.h"
52 //#include "patch.h"
53 //#include "nurbsconsts.h"
54 //#include "trimvertpool.h"
55 #include "simplemath.h"
56 
57 #include "polyUtil.h" //for function area()
58 
59 //#define PARTITION_TEST
60 #ifdef PARTITION_TEST
61 #include "partitionY.h"
62 #include "monoTriangulation.h"
63 #include "dataTransform.h"
64 #include "monoChain.h"
65 
66 #endif
67 
68 
69 #define OPTIMIZE_UNTRIMED_CASE
70 
71 
72 Bin*
74 {
75  Bin* ret = new Bin();
76  REAL smin = from[0];
77  REAL smax = to[0];
78  REAL tmin = from[1];
79  REAL tmax = to[1];
80 
81  pjarc = 0;
82 
83  Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
84  arctessellator.bezier( jarc, smin, smax, tmin, tmin );
85  ret->addarc( jarc );
86  pjarc = jarc->append( pjarc );
87 
88  jarc = new(arcpool) Arc( arc_right, 0 );
89  arctessellator.bezier( jarc, smax, smax, tmin, tmax );
90  ret->addarc( jarc );
91  pjarc = jarc->append( pjarc );
92 
93  jarc = new(arcpool) Arc( arc_top, 0 );
94  arctessellator.bezier( jarc, smax, smin, tmax, tmax );
95  ret->addarc( jarc );
96  pjarc = jarc->append( pjarc );
97 
98  jarc = new(arcpool) Arc( arc_left, 0 );
99  arctessellator.bezier( jarc, smin, smin, tmax, tmin );
100  ret->addarc( jarc );
101  jarc->append( pjarc );
102 
103  assert( jarc->check() != 0 );
104  return ret;
105 }
106 
107 /*---------------------------------------------------------------------------
108  * Subdivider - construct a subdivider
109  *---------------------------------------------------------------------------
110  */
111 
113  : slicer( b ),
114  arctessellator( trimvertexpool, pwlarcpool ),
115  arcpool( sizeof( Arc), 1, "arcpool" ),
116  bezierarcpool( sizeof( BezierArc ), 1, "Bezarcpool" ),
117  pwlarcpool( sizeof( PwlArc ), 1, "Pwlarcpool" ),
118  renderhints( r ),
119  backend( b )
120 {
121 }
122 
123 void
125 {
126  jumpbuffer = j;
127 }
128 
129 /*---------------------------------------------------------------------------
130  * clear - reset all state after possible error condition
131  *---------------------------------------------------------------------------
132  */
133 
134 void
136 {
138  arcpool.clear();
139  pwlarcpool.clear();
141 }
142 
143 /*---------------------------------------------------------------------------
144  * ~Subdivider - destroy a subdivider
145  *---------------------------------------------------------------------------
146  */
147 
149 {
150 }
151 
152 /*---------------------------------------------------------------------------
153  * addArc - add a bezier arc to a trim loop and to a bin
154  *---------------------------------------------------------------------------
155  */
156 void
157 Subdivider::addArc( REAL *cpts, Quilt *quilt, long _nuid )
158 {
159  BezierArc *bezierArc = new(bezierarcpool) BezierArc;
160  Arc *jarc = new(arcpool) Arc( arc_none, _nuid );
161  jarc->pwlArc = 0;
162  jarc->bezierArc = bezierArc;
163  bezierArc->order = quilt->qspec->order;
164  bezierArc->stride = quilt->qspec->stride;
165  bezierArc->mapdesc = quilt->mapdesc;
166  bezierArc->cpts = cpts;
167  initialbin.addarc( jarc );
168  pjarc = jarc->append( pjarc );
169 }
170 
171 /*---------------------------------------------------------------------------
172  * addArc - add a pwl arc to a trim loop and to a bin
173  *---------------------------------------------------------------------------
174  */
175 
176 void
177 Subdivider::addArc( int npts, TrimVertex *pts, long _nuid )
178 {
179  Arc *jarc = new(arcpool) Arc( arc_none, _nuid );
180  jarc->pwlArc = new(pwlarcpool) PwlArc( npts, pts );
181  initialbin.addarc( jarc );
182  pjarc = jarc->append( pjarc );
183 }
184 
185 void
187 {
188  qlist = 0;
189 }
190 
191 void
193 {
194  quilt->next = qlist;
195  qlist = quilt;
196 }
197 
198 /*---------------------------------------------------------------------------
199  * drawSurfaces - main entry point for surface tessellation
200  *---------------------------------------------------------------------------
201  */
202 
203 void
205 {
206  renderhints.init( );
207 
208  if (qlist == NULL)
209  {
210  //initialbin could be nonempty due to some errors
212  return;
213  }
214 
215  for( Quilt *q = qlist; q; q = q->next ) {
216  if( q->isCulled( ) == CULL_TRIVIAL_REJECT ) {
218  return;
219  }
220  }
221 
222 
223  REAL from[2], to[2];
224  qlist->getRange( from, to, spbrkpts, tpbrkpts );
225 #ifdef OPTIMIZE_UNTRIMED_CASE
226  //perform optimization only when the samplng method is
227  //DOMAIN_DISTANCE and the display methdo is either
228  //fill or outline_polygon.
230 #endif
231 
232  if( ! initialbin.isnonempty() ) {
233 #ifdef OPTIMIZE_UNTRIMED_CASE
234  if(! optimize )
235  {
236 
237  makeBorderTrim( from, to );
238  }
239 #else
240  makeBorderTrim( from, to );
241 #endif
242  } else {
243  REAL rate[2];
245 
246  if( decompose( initialbin, min(rate[0], rate[1]) ) )
247  mylongjmp( jumpbuffer, 31 );
248  }
249 
251 
252 #ifdef PARTITION_TEST
253  if( initialbin.isnonempty() && spbrkpts.end-2 == spbrkpts.start &&
254  tpbrkpts.end-2 == tpbrkpts.start)
255 {
256  for(int i=spbrkpts.start; i<spbrkpts.end-1; i++){
257  for(int j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
258  Real pta[2], ptb[2];
259  pta[0] = spbrkpts.pts[i];
260  ptb[0] = spbrkpts.pts[i+1];
261  pta[1] = tpbrkpts.pts[j];
262  ptb[1] = tpbrkpts.pts[j+1];
263  qlist->downloadAll(pta, ptb, backend);
264 
265  directedLine *poly;
266 
267  {
268 
270 
271  poly=poly->deleteDegenerateLinesAllPolygons();
272 
273  sampledLine* retSampledLines;
274 //printf("before MC_partition\n");
275  poly = MC_partitionY(poly, &retSampledLines);
276 //printf("after MC_partition\n");
277 
278  }
279 
280 
281  {
282  primStream pStream(5000,5000);
284 
285  for(temp=poly; temp != NULL; temp=temp->getNextPolygon())
286 
287  monoTriangulation(temp, &pStream);
288 
289  slicer.evalStream(&pStream);
290 
291  }
292  //need to clean up space
293  }
294  }
296  backend.endsurf();
297  return;
298 
299  /*
300  printf("num_polygons=%i\n", poly->numPolygons());
301  printf("num_edges=%i\n", poly->numEdgesAllPolygons());
302  poly->writeAllPolygons("zloutputFile");
303  return;
304  {
305  primStream pStream(20,20);
306  for(directedLine* tempD = poly; tempD != NULL; tempD = tempD->getNextPolygon())
307  monoTriangulation(tempD, &pStream);
308  }
309  return;
310  */
311 }
312 #endif //PARTITION_TEST
313 
314 
315 #ifdef OPTIMIZE_UNTRIMED_CASE
316  if( (!initialbin.isnonempty()) && optimize )
317  {
318  int i,j;
319  int num_u_steps;
320  int num_v_steps;
321  for(i=spbrkpts.start; i<spbrkpts.end-1; i++){
322  for(j=tpbrkpts.start; j<tpbrkpts.end-1; j++){
323  Real pta[2], ptb[2];
324  pta[0] = spbrkpts.pts[i];
325  ptb[0] = spbrkpts.pts[i+1];
326  pta[1] = tpbrkpts.pts[j];
327  ptb[1] = tpbrkpts.pts[j+1];
328  qlist->downloadAll(pta, ptb, backend);
329 
330  num_u_steps = (int) (domain_distance_u_rate * (ptb[0]-pta[0]));
331  num_v_steps = (int) (domain_distance_v_rate * (ptb[1]-pta[1]));
332 
333  if(num_u_steps <= 0) num_u_steps = 1;
334  if(num_v_steps <= 0) num_v_steps = 1;
335 
336  backend.surfgrid(pta[0], ptb[0], num_u_steps,
337  ptb[1], pta[1], num_v_steps);
338  backend.surfmesh(0,0,num_u_steps,num_v_steps);
339 
340 
341 
342  continue;
343  /* the following is left for reference purpose, don't delete
344  {
345  Bin* tempSource;
346  Patchlist patchlist(qlist, pta, ptb);
347  patchlist.getstepsize();
348 
349  tempSource=makePatchBoundary(pta, ptb);
350 
351  tessellation(*tempSource, patchlist);
352 
353  render(*tempSource);
354  delete tempSource;
355  }
356  */
357  }
358  }
359  }
360  else
362 #else
363 
365 #endif
366 
367  backend.endsurf();
368 
369 }
370 
371 void
373 {
375  outline( source );
376  freejarcs( source );
377  } else {
381  }
382 }
383 
384 
385 /*---------------------------------------------------------------------------
386  * splitInS - split a patch and a bin by an isoparametric line
387  *---------------------------------------------------------------------------
388  */
389 
390 void
392 {
393  if( source.isnonempty() ) {
394  if( start != end ) {
395  int i = start + (end - start) / 2;
396  Bin left, right;
397  split( source, left, right, 0, spbrkpts.pts[i] );
398  splitInS( left, start, i );
399  splitInS( right, i+1, end );
400  } else {
401  if( start == spbrkpts.start || start == spbrkpts.end ) {
402  freejarcs( source );
404  outline( source );
405  freejarcs( source );
406  } else {
409  s_index = start;
411  }
412  }
413  }
414 }
415 
416 /*---------------------------------------------------------------------------
417  * splitInT - split a patch and a bin by an isoparametric line
418  *---------------------------------------------------------------------------
419  */
420 
421 void
423 {
424  if( source.isnonempty() ) {
425  if( start != end ) {
426  int i = start + (end - start) / 2;
427  Bin left, right;
428  split( source, left, right, 1, tpbrkpts.pts[i] );
429  splitInT( left, start, i );
430  splitInT( right, i+1, end );
431  } else {
432  if( start == tpbrkpts.start || start == tpbrkpts.end ) {
433  freejarcs( source );
435  outline( source );
436  freejarcs( source );
437  } else {
438  t_index = start;
440  setDegenerate();
441 
442  REAL pta[2], ptb[2];
443  pta[0] = spbrkpts.pts[s_index-1];
444  pta[1] = tpbrkpts.pts[t_index-1];
445 
446  ptb[0] = spbrkpts.pts[s_index];
447  ptb[1] = tpbrkpts.pts[t_index];
448  qlist->downloadAll( pta, ptb, backend );
449 
450  Patchlist patchlist( qlist, pta, ptb );
451 /*
452 printf("-------samplingSplit-----\n");
453 source.show("samplingSplit source");
454 */
458  }
459  }
460  }
461 }
462 
463 /*--------------------------------------------------------------------------
464  * samplingSplit - recursively subdivide patch, cull check each subpatch
465  *--------------------------------------------------------------------------
466  */
467 
468 void
470  Bin& source,
471  Patchlist& patchlist,
472  int subdivisions,
473  int param )
474 {
475  if( ! source.isnonempty() ) return;
476 
477  if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT ) {
478  freejarcs( source );
479  return;
480  }
481 
482  patchlist.getstepsize();
483 
485  tessellation( source, patchlist );
486  outline( source );
487  freejarcs( source );
488  return;
489  }
490 
491  //patchlist.clamp();
492 
493  tessellation( source, patchlist );
494 
495  if( patchlist.needsSamplingSubdivision() && (subdivisions > 0) ) {
496  if( ! patchlist.needsSubdivision( 0 ) )
497  param = 1;
498  else if( ! patchlist.needsSubdivision( 1 ) )
499  param = 0;
500  else
501  param = 1 - param;
502 
503  Bin left, right;
504  REAL mid = ( patchlist.pspec[param].range[0] +
505  patchlist.pspec[param].range[1] ) * 0.5;
506  split( source, left, right, param, mid );
507  Patchlist subpatchlist( patchlist, param, mid );
508  samplingSplit( left, subpatchlist, subdivisions-1, param );
509  samplingSplit( right, patchlist, subdivisions-1, param );
510  } else {
511  setArcTypePwl();
512  setDegenerate();
513  nonSamplingSplit( source, patchlist, subdivisions, param );
514  setDegenerate();
516  }
517 }
518 
519 void
521  Bin& source,
522  Patchlist& patchlist,
523  int subdivisions,
524  int param )
525 {
526  if( patchlist.needsNonSamplingSubdivision() && (subdivisions > 0) ) {
527  param = 1 - param;
528 
529  Bin left, right;
530  REAL mid = ( patchlist.pspec[param].range[0] +
531  patchlist.pspec[param].range[1] ) * 0.5;
532  split( source, left, right, param, mid );
533  Patchlist subpatchlist( patchlist, param, mid );
534  if( left.isnonempty() ) {
535  if( subpatchlist.cullCheck() == CULL_TRIVIAL_REJECT )
536  freejarcs( left );
537  else
538  nonSamplingSplit( left, subpatchlist, subdivisions-1, param );
539  }
540  if( right.isnonempty() ) {
541  if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT )
542  freejarcs( right );
543  else
544  nonSamplingSplit( right, patchlist, subdivisions-1, param );
545  }
546 
547  } else {
548  // make bbox calls
549  patchlist.bbox();
550  backend.patch( patchlist.pspec[0].range[0], patchlist.pspec[0].range[1],
551  patchlist.pspec[1].range[0], patchlist.pspec[1].range[1] );
552 
554  outline( source );
555  freejarcs( source );
556  } else {
557  setArcTypePwl();
558  setDegenerate();
561  }
562  }
563 }
564 
565 /*--------------------------------------------------------------------------
566  * tessellation - set tessellation of interior and boundary of patch
567  *--------------------------------------------------------------------------
568  */
569 
570 void
572 {
573  // tessellate unsampled trim curves
574  tessellate( bin, patchlist.pspec[1].sidestep[1], patchlist.pspec[0].sidestep[1],
575  patchlist.pspec[1].sidestep[0], patchlist.pspec[0].sidestep[0] );
576 
577  // set interior sampling rates
578  slicer.setstriptessellation( patchlist.pspec[0].stepsize, patchlist.pspec[1].stepsize );
579 
580  //added by zl: set the order which will be used in slicer.c++
581  slicer.set_ulinear( (patchlist.get_uorder() == 2));
582  slicer.set_vlinear( (patchlist.get_vorder() == 2));
583 
584  // set boundary sampling rates
585  stepsizes[0] = patchlist.pspec[1].stepsize;
586  stepsizes[1] = patchlist.pspec[0].stepsize;
587  stepsizes[2] = patchlist.pspec[1].stepsize;
588  stepsizes[3] = patchlist.pspec[0].stepsize;
589 }
590 
591 /*---------------------------------------------------------------------------
592  * monosplitInS - split a patch and a bin by an isoparametric line
593  *---------------------------------------------------------------------------
594  */
595 
596 void
598 {
599  if( source.isnonempty() ) {
600  if( start != end ) {
601  int i = start + (end - start) / 2;
602  Bin left, right;
603  split( source, left, right, 0, smbrkpts.pts[i] );
604  monosplitInS( left, start, i );
605  monosplitInS( right, i+1, end );
606  } else {
608  outline( source );
609  freejarcs( source );
610  } else {
611  setArcTypePwl();
612  setDegenerate();
615  }
616  }
617  }
618 }
619 
620 /*---------------------------------------------------------------------------
621  * monosplitInT - split a patch and a bin by an isoparametric line
622  *---------------------------------------------------------------------------
623  */
624 
625 void
627 {
628  if( source.isnonempty() ) {
629  if( start != end ) {
630  int i = start + (end - start) / 2;
631  Bin left, right;
632  split( source, left, right, 1, tmbrkpts.pts[i] );
633  monosplitInT( left, start, i );
634  monosplitInT( right, i+1, end );
635  } else {
637  outline( source );
638  freejarcs( source );
639  } else {
640 /*
641 printf("*******render\n");
642 source.show("source\n");
643 */
644  render( source );
645  freejarcs( source );
646  }
647  }
648  }
649 }
650 
651 
652 /*----------------------------------------------------------------------------
653  * findIrregularS - determine points of non-monotonicity is s direction
654  *----------------------------------------------------------------------------
655  */
656 
657 void
659 {
660  assert( bin.firstarc()->check() != 0 );
661 
662  smbrkpts.grow( bin.numarcs() );
663 
664  for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
665  REAL *a = jarc->prev->tail();
666  REAL *b = jarc->tail();
667  REAL *c = jarc->head();
668 
669  if( b[1] == a[1] && b[1] == c[1] ) continue;
670 
671  //corrected code
672  if((b[1]<=a[1] && b[1] <= c[1]) ||
673  (b[1]>=a[1] && b[1] >= c[1]))
674  {
675  //each arc (jarc, jarc->prev, jarc->next) is a
676  //monotone arc consisting of multiple line segements.
677  //it may happen that jarc->prev and jarc->next are the same,
678  //that is, jarc->prev and jarc form a closed loop.
679  //In such case, a and c will be the same.
680  if(a[0]==c[0] && a[1] == c[1])
681  {
682  if(jarc->pwlArc->npts >2)
683  {
684  c = jarc->pwlArc->pts[jarc->pwlArc->npts-2].param;
685  }
686  else
687  {
688  assert(jarc->prev->pwlArc->npts>2);
689  a = jarc->prev->pwlArc->pts[jarc->prev->pwlArc->npts-2].param;
690  }
691 
692  }
693  if(area(a,b,c) < 0)
694  {
695  smbrkpts.add(b[0]);
696  }
697 
698  }
699 
700  /* old code,
701  if( b[1] <= a[1] && b[1] <= c[1] ) {
702  if( ! ccwTurn_tr( jarc->prev, jarc ) )
703  smbrkpts.add( b[0] );
704  } else if( b[1] >= a[1] && b[1] >= c[1] ) {
705  if( ! ccwTurn_tl( jarc->prev, jarc ) )
706  smbrkpts.add( b[0] );
707  }
708  */
709 
710  }
711 
712  smbrkpts.filter();
713 }
714 
715 /*----------------------------------------------------------------------------
716  * findIrregularT - determine points of non-monotonicity in t direction
717  * where one arc is parallel to the s axis.
718  *----------------------------------------------------------------------------
719  */
720 
721 void
723 {
724  assert( bin.firstarc()->check() != 0 );
725 
726  tmbrkpts.grow( bin.numarcs() );
727 
728  for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
729  REAL *a = jarc->prev->tail();
730  REAL *b = jarc->tail();
731  REAL *c = jarc->head();
732 
733  if( b[0] == a[0] && b[0] == c[0] ) continue;
734 
735  if( b[0] <= a[0] && b[0] <= c[0] ) {
736  if( a[1] != b[1] && b[1] != c[1] ) continue;
737  if( ! ccwTurn_sr( jarc->prev, jarc ) )
738  tmbrkpts.add( b[1] );
739  } else if ( b[0] >= a[0] && b[0] >= c[0] ) {
740  if( a[1] != b[1] && b[1] != c[1] ) continue;
741  if( ! ccwTurn_sl( jarc->prev, jarc ) )
742  tmbrkpts.add( b[1] );
743  }
744  }
745  tmbrkpts.filter( );
746 }
747 
748 /*-----------------------------------------------------------------------------
749  * makeBorderTrim - if no user input trimming data then create
750  * a trimming curve around the boundaries of the Quilt. The curve consists of
751  * four Jordan arcs, one for each side of the Quilt, connected, of course,
752  * head to tail.
753  *-----------------------------------------------------------------------------
754  */
755 
756 void
758 {
759  REAL smin = from[0];
760  REAL smax = to[0];
761  REAL tmin = from[1];
762  REAL tmax = to[1];
763 
764  pjarc = 0;
765 
766  Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
767  arctessellator.bezier( jarc, smin, smax, tmin, tmin );
768  initialbin.addarc( jarc );
769  pjarc = jarc->append( pjarc );
770 
771  jarc = new(arcpool) Arc( arc_right, 0 );
772  arctessellator.bezier( jarc, smax, smax, tmin, tmax );
773  initialbin.addarc( jarc );
774  pjarc = jarc->append( pjarc );
775 
776  jarc = new(arcpool) Arc( arc_top, 0 );
777  arctessellator.bezier( jarc, smax, smin, tmax, tmax );
778  initialbin.addarc( jarc );
779  pjarc = jarc->append( pjarc );
780 
781  jarc = new(arcpool) Arc( arc_left, 0 );
782  arctessellator.bezier( jarc, smin, smin, tmax, tmin );
783  initialbin.addarc( jarc );
784  jarc->append( pjarc );
785 
786  assert( jarc->check() != 0 );
787 }
788 
789 /*----------------------------------------------------------------------------
790  * render - renders all monotone regions in a bin and frees the bin
791  *----------------------------------------------------------------------------
792  */
793 
794 void
796 {
797  bin.markall();
798 
799 #ifdef N_ISOLINE_S
801 #else
802  slicer.setisolines( 0 );
803 #endif
804 
805  for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
806  if( jarc->ismarked() ) {
807  assert( jarc->check( ) != 0 );
808  Arc_ptr jarchead = jarc;
809  do {
810  jarc->clearmark();
811  jarc = jarc->next;
812  } while (jarc != jarchead);
813  slicer.slice( jarc );
814  }
815  }
816 }
817 
818 /*---------------------------------------------------------------------------
819  * outline - render the trimmed patch by outlining the boundary
820  *---------------------------------------------------------------------------
821  */
822 
823 void
825 {
826  bin.markall();
827  for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
828  if( jarc->ismarked() ) {
829  assert( jarc->check( ) != 0 );
830  Arc_ptr jarchead = jarc;
831  do {
832  slicer.outline( jarc );
833  jarc->clearmark();
834  jarc = jarc->prev;
835  } while (jarc != jarchead);
836  }
837  }
838 }
839 
840 /*---------------------------------------------------------------------------
841  * freejarcs - free all arcs in a bin
842  *---------------------------------------------------------------------------
843  */
844 
845 void
847 {
848  bin.adopt(); /* XXX - should not be necessary */
849 
850  Arc_ptr jarc;
851  while( (jarc = bin.removearc()) != NULL ) {
852  if( jarc->pwlArc ) jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
853  if( jarc->bezierArc) jarc->bezierArc->deleteMe( bezierarcpool ); jarc->bezierArc = 0;
854  jarc->deleteMe( arcpool );
855  }
856 }
857 
858 /*----------------------------------------------------------------------------
859  * tessellate - tessellate all Bezier arcs in a bin
860  * 1) only accepts linear Bezier arcs as input
861  * 2) the Bezier arcs are stored in the pwlArc structure
862  * 3) only vertical or horizontal lines work
863  * -- should
864  * 1) represent Bezier arcs in BezierArc structure
865  * (this requires a multitude of changes to the code)
866  * 2) accept high degree Bezier arcs (hard)
867  * 3) map the curve onto the surface to determine tessellation
868  * 4) work for curves of arbitrary geometry
869  *----------------------------------------------------------------------------
870  */
871 
872 
873 void
874 Subdivider::tessellate( Bin& bin, REAL rrate, REAL trate, REAL lrate, REAL brate )
875 {
876  for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
877  if( jarc->isbezier( ) ) {
878  assert( jarc->pwlArc->npts == 2 );
879  TrimVertex *pts = jarc->pwlArc->pts;
880  REAL s1 = pts[0].param[0];
881  REAL t1 = pts[0].param[1];
882  REAL s2 = pts[1].param[0];
883  REAL t2 = pts[1].param[1];
884 
885  jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
886 
887  switch( jarc->getside() ) {
888  case arc_left:
889  assert( s1 == s2 );
890  arctessellator.pwl_left( jarc, s1, t1, t2, lrate );
891  break;
892  case arc_right:
893  assert( s1 == s2 );
894  arctessellator.pwl_right( jarc, s1, t1, t2, rrate );
895  break;
896  case arc_top:
897  assert( t1 == t2 );
898  arctessellator.pwl_top( jarc, t1, s1, s2, trate );
899  break;
900  case arc_bottom:
901  assert( t1 == t2 );
902  arctessellator.pwl_bottom( jarc, t1, s1, s2, brate );
903  break;
904  case arc_none:
905  (void) abort();
906  break;
907  }
908  assert( ! jarc->isbezier() );
909  assert( jarc->check() != 0 );
910  }
911  }
912 }
void surfmesh(long, long, long, long)
Definition: backend.cc:136
Backend & backend
Definition: subdivider.h:121
int cullCheck(void)
Definition: patchlist.cc:96
void freejarcs(Bin &)
Definition: subdivider.cc:846
Definition: quilt.h:64
int is_domain_distance_sampling
Definition: subdivider.h:190
void addArc(REAL *, Quilt *, long)
Definition: subdivider.cc:157
Mapdesc * mapdesc
Definition: quilt.h:67
struct S2 s2
Flist tpbrkpts
Definition: subdivider.h:129
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
void setJumpbuffer(JumpBuffer *)
Definition: subdivider.cc:124
Definition: arc.h:52
Quiltspec qspec[MAXDIM]
Definition: quilt.h:69
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList
REAL * pts
Definition: flist.h:44
void grow(int)
Definition: flist.cc:94
void init(void)
Definition: renderhints.cc:63
void setArcTypeBezier(void)
Definition: subdivider.h:156
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
void patch(REAL, REAL, REAL, REAL)
Definition: backend.cc:89
void render(Bin &)
Definition: subdivider.cc:795
void outline(Bin &)
Definition: subdivider.cc:824
REAL display_method
Definition: renderhints.h:49
#define N_OUTLINE_SUBDIV_ST
Definition: nurbsconsts.h:81
directedLine * deleteDegenerateLinesAllPolygons()
Definition: pwlarc.h:44
#define assert(x)
Definition: debug.h:53
Bin initialbin
Definition: subdivider.h:123
void pwl_top(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:185
void getstepsize(void)
Definition: patchlist.cc:114
GLuint GLuint end
Definition: gl.h:1545
Flist tmbrkpts
Definition: subdivider.h:131
int rate
Definition: pcmconverter.c:98
void samplingSplit(Curvelist &, int)
Definition: curvesub.cc:85
void setArcTypePwl(void)
Definition: subdivider.h:157
REAL sidestep[2]
Definition: patch.h:48
Pool pwlarcpool
Definition: subdivider.h:116
void split(Bin &, Bin &, Bin &, int, REAL)
Definition: splitarcs.cc:58
void endsurf(void)
Definition: backend.cc:178
Definition: arc.h:55
Pool arcpool
Definition: subdivider.h:114
void beginQuilts(void)
Definition: subdivider.cc:186
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
int needsNonSamplingSubdivision(void)
Definition: patchlist.cc:144
int ccwTurn_sl(Arc_ptr, Arc_ptr)
Definition: ccw.cc:170
void findIrregularS(Bin &)
Definition: subdivider.cc:658
int stride
Definition: quilt.h:52
BOOL WINAPI Arc(_In_ HDC hdc, _In_ INT xLeft, _In_ INT yTop, _In_ INT xRight, _In_ INT yBottom, _In_ INT xStartArc, _In_ INT yStartArc, _In_ INT xEndArc, _In_ INT yEndArc)
Definition: arc.c:5
Definition: arc.h:52
void splitInS(Bin &, int, int)
Definition: subdivider.cc:391
int needsSamplingSubdivision(void)
Definition: patchlist.cc:153
Definition: arc.h:52
void monosplitInT(Bin &, int, int)
Definition: subdivider.cc:626
void setNonDegenerate(void)
Definition: subdivider.h:154
Arc_ptr pjarc
Definition: subdivider.h:124
smooth NULL
Definition: ftsmooth.c:416
void bbox()
Definition: patchlist.cc:137
#define N_OUTLINE_PATCH
Definition: nurbsconsts.h:75
void pwl_bottom(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:214
void add(REAL x)
Definition: flist.cc:66
Definition: bin.h:43
REAL * cpts
Definition: bezierarc.h:44
#define N_OUTLINE_SUBDIV_S
Definition: nurbsconsts.h:80
int ccwTurn_sr(Arc_ptr, Arc_ptr)
Definition: ccw.cc:57
int maxsubdivisions
Definition: renderhints.h:55
void tessellate(Arc_ptr, REAL)
Definition: monotonizer.cc:83
void nonSamplingSplit(Bin &, Patchlist &, int, int)
Definition: subdivider.cc:520
void drawSurfaces(long)
Definition: subdivider.cc:204
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
void findIrregularT(Bin &)
Definition: subdivider.cc:722
int get_uorder()
Definition: patchlist.h:76
void outline(Arc_ptr)
Definition: slicer.cc:1292
void bezier(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
void monosplitInS(Bin &, int, int)
Definition: subdivider.cc:597
void setstriptessellation(REAL, REAL)
Definition: slicer.cc:1203
struct S1 s1
#define N_OUTLINE_SUBDIV
Definition: nurbsconsts.h:79
GLfloat param
Definition: glext.h:5796
void findRates(Flist &slist, Flist &tlist, REAL[2])
Definition: quilt.cc:229
void slice(Arc_ptr)
Definition: slicer.cc:1165
int get_vorder()
Definition: patchlist.h:83
const GLubyte * c
Definition: glext.h:8905
Pspec pspec[2]
Definition: patchlist.h:66
void pwl_right(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:155
GLint left
Definition: glext.h:7726
Bin * makePatchBoundary(const REAL *from, const REAL *to)
Definition: subdivider.cc:73
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
GLdouble GLdouble right
Definition: glext.h:10859
void clear(void)
Definition: bufpool.cc:100
void setisolines(int)
Definition: slicer.cc:1197
void clear(void)
Definition: trimvertpool.cc:81
int ret
REAL stepsizes[4]
Definition: subdivider.h:132
void filter(void)
Definition: flist.cc:76
REAL domain_distance_v_rate
Definition: subdivider.h:189
void set_vlinear(int vlinear_flag)
Definition: slicer.h:67
#define N_OUTLINE_PARAM
Definition: nurbsconsts.h:76
ArcTessellator arctessellator
Definition: subdivider.h:113
void splitInT(Bin &, int, int)
Definition: subdivider.cc:422
void setDegenerate(void)
Definition: subdivider.h:153
int isnonempty(void)
Definition: bin.h:54
REAL domain_distance_u_rate
Definition: subdivider.h:188
void makeBorderTrim(const REAL *, const REAL *)
Definition: subdivider.cc:757
Flist smbrkpts
Definition: subdivider.h:130
Definition: arc.h:52
void addQuilt(Quilt *)
Definition: subdivider.cc:192
Flist spbrkpts
Definition: subdivider.h:128
void clear(void)
Definition: subdivider.cc:135
PwlArc * pwlArc
Definition: arc.h:65
Subdivider(Renderhints &, Backend &)
Definition: subdivider.cc:112
class Arc * Arc_ptr
Definition: arc.h:50
TrimVertexPool trimvertexpool
Definition: subdivider.h:117
void bgnsurf(int, int, long)
Definition: backend.cc:58
static calc_node_t temp
Definition: rpn_ieee.c:38
GLuint start
Definition: gl.h:1545
void set_ulinear(int ulinear_flag)
Definition: slicer.h:63
#define N_OUTLINE_PARAM_ST
Definition: nurbsconsts.h:78
int needsSubdivision(int)
Definition: patchlist.cc:166
void subdivideInS(Bin &)
Definition: subdivider.cc:372
void getRange(REAL *, REAL *, Flist &, Flist &)
Definition: quilt.cc:185
void evalStream(primStream *)
Definition: slicer.cc:1027
#define abort()
Definition: i386-dis.c:35
JumpBuffer * jumpbuffer
Definition: subdivider.h:119
void pwl_left(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:125
Renderhints & renderhints
Definition: subdivider.h:120
int order
Definition: quilt.h:55
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
#define min(a, b)
Definition: monoChain.cc:55
~Subdivider(void)
Definition: subdivider.cc:148
void downloadAll(REAL *, REAL *, Backend &)
Definition: quilt.cc:156
float Real
Definition: definitions.h:36
REAL param[2]
Definition: trimvertex.h:45
int start
Definition: flist.h:46
void tessellation(Bin &, Patchlist &)
Definition: subdivider.cc:571
static struct _PeImage bin
struct define * next
Definition: wpp.c:35
#define N_OUTLINE_PARAM_S
Definition: nurbsconsts.h:77
Pool bezierarcpool
Definition: subdivider.h:115
directedLine * bin_to_DLineLoops(Bin &bin)
void addarc(Arc_ptr)
Definition: bin.h:70
REAL stepsize
Definition: patch.h:49
void surfgrid(REAL, REAL, long, REAL, REAL, long)
Definition: backend.cc:126
Mapdesc * mapdesc
Definition: bezierarc.h:48
Quilt * next
Definition: quilt.h:71
int stride
Definition: bezierarc.h:46
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
float REAL
Definition: types.h:41
CardRegion * from
Definition: spigame.cpp:19
int end
Definition: flist.h:47
void monoTriangulation(directedLine *monoPolygon, primStream *pStream)
Arc_ptr append(Arc_ptr)
Definition: arc.cc:335
#define N_ISOLINE_S
Definition: nurbsconsts.h:82
BezierArc * bezierArc
Definition: arc.h:64
int decompose(Bin &, REAL)
Definition: monotonizer.cc:56
Quilt * qlist
Definition: subdivider.h:127
#define CULL_TRIVIAL_REJECT
Definition: defines.h:40
REAL range[3]
Definition: patch.h:47
Slicer slicer
Definition: subdivider.h:112
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
Definition: arc.h:52
int order
Definition: bezierarc.h:45
directedLine * MC_partitionY(directedLine *polygons, sampledLine **retSampledLines)
Definition: monoChain.cc:647