FreeWRL / FreeX3D 4.3.0
mesher.cc
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 * mesher.c++
37 *
38 */
39
40#include "glimports.h"
41#include "myassert.h"
42#include "mystdio.h"
43#include "gridvertex.h"
44#include "gridtrimvertex.h"
45#include "jarcloc.h"
46#include "gridline.h"
47#include "trimline.h"
48#include "uarray.h"
49#include "backend.h"
50#include "mesher.h"
51
52
53const float Mesher::ZERO = 0.0;
54
55Mesher::Mesher( Backend& b )
56 : backend( b ),
57 p( sizeof( GridTrimVertex ), 100, "GridTrimVertexPool" )
58{
59 stacksize = 0;
60 vdata = 0;
61 lastedge = 0; //needed to prevent purify UMR
62}
63
64Mesher::~Mesher( void )
65{
66 if( vdata ) delete[] vdata;
67}
68
69void
70Mesher::init( unsigned int npts )
71{
72 p.clear();
73 if( stacksize < npts ) {
74 stacksize = 2 * npts;
75 if( vdata ) delete[] vdata;
76 vdata = new GridTrimVertex_p[stacksize];
77 }
78}
79
80inline void
81Mesher::push( GridTrimVertex *gt )
82{
83 assert( itop+1 != (int)stacksize );
84 vdata[++itop] = gt;
85}
86
87inline void
88Mesher::pop( long )
89{
90}
91
92inline void
93Mesher::openMesh()
94{
95 backend.bgntmesh( "addedge" );
96}
97
98inline void
99Mesher::closeMesh()
100{
101 backend.endtmesh();
102}
103
104inline void
105Mesher::swapMesh()
106{
107 backend.swaptmesh();
108}
109
110inline void
111Mesher::clearStack()
112{
113 itop = -1;
114 last[0] = 0;
115}
116
117void
118Mesher::finishLower( GridTrimVertex *gtlower )
119{
120 for( push(gtlower);
121 nextlower( gtlower=new(p) GridTrimVertex );
122 push(gtlower) )
123 addLower();
124 addLast();
125}
126
127void
128Mesher::finishUpper( GridTrimVertex *gtupper )
129{
130 for( push(gtupper);
131 nextupper( gtupper=new(p) GridTrimVertex );
132 push(gtupper) )
133 addUpper();
134 addLast();
135}
136
137void
138Mesher::mesh( void )
139{
140 GridTrimVertex *gtlower, *gtupper;
141
142 Hull::init( );
143 nextupper( gtupper = new(p) GridTrimVertex );
144 nextlower( gtlower = new(p) GridTrimVertex );
145
146 clearStack();
147 openMesh();
148 push(gtupper);
149
150 nextupper( gtupper = new(p) GridTrimVertex );
151 nextlower( gtlower );
152
153 assert( gtupper->t && gtlower->t );
154
155 if( gtupper->t->param[0] < gtlower->t->param[0] ) {
156 push(gtupper);
157 lastedge = 1;
158 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
159 finishLower(gtlower);
160 return;
161 }
162 } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
163 push(gtlower);
164 lastedge = 0;
165 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
166 finishUpper(gtupper);
167 return;
168 }
169 } else {
170 if( lastedge == 0 ) {
171 push(gtupper);
172 lastedge = 1;
173 if( nextupper(gtupper=new(p) GridTrimVertex) == 0 ) {
174 finishLower(gtlower);
175 return;
176 }
177 } else {
178 push(gtlower);
179 lastedge = 0;
180 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
181 finishUpper(gtupper);
182 return;
183 }
184 }
185 }
186
187 while ( 1 ) {
188 if( gtupper->t->param[0] < gtlower->t->param[0] ) {
189 push(gtupper);
190 addUpper();
191 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
192 finishLower(gtlower);
193 return;
194 }
195 } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
196 push(gtlower);
197 addLower();
198 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
199 finishUpper(gtupper);
200 return;
201 }
202 } else {
203 if( lastedge == 0 ) {
204 push(gtupper);
205 addUpper();
206 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
207 finishLower(gtlower);
208 return;
209 }
210 } else {
211 push(gtlower);
212 addLower();
213 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
214 finishUpper(gtupper);
215 return;
216 }
217 }
218 }
219 }
220}
221
222inline int
223Mesher::isCcw( int ilast )
224{
225 REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
226 return (area < ZERO) ? 0 : 1;
227}
228
229inline int
230Mesher::isCw( int ilast )
231{
232 REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
233 return (area > -ZERO) ? 0 : 1;
234}
235
236inline int
237Mesher::equal( int x, int y )
238{
239 return( last[0] == vdata[x] && last[1] == vdata[y] );
240}
241
242inline void
243Mesher::copy( int x, int y )
244{
245 last[0] = vdata[x]; last[1] = vdata[y];
246}
247
248inline void
249Mesher::move( int x, int y )
250{
251 vdata[x] = vdata[y];
252}
253
254inline void
255Mesher::output( int x )
256{
257 backend.tmeshvert( vdata[x] );
258}
259
260/*---------------------------------------------------------------------------
261 * addedge - addedge an edge to the triangulation
262 *
263 * This code has been re-written to generate large triangle meshes
264 * from a monotone polygon. Although smaller triangle meshes
265 * could be generated faster and with less code, larger meshes
266 * actually give better SYSTEM performance. This is because
267 * vertices are processed in the backend slower than they are
268 * generated by this code and any decrease in the number of vertices
269 * results in a decrease in the time spent in the backend.
270 *---------------------------------------------------------------------------
271 */
272
273void
274Mesher::addLast( )
275{
276 register int ilast = itop;
277
278 if( lastedge == 0 ) {
279 if( equal( 0, 1 ) ) {
280 output( ilast );
281 swapMesh();
282 for( register int i = 2; i < ilast; i++ ) {
283 swapMesh();
284 output( i );
285 }
286 copy( ilast, ilast-1 );
287 } else if( equal( ilast-2, ilast-1) ) {
288 swapMesh();
289 output( ilast );
290 for( register int i = ilast-3; i >= 0; i-- ) {
291 output( i );
292 swapMesh();
293 }
294 copy( 0, ilast );
295 } else {
296 closeMesh(); openMesh();
297 output( ilast );
298 output( 0 );
299 for( register int i = 1; i < ilast; i++ ) {
300 swapMesh();
301 output( i );
302 }
303 copy( ilast, ilast-1 );
304 }
305 } else {
306 if( equal( 1, 0) ) {
307 swapMesh();
308 output( ilast );
309 for( register int i = 2; i < ilast; i++ ) {
310 output( i );
311 swapMesh();
312 }
313 copy( ilast-1, ilast );
314 } else if( equal( ilast-1, ilast-2) ) {
315 output( ilast );
316 swapMesh();
317 for( register int i = ilast-3; i >= 0; i-- ) {
318 swapMesh();
319 output( i );
320 }
321 copy( ilast, 0 );
322 } else {
323 closeMesh(); openMesh();
324 output( 0 );
325 output( ilast );
326 for( register int i = 1; i < ilast; i++ ) {
327 output( i );
328 swapMesh();
329 }
330 copy( ilast-1, ilast );
331 }
332 }
333 closeMesh();
334 //for( register long k=0; k<=ilast; k++ ) pop( k );
335}
336
337void
338Mesher::addUpper( )
339{
340 register int ilast = itop;
341
342 if( lastedge == 0 ) {
343 if( equal( 0, 1 ) ) {
344 output( ilast );
345 swapMesh();
346 for( register int i = 2; i < ilast; i++ ) {
347 swapMesh();
348 output( i );
349 }
350 copy( ilast, ilast-1 );
351 } else if( equal( ilast-2, ilast-1) ) {
352 swapMesh();
353 output( ilast );
354 for( register int i = ilast-3; i >= 0; i-- ) {
355 output( i );
356 swapMesh();
357 }
358 copy( 0, ilast );
359 } else {
360 closeMesh(); openMesh();
361 output( ilast );
362 output( 0 );
363 for( register int i = 1; i < ilast; i++ ) {
364 swapMesh();
365 output( i );
366 }
367 copy( ilast, ilast-1 );
368 }
369 lastedge = 1;
370 //for( register long k=0; k<ilast-1; k++ ) pop( k );
371 move( 0, ilast-1 );
372 move( 1, ilast );
373 itop = 1;
374 } else {
375 if( ! isCcw( ilast ) ) return;
376 do {
377 itop--;
378 } while( (itop > 1) && isCcw( ilast ) );
379
380 if( equal( ilast-1, ilast-2 ) ) {
381 output( ilast );
382 swapMesh();
383 for( register int i=ilast-3; i>=itop-1; i-- ) {
384 swapMesh();
385 output( i );
386 }
387 copy( ilast, itop-1 );
388 } else if( equal( itop, itop-1 ) ) {
389 swapMesh();
390 output( ilast );
391 for( register int i = itop+1; i < ilast; i++ ) {
392 output( i );
393 swapMesh();
394 }
395 copy( ilast-1, ilast );
396 } else {
397 closeMesh(); openMesh();
398 output( ilast );
399 output( ilast-1 );
400 for( register int i=ilast-2; i>=itop-1; i-- ) {
401 swapMesh();
402 output( i );
403 }
404 copy( ilast, itop-1 );
405 }
406 //for( register int k=itop; k<ilast; k++ ) pop( k );
407 move( itop, ilast );
408 }
409}
410
411void
412Mesher::addLower()
413{
414 register int ilast = itop;
415
416 if( lastedge == 1 ) {
417 if( equal( 1, 0) ) {
418 swapMesh();
419 output( ilast );
420 for( register int i = 2; i < ilast; i++ ) {
421 output( i );
422 swapMesh();
423 }
424 copy( ilast-1, ilast );
425 } else if( equal( ilast-1, ilast-2) ) {
426 output( ilast );
427 swapMesh();
428 for( register int i = ilast-3; i >= 0; i-- ) {
429 swapMesh();
430 output( i );
431 }
432 copy( ilast, 0 );
433 } else {
434 closeMesh(); openMesh();
435 output( 0 );
436 output( ilast );
437 for( register int i = 1; i < ilast; i++ ) {
438 output( i );
439 swapMesh();
440 }
441 copy( ilast-1, ilast );
442 }
443
444 lastedge = 0;
445 //for( register long k=0; k<ilast-1; k++ ) pop( k );
446 move( 0, ilast-1 );
447 move( 1, ilast );
448 itop = 1;
449 } else {
450 if( ! isCw( ilast ) ) return;
451 do {
452 itop--;
453 } while( (itop > 1) && isCw( ilast ) );
454
455 if( equal( ilast-2, ilast-1) ) {
456 swapMesh();
457 output( ilast );
458 for( register int i=ilast-3; i>=itop-1; i--) {
459 output( i );
460 swapMesh( );
461 }
462 copy( itop-1, ilast );
463 } else if( equal( itop-1, itop) ) {
464 output( ilast );
465 swapMesh();
466 for( register int i=itop+1; i<ilast; i++ ) {
467 swapMesh( );
468 output( i );
469 }
470 copy( ilast, ilast-1 );
471 } else {
472 closeMesh(); openMesh();
473 output( ilast-1 );
474 output( ilast );
475 for( register int i=ilast-2; i>=itop-1; i-- ) {
476 output( i );
477 swapMesh( );
478 }
479 copy( itop-1, ilast );
480 }
481 //for( register int k=itop; k<ilast; k++ ) pop( k );
482 move( itop, ilast );
483 }
484}
485
486