| /* |
| * Copyright (c) 2005, 2013, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| #include <math.h> |
| #include <assert.h> |
| #include <stdlib.h> |
| #include <string.h> |
| |
| #include "j2d_md.h" |
| #include "java_awt_geom_PathIterator.h" |
| |
| #include "ProcessPath.h" |
| |
| /* |
| * This framework performs filling and drawing of paths with sub-pixel |
| * precision. Also, it performs clipping by the specified view area. |
| * |
| * Drawing of the shapes is performed not pixel by pixel but segment by segment |
| * except several pixels near endpoints of the drawn line. This approach saves |
| * lot's of cpu cycles especially in case of large primitives (like ovals with |
| * sizes more than 50) and helps in achieving appropriate visual quality. Also, |
| * such method of drawing is useful for the accelerated pipelines where |
| * overhead of the per-pixel drawing could eliminate all benefits of the |
| * hardware acceleration. |
| * |
| * Filling of the path was taken from |
| * |
| * [Graphics Gems, edited by Andrew S Glassner. Academic Press 1990, |
| * ISBN 0-12-286165-5 (Concave polygon scan conversion), 87-91] |
| * |
| * and modified to work with sub-pixel precision and non-continuous paths. |
| * It's also speeded up by using hash table by rows of the filled objects. |
| * |
| * Here is high level scheme showing the rendering process: |
| * |
| * doDrawPath doFillPath |
| * \ / |
| * ProcessPath |
| * | |
| * CheckPathSegment |
| * | |
| * --------+------ |
| * | | |
| * | | |
| * | | |
| * _->ProcessCurve | |
| * / / | | |
| * \___/ | | |
| * | | |
| * DrawCurve ProcessLine |
| * \ / |
| * \ / |
| * \ / |
| * \ / |
| * ------+------ |
| * (filling) / \ (drawing) |
| * / \ |
| * Clipping and Clipping |
| * clamping \ |
| * | \ |
| * StoreFixedLine ProcessFixedLine |
| * | / \ |
| * | / \ |
| * FillPolygon PROCESS_LINE PROCESS_POINT |
| * |
| * |
| * |
| * CheckPathSegment - rough checking and skipping path's segments in case of |
| * invalid or huge coordinates of the control points to |
| * avoid calculation problems with NaNs and values close |
| * to the FLT_MAX |
| * |
| * ProcessCurve - (ProcessQuad, ProcessCubic) Splitting the curve into |
| * monotonic parts having appropriate size (calculated as |
| * boundary box of the control points) |
| * |
| * DrawMonotonicCurve - (DrawMonotonicQuad, DrawMonotonicCubic) flattening |
| * monotonic curve using adaptive forward differencing |
| * |
| * StoreFixedLine - storing segment from the flattened path to the |
| * FillData structure. Performing clipping and clamping if |
| * necessary. |
| * |
| * PROCESS_LINE, PROCESS_POINT - Helpers for calling appropriate primitive from |
| * DrawHandler structure |
| * |
| * ProcessFixedLine - Drawing line segment with subpixel precision. |
| * |
| */ |
| |
| #define PROCESS_LINE(hnd, fX0, fY0, fX1, fY1, checkBounds, pixelInfo) \ |
| do { \ |
| jint X0 = (fX0) >> MDP_PREC; \ |
| jint Y0 = (fY0) >> MDP_PREC; \ |
| jint X1 = (fX1) >> MDP_PREC; \ |
| jint Y1 = (fY1) >> MDP_PREC; \ |
| jint res; \ |
| \ |
| /* Checking bounds and clipping if necessary. \ |
| * REMIND: It's temporary solution to avoid OOB in rendering code. \ |
| * Current approach uses float equations which are unreliable for \ |
| * clipping and makes assumptions about the line biases of the \ |
| * rendering algorithm. Also, clipping code should be moved down \ |
| * into only those output renderers that need it. \ |
| */ \ |
| if (checkBounds) { \ |
| jfloat xMinf = hnd->dhnd->xMinf + 0.5f; \ |
| jfloat yMinf = hnd->dhnd->yMinf + 0.5f; \ |
| jfloat xMaxf = hnd->dhnd->xMaxf + 0.5f; \ |
| jfloat yMaxf = hnd->dhnd->yMaxf + 0.5f; \ |
| TESTANDCLIP(yMinf, yMaxf, Y0, X0, Y1, X1, jint, res); \ |
| if (res == CRES_INVISIBLE) break; \ |
| TESTANDCLIP(yMinf, yMaxf, Y1, X1, Y0, X0, jint, res); \ |
| if (res == CRES_INVISIBLE) break; \ |
| TESTANDCLIP(xMinf, xMaxf, X0, Y0, X1, Y1, jint, res); \ |
| if (res == CRES_INVISIBLE) break; \ |
| TESTANDCLIP(xMinf, xMaxf, X1, Y1, X0, Y0, jint, res); \ |
| if (res == CRES_INVISIBLE) break; \ |
| } \ |
| \ |
| /* Handling lines having just one pixel */ \ |
| if (((X0^X1) | (Y0^Y1)) == 0) { \ |
| if (pixelInfo[0] == 0) { \ |
| pixelInfo[0] = 1; \ |
| pixelInfo[1] = X0; \ |
| pixelInfo[2] = Y0; \ |
| pixelInfo[3] = X0; \ |
| pixelInfo[4] = Y0; \ |
| hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ |
| } else if ((X0 != pixelInfo[3] || Y0 != pixelInfo[4]) && \ |
| (X0 != pixelInfo[1] || Y0 != pixelInfo[2])) { \ |
| hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ |
| pixelInfo[3] = X0; \ |
| pixelInfo[4] = Y0; \ |
| } \ |
| break; \ |
| } \ |
| \ |
| if (pixelInfo[0] && \ |
| ((pixelInfo[1] == X0 && pixelInfo[2] == Y0) || \ |
| (pixelInfo[3] == X0 && pixelInfo[4] == Y0))) \ |
| { \ |
| hnd->dhnd->pDrawPixel(hnd->dhnd, X0, Y0); \ |
| } \ |
| \ |
| hnd->dhnd->pDrawLine(hnd->dhnd, X0, Y0, X1, Y1); \ |
| \ |
| if (pixelInfo[0] == 0) { \ |
| pixelInfo[0] = 1; \ |
| pixelInfo[1] = X0; \ |
| pixelInfo[2] = Y0; \ |
| pixelInfo[3] = X0; \ |
| pixelInfo[4] = Y0; \ |
| } \ |
| \ |
| /* Switch on last pixel of the line if it was already \ |
| * drawn during rendering of the previous segments \ |
| */ \ |
| if ((pixelInfo[1] == X1 && pixelInfo[2] == Y1) || \ |
| (pixelInfo[3] == X1 && pixelInfo[4] == Y1)) \ |
| { \ |
| hnd->dhnd->pDrawPixel(hnd->dhnd, X1, Y1); \ |
| } \ |
| pixelInfo[3] = X1; \ |
| pixelInfo[4] = Y1; \ |
| } while(0) |
| |
| #define PROCESS_POINT(hnd, fX, fY, checkBounds, pixelInfo) \ |
| do { \ |
| jint X_ = (fX)>> MDP_PREC; \ |
| jint Y_ = (fY)>> MDP_PREC; \ |
| if (checkBounds && \ |
| (hnd->dhnd->yMin > Y_ || \ |
| hnd->dhnd->yMax <= Y_ || \ |
| hnd->dhnd->xMin > X_ || \ |
| hnd->dhnd->xMax <= X_)) break; \ |
| /* \ |
| * (X_,Y_) should be inside boundaries \ |
| * \ |
| * assert(hnd->dhnd->yMin <= Y_ && \ |
| * hnd->dhnd->yMax > Y_ && \ |
| * hnd->dhnd->xMin <= X_ && \ |
| * hnd->dhnd->xMax > X_); \ |
| * \ |
| */ \ |
| if (pixelInfo[0] == 0) { \ |
| pixelInfo[0] = 1; \ |
| pixelInfo[1] = X_; \ |
| pixelInfo[2] = Y_; \ |
| pixelInfo[3] = X_; \ |
| pixelInfo[4] = Y_; \ |
| hnd->dhnd->pDrawPixel(hnd->dhnd, X_, Y_); \ |
| } else if ((X_ != pixelInfo[3] || Y_ != pixelInfo[4]) && \ |
| (X_ != pixelInfo[1] || Y_ != pixelInfo[2])) { \ |
| hnd->dhnd->pDrawPixel(hnd->dhnd, X_, Y_); \ |
| pixelInfo[3] = X_; \ |
| pixelInfo[4] = Y_; \ |
| } \ |
| } while(0) |
| |
| |
| /* |
| * Constants for the forward differencing |
| * of the cubic and quad curves |
| */ |
| |
| /* Maximum size of the cubic curve (calculated as the size of the bounding box |
| * of the control points) which could be rendered without splitting |
| */ |
| #define MAX_CUB_SIZE 256 |
| |
| /* Maximum size of the quad curve (calculated as the size of the bounding box |
| * of the control points) which could be rendered without splitting |
| */ |
| #define MAX_QUAD_SIZE 1024 |
| |
| /* Default power of 2 steps used in the forward differencing. Here DF prefix |
| * stands for DeFault. Constants below are used as initial values for the |
| * adaptive forward differencing algorithm. |
| */ |
| #define DF_CUB_STEPS 3 |
| #define DF_QUAD_STEPS 2 |
| |
| /* Shift of the current point of the curve for preparing to the midpoint |
| * rounding |
| */ |
| #define DF_CUB_SHIFT (FWD_PREC + DF_CUB_STEPS*3 - MDP_PREC) |
| #define DF_QUAD_SHIFT (FWD_PREC + DF_QUAD_STEPS*2 - MDP_PREC) |
| |
| /* Default amount of steps of the forward differencing */ |
| #define DF_CUB_COUNT (1<<DF_CUB_STEPS) |
| #define DF_QUAD_COUNT (1<<DF_QUAD_STEPS) |
| |
| /* Default boundary constants used to check the necessity of the restepping */ |
| #define DF_CUB_DEC_BND (1<<(DF_CUB_STEPS*3 + FWD_PREC + 2)) |
| #define DF_CUB_INC_BND (1<<(DF_CUB_STEPS*3 + FWD_PREC - 1)) |
| #define DF_QUAD_DEC_BND (1<<(DF_QUAD_STEPS*2 + FWD_PREC + 2)) |
| |
| /* Multiplyers for the coefficients of the polynomial form of the cubic and |
| * quad curves representation |
| */ |
| #define CUB_A_SHIFT FWD_PREC |
| #define CUB_B_SHIFT (DF_CUB_STEPS + FWD_PREC + 1) |
| #define CUB_C_SHIFT (DF_CUB_STEPS*2 + FWD_PREC) |
| |
| #define CUB_A_MDP_MULT (1<<CUB_A_SHIFT) |
| #define CUB_B_MDP_MULT (1<<CUB_B_SHIFT) |
| #define CUB_C_MDP_MULT (1<<CUB_C_SHIFT) |
| |
| #define QUAD_A_SHIFT FWD_PREC |
| #define QUAD_B_SHIFT (DF_QUAD_STEPS + FWD_PREC) |
| |
| #define QUAD_A_MDP_MULT (1<<QUAD_A_SHIFT) |
| #define QUAD_B_MDP_MULT (1<<QUAD_B_SHIFT) |
| |
| #define CALC_MAX(MAX, X) ((MAX)=((X)>(MAX))?(X):(MAX)) |
| #define CALC_MIN(MIN, X) ((MIN)=((X)<(MIN))?(X):(MIN)) |
| #define MAX(MAX, X) (((X)>(MAX))?(X):(MAX)) |
| #define MIN(MIN, X) (((X)<(MIN))?(X):(MIN)) |
| #define ABS32(X) (((X)^((X)>>31))-((X)>>31)) |
| #define SIGN32(X) ((X) >> 31) | ((juint)(-(X)) >> 31) |
| |
| /* Boundaries used for clipping large path segments (those are inside |
| * [UPPER/LOWER]_BND boundaries) |
| */ |
| #define UPPER_OUT_BND (1 << (30 - MDP_PREC)) |
| #define LOWER_OUT_BND (-UPPER_OUT_BND) |
| |
| #define ADJUST(X, LBND, UBND) \ |
| do { \ |
| if ((X) < (LBND)) { \ |
| (X) = (LBND); \ |
| } else if ((X) > UBND) { \ |
| (X) = (UBND); \ |
| } \ |
| } while(0) |
| |
| /* Following constants are used for providing open boundaries of the intervals |
| */ |
| #define EPSFX 1 |
| #define EPSF (((jfloat)EPSFX)/MDP_MULT) |
| |
| /* Calculation boundary. It is used for switching to the more slow but allowing |
| * larger input values method of calculation of the initial values of the scan |
| * converted line segments inside the FillPolygon. |
| */ |
| #define CALC_BND (1 << (30 - MDP_PREC)) |
| |
| /* Clipping macros for drawing and filling algorithms */ |
| |
| #define CLIP(a1, b1, a2, b2, t) \ |
| (b1 + ((jdouble)(t - a1)*(b2 - b1)) / (a2 - a1)) |
| |
| enum { |
| CRES_MIN_CLIPPED, |
| CRES_MAX_CLIPPED, |
| CRES_NOT_CLIPPED, |
| CRES_INVISIBLE |
| }; |
| |
| #define IS_CLIPPED(res) (res == CRES_MIN_CLIPPED || res == CRES_MAX_CLIPPED) |
| |
| #define TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res) \ |
| do { \ |
| jdouble t; \ |
| res = CRES_NOT_CLIPPED; \ |
| if (a1 < (LINE_MIN) || a1 > (LINE_MAX)) { \ |
| if (a1 < (LINE_MIN)) { \ |
| if (a2 < (LINE_MIN)) { \ |
| res = CRES_INVISIBLE; \ |
| break; \ |
| }; \ |
| res = CRES_MIN_CLIPPED; \ |
| t = (LINE_MIN); \ |
| } else { \ |
| if (a2 > (LINE_MAX)) { \ |
| res = CRES_INVISIBLE; \ |
| break; \ |
| }; \ |
| res = CRES_MAX_CLIPPED; \ |
| t = (LINE_MAX); \ |
| } \ |
| b1 = (TYPE)CLIP(a1, b1, a2, b2, t); \ |
| a1 = (TYPE)t; \ |
| } \ |
| } while (0) |
| |
| /* Following macro is used for clipping and clumping filled shapes. |
| * An example of this process is shown on the picture below: |
| * ----+ ----+ |
| * |/ | |/ | |
| * + | + | |
| * /| | I | |
| * / | | I | |
| * | | | ===> I | |
| * \ | | I | |
| * \| | I | |
| * + | + | |
| * |\ | |\ | |
| * | ----+ | ----+ |
| * boundary boundary |
| * |
| * We can only perform clipping in case of right side of the output area |
| * because all segments passed out the right boundary don't influence on the |
| * result of scan conversion algorithm (it correctly handles half open |
| * contours). |
| * |
| */ |
| #define CLIPCLAMP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, a3, b3, TYPE, res) \ |
| do { \ |
| a3 = a1; \ |
| b3 = b1; \ |
| TESTANDCLIP(LINE_MIN, LINE_MAX, a1, b1, a2, b2, TYPE, res); \ |
| if (res == CRES_MIN_CLIPPED) { \ |
| a3 = a1; \ |
| } else if (res == CRES_MAX_CLIPPED) { \ |
| a3 = a1; \ |
| res = CRES_MAX_CLIPPED; \ |
| } else if (res == CRES_INVISIBLE) { \ |
| if (a1 > LINE_MAX) { \ |
| res = CRES_INVISIBLE; \ |
| } else { \ |
| a1 = (TYPE)LINE_MIN; \ |
| a2 = (TYPE)LINE_MIN; \ |
| res = CRES_NOT_CLIPPED; \ |
| } \ |
| } \ |
| } while (0) |
| |
| /* Following macro is used for solving quadratic equations: |
| * A*t^2 + B*t + C = 0 |
| * in (0,1) range. That means we put to the RES the only roots which |
| * belongs to the (0,1) range. Note: 0 and 1 are not included. |
| * See solveQuadratic method in |
| * src/share/classes/java/awt/geom/QuadCurve2D.java |
| * for more info about calculations |
| */ |
| #define SOLVEQUADINRANGE(A,B,C,RES,RCNT) \ |
| do { \ |
| double param; \ |
| if ((A) != 0) { \ |
| /* Calculating roots of the following equation \ |
| * A*t^2 + B*t + C = 0 \ |
| */ \ |
| double d = (B)*(B) - 4*(A)*(C); \ |
| double q; \ |
| if (d < 0) { \ |
| break; \ |
| } \ |
| d = sqrt(d); \ |
| /* For accuracy, calculate one root using: \ |
| * (-B +/- d) / 2*A \ |
| * and the other using: \ |
| * 2*C / (-B +/- d) \ |
| * Choose the sign of the +/- so that B+D gets larger \ |
| * in magnitude \ |
| */ \ |
| if ((B) < 0) { \ |
| d = -d; \ |
| } \ |
| q = ((B) + d) / -2.0; \ |
| param = q/(A); \ |
| if (param < 1.0 && param > 0.0) { \ |
| (RES)[(RCNT)++] = param; \ |
| } \ |
| if (d == 0 || q == 0) { \ |
| break; \ |
| } \ |
| param = (C)/q; \ |
| if (param < 1.0 && param > 0.0) { \ |
| (RES)[(RCNT)++] = param; \ |
| } \ |
| } else { \ |
| /* Calculating root of the following equation \ |
| * B*t + C = 0 \ |
| */ \ |
| if ((B) == 0) { \ |
| break; \ |
| } \ |
| param = -(C)/(B); \ |
| if (param < 1.0 && param > 0.0) { \ |
| (RES)[(RCNT)++] = param; \ |
| } \ |
| } \ |
| } while(0) |
| |
| /* Drawing line with subpixel endpoints |
| * |
| * (x1, y1), (x2, y2) - fixed point coordinates of the endpoints |
| * with MDP_PREC bits for the fractional part |
| * |
| * pixelInfo - structure which keeps drawing info for avoiding |
| * multiple drawing at the same position on the |
| * screen (required for the XOR mode of drawing) |
| * |
| * pixelInfo[0] - state of the drawing |
| * 0 - no pixel drawn between |
| * moveTo/close of the path |
| * 1 - there are drawn pixels |
| * |
| * pixelInfo[1,2] - first pixel of the path |
| * between moveTo/close of the |
| * path |
| * |
| * pixelInfo[3,4] - last drawn pixel between |
| * moveTo/close of the path |
| * |
| * checkBounds - flag showing necessity of checking the clip |
| * |
| */ |
| void ProcessFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2, |
| jint* pixelInfo,jboolean checkBounds, |
| jboolean endSubPath) |
| { |
| /* Checking if line is inside a (X,Y),(X+MDP_MULT,Y+MDP_MULT) box */ |
| jint c = ((x1 ^ x2) | (y1 ^ y2)); |
| jint rx1, ry1, rx2, ry2; |
| if ((c & MDP_W_MASK) == 0) { |
| /* Checking for the segments with integer coordinates having |
| * the same start and end points |
| */ |
| if (c == 0) { |
| PROCESS_POINT(hnd, x1 + MDP_HALF_MULT, y1 + MDP_HALF_MULT, |
| checkBounds, pixelInfo); |
| } |
| return; |
| } |
| |
| if (x1 == x2 || y1 == y2) { |
| rx1 = x1 + MDP_HALF_MULT; |
| rx2 = x2 + MDP_HALF_MULT; |
| ry1 = y1 + MDP_HALF_MULT; |
| ry2 = y2 + MDP_HALF_MULT; |
| } else { |
| /* Neither dx nor dy can be zero because of the check above */ |
| jint dx = x2 - x1; |
| jint dy = y2 - y1; |
| |
| /* Floor of x1, y1, x2, y2 */ |
| jint fx1 = x1 & MDP_W_MASK; |
| jint fy1 = y1 & MDP_W_MASK; |
| jint fx2 = x2 & MDP_W_MASK; |
| jint fy2 = y2 & MDP_W_MASK; |
| |
| /* Processing first endpoint */ |
| if (fx1 == x1 || fy1 == y1) { |
| /* Adding MDP_HALF_MULT to the [xy]1 if f[xy]1 == [xy]1 will not |
| * affect the result |
| */ |
| rx1 = x1 + MDP_HALF_MULT; |
| ry1 = y1 + MDP_HALF_MULT; |
| } else { |
| /* Boundary at the direction from (x1,y1) to (x2,y2) */ |
| jint bx1 = (x1 < x2) ? fx1 + MDP_MULT : fx1; |
| jint by1 = (y1 < y2) ? fy1 + MDP_MULT : fy1; |
| |
| /* intersection with column bx1 */ |
| jint cross = y1 + ((bx1 - x1)*dy)/dx; |
| if (cross >= fy1 && cross <= fy1 + MDP_MULT) { |
| rx1 = bx1; |
| ry1 = cross + MDP_HALF_MULT; |
| } else { |
| /* intersection with row by1 */ |
| cross = x1 + ((by1 - y1)*dx)/dy; |
| rx1 = cross + MDP_HALF_MULT; |
| ry1 = by1; |
| } |
| } |
| |
| /* Processing second endpoint */ |
| if (fx2 == x2 || fy2 == y2) { |
| /* Adding MDP_HALF_MULT to the [xy]2 if f[xy]2 == [xy]2 will not |
| * affect the result |
| */ |
| rx2 = x2 + MDP_HALF_MULT; |
| ry2 = y2 + MDP_HALF_MULT; |
| } else { |
| /* Boundary at the direction from (x2,y2) to (x1,y1) */ |
| jint bx2 = (x1 > x2) ? fx2 + MDP_MULT : fx2; |
| jint by2 = (y1 > y2) ? fy2 + MDP_MULT : fy2; |
| |
| /* intersection with column bx2 */ |
| jint cross = y2 + ((bx2 - x2)*dy)/dx; |
| if (cross >= fy2 && cross <= fy2 + MDP_MULT) { |
| rx2 = bx2; |
| ry2 = cross + MDP_HALF_MULT; |
| } else { |
| /* intersection with row by2 */ |
| cross = x2 + ((by2 - y2)*dx)/dy; |
| rx2 = cross + MDP_HALF_MULT; |
| ry2 = by2; |
| } |
| } |
| } |
| |
| PROCESS_LINE(hnd, rx1, ry1, rx2, ry2, checkBounds, pixelInfo); |
| } |
| |
| /* Performing drawing of the monotonic in X and Y quadratic curves with sizes |
| * less than MAX_QUAD_SIZE by using forward differencing method of calculation. |
| * See comments to the DrawMonotonicCubic. |
| */ |
| static void DrawMonotonicQuad(ProcessHandler* hnd, |
| jfloat *coords, |
| jboolean checkBounds, |
| jint* pixelInfo) |
| { |
| jint x0 = (jint)(coords[0]*MDP_MULT); |
| jint y0 = (jint)(coords[1]*MDP_MULT); |
| |
| jint xe = (jint)(coords[4]*MDP_MULT); |
| jint ye = (jint)(coords[5]*MDP_MULT); |
| |
| /* Extracting fractional part of coordinates of first control point */ |
| jint px = (x0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT; |
| jint py = (y0 & (~MDP_W_MASK)) << DF_QUAD_SHIFT; |
| |
| /* Setting default amount of steps */ |
| jint count = DF_QUAD_COUNT; |
| |
| /* Setting default shift for preparing to the midpoint rounding */ |
| jint shift = DF_QUAD_SHIFT; |
| |
| jint ax = (jint)((coords[0] - 2*coords[2] + |
| coords[4])*QUAD_A_MDP_MULT); |
| jint ay = (jint)((coords[1] - 2*coords[3] + |
| coords[5])*QUAD_A_MDP_MULT); |
| |
| jint bx = (jint)((-2*coords[0] + 2*coords[2])*QUAD_B_MDP_MULT); |
| jint by = (jint)((-2*coords[1] + 2*coords[3])*QUAD_B_MDP_MULT); |
| |
| jint ddpx = 2*ax; |
| jint ddpy = 2*ay; |
| |
| jint dpx = ax + bx; |
| jint dpy = ay + by; |
| |
| jint x1, y1; |
| |
| jint x2 = x0; |
| jint y2 = y0; |
| |
| jint maxDD = MAX(ABS32(ddpx),ABS32(ddpy)); |
| jint x0w = x0 & MDP_W_MASK; |
| jint y0w = y0 & MDP_W_MASK; |
| |
| jint dx = xe - x0; |
| jint dy = ye - y0; |
| |
| /* Perform decreasing step in 2 times if slope of the second forward |
| * difference changes too quickly (more than a pixel per step in X or Y |
| * direction). We can perform adjusting of the step size before the |
| * rendering loop because the curvature of the quad curve remains the same |
| * along all the curve |
| */ |
| while (maxDD > DF_QUAD_DEC_BND) { |
| dpx = (dpx<<1) - ax; |
| dpy = (dpy<<1) - ay; |
| count <<= 1; |
| maxDD >>= 2; |
| px <<=2; |
| py <<=2; |
| shift += 2; |
| } |
| |
| while(count-- > 1) { |
| |
| px += dpx; |
| py += dpy; |
| |
| dpx += ddpx; |
| dpy += ddpy; |
| |
| x1 = x2; |
| y1 = y2; |
| |
| x2 = x0w + (px >> shift); |
| y2 = y0w + (py >> shift); |
| |
| /* Checking that we are not running out of the endpoint and bounding |
| * violating coordinate. The check is pretty simple because the curve |
| * passed to the DrawMonotonicQuad already split into the monotonic |
| * in X and Y pieces |
| */ |
| |
| /* Bounding x2 by xe */ |
| if (((xe-x2)^dx) < 0) { |
| x2 = xe; |
| } |
| |
| /* Bounding y2 by ye */ |
| if (((ye-y2)^dy) < 0) { |
| y2 = ye; |
| } |
| |
| hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds, |
| JNI_FALSE); |
| } |
| |
| /* We are performing one step less than necessary and use actual (xe,ye) |
| * curve's endpoint instead of calculated. This prevent us from accumulated |
| * errors at the last point. |
| */ |
| |
| hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds, |
| JNI_FALSE); |
| } |
| |
| /* |
| * Checking size of the quad curves and split them if necessary. |
| * Calling DrawMonotonicQuad for the curves of the appropriate size. |
| * Note: coords array could be changed |
| */ |
| static void ProcessMonotonicQuad(ProcessHandler* hnd, |
| jfloat *coords, |
| jint* pixelInfo) { |
| |
| jfloat coords1[6]; |
| jfloat xMin, xMax; |
| jfloat yMin, yMax; |
| |
| xMin = xMax = coords[0]; |
| yMin = yMax = coords[1]; |
| |
| CALC_MIN(xMin, coords[2]); |
| CALC_MAX(xMax, coords[2]); |
| CALC_MIN(yMin, coords[3]); |
| CALC_MAX(yMax, coords[3]); |
| CALC_MIN(xMin, coords[4]); |
| CALC_MAX(xMax, coords[4]); |
| CALC_MIN(yMin, coords[5]); |
| CALC_MAX(yMax, coords[5]); |
| |
| |
| if (hnd->clipMode == PH_MODE_DRAW_CLIP) { |
| |
| /* In case of drawing we could just skip curves which are completely |
| * out of bounds |
| */ |
| if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax || |
| hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) { |
| return; |
| } |
| } else { |
| |
| /* In case of filling we could skip curves which are above, |
| * below and behind the right boundary of the visible area |
| */ |
| |
| if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax || |
| hnd->dhnd->xMaxf < xMin) |
| { |
| return; |
| } |
| |
| /* We could clamp x coordinates to the corresponding boundary |
| * if the curve is completely behind the left one |
| */ |
| |
| if (hnd->dhnd->xMinf > xMax) { |
| coords[0] = coords[2] = coords[4] = hnd->dhnd->xMinf; |
| } |
| } |
| |
| if (xMax - xMin > MAX_QUAD_SIZE || yMax - yMin > MAX_QUAD_SIZE) { |
| coords1[4] = coords[4]; |
| coords1[5] = coords[5]; |
| coords1[2] = (coords[2] + coords[4])/2.0f; |
| coords1[3] = (coords[3] + coords[5])/2.0f; |
| coords[2] = (coords[0] + coords[2])/2.0f; |
| coords[3] = (coords[1] + coords[3])/2.0f; |
| coords[4] = coords1[0] = (coords[2] + coords1[2])/2.0f; |
| coords[5] = coords1[1] = (coords[3] + coords1[3])/2.0f; |
| |
| ProcessMonotonicQuad(hnd, coords, pixelInfo); |
| |
| ProcessMonotonicQuad(hnd, coords1, pixelInfo); |
| } else { |
| DrawMonotonicQuad(hnd, coords, |
| /* Set checkBounds parameter if curve intersects |
| * boundary of the visible area. We know that the |
| * curve is visible, so the check is pretty simple |
| */ |
| hnd->dhnd->xMinf >= xMin || hnd->dhnd->xMaxf <= xMax || |
| hnd->dhnd->yMinf >= yMin || hnd->dhnd->yMaxf <= yMax, |
| pixelInfo); |
| } |
| } |
| |
| /* |
| * Bite the piece of the quadratic curve from start point till the point |
| * corresponding to the specified parameter then call ProcessQuad for the |
| * bitten part. |
| * Note: coords array will be changed |
| */ |
| static void ProcessFirstMonotonicPartOfQuad(ProcessHandler* hnd, jfloat* coords, |
| jint* pixelInfo, jfloat t) |
| { |
| jfloat coords1[6]; |
| |
| coords1[0] = coords[0]; |
| coords1[1] = coords[1]; |
| coords1[2] = coords[0] + t*(coords[2] - coords[0]); |
| coords1[3] = coords[1] + t*(coords[3] - coords[1]); |
| coords[2] = coords[2] + t*(coords[4] - coords[2]); |
| coords[3] = coords[3] + t*(coords[5] - coords[3]); |
| coords[0] = coords1[4] = coords1[2] + t*(coords[2] - coords1[2]); |
| coords[1] = coords1[5] = coords1[3] + t*(coords[3] - coords1[3]); |
| |
| ProcessMonotonicQuad(hnd, coords1, pixelInfo); |
| } |
| |
| /* |
| * Split quadratic curve into monotonic in X and Y parts. Calling |
| * ProcessMonotonicQuad for each monotonic piece of the curve. |
| * Note: coords array could be changed |
| */ |
| static void ProcessQuad(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) { |
| |
| /* Temporary array for holding parameters corresponding to the extreme in X |
| * and Y points. The values are inside the (0,1) range (0 and 1 excluded) |
| * and in ascending order. |
| */ |
| double params[2]; |
| |
| jint cnt = 0; |
| double param; |
| |
| /* Simple check for monotonicity in X before searching for the extreme |
| * points of the X(t) function. We first check if the curve is monotonic |
| * in X by seeing if all of the X coordinates are strongly ordered. |
| */ |
| if ((coords[0] > coords[2] || coords[2] > coords[4]) && |
| (coords[0] < coords[2] || coords[2] < coords[4])) |
| { |
| /* Searching for extreme points of the X(t) function by solving |
| * dX(t) |
| * ---- = 0 equation |
| * dt |
| */ |
| double ax = coords[0] - 2*coords[2] + coords[4]; |
| if (ax != 0) { |
| /* Calculating root of the following equation |
| * ax*t + bx = 0 |
| */ |
| double bx = coords[0] - coords[2]; |
| |
| param = bx/ax; |
| if (param < 1.0 && param > 0.0) { |
| params[cnt++] = param; |
| } |
| } |
| } |
| |
| /* Simple check for monotonicity in Y before searching for the extreme |
| * points of the Y(t) function. We first check if the curve is monotonic |
| * in Y by seeing if all of the Y coordinates are strongly ordered. |
| */ |
| if ((coords[1] > coords[3] || coords[3] > coords[5]) && |
| (coords[1] < coords[3] || coords[3] < coords[5])) |
| { |
| /* Searching for extreme points of the Y(t) function by solving |
| * dY(t) |
| * ----- = 0 equation |
| * dt |
| */ |
| double ay = coords[1] - 2*coords[3] + coords[5]; |
| |
| if (ay != 0) { |
| /* Calculating root of the following equation |
| * ay*t + by = 0 |
| */ |
| double by = coords[1] - coords[3]; |
| |
| param = by/ay; |
| if (param < 1.0 && param > 0.0) { |
| if (cnt > 0) { |
| /* Inserting parameter only if it differs from |
| * already stored |
| */ |
| if (params[0] > param) { |
| params[cnt++] = params[0]; |
| params[0] = param; |
| } else if (params[0] < param) { |
| params[cnt++] = param; |
| } |
| } else { |
| params[cnt++] = param; |
| } |
| } |
| } |
| } |
| |
| /* Processing obtained monotonic parts */ |
| switch(cnt) { |
| case 0: |
| break; |
| case 1: |
| ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, |
| (jfloat)params[0]); |
| break; |
| case 2: |
| ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, |
| (jfloat)params[0]); |
| param = params[1] - params[0]; |
| if (param > 0) { |
| ProcessFirstMonotonicPartOfQuad(hnd, coords, pixelInfo, |
| /* Scale parameter to match with rest of the curve */ |
| (jfloat)(param/(1.0 - params[0]))); |
| } |
| break; |
| } |
| |
| ProcessMonotonicQuad(hnd,coords,pixelInfo); |
| } |
| |
| /* |
| * Performing drawing of the monotonic in X and Y cubic curves with sizes less |
| * than MAX_CUB_SIZE by using forward differencing method of calculation. |
| * |
| * Here is some math used in the code below. |
| * |
| * If we express the parametric equation for the coordinates as |
| * simple polynomial: |
| * |
| * V(t) = a * t^3 + b * t^2 + c * t + d |
| * |
| * The equations for how we derive these polynomial coefficients |
| * from the Bezier control points can be found in the method comments |
| * for the CubicCurve.fillEqn Java method. |
| * |
| * From this polynomial, we can derive the forward differences to |
| * allow us to calculate V(t+K) from V(t) as follows: |
| * |
| * 1) V1(0) |
| * = V(K)-V(0) |
| * = aK^3 + bK^2 + cK + d - d |
| * = aK^3 + bK^2 + cK |
| * |
| * 2) V1(K) |
| * = V(2K)-V(K) |
| * = 8aK^3 + 4bK^2 + 2cK + d - aK^3 - bK^2 - cK - d |
| * = 7aK^3 + 3bK^2 + cK |
| * |
| * 3) V1(2K) |
| * = V(3K)-V(2K) |
| * = 27aK^3 + 9bK^2 + 3cK + d - 8aK^3 - 4bK^2 - 2cK - d |
| * = 19aK^3 + 5bK^2 + cK |
| * |
| * 4) V2(0) |
| * = V1(K) - V1(0) |
| * = 7aK^3 + 3bK^2 + cK - aK^3 - bK^2 - cK |
| * = 6aK^3 + 2bK^2 |
| * |
| * 5) V2(K) |
| * = V1(2K) - V1(K) |
| * = 19aK^3 + 5bK^2 + cK - 7aK^3 - 3bK^2 - cK |
| * = 12aK^3 + 2bK^2 |
| * |
| * 6) V3(0) |
| * = V2(K) - V2(0) |
| * = 12aK^3 + 2bK^2 - 6aK^3 - 2bK^2 |
| * = 6aK^3 |
| * |
| * Note that if we continue on to calculate V1(3K), V2(2K) and |
| * V3(K) we will see that V3(K) == V3(0) so we need at most |
| * 3 cascading forward differences to step through the cubic |
| * curve. |
| * |
| * Note, b coefficient calculating in the DrawCubic is actually twice the b |
| * coefficient seen above. It's been done for the better accuracy. |
| * |
| * In our case, initialy K is chosen as 1/(2^DF_CUB_STEPS) this value is taken |
| * with FWD_PREC bits precision. This means that we should do 2^DF_CUB_STEPS |
| * steps to pass through all the curve. |
| * |
| * On each step we examine how far we are stepping by examining our first(V1) |
| * and second (V2) order derivatives and verifying that they are met following |
| * conditions: |
| * |
| * abs(V2) <= DF_CUB_DEC_BND |
| * abs(V1) > DF_CUB_INC_BND |
| * |
| * So, ensures that we step through the curve more slowly when its curvature is |
| * high and faster when its curvature is lower. If the step size needs |
| * adjustment we adjust it so that we step either twice as fast, or twice as |
| * slow until our step size is within range. This modifies our stepping |
| * variables as follows: |
| * |
| * Decreasing step size |
| * (See Graphics Gems/by A.Glassner,(Tutorial on forward differencing),601-602) |
| * |
| * V3 = oV3/8 |
| * V2 = oV2/4 - V3 |
| * V1 = (oV1 - V2)/2 |
| * |
| * Here V1-V3 stands for new values of the forward differencies and oV1 - oV3 |
| * for the old ones |
| * |
| * Using the equations above it's easy to calculating stepping variables for |
| * the increasing step size: |
| * |
| * V1 = 2*oV1 + oV2 |
| * V2 = 4*oV2 + 4*oV3 |
| * V3 = 8*oV3 |
| * |
| * And then for not to running out of 32 bit precision we are performing 3 bit |
| * shift of the forward differencing precision (keeping in shift variable) in |
| * left or right direction depending on what is happening (decreasing or |
| * increasing). So, all oV1 - oV3 variables should be thought as appropriately |
| * shifted in regard to the V1 - V3. |
| * |
| * Taking all of the above into account we will have following: |
| * |
| * Decreasing step size: |
| * |
| * shift = shift + 3 |
| * V3 keeps the same |
| * V2 = 2*oV2 - V3 |
| * V1 = 4*oV1 - V2/2 |
| * |
| * Increasing step size: |
| * |
| * shift = shift - 3 |
| * V1 = oV1/4 + oV2/8 |
| * V2 = oV2/2 + oV3/2 |
| * V3 keeps the same |
| * |
| */ |
| |
| static void DrawMonotonicCubic(ProcessHandler* hnd, |
| jfloat *coords, |
| jboolean checkBounds, |
| jint* pixelInfo) |
| { |
| jint x0 = (jint)(coords[0]*MDP_MULT); |
| jint y0 = (jint)(coords[1]*MDP_MULT); |
| |
| jint xe = (jint)(coords[6]*MDP_MULT); |
| jint ye = (jint)(coords[7]*MDP_MULT); |
| |
| /* Extracting fractional part of coordinates of first control point */ |
| jint px = (x0 & (~MDP_W_MASK)) << DF_CUB_SHIFT; |
| jint py = (y0 & (~MDP_W_MASK)) << DF_CUB_SHIFT; |
| |
| /* Setting default boundary values for checking first and second forward |
| * difference for the necessity of the restepping. See comments to the |
| * boundary values in ProcessQuad for more info. |
| */ |
| jint incStepBnd1 = DF_CUB_INC_BND; |
| jint incStepBnd2 = DF_CUB_INC_BND << 1; |
| jint decStepBnd1 = DF_CUB_DEC_BND; |
| jint decStepBnd2 = DF_CUB_DEC_BND << 1; |
| |
| /* Setting default amount of steps */ |
| jint count = DF_CUB_COUNT; |
| |
| /* Setting default shift for preparing to the midpoint rounding */ |
| jint shift = DF_CUB_SHIFT; |
| |
| jint ax = (jint)((-coords[0] + 3*coords[2] - 3*coords[4] + |
| coords[6])*CUB_A_MDP_MULT); |
| jint ay = (jint)((-coords[1] + 3*coords[3] - 3*coords[5] + |
| coords[7])*CUB_A_MDP_MULT); |
| |
| jint bx = (jint)((3*coords[0] - 6*coords[2] + |
| 3*coords[4])*CUB_B_MDP_MULT); |
| jint by = (jint)((3*coords[1] - 6*coords[3] + |
| 3*coords[5])*CUB_B_MDP_MULT); |
| |
| jint cx = (jint)((-3*coords[0] + 3*coords[2])*(CUB_C_MDP_MULT)); |
| jint cy = (jint)((-3*coords[1] + 3*coords[3])*(CUB_C_MDP_MULT)); |
| |
| jint dddpx = 6*ax; |
| jint dddpy = 6*ay; |
| |
| jint ddpx = dddpx + bx; |
| jint ddpy = dddpy + by; |
| |
| jint dpx = ax + (bx>>1) + cx; |
| jint dpy = ay + (by>>1) + cy; |
| |
| jint x1, y1; |
| |
| jint x2 = x0; |
| jint y2 = y0; |
| |
| /* Calculating whole part of the first point of the curve */ |
| jint x0w = x0 & MDP_W_MASK; |
| jint y0w = y0 & MDP_W_MASK; |
| |
| jint dx = xe - x0; |
| jint dy = ye - y0; |
| |
| while (count > 0) { |
| /* Perform decreasing step in 2 times if necessary */ |
| while ( |
| /* The code below is an optimized version of the checks: |
| * abs(ddpx) > decStepBnd1 || |
| * abs(ddpy) > decStepBnd1 |
| */ |
| (juint)(ddpx + decStepBnd1) > (juint)decStepBnd2 || |
| (juint)(ddpy + decStepBnd1) > (juint)decStepBnd2) |
| { |
| ddpx = (ddpx<<1) - dddpx; |
| ddpy = (ddpy<<1) - dddpy; |
| dpx = (dpx<<2) - (ddpx>>1); |
| dpy = (dpy<<2) - (ddpy>>1); |
| count <<=1; |
| decStepBnd1 <<=3; |
| decStepBnd2 <<=3; |
| incStepBnd1 <<=3; |
| incStepBnd2 <<=3; |
| px <<=3; |
| py <<=3; |
| shift += 3; |
| } |
| |
| /* Perform increasing step in 2 times if necessary. |
| * Note: we could do it only in even steps |
| */ |
| |
| while (((count & 1) ^ 1) && shift > DF_CUB_SHIFT && |
| /* The code below is an optimized version of the check: |
| * abs(dpx) <= incStepBnd1 && |
| * abs(dpy) <= incStepBnd1 |
| */ |
| (juint)(dpx + incStepBnd1) <= (juint)incStepBnd2 && |
| (juint)(dpy + incStepBnd1) <= (juint)incStepBnd2) |
| { |
| dpx = (dpx>>2) + (ddpx>>3); |
| dpy = (dpy>>2) + (ddpy>>3); |
| ddpx = (ddpx + dddpx)>>1; |
| ddpy = (ddpy + dddpy)>>1; |
| count >>=1; |
| decStepBnd1 >>=3; |
| decStepBnd2 >>=3; |
| incStepBnd1 >>=3; |
| incStepBnd2 >>=3; |
| px >>=3; |
| py >>=3; |
| shift -= 3; |
| } |
| |
| count--; |
| |
| /* We are performing one step less than necessary and use actual |
| * (xe,ye) endpoint of the curve instead of calculated. This prevent |
| * us from accumulated errors at the last point. |
| */ |
| if (count) { |
| |
| px += dpx; |
| py += dpy; |
| |
| dpx += ddpx; |
| dpy += ddpy; |
| ddpx += dddpx; |
| ddpy += dddpy; |
| |
| x1 = x2; |
| y1 = y2; |
| |
| x2 = x0w + (px >> shift); |
| y2 = y0w + (py >> shift); |
| |
| /* Checking that we are not running out of the endpoint and |
| * bounding violating coordinate. The check is pretty simple |
| * because the curve passed to the DrawMonotonicCubic already |
| * split into the monotonic in X and Y pieces |
| */ |
| |
| /* Bounding x2 by xe */ |
| if (((xe-x2)^dx) < 0) { |
| x2 = xe; |
| } |
| |
| /* Bounding y2 by ye */ |
| if (((ye-y2)^dy) < 0) { |
| y2 = ye; |
| } |
| |
| hnd->pProcessFixedLine(hnd, x1, y1, x2, y2, pixelInfo, checkBounds, |
| JNI_FALSE); |
| } else { |
| hnd->pProcessFixedLine(hnd, x2, y2, xe, ye, pixelInfo, checkBounds, |
| JNI_FALSE); |
| } |
| } |
| } |
| |
| /* |
| * Checking size of the cubic curves and split them if necessary. |
| * Calling DrawMonotonicCubic for the curves of the appropriate size. |
| * Note: coords array could be changed |
| */ |
| static void ProcessMonotonicCubic(ProcessHandler* hnd, |
| jfloat *coords, |
| jint* pixelInfo) { |
| |
| jfloat coords1[8]; |
| jfloat tx, ty; |
| jfloat xMin, xMax; |
| jfloat yMin, yMax; |
| |
| xMin = xMax = coords[0]; |
| yMin = yMax = coords[1]; |
| |
| CALC_MIN(xMin, coords[2]); |
| CALC_MAX(xMax, coords[2]); |
| CALC_MIN(yMin, coords[3]); |
| CALC_MAX(yMax, coords[3]); |
| CALC_MIN(xMin, coords[4]); |
| CALC_MAX(xMax, coords[4]); |
| CALC_MIN(yMin, coords[5]); |
| CALC_MAX(yMax, coords[5]); |
| CALC_MIN(xMin, coords[6]); |
| CALC_MAX(xMax, coords[6]); |
| CALC_MIN(yMin, coords[7]); |
| CALC_MAX(yMax, coords[7]); |
| |
| if (hnd->clipMode == PH_MODE_DRAW_CLIP) { |
| |
| /* In case of drawing we could just skip curves which are completely |
| * out of bounds |
| */ |
| if (hnd->dhnd->xMaxf < xMin || hnd->dhnd->xMinf > xMax || |
| hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax) { |
| return; |
| } |
| } else { |
| |
| /* In case of filling we could skip curves which are above, |
| * below and behind the right boundary of the visible area |
| */ |
| |
| if (hnd->dhnd->yMaxf < yMin || hnd->dhnd->yMinf > yMax || |
| hnd->dhnd->xMaxf < xMin) |
| { |
| return; |
| } |
| |
| /* We could clamp x coordinates to the corresponding boundary |
| * if the curve is completely behind the left one |
| */ |
| |
| if (hnd->dhnd->xMinf > xMax) { |
| coords[0] = coords[2] = coords[4] = coords[6] = |
| hnd->dhnd->xMinf; |
| } |
| } |
| |
| if (xMax - xMin > MAX_CUB_SIZE || yMax - yMin > MAX_CUB_SIZE) { |
| coords1[6] = coords[6]; |
| coords1[7] = coords[7]; |
| coords1[4] = (coords[4] + coords[6])/2.0f; |
| coords1[5] = (coords[5] + coords[7])/2.0f; |
| tx = (coords[2] + coords[4])/2.0f; |
| ty = (coords[3] + coords[5])/2.0f; |
| coords1[2] = (tx + coords1[4])/2.0f; |
| coords1[3] = (ty + coords1[5])/2.0f; |
| coords[2] = (coords[0] + coords[2])/2.0f; |
| coords[3] = (coords[1] + coords[3])/2.0f; |
| coords[4] = (coords[2] + tx)/2.0f; |
| coords[5] = (coords[3] + ty)/2.0f; |
| coords[6]=coords1[0]=(coords[4] + coords1[2])/2.0f; |
| coords[7]=coords1[1]=(coords[5] + coords1[3])/2.0f; |
| |
| ProcessMonotonicCubic(hnd, coords, pixelInfo); |
| |
| ProcessMonotonicCubic(hnd, coords1, pixelInfo); |
| |
| } else { |
| DrawMonotonicCubic(hnd, coords, |
| /* Set checkBounds parameter if curve intersects |
| * boundary of the visible area. We know that the |
| * curve is visible, so the check is pretty simple |
| */ |
| hnd->dhnd->xMinf > xMin || hnd->dhnd->xMaxf < xMax || |
| hnd->dhnd->yMinf > yMin || hnd->dhnd->yMaxf < yMax, |
| pixelInfo); |
| } |
| } |
| |
| /* |
| * Bite the piece of the cubic curve from start point till the point |
| * corresponding to the specified parameter then call ProcessMonotonicCubic for |
| * the bitten part. |
| * Note: coords array will be changed |
| */ |
| static void ProcessFirstMonotonicPartOfCubic(ProcessHandler* hnd, |
| jfloat* coords, jint* pixelInfo, |
| jfloat t) |
| { |
| jfloat coords1[8]; |
| jfloat tx, ty; |
| |
| coords1[0] = coords[0]; |
| coords1[1] = coords[1]; |
| tx = coords[2] + t*(coords[4] - coords[2]); |
| ty = coords[3] + t*(coords[5] - coords[3]); |
| coords1[2] = coords[0] + t*(coords[2] - coords[0]); |
| coords1[3] = coords[1] + t*(coords[3] - coords[1]); |
| coords1[4] = coords1[2] + t*(tx - coords1[2]); |
| coords1[5] = coords1[3] + t*(ty - coords1[3]); |
| coords[4] = coords[4] + t*(coords[6] - coords[4]); |
| coords[5] = coords[5] + t*(coords[7] - coords[5]); |
| coords[2] = tx + t*(coords[4] - tx); |
| coords[3] = ty + t*(coords[5] - ty); |
| coords[0]=coords1[6]=coords1[4] + t*(coords[2] - coords1[4]); |
| coords[1]=coords1[7]=coords1[5] + t*(coords[3] - coords1[5]); |
| |
| ProcessMonotonicCubic(hnd, coords1, pixelInfo); |
| } |
| |
| /* |
| * Split cubic curve into monotonic in X and Y parts. Calling ProcessCubic for |
| * each monotonic piece of the curve. |
| * |
| * Note: coords array could be changed |
| */ |
| static void ProcessCubic(ProcessHandler* hnd, jfloat* coords, jint* pixelInfo) |
| { |
| /* Temporary array for holding parameters corresponding to the extreme in X |
| * and Y points. The values are inside the (0,1) range (0 and 1 excluded) |
| * and in ascending order. |
| */ |
| double params[4]; |
| jint cnt = 0, i; |
| |
| /* Simple check for monotonicity in X before searching for the extreme |
| * points of the X(t) function. We first check if the curve is monotonic in |
| * X by seeing if all of the X coordinates are strongly ordered. |
| */ |
| if ((coords[0] > coords[2] || coords[2] > coords[4] || |
| coords[4] > coords[6]) && |
| (coords[0] < coords[2] || coords[2] < coords[4] || |
| coords[4] < coords[6])) |
| { |
| /* Searching for extreme points of the X(t) function by solving |
| * dX(t) |
| * ---- = 0 equation |
| * dt |
| */ |
| double ax = -coords[0] + 3*coords[2] - 3*coords[4] + coords[6]; |
| double bx = 2*(coords[0] - 2*coords[2] + coords[4]); |
| double cx = -coords[0] + coords[2]; |
| |
| SOLVEQUADINRANGE(ax,bx,cx,params,cnt); |
| } |
| |
| /* Simple check for monotonicity in Y before searching for the extreme |
| * points of the Y(t) function. We first check if the curve is monotonic in |
| * Y by seeing if all of the Y coordinates are strongly ordered. |
| */ |
| if ((coords[1] > coords[3] || coords[3] > coords[5] || |
| coords[5] > coords[7]) && |
| (coords[1] < coords[3] || coords[3] < coords[5] || |
| coords[5] < coords[7])) |
| { |
| /* Searching for extreme points of the Y(t) function by solving |
| * dY(t) |
| * ----- = 0 equation |
| * dt |
| */ |
| double ay = -coords[1] + 3*coords[3] - 3*coords[5] + coords[7]; |
| double by = 2*(coords[1] - 2*coords[3] + coords[5]); |
| double cy = -coords[1] + coords[3]; |
| |
| SOLVEQUADINRANGE(ay,by,cy,params,cnt); |
| } |
| |
| if (cnt > 0) { |
| /* Sorting parameter values corresponding to the extremum points of |
| * the curve. We are using insertion sort because of tiny size of the |
| * array. |
| */ |
| jint j; |
| |
| for(i = 1; i < cnt; i++) { |
| double value = params[i]; |
| for (j = i - 1; j >= 0 && params[j] > value; j--) { |
| params[j + 1] = params[j]; |
| } |
| params[j + 1] = value; |
| } |
| |
| /* Processing obtained monotonic parts */ |
| ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo, |
| (jfloat)params[0]); |
| for (i = 1; i < cnt; i++) { |
| double param = params[i] - params[i-1]; |
| if (param > 0) { |
| ProcessFirstMonotonicPartOfCubic(hnd, coords, pixelInfo, |
| /* Scale parameter to match with rest of the curve */ |
| (float)(param/(1.0 - params[i - 1]))); |
| } |
| } |
| } |
| |
| ProcessMonotonicCubic(hnd,coords,pixelInfo); |
| } |
| |
| static void ProcessLine(ProcessHandler* hnd, |
| jfloat *coord1, jfloat *coord2, jint* pixelInfo) { |
| |
| jfloat xMin, yMin, xMax, yMax; |
| jint X1, Y1, X2, Y2, X3, Y3, res; |
| jboolean clipped = JNI_FALSE; |
| jfloat x1 = coord1[0]; |
| jfloat y1 = coord1[1]; |
| jfloat x2 = coord2[0]; |
| jfloat y2 = coord2[1]; |
| jfloat x3,y3; |
| |
| jboolean lastClipped; |
| |
| xMin = hnd->dhnd->xMinf; |
| yMin = hnd->dhnd->yMinf; |
| xMax = hnd->dhnd->xMaxf; |
| yMax = hnd->dhnd->yMaxf; |
| |
| TESTANDCLIP(yMin, yMax, y1, x1, y2, x2, jfloat, res); |
| if (res == CRES_INVISIBLE) return; |
| clipped = IS_CLIPPED(res); |
| TESTANDCLIP(yMin, yMax, y2, x2, y1, x1, jfloat, res); |
| if (res == CRES_INVISIBLE) return; |
| lastClipped = IS_CLIPPED(res); |
| clipped = clipped || lastClipped; |
| |
| if (hnd->clipMode == PH_MODE_DRAW_CLIP) { |
| TESTANDCLIP(xMin, xMax, |
| x1, y1, x2, y2, jfloat, res); |
| if (res == CRES_INVISIBLE) return; |
| clipped = clipped || IS_CLIPPED(res); |
| TESTANDCLIP(xMin, xMax, |
| x2, y2, x1, y1, jfloat, res); |
| if (res == CRES_INVISIBLE) return; |
| lastClipped = lastClipped || IS_CLIPPED(res); |
| clipped = clipped || lastClipped; |
| X1 = (jint)(x1*MDP_MULT); |
| Y1 = (jint)(y1*MDP_MULT); |
| X2 = (jint)(x2*MDP_MULT); |
| Y2 = (jint)(y2*MDP_MULT); |
| |
| hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo, |
| clipped, /* enable boundary checking in case |
| of clipping to avoid entering |
| out of bounds which could |
| happens during rounding |
| */ |
| lastClipped /* Notify pProcessFixedLine that |
| this is the end of the |
| subpath (because of exiting |
| out of boundaries) |
| */ |
| ); |
| } else { |
| /* Clamping starting from first vertex of the processed segment |
| */ |
| CLIPCLAMP(xMin, xMax, x1, y1, x2, y2, x3, y3, jfloat, res); |
| X1 = (jint)(x1*MDP_MULT); |
| Y1 = (jint)(y1*MDP_MULT); |
| |
| /* Clamping only by left boundary */ |
| if (res == CRES_MIN_CLIPPED) { |
| X3 = (jint)(x3*MDP_MULT); |
| Y3 = (jint)(y3*MDP_MULT); |
| hnd->pProcessFixedLine(hnd, X3, Y3, X1, Y1, pixelInfo, |
| JNI_FALSE, lastClipped); |
| |
| } else if (res == CRES_INVISIBLE) { |
| return; |
| } |
| |
| /* Clamping starting from last vertex of the processed segment |
| */ |
| CLIPCLAMP(xMin, xMax, x2, y2, x1, y1, x3, y3, jfloat, res); |
| |
| /* Checking if there was a clip by right boundary */ |
| lastClipped = lastClipped || (res == CRES_MAX_CLIPPED); |
| |
| X2 = (jint)(x2*MDP_MULT); |
| Y2 = (jint)(y2*MDP_MULT); |
| hnd->pProcessFixedLine(hnd, X1, Y1, X2, Y2, pixelInfo, |
| JNI_FALSE, lastClipped); |
| |
| /* Clamping only by left boundary */ |
| if (res == CRES_MIN_CLIPPED) { |
| X3 = (jint)(x3*MDP_MULT); |
| Y3 = (jint)(y3*MDP_MULT); |
| hnd->pProcessFixedLine(hnd, X2, Y2, X3, Y3, pixelInfo, |
| JNI_FALSE, lastClipped); |
| } |
| } |
| } |
| |
| jboolean ProcessPath(ProcessHandler* hnd, |
| jfloat transXf, jfloat transYf, |
| jfloat* coords, jint maxCoords, |
| jbyte* types, jint numTypes) |
| { |
| jfloat tCoords[8]; |
| jfloat closeCoord[2]; |
| jint pixelInfo[5]; |
| jboolean skip = JNI_FALSE; |
| jboolean subpathStarted = JNI_FALSE; |
| jfloat lastX, lastY; |
| int i, index = 0; |
| |
| pixelInfo[0] = 0; |
| |
| /* Adding support of the KEY_STROKE_CONTROL rendering hint. |
| * Now we are supporting two modes: "pixels at centers" and |
| * "pixels at corners". |
| * First one is disabled by default but could be enabled by setting |
| * VALUE_STROKE_PURE to the rendering hint. It means that pixel at the |
| * screen (x,y) has (x + 0.5, y + 0.5) float coordinates. |
| * |
| * Second one is enabled by default and means straightforward mapping |
| * (x,y) --> (x,y) |
| * |
| */ |
| if (hnd->stroke == PH_STROKE_PURE) { |
| closeCoord[0] = -0.5f; |
| closeCoord[1] = -0.5f; |
| transXf -= 0.5; |
| transYf -= 0.5; |
| } else { |
| closeCoord[0] = 0.0f; |
| closeCoord[1] = 0.0f; |
| } |
| |
| /* Adjusting boundaries to the capabilities of the ProcessPath code */ |
| ADJUST(hnd->dhnd->xMin, LOWER_OUT_BND, UPPER_OUT_BND); |
| ADJUST(hnd->dhnd->yMin, LOWER_OUT_BND, UPPER_OUT_BND); |
| ADJUST(hnd->dhnd->xMax, LOWER_OUT_BND, UPPER_OUT_BND); |
| ADJUST(hnd->dhnd->yMax, LOWER_OUT_BND, UPPER_OUT_BND); |
| |
| |
| /* Setting up fractional clipping box |
| * |
| * We are using following float -> int mapping: |
| * |
| * xi = floor(xf + 0.5) |
| * |
| * So, fractional values that hit the [xmin, xmax) integer interval will be |
| * situated inside the [xmin-0.5, xmax - 0.5) fractional interval. We are |
| * using EPSF constant to provide that upper boundary is not included. |
| */ |
| hnd->dhnd->xMinf = hnd->dhnd->xMin - 0.5f; |
| hnd->dhnd->yMinf = hnd->dhnd->yMin - 0.5f; |
| hnd->dhnd->xMaxf = hnd->dhnd->xMax - 0.5f - EPSF; |
| hnd->dhnd->yMaxf = hnd->dhnd->yMax - 0.5f - EPSF; |
| |
| |
| for (i = 0; i < numTypes; i++) { |
| switch (types[i]) { |
| case java_awt_geom_PathIterator_SEG_MOVETO: |
| if (index + 2 <= maxCoords) { |
| /* Performing closing of the unclosed segments */ |
| if (subpathStarted & !skip) { |
| if (hnd->clipMode == PH_MODE_FILL_CLIP) { |
| if (tCoords[0] != closeCoord[0] || |
| tCoords[1] != closeCoord[1]) |
| { |
| ProcessLine(hnd, tCoords, closeCoord, |
| pixelInfo); |
| } |
| } |
| hnd->pProcessEndSubPath(hnd); |
| } |
| |
| tCoords[0] = coords[index++] + transXf; |
| tCoords[1] = coords[index++] + transYf; |
| |
| /* Checking SEG_MOVETO coordinates if they are out of the |
| * [LOWER_BND, UPPER_BND] range. This check also handles |
| * NaN and Infinity values. Skipping next path segment in |
| * case of invalid data. |
| */ |
| |
| if (tCoords[0] < UPPER_BND && |
| tCoords[0] > LOWER_BND && |
| tCoords[1] < UPPER_BND && |
| tCoords[1] > LOWER_BND) |
| { |
| subpathStarted = JNI_TRUE; |
| skip = JNI_FALSE; |
| closeCoord[0] = tCoords[0]; |
| closeCoord[1] = tCoords[1]; |
| } else { |
| skip = JNI_TRUE; |
| } |
| } else { |
| return JNI_FALSE; |
| } |
| break; |
| case java_awt_geom_PathIterator_SEG_LINETO: |
| if (index + 2 <= maxCoords) { |
| lastX = tCoords[2] = coords[index++] + transXf; |
| lastY = tCoords[3] = coords[index++] + transYf; |
| |
| /* Checking SEG_LINETO coordinates if they are out of the |
| * [LOWER_BND, UPPER_BND] range. This check also handles |
| * NaN and Infinity values. Ignoring current path segment |
| * in case of invalid data. If segment is skipped its |
| * endpoint (if valid) is used to begin new subpath. |
| */ |
| |
| if (lastX < UPPER_BND && |
| lastX > LOWER_BND && |
| lastY < UPPER_BND && |
| lastY > LOWER_BND) |
| { |
| if (skip) { |
| tCoords[0] = closeCoord[0] = lastX; |
| tCoords[1] = closeCoord[1] = lastY; |
| subpathStarted = JNI_TRUE; |
| skip = JNI_FALSE; |
| } else { |
| ProcessLine(hnd, tCoords, tCoords + 2, |
| pixelInfo); |
| tCoords[0] = lastX; |
| tCoords[1] = lastY; |
| } |
| } |
| } else { |
| return JNI_FALSE; |
| } |
| break; |
| case java_awt_geom_PathIterator_SEG_QUADTO: |
| if (index + 4 <= maxCoords) { |
| tCoords[2] = coords[index++] + transXf; |
| tCoords[3] = coords[index++] + transYf; |
| lastX = tCoords[4] = coords[index++] + transXf; |
| lastY = tCoords[5] = coords[index++] + transYf; |
| |
| /* Checking SEG_QUADTO coordinates if they are out of the |
| * [LOWER_BND, UPPER_BND] range. This check also handles |
| * NaN and Infinity values. Ignoring current path segment |
| * in case of invalid endpoints's data. Equivalent to |
| * the SEG_LINETO if endpoint coordinates are valid but |
| * there are invalid data among other coordinates |
| */ |
| |
| if (lastX < UPPER_BND && |
| lastX > LOWER_BND && |
| lastY < UPPER_BND && |
| lastY > LOWER_BND) |
| { |
| if (skip) { |
| tCoords[0] = closeCoord[0] = lastX; |
| tCoords[1] = closeCoord[1] = lastY; |
| subpathStarted = JNI_TRUE; |
| skip = JNI_FALSE; |
| } else { |
| if (tCoords[2] < UPPER_BND && |
| tCoords[2] > LOWER_BND && |
| tCoords[3] < UPPER_BND && |
| tCoords[3] > LOWER_BND) |
| { |
| ProcessQuad(hnd, tCoords, pixelInfo); |
| } else { |
| ProcessLine(hnd, tCoords, |
| tCoords + 4, pixelInfo); |
| } |
| tCoords[0] = lastX; |
| tCoords[1] = lastY; |
| } |
| } |
| } else { |
| return JNI_FALSE; |
| } |
| break; |
| case java_awt_geom_PathIterator_SEG_CUBICTO: |
| if (index + 6 <= maxCoords) { |
| tCoords[2] = coords[index++] + transXf; |
| tCoords[3] = coords[index++] + transYf; |
| tCoords[4] = coords[index++] + transXf; |
| tCoords[5] = coords[index++] + transYf; |
| lastX = tCoords[6] = coords[index++] + transXf; |
| lastY = tCoords[7] = coords[index++] + transYf; |
| |
| /* Checking SEG_CUBICTO coordinates if they are out of the |
| * [LOWER_BND, UPPER_BND] range. This check also handles |
| * NaN and Infinity values. Ignoring current path segment |
| * in case of invalid endpoints's data. Equivalent to |
| * the SEG_LINETO if endpoint coordinates are valid but |
| * there are invalid data among other coordinates |
| */ |
| |
| if (lastX < UPPER_BND && |
| lastX > LOWER_BND && |
| lastY < UPPER_BND && |
| lastY > LOWER_BND) |
| { |
| if (skip) { |
| tCoords[0] = closeCoord[0] = tCoords[6]; |
| tCoords[1] = closeCoord[1] = tCoords[7]; |
| subpathStarted = JNI_TRUE; |
| skip = JNI_FALSE; |
| } else { |
| if (tCoords[2] < UPPER_BND && |
| tCoords[2] > LOWER_BND && |
| tCoords[3] < UPPER_BND && |
| tCoords[3] > LOWER_BND && |
| tCoords[4] < UPPER_BND && |
| tCoords[4] > LOWER_BND && |
| tCoords[5] < UPPER_BND && |
| tCoords[5] > LOWER_BND) |
| { |
| ProcessCubic(hnd, tCoords, pixelInfo); |
| } else { |
| ProcessLine(hnd, tCoords, tCoords + 6, |
| pixelInfo); |
| } |
| tCoords[0] = lastX; |
| tCoords[1] = lastY; |
| } |
| } |
| } else { |
| return JNI_FALSE; |
| } |
| break; |
| case java_awt_geom_PathIterator_SEG_CLOSE: |
| if (subpathStarted && !skip) { |
| skip = JNI_FALSE; |
| if (tCoords[0] != closeCoord[0] || |
| tCoords[1] != closeCoord[1]) |
| { |
| ProcessLine(hnd, tCoords, closeCoord, pixelInfo); |
| /* Storing last path's point for using in |
| * following segments without initial moveTo |
| */ |
| tCoords[0] = closeCoord[0]; |
| tCoords[1] = closeCoord[1]; |
| } |
| |
| hnd->pProcessEndSubPath(hnd); |
| } |
| |
| break; |
| } |
| } |
| |
| /* Performing closing of the unclosed segments */ |
| if (subpathStarted & !skip) { |
| if (hnd->clipMode == PH_MODE_FILL_CLIP) { |
| if (tCoords[0] != closeCoord[0] || |
| tCoords[1] != closeCoord[1]) |
| { |
| ProcessLine(hnd, tCoords, closeCoord, |
| pixelInfo); |
| } |
| } |
| hnd->pProcessEndSubPath(hnd); |
| } |
| |
| return JNI_TRUE; |
| } |
| |
| /* TODO Add checking of the result of the malloc/realloc functions to handle |
| * out of memory error and don't leak earlier allocated data |
| */ |
| |
| |
| #define ALLOC(ptr, type, n) \ |
| ptr = (type *)malloc((n)*sizeof(type)) |
| #define REALLOC(ptr, type, n) \ |
| ptr = (type *)realloc(ptr, (n)*sizeof(type)) |
| |
| |
| struct _Edge; |
| |
| typedef struct _Point { |
| jint x; |
| jint y; |
| jboolean lastPoint; |
| struct _Point* prev; |
| struct _Point* next; |
| struct _Point* nextByY; |
| jboolean endSL; |
| struct _Edge* edge; |
| } Point; |
| |
| |
| typedef struct _Edge { |
| jint x; |
| jint dx; |
| Point* p; |
| jint dir; |
| struct _Edge* prev; |
| struct _Edge* next; |
| } Edge; |
| |
| /* Size of the default buffer in the FillData structure. This buffer is |
| * replaced with heap allocated in case of large paths. |
| */ |
| #define DF_MAX_POINT 256 |
| |
| /* Following structure accumulates points of the non-continuous flattened |
| * path during iteration through the origin path's segments . The end |
| * of the each subpath is marked as lastPoint flag set at the last point |
| */ |
| |
| typedef struct { |
| Point *plgPnts; |
| Point dfPlgPnts[DF_MAX_POINT]; |
| jint plgSize; |
| jint plgMax; |
| jint plgYMin; |
| jint plgYMax; |
| } FillData; |
| |
| #define FD_INIT(PTR) \ |
| do { \ |
| (PTR)->plgPnts = (PTR)->dfPlgPnts; \ |
| (PTR)->plgSize = 0; \ |
| (PTR)->plgMax = DF_MAX_POINT; \ |
| } while(0) |
| |
| #define FD_ADD_POINT(PTR, X, Y, LASTPT) \ |
| do { \ |
| Point* _pnts = (PTR)->plgPnts; \ |
| jint _size = (PTR)->plgSize; \ |
| if (_size >= (PTR)->plgMax) { \ |
| jint newMax = (PTR)->plgMax*2; \ |
| if ((PTR)->plgPnts == (PTR)->dfPlgPnts) { \ |
| (PTR)->plgPnts = (Point*)malloc(newMax*sizeof(Point)); \ |
| memcpy((PTR)->plgPnts, _pnts, _size*sizeof(Point)); \ |
| } else { \ |
| (PTR)->plgPnts = (Point*)realloc( \ |
| _pnts, newMax*sizeof(Point)); \ |
| } \ |
| _pnts = (PTR)->plgPnts; \ |
| (PTR)->plgMax = newMax; \ |
| } \ |
| _pnts += _size; \ |
| _pnts->x = X; \ |
| _pnts->y = Y; \ |
| _pnts->lastPoint = LASTPT; \ |
| if (_size) { \ |
| if ((PTR)->plgYMin > Y) (PTR)->plgYMin = Y; \ |
| if ((PTR)->plgYMax < Y) (PTR)->plgYMax = Y; \ |
| } else { \ |
| (PTR)->plgYMin = Y; \ |
| (PTR)->plgYMax = Y; \ |
| } \ |
| (PTR)->plgSize = _size + 1; \ |
| } while(0) |
| |
| |
| #define FD_FREE_POINTS(PTR) \ |
| do { \ |
| if ((PTR)->plgPnts != (PTR)->dfPlgPnts) { \ |
| free((PTR)->plgPnts); \ |
| } \ |
| } while(0) |
| |
| #define FD_IS_EMPTY(PTR) (!((PTR)->plgSize)) |
| |
| #define FD_IS_ENDED(PTR) ((PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint) |
| |
| #define FD_SET_ENDED(PTR) \ |
| do { \ |
| (PTR)->plgPnts[(PTR)->plgSize - 1].lastPoint = JNI_TRUE; \ |
| } while(0) |
| |
| #define PFD(HND) ((FillData*)(HND)->pData) |
| |
| /* Bubble sorting in the ascending order of the linked list. This |
| * implementation stops processing the list if there were no changes during the |
| * previous pass. |
| * |
| * LIST - ptr to the ptr to the first element of the list |
| * ETYPE - type of the element in the list |
| * NEXT - accessor to the next field in the list element |
| * GET_LKEY - accessor to the key of the list element |
| */ |
| #define LBUBBLE_SORT(LIST, ETYPE, NEXT, GET_LKEY) \ |
| do { \ |
| ETYPE *p, *q, *r, *s = NULL, *temp ; \ |
| jint wasSwap = 1; \ |
| /* r precedes p and s points to the node up to which comparisons \ |
| * are to be made */ \ |
| while ( s != NEXT(*LIST) && wasSwap) { \ |
| r = p = *LIST; \ |
| q = NEXT(p); \ |
| wasSwap = 0; \ |
| while ( p != s ) { \ |
| if (GET_LKEY(p) >= GET_LKEY(q)) { \ |
| wasSwap = 1; \ |
| if ( p == *LIST ) { \ |
| temp = NEXT(q); \ |
| NEXT(q) = p ; \ |
| NEXT(p) = temp ; \ |
| *LIST = q ; \ |
| r = q ; \ |
| } else { \ |
| temp = NEXT(q); \ |
| NEXT(q) = p ; \ |
| NEXT(p) = temp ; \ |
| NEXT(r) = q ; \ |
| r = q ; \ |
| } \ |
| } else { \ |
| r = p ; \ |
| p = NEXT(p); \ |
| } \ |
| q = NEXT(p); \ |
| if ( q == s ) s = p ; \ |
| } \ |
| } \ |
| } while(0); |
| |
| /* Accessors for the Edge structure to work with LBUBBLE_SORT */ |
| #define GET_ACTIVE_KEY(a) (a->x) |
| #define GET_ACTIVE_NEXT(a) ((a)->next) |
| |
| /* TODO: Implement stack/heap allocation technique for active edges |
| */ |
| #define DELETE_ACTIVE(head,pnt) \ |
| do { \ |
| Edge *prevp = pnt->prev; \ |
| Edge *nextp = pnt->next; \ |
| if (prevp) { \ |
| prevp->next = nextp; \ |
| } else { \ |
| head = nextp; \ |
| } \ |
| if (nextp) { \ |
| nextp->prev = prevp; \ |
| } \ |
| } while(0); |
| |
| #define INSERT_ACTIVE(head,pnt,cy) \ |
| do { \ |
| Point *np = pnt->next; \ |
| Edge *ne = active + nact; \ |
| if (pnt->y == np->y) { \ |
| /* Skipping horizontal segments */ \ |
| break; \ |
| } else { \ |
| jint dX = np->x - pnt->x; \ |
| jint dY = np->y - pnt->y; \ |
| jint dy; \ |
| if (pnt->y < np->y) { \ |
| ne->dir = -1; \ |
| ne->p = pnt; \ |
| ne->x = pnt->x; \ |
| dy = cy - pnt->y; \ |
| } else { /* pnt->y > np->y */ \ |
| ne->dir = 1; \ |
| ne->p = np; \ |
| ne->x = np->x; \ |
| dy = cy - np->y; \ |
| } \ |
| \ |
| /* We need to worry only about dX because dY is in */\ |
| /* denominator and abs(dy) < MDP_MULT (cy is a first */\ |
| /* scanline of the scan converted segment and we subtract */\ |
| /* y coordinate of the nearest segment's end from it to */\ |
| /* obtain dy) */\ |
| if (ABS32(dX) > CALC_BND) { \ |
| ne->dx = (jint)((((jdouble)dX)*MDP_MULT)/dY); \ |
| ne->x += (jint)((((jdouble)dX)*dy)/dY); \ |
| } else { \ |
| ne->dx = ((dX)<<MDP_PREC)/dY; \ |
| ne->x += (dX*dy)/dY; \ |
| } \ |
| } \ |
| ne->next = head; \ |
| ne->prev = NULL; \ |
| if (head) { \ |
| head->prev = ne; \ |
| } \ |
| head = active + nact; \ |
| pnt->edge = head; \ |
| nact++; \ |
| } while(0); |
| |
| void FillPolygon(ProcessHandler* hnd, |
| jint fillRule) { |
| jint k, y, xl, xr; |
| jint drawing; |
| Edge* activeList, *active; |
| Edge* curEdge, *prevEdge; |
| jint nact; |
| jint n; |
| Point* pt, *curpt, *ept; |
| Point** yHash; |
| Point** curHash; |
| jint rightBnd = hnd->dhnd->xMax - 1; |
| FillData* pfd = (FillData*)(hnd->pData); |
| jint yMin = pfd->plgYMin; |
| jint yMax = pfd->plgYMax; |
| jint hashSize = ((yMax - yMin)>>MDP_PREC) + 4; |
| |
| /* Because of support of the KEY_STROKE_CONTROL hint we are performing |
| * shift of the coordinates at the higher level |
| */ |
| jint hashOffset = ((yMin - 1) & MDP_W_MASK); |
| |
| // TODO creating lists using fake first element to avoid special casing of |
| // the first element in the list (which otherwise should be performed in each |
| // list operation) |
| |
| /* Winding counter */ |
| jint counter; |
| |
| /* Calculating mask to be applied to the winding counter */ |
| jint counterMask = |
| (fillRule == java_awt_geom_PathIterator_WIND_NON_ZERO)? -1:1; |
| pt = pfd->plgPnts; |
| n = pfd->plgSize; |
| |
| if (n <=1) return; |
| |
| ALLOC(yHash, Point*, hashSize); |
| for (k = 0; k < hashSize; k++) { |
| yHash[k] = NULL; |
| } |
| |
| ALLOC(active, Edge, n); |
| |
| /* Creating double linked list (prev, next links) describing path order and |
| * hash table with points which fall between scanlines. nextByY link is |
| * used for the points which are between same scanlines. Scanlines are |
| * passed through the centers of the pixels. |
| */ |
| curpt = pt; |
| curpt->prev = NULL; |
| ept = pt + n - 1; |
| for (curpt = pt; curpt != ept; curpt++) { |
| Point* nextpt = curpt + 1; |
| curHash = yHash + ((curpt->y - hashOffset - 1) >> MDP_PREC); |
| curpt->nextByY = *curHash; |
| *curHash = curpt; |
| curpt->next = nextpt; |
| nextpt->prev = curpt; |
| curpt->edge = NULL; |
| } |
| |
| curHash = yHash + ((ept->y - hashOffset - 1) >> MDP_PREC); |
| ept->nextByY = *curHash; |
| *curHash = ept; |
| ept->next = NULL; |
| ept->edge = NULL; |
| nact = 0; |
| |
| activeList = NULL; |
| for (y=hashOffset + MDP_MULT,k = 0; |
| y<=yMax && k < hashSize; y += MDP_MULT, k++) |
| { |
| for(pt = yHash[k];pt; pt=pt->nextByY) { |
| /* pt->y should be inside hashed interval |
| * assert(y-MDP_MULT <= pt->y && pt->y < y); |
| */ |
| if (pt->prev && !pt->prev->lastPoint) { |
| if (pt->prev->edge && pt->prev->y <= y) { |
| DELETE_ACTIVE(activeList, pt->prev->edge); |
| pt->prev->edge = NULL; |
| } else if (pt->prev->y > y) { |
| INSERT_ACTIVE(activeList, pt->prev, y); |
| } |
| } |
| |
| if (!pt->lastPoint && pt->next) { |
| if (pt->edge && pt->next->y <= y) { |
| DELETE_ACTIVE(activeList, pt->edge); |
| pt->edge = NULL; |
| } else if (pt->next->y > y) { |
| INSERT_ACTIVE(activeList, pt, y); |
| } |
| } |
| } |
| |
| if (!activeList) continue; |
| |
| /* We could not use O(N) Radix sort here because in most cases list of |
| * edges almost sorted. So, bubble sort (O(N^2))is working much |
| * better. Note, in case of array of edges Shell sort is more |
| * efficient. |
| */ |
| LBUBBLE_SORT((&activeList), Edge, GET_ACTIVE_NEXT, GET_ACTIVE_KEY); |
| |
| /* Correction of the back links in the double linked edge list */ |
| curEdge=activeList; |
| prevEdge = NULL; |
| while (curEdge) { |
| curEdge->prev = prevEdge; |
| prevEdge = curEdge; |
| curEdge = curEdge->next; |
| } |
| |
| xl = xr = hnd->dhnd->xMin; |
| curEdge = activeList; |
| counter = 0; |
| drawing = 0; |
| for(;curEdge; curEdge = curEdge->next) { |
| counter += curEdge->dir; |
| if ((counter & counterMask) && !drawing) { |
| xl = (curEdge->x + MDP_MULT - 1)>>MDP_PREC; |
| drawing = 1; |
| } |
| |
| if (!(counter & counterMask) && drawing) { |
| xr = (curEdge->x - 1)>>MDP_PREC; |
| if (xl <= xr) { |
| hnd->dhnd->pDrawScanline(hnd->dhnd, xl, xr, y >> MDP_PREC); |
| } |
| drawing = 0; |
| } |
| |
| curEdge->x += curEdge->dx; |
| } |
| |
| /* Performing drawing till the right boundary (for correct rendering |
| * shapes clipped at the right side) |
| */ |
| if (drawing && xl <= rightBnd) { |
| hnd->dhnd->pDrawScanline(hnd->dhnd, xl, rightBnd, y >> MDP_PREC); |
| } |
| } |
| free(active); |
| free(yHash); |
| } |
| |
| |
| |
| void StoreFixedLine(ProcessHandler* hnd,jint x1,jint y1,jint x2,jint y2, |
| jint* pixelInfo,jboolean checkBounds, |
| jboolean endSubPath) { |
| FillData* pfd; |
| jint outXMin, outXMax, outYMin, outYMax; |
| jint x3, y3, res; |
| |
| /* There is no need to round line coordinates to the forward differencing |
| * precision anymore. Such a rounding was used for preventing the curve go |
| * out the endpoint (this sometimes does not help). The problem was fixed |
| * in the forward differencing loops. |
| */ |
| |
| if (checkBounds) { |
| jboolean lastClipped = JNI_FALSE; |
| |
| /* This function is used only for filling shapes, so there is no |
| * check for the type of clipping |
| */ |
| outXMin = (jint)(hnd->dhnd->xMinf * MDP_MULT); |
| outXMax = (jint)(hnd->dhnd->xMaxf * MDP_MULT); |
| outYMin = (jint)(hnd->dhnd->yMinf * MDP_MULT); |
| outYMax = (jint)(hnd->dhnd->yMaxf * MDP_MULT); |
| |
| TESTANDCLIP(outYMin, outYMax, y1, x1, y2, x2, jint, res); |
| if (res == CRES_INVISIBLE) return; |
| TESTANDCLIP(outYMin, outYMax, y2, x2, y1, x1, jint, res); |
| if (res == CRES_INVISIBLE) return; |
| lastClipped = IS_CLIPPED(res); |
| |
| /* Clamping starting from first vertex of the processed segment */ |
| CLIPCLAMP(outXMin, outXMax, x1, y1, x2, y2, x3, y3, jint, res); |
| |
| /* Clamping only by left boundary */ |
| if (res == CRES_MIN_CLIPPED) { |
| StoreFixedLine(hnd, x3, y3, x1, y1, pixelInfo, |
| JNI_FALSE, lastClipped); |
| |
| } else if (res == CRES_INVISIBLE) { |
| return; |
| } |
| |
| /* Clamping starting from last vertex of the processed segment */ |
| CLIPCLAMP(outXMin, outXMax, x2, y2, x1, y1, x3, y3, jint, res); |
| |
| /* Checking if there was a clip by right boundary */ |
| lastClipped = lastClipped || (res == CRES_MAX_CLIPPED); |
| |
| StoreFixedLine(hnd, x1, y1, x2, y2, pixelInfo, |
| JNI_FALSE, lastClipped); |
| |
| /* Clamping only by left boundary */ |
| if (res == CRES_MIN_CLIPPED) { |
| StoreFixedLine(hnd, x2, y2, x3, y3, pixelInfo, |
| JNI_FALSE, lastClipped); |
| } |
| |
| return; |
| } |
| pfd = (FillData*)(hnd->pData); |
| |
| /* Adding first point of the line only in case of empty or just finished |
| * path |
| */ |
| if (FD_IS_EMPTY(pfd) || FD_IS_ENDED(pfd)) { |
| FD_ADD_POINT(pfd, x1, y1, JNI_FALSE); |
| } |
| |
| FD_ADD_POINT(pfd, x2, y2, JNI_FALSE); |
| |
| if (endSubPath) { |
| FD_SET_ENDED(pfd); |
| } |
| } |
| |
| |
| static void endSubPath(ProcessHandler* hnd) { |
| FillData* pfd = (FillData*)(hnd->pData); |
| if (!FD_IS_EMPTY(pfd)) { |
| FD_SET_ENDED(pfd); |
| } |
| } |
| |
| static void stubEndSubPath(ProcessHandler* hnd) { |
| } |
| |
| jboolean doFillPath(DrawHandler* dhnd, |
| jint transX, jint transY, |
| jfloat* coords, jint maxCoords, |
| jbyte* types, jint numTypes, |
| PHStroke stroke, jint fillRule) |
| { |
| jint res; |
| |
| FillData fillData; |
| |
| ProcessHandler hnd = |
| { |
| &StoreFixedLine, |
| &endSubPath, |
| NULL, |
| PH_STROKE_DEFAULT, |
| PH_MODE_FILL_CLIP, |
| NULL |
| }; |
| |
| /* Initialization of the following fields in the declaration of the hnd |
| * above causes warnings on sun studio compiler with -xc99=%none option |
| * applied (this option means compliance with C90 standard instead of C99) |
| */ |
| hnd.dhnd = dhnd; |
| hnd.pData = &fillData; |
| hnd.stroke = stroke; |
| |
| FD_INIT(&fillData); |
| res = ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, |
| coords, maxCoords, types, numTypes); |
| if (!res) { |
| FD_FREE_POINTS(&fillData); |
| return JNI_FALSE; |
| } |
| FillPolygon(&hnd, fillRule); |
| FD_FREE_POINTS(&fillData); |
| return JNI_TRUE; |
| } |
| |
| jboolean doDrawPath(DrawHandler* dhnd, |
| void (*pProcessEndSubPath)(ProcessHandler*), |
| jint transX, jint transY, |
| jfloat* coords, jint maxCoords, |
| jbyte* types, jint numTypes, PHStroke stroke) |
| { |
| ProcessHandler hnd = |
| { |
| &ProcessFixedLine, |
| NULL, |
| NULL, |
| PH_STROKE_DEFAULT, |
| PH_MODE_DRAW_CLIP, |
| NULL |
| }; |
| |
| /* Initialization of the following fields in the declaration of the hnd |
| * above causes warnings on sun studio compiler with -xc99=%none option |
| * applied (this option means compliance with C90 standard instead of C99) |
| */ |
| hnd.dhnd = dhnd; |
| hnd.stroke = stroke; |
| |
| hnd.pProcessEndSubPath = (pProcessEndSubPath == NULL)? |
| stubEndSubPath : pProcessEndSubPath; |
| return ProcessPath(&hnd, (jfloat)transX, (jfloat)transY, coords, maxCoords, |
| types, numTypes); |
| } |