Blame - jdk/src/share/native/sun/java2d/loops/ProcessPath.c - platform/libcore

blob: eff9200a14bfdcab0cb27d9a231f736425bb5e63 [file] [log] [blame]

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