ReactOS  0.4.14-dev-98-gb0d4763
bezier.c
Go to the documentation of this file.
1 /*
2  * COPYRIGHT: GNU LGPL
3  * PURPOSE: Bezier functions
4  */
5 
6 #include <win32k.h>
7 
8 #define NDEBUG
9 #include <debug.h>
10 
11 /* Based on Wine Staging 1.7.37 - dlls/gdi32/painting.c */
12 
13 /******************************************************************
14  *
15  * *Very* simple bezier drawing code,
16  *
17  * It uses a recursive algorithm to divide the curve in a series
18  * of straight line segments. Not ideal but sufficient for me.
19  * If you are in need for something better look for some incremental
20  * algorithm.
21  *
22  * 7 July 1998 Rein Klazes
23  */
24 
25  /*
26  * some macro definitions for bezier drawing
27  *
28  * to avoid truncation errors the coordinates are
29  * shifted upwards. When used in drawing they are
30  * shifted down again, including correct rounding
31  * and avoiding floating point arithmetic
32  * 4 bits should allow 27 bits coordinates which I saw
33  * somewhere in the win32 doc's
34  *
35  */
36 
37 #define BEZIERSHIFTBITS 4
38 #define BEZIERSHIFTUP(x) ((x)<<BEZIERSHIFTBITS)
39 #define BEZIERPIXEL BEZIERSHIFTUP(1)
40 #define BEZIERSHIFTDOWN(x) (((x)+(1<<(BEZIERSHIFTBITS-1)))>>BEZIERSHIFTBITS)
41 /* maximum depth of recursion */
42 #define BEZIERMAXDEPTH 8
43 
44 /* size of array to store points on */
45 /* enough for one curve */
46 #define BEZIER_INITBUFSIZE (150)
47 
48 /* calculate Bezier average, in this case the middle
49  * correctly rounded...
50  * */
51 
52 #define BEZIERMIDDLE(Mid, P1, P2) \
53  (Mid).x=((P1).x+(P2).x + 1)/2;\
54  (Mid).y=((P1).y+(P2).y + 1)/2;
55 
56 /**********************************************************
57 * BezierCheck helper function to check
58 * that recursion can be terminated
59 * Points[0] and Points[3] are begin and endpoint
60 * Points[1] and Points[2] are control points
61 * level is the recursion depth
62 * returns true if the recursion can be terminated
63 */
64 static BOOL BezierCheck( int level, POINT *Points)
65 {
66  INT dx, dy;
67  dx=Points[3].x-Points[0].x;
68  dy=Points[3].y-Points[0].y;
69  if(abs(dy)<=abs(dx)){/* shallow line */
70  /* check that control points are between begin and end */
71  if(Points[1].x < Points[0].x){
72  if(Points[1].x < Points[3].x)
73  return FALSE;
74  }else
75  if(Points[1].x > Points[3].x)
76  return FALSE;
77  if(Points[2].x < Points[0].x){
78  if(Points[2].x < Points[3].x)
79  return FALSE;
80  }else
81  if(Points[2].x > Points[3].x)
82  return FALSE;
84  if(!dx) return TRUE;
85  if(abs(Points[1].y-Points[0].y-(dy/dx)*
86  BEZIERSHIFTDOWN(Points[1].x-Points[0].x)) > BEZIERPIXEL ||
87  abs(Points[2].y-Points[0].y-(dy/dx)*
88  BEZIERSHIFTDOWN(Points[2].x-Points[0].x)) > BEZIERPIXEL )
89  return FALSE;
90  else
91  return TRUE;
92  }else{ /* steep line */
93  /* check that control points are between begin and end */
94  if(Points[1].y < Points[0].y){
95  if(Points[1].y < Points[3].y)
96  return FALSE;
97  }else
98  if(Points[1].y > Points[3].y)
99  return FALSE;
100  if(Points[2].y < Points[0].y){
101  if(Points[2].y < Points[3].y)
102  return FALSE;
103  }else
104  if(Points[2].y > Points[3].y)
105  return FALSE;
107  if(!dy) return TRUE;
108  if(abs(Points[1].x-Points[0].x-(dx/dy)*
109  BEZIERSHIFTDOWN(Points[1].y-Points[0].y)) > BEZIERPIXEL ||
110  abs(Points[2].x-Points[0].x-(dx/dy)*
111  BEZIERSHIFTDOWN(Points[2].y-Points[0].y)) > BEZIERPIXEL )
112  return FALSE;
113  else
114  return TRUE;
115  }
116 }
117 
118 /* Helper for GDI_Bezier.
119  * Just handles one Bezier, so Points should point to four POINTs
120  */
121 static void GDI_InternalBezier( POINT *Points, POINT **PtsOut, INT *dwOut,
122  INT *nPtsOut, INT level )
123 {
124  if(*nPtsOut == *dwOut) {
125  *dwOut *= 2;
126  *PtsOut = ExAllocatePoolWithTag(PagedPool, *dwOut * sizeof(POINT), TAG_BEZIER);
127  if (*PtsOut == NULL)
128  {
130  NT_ASSERT(FALSE);
131  return;
132  }
133  }
134 
135  if(!level || BezierCheck(level, Points)) {
136  if(*nPtsOut == 0) {
137  (*PtsOut)[0].x = BEZIERSHIFTDOWN(Points[0].x);
138  (*PtsOut)[0].y = BEZIERSHIFTDOWN(Points[0].y);
139  *nPtsOut = 1;
140  }
141  (*PtsOut)[*nPtsOut].x = BEZIERSHIFTDOWN(Points[3].x);
142  (*PtsOut)[*nPtsOut].y = BEZIERSHIFTDOWN(Points[3].y);
143  (*nPtsOut) ++;
144  } else {
145  POINT Points2[4]; /* for the second recursive call */
146  Points2[3]=Points[3];
147  BEZIERMIDDLE(Points2[2], Points[2], Points[3]);
148  BEZIERMIDDLE(Points2[0], Points[1], Points[2]);
149  BEZIERMIDDLE(Points2[1],Points2[0],Points2[2]);
150 
151  BEZIERMIDDLE(Points[1], Points[0], Points[1]);
152  BEZIERMIDDLE(Points[2], Points[1], Points2[0]);
153  BEZIERMIDDLE(Points[3], Points[2], Points2[1]);
154 
155  Points2[0]=Points[3];
156 
157  /* do the two halves */
158  GDI_InternalBezier(Points, PtsOut, dwOut, nPtsOut, level-1);
159  GDI_InternalBezier(Points2, PtsOut, dwOut, nPtsOut, level-1);
160  }
161 }
162 
163 
164 
165 /***********************************************************************
166  * GDI_Bezier [INTERNAL]
167  * Calculate line segments that approximate -what microsoft calls- a bezier
168  * curve.
169  * The routine recursively divides the curve in two parts until a straight
170  * line can be drawn
171  *
172  * PARAMS
173  *
174  * Points [I] Ptr to count POINTs which are the end and control points
175  * of the set of Bezier curves to flatten.
176  * count [I] Number of Points. Must be 3n+1.
177  * nPtsOut [O] Will contain no of points that have been produced (i.e. no. of
178  * lines+1).
179  *
180  * RETURNS
181  *
182  * Ptr to an array of POINTs that contain the lines that approximate the
183  * Beziers. The array is allocated on the process heap and it is the caller's
184  * responsibility to HeapFree it. [this is not a particularly nice interface
185  * but since we can't know in advance how many points we will generate, the
186  * alternative would be to call the function twice, once to determine the size
187  * and a second time to do the work - I decided this was too much of a pain].
188  */
189 POINT *GDI_Bezier( const POINT *Points, INT count, INT *nPtsOut )
190 {
191  POINT *out;
192  INT Bezier, dwOut = BEZIER_INITBUFSIZE, i;
193 
194  if (count == 1 || (count - 1) % 3 != 0) {
195  DPRINT1("Invalid no. of points %d\n", count);
196  return NULL;
197  }
198  *nPtsOut = 0;
199 
200  out = ExAllocatePoolWithTag(PagedPool, dwOut * sizeof(POINT), TAG_BEZIER);
201  if (!out) return NULL;
202 
203  for(Bezier = 0; Bezier < (count-1)/3; Bezier++) {
204  POINT ptBuf[4];
205  memcpy(ptBuf, Points + Bezier * 3, sizeof(POINT) * 4);
206  for(i = 0; i < 4; i++) {
207  ptBuf[i].x = BEZIERSHIFTUP(ptBuf[i].x);
208  ptBuf[i].y = BEZIERSHIFTUP(ptBuf[i].y);
209  }
210  GDI_InternalBezier( ptBuf, &out, &dwOut, nPtsOut, BEZIERMAXDEPTH );
211  }
212  DPRINT("Produced %d points\n", *nPtsOut);
213  return out;
214 }
215 /* EOF */
static void GDI_InternalBezier(POINT *Points, POINT **PtsOut, INT *dwOut, INT *nPtsOut, INT level)
Definition: bezier.c:121
#define abs(i)
Definition: fconv.c:206
GLint level
Definition: gl.h:1546
#define TRUE
Definition: types.h:120
long y
Definition: polytest.cpp:48
long x
Definition: polytest.cpp:48
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLint dy
Definition: linetemp.h:97
#define BEZIERMAXDEPTH
Definition: bezier.c:42
#define BEZIER_INITBUFSIZE
Definition: bezier.c:46
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
#define BEZIERSHIFTUP(x)
Definition: bezier.c:38
void Bezier(HDC hdc, POINT p1, POINT p2, POINT p3, POINT p4, COLORREF color, int thickness)
Definition: drawing.cpp:95
int32_t INT
Definition: typedefs.h:56
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
unsigned int BOOL
Definition: ntddk_ex.h:94
#define TAG_BEZIER
Definition: tags.h:13
smooth NULL
Definition: ftsmooth.c:416
void DPRINT(...)
Definition: polytest.cpp:61
#define BEZIERSHIFTDOWN(x)
Definition: bezier.c:40
static FILE * out
Definition: regtests2xml.c:44
POINT * GDI_Bezier(const POINT *Points, INT count, INT *nPtsOut)
Definition: bezier.c:189
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
static BOOL BezierCheck(int level, POINT *Points)
Definition: bezier.c:64
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLint dx
Definition: linetemp.h:97
#define DPRINT1
Definition: precomp.h:8
#define BEZIERPIXEL
Definition: bezier.c:39
#define BEZIERMIDDLE(Mid, P1, P2)
Definition: bezier.c:52
#define NT_ASSERT
Definition: rtlfuncs.h:3312