| author | ohair |
| Wed, 06 Apr 2011 22:06:11 -0700 | |
| changeset 9035 | 1255eb81cc2f |
| parent 8746 | 3eef91f87691 |
| child 21278 | ef8a3a2a72f2 |
| permissions | -rw-r--r-- |
| 2 | 1 |
/* |
|
9035
1255eb81cc2f
7033660: Update copyright year to 2011 on any files changed in 2011
ohair
parents:
8746
diff
changeset
|
2 |
* Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. |
| 2 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
| 5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
| 2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
| 5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
| 2 | 10 |
* |
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
| 5506 | 21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
| 2 | 24 |
*/ |
25 |
||
26 |
#include <math.h> |
|
27 |
#include <assert.h> |
|
28 |
#include <stdlib.h> |
|
29 |
#include <string.h> |
|
30 |
||
31 |
#include "j2d_md.h" |
|
32 |
#include "java_awt_geom_PathIterator.h" |
|
33 |
||
34 |
#include "ProcessPath.h" |
|
35 |
||
36 |
/* |
|
37 |
* This framework performs filling and drawing of paths with sub-pixel |
|
38 |
* precision. Also, it performs clipping by the specified view area. |
|
39 |
* |
|
40 |
* Drawing of the shapes is performed not pixel by pixel but segment by segment |
|
41 |
* except several pixels near endpoints of the drawn line. This approach saves |
|
42 |
* lot's of cpu cycles especially in case of large primitives (like ovals with |
|
43 |
* sizes more than 50) and helps in achieving appropriate visual quality. Also, |
|
44 |
* such method of drawing is useful for the accelerated pipelines where |
|
45 |
* overhead of the per-pixel drawing could eliminate all benefits of the |
|
46 |
* hardware acceleration. |
|
47 |
* |
|
48 |
* Filling of the path was taken from |
|
49 |
* |
|
50 |
* [Graphics Gems, edited by Andrew S Glassner. Academic Press 1990, |
|
51 |
* ISBN 0-12-286165-5 (Concave polygon scan conversion), 87-91] |
|
52 |
* |
|
53 |
* and modified to work with sub-pixel precision and non-continuous paths. |
|
54 |
* It's also speeded up by using hash table by rows of the filled objects. |
|
55 |
* |
|
56 |
* Here is high level scheme showing the rendering process: |
|
57 |
* |
|
58 |
* doDrawPath doFillPath |
|
59 |
* \ / |
|
60 |
* ProcessPath |
|
61 |
* | |
|
62 |
* CheckPathSegment |
|
63 |
* | |
|
64 |
* --------+------ |
|
65 |
* | | |
|
66 |
* | | |
|
67 |
* | | |
|
68 |
* _->ProcessCurve | |
|
69 |
* / / | | |
|
70 |
* \___/ | | |
|
71 |
* | | |
|
72 |
* DrawCurve ProcessLine |
|
73 |
* \ / |
|
74 |
* \ / |
|
75 |
* \ / |
|
76 |
* \ / |
|
77 |
* ------+------ |
|
78 |
* (filling) / \ (drawing) |
|
79 |
* / \ |
|
80 |
* Clipping and Clipping |
|
81 |
* clamping \ |
|
82 |
* | \ |
|
83 |
* StoreFixedLine ProcessFixedLine |
|
84 |
* | / \ |
|
85 |
* | / \ |
|
86 |
* FillPolygon PROCESS_LINE PROCESS_POINT |
|
87 |
* |
|
88 |
* |
|
89 |
* |
|
90 |
* CheckPathSegment - rough checking and skipping path's segments in case of |
|
91 |
* invalid or huge coordinates of the control points to |
|
92 |
* avoid calculation problems with NaNs and values close |
|
93 |
* to the FLT_MAX |
|
94 |
* |
|
95 |
* ProcessCurve - (ProcessQuad, ProcessCubic) Splitting the curve into |
|
96 |
* monotonic parts having appropriate size (calculated as |
|
97 |
* boundary box of the control points) |
|
98 |
* |
|
99 |
* DrawMonotonicCurve - (DrawMonotonicQuad, DrawMonotonicCubic) flattening |
|
100 |
* monotonic curve using adaptive forward differencing |
|
101 |
* |
|
102 |
* StoreFixedLine - storing segment from the flattened path to the |
|
103 |
* FillData structure. Performing clipping and clamping if |
|
104 |
* necessary. |
|
105 |
* |
|
106 |
* PROCESS_LINE, PROCESS_POINT - Helpers for calling appropriate primitive from |
|
107 |
* DrawHandler structure |
|
108 |
* |
|
109 |
* ProcessFixedLine - Drawing line segment with subpixel precision. |
|
110 |
* |
|
111 |
*/ |
|
112 |
||
113 |
#define PROCESS_LINE(hnd, fX0, fY0, fX1, fY1, checkBounds, pixelInfo) \ |
|
114 |
do { \
|
|
115 |
jint X0 = (fX0) >> MDP_PREC; \ |
|
116 |
jint Y0 = (fY0) >> MDP_PREC; \ |
|
117 |
jint X1 = (fX1) >> MDP_PREC; \ |
|
118 |
jint Y1 = (fY1) >> MDP_PREC; \ |
|
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
119 |
jint res; \ |
|
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
120 |
\ |
|
8746
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
121 |
/* Checking bounds and clipping if necessary. \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
122 |
* REMIND: It's temporary solution to avoid OOB in rendering code. \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
123 |
* Current approach uses float equations which are unreliable for \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
124 |
* clipping and makes assumptions about the line biases of the \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
125 |
* rendering algorithm. Also, clipping code should be moved down \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
126 |
* into only those output renderers that need it. \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
127 |
*/ \ |
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
128 |
if (checkBounds) { \
|
|
8746
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
129 |
jfloat xMinf = hnd->dhnd->xMinf + 0.5f; \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
130 |
jfloat yMinf = hnd->dhnd->yMinf + 0.5f; \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
131 |
jfloat xMaxf = hnd->dhnd->xMaxf + 0.5f; \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
132 |
jfloat yMaxf = hnd->dhnd->yMaxf + 0.5f; \ |
|
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
133 |
TESTANDCLIP(yMinf, yMaxf, Y0, X0, Y1, X1, jint, res); \ |
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
134 |
if (res == CRES_INVISIBLE) break; \ |
|
8746
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
135 |
TESTANDCLIP(yMinf, yMaxf, Y1, X1, Y0, X0, jint, res); \ |
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
136 |
if (res == CRES_INVISIBLE) break; \ |
|
8746
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
137 |
TESTANDCLIP(xMinf, xMaxf, X0, Y0, X1, Y1, jint, res); \ |
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
138 |
if (res == CRES_INVISIBLE) break; \ |
|
8746
3eef91f87691
6710434: PIT: Reg test java/awt/Graphics2D/ClipPrimitivesTest.java fails in pit build 6u10_b26
bae
parents:
7668
diff
changeset
|
139 |
TESTANDCLIP(xMinf, xMaxf, X1, Y1, X0, Y0, jint, res); \ |
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
140 |
if (res == CRES_INVISIBLE) break; \ |
|
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
141 |
} \ |
|
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
142 |
\ |
|
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
143 |
/* Handling lines having just one pixel */ \ |
| 2 | 144 |
if (((X0^X1) | (Y0^Y1)) == 0) { \
|
145 |
if (pixelInfo[0] == 0) { \
|
|
146 |
pixelInfo[0] = 1; \ |
|
147 |
pixelInfo[1] = X0; \ |
|
148 |
pixelInfo[2] = Y0; \ |
|
149 |
pixelInfo[3] = X0; \ |
|
150 |
pixelInfo[4] = Y0; \ |
|
151 |
hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ |
|
152 |
} else if ((X0 != pixelInfo[3] || Y0 != pixelInfo[4]) && \ |
|
153 |
(X0 != pixelInfo[1] || Y0 != pixelInfo[2])) { \
|
|
154 |
hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ |
|
155 |
pixelInfo[3] = X0; \ |
|
156 |
pixelInfo[4] = Y0; \ |
|
157 |
} \ |
|
158 |
break; \ |
|
159 |
} \ |
|
160 |
\ |
|
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
161 |
if (pixelInfo[0] && \ |
|
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
162 |
((pixelInfo[1] == X0 && pixelInfo[2] == Y0) || \ |
|
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
163 |
(pixelInfo[3] == X0 && pixelInfo[4] == Y0))) \ |
| 2 | 164 |
{ \
|
|
6998
2a7e17242300
6670881: Phantom lines appear when rendering polygons & ellipses with antialiasing OFF
bae
parents:
5506
diff
changeset
|
165 |
hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ |
| 2 | 166 |
} \ |
167 |
\ |
|
168 |
hnd->dhnd->pDrawLine(hnd->dhnd, X0, Y0, X1, Y1); \ |
|
169 |
\ |
|
170 |
if (pixelInfo[0] == 0) { \
|
|
171 |
pixelInfo[0] = 1; \ |
|
172 |
pixelInfo[1] = X0; \ |
|
173 |
pixelInfo[2] = Y0; \ |
|
174 |
pixelInfo[3] = X0; \ |
|
175 |
pixelInfo[4] = Y0; \ |
|
176 |
} \ |
|
177 |
\ |
|
178 |
/* Switch on last pixel of the line if it was already \ |
|
179 |
* drawn during rendering of the previous segments \ |
|
180 |
*/ \ |
|
181 |
if ((pixelInfo[1] == X1 && pixelInfo[2] == Y1) || \ |
|
182 |
(pixelInfo[3] == X1 && pixelInfo[4] == Y1)) \ |
|
183 |
{ \
|
|
184 |
hnd->dhnd->pDrawPixel(hnd->dhnd, X1, Y1); \ |
|
185 |
} \ |
|
186 |
pixelInfo[3] = X1; \ |
|
187 |
pixelInfo[4] = Y1; \ |
|
188 |
} while(0) |
|
189 |
||
190 |
#define PROCESS_POINT(hnd, fX, fY, checkBounds, pixelInfo) \ |
|
191 |
do { \
|
|
192 |
jint _X = (fX)>> MDP_PREC; \ |
|
193 |
jint _Y = (fY)>> MDP_PREC; \ |
|
194 |
if (checkBounds && \ |
|
195 |
(hnd->dhnd->yMin > _Y || \ |
|
196 |
hnd->dhnd->yMax <= _Y || \ |
|
197 |
hnd->dhnd->xMin > _X || \ |
|
198 |
hnd->dhnd->xMax <= _X)) break; \ |
|
199 |
/* \ |
|
200 |
* (_X,_Y) should be inside boundaries \ |
|
201 |
* \ |
|
202 |
* assert(hnd->dhnd->yMin <= _Y && \ |
|
203 |
* hnd->dhnd->yMax > _Y && \ |
|
204 |
* hnd->dhnd->xMin <= _X && \ |
|
205 |
* hnd->dhnd->xMax > _X); \ |
|
206 |
* \ |
|
207 |
*/ \ |
|
208 |
if (pixelInfo[0] == 0) { \
|
|
209 |
pixelInfo[0] = 1; \ |
|
210 |
pixelInfo[1] = _X; \ |
|
211 |
pixelInfo[2] = _Y; \ |
|
212 |
pixelInfo[3] = _X; \ |
|
213 |
pixelInfo[4] = _Y; \ |
|
214 |
hnd->dhnd->pDrawPixel(hnd->dhnd, _X, _Y); \ |
|
215 |
} else if ((_X != pixelInfo[3] || _Y != pixelInfo[4]) && \ |
|
216 |
(_X != pixelInfo[1] || _Y != pixelInfo[2])) { \
|
|
217 |
hnd->dhnd->pDrawPixel(hnd->dhnd, _X, _Y); \ |
|
218 |
pixelInfo[3] = _X; \ |
|
219 |
pixelInfo[4] = _Y; \ |
|
220 |
} \ |
|
221 |
} while(0) |
|
222 |
||
223 |
||
224 |
/* |
|
225 |
* Constants for the forward differencing |
|
226 |
* of the cubic and quad curves |
|
227 |
*/ |
|
228 |
||
229 |
/* Maximum size of the cubic curve (calculated as the size of the bounding box |
|
230 |
* of the control points) which could be rendered without splitting |
|
231 |
*/ |
|
232 |
#define MAX_CUB_SIZE 256 |
|
233 |
||
234 |
/* Maximum size of the quad curve (calculated as the size of the bounding box |
|
235 |
* of the control points) which could be rendered without splitting |
|
236 |
*/ |
|
237 |
#define MAX_QUAD_SIZE 1024 |
|
238 |
||
239 |
/* Default power of 2 steps used in the forward differencing. Here DF prefix |
|
240 |
* stands for DeFault. Constants below are used as initial values for the |
|
241 |
* adaptive forward differencing algorithm. |
|
242 |
*/ |
|
243 |
#define DF_CUB_STEPS 3 |
|
244 |
#define DF_QUAD_STEPS 2 |
|
245 |
||
246 |
/* Shift of the current point of the curve for preparing to the midpoint |
|
247 |
* rounding |
|
248 |
*/ |
|
249 |
#define DF_CUB_SHIFT (FWD_PREC + DF_CUB_STEPS*3 - MDP_PREC) |
|
250 |
#define DF_QUAD_SHIFT (FWD_PREC + DF_QUAD_STEPS*2 - MDP_PREC) |
|
251 |
||
252 |
/* Default amount of steps of the forward differencing */ |
|
253 |
#define DF_CUB_COUNT (1<<DF_CUB_STEPS) |
|
254 |
#define DF_QUAD_COUNT (1<<DF_QUAD_STEPS) |
|
255 |
||
256 |
/* Default boundary constants used to check the necessity of the restepping */ |
|
257 |
#define DF_CUB_DEC_BND (1<<(DF_CUB_STEPS*3 + FWD_PREC + 2)) |
|
258 |
#define DF_CUB_INC_BND (1<<(DF_CUB_STEPS*3 + FWD_PREC - 1)) |
|
259 |
#define DF_QUAD_DEC_BND (1<<(DF_QUAD_STEPS*2 + FWD_PREC + 2)) |
|
260 |
||
261 |
/* Multiplyers for the coefficients of the polynomial form of the cubic and |
|
262 |
* quad curves representation |
|
263 |
*/ |
|
264 |
#define CUB_A_SHIFT FWD_PREC |
|
265 |
#define CUB_B_SHIFT (DF_CUB_STEPS + FWD_PREC + 1) |
|
266 |
#define CUB_C_SHIFT (DF_CUB_STEPS*2 + FWD_PREC) |
|
267 |
||
268 |
#define CUB_A_MDP_MULT (1<<CUB_A_SHIFT) |
|
269 |
#define CUB_B_MDP_MULT (1<<CUB_B_SHIFT) |
|
270 |
#define CUB_C_MDP_MULT (1<<CUB_C_SHIFT) |
|
271 |
||
272 |
#define QUAD_A_SHIFT FWD_PREC |
|
273 |
#define QUAD_B_SHIFT (DF_QUAD_STEPS + FWD_PREC) |
|
274 |
||
275 |
#define QUAD_A_MDP_MULT (1<<QUAD_A_SHIFT) |
|
276 |
#define QUAD_B_MDP_MULT (1<<QUAD_B_SHIFT) |
|
277 |
||
278 |
#define CALC_MAX(MAX, X) ((MAX)=((X)>(MAX))?(X):(MAX)) |
|
279 |
#define CALC_MIN(MIN, X) ((MIN)=((X)<(MIN))?(X):(MIN)) |
|
280 |
#define MAX(MAX, X) (((X)>(MAX))?(X):(MAX)) |
|
281 |
#define MIN(MIN, X) (((X)<(MIN))?(X):(MIN)) |
|
282 |
#define ABS32(X) (((X)^((X)>>31))-((X)>>31)) |
|
283 |
#define SIGN32(X) ((X) >> 31) | ((juint)(-(X)) >> 31) |
|
284 |
||
285 |
/* Boundaries used for clipping large path segments (those are inside |
|
286 |
* [UPPER/LOWER]_BND boundaries) |
|
287 |
*/ |
|
288 |
#define UPPER_OUT_BND (1 << (30 - MDP_PREC)) |
|
289 |
#define LOWER_OUT_BND (-UPPER_OUT_BND) |
|
290 |
||
291 |
#define ADJUST(X, LBND, UBND) \ |
|
292 |
do { \
|
|
293 |
if ((X) < (LBND)) { \
|
|
294 |
(X) = (LBND); \ |
|
295 |
} else if ((X) > UBND) { \
|
|
296 |
(X) = (UBND); \ |
|
297 |
} \ |
|
298 |
} while(0) |
|
299 |
||
300 |
/* Following constants are used for providing open boundaries of the intervals |
|
301 |
*/ |
|
302 |
#define EPSFX 1 |
|
303 |
#define EPSF (((jfloat)EPSFX)/MDP_MULT) |
|
304 |
||
305 |
/* Calculation boundary. It is used for switching to the more slow but allowing |
|
306 |
* larger input values method of calculation of the initial values of the scan |
|
307 |
* converted line segments inside the FillPolygon. |
|
308 |
*/ |
|
309 |
#define CALC_BND (1 << (30 - MDP_PREC)) |
|
310 |
||
311 |
/* Clipping macros for drawing and filling algorithms */ |
|
312 |
||
313 |
#define CLIP(a1, b1, a2, b2, t) \ |
|
314 |
(b1 + ((jdouble)(t - a1)*(b2 - b1)) / (a2 - a1)) |
|
315 |
||
316 |
enum {
|
|
317 |
CRES_MIN_CLIPPED, |
|
318 |
CRES_MAX_CLIPPED, |
|
319 |
CRES_NOT_CLIPPED, |
|
320 |
CRES_INVISIBLE |
|
321 |
}; |
|
322 |
||
323 |
#define IS_CLIPPED(res) (res == CRES_MIN_CLIPPED || res == CRES_MAX_CLIPPED) |
|
324 |
||
325 |
#define TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res) \ |
|
326 |
do { \
|
|
327 |
jdouble t; \ |
|
328 |
res = CRES_NOT_CLIPPED; \ |
|
329 |
if (a1 < (LINE_MIN) || a1 > (LINE_MAX)) { \
|
|
330 |
if (a1 < (LINE_MIN)) { \
|
|
331 |
if (a2 < (LINE_MIN)) { \
|
|
332 |
res = CRES_INVISIBLE; \ |
|
333 |
break; \ |
|
334 |
}; \ |
|
335 |
res = CRES_MIN_CLIPPED; \ |
|
336 |
t = (LINE_MIN); \ |
|
337 |
} else { \
|
|
338 |
if (a2 > (LINE_MAX)) { \
|
|
339 |
res = CRES_INVISIBLE; \ |
|
340 |
break; \ |
|
341 |
}; \ |
|
342 |
res = CRES_MAX_CLIPPED; \ |
|
343 |
t = (LINE_MAX); \ |
|
344 |
} \ |
|
345 |
b1 = (TYPE)CLIP(a1, b1, a2, b2, t); \ |
|
346 |
a1 = (TYPE)t; \ |
|
347 |
} \ |
|
348 |
} while (0) |
|
349 |
||
350 |
/* Following macro is used for clipping and clumping filled shapes. |
|
351 |
* An example of this process is shown on the picture below: |
|
352 |
* ----+ ----+ |
|
353 |
* |/ | |/ | |
|
354 |
* + | + | |
|
355 |
* /| | I | |
|
356 |
* / | | I | |
|
357 |
* | | | ===> I | |
|
358 |
* \ | | I | |
|
359 |
* \| | I | |
|
360 |
* + | + | |
|
361 |
* |\ | |\ | |
|
362 |
* | ----+ | ----+ |
|
363 |
* boundary boundary |
|
364 |
* |
|
365 |
* We can only perform clipping in case of right side of the output area |
|
366 |
* because all segments passed out the right boundary don't influence on the |
|
367 |
* result of scan conversion algorithm (it correctly handles half open |
|
368 |
* contours). |
|
369 |
* |
|
370 |
*/ |
|
371 |
#define CLIPCLAMP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, a3, b3, TYPE, res) \ |
|
372 |
do { \
|
|
373 |
a3 = a1; \ |
|
374 |
b3 = b1; \ |
|
375 |
TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res); \ |
|
376 |
if (res == CRES_MIN_CLIPPED) { \
|
|
377 |
a3 = a1; \ |
|
378 |
} else if (res == CRES_MAX_CLIPPED) { \
|
|
379 |
a3 = a1; \ |
|
380 |
res = CRES_MAX_CLIPPED; \ |
|
381 |
} else if (res == CRES_INVISIBLE) { \
|
|
382 |
if (a1 > LINE_MAX) { \
|
|
383 |
res = CRES_INVISIBLE; \ |
|
384 |
} else { \
|
|
385 |
a1 = (TYPE)LINE_MIN; \ |
|
386 |
a2 = (TYPE)LINE_MIN; \ |
|
387 |
res = CRES_NOT_CLIPPED; \ |
|
388 |
} \ |
|
389 |
} \ |
|
390 |
} while (0) |
|
391 |
||
392 |
/* Following macro is used for solving quadratic equations: |
|
393 |
* A*t^2 + B*t + C = 0 |
|
394 |
* in (0,1) range. That means we put to the RES the only roots which |
|
395 |
* belongs to the (0,1) range. Note: 0 and 1 are not included. |
|
396 |
* See solveQuadratic method in |
|
397 |
* src/share/classes/java/awt/geom/QuadCurve2D.java |
|
398 |
* for more info about calculations |
|
399 |
*/ |
|
400 |
#define SOLVEQUADINRANGE(A,B,C,RES,RCNT) \ |
|
401 |
do { \
|
|
402 |
double param; \ |
|
403 |
if ((A) != 0) { \
|
|
404 |
/* Calculating roots of the following equation \ |
|
405 |
* A*t^2 + B*t + C = 0 \ |
|
406 |
*/ \ |
|
407 |
double d = (B)*(B) - 4*(A)*(C); \ |
|
408 |
double q; \ |
|
409 |
if (d < 0) { \
|
|
410 |
break; \ |
|
411 |
} \ |
|
412 |
d = sqrt(d); \ |
|
413 |
/* For accuracy, calculate one root using: \ |
|
414 |
* (-B +/- d) / 2*A \ |
|
415 |
* and the other using: \ |
|
416 |
* 2*C / (-B +/- d) \ |
|
417 |
* Choose the sign of the +/- so that B+D gets larger \ |
|
418 |
* in magnitude \ |
|
419 |
*/ \ |
|
420 |
if ((B) < 0) { \
|
|
421 |
d = -d; \ |
|
422 |
} \ |
|
423 |
q = ((B) + d) / -2.0; \ |
|
424 |
param = q/(A); \ |
|
425 |
if (param < 1.0 && param > 0.0) { \
|
|
426 |
(RES)[(RCNT)++] = param; \ |
|
427 |
} \ |
|
428 |
if (d == 0 || q == 0) { \
|
|
429 |
break; \ |
|
430 |
} \ |
|
431 |
param = (C)/q; \ |
|
432 |
if (param < 1.0 && param > 0.0) { \
|
|
433 |
(RES)[(RCNT)++] = param; \ |
|
434 |
} \ |
|
435 |
} else { \
|
|
436 |
/* Calculating root of the following equation \ |
|
437 |
* B*t + C = 0 \ |
|
438 |
*/ \ |
|
439 |
if ((B) == 0) { \
|
|
440 |
break; \ |
|
441 |
} \ |
|
442 |
param = -(C)/(B); \ |
|
443 |
if (param < 1.0 && param > 0.0) { \
|
|
444 |
(RES)[(RCNT)++] = param; \ |
|
445 |
} \ |
|
446 |
} \ |
|
447 |
} while(0) |
|
448 |
||
449 |
/* Drawing line with subpixel endpoints |
|
450 |
* |
|
451 |
* (x1, y1), (x2, y2) - fixed point coordinates of the endpoints |
|
452 |
* with MDP_PREC bits for the fractional part |
|
453 |
* |
|
454 |
* pixelInfo - structure which keeps drawing info for avoiding |
|
455 |
* multiple drawing at the same position on the |
|
456 |
* screen (required for the XOR mode of drawing) |
|
457 |
* |
|
458 |
* pixelInfo[0] - state of the drawing |
|
459 |
* 0 - no pixel drawn between |
|
460 |
* moveTo/close of the path |
|
461 |
* 1 - there are drawn pixels |
|
462 |
* |
|
463 |
* pixelInfo[1,2] - first pixel of the path |
|
464 |
* between moveTo/close of the |
|
465 |
* path |
|
466 |
* |
|
467 |
* pixelInfo[3,4] - last drawn pixel between |
|
468 |
* moveTo/close of the path |
|
469 |
* |
|
470 |
* checkBounds - flag showing necessity of checking the clip |
|
471 |
* |
|
472 |
*/ |
|
473 |
void ProcessFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2, |
|
474 |
jint* pixelInfo,jboolean checkBounds, |
|
475 |
jboolean endSubPath) |
|
476 |
{
|
|
477 |
/* Checking if line is inside a (X,Y),(X+MDP_MULT,Y+MDP_MULT) box */ |
|
478 |
jint c = ((x1 ^ x2) | (y1 ^ y2)); |
|
479 |
jint rx1, ry1, rx2, ry2; |
|
480 |
if ((c & MDP_W_MASK) == 0) {
|
|
481 |
/* Checking for the segments with integer coordinates having |
|
482 |
* the same start and end points |
|
483 |
*/ |
|
484 |
if (c == 0) {
|
|
485 |
PROCESS_POINT(hnd, x1 + MDP_HALF_MULT, y1 + MDP_HALF_MULT, |
|
486 |
checkBounds, pixelInfo); |
|
487 |
} |
|
488 |
return; |
|
489 |
} |
|
490 |
||
491 |
if (x1 == x2 || y1 == y2) {
|
|
492 |
rx1 = x1 + MDP_HALF_MULT; |
|
493 |
rx2 = x2 + MDP_HALF_MULT; |
|
494 |
ry1 = y1 + MDP_HALF_MULT; |
|
495 |
ry2 = y2 + MDP_HALF_MULT; |
|
496 |
} else {
|
|
497 |
/* Neither dx nor dy can be zero because of the check above */ |
|
498 |
jint dx = x2 - x1; |
|
499 |
jint dy = y2 - y1; |
|
500 |
||
501 |
/* Floor of x1, y1, x2, y2 */ |
|
502 |
jint fx1 = x1 & MDP_W_MASK; |
|
503 |
jint fy1 = y1 & MDP_W_MASK; |
|
504 |
jint fx2 = x2 & MDP_W_MASK; |
|
505 |
jint fy2 = y2 & MDP_W_MASK; |
|
506 |
||
507 |
/* Processing first endpoint */ |
|
508 |
if (fx1 == x1 || fy1 == y1) {
|
|
509 |
/* Adding MDP_HALF_MULT to the [xy]1 if f[xy]1 == [xy]1 will not |
|
510 |
* affect the result |
|
511 |
*/ |
|
512 |
rx1 = x1 + MDP_HALF_MULT; |
|
513 |
ry1 = y1 + MDP_HALF_MULT; |
|
514 |
} else {
|
|
515 |
/* Boundary at the direction from (x1,y1) to (x2,y2) */ |
|
516 |
jint bx1 = (x1 < x2) ? fx1 + MDP_MULT : fx1; |
|
517 |
jint by1 = (y1 < y2) ? fy1 + MDP_MULT : fy1; |
|
518 |
||
519 |
/* intersection with column bx1 */ |
|
520 |
jint cross = y1 + ((bx1 - x1)*dy)/dx; |
|
521 |
if (cross >= fy1 && cross <= fy1 + MDP_MULT) {
|
|
522 |
rx1 = bx1; |
|
523 |
ry1 = cross + MDP_HALF_MULT; |
|
524 |
} else {
|
|
525 |
/* intersection with row by1 */ |
|
526 |
cross = x1 + ((by1 - y1)*dx)/dy; |
|
527 |
rx1 = cross + MDP_HALF_MULT; |
|
528 |
ry1 = by1; |
|
529 |
} |
|
530 |
} |
|
531 |
||
532 |
/* Processing second endpoint */ |
|
533 |
if (fx2 == x2 || fy2 == y2) {
|
|
534 |
/* Adding MDP_HALF_MULT to the [xy]2 if f[xy]2 == [xy]2 will not |
|
535 |
* affect the result |
|
536 |
*/ |
|
537 |
rx2 = x2 + MDP_HALF_MULT; |
|
538 |
ry2 = y2 + MDP_HALF_MULT; |
|
539 |
} else {
|
|
540 |
/* Boundary at the direction from (x2,y2) to (x1,y1) */ |
|
541 |
jint bx2 = (x1 > x2) ? fx2 + MDP_MULT : fx2; |
|
542 |
jint by2 = (y1 > y2) ? fy2 + MDP_MULT : fy2; |
|
543 |
||
544 |
/* intersection with column bx2 */ |
|
545 |
jint cross = y2 + ((bx2 - x2)*dy)/dx; |
|
546 |
if (cross >= fy2 && cross <= fy2 + MDP_MULT) {
|
|
547 |
rx2 = bx2; |
|
548 |
ry2 = cross + MDP_HALF_MULT; |
|
549 |
} else {
|
|
550 |
/* intersection with row by2 */ |
|
551 |
cross = x2 + ((by2 - y2)*dx)/dy; |
|
552 |
rx2 = cross + MDP_HALF_MULT; |
|
553 |
ry2 = by2; |
|
554 |
} |
|
555 |
} |
|
556 |
} |
|
557 |
||
558 |
PROCESS_LINE(hnd, rx1, ry1, rx2, ry2, checkBounds, pixelInfo); |
|
559 |
} |
|
560 |
||
561 |
/* Performing drawing of the monotonic in X and Y quadratic curves with sizes |
|
562 |
* less than MAX_QUAD_SIZE by using forward differencing method of calculation. |
|
563 |
* See comments to the DrawMonotonicCubic. |
|
564 |
*/ |
|
565 |
static void DrawMonotonicQuad(ProcessHandler* hnd, |
|
566 |
jfloat *coords, |
|
567 |
jboolean checkBounds, |
|
568 |
jint* pixelInfo) |
|
569 |
{
|
|
570 |
jint x0 = (jint)(coords[0]*MDP_MULT); |
|
571 |
jint y0 = (jint)(coords[1]*MDP_MULT); |
|
572 |
||
573 |
jint xe = (jint)(coords[4]*MDP_MULT); |
|
574 |
jint ye = (jint)(coords[5]*MDP_MULT); |
|
575 |
||
576 |
/* Extracting fractional part of coordinates of first control point */ |
|
577 |
jint px = (x0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT; |
|
578 |
jint py = (y0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT; |
|
579 |
||
580 |
/* Setting default amount of steps */ |
|
581 |
jint count = DF_QUAD_COUNT; |
|
582 |
||
583 |
/* Setting default shift for preparing to the midpoint rounding */ |
|
584 |
jint shift = DF_QUAD_SHIFT; |
|
585 |
||
586 |
jint ax = (jint)((coords[0] - 2*coords[2] + |
|
587 |
coords[4])*QUAD_A_MDP_MULT); |
|
588 |
jint ay = (jint)((coords[1] - 2*coords[3] + |
|
589 |
coords[5])*QUAD_A_MDP_MULT); |
|
590 |
||
591 |
jint bx = (jint)((-2*coords[0] + 2*coords[2])*QUAD_B_MDP_MULT); |
|
592 |
jint by = (jint)((-2*coords[1] + 2*coords[3])*QUAD_B_MDP_MULT); |
|
593 |
||
594 |
jint ddpx = 2*ax; |
|
595 |
jint ddpy = 2*ay; |
|
596 |
||
597 |
jint dpx = ax + bx; |
|
598 |
jint dpy = ay + by; |
|
599 |
||
600 |
jint x1, y1; |
|
601 |
||
602 |
jint x2 = x0; |
|
603 |
jint y2 = y0; |
|
604 |
||
605 |
jint maxDD = MAX(ABS32(ddpx),ABS32(ddpy)); |
|
606 |
jint x0w = x0 & MDP_W_MASK; |
|
607 |
jint y0w = y0 & MDP_W_MASK; |
|
608 |
||
609 |
jint dx = xe - x0; |
|
610 |
jint dy = ye - y0; |
|
611 |
||
612 |
/* Perform decreasing step in 2 times if slope of the second forward |
|
613 |
* difference changes too quickly (more than a pixel per step in X or Y |
|
614 |
* direction). We can perform adjusting of the step size before the |
|
615 |
* rendering loop because the curvature of the quad curve remains the same |
|
616 |
* along all the curve |
|
617 |
*/ |
|
618 |
while (maxDD > DF_QUAD_DEC_BND) {
|
|
619 |
dpx = (dpx<<1) - ax; |
|
620 |
dpy = (dpy<<1) - ay; |
|
621 |
count <<= 1; |
|
622 |
maxDD >>= 2; |
|
623 |
px <<=2; |
|
624 |
py <<=2; |
|
625 |
shift += 2; |
|
626 |
} |
|
627 |
||
628 |
while(count-- > 1) {
|
|
629 |
||
630 |
px += dpx; |
|
631 |
py += dpy; |
|
632 |
||
633 |
dpx += ddpx; |
|
634 |
dpy += ddpy; |
|
635 |
||
636 |
x1 = x2; |
|
637 |
y1 = y2; |
|
638 |
||
639 |
x2 = x0w + (px >> shift); |
|
640 |
y2 = y0w + (py >> shift); |
|
641 |
||
642 |
/* Checking that we are not running out of the endpoint and bounding |
|
643 |
* violating coordinate. The check is pretty simple because the curve |
|
644 |
* passed to the DrawMonotonicQuad already splitted into the monotonic |
|
645 |
* in X and Y pieces |
|
646 |
*/ |
|
647 |
||
648 |
/* Bounding x2 by xe */ |
|
649 |
if (((xe-x2)^dx) < 0) {
|
|
650 |
x2 = xe; |
|
651 |
} |
|
652 |
||
653 |
/* Bounding y2 by ye */ |
|
654 |
if (((ye-y2)^dy) < 0) {
|
|
655 |
y2 = ye; |
|
656 |
} |
|
657 |
||
658 |
hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds, |
|
659 |
JNI_FALSE); |
|
660 |
} |
|
661 |
||
662 |
/* We are performing one step less than necessary and use actual (xe,ye) |
|
663 |
* curve's endpoint instead of calculated. This prevent us from accumulated |
|
664 |
* errors at the last point. |
|
665 |
*/ |
|
666 |
||
667 |
hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds, |
|
668 |
JNI_FALSE); |
|
669 |
} |
|
670 |
||
671 |
/* |
|
672 |
* Checking size of the quad curves and split them if necessary. |
|
673 |
* Calling DrawMonotonicQuad for the curves of the appropriate size. |
|
674 |
* Note: coords array could be changed |
|
675 |
*/ |
|
676 |
static void ProcessMonotonicQuad(ProcessHandler* hnd, |
|
677 |
jfloat *coords, |
|
678 |
jint* pixelInfo) {
|
|
679 |
||
680 |
jfloat coords1[6]; |
|
681 |
jfloat xMin, xMax; |
|
682 |
jfloat yMin, yMax; |
|
683 |
||
684 |
xMin = xMax = coords[0]; |
|
685 |
yMin = yMax = coords[1]; |
|
686 |
||
687 |
CALC_MIN(xMin, coords[2]); |
|
688 |
CALC_MAX(xMax, coords[2]); |
|
689 |
CALC_MIN(yMin, coords[3]); |
|
690 |
CALC_MAX(yMax, coords[3]); |
|
691 |
CALC_MIN(xMin, coords[4]); |
|
692 |
CALC_MAX(xMax, coords[4]); |
|
693 |
CALC_MIN(yMin, coords[5]); |
|
694 |
CALC_MAX(yMax, coords[5]); |
|
695 |
||
696 |
||
697 |
if (hnd->clipMode == PH_MODE_DRAW_CLIP) {
|
|
698 |
||
699 |
/* In case of drawing we could just skip curves which are completely |
|
700 |
* out of bounds |
|
701 |
*/ |
|
702 |
if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax || |
|
703 |
hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) {
|
|
704 |
return; |
|
705 |
} |
|
706 |
} else {
|
|
707 |
||
708 |
/* In case of filling we could skip curves which are above, |
|
709 |
* below and behind the right boundary of the visible area |
|
710 |
*/ |
|
711 |
||
712 |
if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax || |
|
713 |
hnd->dhnd->xMaxf < xMin) |
|
714 |
{
|
|
715 |
return; |
|
716 |
} |
|
717 |
||
718 |
/* We could clamp x coordinates to the corresponding boundary |
|
719 |
* if the curve is completely behind the left one |
|
720 |
*/ |
|
721 |
||
722 |
if (hnd->dhnd->xMinf > xMax) {
|
|
723 |
coords[0] = coords[2] = coords[4] = hnd->dhnd->xMinf; |
|
724 |
} |
|
725 |
} |
|
726 |
||
727 |
if (xMax - xMin > MAX_QUAD_SIZE || yMax - yMin > MAX_QUAD_SIZE) {
|
|
728 |
coords1[4] = coords[4]; |
|
729 |
coords1[5] = coords[5]; |
|
730 |
coords1[2] = (coords[2] + coords[4])/2.0f; |
|
731 |
coords1[3] = (coords[3] + coords[5])/2.0f; |
|
732 |
coords[2] = (coords[0] + coords[2])/2.0f; |
|
733 |
coords[3] = (coords[1] + coords[3])/2.0f; |
|
734 |
coords[4] = coords1[0] = (coords[2] + coords1[2])/2.0f; |
|
735 |
coords[5] = coords1[1] = (coords[3] + coords1[3])/2.0f; |
|
736 |
||
737 |
ProcessMonotonicQuad(hnd, coords, pixelInfo); |
|
738 |
||
739 |
ProcessMonotonicQuad(hnd, coords1, pixelInfo); |
|
740 |
} else {
|
|
741 |
DrawMonotonicQuad(hnd, coords, |
|
742 |
/* Set checkBounds parameter if curve intersects |
|
743 |
* boundary of the visible area. We know that the |
|
744 |
* curve is visible, so the check is pretty simple |
|
745 |
*/ |
|
746 |
hnd->dhnd->xMinf >= xMin || hnd->dhnd->xMaxf <= xMax || |
|
747 |
hnd->dhnd->yMinf >= yMin || hnd->dhnd->yMaxf <= yMax, |
|
748 |
pixelInfo); |
|
749 |
} |
|
750 |
} |
|
751 |
||
752 |
/* |
|
753 |
* Bite the piece of the quadratic curve from start point till the point |
|
754 |
* corresponding to the specified parameter then call ProcessQuad for the |
|
755 |
* bitten part. |
|
756 |
* Note: coords array will be changed |
|
757 |
*/ |
|
758 |
static void ProcessFirstMonotonicPartOfQuad(ProcessHandler* hnd, jfloat* coords, |
|
759 |
jint* pixelInfo, jfloat t) |
|
760 |
{
|
|
761 |
jfloat coords1[6]; |
|
762 |
||
763 |
coords1[0] = coords[0]; |
|
764 |
coords1[1] = coords[1]; |
|
765 |
coords1[2] = coords[0] + t*(coords[2] - coords[0]); |
|
766 |
coords1[3] = coords[1] + t*(coords[3] - coords[1]); |
|
767 |
coords[2] = coords[2] + t*(coords[4] - coords[2]); |
|
768 |
coords[3] = coords[3] + t*(coords[5] - coords[3]); |
|
769 |
coords[0] = coords1[4] = coords1[2] + t*(coords[2] - coords1[2]); |
|
770 |
coords[1] = coords1[5] = coords1[3] + t*(coords[3] - coords1[3]); |
|
771 |
||
772 |
ProcessMonotonicQuad(hnd, coords1, pixelInfo); |
|
773 |
} |
|
774 |
||
775 |
/* |
|
776 |
* Split quadratic curve into monotonic in X and Y parts. Calling |
|
777 |
* ProcessMonotonicQuad for each monotonic piece of the curve. |
|
778 |
* Note: coords array could be changed |
|
779 |
*/ |
|
780 |
static void ProcessQuad(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) {
|
|
781 |
||
782 |
/* Temporary array for holding parameters corresponding to the extreme in X |
|
783 |
* and Y points. The values are inside the (0,1) range (0 and 1 excluded) |
|
784 |
* and in ascending order. |
|
785 |
*/ |
|
786 |
double params[2]; |
|
787 |
||
788 |
jint cnt = 0; |
|
789 |
double param; |
|
790 |
||
791 |
/* Simple check for monotonicity in X before searching for the extreme |
|
792 |
* points of the X(t) function. We first check if the curve is monotonic |
|
793 |
* in X by seeing if all of the X coordinates are strongly ordered. |
|
794 |
*/ |
|
795 |
if ((coords[0] > coords[2] || coords[2] > coords[4]) && |
|
796 |
(coords[0] < coords[2] || coords[2] < coords[4])) |
|
797 |
{
|
|
798 |
/* Searching for extreme points of the X(t) function by solving |
|
799 |
* dX(t) |
|
800 |
* ---- = 0 equation |
|
801 |
* dt |
|
802 |
*/ |
|
803 |
double ax = coords[0] - 2*coords[2] + coords[4]; |
|
804 |
if (ax != 0) {
|
|
805 |
/* Calculating root of the following equation |
|
806 |
* ax*t + bx = 0 |
|
807 |
*/ |
|
808 |
double bx = coords[0] - coords[2]; |
|
809 |
||
810 |
param = bx/ax; |
|
811 |
if (param < 1.0 && param > 0.0) {
|
|
812 |
params[cnt++] = param; |
|
813 |
} |
|
814 |
} |
|
815 |
} |
|
816 |
||
817 |
/* Simple check for monotonicity in Y before searching for the extreme |
|
818 |
* points of the Y(t) function. We first check if the curve is monotonic |
|
819 |
* in Y by seeing if all of the Y coordinates are strongly ordered. |
|
820 |
*/ |
|
821 |
if ((coords[1] > coords[3] || coords[3] > coords[5]) && |
|
822 |
(coords[1] < coords[3] || coords[3] < coords[5])) |
|
823 |
{
|
|
824 |
/* Searching for extreme points of the Y(t) function by solving |
|
825 |
* dY(t) |
|
826 |
* ----- = 0 equation |
|
827 |
* dt |
|
828 |
*/ |
|
829 |
double ay = coords[1] - 2*coords[3] + coords[5]; |
|
830 |
||
831 |
if (ay != 0) {
|
|
832 |
/* Calculating root of the following equation |
|
833 |
* ay*t + by = 0 |
|
834 |
*/ |
|
835 |
double by = coords[1] - coords[3]; |
|
836 |
||
837 |
param = by/ay; |
|
838 |
if (param < 1.0 && param > 0.0) {
|
|
839 |
if (cnt > 0) {
|
|
840 |
/* Inserting parameter only if it differs from |
|
841 |
* already stored |
|
842 |
*/ |
|
843 |
if (params[0] > param) {
|
|
844 |
params[cnt++] = params[0]; |
|
845 |
params[0] = param; |
|
846 |
} else if (params[0] < param) {
|
|
847 |
params[cnt++] = param; |
|
848 |
} |
|
849 |
} else {
|
|
850 |
params[cnt++] = param; |
|
851 |
} |
|
852 |
} |
|
853 |
} |
|
854 |
} |
|
855 |
||
856 |
/* Processing obtained monotonic parts */ |
|
857 |
switch(cnt) {
|
|
858 |
case 0: |
|
859 |
break; |
|
860 |
case 1: |
|
861 |
ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, |
|
862 |
(jfloat)params[0]); |
|
863 |
break; |
|
864 |
case 2: |
|
865 |
ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, |
|
866 |
(jfloat)params[0]); |
|
867 |
param = params[1] - params[0]; |
|
868 |
if (param > 0) {
|
|
869 |
ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, |
|
870 |
/* Scale parameter to match with rest of the curve */ |
|
871 |
(jfloat)(param/(1.0 - params[0]))); |
|
872 |
} |
|
873 |
break; |
|
874 |
} |
|
875 |
||
876 |
ProcessMonotonicQuad(hnd,coords,pixelInfo); |
|
877 |
} |
|
878 |
||
879 |
/* |
|
880 |
* Performing drawing of the monotonic in X and Y cubic curves with sizes less |
|
881 |
* than MAX_CUB_SIZE by using forward differencing method of calculation. |
|
882 |
* |
|
883 |
* Here is some math used in the code below. |
|
884 |
* |
|
885 |
* If we express the parametric equation for the coordinates as |
|
886 |
* simple polynomial: |
|
887 |
* |
|
888 |
* V(t) = a * t^3 + b * t^2 + c * t + d |
|
889 |
* |
|
890 |
* The equations for how we derive these polynomial coefficients |
|
891 |
* from the Bezier control points can be found in the method comments |
|
892 |
* for the CubicCurve.fillEqn Java method. |
|
893 |
* |
|
894 |
* From this polynomial, we can derive the forward differences to |
|
895 |
* allow us to calculate V(t+K) from V(t) as follows: |
|
896 |
* |
|
897 |
* 1) V1(0) |
|
898 |
* = V(K)-V(0) |
|
899 |
* = aK^3 + bK^2 + cK + d - d |
|
900 |
* = aK^3 + bK^2 + cK |
|
901 |
* |
|
902 |
* 2) V1(K) |
|
903 |
* = V(2K)-V(K) |
|
904 |
* = 8aK^3 + 4bK^2 + 2cK + d - aK^3 - bK^2 - cK - d |
|
905 |
* = 7aK^3 + 3bK^2 + cK |
|
906 |
* |
|
907 |
* 3) V1(2K) |
|
908 |
* = V(3K)-V(2K) |
|
909 |
* = 27aK^3 + 9bK^2 + 3cK + d - 8aK^3 - 4bK^2 - 2cK - d |
|
910 |
* = 19aK^3 + 5bK^2 + cK |
|
911 |
* |
|
912 |
* 4) V2(0) |
|
913 |
* = V1(K) - V1(0) |
|
914 |
* = 7aK^3 + 3bK^2 + cK - aK^3 - bK^2 - cK |
|
915 |
* = 6aK^3 + 2bK^2 |
|
916 |
* |
|
917 |
* 5) V2(K) |
|
918 |
* = V1(2K) - V1(K) |
|
919 |
* = 19aK^3 + 5bK^2 + cK - 7aK^3 - 3bK^2 - cK |
|
920 |
* = 12aK^3 + 2bK^2 |
|
921 |
* |
|
922 |
* 6) V3(0) |
|
923 |
* = V2(K) - V2(0) |
|
924 |
* = 12aK^3 + 2bK^2 - 6aK^3 - 2bK^2 |
|
925 |
* = 6aK^3 |
|
926 |
* |
|
927 |
* Note that if we continue on to calculate V1(3K), V2(2K) and |
|
928 |
* V3(K) we will see that V3(K) == V3(0) so we need at most |
|
929 |
* 3 cascading forward differences to step through the cubic |
|
930 |
* curve. |
|
931 |
* |
|
932 |
* Note, b coefficient calculating in the DrawCubic is actually twice the b |
|
933 |
* coefficient seen above. It's been done for the better accuracy. |
|
934 |
* |
|
935 |
* In our case, initialy K is chosen as 1/(2^DF_CUB_STEPS) this value is taken |
|
936 |
* with FWD_PREC bits precision. This means that we should do 2^DF_CUB_STEPS |
|
937 |
* steps to pass through all the curve. |
|
938 |
* |
|
939 |
* On each step we examine how far we are stepping by examining our first(V1) |
|
940 |
* and second (V2) order derivatives and verifying that they are met following |
|
941 |
* conditions: |
|
942 |
* |
|
943 |
* abs(V2) <= DF_CUB_DEC_BND |
|
944 |
* abs(V1) > DF_CUB_INC_BND |
|
945 |
* |
|
946 |
* So, ensures that we step through the curve more slowly when its curvature is |
|
947 |
* high and faster when its curvature is lower. If the step size needs |
|
948 |
* adjustment we adjust it so that we step either twice as fast, or twice as |
|
949 |
* slow until our step size is within range. This modifies our stepping |
|
950 |
* variables as follows: |
|
951 |
* |
|
952 |
* Decreasing step size |
|
953 |
* (See Graphics Gems/by A.Glassner,(Tutorial on forward differencing),601-602) |
|
954 |
* |
|
955 |
* V3 = oV3/8 |
|
956 |
* V2 = oV2/4 - V3 |
|
957 |
* V1 = (oV1 - V2)/2 |
|
958 |
* |
|
959 |
* Here V1-V3 stands for new values of the forward differencies and oV1 - oV3 |
|
960 |
* for the old ones |
|
961 |
* |
|
962 |
* Using the equations above it's easy to calculating stepping variables for |
|
963 |
* the increasing step size: |
|
964 |
* |
|
965 |
* V1 = 2*oV1 + oV2 |
|
966 |
* V2 = 4*oV2 + 4*oV3 |
|
967 |
* V3 = 8*oV3 |
|
968 |
* |
|
969 |
* And then for not to running out of 32 bit precision we are performing 3 bit |
|
970 |
* shift of the forward differencing precision (keeping in shift variable) in |
|
971 |
* left or right direction depending on what is happening (decreasing or |
|
972 |
* increasing). So, all oV1 - oV3 variables should be thought as appropriately |
|
973 |
* shifted in regard to the V1 - V3. |
|
974 |
* |
|
975 |
* Taking all of the above into account we will have following: |
|
976 |
* |
|
977 |
* Decreasing step size: |
|
978 |
* |
|
979 |
* shift = shift + 3 |
|
980 |
* V3 keeps the same |
|
981 |
* V2 = 2*oV2 - V3 |
|
982 |
* V1 = 4*oV1 - V2/2 |
|
983 |
* |
|
984 |
* Increasing step size: |
|
985 |
* |
|
986 |
* shift = shift - 3 |
|
987 |
* V1 = oV1/4 + oV2/8 |
|
988 |
* V2 = oV2/2 + oV3/2 |
|
989 |
* V3 keeps the same |
|
990 |
* |
|
991 |
*/ |
|
992 |
||
993 |
static void DrawMonotonicCubic(ProcessHandler* hnd, |
|
994 |
jfloat *coords, |
|
995 |
jboolean checkBounds, |
|
996 |
jint* pixelInfo) |
|
997 |
{
|
|
998 |
jint x0 = (jint)(coords[0]*MDP_MULT); |
|
999 |
jint y0 = (jint)(coords[1]*MDP_MULT); |
|
1000 |
||
1001 |
jint xe = (jint)(coords[6]*MDP_MULT); |
|
1002 |
jint ye = (jint)(coords[7]*MDP_MULT); |
|
1003 |
||
1004 |
/* Extracting fractional part of coordinates of first control point */ |
|
1005 |
jint px = (x0 & (~MDP_W_MASK)) << DF_CUB_SHIFT; |
|
1006 |
jint py = (y0 & (~MDP_W_MASK)) << DF_CUB_SHIFT; |
|
1007 |
||
1008 |
/* Setting default boundary values for checking first and second forward |
|
1009 |
* difference for the necessity of the restepping. See comments to the |
|
1010 |
* boundary values in ProcessQuad for more info. |
|
1011 |
*/ |
|
1012 |
jint incStepBnd1 = DF_CUB_INC_BND; |
|
1013 |
jint incStepBnd2 = DF_CUB_INC_BND << 1; |
|
1014 |
jint decStepBnd1 = DF_CUB_DEC_BND; |
|
1015 |
jint decStepBnd2 = DF_CUB_DEC_BND << 1; |
|
1016 |
||
1017 |
/* Setting default amount of steps */ |
|
1018 |
jint count = DF_CUB_COUNT; |
|
1019 |
||
1020 |
/* Setting default shift for preparing to the midpoint rounding */ |
|
1021 |
jint shift = DF_CUB_SHIFT; |
|
1022 |
||
1023 |
jint ax = (jint)((-coords[0] + 3*coords[2] - 3*coords[4] + |
|
1024 |
coords[6])*CUB_A_MDP_MULT); |
|
1025 |
jint ay = (jint)((-coords[1] + 3*coords[3] - 3*coords[5] + |
|
1026 |
coords[7])*CUB_A_MDP_MULT); |
|
1027 |
||
1028 |
jint bx = (jint)((3*coords[0] - 6*coords[2] + |
|
1029 |
3*coords[4])*CUB_B_MDP_MULT); |
|
1030 |
jint by = (jint)((3*coords[1] - 6*coords[3] + |
|
1031 |
3*coords[5])*CUB_B_MDP_MULT); |
|
1032 |
||
1033 |
jint cx = (jint)((-3*coords[0] + 3*coords[2])*(CUB_C_MDP_MULT)); |
|
1034 |
jint cy = (jint)((-3*coords[1] + 3*coords[3])*(CUB_C_MDP_MULT)); |
|
1035 |
||
1036 |
jint dddpx = 6*ax; |
|
1037 |
jint dddpy = 6*ay; |
|
1038 |
||
1039 |
jint ddpx = dddpx + bx; |
|
1040 |
jint ddpy = dddpy + by; |
|
1041 |
||
1042 |
jint dpx = ax + (bx>>1) + cx; |
|
1043 |
jint dpy = ay + (by>>1) + cy; |
|
1044 |
||
1045 |
jint x1, y1; |
|
1046 |
||
1047 |
jint x2 = x0; |
|
1048 |
jint y2 = y0; |
|
1049 |
||
1050 |
/* Calculating whole part of the first point of the curve */ |
|
1051 |
jint x0w = x0 & MDP_W_MASK; |
|
1052 |
jint y0w = y0 & MDP_W_MASK; |
|
1053 |
||
1054 |
jint dx = xe - x0; |
|
1055 |
jint dy = ye - y0; |
|
1056 |
||
1057 |
while (count > 0) {
|
|
1058 |
/* Perform decreasing step in 2 times if necessary */ |
|
1059 |
while ( |
|
1060 |
/* The code below is an optimized version of the checks: |
|
1061 |
* abs(ddpx) > decStepBnd1 || |
|
1062 |
* abs(ddpy) > decStepBnd1 |
|
1063 |
*/ |
|
1064 |
(juint)(ddpx + decStepBnd1) > (juint)decStepBnd2 || |
|
1065 |
(juint)(ddpy + decStepBnd1) > (juint)decStepBnd2) |
|
1066 |
{
|
|
1067 |
ddpx = (ddpx<<1) - dddpx; |
|
1068 |
ddpy = (ddpy<<1) - dddpy; |
|
1069 |
dpx = (dpx<<2) - (ddpx>>1); |
|
1070 |
dpy = (dpy<<2) - (ddpy>>1); |
|
1071 |
count <<=1; |
|
1072 |
decStepBnd1 <<=3; |
|
1073 |
decStepBnd2 <<=3; |
|
1074 |
incStepBnd1 <<=3; |
|
1075 |
incStepBnd2 <<=3; |
|
1076 |
px <<=3; |
|
1077 |
py <<=3; |
|
1078 |
shift += 3; |
|
1079 |
} |
|
1080 |
||
1081 |
/* Perform increasing step in 2 times if necessary. |
|
1082 |
* Note: we could do it only in even steps |
|
1083 |
*/ |
|
1084 |
||
1085 |
while (((count & 1) ^ 1) && shift > DF_CUB_SHIFT && |
|
1086 |
/* The code below is an optimized version of the check: |
|
1087 |
* abs(dpx) <= incStepBnd1 && |
|
1088 |
* abs(dpy) <= incStepBnd1 |
|
1089 |
*/ |
|
1090 |
(juint)(dpx + incStepBnd1) <= (juint)incStepBnd2 && |
|
1091 |
(juint)(dpy + incStepBnd1) <= (juint)incStepBnd2) |
|
1092 |
{
|
|
1093 |
dpx = (dpx>>2) + (ddpx>>3); |
|
1094 |
dpy = (dpy>>2) + (ddpy>>3); |
|
1095 |
ddpx = (ddpx + dddpx)>>1; |
|
1096 |
ddpy = (ddpy + dddpy)>>1; |
|
1097 |
count >>=1; |
|
1098 |
decStepBnd1 >>=3; |
|
1099 |
decStepBnd2 >>=3; |
|
1100 |
incStepBnd1 >>=3; |
|
1101 |
incStepBnd2 >>=3; |
|
1102 |
px >>=3; |
|
1103 |
py >>=3; |
|
1104 |
shift -= 3; |
|
1105 |
} |
|
1106 |
||
1107 |
count--; |
|
1108 |
||
1109 |
/* We are performing one step less than necessary and use actual |
|
1110 |
* (xe,ye) endpoint of the curve instead of calculated. This prevent |
|
1111 |
* us from accumulated errors at the last point. |
|
1112 |
*/ |
|
1113 |
if (count) {
|
|
1114 |
||
1115 |
px += dpx; |
|
1116 |
py += dpy; |
|
1117 |
||
1118 |
dpx += ddpx; |
|
1119 |
dpy += ddpy; |
|
1120 |
ddpx += dddpx; |
|
1121 |
ddpy += dddpy; |
|
1122 |
||
1123 |
x1 = x2; |
|
1124 |
y1 = y2; |
|
1125 |
||
1126 |
x2 = x0w + (px >> shift); |
|
1127 |
y2 = y0w + (py >> shift); |
|
1128 |
||
1129 |
/* Checking that we are not running out of the endpoint and |
|
1130 |
* bounding violating coordinate. The check is pretty simple |
|
1131 |
* because the curve passed to the DrawMonotonicCubic already |
|
1132 |
* splitted into the monotonic in X and Y pieces |
|
1133 |
*/ |
|
1134 |
||
1135 |
/* Bounding x2 by xe */ |
|
1136 |
if (((xe-x2)^dx) < 0) {
|
|
1137 |
x2 = xe; |
|
1138 |
} |
|
1139 |
||
1140 |
/* Bounding y2 by ye */ |
|
1141 |
if (((ye-y2)^dy) < 0) {
|
|
1142 |
y2 = ye; |
|
1143 |
} |
|
1144 |
||
1145 |
hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds, |
|
1146 |
JNI_FALSE); |
|
1147 |
} else {
|
|
1148 |
hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds, |
|
1149 |
JNI_FALSE); |
|
1150 |
} |
|
1151 |
} |
|
1152 |
} |
|
1153 |
||
1154 |
/* |
|
1155 |
* Checking size of the cubic curves and split them if necessary. |
|
1156 |
* Calling DrawMonotonicCubic for the curves of the appropriate size. |
|
1157 |
* Note: coords array could be changed |
|
1158 |
*/ |
|
1159 |
static void ProcessMonotonicCubic(ProcessHandler* hnd, |
|
1160 |
jfloat *coords, |
|
1161 |
jint* pixelInfo) {
|
|
1162 |
||
1163 |
jfloat coords1[8]; |
|
1164 |
jfloat tx, ty; |
|
1165 |
jfloat xMin, xMax; |
|
1166 |
jfloat yMin, yMax; |
|
1167 |
||
1168 |
xMin = xMax = coords[0]; |
|
1169 |
yMin = yMax = coords[1]; |
|
1170 |
||
1171 |
CALC_MIN(xMin, coords[2]); |
|
1172 |
CALC_MAX(xMax, coords[2]); |
|
1173 |
CALC_MIN(yMin, coords[3]); |
|
1174 |
CALC_MAX(yMax, coords[3]); |
|
1175 |
CALC_MIN(xMin, coords[4]); |
|
1176 |
CALC_MAX(xMax, coords[4]); |
|
1177 |
CALC_MIN(yMin, coords[5]); |
|
1178 |
CALC_MAX(yMax, coords[5]); |
|
1179 |
CALC_MIN(xMin, coords[6]); |
|
1180 |
CALC_MAX(xMax, coords[6]); |
|
1181 |
CALC_MIN(yMin, coords[7]); |
|
1182 |
CALC_MAX(yMax, coords[7]); |
|
1183 |
||
1184 |
if (hnd->clipMode == PH_MODE_DRAW_CLIP) {
|
|
1185 |
||
1186 |
/* In case of drawing we could just skip curves which are completely |
|
1187 |
* out of bounds |
|
1188 |
*/ |
|
1189 |
if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax || |
|
1190 |
hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) {
|
|
1191 |
return; |
|
1192 |
} |
|
1193 |
} else {
|
|
1194 |
||
1195 |
/* In case of filling we could skip curves which are above, |
|
1196 |
* below and behind the right boundary of the visible area |
|
1197 |
*/ |
|
1198 |
||
1199 |
if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax || |
|
1200 |
hnd->dhnd->xMaxf < xMin) |
|
1201 |
{
|
|
1202 |
return; |
|
1203 |
} |
|
1204 |
||
1205 |
/* We could clamp x coordinates to the corresponding boundary |
|
1206 |
* if the curve is completely behind the left one |
|
1207 |
*/ |
|
1208 |
||
1209 |
if (hnd->dhnd->xMinf > xMax) {
|
|
1210 |
coords[0] = coords[2] = coords[4] = coords[6] = |
|
1211 |
hnd->dhnd->xMinf; |
|
1212 |
} |
|
1213 |
} |
|
1214 |
||
1215 |
if (xMax - xMin > MAX_CUB_SIZE || yMax - yMin > MAX_CUB_SIZE) {
|
|
1216 |
coords1[6] = coords[6]; |
|
1217 |
coords1[7] = coords[7]; |
|
1218 |
coords1[4] = (coords[4] + coords[6])/2.0f; |
|
1219 |
coords1[5] = (coords[5] + coords[7])/2.0f; |
|
1220 |
tx = (coords[2] + coords[4])/2.0f; |
|
1221 |
ty = (coords[3] + coords[5])/2.0f; |
|
1222 |
coords1[2] = (tx + coords1[4])/2.0f; |
|
1223 |
coords1[3] = (ty + coords1[5])/2.0f; |
|
1224 |
coords[2] = (coords[0] + coords[2])/2.0f; |
|
1225 |
coords[3] = (coords[1] + coords[3])/2.0f; |
|
1226 |
coords[4] = (coords[2] + tx)/2.0f; |
|
1227 |
coords[5] = (coords[3] + ty)/2.0f; |
|
1228 |
coords[6]=coords1[0]=(coords[4] + coords1[2])/2.0f; |
|
1229 |
coords[7]=coords1[1]=(coords[5] + coords1[3])/2.0f; |
|
1230 |
||
1231 |
ProcessMonotonicCubic(hnd, coords, pixelInfo); |
|
1232 |
||
1233 |
ProcessMonotonicCubic(hnd, coords1, pixelInfo); |
|
1234 |
||
1235 |
} else {
|
|
1236 |
DrawMonotonicCubic(hnd, coords, |
|
1237 |
/* Set checkBounds parameter if curve intersects |
|
1238 |
* boundary of the visible area. We know that the |
|
1239 |
* curve is visible, so the check is pretty simple |
|
1240 |
*/ |
|
1241 |
hnd->dhnd->xMinf > xMin || hnd->dhnd->xMaxf < xMax || |
|
1242 |
hnd->dhnd->yMinf > yMin || hnd->dhnd->yMaxf < yMax, |
|
1243 |
pixelInfo); |
|
1244 |
} |
|
1245 |
} |
|
1246 |
||
1247 |
/* |
|
1248 |
* Bite the piece of the cubic curve from start point till the point |
|
1249 |
* corresponding to the specified parameter then call ProcessMonotonicCubic for |
|
1250 |
* the bitten part. |
|
1251 |
* Note: coords array will be changed |
|
1252 |
*/ |
|
1253 |
static void ProcessFirstMonotonicPartOfCubic(ProcessHandler* hnd, |
|
1254 |
jfloat* coords, jint* pixelInfo, |
|
1255 |
jfloat t) |
|
1256 |
{
|
|
1257 |
jfloat coords1[8]; |
|
1258 |
jfloat tx, ty; |
|
1259 |
||
1260 |
coords1[0] = coords[0]; |
|
1261 |
coords1[1] = coords[1]; |
|
1262 |
tx = coords[2] + t*(coords[4] - coords[2]); |
|
1263 |
ty = coords[3] + t*(coords[5] - coords[3]); |
|
1264 |
coords1[2] = coords[0] + t*(coords[2] - coords[0]); |
|
1265 |
coords1[3] = coords[1] + t*(coords[3] - coords[1]); |
|
1266 |
coords1[4] = coords1[2] + t*(tx - coords1[2]); |
|
1267 |
coords1[5] = coords1[3] + t*(ty - coords1[3]); |
|
1268 |
coords[4] = coords[4] + t*(coords[6] - coords[4]); |
|
1269 |
coords[5] = coords[5] + t*(coords[7] - coords[5]); |
|
1270 |
coords[2] = tx + t*(coords[4] - tx); |
|
1271 |
coords[3] = ty + t*(coords[5] - ty); |
|
1272 |
coords[0]=coords1[6]=coords1[4] + t*(coords[2] - coords1[4]); |
|
1273 |
coords[1]=coords1[7]=coords1[5] + t*(coords[3] - coords1[5]); |
|
1274 |
||
1275 |
ProcessMonotonicCubic(hnd, coords1, pixelInfo); |
|
1276 |
} |
|
1277 |
||
1278 |
/* |
|
1279 |
* Split cubic curve into monotonic in X and Y parts. Calling ProcessCubic for |
|
1280 |
* each monotonic piece of the curve. |
|
1281 |
* |
|
1282 |
* Note: coords array could be changed |
|
1283 |
*/ |
|
1284 |
static void ProcessCubic(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) |
|
1285 |
{
|
|
1286 |
/* Temporary array for holding parameters corresponding to the extreme in X |
|
1287 |
* and Y points. The values are inside the (0,1) range (0 and 1 excluded) |
|
1288 |
* and in ascending order. |
|
1289 |
*/ |
|
1290 |
double params[4]; |
|
1291 |
jint cnt = 0, i; |
|
1292 |
||
1293 |
/* Simple check for monotonicity in X before searching for the extreme |
|
1294 |
* points of the X(t) function. We first check if the curve is monotonic in |
|
1295 |
* X by seeing if all of the X coordinates are strongly ordered. |
|
1296 |
*/ |
|
1297 |
if ((coords[0] > coords[2] || coords[2] > coords[4] || |
|
1298 |
coords[4] > coords[6]) && |
|
1299 |
(coords[0] < coords[2] || coords[2] < coords[4] || |
|
1300 |
coords[4] < coords[6])) |
|
1301 |
{
|
|
1302 |
/* Searching for extreme points of the X(t) function by solving |
|
1303 |
* dX(t) |
|
1304 |
* ---- = 0 equation |
|
1305 |
* dt |
|
1306 |
*/ |
|
1307 |
double ax = -coords[0] + 3*coords[2] - 3*coords[4] + coords[6]; |
|
1308 |
double bx = 2*(coords[0] - 2*coords[2] + coords[4]); |
|
1309 |
double cx = -coords[0] + coords[2]; |
|
1310 |
||
1311 |
SOLVEQUADINRANGE(ax,bx,cx,params,cnt); |
|
1312 |
} |
|
1313 |
||
1314 |
/* Simple check for monotonicity in Y before searching for the extreme |
|
1315 |
* points of the Y(t) function. We first check if the curve is monotonic in |
|
1316 |
* Y by seeing if all of the Y coordinates are strongly ordered. |
|
1317 |
*/ |
|
1318 |
if ((coords[1] > coords[3] || coords[3] > coords[5] || |
|
1319 |
coords[5] > coords[7]) && |
|
1320 |
(coords[1] < coords[3] || coords[3] < coords[5] || |
|
1321 |
coords[5] < coords[7])) |
|
1322 |
{
|
|
1323 |
/* Searching for extreme points of the Y(t) function by solving |
|
1324 |
* dY(t) |
|
1325 |
* ----- = 0 equation |
|
1326 |
* dt |
|
1327 |
*/ |
|
1328 |
double ay = -coords[1] + 3*coords[3] - 3*coords[5] + coords[7]; |
|
1329 |
double by = 2*(coords[1] - 2*coords[3] + coords[5]); |
|
1330 |
double cy = -coords[1] + coords[3]; |
|
1331 |
||
1332 |
SOLVEQUADINRANGE(ay,by,cy,params,cnt); |
|
1333 |
} |
|
1334 |
||
1335 |
if (cnt > 0) {
|
|
1336 |
/* Sorting parameter values corresponding to the extremum points of |
|
1337 |
* the curve. We are using insertion sort because of tiny size of the |
|
1338 |
* array. |
|
1339 |
*/ |
|
1340 |
jint j; |
|
1341 |
||
1342 |
for(i = 1; i < cnt; i++) {
|
|
1343 |
double value = params[i]; |
|
1344 |
for (j = i - 1; j >= 0 && params[j] > value; j--) {
|
|
1345 |
params[j + 1] = params[j]; |
|
1346 |
} |
|
1347 |
params[j + 1] = value; |
|
1348 |
} |
|
1349 |
||
1350 |
/* Processing obtained monotonic parts */ |
|
1351 |
ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo, |
|
1352 |
(jfloat)params[0]); |
|
1353 |
for (i = 1; i < cnt; i++) {
|
|
1354 |
double param = params[i] - params[i-1]; |
|
1355 |
if (param > 0) {
|
|
1356 |
ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo, |
|
1357 |
/* Scale parameter to match with rest of the curve */ |
|
1358 |
(float)(param/(1.0 - params[i - 1]))); |
|
1359 |
} |
|
1360 |
} |
|
1361 |
} |
|
1362 |
||
1363 |
ProcessMonotonicCubic(hnd,coords,pixelInfo); |
|
1364 |
} |
|
1365 |
||
1366 |
static void ProcessLine(ProcessHandler* hnd, |
|
1367 |
jfloat *coord1, jfloat *coord2, jint* pixelInfo) {
|
|
1368 |
||
1369 |
jfloat xMin, yMin, xMax, yMax; |
|
1370 |
jint X1, Y1, X2, Y2, X3, Y3, res; |
|
1371 |
jboolean clipped = JNI_FALSE; |
|
1372 |
jfloat x1 = coord1[0]; |
|
1373 |
jfloat y1 = coord1[1]; |
|
1374 |
jfloat x2 = coord2[0]; |
|
1375 |
jfloat y2 = coord2[1]; |
|
1376 |
jfloat x3,y3; |
|
1377 |
||
1378 |
jboolean lastClipped; |
|
1379 |
||
1380 |
xMin = hnd->dhnd->xMinf; |
|
1381 |
yMin = hnd->dhnd->yMinf; |
|
1382 |
xMax = hnd->dhnd->xMaxf; |
|
1383 |
yMax = hnd->dhnd->yMaxf; |
|
1384 |
||
1385 |
TESTANDCLIP(yMin, yMax, y1, x1, y2, x2, jfloat, res); |
|
1386 |
if (res == CRES_INVISIBLE) return; |
|
1387 |
clipped = IS_CLIPPED(res); |
|
1388 |
TESTANDCLIP(yMin, yMax, y2, x2, y1, x1, jfloat, res); |
|
1389 |
if (res == CRES_INVISIBLE) return; |
|
1390 |
lastClipped = IS_CLIPPED(res); |
|
1391 |
clipped = clipped || lastClipped; |
|
1392 |
||
1393 |
if (hnd->clipMode == PH_MODE_DRAW_CLIP) {
|
|
1394 |
TESTANDCLIP(xMin, xMax, |
|
1395 |
x1, y1, x2, y2, jfloat, res); |
|
1396 |
if (res == CRES_INVISIBLE) return; |
|
1397 |
clipped = clipped || IS_CLIPPED(res); |
|
1398 |
TESTANDCLIP(xMin, xMax, |
|
1399 |
x2, y2, x1, y1, jfloat, res); |
|
1400 |
if (res == CRES_INVISIBLE) return; |
|
1401 |
lastClipped = lastClipped || IS_CLIPPED(res); |
|
1402 |
clipped = clipped || lastClipped; |
|
1403 |
X1 = (jint)(x1*MDP_MULT); |
|
1404 |
Y1 = (jint)(y1*MDP_MULT); |
|
1405 |
X2 = (jint)(x2*MDP_MULT); |
|
1406 |
Y2 = (jint)(y2*MDP_MULT); |
|
1407 |
||
1408 |
hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo, |
|
1409 |
clipped, /* enable boundary checking in case |
|
1410 |
of clipping to avoid entering |
|
1411 |
out of bounds which could |
|
1412 |
happens during rounding |
|
1413 |
*/ |
|
1414 |
lastClipped /* Notify pProcessFixedLine that |
|
1415 |
this is the end of the |
|
1416 |
subpath (because of exiting |
|
1417 |
out of boundaries) |
|
1418 |
*/ |
|
1419 |
); |
|
1420 |
} else {
|
|
1421 |
/* Clamping starting from first vertex of the the processed segment |
|
1422 |
*/ |
|
1423 |
CLIPCLAMP(xMin, xMax, x1, y1, x2, y2, x3, y3, jfloat, res); |
|
1424 |
X1 = (jint)(x1*MDP_MULT); |
|
1425 |
Y1 = (jint)(y1*MDP_MULT); |
|
1426 |
||
1427 |
/* Clamping only by left boundary */ |
|
1428 |
if (res == CRES_MIN_CLIPPED) {
|
|
1429 |
X3 = (jint)(x3*MDP_MULT); |
|
1430 |
Y3 = (jint)(y3*MDP_MULT); |
|
1431 |
hnd->pProcessFixedLine(hnd, X3, Y3, X1, Y1, pixelInfo, |
|
1432 |
JNI_FALSE, lastClipped); |
|
1433 |
||
1434 |
} else if (res == CRES_INVISIBLE) {
|
|
1435 |
return; |
|
1436 |
} |
|
1437 |
||
1438 |
/* Clamping starting from last vertex of the the processed segment |
|
1439 |
*/ |
|
1440 |
CLIPCLAMP(xMin, xMax, x2, y2, x1, y1, x3, y3, jfloat, res); |
|
1441 |
||
1442 |
/* Checking if there was a clip by right boundary */ |
|
1443 |
lastClipped = lastClipped || (res == CRES_MAX_CLIPPED); |
|
1444 |
||
1445 |
X2 = (jint)(x2*MDP_MULT); |
|
1446 |
Y2 = (jint)(y2*MDP_MULT); |
|
1447 |
hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo, |
|
1448 |
JNI_FALSE, lastClipped); |
|
1449 |
||
1450 |
/* Clamping only by left boundary */ |
|
1451 |
if (res == CRES_MIN_CLIPPED) {
|
|
1452 |
X3 = (jint)(x3*MDP_MULT); |
|
1453 |
Y3 = (jint)(y3*MDP_MULT); |
|
1454 |
hnd->pProcessFixedLine(hnd, X2, Y2, X3, Y3, pixelInfo, |
|
1455 |
JNI_FALSE, lastClipped); |
|
1456 |
} |
|
1457 |
} |
|
1458 |
} |
|
1459 |
||
1460 |
jboolean ProcessPath(ProcessHandler* hnd, |
|
1461 |
jfloat transXf, jfloat transYf, |
|
1462 |
jfloat* coords, jint maxCoords, |
|
1463 |
jbyte* types, jint numTypes) |
|
1464 |
{
|
|
1465 |
jfloat tCoords[8]; |
|
1466 |
jfloat closeCoord[2]; |
|
1467 |
jint pixelInfo[5]; |
|
1468 |
jboolean skip = JNI_FALSE; |
|
1469 |
jboolean subpathStarted = JNI_FALSE; |
|
1470 |
jfloat lastX, lastY; |
|
1471 |
int i, index = 0; |
|
1472 |
||
1473 |
pixelInfo[0] = 0; |
|
1474 |
||
1475 |
/* Adding support of the KEY_STROKE_CONTROL rendering hint. |
|
1476 |
* Now we are supporting two modes: "pixels at centers" and |
|
1477 |
* "pixels at corners". |
|
1478 |
* First one is disabled by default but could be enabled by setting |
|
1479 |
* VALUE_STROKE_PURE to the rendering hint. It means that pixel at the |
|
1480 |
* screen (x,y) has (x + 0.5, y + 0.5) float coordinates. |
|
1481 |
* |
|
1482 |
* Second one is enabled by default and means straightforward mapping |
|
1483 |
* (x,y) --> (x,y) |
|
1484 |
* |
|
1485 |
*/ |
|
1486 |
if (hnd->stroke == PH_STROKE_PURE) {
|
|
1487 |
closeCoord[0] = -0.5f; |
|
1488 |
closeCoord[1] = -0.5f; |
|
1489 |
transXf -= 0.5; |
|
1490 |
transYf -= 0.5; |
|
1491 |
} else {
|
|
1492 |
closeCoord[0] = 0.0f; |
|
1493 |
closeCoord[1] = 0.0f; |
|
1494 |
} |
|
1495 |
||
1496 |
/* Adjusting boundaries to the capabilities of the ProcessPath code */ |
|
1497 |
ADJUST(hnd->dhnd->xMin, LOWER_OUT_BND, UPPER_OUT_BND); |
|
1498 |
ADJUST(hnd->dhnd->yMin, LOWER_OUT_BND, UPPER_OUT_BND); |
|
1499 |
ADJUST(hnd->dhnd->xMax, LOWER_OUT_BND, UPPER_OUT_BND); |
|
1500 |
ADJUST(hnd->dhnd->yMax, LOWER_OUT_BND, UPPER_OUT_BND); |
|
1501 |
||
1502 |
||
1503 |
/* Setting up fractional clipping box |
|
1504 |
* |
|
1505 |
* We are using following float -> int mapping: |
|
1506 |
* |
|
1507 |
* xi = floor(xf + 0.5) |
|
1508 |
* |
|
1509 |
* So, fractional values that hit the [xmin, xmax) integer interval will be |
|
1510 |
* situated inside the [xmin-0.5, xmax - 0.5) fractional interval. We are |
|
1511 |
* using EPSF constant to provide that upper boundary is not included. |
|
1512 |
*/ |
|
1513 |
hnd->dhnd->xMinf = hnd->dhnd->xMin - 0.5f; |
|
1514 |
hnd->dhnd->yMinf = hnd->dhnd->yMin - 0.5f; |
|
1515 |
hnd->dhnd->xMaxf = hnd->dhnd->xMax - 0.5f - EPSF; |
|
1516 |
hnd->dhnd->yMaxf = hnd->dhnd->yMax - 0.5f - EPSF; |
|
1517 |
||
1518 |
||
1519 |
for (i = 0; i < numTypes; i++) {
|
|
1520 |
switch (types[i]) {
|
|
1521 |
case java_awt_geom_PathIterator_SEG_MOVETO: |
|
1522 |
if (index + 2 <= maxCoords) {
|
|
1523 |
/* Performing closing of the unclosed segments */ |
|
1524 |
if (subpathStarted & !skip) {
|
|
1525 |
if (hnd->clipMode == PH_MODE_FILL_CLIP) {
|
|
1526 |
if (tCoords[0] != closeCoord[0] || |
|
1527 |
tCoords[1] != closeCoord[1]) |
|
1528 |
{
|
|
1529 |
ProcessLine(hnd, tCoords, closeCoord, |
|
1530 |
pixelInfo); |
|
1531 |
} |
|
1532 |
} |
|
1533 |
hnd->pProcessEndSubPath(hnd); |
|
1534 |
} |
|
1535 |
||
1536 |
tCoords[0] = coords[index++] + transXf; |
|
1537 |
tCoords[1] = coords[index++] + transYf; |
|
1538 |
||
1539 |
/* Checking SEG_MOVETO coordinates if they are out of the |
|
1540 |
* [LOWER_BND, UPPER_BND] range. This check also handles |
|
1541 |
* NaN and Infinity values. Skipping next path segment in |
|
1542 |
* case of invalid data. |
|
1543 |
*/ |
|
1544 |
||
1545 |
if (tCoords[0] < UPPER_BND && |
|
1546 |
tCoords[0] > LOWER_BND && |
|
1547 |
tCoords[1] < UPPER_BND && |
|
1548 |
tCoords[1] > LOWER_BND) |
|
1549 |
{
|
|
1550 |
subpathStarted = JNI_TRUE; |
|
1551 |
skip = JNI_FALSE; |
|
1552 |
closeCoord[0] = tCoords[0]; |
|
1553 |
closeCoord[1] = tCoords[1]; |
|
1554 |
} else {
|
|
1555 |
skip = JNI_TRUE; |
|
1556 |
} |
|
1557 |
} else {
|
|
1558 |
return JNI_FALSE; |
|
1559 |
} |
|
1560 |
break; |
|
1561 |
case java_awt_geom_PathIterator_SEG_LINETO: |
|
1562 |
if (index + 2 <= maxCoords) {
|
|
1563 |
lastX = tCoords[2] = coords[index++] + transXf; |
|
1564 |
lastY = tCoords[3] = coords[index++] + transYf; |
|
1565 |
||
1566 |
/* Checking SEG_LINETO coordinates if they are out of the |
|
1567 |
* [LOWER_BND, UPPER_BND] range. This check also handles |
|
1568 |
* NaN and Infinity values. Ignoring current path segment |
|
1569 |
* in case of invalid data. If segment is skipped its |
|
1570 |
* endpoint (if valid) is used to begin new subpath. |
|
1571 |
*/ |
|
1572 |
||
1573 |
if (lastX < UPPER_BND && |
|
1574 |
lastX > LOWER_BND && |
|
1575 |
lastY < UPPER_BND && |
|
1576 |
lastY > LOWER_BND) |
|
1577 |
{
|
|
1578 |
if (skip) {
|
|
1579 |
tCoords[0] = closeCoord[0] = lastX; |
|
1580 |
tCoords[1] = closeCoord[1] = lastY; |
|
1581 |
subpathStarted = JNI_TRUE; |
|
1582 |
skip = JNI_FALSE; |
|
1583 |
} else {
|
|
1584 |
ProcessLine(hnd, tCoords, tCoords + 2, |
|
1585 |
pixelInfo); |
|
1586 |
tCoords[0] = lastX; |
|
1587 |
tCoords[1] = lastY; |
|
1588 |
} |
|
1589 |
} |
|
1590 |
} else {
|
|
1591 |
return JNI_FALSE; |
|
1592 |
} |
|
1593 |
break; |
|
1594 |
case java_awt_geom_PathIterator_SEG_QUADTO: |
|
1595 |
if (index + 4 <= maxCoords) {
|
|
1596 |
tCoords[2] = coords[index++] + transXf; |
|
1597 |
tCoords[3] = coords[index++] + transYf; |
|
1598 |
lastX = tCoords[4] = coords[index++] + transXf; |
|
1599 |
lastY = tCoords[5] = coords[index++] + transYf; |
|
1600 |
||
1601 |
/* Checking SEG_QUADTO coordinates if they are out of the |
|
1602 |
* [LOWER_BND, UPPER_BND] range. This check also handles |
|
1603 |
* NaN and Infinity values. Ignoring current path segment |
|
1604 |
* in case of invalid endpoints's data. Equivalent to |
|
1605 |
* the SEG_LINETO if endpoint coordinates are valid but |
|
1606 |
* there are invalid data among other coordinates |
|
1607 |
*/ |
|
1608 |
||
1609 |
if (lastX < UPPER_BND && |
|
1610 |
lastX > LOWER_BND && |
|
1611 |
lastY < UPPER_BND && |
|
1612 |
lastY > LOWER_BND) |
|
1613 |
{
|
|
1614 |
if (skip) {
|
|
1615 |
tCoords[0] = closeCoord[0] = lastX; |
|
1616 |
tCoords[1] = closeCoord[1] = lastY; |
|
1617 |
subpathStarted = JNI_TRUE; |
|
1618 |
skip = JNI_FALSE; |
|
1619 |
} else {
|
|
1620 |
if (tCoords[2] < UPPER_BND && |
|
1621 |
tCoords[2] > LOWER_BND && |
|
1622 |
tCoords[3] < UPPER_BND && |
|
1623 |
tCoords[3] > LOWER_BND) |
|
1624 |
{
|
|
1625 |
ProcessQuad(hnd, tCoords, pixelInfo); |
|
1626 |
} else {
|
|
1627 |
ProcessLine(hnd, tCoords, |
|
1628 |
tCoords + 4, pixelInfo); |
|
1629 |
} |
|
1630 |
tCoords[0] = lastX; |
|
1631 |
tCoords[1] = lastY; |
|
1632 |
} |
|
1633 |
} |
|
1634 |
} else {
|
|
1635 |
return JNI_FALSE; |
|
1636 |
} |
|
1637 |
break; |
|
1638 |
case java_awt_geom_PathIterator_SEG_CUBICTO: |
|
1639 |
if (index + 6 <= maxCoords) {
|
|
1640 |
tCoords[2] = coords[index++] + transXf; |
|
1641 |
tCoords[3] = coords[index++] + transYf; |
|
1642 |
tCoords[4] = coords[index++] + transXf; |
|
1643 |
tCoords[5] = coords[index++] + transYf; |
|
1644 |
lastX = tCoords[6] = coords[index++] + transXf; |
|
1645 |
lastY = tCoords[7] = coords[index++] + transYf; |
|
1646 |
||
1647 |
/* Checking SEG_CUBICTO coordinates if they are out of the |
|
1648 |
* [LOWER_BND, UPPER_BND] range. This check also handles |
|
1649 |
* NaN and Infinity values. Ignoring current path segment |
|
1650 |
* in case of invalid endpoints's data. Equivalent to |
|
1651 |
* the SEG_LINETO if endpoint coordinates are valid but |
|
1652 |
* there are invalid data among other coordinates |
|
1653 |
*/ |
|
1654 |
||
1655 |
if (lastX < UPPER_BND && |
|
1656 |
lastX > LOWER_BND && |
|
1657 |
lastY < UPPER_BND && |
|
1658 |
lastY > LOWER_BND) |
|
1659 |
{
|
|
1660 |
if (skip) {
|
|
1661 |
tCoords[0] = closeCoord[0] = tCoords[6]; |
|
1662 |
tCoords[1] = closeCoord[1] = tCoords[7]; |
|
1663 |
subpathStarted = JNI_TRUE; |
|
1664 |
skip = JNI_FALSE; |
|
1665 |
} else {
|
|
1666 |
if (tCoords[2] < UPPER_BND && |
|
1667 |
tCoords[2] > LOWER_BND && |
|
1668 |
tCoords[3] < UPPER_BND && |
|
1669 |
tCoords[3] > LOWER_BND && |
|
1670 |
tCoords[4] < UPPER_BND && |
|
1671 |
tCoords[4] > LOWER_BND && |
|
1672 |
tCoords[5] < UPPER_BND && |
|
1673 |
tCoords[5] > LOWER_BND) |
|
1674 |
{
|
|
1675 |
ProcessCubic(hnd, tCoords, pixelInfo); |
|
1676 |
} else {
|
|
1677 |
ProcessLine(hnd, tCoords, tCoords + 6, |
|
1678 |
pixelInfo); |
|
1679 |
} |
|
1680 |
tCoords[0] = lastX; |
|
1681 |
tCoords[1] = lastY; |
|
1682 |
} |
|
1683 |
} |
|
1684 |
} else {
|
|
1685 |
return JNI_FALSE; |
|
1686 |
} |
|
1687 |
break; |
|
1688 |
case java_awt_geom_PathIterator_SEG_CLOSE: |
|
1689 |
if (subpathStarted && !skip) {
|
|
1690 |
skip = JNI_FALSE; |
|
1691 |
if (tCoords[0] != closeCoord[0] || |
|
1692 |
tCoords[1] != closeCoord[1]) |
|
1693 |
{
|
|
1694 |
ProcessLine(hnd, tCoords, closeCoord, pixelInfo); |
|
1695 |
/* Storing last path's point for using in |
|
1696 |
* following segments without initial moveTo |
|
1697 |
*/ |
|
1698 |
tCoords[0] = closeCoord[0]; |
|
1699 |
tCoords[1] = closeCoord[1]; |
|
1700 |
} |
|
1701 |
||
1702 |
hnd->pProcessEndSubPath(hnd); |
|
1703 |
} |
|
1704 |
||
1705 |
break; |
|
1706 |
} |
|
1707 |
} |
|
1708 |
||
1709 |
/* Performing closing of the unclosed segments */ |
|
1710 |
if (subpathStarted & !skip) {
|
|
1711 |
if (hnd->clipMode == PH_MODE_FILL_CLIP) {
|
|
1712 |
if (tCoords[0] != closeCoord[0] || |
|
1713 |
tCoords[1] != closeCoord[1]) |
|
1714 |
{
|
|
1715 |
ProcessLine(hnd, tCoords, closeCoord, |
|
1716 |
pixelInfo); |
|
1717 |
} |
|
1718 |
} |
|
1719 |
hnd->pProcessEndSubPath(hnd); |
|
1720 |
} |
|
1721 |
||
1722 |
return JNI_TRUE; |
|
1723 |
} |
|
1724 |
||
1725 |
/* TODO Add checking of the result of the malloc/realloc functions to handle |
|
1726 |
* out of memory error and don't leak earlier allocated data |
|
1727 |
*/ |
|
1728 |
||
1729 |
||
1730 |
#define ALLOC(ptr, type, n) \ |
|
1731 |
ptr = (type *)malloc((n)*sizeof(type)) |
|
1732 |
#define REALLOC(ptr, type, n) \ |
|
1733 |
ptr = (type *)realloc(ptr, (n)*sizeof(type)) |
|
1734 |
||
1735 |
||
1736 |
struct _Edge; |
|
1737 |
||
1738 |
typedef struct _Point {
|
|
1739 |
jint x; |
|
1740 |
jint y; |
|
1741 |
jboolean lastPoint; |
|
1742 |
struct _Point* prev; |
|
1743 |
struct _Point* next; |
|
1744 |
struct _Point* nextByY; |
|
1745 |
jboolean endSL; |
|
1746 |
struct _Edge* edge; |
|
1747 |
} Point; |
|
1748 |
||
1749 |
||
1750 |
typedef struct _Edge {
|
|
1751 |
jint x; |
|
1752 |
jint dx; |
|
1753 |
Point* p; |
|
1754 |
jint dir; |
|
1755 |
struct _Edge* prev; |
|
1756 |
struct _Edge* next; |
|
1757 |
} Edge; |
|
1758 |
||
1759 |
/* Size of the default buffer in the FillData structure. This buffer is |
|
1760 |
* replaced with heap allocated in case of large paths. |
|
1761 |
*/ |
|
1762 |
#define DF_MAX_POINT 256 |
|
1763 |
||
1764 |
/* Following structure accumulates points of the non-continuous flattened |
|
1765 |
* path during iteration through the origin path's segments . The end |
|
1766 |
* of the each subpath is marked as lastPoint flag set at the last point |
|
1767 |
*/ |
|
1768 |
||
1769 |
typedef struct {
|
|
1770 |
Point *plgPnts; |
|
1771 |
Point dfPlgPnts[DF_MAX_POINT]; |
|
1772 |
jint plgSize; |
|
1773 |
jint plgMax; |
|
1774 |
jint plgYMin; |
|
1775 |
jint plgYMax; |
|
1776 |
} FillData; |
|
1777 |
||
1778 |
#define FD_INIT(PTR) \ |
|
1779 |
do { \
|
|
1780 |
(PTR)->plgPnts = (PTR)->dfPlgPnts; \ |
|
1781 |
(PTR)->plgSize = 0; \ |
|
1782 |
(PTR)->plgMax = DF_MAX_POINT; \ |
|
1783 |
} while(0) |
|
1784 |
||
1785 |
#define FD_ADD_POINT(PTR, X, Y, LASTPT) \ |
|
1786 |
do { \
|
|
1787 |
Point* _pnts = (PTR)->plgPnts; \ |
|
1788 |
jint _size = (PTR)->plgSize; \ |
|
1789 |
if (_size >= (PTR)->plgMax) { \
|
|
1790 |
jint newMax = (PTR)->plgMax*2; \ |
|
1791 |
if ((PTR)->plgPnts == (PTR)->dfPlgPnts) { \
|
|
1792 |
(PTR)->plgPnts = (Point*)malloc(newMax*sizeof(Point)); \ |
|
1793 |
memcpy((PTR)->plgPnts, _pnts, _size*sizeof(Point)); \ |
|
1794 |
} else { \
|
|
1795 |
(PTR)->plgPnts = (Point*)realloc( \ |
|
1796 |
_pnts, newMax*sizeof(Point)); \ |
|
1797 |
} \ |
|
1798 |
_pnts = (PTR)->plgPnts; \ |
|
1799 |
(PTR)->plgMax = newMax; \ |
|
1800 |
} \ |
|
1801 |
_pnts += _size; \ |
|
1802 |
_pnts->x = X; \ |
|
1803 |
_pnts->y = Y; \ |
|
1804 |
_pnts->lastPoint = LASTPT; \ |
|
1805 |
if (_size) { \
|
|
1806 |
if ((PTR)->plgYMin > Y) (PTR)->plgYMin = Y; \ |
|
1807 |
if ((PTR)->plgYMax < Y) (PTR)->plgYMax = Y; \ |
|
1808 |
} else { \
|
|
1809 |
(PTR)->plgYMin = Y; \ |
|
1810 |
(PTR)->plgYMax = Y; \ |
|
1811 |
} \ |
|
1812 |
(PTR)->plgSize = _size + 1; \ |
|
1813 |
} while(0) |
|
1814 |
||
1815 |
||
1816 |
#define FD_FREE_POINTS(PTR) \ |
|
1817 |
do { \
|
|
1818 |
if ((PTR)->plgPnts != (PTR)->dfPlgPnts) { \
|
|
1819 |
free((PTR)->plgPnts); \ |
|
1820 |
} \ |
|
1821 |
} while(0) |
|
1822 |
||
1823 |
#define FD_IS_EMPTY(PTR) (!((PTR)->plgSize)) |
|
1824 |
||
1825 |
#define FD_IS_ENDED(PTR) ((PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint) |
|
1826 |
||
1827 |
#define FD_SET_ENDED(PTR) \ |
|
1828 |
do { \
|
|
1829 |
(PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint = JNI_TRUE; \ |
|
1830 |
} while(0) |
|
1831 |
||
1832 |
#define PFD(HND) ((FillData*)(HND)->pData) |
|
1833 |
||
1834 |
/* Bubble sorting in the ascending order of the linked list. This |
|
1835 |
* implementation stops processing the list if there were no changes during the |
|
1836 |
* previous pass. |
|
1837 |
* |
|
1838 |
* LIST - ptr to the ptr to the first element of the list |
|
1839 |
* ETYPE - type of the element in the list |
|
1840 |
* NEXT - accessor to the next field in the list element |
|
1841 |
* GET_LKEY - accessor to the key of the list element |
|
1842 |
*/ |
|
1843 |
#define LBUBBLE_SORT(LIST, ETYPE, NEXT, GET_LKEY) \ |
|
1844 |
do { \
|
|
1845 |
ETYPE *p, *q, *r, *s = NULL, *temp ; \ |
|
1846 |
jint wasSwap = 1; \ |
|
1847 |
/* r precedes p and s points to the node up to which comparisons \ |
|
1848 |
* are to be made */ \ |
|
1849 |
while ( s != NEXT(*LIST) && wasSwap) { \
|
|
1850 |
r = p = *LIST; \ |
|
1851 |
q = NEXT(p); \ |
|
1852 |
wasSwap = 0; \ |
|
1853 |
while ( p != s ) { \
|
|
1854 |
if (GET_LKEY(p) >= GET_LKEY(q)) { \
|
|
1855 |
wasSwap = 1; \ |
|
1856 |
if ( p == *LIST ) { \
|
|
1857 |
temp = NEXT(q); \ |
|
1858 |
NEXT(q) = p ; \ |
|
1859 |
NEXT(p) = temp ; \ |
|
1860 |
*LIST = q ; \ |
|
1861 |
r = q ; \ |
|
1862 |
} else { \
|
|
1863 |
temp = NEXT(q); \ |
|
1864 |
NEXT(q) = p ; \ |
|
1865 |
NEXT(p) = temp ; \ |
|
1866 |
NEXT(r) = q ; \ |
|
1867 |
r = q ; \ |
|
1868 |
} \ |
|
1869 |
} else { \
|
|
1870 |
r = p ; \ |
|
1871 |
p = NEXT(p); \ |
|
1872 |
} \ |
|
1873 |
q = NEXT(p); \ |
|
1874 |
if ( q == s ) s = p ; \ |
|
1875 |
} \ |
|
1876 |
} \ |
|
1877 |
} while(0); |
|
1878 |
||
1879 |
/* Accessors for the Edge structure to work with LBUBBLE_SORT */ |
|
1880 |
#define GET_ACTIVE_KEY(a) (a->x) |
|
1881 |
#define GET_ACTIVE_NEXT(a) ((a)->next) |
|
1882 |
||
1883 |
/* TODO: Implement stack/heap allocation technique for active edges |
|
1884 |
*/ |
|
1885 |
#define DELETE_ACTIVE(head,pnt) \ |
|
1886 |
do { \
|
|
1887 |
Edge *prevp = pnt->prev; \ |
|
1888 |
Edge *nextp = pnt->next; \ |
|
1889 |
if (prevp) { \
|
|
1890 |
prevp->next = nextp; \ |
|
1891 |
} else { \
|
|
1892 |
head = nextp; \ |
|
1893 |
} \ |
|
1894 |
if (nextp) { \
|
|
1895 |
nextp->prev = prevp; \ |
|
1896 |
} \ |
|
1897 |
} while(0); |
|
1898 |
||
1899 |
#define INSERT_ACTIVE(head,pnt,cy) \ |
|
1900 |
do { \
|
|
1901 |
Point *np = pnt->next; \ |
|
1902 |
Edge *ne = active + nact; \ |
|
1903 |
if (pnt->y == np->y) { \
|
|
1904 |
/* Skipping horizontal segments */ \ |
|
1905 |
break; \ |
|
1906 |
} else { \
|
|
1907 |
jint dX = np->x - pnt->x; \ |
|
1908 |
jint dY = np->y - pnt->y; \ |
|
1909 |
jint dy; \ |
|
1910 |
if (pnt->y < np->y) { \
|
|
1911 |
ne->dir = -1; \ |
|
1912 |
ne->p = pnt; \ |
|
1913 |
ne->x = pnt->x; \ |
|
1914 |
dy = cy - pnt->y; \ |
|
1915 |
} else { /* pnt->y > np->y */ \
|
|
1916 |
ne->dir = 1; \ |
|
1917 |
ne->p = np; \ |
|
1918 |
ne->x = np->x; \ |
|
1919 |
dy = cy - np->y; \ |
|
1920 |
} \ |
|
1921 |
\ |
|
1922 |
/* We need to worry only about dX because dY is in */\ |
|
1923 |
/* denominator and abs(dy) < MDP_MULT (cy is a first */\ |
|
1924 |
/* scanline of the scan converted segment and we subtract */\ |
|
1925 |
/* y coordinate of the nearest segment's end from it to */\ |
|
1926 |
/* obtain dy) */\ |
|
1927 |
if (ABS32(dX) > CALC_BND) { \
|
|
1928 |
ne->dx = (jint)((((jdouble)dX)*MDP_MULT)/dY); \ |
|
1929 |
ne->x += (jint)((((jdouble)dX)*dy)/dY); \ |
|
1930 |
} else { \
|
|
1931 |
ne->dx = ((dX)<<MDP_PREC)/dY; \ |
|
1932 |
ne->x += (dX*dy)/dY; \ |
|
1933 |
} \ |
|
1934 |
} \ |
|
1935 |
ne->next = head; \ |
|
1936 |
ne->prev = NULL; \ |
|
1937 |
if (head) { \
|
|
1938 |
head->prev = ne; \ |
|
1939 |
} \ |
|
1940 |
head = active + nact; \ |
|
1941 |
pnt->edge = head; \ |
|
1942 |
nact++; \ |
|
1943 |
} while(0); |
|
1944 |
||
1945 |
void FillPolygon(ProcessHandler* hnd, |
|
1946 |
jint fillRule) {
|
|
1947 |
jint k, y, xl, xr; |
|
1948 |
jint drawing; |
|
1949 |
Edge* activeList, *active; |
|
1950 |
Edge* curEdge, *prevEdge; |
|
1951 |
jint nact; |
|
1952 |
jint n; |
|
1953 |
Point* pt, *curpt, *ept; |
|
1954 |
Point** yHash; |
|
1955 |
Point** curHash; |
|
1956 |
jint rightBnd = hnd->dhnd->xMax - 1; |
|
1957 |
FillData* pfd = (FillData*)(hnd->pData); |
|
1958 |
jint yMin = pfd->plgYMin; |
|
1959 |
jint yMax = pfd->plgYMax; |
|
1960 |
jint hashSize = ((yMax - yMin)>>MDP_PREC) + 4; |
|
1961 |
||
1962 |
/* Because of support of the KEY_STROKE_CONTROL hint we are performing |
|
1963 |
* shift of the coordinates at the higher level |
|
1964 |
*/ |
|
1965 |
jint hashOffset = ((yMin - 1) & MDP_W_MASK); |
|
1966 |
||
1967 |
// TODO creating lists using fake first element to avoid special casing of |
|
1968 |
// the first element in the list (which otherwise should be performed in each |
|
1969 |
// list operation) |
|
1970 |
||
1971 |
/* Winding counter */ |
|
1972 |
jint counter; |
|
1973 |
||
1974 |
/* Calculating mask to be applied to the winding counter */ |
|
1975 |
jint counterMask = |
|
1976 |
(fillRule == java_awt_geom_PathIterator_WIND_NON_ZERO)? -1:1; |
|
1977 |
pt = pfd->plgPnts; |
|
1978 |
n = pfd->plgSize; |
|
1979 |
||
1980 |
if (n <=1) return; |
|
1981 |
||
1982 |
ALLOC(yHash, Point*, hashSize); |
|
1983 |
for (k = 0; k < hashSize; k++) {
|
|
1984 |
yHash[k] = NULL; |
|
1985 |
} |
|
1986 |
||
1987 |
ALLOC(active, Edge, n); |
|
1988 |
||
1989 |
/* Creating double linked list (prev, next links) describing path order and |
|
1990 |
* hash table with points which fall between scanlines. nextByY link is |
|
1991 |
* used for the points which are between same scanlines. Scanlines are |
|
1992 |
* passed through the centers of the pixels. |
|
1993 |
*/ |
|
1994 |
curpt = pt; |
|
1995 |
curpt->prev = NULL; |
|
1996 |
ept = pt + n - 1; |
|
1997 |
for (curpt = pt; curpt != ept; curpt++) {
|
|
1998 |
Point* nextpt = curpt + 1; |
|
1999 |
curHash = yHash + ((curpt->y - hashOffset - 1) >> MDP_PREC); |
|
2000 |
curpt->nextByY = *curHash; |
|
2001 |
*curHash = curpt; |
|
2002 |
curpt->next = nextpt; |
|
2003 |
nextpt->prev = curpt; |
|
2004 |
curpt->edge = NULL; |
|
2005 |
} |
|
2006 |
||
2007 |
curHash = yHash + ((ept->y - hashOffset - 1) >> MDP_PREC); |
|
2008 |
ept->nextByY = *curHash; |
|
2009 |
*curHash = ept; |
|
2010 |
ept->next = NULL; |
|
2011 |
ept->edge = NULL; |
|
2012 |
nact = 0; |
|
2013 |
||
2014 |
activeList = NULL; |
|
2015 |
for (y=hashOffset + MDP_MULT,k = 0; |
|
2016 |
y<=yMax && k < hashSize; y += MDP_MULT, k++) |
|
2017 |
{
|
|
2018 |
for(pt = yHash[k];pt; pt=pt->nextByY) {
|
|
2019 |
/* pt->y should be inside hashed interval |
|
2020 |
* assert(y-MDP_MULT <= pt->y && pt->y < y); |
|
2021 |
*/ |
|
2022 |
if (pt->prev && !pt->prev->lastPoint) {
|
|
2023 |
if (pt->prev->edge && pt->prev->y <= y) {
|
|
2024 |
DELETE_ACTIVE(activeList, pt->prev->edge); |
|
2025 |
pt->prev->edge = NULL; |
|
2026 |
} else if (pt->prev->y > y) {
|
|
2027 |
INSERT_ACTIVE(activeList, pt->prev, y); |
|
2028 |
} |
|
2029 |
} |
|
2030 |
||
2031 |
if (!pt->lastPoint && pt->next) {
|
|
2032 |
if (pt->edge && pt->next->y <= y) {
|
|
2033 |
DELETE_ACTIVE(activeList, pt->edge); |
|
2034 |
pt->edge = NULL; |
|
2035 |
} else if (pt->next->y > y) {
|
|
2036 |
INSERT_ACTIVE(activeList, pt, y); |
|
2037 |
} |
|
2038 |
} |
|
2039 |
} |
|
2040 |
||
2041 |
if (!activeList) continue; |
|
2042 |
||
2043 |
/* We could not use O(N) Radix sort here because in most cases list of |
|
2044 |
* edges almost sorted. So, bubble sort (O(N^2))is working much |
|
2045 |
* better. Note, in case of array of edges Shell sort is more |
|
2046 |
* efficient. |
|
2047 |
*/ |
|
2048 |
LBUBBLE_SORT((&activeList), Edge, GET_ACTIVE_NEXT, GET_ACTIVE_KEY); |
|
2049 |
||
2050 |
/* Correction of the back links in the double linked edge list */ |
|
2051 |
curEdge=activeList; |
|
2052 |
prevEdge = NULL; |
|
2053 |
while (curEdge) {
|
|
2054 |
curEdge->prev = prevEdge; |
|
2055 |
prevEdge = curEdge; |
|
2056 |
curEdge = curEdge->next; |
|
2057 |
} |
|
2058 |
||
2059 |
xl = xr = hnd->dhnd->xMin; |
|
2060 |
curEdge = activeList; |
|
2061 |
counter = 0; |
|
2062 |
drawing = 0; |
|
2063 |
for(;curEdge; curEdge = curEdge->next) {
|
|
2064 |
counter += curEdge->dir; |
|
2065 |
if ((counter & counterMask) && !drawing) {
|
|
2066 |
xl = (curEdge->x + MDP_MULT - 1)>>MDP_PREC; |
|
2067 |
drawing = 1; |
|
2068 |
} |
|
2069 |
||
2070 |
if (!(counter & counterMask) && drawing) {
|
|
2071 |
xr = (curEdge->x - 1)>>MDP_PREC; |
|
2072 |
if (xl <= xr) {
|
|
2073 |
hnd->dhnd->pDrawScanline(hnd->dhnd, xl, xr, y >> MDP_PREC); |
|
2074 |
} |
|
2075 |
drawing = 0; |
|
2076 |
} |
|
2077 |
||
2078 |
curEdge->x += curEdge->dx; |
|
2079 |
} |
|
2080 |
||
2081 |
/* Performing drawing till the right boundary (for correct rendering |
|
2082 |
* shapes clipped at the right side) |
|
2083 |
*/ |
|
2084 |
if (drawing && xl <= rightBnd) {
|
|
2085 |
hnd->dhnd->pDrawScanline(hnd->dhnd, xl, rightBnd, y >> MDP_PREC); |
|
2086 |
} |
|
2087 |
} |
|
2088 |
free(active); |
|
2089 |
free(yHash); |
|
2090 |
} |
|
2091 |
||
2092 |
||
2093 |
||
2094 |
void StoreFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2, |
|
2095 |
jint* pixelInfo,jboolean checkBounds, |
|
2096 |
jboolean endSubPath) {
|
|
2097 |
FillData* pfd; |
|
2098 |
jint outXMin, outXMax, outYMin, outYMax; |
|
2099 |
jint x3, y3, res; |
|
2100 |
||
2101 |
/* There is no need to round line coordinates to the forward differencing |
|
2102 |
* precision anymore. Such a rounding was used for preventing the curve go |
|
2103 |
* out the endpoint (this sometimes does not help). The problem was fixed |
|
2104 |
* in the forward differencing loops. |
|
2105 |
*/ |
|
2106 |
||
2107 |
if (checkBounds) {
|
|
2108 |
jboolean lastClipped = JNI_FALSE; |
|
2109 |
||
2110 |
/* This function is used only for filling shapes, so there is no |
|
2111 |
* check for the type of clipping |
|
2112 |
*/ |
|
2113 |
outXMin = (jint)(hnd->dhnd->xMinf * MDP_MULT); |
|
2114 |
outXMax = (jint)(hnd->dhnd->xMaxf * MDP_MULT); |
|
2115 |
outYMin = (jint)(hnd->dhnd->yMinf * MDP_MULT); |
|
2116 |
outYMax = (jint)(hnd->dhnd->yMaxf * MDP_MULT); |
|
2117 |
||
2118 |
TESTANDCLIP(outYMin, outYMax, y1, x1, y2, x2, jint, res); |
|
2119 |
if (res == CRES_INVISIBLE) return; |
|
2120 |
TESTANDCLIP(outYMin, outYMax, y2, x2, y1, x1, jint, res); |
|
2121 |
if (res == CRES_INVISIBLE) return; |
|
2122 |
lastClipped = IS_CLIPPED(res); |
|
2123 |
||
2124 |
/* Clamping starting from first vertex of the the processed segment */ |
|
2125 |
CLIPCLAMP(outXMin, outXMax, x1, y1, x2, y2, x3, y3, jint, res); |
|
2126 |
||
2127 |
/* Clamping only by left boundary */ |
|
2128 |
if (res == CRES_MIN_CLIPPED) {
|
|
2129 |
StoreFixedLine(hnd, x3, y3, x1, y1, pixelInfo, |
|
2130 |
JNI_FALSE, lastClipped); |
|
2131 |
||
2132 |
} else if (res == CRES_INVISIBLE) {
|
|
2133 |
return; |
|
2134 |
} |
|
2135 |
||
2136 |
/* Clamping starting from last vertex of the the processed segment */ |
|
2137 |
CLIPCLAMP(outXMin, outXMax, x2, y2, x1, y1, x3, y3, jint, res); |
|
2138 |
||
2139 |
/* Checking if there was a clip by right boundary */ |
|
2140 |
lastClipped = lastClipped || (res == CRES_MAX_CLIPPED); |
|
2141 |
||
2142 |
StoreFixedLine(hnd, x1, y1, x2, y2, pixelInfo, |
|
2143 |
JNI_FALSE, lastClipped); |
|
2144 |
||
2145 |
/* Clamping only by left boundary */ |
|
2146 |
if (res == CRES_MIN_CLIPPED) {
|
|
2147 |
StoreFixedLine(hnd, x2, y2, x3, y3, pixelInfo, |
|
2148 |
JNI_FALSE, lastClipped); |
|
2149 |
} |
|
2150 |
||
2151 |
return; |
|
2152 |
} |
|
2153 |
pfd = (FillData*)(hnd->pData); |
|
2154 |
||
2155 |
/* Adding first point of the line only in case of empty or just finished |
|
2156 |
* path |
|
2157 |
*/ |
|
2158 |
if (FD_IS_EMPTY(pfd) || FD_IS_ENDED(pfd)) {
|
|
2159 |
FD_ADD_POINT(pfd, x1, y1, JNI_FALSE); |
|
2160 |
} |
|
2161 |
||
2162 |
FD_ADD_POINT(pfd, x2, y2, JNI_FALSE); |
|
2163 |
||
2164 |
if (endSubPath) {
|
|
2165 |
FD_SET_ENDED(pfd); |
|
2166 |
} |
|
2167 |
} |
|
2168 |
||
2169 |
||
2170 |
static void endSubPath(ProcessHandler* hnd) {
|
|
2171 |
FillData* pfd = (FillData*)(hnd->pData); |
|
2172 |
if (!FD_IS_EMPTY(pfd)) {
|
|
2173 |
FD_SET_ENDED(pfd); |
|
2174 |
} |
|
2175 |
} |
|
2176 |
||
2177 |
static void stubEndSubPath(ProcessHandler* hnd) {
|
|
2178 |
} |
|
2179 |
||
2180 |
jboolean doFillPath(DrawHandler* dhnd, |
|
2181 |
jint transX, jint transY, |
|
2182 |
jfloat* coords, jint maxCoords, |
|
2183 |
jbyte* types, jint numTypes, |
|
2184 |
PHStroke stroke, jint fillRule) |
|
2185 |
{
|
|
2186 |
jint res; |
|
2187 |
||
2188 |
FillData fillData; |
|
2189 |
||
2190 |
ProcessHandler hnd = |
|
2191 |
{
|
|
2192 |
&StoreFixedLine, |
|
2193 |
&endSubPath, |
|
2194 |
NULL, |
|
2195 |
PH_STROKE_DEFAULT, |
|
2196 |
PH_MODE_FILL_CLIP, |
|
2197 |
NULL |
|
2198 |
}; |
|
2199 |
||
2200 |
/* Initialization of the following fields in the declaration of the hnd |
|
2201 |
* above causes warnings on sun studio compiler with -xc99=%none option |
|
2202 |
* applied (this option means compliance with C90 standard instead of C99) |
|
2203 |
*/ |
|
2204 |
hnd.dhnd = dhnd; |
|
2205 |
hnd.pData = &fillData; |
|
2206 |
hnd.stroke = stroke; |
|
2207 |
||
2208 |
FD_INIT(&fillData); |
|
2209 |
res = ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, |
|
2210 |
coords, maxCoords, types, numTypes); |
|
2211 |
if (!res) {
|
|
2212 |
FD_FREE_POINTS(&fillData); |
|
2213 |
return JNI_FALSE; |
|
2214 |
} |
|
2215 |
FillPolygon(&hnd, fillRule); |
|
2216 |
FD_FREE_POINTS(&fillData); |
|
2217 |
return JNI_TRUE; |
|
2218 |
} |
|
2219 |
||
2220 |
jboolean doDrawPath(DrawHandler* dhnd, |
|
2221 |
void (*pProcessEndSubPath)(ProcessHandler*), |
|
2222 |
jint transX, jint transY, |
|
2223 |
jfloat* coords, jint maxCoords, |
|
2224 |
jbyte* types, jint numTypes, PHStroke stroke) |
|
2225 |
{
|
|
2226 |
ProcessHandler hnd = |
|
2227 |
{
|
|
2228 |
&ProcessFixedLine, |
|
2229 |
NULL, |
|
2230 |
NULL, |
|
2231 |
PH_STROKE_DEFAULT, |
|
2232 |
PH_MODE_DRAW_CLIP, |
|
2233 |
NULL |
|
2234 |
}; |
|
2235 |
||
2236 |
/* Initialization of the following fields in the declaration of the hnd |
|
2237 |
* above causes warnings on sun studio compiler with -xc99=%none option |
|
2238 |
* applied (this option means compliance with C90 standard instead of C99) |
|
2239 |
*/ |
|
2240 |
hnd.dhnd = dhnd; |
|
2241 |
hnd.stroke = stroke; |
|
2242 |
||
2243 |
hnd.pProcessEndSubPath = (pProcessEndSubPath == NULL)? |
|
2244 |
stubEndSubPath : pProcessEndSubPath; |
|
2245 |
return ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, coords, maxCoords, |
|
2246 |
types, numTypes); |
|
2247 |
} |