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 * monotonizer.c++
37 *
38 */
39
40#include "glimports.h"
41#include "mystdio.h"
42#include "myassert.h"
43#include "arc.h"
44#include "arctess.h"
45#include "bezierarc.h"
46#include "bin.h"
47#include "mapdesc.h"
48#include "nurbsconsts.h"
49#include "subdivider.h"
50
51/*-----------------------------------------------------------------------------
52 * Subdivider::decompose - break all curves into monotone arcs
53 *-----------------------------------------------------------------------------
54 */
55int
56Subdivider::decompose( Bin& bin, REAL geo_stepsize )
57{
58    Arc_ptr jarc;
59    for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
60	if( ! jarc->isTessellated() ) {
61	    /* points have not been transformed, therefore they may be either
62	       homogeneous or inhomogeneous */
63	    tessellate( jarc, geo_stepsize );
64	    if( jarc->isDisconnected() || jarc->next->isDisconnected() )
65		return 1;
66	}
67    }
68
69    for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
70	monotonize( jarc, bin );
71    }
72
73#ifndef NDEBUG
74    for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
75	assert( isMonotone( jarc ) != 0 );
76    }
77#endif
78
79    return 0;
80}
81
82void
83Subdivider::tessellate( Arc_ptr jarc, REAL geo_stepsize )
84{
85    BezierArc *b = jarc->bezierArc;
86    Mapdesc *mapdesc = b->mapdesc;
87
88    if( mapdesc->isRational() ) {
89	REAL max = mapdesc->calcVelocityRational( b->cpts, b->stride, b->order );
90	REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0;
91	if( jarc->bezierArc->order != 2 )
92	    arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 1 );
93	else {
94	    arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 1 );
95	}
96    } else {
97	REAL max = mapdesc->calcVelocityNonrational( b->cpts, b->stride, b->order );
98	REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0;
99	if( jarc->bezierArc->order != 2 )
100	    arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 0 );
101	else {
102	    arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 0 );
103	}
104    }
105}
106
107/*-------------------------------------------------------------------------
108 * Subdivider::monotonize - break up a jordan arc into s,t-monotone
109 *	components.  This code will remove degenerate segments, including
110 *	arcs of only a single point.
111 *-------------------------------------------------------------------------
112 */
113void
114Subdivider::monotonize( Arc_ptr jarc, Bin& bin )
115{
116    TrimVertex  *firstvert = jarc->pwlArc->pts;
117    TrimVertex  *lastvert = firstvert + (jarc->pwlArc->npts - 1);
118    long	uid = jarc->nuid;
119    arc_side	side = jarc->getside();
120    dir		sdir = none;
121    dir		tdir = none;
122    int 	degenerate = 1;
123
124    int		nudegenerate;
125    int		change;
126
127    TrimVertex *vert;
128    for( vert = firstvert; vert != lastvert; vert++ ) {
129
130        nudegenerate = 1;
131        change = 0;
132
133	/* check change relative to s axis, clear degenerate bit if needed */
134        REAL sdiff = vert[1].param[0] - vert[0].param[0];
135        if( sdiff == 0 ) {
136	    if( sdir != same ) {
137	        sdir = same;
138		change = 1;
139	    }
140        } else if( sdiff < 0.0 ) {
141	    if( sdir != down ) {
142	        sdir = down;
143		change = 1;
144	    }
145	    nudegenerate = 0;
146        } else {
147	    if( sdir != up ) {
148	        sdir = up;
149		change = 1;
150	    }
151	    nudegenerate = 0;
152        }
153
154	/* check change relative to t axis, clear degenerate bit if needed */
155        REAL tdiff = vert[1].param[1] - vert[0].param[1];
156        if( tdiff == 0 ) {
157	    if( tdir != same ) {
158	        tdir = same;
159	 	change = 1;
160	    }
161        } else if( tdiff < 0.0 ) {
162	    if( tdir != down ) {
163	        tdir = down;
164		change = 1;
165	    }
166	    nudegenerate = 0;
167        } else {
168	    if( tdir != up ) {
169	        tdir = up;
170		change = 1;
171	    }
172	    nudegenerate = 0;
173        }
174
175	if( change ) {
176	    if( ! degenerate ) {
177	        /* make last segment into separate pwl curve */
178	        jarc->pwlArc->npts = vert - firstvert + 1;
179	        jarc = (new(arcpool) Arc( side, uid ))->append( jarc );
180	        jarc->pwlArc = new(pwlarcpool) PwlArc();
181		bin.addarc( jarc );
182	    }
183	    firstvert = jarc->pwlArc->pts = vert;
184	    degenerate = nudegenerate;
185	}
186    }
187    jarc->pwlArc->npts = vert - firstvert + 1;
188
189    if( degenerate ) {
190	/* remove jarc from circularly linked list */
191	jarc->prev->next = jarc->next;
192	jarc->next->prev = jarc->prev;
193
194        assert( jarc->prev->check(  ) != 0 );
195        assert( jarc->next->check(  ) != 0 );
196
197	/* remove jarc from bin */
198	bin.remove_this_arc( jarc  );
199
200	jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
201	jarc->deleteMe( arcpool );
202    }
203}
204
205/*-------------------------------------------------------------------------
206 * Subdivider::isMonotone - return true if arc is monotone AND non-degenerate
207 *-------------------------------------------------------------------------
208 */
209int
210Subdivider::isMonotone( Arc_ptr jarc )
211{
212    TrimVertex  *firstvert = jarc->pwlArc->pts;
213    TrimVertex  *lastvert = firstvert + (jarc->pwlArc->npts - 1);
214
215    if( firstvert == lastvert ) return 1;
216
217    TrimVertex	*vert = firstvert;
218    enum dir	sdir;
219    enum dir	tdir;
220
221    REAL diff = vert[1].param[0] - vert[0].param[0];
222    if( diff == 0.0 )
223        sdir = same;
224    else if( diff < 0.0 )
225        sdir = down;
226    else
227        sdir = up;
228
229    diff = vert[1].param[1] - vert[0].param[1];
230    if( diff == 0.0 )
231        tdir = same;
232    else if( diff < 0.0 )
233        tdir = down;
234    else
235        tdir = up;
236
237    if( (sdir == same) && (tdir == same) ) return 0;
238
239    for( ++vert ; vert != lastvert; vert++ ) {
240        diff = vert[1].param[0] - vert[0].param[0];
241        if( diff == 0.0 ) {
242	    if( sdir != same ) return 0;
243        } else if( diff < 0.0 ) {
244	    if( sdir != down ) return 0;
245        } else {
246	    if( sdir != up ) return 0;
247        }
248
249        diff = vert[1].param[1] - vert[0].param[1];
250        if( diff == 0.0 ) {
251	    if( tdir != same ) return 0;
252        } else if( diff < 0.0 ) {
253	    if( tdir != down ) return 0;
254        } else {
255	    if( tdir != up ) return 0;
256        }
257    }
258    return 1;
259}
260
261