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