← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/vnc4/gutsy

« back to all changes in this revision

Viewing changes to unix/xc/extras/ogl-sample/main/gfx/lib/glu/libnurbs/internals/mesher.cc

  • Committer: Bazaar Package Importer
  • Author(s): Ola Lundqvist
  • Date: 2006-05-15 20:35:17 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20060515203517-l4lre1ku942mn26k
Tags: 4.1.1+X4.3.0-10
* Correction of critical security issue. Thanks to Martin Kogler
  <e9925248@student.tuwien.ac.at> that informed me about the issue,
  and provided the patch.
  This flaw was originally found by Steve Wiseman of intelliadmin.com.
* Applied patch from Javier Kohen <jkohen@users.sourceforge.net> that
  inform the user that only 8 first characters of the password will
  actually be used when typing more than 8 characters, closes:
  #355619.

Show diffs side-by-side

added added

removed removed

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