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