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