ReactOS  0.4.15-dev-345-g5d88487
monotonizer.cc
Go to the documentation of this file.
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  */
55 int
56 Subdivider::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 
82 void
83 Subdivider::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  */
113 void
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  */
209 int
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 
void monotonize(Arc_ptr, Bin &)
Definition: monotonizer.cc:114
#define max(a, b)
Definition: svc.c:63
arc_side
Definition: arc.h:52
Definition: pwlarc.h:44
#define assert(x)
Definition: debug.h:53
REAL calcVelocityRational(REAL *, int, int)
Definition: mapdesc.cc:723
static void append(struct dump_context *dc, const void *data, unsigned size)
Definition: minidump.c:380
Pool pwlarcpool
Definition: subdivider.h:116
Pool arcpool
Definition: subdivider.h:114
void tessellateNonlinear(Arc_ptr, REAL, REAL, int)
Definition: arctess.cc:324
REAL calcVelocityNonrational(REAL *, int, int)
Definition: mapdesc.cc:744
BOOL WINAPI Arc(_In_ HDC hdc, _In_ INT xLeft, _In_ INT yTop, _In_ INT xRight, _In_ INT yBottom, _In_ INT xStartArc, _In_ INT yStartArc, _In_ INT xEndArc, _In_ INT yEndArc)
Definition: arc.c:5
void tessellateLinear(Arc_ptr, REAL, REAL, int)
Definition: arctess.cc:279
Definition: bin.h:43
void tessellate(Arc_ptr, REAL)
Definition: monotonizer.cc:83
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
long nuid
Definition: trimvertex.h:50
int isMonotone(Arc_ptr)
Definition: monotonizer.cc:210
ArcTessellator arctessellator
Definition: subdivider.h:113
class Arc * Arc_ptr
Definition: arc.h:50
int isRational(void)
Definition: mapdesc.h:192
REAL param[2]
Definition: trimvertex.h:45
static struct _PeImage bin
float REAL
Definition: types.h:41
int decompose(Bin &, REAL)
Definition: monotonizer.cc:56