ReactOS 0.4.15-dev-8408-g466a198
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
72Bin*
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
123void
125{
126 jumpbuffer = j;
127}
128
129/*---------------------------------------------------------------------------
130 * clear - reset all state after possible error condition
131 *---------------------------------------------------------------------------
132 */
133
134void
136{
138 arcpool.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 */
156void
157Subdivider::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
176void
177Subdivider::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
185void
187{
188 qlist = 0;
189}
190
191void
193{
194 quilt->next = qlist;
195 qlist = quilt;
196}
197
198/*---------------------------------------------------------------------------
199 * drawSurfaces - main entry point for surface tessellation
200 *---------------------------------------------------------------------------
201 */
202
203void
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];
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
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
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 }
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
368
369}
370
371void
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
390void
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
421void
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;
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/*
452printf("-------samplingSplit-----\n");
453source.show("samplingSplit source");
454*/
458 }
459 }
460 }
461}
462
463/*--------------------------------------------------------------------------
464 * samplingSplit - recursively subdivide patch, cull check each subpatch
465 *--------------------------------------------------------------------------
466 */
467
468void
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 {
513 nonSamplingSplit( source, patchlist, subdivisions, param );
516 }
517}
518
519void
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 {
561 }
562 }
563}
564
565/*--------------------------------------------------------------------------
566 * tessellation - set tessellation of interior and boundary of patch
567 *--------------------------------------------------------------------------
568 */
569
570void
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
596void
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] );
605 monosplitInS( right, i+1, end );
606 } else {
608 outline( source );
609 freejarcs( source );
610 } else {
615 }
616 }
617 }
618}
619
620/*---------------------------------------------------------------------------
621 * monosplitInT - split a patch and a bin by an isoparametric line
622 *---------------------------------------------------------------------------
623 */
624
625void
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] );
634 monosplitInT( right, i+1, end );
635 } else {
637 outline( source );
638 freejarcs( source );
639 } else {
640/*
641printf("*******render\n");
642source.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
657void
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
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
721void
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
756void
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
794void
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
823void
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
845void
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 );
853 jarc->pwlArc = 0;
854 if( jarc->bezierArc) jarc->bezierArc->deleteMe( bezierarcpool );
855 jarc->bezierArc = 0;
856 jarc->deleteMe( arcpool );
857 }
858}
859
860/*----------------------------------------------------------------------------
861 * tessellate - tessellate all Bezier arcs in a bin
862 * 1) only accepts linear Bezier arcs as input
863 * 2) the Bezier arcs are stored in the pwlArc structure
864 * 3) only vertical or horizontal lines work
865 * -- should
866 * 1) represent Bezier arcs in BezierArc structure
867 * (this requires a multitude of changes to the code)
868 * 2) accept high degree Bezier arcs (hard)
869 * 3) map the curve onto the surface to determine tessellation
870 * 4) work for curves of arbitrary geometry
871 *----------------------------------------------------------------------------
872 */
873
874
875void
876Subdivider::tessellate( Bin& bin, REAL rrate, REAL trate, REAL lrate, REAL brate )
877{
878 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
879 if( jarc->isbezier( ) ) {
880 assert( jarc->pwlArc->npts == 2 );
881 TrimVertex *pts = jarc->pwlArc->pts;
882 REAL s1 = pts[0].param[0];
883 REAL t1 = pts[0].param[1];
884 REAL s2 = pts[1].param[0];
885 REAL t2 = pts[1].param[1];
886
887 jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
888
889 switch( jarc->getside() ) {
890 case arc_left:
891 assert( s1 == s2 );
892 arctessellator.pwl_left( jarc, s1, t1, t2, lrate );
893 break;
894 case arc_right:
895 assert( s1 == s2 );
896 arctessellator.pwl_right( jarc, s1, t1, t2, rrate );
897 break;
898 case arc_top:
899 assert( t1 == t2 );
900 arctessellator.pwl_top( jarc, t1, s1, s2, trate );
901 break;
902 case arc_bottom:
903 assert( t1 == t2 );
904 arctessellator.pwl_bottom( jarc, t1, s1, s2, brate );
905 break;
906 case arc_none:
907 (void) abort();
908 break;
909 }
910 assert( ! jarc->isbezier() );
911 assert( jarc->check() != 0 );
912 }
913 }
914}
void pwl_right(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:155
void pwl_top(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:185
void pwl_bottom(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:214
void bezier(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:79
void pwl_left(Arc_ptr, REAL, REAL, REAL, REAL)
Definition: arctess.cc:125
Definition: arc.h:55
Arc_ptr append(Arc_ptr)
Definition: arc.cc:335
BezierArc * bezierArc
Definition: arc.h:64
PwlArc * pwlArc
Definition: arc.h:65
void bgnsurf(int, int, long)
Definition: backend.cc:58
void endsurf(void)
Definition: backend.cc:178
void surfmesh(long, long, long, long)
Definition: backend.cc:136
void patch(REAL, REAL, REAL, REAL)
Definition: backend.cc:89
void surfgrid(REAL, REAL, long, REAL, REAL, long)
Definition: backend.cc:126
Definition: bin.h:44
int isnonempty(void)
Definition: bin.h:54
void addarc(Arc_ptr)
Definition: bin.h:70
REAL * pts
Definition: flist.h:44
int start
Definition: flist.h:46
void filter(void)
Definition: flist.cc:76
int end
Definition: flist.h:47
void grow(int)
Definition: flist.cc:94
void add(REAL x)
Definition: flist.cc:66
int get_vorder()
Definition: patchlist.h:83
void bbox()
Definition: patchlist.cc:137
Pspec pspec[2]
Definition: patchlist.h:66
void getstepsize(void)
Definition: patchlist.cc:114
int get_uorder()
Definition: patchlist.h:76
int needsSamplingSubdivision(void)
Definition: patchlist.cc:153
int needsSubdivision(int)
Definition: patchlist.cc:166
int needsNonSamplingSubdivision(void)
Definition: patchlist.cc:144
int cullCheck(void)
Definition: patchlist.cc:96
void clear(void)
Definition: bufpool.cc:100
Definition: pwlarc.h:44
Definition: quilt.h:64
Quilt * next
Definition: quilt.h:71
Mapdesc * mapdesc
Definition: quilt.h:67
void findRates(Flist &slist, Flist &tlist, REAL[2])
Definition: quilt.cc:230
void downloadAll(REAL *, REAL *, Backend &)
Definition: quilt.cc:157
void getRange(REAL *, REAL *, Flist &, Flist &)
Definition: quilt.cc:186
Quiltspec qspec[MAXDIM]
Definition: quilt.h:69
int maxsubdivisions
Definition: renderhints.h:55
REAL display_method
Definition: renderhints.h:49
void init(void)
Definition: renderhints.cc:63
void evalStream(primStream *)
Definition: slicer.cc:1027
void outline(Arc_ptr)
Definition: slicer.cc:1292
void set_ulinear(int ulinear_flag)
Definition: slicer.h:63
void set_vlinear(int vlinear_flag)
Definition: slicer.h:67
void setisolines(int)
Definition: slicer.cc:1197
void setstriptessellation(REAL, REAL)
Definition: slicer.cc:1203
void slice(Arc_ptr)
Definition: slicer.cc:1165
void freejarcs(Bin &)
Definition: subdivider.cc:846
Subdivider(Renderhints &, Backend &)
Definition: subdivider.cc:112
REAL domain_distance_u_rate
Definition: subdivider.h:188
void outline(Bin &)
Definition: subdivider.cc:824
Bin initialbin
Definition: subdivider.h:123
int ccwTurn_sr(Arc_ptr, Arc_ptr)
Definition: ccw.cc:57
void samplingSplit(Curvelist &, int)
Definition: curvesub.cc:85
int is_domain_distance_sampling
Definition: subdivider.h:190
~Subdivider(void)
Definition: subdivider.cc:148
void splitInT(Bin &, int, int)
Definition: subdivider.cc:422
Pool bezierarcpool
Definition: subdivider.h:115
int decompose(Bin &, REAL)
Definition: monotonizer.cc:56
void drawSurfaces(long)
Definition: subdivider.cc:204
void monosplitInT(Bin &, int, int)
Definition: subdivider.cc:626
void makeBorderTrim(const REAL *, const REAL *)
Definition: subdivider.cc:757
Renderhints & renderhints
Definition: subdivider.h:120
ArcTessellator arctessellator
Definition: subdivider.h:113
Bin * makePatchBoundary(const REAL *from, const REAL *to)
Definition: subdivider.cc:73
REAL stepsizes[4]
Definition: subdivider.h:132
Flist smbrkpts
Definition: subdivider.h:130
void beginQuilts(void)
Definition: subdivider.cc:186
Backend & backend
Definition: subdivider.h:121
Arc_ptr pjarc
Definition: subdivider.h:124
REAL domain_distance_v_rate
Definition: subdivider.h:189
JumpBuffer * jumpbuffer
Definition: subdivider.h:119
Pool pwlarcpool
Definition: subdivider.h:116
void setNonDegenerate(void)
Definition: subdivider.h:154
void findIrregularT(Bin &)
Definition: subdivider.cc:722
Slicer slicer
Definition: subdivider.h:112
Pool arcpool
Definition: subdivider.h:114
void tessellate(Arc_ptr, REAL)
Definition: monotonizer.cc:83
Flist spbrkpts
Definition: subdivider.h:128
Quilt * qlist
Definition: subdivider.h:127
void tessellation(Bin &, Patchlist &)
Definition: subdivider.cc:571
void render(Bin &)
Definition: subdivider.cc:795
void monosplitInS(Bin &, int, int)
Definition: subdivider.cc:597
void addQuilt(Quilt *)
Definition: subdivider.cc:192
Flist tpbrkpts
Definition: subdivider.h:129
void subdivideInS(Bin &)
Definition: subdivider.cc:372
void addArc(REAL *, Quilt *, long)
Definition: subdivider.cc:157
Flist tmbrkpts
Definition: subdivider.h:131
void splitInS(Bin &, int, int)
Definition: subdivider.cc:391
void nonSamplingSplit(Bin &, Patchlist &, int, int)
Definition: subdivider.cc:520
void setArcTypePwl(void)
Definition: subdivider.h:157
void clear(void)
Definition: subdivider.cc:135
void split(Bin &, Bin &, Bin &, int, REAL)
Definition: splitarcs.cc:58
void setJumpbuffer(JumpBuffer *)
Definition: subdivider.cc:124
void setDegenerate(void)
Definition: subdivider.h:153
int ccwTurn_sl(Arc_ptr, Arc_ptr)
Definition: ccw.cc:170
TrimVertexPool trimvertexpool
Definition: subdivider.h:117
void findIrregularS(Bin &)
Definition: subdivider.cc:658
void setArcTypeBezier(void)
Definition: subdivider.h:156
void clear(void)
Definition: trimvertpool.cc:81
REAL param[2]
Definition: trimvertex.h:45
directedLine * deleteDegenerateLinesAllPolygons()
directedLine * bin_to_DLineLoops(Bin &bin)
float Real
Definition: definitions.h:36
#define NULL
Definition: types.h:112
class Arc * Arc_ptr
Definition: arc.h:50
@ arc_left
Definition: arc.h:52
@ arc_none
Definition: arc.h:52
@ arc_bottom
Definition: arc.h:52
@ arc_top
Definition: arc.h:52
@ arc_right
Definition: arc.h:52
#define CULL_TRIVIAL_REJECT
Definition: defines.h:40
float REAL
Definition: types.h:41
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
#define assert(x)
Definition: debug.h:53
GLuint start
Definition: gl.h:1545
GLuint GLuint end
Definition: gl.h:1545
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
const GLubyte * c
Definition: glext.h:8905
GLdouble GLdouble right
Definition: glext.h:10859
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLint left
Definition: glext.h:7726
GLfloat param
Definition: glext.h:5796
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
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
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
#define abort()
Definition: i386-dis.c:34
struct S1 s1
struct S2 s2
static struct _PeImage bin
directedLine * MC_partitionY(directedLine *polygons, sampledLine **retSampledLines)
Definition: monoChain.cc:647
#define min(a, b)
Definition: monoChain.cc:55
void monoTriangulation(directedLine *monoPolygon, primStream *pStream)
#define N_ISOLINE_S
Definition: nurbsconsts.h:82
#define N_OUTLINE_PARAM_S
Definition: nurbsconsts.h:77
#define N_OUTLINE_PATCH
Definition: nurbsconsts.h:75
#define N_OUTLINE_SUBDIV_ST
Definition: nurbsconsts.h:81
#define N_OUTLINE_SUBDIV
Definition: nurbsconsts.h:79
#define N_OUTLINE_PARAM_ST
Definition: nurbsconsts.h:78
#define N_OUTLINE_PARAM
Definition: nurbsconsts.h:76
#define N_OUTLINE_SUBDIV_S
Definition: nurbsconsts.h:80
int rate
Definition: pcmconverter.c:97
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
static calc_node_t temp
Definition: rpn_ieee.c:38
CardRegion * from
Definition: spigame.cpp:19
static void render(void)
Definition: ssstars.c:272
Mapdesc * mapdesc
Definition: bezierarc.h:48
REAL * cpts
Definition: bezierarc.h:44
int stride
Definition: bezierarc.h:46
int order
Definition: bezierarc.h:45
REAL sidestep[2]
Definition: patch.h:48
REAL range[3]
Definition: patch.h:47
REAL stepsize
Definition: patch.h:49
int order
Definition: quilt.h:55
int stride
Definition: quilt.h:52
Definition: mesh.c:5330
int ret
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList