ReactOS 0.4.15-dev-8102-g108db8f
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*/
64static 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 */
121static 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 {
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 */
189POINT *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
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 */
#define DPRINT1
Definition: precomp.h:8
#define BEZIERSHIFTUP(x)
Definition: bezier.c:38
static void GDI_InternalBezier(POINT *Points, POINT **PtsOut, INT *dwOut, INT *nPtsOut, INT level)
Definition: bezier.c:121
#define BEZIERMAXDEPTH
Definition: bezier.c:42
#define BEZIERPIXEL
Definition: bezier.c:39
static BOOL BezierCheck(int level, POINT *Points)
Definition: bezier.c:64
#define BEZIERMIDDLE(Mid, P1, P2)
Definition: bezier.c:52
POINT * GDI_Bezier(const POINT *Points, INT count, INT *nPtsOut)
Definition: bezier.c:189
#define BEZIER_INITBUFSIZE
Definition: bezier.c:46
#define BEZIERSHIFTDOWN(x)
Definition: bezier.c:40
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
void Bezier(HDC hdc, POINT p1, POINT p2, POINT p3, POINT p4, COLORREF color, int thickness)
Definition: drawing.cpp:93
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define PagedPool
Definition: env_spec_w32.h:308
#define abs(i)
Definition: fconv.c:206
unsigned int BOOL
Definition: ntddk_ex.h:94
GLint level
Definition: gl.h:1546
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLuint GLuint GLsizei count
Definition: gl.h:1545
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
GLint dy
Definition: linetemp.h:97
GLint dx
Definition: linetemp.h:97
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
static FILE * out
Definition: regtests2xml.c:44
#define DPRINT
Definition: sndvol32.h:73
long y
Definition: polytest.cpp:48
long x
Definition: polytest.cpp:48
int32_t INT
Definition: typedefs.h:58
#define TAG_BEZIER
Definition: tags.h:13
#define NT_ASSERT
Definition: rtlfuncs.h:3310