1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17/**
18 * @author Denis M. Kishenko
19 * @version $Revision$
20 */
21package org.apache.harmony.awt.gl.render;
22
23import org.apache.harmony.awt.gl.MultiRectArea;
24
25public class JavaArcRasterizer {
26
27    /**
28     * Adds particular arc segment to mra
29     */
30    static void addX0LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
31        int x1 = 0;
32        for(int i = 0; i < line.length; i++) {
33            int x2 = line[i];
34            int y = cy + (b - i);
35            if (x1 <= finish && x2 >= start) {
36                mra.addRect(cx + Math.max(x1, start), y, cx + Math.min(x2, finish), y);
37            }
38            x1 = x2 + 1;
39        }
40    }
41
42    static void addX1LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
43        int x1 = 0;
44        for(int i = 0; i < line.length; i++) {
45            int x2 = line[i];
46            int y = cy - (b - i);
47            if (x1 <= finish && x2 >= start) {
48                mra.addRect(cx + Math.max(x1, start), y, cx + Math.min(x2, finish), y);
49            }
50            x1 = x2 + 1;
51        }
52    }
53
54    static void addX2LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
55        int x1 = 0;
56        for(int i = 0; i < line.length; i++) {
57            int x2 = line[i];
58            int y = cy - (b - i);
59            if (x1 <= finish && x2 >= start) {
60                mra.addRect(cx - Math.min(x2, finish), y, cx - Math.max(x1, start), y);
61            }
62            x1 = x2 + 1;
63        }
64    }
65
66    static void addX3LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
67        int x1 = 0;
68        for(int i = 0; i < line.length; i++) {
69            int x2 = line[i];
70            int y = cy + (b - i);
71            if (x1 <= finish && x2 >= start) {
72                mra.addRect(cx - Math.min(x2, finish), y, cx - Math.max(x1, start), y);
73            }
74            x1 = x2 + 1;
75        }
76    }
77
78    static void addY0LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
79        int y1 = 0;
80        for(int i = 0; i < line.length; i++) {
81            int x = cx + (b - i);
82            int y2 = line[i];
83            if (y1 <= finish && y2 >= start) {
84                mra.addRect(x, cy + Math.max(y1, start), x, cy + Math.min(y2, finish));
85            }
86            y1 = y2 + 1;
87        }
88    }
89
90    static void addY1LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
91        int y1 = 0;
92        for(int i = 0; i < line.length; i++) {
93            int x = cx - (b - i);
94            int y2 = line[i];
95            if (y1 <= finish && y2 >= start) {
96                mra.addRect(x, cy + Math.max(y1, start), x, cy + Math.min(y2, finish));
97            }
98            y1 = y2 + 1;
99        }
100    }
101
102    static void addY2LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
103        int y1 = 0;
104        for(int i = 0; i < line.length; i++) {
105            int x = cx - (b - i);
106            int y2 = line[i];
107            if (y1 <= finish && y2 >= start) {
108                mra.addRect(x, cy - Math.min(y2, finish), x, cy - Math.max(y1, start));
109            }
110            y1 = y2 + 1;
111        }
112    }
113
114    static void addY3LineSeg(MultiRectArea mra, int[] line, int cx, int cy, int b, int start, int finish) {
115        int y1 = 0;
116        for(int i = 0; i < line.length; i++) {
117            int x = cx + (b - i);
118            int y2 = line[i];
119            if (y1 <= finish && y2 >= start) {
120                mra.addRect(x, cy - Math.min(y2, finish), x, cy - Math.max(y1, start));
121            }
122            y1 = y2 + 1;
123        }
124    }
125
126    static void addX0Line(MultiRectArea mra, int[] line, int cx, int cy, int b) {
127        int prev = 0;
128        for(int i = 0; i < line.length; i++) {
129            mra.addRect(cx + prev, cy + (b - i), cx + line[i], cy + (b - i));
130            prev = line[i] + 1;
131        }
132    }
133
134    static void addX1Line(MultiRectArea mra, int[] line, int cx, int cy, int b) {
135        int prev = 0;
136        for(int i = 0; i < line.length; i++) {
137            mra.addRect(cx + prev, cy - (b - i), cx + line[i], cy - (b - i));
138            prev = line[i] + 1;
139        }
140    }
141
142    static void addX2Line(MultiRectArea mra, int[] line, int cx, int cy, int b) {
143        int prev = 0;
144        for(int i = 0; i < line.length; i++) {
145            mra.addRect(cx - line[i], cy - (b - i), cx - prev, cy - (b - i));
146            prev = line[i] + 1;
147        }
148    }
149
150    static void addX3Line(MultiRectArea mra, int[] line, int cx, int cy, int b) {
151        int prev = 0;
152        for(int i = 0; i < line.length; i++) {
153            mra.addRect(cx - line[i], cy + (b - i), cx - prev, cy + (b - i));
154            prev = line[i] + 1;
155        }
156    }
157
158    static void addY0Line(MultiRectArea mra, int[] line, int cx, int cy, int a) {
159        int prev = 0;
160        for(int i = 0; i < line.length; i++) {
161            mra.addRect(cx + (a - i), cy + prev, cx + (a - i), cy + line[i]);
162            prev = line[i] + 1;
163        }
164    }
165
166    static void addY1Line(MultiRectArea mra, int[] line, int cx, int cy, int a) {
167        int prev = 0;
168        for(int i = 0; i < line.length; i++) {
169            mra.addRect(cx - (a - i), cy + prev, cx - (a - i), cy + line[i]);
170            prev = line[i] + 1;
171        }
172    }
173
174    static void addY2Line(MultiRectArea mra, int[] line, int cx, int cy, int a) {
175        int prev = 0;
176        for(int i = 0; i < line.length; i++) {
177            mra.addRect(cx - (a - i), cy - line[i], cx - (a - i), cy - prev);
178            prev = line[i] + 1;
179        }
180    }
181
182    static void addY3Line(MultiRectArea mra, int[] line, int cx, int cy, int a) {
183        int prev = 0;
184        for(int i = 0; i < line.length; i++) {
185            mra.addRect(cx + (a - i), cy - line[i], cx + (a - i), cy - prev);
186            prev = line[i] + 1;
187        }
188    }
189
190    /**
191     * Returns normalized angle (from 0 to 360 degrees)
192     */
193    static double getNormAngle(double angle) {
194        angle -= Math.floor(angle / 360) * 360;
195        if (angle < 0) {
196            angle += 360;
197        }
198        return angle;
199    }
200
201    /**
202     * Creates arc lookup table
203     */
204    static int[] createLine(int a, int b, int xcount, int ycount) {
205        int[] buf = new int[b - ycount + 1];
206        int d = a * a + 2 * b * b - 2 * a * a * b;
207        int x = 0;
208        int y = b;
209        while (y >= ycount) {
210            if (d < 0) {
211                d = d + b * b * (4 * x + 6);
212            } else {
213                buf[b - y] = x;
214                d = d + b * b * (4 * x + 6) + 4 * a * a * (1 - y);
215                y--;
216            }
217            x++;
218        }
219        return buf;
220    }
221
222    /**
223     * Adds head/tail arc segment to MultiRectArea
224     */
225    static void addSeg(MultiRectArea mra, int cx1, int cy1, int cx2, int cy2, int a, int b, int[] xline, int[] yline, int[] bounds) {
226        switch(bounds[0]) {
227        case 0:
228            addY3LineSeg(mra, yline, cx2, cy1, a, bounds[1], bounds[2]);
229            break;
230        case 1:
231            addX1LineSeg(mra, xline, cx2, cy1, b, bounds[1], bounds[2]);
232            break;
233        case 2:
234            addX2LineSeg(mra, xline, cx1, cy1, b, bounds[1], bounds[2]);
235            break;
236        case 3:
237            addY2LineSeg(mra, yline, cx1, cy1, a, bounds[1], bounds[2]);
238            break;
239        case 4:
240            addY1LineSeg(mra, yline, cx1, cy2, a, bounds[1], bounds[2]);
241            break;
242        case 5:
243            addX3LineSeg(mra, xline, cx1, cy2, b, bounds[1], bounds[2]);
244            break;
245        case 6:
246            addX0LineSeg(mra, xline, cx2, cy2, b, bounds[1], bounds[2]);
247            break;
248        case 7:
249            addY0LineSeg(mra, yline, cx2, cy2, a, bounds[1], bounds[2]);
250            break;
251        }
252    }
253
254    /**
255     * Returns bounds for non quadratic arc head
256     */
257    static int[] getSegment1(double angle, int ax, int ay, int xcount, int ycount) {
258        int[] bounds = new int[3];
259        switch((int)(angle / 90)) {
260        case 0:
261            if (xcount <  ax) {
262                bounds[0] = 0; // Y3
263                bounds[1] = -ay;
264                bounds[2] = ycount;
265            } else {
266                bounds[0] = 1; // X1
267                bounds[1] = 0;
268                bounds[2] = ax;
269            }
270            break;
271        case 1:
272            if (xcount > -ax) {
273                bounds[0] = 2; // X2
274                bounds[1] = -ax;
275                bounds[2] = xcount;
276            } else {
277                bounds[0] = 3; // Y2
278                bounds[1] = 0;
279                bounds[2] = -ay;
280            }
281            break;
282        case 2:
283            if (xcount < -ax) {
284                bounds[0] = 4; // Y1
285                bounds[1] = ay;
286                bounds[2] = ycount;
287            } else {
288                bounds[0] = 5; // X3
289                bounds[1] = 0;
290                bounds[2] = -ax;
291            }
292            break;
293        case 3:
294            if (xcount >  ax) {
295                bounds[0] = 6; // X0
296                bounds[1] = ax;
297                bounds[2] = xcount;
298            } else {
299                bounds[0] = 7; // Y0
300                bounds[1] = 0;
301                bounds[2] = ay;
302            }
303            break;
304        }
305        return bounds;
306    }
307
308    /**
309     * Returns bounds for non quadratic arc tail
310     */
311    static int[] getSegment2(double angle, int ax, int ay, int xcount, int ycount) {
312        int[] bounds = new int[3];
313        switch((int)(angle / 90)) {
314        case 0:
315            if (xcount <  ax) {
316                bounds[0] = 0; // Y3
317                bounds[1] = 0;
318                bounds[2] = -ay;
319            } else {
320                bounds[0] = 1; // X1
321                bounds[1] = ax;
322                bounds[2] = xcount;
323            }
324            break;
325        case 1:
326            if (xcount > -ax) {
327                bounds[0] = 2; // X2
328                bounds[1] = 0;
329                bounds[2] = -ax;
330            } else {
331                bounds[0] = 3; // Y2
332                bounds[1] = -ay;
333                bounds[2] = ycount;
334            }
335            break;
336        case 2:
337            if (xcount < -ax) {
338                bounds[0] = 4; // Y1
339                bounds[1] = 0;
340                bounds[2] = ay;
341            } else {
342                bounds[0] = 5; // X3
343                bounds[1] = -ax;
344                bounds[2] = xcount;
345            }
346            break;
347        case 3:
348            if (xcount >  ax) {
349                bounds[0] = 6; // X0
350                bounds[1] = 0;
351                bounds[2] = ax;
352            } else {
353                bounds[0] = 7; // Y0
354                bounds[1] = ay;
355                bounds[2] = ycount;
356            }
357            break;
358        }
359        return bounds;
360    }
361
362    /**
363     * Rasterizes arc using clippind and dashing style
364     * @param x1 - the x coordinate of the left-upper corner of the arc bounds
365     * @param y1 - the y coordinate of the left-upper corner of the arc bounds
366     * @param width - the width of the arc bounds
367     * @param height - the height of the arc bounds
368     * @param angleStart - the start angle of the arc in degrees
369     * @param angleExtent - the angle extent in degrees
370     * @param clip - the MultiRectArea object of clipping area
371     * @return a MultiRectArea of rasterizer arc
372     */
373    public static MultiRectArea rasterize(int x, int y, int width, int height, double angleStart, double angleExtent, MultiRectArea clip) {
374
375        MultiRectArea mra = new MultiRectArea(false);
376
377        int cx1, cx2, cy1, cy2;
378        cx1 = cx2 = x + width / 2;
379        cy1 = cy2 = y + height / 2;
380
381        if (width % 2 == 0) {
382            cx2--;
383        }
384
385        if (height % 2 == 0) {
386            cy2--;
387        }
388
389        int a = width / 2;
390        int b = height / 2;
391        double c = Math.sqrt(a * a + b * b);
392
393        int xcount, ycount;
394        if (a < b) {
395            xcount = (int)Math.ceil(a * a / c);
396            ycount = (int)Math.floor(b * b / c);
397        } else {
398            xcount = (int)Math.floor(a * a / c);
399            ycount = (int)Math.ceil(b * b / c);
400        }
401
402        int[] xline = createLine(a, b, xcount, ycount);
403        int[] yline = createLine(b, a, ycount, xcount);
404
405        // Correct lines
406        int i = xline.length;
407        while(xline[--i] > xcount) {
408            xline[i] = xcount;
409        }
410
411        i = yline.length;
412        while(yline[--i] > ycount) {
413            yline[i] = ycount;
414        }
415
416        if (Math.abs(angleExtent) >= 360) {
417            // Rasterize CIRCLE
418            addX0Line(mra, xline, cx2, cy2, b);
419            addX1Line(mra, xline, cx2, cy1, b);
420            addX2Line(mra, xline, cx1, cy1, b);
421            addX3Line(mra, xline, cx1, cy2, b);
422            addY0Line(mra, yline, cx2, cy2, a);
423            addY1Line(mra, yline, cx1, cy2, a);
424            addY2Line(mra, yline, cx1, cy1, a);
425            addY3Line(mra, yline, cx2, cy1, a);
426        } else {
427            // Rasterize ARC
428            angleStart = getNormAngle(angleStart);
429            double angleFinish = getNormAngle(angleStart + angleExtent);
430
431            if (angleExtent < 0) {
432                double tmp = angleStart;
433                angleStart = angleFinish;
434                angleFinish = tmp;
435            }
436
437            double radStart = -Math.toRadians(angleStart);
438            double radFinish = -Math.toRadians(angleFinish);
439            int ax1 = (int)(a * Math.cos(radStart));
440            int ay1 = (int)(b * Math.sin(radStart));
441            int ax2 = (int)(a * Math.cos(radFinish));
442            int ay2 = (int)(b * Math.sin(radFinish));
443
444            int[] seg1 = getSegment1(angleStart, ax1, ay1, xcount, ycount);
445            int[] seg2 = getSegment2(angleFinish, ax2, ay2, xcount, ycount);
446
447            // Start and Finish located in the same quater
448            if (angleStart < angleFinish && seg1[0] == seg2[0]) {
449                if (seg1[0] % 2 == 0) {
450                    seg1[2] = seg2[2];
451                } else {
452                    seg1[1] = seg2[1];
453                }
454                addSeg(mra, cx1, cy1, cx2, cy2, a, b, xline, yline, seg1);
455                return mra;
456            }
457
458            addSeg(mra, cx1, cy1, cx2, cy2, a, b, xline, yline, seg1);
459            addSeg(mra, cx1, cy1, cx2, cy2, a, b, xline, yline, seg2);
460
461            int startSeg = (seg1[0] + 1) % 8;
462            int finishSeg = seg2[0];
463
464            while (startSeg != finishSeg) {
465                switch(startSeg) {
466                case 0:
467                    addY3Line(mra, yline, cx2, cy1, a);
468                    break;
469                case 1:
470                    addX1Line(mra, xline, cx2, cy1, b);
471                    break;
472                case 2:
473                    addX2Line(mra, xline, cx1, cy1, b);
474                    break;
475                case 3:
476                    addY2Line(mra, yline, cx1, cy1, a);
477                    break;
478                case 4:
479                    addY1Line(mra, yline, cx1, cy2, a);
480                    break;
481                case 5:
482                    addX3Line(mra, xline, cx1, cy2, b);
483                    break;
484                case 6:
485                    addX0Line(mra, xline, cx2, cy2, b);
486                    break;
487                case 7:
488                    addY0Line(mra, yline, cx2, cy2, a);
489                    break;
490                }
491                startSeg = (startSeg + 1) % 8;
492            }
493        }
494
495        if (clip != null) {
496            mra.intersect(clip);
497        }
498
499        return mra;
500    }
501
502}