Debian Codegraph @

lib/database/src/so/nodes/nurbs/libnurbs/subdivider.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 /*
38 * subdivider.c++ - $Revision: 1.2 $
39 * Derrick Burns - 1991
40 */
41
42 #include "glimports.h"
43 #include "myassert.h"
44 #include "mystdio.h"
45 #include "subdivider.h"
46 #include "arc.h"
47 #include "bezierarc.h"
48 #include "bin.h"
49 #include "renderhints.h"
50 #include "backend.h"
51 #include "mapdesc.h"
52 #include "quilt.h"
53 #include "patchlist.h"
54 #include "patch.h"
55 #include "nurbsconsts.h"
56 #include "trimvertpool.h"
57 #include "simplemath.h"
58
59 /*---------------------------------------------------------------------------
60 * Subdivider - construct a subdivider
61 *---------------------------------------------------------------------------
62 */
63
64 Subdivider::Subdivider( Renderhints& r, Backend& b )
65 : arcpool( sizeof( Arc), 1, "arcpool" ),
66 bezierarcpool( sizeof( BezierArc ), 1, "Bezarcpool" ),
67 pwlarcpool( sizeof( PwlArc ), 1, "Pwlarcpool" ),
68 renderhints( r ),
69 arctessellator( trimvertexpool, pwlarcpool ),
70 backend( b ),
71 slicer( b )
72 {
73 }
74
75 void
76 Subdivider::setJumpbuffer( JumpBuffer *j )
77 {
78 jumpbuffer = j;
79 }
80
81 /*---------------------------------------------------------------------------
82 * clear - reset all state after possible error condition
83 *---------------------------------------------------------------------------
84 */
85
86 void
87 Subdivider::clear( void )
88 {
89 trimvertexpool.clear();
90 arcpool.clear();
91 pwlarcpool.clear();
92 bezierarcpool.clear();
93 }
94
95 /*---------------------------------------------------------------------------
96 * ~Subdivider - destroy a subdivider
97 *---------------------------------------------------------------------------
98 */
99
100 Subdivider::~Subdivider( void )
101 {
102 }
103
104 /*---------------------------------------------------------------------------
105 * addArc - add a bezier arc to a trim loop and to a bin
106 *---------------------------------------------------------------------------
107 */
108 void
109 Subdivider::addArc( REAL *cpts, Quilt *quilt, long _nuid )
110 {
111 BezierArc *bezierArc = new(bezierarcpool) BezierArc;
112 Arc *jarc = new(arcpool) Arc( arc_none, _nuid );
113 jarc->pwlArc = 0;
114 jarc->bezierArc = bezierArc;
115 bezierArc->order = quilt->qspec->order;
116 bezierArc->stride = quilt->qspec->stride;
117 bezierArc->mapdesc = quilt->mapdesc;
118 bezierArc->cpts = cpts;
119 initialbin.addarc( jarc );
120 pjarc = jarc->append( pjarc );
121 }
122
123 /*---------------------------------------------------------------------------
124 * addArc - add a pwl arc to a trim loop and to a bin
125 *---------------------------------------------------------------------------
126 */
127
128 void
129 Subdivider::addArc( int npts, TrimVertex *pts, long _nuid )
130 {
131 Arc *jarc = new(arcpool) Arc( arc_none, _nuid );
132 jarc->pwlArc = new(pwlarcpool) PwlArc( npts, pts );
133 initialbin.addarc( jarc );
134 pjarc = jarc->append( pjarc );
135 }
136
137 void
138 Subdivider::beginQuilts( void )
139 {
140 qlist = 0;
141 }
142
143 void
144 Subdivider::addQuilt( Quilt *quilt )
145 {
146 quilt->next = qlist;
147 qlist = quilt;
148 }
149
150 /*---------------------------------------------------------------------------
151 * drawSurfaces - main entry point for surface tessellation
152 *---------------------------------------------------------------------------
153 */
154
155 void
156 Subdivider::drawSurfaces( long nuid )
157 {
158 renderhints.init( );
159
160 if (qlist == NULL) return;
161 for( Quilt *q = qlist; q; q = q->next ) {
162 if( q->isCulled( ) == CULL_TRIVIAL_REJECT ) {
163 freejarcs( initialbin );
164 return;
165 }
166 }
167
168 REAL from[2], to[2];
169 qlist->getRange( from, to, spbrkpts, tpbrkpts );
170
171 if( ! initialbin.isnonempty() ) {
172 makeBorderTrim( from, to );
173 } else {
174 REAL rate[2];
175 qlist->findRates( spbrkpts, tpbrkpts, rate );
176
177 if( decompose( initialbin, min(rate[0], rate[1]) ) )
178 mylongjmp( jumpbuffer, 31 );
179 }
180
181 backend.bgnsurf( renderhints.wiretris, renderhints.wirequads, nuid );
182 subdivideInS( initialbin );
183 backend.endsurf();
184 }
185
186 void
187 Subdivider::subdivideInS( Bin& source )
188 {
189 if( renderhints.display_method == N_OUTLINE_PARAM ) {
190 outline( source );
191 freejarcs( source );
192 } else {
193 setArcTypeBezier();
194 setNonDegenerate();
195 splitInS( source, spbrkpts.start, spbrkpts.end );
196 }
197 }
198
199
200 /*---------------------------------------------------------------------------
201 * splitInS - split a patch and a bin by an isoparametric line
202 *---------------------------------------------------------------------------
203 */
204
205 void
206 Subdivider::splitInS( Bin& source, int start, int end )
207 {
208 if( source.isnonempty() ) {
209 if( start != end ) {
210 int i = start + (end - start) / 2;
211 Bin left, right;
212 split( source, left, right, 0, spbrkpts.pts[i] );
213 splitInS( left, start, i );
214 splitInS( right, i+1, end );
215 } else {
216 if( start == spbrkpts.start || start == spbrkpts.end ) {
217 freejarcs( source );
218 } else if( renderhints.display_method == N_OUTLINE_PARAM_S ) {
219 outline( source );
220 freejarcs( source );
221 } else {
222 setArcTypeBezier();
223 setNonDegenerate();
224 s_index = start;
225 splitInT( source, tpbrkpts.start, tpbrkpts.end );
226 }
227 }
228 }
229 }
230
231 /*---------------------------------------------------------------------------
232 * splitInT - split a patch and a bin by an isoparametric line
233 *---------------------------------------------------------------------------
234 */
235
236 void
237 Subdivider::splitInT( Bin& source, int start, int end )
238 {
239 if( source.isnonempty() ) {
240 if( start != end ) {
241 int i = start + (end - start) / 2;
242 Bin left, right;
243 split( source, left, right, 1, tpbrkpts.pts[i] );
244 splitInT( left, start, i );
245 splitInT( right, i+1, end );
246 } else {
247 if( start == tpbrkpts.start || start == tpbrkpts.end ) {
248 freejarcs( source );
249 } else if( renderhints.display_method == N_OUTLINE_PARAM_ST ) {
250 outline( source );
251 freejarcs( source );
252 } else {
253 t_index = start;
254 setArcTypeBezier();
255 setDegenerate();
256
257 REAL pta[2], ptb[2];
258 pta[0] = spbrkpts.pts[s_index-1];
259 pta[1] = tpbrkpts.pts[t_index-1];
260
261 ptb[0] = spbrkpts.pts[s_index];
262 ptb[1] = tpbrkpts.pts[t_index];
263 qlist->downloadAll( pta, ptb, backend );
264
265 Patchlist patchlist( qlist, pta, ptb );
266 samplingSplit( source, patchlist, renderhints.maxsubdivisions, 0 );
267 setNonDegenerate();
268 setArcTypeBezier();
269 }
270 }
271 }
272 }
273
274 /*--------------------------------------------------------------------------
275 * samplingSplit - recursively subdivide patch, cull check each subpatch
276 *--------------------------------------------------------------------------
277 */
278
279 void
280 Subdivider::samplingSplit(
281 Bin& source,
282 Patchlist& patchlist,
283 int subdivisions,
284 int param )
285 {
286 if( ! source.isnonempty() ) return;
287
288 if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT ) {
289 freejarcs( source );
290 return;
291 }
292
293 patchlist.getstepsize();
294
295 if( renderhints.display_method == N_OUTLINE_PATCH ) {
296 tessellation( source, patchlist );
297 outline( source );
298 freejarcs( source );
299 return;
300 }
301
302 //patchlist.clamp();
303
304 tessellation( source, patchlist );
305
306 if( patchlist.needsSamplingSubdivision() && (subdivisions > 0) ) {
307 if( ! patchlist.needsSubdivision( 0 ) )
308 param = 1;
309 else if( ! patchlist.needsSubdivision( 1 ) )
310 param = 0;
311 else
312 param = 1 - param;
313
314 Bin left, right;
315 REAL mid = ( patchlist.pspec[param].range[0] +
316 patchlist.pspec[param].range[1] ) * 0.5;
317 split( source, left, right, param, mid );
318 Patchlist subpatchlist( patchlist, param, mid );
319 samplingSplit( left, subpatchlist, subdivisions-1, param );
320 samplingSplit( right, patchlist, subdivisions-1, param );
321 } else {
322 setArcTypePwl();
323 setDegenerate();
324 nonSamplingSplit( source, patchlist, subdivisions, param );
325 setDegenerate();
326 setArcTypeBezier();
327 }
328 }
329
330 void
331 Subdivider::nonSamplingSplit(
332 Bin& source,
333 Patchlist& patchlist,
334 int subdivisions,
335 int param )
336 {
337 if( patchlist.needsNonSamplingSubdivision() && (subdivisions > 0) ) {
338 param = 1 - param;
339
340 Bin left, right;
341 REAL mid = ( patchlist.pspec[param].range[0] +
342 patchlist.pspec[param].range[1] ) * 0.5;
343 split( source, left, right, param, mid );
344 Patchlist subpatchlist( patchlist, param, mid );
345 if( left.isnonempty() )
346 if( subpatchlist.cullCheck() == CULL_TRIVIAL_REJECT )
347 freejarcs( left );
348 else
349 nonSamplingSplit( left, subpatchlist, subdivisions-1, param );
350 if( right.isnonempty() )
351 if( patchlist.cullCheck() == CULL_TRIVIAL_REJECT )
352 freejarcs( right );
353 else
354 nonSamplingSplit( right, patchlist, subdivisions-1, param );
355
356 } else {
357 // make bbox calls
358 patchlist.bbox();
359 backend.patch( patchlist.pspec[0].range[0], patchlist.pspec[0].range[1],
360 patchlist.pspec[1].range[0], patchlist.pspec[1].range[1] );
361
362 if( renderhints.display_method == N_OUTLINE_SUBDIV ) {
363 outline( source );
364 freejarcs( source );
365 } else {
366 setArcTypePwl();
367 setDegenerate();
368 findIrregularS( source );
369 monosplitInS( source, smbrkpts.start, smbrkpts.end );
370 }
371 }
372 }
373
374 /*--------------------------------------------------------------------------
375 * tessellation - set tessellation of interior and boundary of patch
376 *--------------------------------------------------------------------------
377 */
378
379 void
380 Subdivider::tessellation( Bin& bin, Patchlist &patchlist )
381 {
382 // tessellate unsampled trim curves
383 tessellate( bin, patchlist.pspec[1].sidestep[1], patchlist.pspec[0].sidestep[1],
384 patchlist.pspec[1].sidestep[0], patchlist.pspec[0].sidestep[0] );
385
386 // set interior sampling rates
387 slicer.setstriptessellation( patchlist.pspec[0].stepsize, patchlist.pspec[1].stepsize );
388
389 // set boundary sampling rates
390 stepsizes[0] = patchlist.pspec[1].stepsize;
391 stepsizes[1] = patchlist.pspec[0].stepsize;
392 stepsizes[2] = patchlist.pspec[1].stepsize;
393 stepsizes[3] = patchlist.pspec[0].stepsize;
394 }
395
396 /*---------------------------------------------------------------------------
397 * monosplitInS - split a patch and a bin by an isoparametric line
398 *---------------------------------------------------------------------------
399 */
400
401 void
402 Subdivider::monosplitInS( Bin& source, int start, int end )
403 {
404 if( source.isnonempty() ) {
405 if( start != end ) {
406 int i = start + (end - start) / 2;
407 Bin left, right;
408 split( source, left, right, 0, smbrkpts.pts[i] );
409 monosplitInS( left, start, i );
410 monosplitInS( right, i+1, end );
411 } else {
412 if( renderhints.display_method == N_OUTLINE_SUBDIV_S ) {
413 outline( source );
414 freejarcs( source );
415 } else {
416 setArcTypePwl();
417 setDegenerate();
418 findIrregularT( source );
419 monosplitInT( source, tmbrkpts.start, tmbrkpts.end );
420 }
421 }
422 }
423 }
424
425 /*---------------------------------------------------------------------------
426 * monosplitInT - split a patch and a bin by an isoparametric line
427 *---------------------------------------------------------------------------
428 */
429
430 void
431 Subdivider::monosplitInT( Bin& source, int start, int end )
432 {
433 if( source.isnonempty() ) {
434 if( start != end ) {
435 int i = start + (end - start) / 2;
436 Bin left, right;
437 split( source, left, right, 1, tmbrkpts.pts[i] );
438 monosplitInT( left, start, i );
439 monosplitInT( right, i+1, end );
440 } else {
441 if( renderhints.display_method == N_OUTLINE_SUBDIV_ST ) {
442 outline( source );
443 freejarcs( source );
444 } else {
445 render( source );
446 freejarcs( source );
447 }
448 }
449 }
450 }
451
452
453 /*----------------------------------------------------------------------------
454 * findIrregularS - determine points of non-monotonicity is s direction
455 *----------------------------------------------------------------------------
456 */
457
458 void
459 Subdivider::findIrregularS( Bin& bin )
460 {
461 assert( bin.firstarc()->check() );
462
463 smbrkpts.grow( bin.numarcs() );
464
465 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
466 REAL *a = jarc->prev->tail();
467 REAL *b = jarc->tail();
468 REAL *c = jarc->head();
469
470 if( b[1] == a[1] && b[1] == c[1] ) continue;
471
472 if( b[1] <= a[1] && b[1] <= c[1] ) {
473 if( ! ccwTurn_tr( jarc->prev, jarc ) )
474 smbrkpts.add( b[0] );
475 } else if( b[1] >= a[1] && b[1] >= c[1] ) {
476 if( ! ccwTurn_tl( jarc->prev, jarc ) )
477 smbrkpts.add( b[0] );
478 }
479 }
480
481 smbrkpts.filter();
482 }
483
484 /*----------------------------------------------------------------------------
485 * findIrregularT - determine points of non-monotonicity in t direction
486 * where one arc is parallel to the s axis.
487 *----------------------------------------------------------------------------
488 */
489
490 void
491 Subdivider::findIrregularT( Bin& bin )
492 {
493 assert( bin.firstarc()->check() );
494
495 tmbrkpts.grow( bin.numarcs() );
496
497 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
498 REAL *a = jarc->prev->tail();
499 REAL *b = jarc->tail();
500 REAL *c = jarc->head();
501
502 if( b[0] == a[0] && b[0] == c[0] ) continue;
503
504 if( b[0] <= a[0] && b[0] <= c[0] ) {
505 if( a[1] != b[1] && b[1] != c[1] ) continue;
506 if( ! ccwTurn_sr( jarc->prev, jarc ) )
507 tmbrkpts.add( b[1] );
508 } else if ( b[0] >= a[0] && b[0] >= c[0] ) {
509 if( a[1] != b[1] && b[1] != c[1] ) continue;
510 if( ! ccwTurn_sl( jarc->prev, jarc ) )
511 tmbrkpts.add( b[1] );
512 }
513 }
514 tmbrkpts.filter( );
515 }
516
517 /*-----------------------------------------------------------------------------
518 * makeBorderTrim - if no user input trimming data then create
519 * a trimming curve around the boundaries of the Quilt. The curve consists of
520 * four Jordan arcs, one for each side of the Quilt, connected, of course,
521 * head to tail.
522 *-----------------------------------------------------------------------------
523 */
524
525 void
526 Subdivider::makeBorderTrim( const REAL *from, const REAL *to )
527 {
528 REAL smin = from[0];
529 REAL smax = to[0];
530 REAL tmin = from[1];
531 REAL tmax = to[1];
532
533 pjarc = 0;
534
535 Arc_ptr jarc = new(arcpool) Arc( arc_bottom, 0 );
536 arctessellator.bezier( jarc, smin, smax, tmin, tmin );
537 initialbin.addarc( jarc );
538 pjarc = jarc->append( pjarc );
539
540 jarc = new(arcpool) Arc( arc_right, 0 );
541 arctessellator.bezier( jarc, smax, smax, tmin, tmax );
542 initialbin.addarc( jarc );
543 pjarc = jarc->append( pjarc );
544
545 jarc = new(arcpool) Arc( arc_top, 0 );
546 arctessellator.bezier( jarc, smax, smin, tmax, tmax );
547 initialbin.addarc( jarc );
548 pjarc = jarc->append( pjarc );
549
550 jarc = new(arcpool) Arc( arc_left, 0 );
551 arctessellator.bezier( jarc, smin, smin, tmax, tmin );
552 initialbin.addarc( jarc );
553 jarc->append( pjarc );
554
555 assert( jarc->check() );
556 }
557
558 /*----------------------------------------------------------------------------
559 * render - renders all monotone regions in a bin and frees the bin
560 *----------------------------------------------------------------------------
561 */
562
563 void
564 Subdivider::render( Bin& bin )
565 {
566 bin.markall();
567
568 #ifdef N_ISOLINE_S
569 slicer.setisolines( ( renderhints.display_method == N_ISOLINE_S ) ? 1 : 0 );
570 #else
571 slicer.setisolines( 0 );
572 #endif
573
574 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
575 if( jarc->ismarked() ) {
576 assert( jarc->check( ) );
577 Arc_ptr jarchead = jarc;
578 do {
579 jarc->clearmark();
580 jarc = jarc->next;
581 } while (jarc != jarchead);
582 slicer.slice( jarc );
583 }
584 }
585 }
586
587 /*---------------------------------------------------------------------------
588 * outline - render the trimmed patch by outlining the boundary
589 *---------------------------------------------------------------------------
590 */
591
592 void
593 Subdivider::outline( Bin& bin )
594 {
595 bin.markall();
596 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
597 if( jarc->ismarked() ) {
598 assert( jarc->check( ) );
599 Arc_ptr jarchead = jarc;
600 do {
601 slicer.outline( jarc );
602 jarc->clearmark();
603 jarc = jarc->prev;
604 } while (jarc != jarchead);
605 }
606 }
607 }
608
609 /*---------------------------------------------------------------------------
610 * freejarcs - free all arcs in a bin
611 *---------------------------------------------------------------------------
612 */
613
614 void
615 Subdivider::freejarcs( Bin& bin )
616 {
617 bin.adopt(); /* XXX - should not be necessary */
618
619 Arc_ptr jarc;
620 while( jarc = bin.removearc() ) {
621 if( jarc->pwlArc ) jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
622 if( jarc->bezierArc) jarc->bezierArc->deleteMe( bezierarcpool ); jarc->bezierArc = 0;
623 jarc->deleteMe( arcpool );
624 }
625 }
626
627 /*----------------------------------------------------------------------------
628 * tessellate - tessellate all Bezier arcs in a bin
629 * 1) only accepts linear Bezier arcs as input
630 * 2) the Bezier arcs are stored in the pwlArc structure
631 * 3) only vertical or horizontal lines work
632 * -- should
633 * 1) represent Bezier arcs in BezierArc structure
634 * (this requires a multitude of changes to the code)
635 * 2) accept high degree Bezier arcs (hard)
636 * 3) map the curve onto the surface to determine tessellation
637 * 4) work for curves of arbitrary geometry
638 *----------------------------------------------------------------------------
639 */
640
641
642 void
643 Subdivider::tessellate( Bin& bin, REAL rrate, REAL trate, REAL lrate, REAL brate )
644 {
645 for( Arc_ptr jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
646 if( jarc->isbezier( ) ) {
647 assert( jarc->pwlArc->npts == 2 );
648 TrimVertex *pts = jarc->pwlArc->pts;
649 REAL s1 = pts[0].param[0];
650 REAL t1 = pts[0].param[1];
651 REAL s2 = pts[1].param[0];
652 REAL t2 = pts[1].param[1];
653
654 jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
655
656 switch( jarc->getside() ) {
657 case arc_left:
658 assert( s1 == s2 );
659 arctessellator.pwl_left( jarc, s1, t1, t2, lrate );
660 break;
661 case arc_right:
662 assert( s1 == s2 );
663 arctessellator.pwl_right( jarc, s1, t1, t2, rrate );
664 break;
665 case arc_top:
666 assert( t1 == t2 );
667 arctessellator.pwl_top( jarc, t1, s1, s2, trate );
668 break;
669 case arc_bottom:
670 assert( t1 == t2 );
671 arctessellator.pwl_bottom( jarc, t1, s1, s2, brate );
672 break;
673 case arc_none:
674 (void) abort();
675 break;
676 }
677 assert( ! jarc->isbezier() );
678 assert( jarc->check() );
679 }
680 }
681 }