source: trunk/src/opengl/glu/nurbs/internals/mesher.cpp

Last change on this file was 2689, checked in by jeroen, 26 years ago

* empty log message *
File size: 10.9 KB
Line 
1/* $Id: mesher.cpp,v 1.1 2000-02-09 08:50:25 jeroen Exp $ */
2/*
3** License Applicability. Except to the extent portions of this file are
4** made subject to an alternative license as permitted in the SGI Free
5** Software License B, Version 1.0 (the "License"), the contents of this
6** file are subject only to the provisions of the License. You may not use
7** this file except in compliance with the License. You may obtain a copy
8** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
9** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10**
11** http://oss.sgi.com/projects/FreeB
12**
13** Note that, as provided in the License, the Software is distributed on an
14** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
15** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
16** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
17** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18**
19** Original Code. The Original Code is: OpenGL Sample Implementation,
20** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
21** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
22** Copyright in any portions created by third parties is as indicated
23** elsewhere herein. All Rights Reserved.
24**
25** Additional Notice Provisions: The application programming interfaces
26** established by SGI in conjunction with the Original Code are The
27** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
28** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
29** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
30** Window System(R) (Version 1.3), released October 19, 1998. This software
31** was created using the OpenGL(R) version 1.2.1 Sample Implementation
32** published by SGI, but has not been independently verified as being
33** compliant with the OpenGL(R) version 1.2.1 Specification.
34*/
35
36/*
37 * mesher.c++
38 *
39 * $Date: 2000-02-09 08:50:25 $ $Revision: 1.1 $
40 * $Header: /home/ktk/tmp/odin/2007/netlabs.cvs/odin32/src/opengl/glu/nurbs/internals/mesher.cpp,v 1.1 2000-02-09 08:50:25 jeroen Exp $
41 */
42
43#include "glimports.h"
44#include "myassert.h"
45#include "mystdio.h"
46#include "mesher.h"
47#include "gridvertex.h"
48#include "gridtrimvertex.h"
49#include "jarcloc.h"
50#include "gridline.h"
51#include "trimline.h"
52#include "uarray.h"
53#include "backend.h"
54
55
56const float Mesher::ZERO = 0.0;
57
58Mesher::Mesher( Backend& b )
59 : backend( b ),
60 p( sizeof( GridTrimVertex ), 100, "GridTrimVertexPool" )
61{
62 stacksize = 0;
63 vdata = 0;
64 lastedge = 0; //needed to prevent purify UMR
65}
66
67Mesher::~Mesher( void )
68{
69 if( vdata ) delete[] vdata;
70}
71
72void
73Mesher::init( unsigned int npts )
74{
75 p.clear();
76 if( stacksize < npts ) {
77 stacksize = 2 * npts;
78 if( vdata ) delete[] vdata;
79 vdata = new GridTrimVertex_p[stacksize];
80 }
81}
82
83inline void
84Mesher::push( GridTrimVertex *gt )
85{
86 assert( itop+1 != stacksize );
87 vdata[++itop] = gt;
88}
89
90inline void
91Mesher::pop( long )
92{
93}
94
95inline void
96Mesher::openMesh()
97{
98 backend.bgntmesh( "addedge" );
99}
100
101inline void
102Mesher::closeMesh()
103{
104 backend.endtmesh();
105}
106
107inline void
108Mesher::swapMesh()
109{
110 backend.swaptmesh();
111}
112
113inline void
114Mesher::clearStack()
115{
116 itop = -1;
117 last[0] = 0;
118}
119
120void
121Mesher::finishLower( GridTrimVertex *gtlower )
122{
123 for( push(gtlower);
124 nextlower( gtlower=new(p) GridTrimVertex );
125 push(gtlower) )
126 addLower();
127 addLast();
128}
129
130void
131Mesher::finishUpper( GridTrimVertex *gtupper )
132{
133 for( push(gtupper);
134 nextupper( gtupper=new(p) GridTrimVertex );
135 push(gtupper) )
136 addUpper();
137 addLast();
138}
139
140void
141Mesher::mesh( void )
142{
143 GridTrimVertex *gtlower, *gtupper;
144
145 Hull::init( );
146 nextupper( gtupper = new(p) GridTrimVertex );
147 nextlower( gtlower = new(p) GridTrimVertex );
148
149 clearStack();
150 openMesh();
151 push(gtupper);
152
153 nextupper( gtupper = new(p) GridTrimVertex );
154 nextlower( gtlower );
155
156 assert( gtupper->t && gtlower->t );
157
158 if( gtupper->t->param[0] < gtlower->t->param[0] ) {
159 push(gtupper);
160 lastedge = 1;
161 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
162 finishLower(gtlower);
163 return;
164 }
165 } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
166 push(gtlower);
167 lastedge = 0;
168 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
169 finishUpper(gtupper);
170 return;
171 }
172 } else {
173 if( lastedge == 0 ) {
174 push(gtupper);
175 lastedge = 1;
176 if( nextupper(gtupper=new(p) GridTrimVertex) == 0 ) {
177 finishLower(gtlower);
178 return;
179 }
180 } else {
181 push(gtlower);
182 lastedge = 0;
183 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
184 finishUpper(gtupper);
185 return;
186 }
187 }
188 }
189
190 while ( 1 ) {
191 if( gtupper->t->param[0] < gtlower->t->param[0] ) {
192 push(gtupper);
193 addUpper();
194 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
195 finishLower(gtlower);
196 return;
197 }
198 } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
199 push(gtlower);
200 addLower();
201 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
202 finishUpper(gtupper);
203 return;
204 }
205 } else {
206 if( lastedge == 0 ) {
207 push(gtupper);
208 addUpper();
209 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
210 finishLower(gtlower);
211 return;
212 }
213 } else {
214 push(gtlower);
215 addLower();
216 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
217 finishUpper(gtupper);
218 return;
219 }
220 }
221 }
222 }
223}
224
225inline int
226Mesher::isCcw( int ilast )
227{
228 REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
229 return (area < ZERO) ? 0 : 1;
230}
231
232inline int
233Mesher::isCw( int ilast )
234{
235 REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
236 return (area > -ZERO) ? 0 : 1;
237}
238
239inline int
240Mesher::equal( int x, int y )
241{
242 return( last[0] == vdata[x] && last[1] == vdata[y] );
243}
244
245inline void
246Mesher::copy( int x, int y )
247{
248 last[0] = vdata[x]; last[1] = vdata[y];
249}
250
251inline void
252Mesher::move( int x, int y )
253{
254 vdata[x] = vdata[y];
255}
256
257inline void
258Mesher::output( int x )
259{
260 backend.tmeshvert( vdata[x] );
261}
262
263/*---------------------------------------------------------------------------
264 * addedge - addedge an edge to the triangulation
265 *
266 * This code has been re-written to generate large triangle meshes
267 * from a monotone polygon. Although smaller triangle meshes
268 * could be generated faster and with less code, larger meshes
269 * actually give better SYSTEM performance. This is because
270 * vertices are processed in the backend slower than they are
271 * generated by this code and any decrease in the number of vertices
272 * results in a decrease in the time spent in the backend.
273 *---------------------------------------------------------------------------
274 */
275
276void
277Mesher::addLast( )
278{
279 register int ilast = itop;
280
281 if( lastedge == 0 ) {
282 if( equal( 0, 1 ) ) {
283 output( ilast );
284 swapMesh();
285 for( register int i = 2; i < ilast; i++ ) {
286 swapMesh();
287 output( i );
288 }
289 copy( ilast, ilast-1 );
290 } else if( equal( ilast-2, ilast-1) ) {
291 swapMesh();
292 output( ilast );
293 for( register int i = ilast-3; i >= 0; i-- ) {
294 output( i );
295 swapMesh();
296 }
297 copy( 0, ilast );
298 } else {
299 closeMesh(); openMesh();
300 output( ilast );
301 output( 0 );
302 for( register int i = 1; i < ilast; i++ ) {
303 swapMesh();
304 output( i );
305 }
306 copy( ilast, ilast-1 );
307 }
308 } else {
309 if( equal( 1, 0) ) {
310 swapMesh();
311 output( ilast );
312 for( register int i = 2; i < ilast; i++ ) {
313 output( i );
314 swapMesh();
315 }
316 copy( ilast-1, ilast );
317 } else if( equal( ilast-1, ilast-2) ) {
318 output( ilast );
319 swapMesh();
320 for( register int i = ilast-3; i >= 0; i-- ) {
321 swapMesh();
322 output( i );
323 }
324 copy( ilast, 0 );
325 } else {
326 closeMesh(); openMesh();
327 output( 0 );
328 output( ilast );
329 for( register int i = 1; i < ilast; i++ ) {
330 output( i );
331 swapMesh();
332 }
333 copy( ilast-1, ilast );
334 }
335 }
336 closeMesh();
337 //for( register long k=0; k<=ilast; k++ ) pop( k );
338}
339
340void
341Mesher::addUpper( )
342{
343 register int ilast = itop;
344
345 if( lastedge == 0 ) {
346 if( equal( 0, 1 ) ) {
347 output( ilast );
348 swapMesh();
349 for( register int i = 2; i < ilast; i++ ) {
350 swapMesh();
351 output( i );
352 }
353 copy( ilast, ilast-1 );
354 } else if( equal( ilast-2, ilast-1) ) {
355 swapMesh();
356 output( ilast );
357 for( register int i = ilast-3; i >= 0; i-- ) {
358 output( i );
359 swapMesh();
360 }
361 copy( 0, ilast );
362 } else {
363 closeMesh(); openMesh();
364 output( ilast );
365 output( 0 );
366 for( register int i = 1; i < ilast; i++ ) {
367 swapMesh();
368 output( i );
369 }
370 copy( ilast, ilast-1 );
371 }
372 lastedge = 1;
373 //for( register long k=0; k<ilast-1; k++ ) pop( k );
374 move( 0, ilast-1 );
375 move( 1, ilast );
376 itop = 1;
377 } else {
378 if( ! isCcw( ilast ) ) return;
379 do {
380 itop--;
381 } while( (itop > 1) && isCcw( ilast ) );
382
383 if( equal( ilast-1, ilast-2 ) ) {
384 output( ilast );
385 swapMesh();
386 for( register int i=ilast-3; i>=itop-1; i-- ) {
387 swapMesh();
388 output( i );
389 }
390 copy( ilast, itop-1 );
391 } else if( equal( itop, itop-1 ) ) {
392 swapMesh();
393 output( ilast );
394 for( register int i = itop+1; i < ilast; i++ ) {
395 output( i );
396 swapMesh();
397 }
398 copy( ilast-1, ilast );
399 } else {
400 closeMesh(); openMesh();
401 output( ilast );
402 output( ilast-1 );
403 for( register int i=ilast-2; i>=itop-1; i-- ) {
404 swapMesh();
405 output( i );
406 }
407 copy( ilast, itop-1 );
408 }
409 //for( register int k=itop; k<ilast; k++ ) pop( k );
410 move( itop, ilast );
411 }
412}
413
414void
415Mesher::addLower()
416{
417 register int ilast = itop;
418
419 if( lastedge == 1 ) {
420 if( equal( 1, 0) ) {
421 swapMesh();
422 output( ilast );
423 for( register int i = 2; i < ilast; i++ ) {
424 output( i );
425 swapMesh();
426 }
427 copy( ilast-1, ilast );
428 } else if( equal( ilast-1, ilast-2) ) {
429 output( ilast );
430 swapMesh();
431 for( register int i = ilast-3; i >= 0; i-- ) {
432 swapMesh();
433 output( i );
434 }
435 copy( ilast, 0 );
436 } else {
437 closeMesh(); openMesh();
438 output( 0 );
439 output( ilast );
440 for( register int i = 1; i < ilast; i++ ) {
441 output( i );
442 swapMesh();
443 }
444 copy( ilast-1, ilast );
445 }
446
447 lastedge = 0;
448 //for( register long k=0; k<ilast-1; k++ ) pop( k );
449 move( 0, ilast-1 );
450 move( 1, ilast );
451 itop = 1;
452 } else {
453 if( ! isCw( ilast ) ) return;
454 do {
455 itop--;
456 } while( (itop > 1) && isCw( ilast ) );
457
458 if( equal( ilast-2, ilast-1) ) {
459 swapMesh();
460 output( ilast );
461 for( register int i=ilast-3; i>=itop-1; i--) {
462 output( i );
463 swapMesh( );
464 }
465 copy( itop-1, ilast );
466 } else if( equal( itop-1, itop) ) {
467 output( ilast );
468 swapMesh();
469 for( register int i=itop+1; i<ilast; i++ ) {
470 swapMesh( );
471 output( i );
472 }
473 copy( ilast, ilast-1 );
474 } else {
475 closeMesh(); openMesh();
476 output( ilast-1 );
477 output( ilast );
478 for( register int i=ilast-2; i>=itop-1; i-- ) {
479 output( i );
480 swapMesh( );
481 }
482 copy( itop-1, ilast );
483 }
484 //for( register int k=itop; k<ilast; k++ ) pop( k );
485 move( itop, ilast );
486 }
487}
488
489
Note: See TracBrowser for help on using the repository browser.