3909N/A * Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A * This framework performs filling and drawing of paths with sub-pixel 0N/A * precision. Also, it performs clipping by the specified view area. 0N/A * Drawing of the shapes is performed not pixel by pixel but segment by segment 0N/A * except several pixels near endpoints of the drawn line. This approach saves 0N/A * lot's of cpu cycles especially in case of large primitives (like ovals with 0N/A * sizes more than 50) and helps in achieving appropriate visual quality. Also, 0N/A * such method of drawing is useful for the accelerated pipelines where 0N/A * overhead of the per-pixel drawing could eliminate all benefits of the 0N/A * hardware acceleration. 0N/A * Filling of the path was taken from 0N/A * [Graphics Gems, edited by Andrew S Glassner. Academic Press 1990, 0N/A * ISBN 0-12-286165-5 (Concave polygon scan conversion), 87-91] 0N/A * and modified to work with sub-pixel precision and non-continuous paths. 0N/A * It's also speeded up by using hash table by rows of the filled objects. 0N/A * Here is high level scheme showing the rendering process: 0N/A * doDrawPath doFillPath 0N/A * DrawCurve ProcessLine 0N/A * (filling) / \ (drawing) 0N/A * Clipping and Clipping 0N/A * StoreFixedLine ProcessFixedLine 0N/A * FillPolygon PROCESS_LINE PROCESS_POINT 0N/A * CheckPathSegment - rough checking and skipping path's segments in case of 0N/A * invalid or huge coordinates of the control points to 0N/A * avoid calculation problems with NaNs and values close 0N/A * ProcessCurve - (ProcessQuad, ProcessCubic) Splitting the curve into 0N/A * monotonic parts having appropriate size (calculated as 0N/A * boundary box of the control points) 0N/A * DrawMonotonicCurve - (DrawMonotonicQuad, DrawMonotonicCubic) flattening 0N/A * monotonic curve using adaptive forward differencing 0N/A * StoreFixedLine - storing segment from the flattened path to the 0N/A * FillData structure. Performing clipping and clamping if 0N/A * PROCESS_LINE, PROCESS_POINT - Helpers for calling appropriate primitive from 0N/A * DrawHandler structure 0N/A * ProcessFixedLine - Drawing line segment with subpixel precision. 3717N/A /* Checking bounds and clipping if necessary. \ 3717N/A * REMIND: It's temporary solution to avoid OOB in rendering code. \ 3717N/A * Current approach uses float equations which are unreliable for \ 3717N/A * clipping and makes assumptions about the line biases of the \ 3717N/A * rendering algorithm. Also, clipping code should be moved down \ 3717N/A * into only those output renderers that need it. \ 2957N/A /* Handling lines having just one pixel */ \
0N/A /* Switch on last pixel of the line if it was already \ 0N/A * drawn during rendering of the previous segments \ 0N/A * (_X,_Y) should be inside boundaries \ 0N/A * assert(hnd->dhnd->yMin <= _Y && \ 0N/A * hnd->dhnd->yMax > _Y && \ 0N/A * hnd->dhnd->xMin <= _X && \ 0N/A * hnd->dhnd->xMax > _X); \ 0N/A * Constants for the forward differencing 0N/A * of the cubic and quad curves 0N/A/* Maximum size of the cubic curve (calculated as the size of the bounding box 0N/A * of the control points) which could be rendered without splitting 0N/A/* Maximum size of the quad curve (calculated as the size of the bounding box 0N/A * of the control points) which could be rendered without splitting 0N/A/* Default power of 2 steps used in the forward differencing. Here DF prefix 0N/A * stands for DeFault. Constants below are used as initial values for the 0N/A * adaptive forward differencing algorithm. 0N/A/* Shift of the current point of the curve for preparing to the midpoint 0N/A/* Default amount of steps of the forward differencing */ 0N/A/* Default boundary constants used to check the necessity of the restepping */ 0N/A/* Multiplyers for the coefficients of the polynomial form of the cubic and 0N/A * quad curves representation 0N/A#
define ABS32(X) (((X)^((X)>>
31))-((X)>>
31))
0N/A/* Boundaries used for clipping large path segments (those are inside 0N/A/* Following constants are used for providing open boundaries of the intervals 0N/A/* Calculation boundary. It is used for switching to the more slow but allowing 0N/A * larger input values method of calculation of the initial values of the scan 0N/A * converted line segments inside the FillPolygon. 0N/A/* Clipping macros for drawing and filling algorithms */ 0N/A/* Following macro is used for clipping and clumping filled shapes. 0N/A * An example of this process is shown on the picture below: 0N/A * We can only perform clipping in case of right side of the output area 0N/A * because all segments passed out the right boundary don't influence on the 0N/A * result of scan conversion algorithm (it correctly handles half open 0N/A/* Following macro is used for solving quadratic equations: 0N/A * A*t^2 + B*t + C = 0 0N/A * in (0,1) range. That means we put to the RES the only roots which 0N/A * belongs to the (0,1) range. Note: 0 and 1 are not included. 0N/A * See solveQuadratic method in 0N/A * for more info about calculations 0N/A /* Calculating roots of the following equation \ 0N/A * A*t^2 + B*t + C = 0 \ 0N/A double d = (B)*(B) -
4*(A)*(C); \
0N/A /* For accuracy, calculate one root using: \ 0N/A * (-B +/- d) / 2*A \ 0N/A * and the other using: \ 0N/A * 2*C / (-B +/- d) \ 0N/A * Choose the sign of the +/- so that B+D gets larger \ 0N/A q = ((B) + d) / -
2.0; \
0N/A if (d == 0 || q == 0) { \
0N/A /* Calculating root of the following equation \ 0N/A/* Drawing line with subpixel endpoints 0N/A * (x1, y1), (x2, y2) - fixed point coordinates of the endpoints 0N/A * with MDP_PREC bits for the fractional part 0N/A * pixelInfo - structure which keeps drawing info for avoiding 0N/A * multiple drawing at the same position on the 0N/A * screen (required for the XOR mode of drawing) 0N/A * pixelInfo[0] - state of the drawing 0N/A * 0 - no pixel drawn between 0N/A * 1 - there are drawn pixels 0N/A * pixelInfo[1,2] - first pixel of the path 0N/A * pixelInfo[3,4] - last drawn pixel between 0N/A * checkBounds - flag showing necessity of checking the clip 0N/A /* Checking if line is inside a (X,Y),(X+MDP_MULT,Y+MDP_MULT) box */ 0N/A /* Checking for the segments with integer coordinates having 0N/A * the same start and end points 0N/A /* Neither dx nor dy can be zero because of the check above */ 0N/A /* Floor of x1, y1, x2, y2 */ 0N/A /* Processing first endpoint */ 0N/A /* Adding MDP_HALF_MULT to the [xy]1 if f[xy]1 == [xy]1 will not 0N/A /* Boundary at the direction from (x1,y1) to (x2,y2) */ 0N/A /* intersection with column bx1 */ 0N/A /* intersection with row by1 */ 0N/A /* Processing second endpoint */ 0N/A /* Adding MDP_HALF_MULT to the [xy]2 if f[xy]2 == [xy]2 will not 0N/A /* Boundary at the direction from (x2,y2) to (x1,y1) */ 0N/A /* intersection with column bx2 */ 0N/A /* intersection with row by2 */ 0N/A/* Performing drawing of the monotonic in X and Y quadratic curves with sizes 0N/A * less than MAX_QUAD_SIZE by using forward differencing method of calculation. 0N/A * See comments to the DrawMonotonicCubic. 0N/A /* Extracting fractional part of coordinates of first control point */ 0N/A /* Setting default amount of steps */ 0N/A /* Setting default shift for preparing to the midpoint rounding */ 0N/A /* Perform decreasing step in 2 times if slope of the second forward 0N/A * difference changes too quickly (more than a pixel per step in X or Y 0N/A * direction). We can perform adjusting of the step size before the 0N/A * rendering loop because the curvature of the quad curve remains the same 0N/A * along all the curve 0N/A /* Checking that we are not running out of the endpoint and bounding 0N/A * violating coordinate. The check is pretty simple because the curve 0N/A * passed to the DrawMonotonicQuad already splitted into the monotonic 0N/A /* Bounding x2 by xe */ 0N/A /* Bounding y2 by ye */ 0N/A /* We are performing one step less than necessary and use actual (xe,ye) 0N/A * curve's endpoint instead of calculated. This prevent us from accumulated 0N/A * errors at the last point. 0N/A * Checking size of the quad curves and split them if necessary. 0N/A * Calling DrawMonotonicQuad for the curves of the appropriate size. 0N/A * Note: coords array could be changed 0N/A /* In case of drawing we could just skip curves which are completely 0N/A /* In case of filling we could skip curves which are above, 0N/A * below and behind the right boundary of the visible area 0N/A /* We could clamp x coordinates to the corresponding boundary 0N/A * if the curve is completely behind the left one 0N/A /* Set checkBounds parameter if curve intersects 0N/A * boundary of the visible area. We know that the 0N/A * curve is visible, so the check is pretty simple 0N/A * Bite the piece of the quadratic curve from start point till the point 0N/A * corresponding to the specified parameter then call ProcessQuad for the 0N/A * Note: coords array will be changed 0N/A * Split quadratic curve into monotonic in X and Y parts. Calling 0N/A * ProcessMonotonicQuad for each monotonic piece of the curve. 0N/A * Note: coords array could be changed 0N/A /* Temporary array for holding parameters corresponding to the extreme in X 0N/A * and Y points. The values are inside the (0,1) range (0 and 1 excluded) 0N/A * and in ascending order. 0N/A /* Simple check for monotonicity in X before searching for the extreme 0N/A * points of the X(t) function. We first check if the curve is monotonic 0N/A * in X by seeing if all of the X coordinates are strongly ordered. 0N/A /* Searching for extreme points of the X(t) function by solving 0N/A /* Calculating root of the following equation 0N/A /* Simple check for monotonicity in Y before searching for the extreme 0N/A * points of the Y(t) function. We first check if the curve is monotonic 0N/A * in Y by seeing if all of the Y coordinates are strongly ordered. 0N/A /* Searching for extreme points of the Y(t) function by solving 0N/A * ----- = 0 equation 0N/A /* Calculating root of the following equation 0N/A /* Inserting parameter only if it differs from 0N/A /* Processing obtained monotonic parts */ 0N/A /* Scale parameter to match with rest of the curve */ 0N/A * Performing drawing of the monotonic in X and Y cubic curves with sizes less 0N/A * than MAX_CUB_SIZE by using forward differencing method of calculation. 0N/A * Here is some math used in the code below. 0N/A * If we express the parametric equation for the coordinates as 0N/A * simple polynomial: 0N/A * V(t) = a * t^3 + b * t^2 + c * t + d 0N/A * The equations for how we derive these polynomial coefficients 0N/A * from the Bezier control points can be found in the method comments 0N/A * for the CubicCurve.fillEqn Java method. 0N/A * From this polynomial, we can derive the forward differences to 0N/A * allow us to calculate V(t+K) from V(t) as follows: 0N/A * = aK^3 + bK^2 + cK + d - d 0N/A * = aK^3 + bK^2 + cK 0N/A * = 8aK^3 + 4bK^2 + 2cK + d - aK^3 - bK^2 - cK - d 0N/A * = 7aK^3 + 3bK^2 + cK 0N/A * = 27aK^3 + 9bK^2 + 3cK + d - 8aK^3 - 4bK^2 - 2cK - d 0N/A * = 19aK^3 + 5bK^2 + cK 0N/A * = 7aK^3 + 3bK^2 + cK - aK^3 - bK^2 - cK 0N/A * = 19aK^3 + 5bK^2 + cK - 7aK^3 - 3bK^2 - cK 0N/A * = 12aK^3 + 2bK^2 - 6aK^3 - 2bK^2 0N/A * Note that if we continue on to calculate V1(3K), V2(2K) and 0N/A * V3(K) we will see that V3(K) == V3(0) so we need at most 0N/A * 3 cascading forward differences to step through the cubic 0N/A * Note, b coefficient calculating in the DrawCubic is actually twice the b 0N/A * coefficient seen above. It's been done for the better accuracy. 0N/A * In our case, initialy K is chosen as 1/(2^DF_CUB_STEPS) this value is taken 0N/A * with FWD_PREC bits precision. This means that we should do 2^DF_CUB_STEPS 0N/A * steps to pass through all the curve. 0N/A * On each step we examine how far we are stepping by examining our first(V1) 0N/A * and second (V2) order derivatives and verifying that they are met following 0N/A * abs(V2) <= DF_CUB_DEC_BND 0N/A * abs(V1) > DF_CUB_INC_BND 0N/A * So, ensures that we step through the curve more slowly when its curvature is 0N/A * high and faster when its curvature is lower. If the step size needs 0N/A * adjustment we adjust it so that we step either twice as fast, or twice as 0N/A * slow until our step size is within range. This modifies our stepping 0N/A * variables as follows: 0N/A * Decreasing step size 0N/A * (See Graphics Gems/by A.Glassner,(Tutorial on forward differencing),601-602) 0N/A * Here V1-V3 stands for new values of the forward differencies and oV1 - oV3 0N/A * Using the equations above it's easy to calculating stepping variables for 0N/A * the increasing step size: 0N/A * V2 = 4*oV2 + 4*oV3 0N/A * And then for not to running out of 32 bit precision we are performing 3 bit 0N/A * shift of the forward differencing precision (keeping in shift variable) in 0N/A * left or right direction depending on what is happening (decreasing or 0N/A * increasing). So, all oV1 - oV3 variables should be thought as appropriately 0N/A * shifted in regard to the V1 - V3. 0N/A * Taking all of the above into account we will have following: 0N/A * Decreasing step size: 0N/A * Increasing step size: 0N/A * V1 = oV1/4 + oV2/8 0N/A * V2 = oV2/2 + oV3/2 0N/A /* Extracting fractional part of coordinates of first control point */ 0N/A /* Setting default boundary values for checking first and second forward 0N/A * difference for the necessity of the restepping. See comments to the 0N/A * boundary values in ProcessQuad for more info. 0N/A /* Setting default amount of steps */ 0N/A /* Setting default shift for preparing to the midpoint rounding */ 0N/A /* Calculating whole part of the first point of the curve */ 0N/A /* Perform decreasing step in 2 times if necessary */ 0N/A /* The code below is an optimized version of the checks: 0N/A * abs(ddpx) > decStepBnd1 || 0N/A * abs(ddpy) > decStepBnd1 0N/A /* Perform increasing step in 2 times if necessary. 0N/A * Note: we could do it only in even steps 0N/A /* The code below is an optimized version of the check: 0N/A * abs(dpx) <= incStepBnd1 && 0N/A * abs(dpy) <= incStepBnd1 0N/A /* We are performing one step less than necessary and use actual 0N/A * (xe,ye) endpoint of the curve instead of calculated. This prevent 0N/A * us from accumulated errors at the last point. 0N/A /* Checking that we are not running out of the endpoint and 0N/A * bounding violating coordinate. The check is pretty simple 0N/A * because the curve passed to the DrawMonotonicCubic already 0N/A * splitted into the monotonic in X and Y pieces 0N/A /* Bounding x2 by xe */ 0N/A /* Bounding y2 by ye */ 0N/A * Checking size of the cubic curves and split them if necessary. 0N/A * Calling DrawMonotonicCubic for the curves of the appropriate size. 0N/A * Note: coords array could be changed 0N/A /* In case of drawing we could just skip curves which are completely 0N/A /* In case of filling we could skip curves which are above, 0N/A * below and behind the right boundary of the visible area 0N/A /* We could clamp x coordinates to the corresponding boundary 0N/A * if the curve is completely behind the left one 0N/A /* Set checkBounds parameter if curve intersects 0N/A * boundary of the visible area. We know that the 0N/A * curve is visible, so the check is pretty simple 0N/A * Bite the piece of the cubic curve from start point till the point 0N/A * corresponding to the specified parameter then call ProcessMonotonicCubic for 0N/A * Note: coords array will be changed 0N/A * Split cubic curve into monotonic in X and Y parts. Calling ProcessCubic for 0N/A * each monotonic piece of the curve. 0N/A * Note: coords array could be changed 0N/A /* Temporary array for holding parameters corresponding to the extreme in X 0N/A * and Y points. The values are inside the (0,1) range (0 and 1 excluded) 0N/A * and in ascending order. 0N/A /* Simple check for monotonicity in X before searching for the extreme 0N/A * points of the X(t) function. We first check if the curve is monotonic in 0N/A * X by seeing if all of the X coordinates are strongly ordered. 0N/A /* Searching for extreme points of the X(t) function by solving 0N/A /* Simple check for monotonicity in Y before searching for the extreme 0N/A * points of the Y(t) function. We first check if the curve is monotonic in 0N/A * Y by seeing if all of the Y coordinates are strongly ordered. 0N/A /* Searching for extreme points of the Y(t) function by solving 0N/A * ----- = 0 equation 0N/A /* Sorting parameter values corresponding to the extremum points of 0N/A * the curve. We are using insertion sort because of tiny size of the 0N/A /* Processing obtained monotonic parts */ 0N/A /* Scale parameter to match with rest of the curve */ 0N/A of clipping to avoid entering 0N/A out of bounds which could 0N/A happens during rounding 0N/A this is the end of the 0N/A subpath (because of exiting 0N/A /* Clamping starting from first vertex of the the processed segment 0N/A /* Clamping only by left boundary */ 0N/A /* Clamping starting from last vertex of the the processed segment 0N/A /* Checking if there was a clip by right boundary */ 0N/A /* Clamping only by left boundary */ 0N/A /* Adding support of the KEY_STROKE_CONTROL rendering hint. 0N/A * Now we are supporting two modes: "pixels at centers" and 0N/A * "pixels at corners". 0N/A * First one is disabled by default but could be enabled by setting 0N/A * VALUE_STROKE_PURE to the rendering hint. It means that pixel at the 0N/A * screen (x,y) has (x + 0.5, y + 0.5) float coordinates. 0N/A * Second one is enabled by default and means straightforward mapping 0N/A /* Adjusting boundaries to the capabilities of the ProcessPath code */ 0N/A /* Setting up fractional clipping box 0N/A * We are using following float -> int mapping: 0N/A * xi = floor(xf + 0.5) 0N/A * So, fractional values that hit the [xmin, xmax) integer interval will be 0N/A * situated inside the [xmin-0.5, xmax - 0.5) fractional interval. We are 0N/A * using EPSF constant to provide that upper boundary is not included. 0N/A /* Performing closing of the unclosed segments */ 0N/A /* Checking SEG_MOVETO coordinates if they are out of the 0N/A * [LOWER_BND, UPPER_BND] range. This check also handles 0N/A * NaN and Infinity values. Skipping next path segment in 0N/A * case of invalid data. 0N/A /* Checking SEG_LINETO coordinates if they are out of the 0N/A * [LOWER_BND, UPPER_BND] range. This check also handles 0N/A * NaN and Infinity values. Ignoring current path segment 0N/A * in case of invalid data. If segment is skipped its 0N/A * endpoint (if valid) is used to begin new subpath. 0N/A /* Checking SEG_QUADTO coordinates if they are out of the 0N/A * [LOWER_BND, UPPER_BND] range. This check also handles 0N/A * NaN and Infinity values. Ignoring current path segment 0N/A * in case of invalid endpoints's data. Equivalent to 0N/A * the SEG_LINETO if endpoint coordinates are valid but 0N/A * there are invalid data among other coordinates 0N/A /* Checking SEG_CUBICTO coordinates if they are out of the 0N/A * [LOWER_BND, UPPER_BND] range. This check also handles 0N/A * NaN and Infinity values. Ignoring current path segment 0N/A * in case of invalid endpoints's data. Equivalent to 0N/A * the SEG_LINETO if endpoint coordinates are valid but 0N/A * there are invalid data among other coordinates 0N/A /* Storing last path's point for using in 0N/A * following segments without initial moveTo 0N/A /* Performing closing of the unclosed segments */ 0N/A * out of memory error and don't leak earlier allocated data 0N/A/* Size of the default buffer in the FillData structure. This buffer is 0N/A * replaced with heap allocated in case of large paths. 0N/A/* Following structure accumulates points of the non-continuous flattened 0N/A * path during iteration through the origin path's segments . The end 0N/A * of the each subpath is marked as lastPoint flag set at the last point 0N/A/* Bubble sorting in the ascending order of the linked list. This 0N/A * implementation stops processing the list if there were no changes during the 0N/A * LIST - ptr to the ptr to the first element of the list 0N/A * ETYPE - type of the element in the list 0N/A * NEXT - accessor to the next field in the list element 0N/A * GET_LKEY - accessor to the key of the list element 0N/A /* r precedes p and s points to the node up to which comparisons \ 0N/A * are to be made */ \
0N/A while ( p != s ) { \
0N/A if ( q == s ) s = p ; \
0N/A/* Accessors for the Edge structure to work with LBUBBLE_SORT */ 0N/A/* TODO: Implement stack/heap allocation technique for active edges 0N/A /* Skipping horizontal segments */ \
0N/A }
else {
/* pnt->y > np->y */ \
0N/A /* We need to worry only about dX because dY is in */\
0N/A /* denominator and abs(dy) < MDP_MULT (cy is a first */\
0N/A /* scanline of the scan converted segment and we subtract */\
0N/A /* y coordinate of the nearest segment's end from it to */\
0N/A /* Because of support of the KEY_STROKE_CONTROL hint we are performing 0N/A * shift of the coordinates at the higher level 0N/A// TODO creating lists using fake first element to avoid special casing of 0N/A// the first element in the list (which otherwise should be performed in each 0N/A /* Winding counter */ 0N/A /* Calculating mask to be applied to the winding counter */ 0N/A /* Creating double linked list (prev, next links) describing path order and 0N/A * hash table with points which fall between scanlines. nextByY link is 0N/A * used for the points which are between same scanlines. Scanlines are 0N/A * passed through the centers of the pixels. 0N/A /* pt->y should be inside hashed interval 0N/A * assert(y-MDP_MULT <= pt->y && pt->y < y); 0N/A /* We could not use O(N) Radix sort here because in most cases list of 0N/A * edges almost sorted. So, bubble sort (O(N^2))is working much 0N/A * better. Note, in case of array of edges Shell sort is more 0N/A /* Correction of the back links in the double linked edge list */ 0N/A /* Performing drawing till the right boundary (for correct rendering 0N/A * shapes clipped at the right side) 0N/A /* There is no need to round line coordinates to the forward differencing 0N/A * precision anymore. Such a rounding was used for preventing the curve go 0N/A * out the endpoint (this sometimes does not help). The problem was fixed 0N/A * in the forward differencing loops. 0N/A /* This function is used only for filling shapes, so there is no 0N/A * check for the type of clipping 0N/A /* Clamping starting from first vertex of the the processed segment */ 0N/A /* Clamping only by left boundary */ 0N/A /* Clamping starting from last vertex of the the processed segment */ 0N/A /* Checking if there was a clip by right boundary */ 0N/A /* Clamping only by left boundary */ 0N/A /* Adding first point of the line only in case of empty or just finished 0N/A /* Initialization of the following fields in the declaration of the hnd 0N/A * above causes warnings on sun studio compiler with -xc99=%none option 0N/A * applied (this option means compliance with C90 standard instead of C99) 0N/A /* Initialization of the following fields in the declaration of the hnd 0N/A * above causes warnings on sun studio compiler with -xc99=%none option 0N/A * applied (this option means compliance with C90 standard instead of C99)