001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: /**
018: * @author Denis M. Kishenko
019: * @version $Revision$
020: */package org.apache.harmony.awt.gl.render;
021:
022: import java.awt.Shape;
023: import java.awt.geom.PathIterator;
024:
025: import org.apache.harmony.awt.gl.MultiRectArea;
026: import org.apache.harmony.awt.internal.nls.Messages;
027:
028: public class JavaShapeRasterizer {
029:
030: static final int POINT_CAPACITY = 16;
031:
032: int edgesCount;
033: int edgeCur;
034: int[] edgesX;
035: int[] edgesY;
036: int[] edgesYS; // Y coordinate of edge START point
037: int[] edgesN;
038: int[] edgesDY;
039: int[] bounds;
040: int boundCount;
041: boolean[] edgesExt; // Extremal points
042:
043: int activeCount;
044: float[] activeX;
045: int[] activeYEnd;
046: float[] activeXStep;
047: int[] activeDY;
048: boolean[] activeExt;
049:
050: int[] crossX;
051: int[] crossDY;
052:
053: Filler filler;
054:
055: /**
056: * Rasterization filler for different path rules
057: */
058: static abstract class Filler {
059:
060: static class NonZero extends Filler {
061: @Override
062: void add(MultiRectArea.LineCash rect, int[] points,
063: int[] orient, int length, int y) {
064:
065: int[] dst = new int[length];
066: int dstLength = 1;
067: dst[0] = points[0];
068: int count = 0;
069: boolean inside = true;
070: for (int i = 0; i < length; i++) {
071: count += orient[i] > 0 ? 1 : -1;
072: if (count == 0) {
073: dst[dstLength++] = points[i];
074: inside = false;
075: } else {
076: if (!inside) {
077: dst[dstLength++] = points[i];
078: inside = true;
079: }
080: }
081:
082: }
083:
084: for (int i = 1; i < dstLength; i += 2) {
085: dst[i]--;
086: }
087:
088: dstLength = excludeEmpty(dst, dstLength);
089: // System.out.println("test");
090:
091: dstLength = union(dst, dstLength);
092:
093: rect.addLine(dst, dstLength);
094: }
095: }
096:
097: static class EvenOdd extends Filler {
098: @Override
099: void add(MultiRectArea.LineCash rect, int[] points,
100: int[] orient, int length, int y) {
101: /*
102: int[] buf = new int[length];
103: int j = 0;
104: for(int i = 0; i < length - 1; i++) {
105: if (points[i] != points[i + 1]) {
106: buf[j++] = points[i];
107: }
108: }
109: */
110: for (int i = 1; i < length; i += 2) {
111: points[i]--;
112: }
113:
114: length = excludeEmpty(points, length);
115: // System.out.println("test");
116:
117: length = union(points, length);
118: rect.addLine(points, length);
119: /*
120: for(int i = 0; i < length;) {
121: rect.add(points[i++], y, points[i++], y);
122: }
123: */
124: }
125: }
126:
127: abstract void add(MultiRectArea.LineCash rect, int[] points,
128: int[] orient, int length, int y);
129:
130: static int excludeEmpty(int[] points, int length) {
131: int i = 0;
132: while (i < length) {
133: if (points[i] <= points[i + 1]) {
134: i += 2;
135: } else {
136: length -= 2;
137: System.arraycopy(points, i + 2, points, i, length
138: - i);
139: }
140: }
141: return length;
142: }
143:
144: static int union(int[] points, int length) {
145: int i = 1;
146: while (i < length - 1) {
147: if (points[i] < points[i - 1]) {
148: System.arraycopy(points, i + 1, points, i - 1,
149: length - i - 1);
150: length -= 2;
151: } else if (points[i] >= points[i + 1] - 1) {
152: System.arraycopy(points, i + 2, points, i, length
153: - i - 2);
154: length -= 2;
155: } else {
156: i += 2;
157: }
158: }
159: return length;
160: }
161:
162: }
163:
164: public JavaShapeRasterizer() {
165: }
166:
167: /**
168: * Checks buffer size and realloc if necessary
169: */
170: int[] checkBufSize(int[] buf, int size) {
171: if (size == buf.length) {
172: int[] tmp;
173: tmp = new int[size + POINT_CAPACITY];
174: System.arraycopy(buf, 0, tmp, 0, buf.length);
175: buf = tmp;
176: }
177: return buf;
178: }
179:
180: /**
181: * Adds to the buffers new edge
182: */
183: void addEdge(int x, int y, int num) {
184: edgesX = checkBufSize(edgesX, edgesCount);
185: edgesY = checkBufSize(edgesY, edgesCount);
186: edgesN = checkBufSize(edgesN, edgesCount);
187: edgesX[edgesCount] = x;
188: edgesY[edgesCount] = y;
189: edgesN[edgesCount] = (num << 16) | edgesCount;
190: edgesCount++;
191: }
192:
193: /**
194: * Prepare all buffers and variable to rasterize shape
195: */
196: void makeBuffer(PathIterator path, double flatness) {
197: edgesX = new int[POINT_CAPACITY];
198: edgesY = new int[POINT_CAPACITY];
199: edgesN = new int[POINT_CAPACITY];
200: bounds = new int[POINT_CAPACITY];
201: boundCount = 0;
202: edgesCount = 0;
203:
204: if (path.getWindingRule() == PathIterator.WIND_EVEN_ODD) {
205: filler = new Filler.EvenOdd();
206: } else {
207: filler = new Filler.NonZero();
208: }
209: float[] coords = new float[2];
210: boolean closed = true;
211: while (!path.isDone()) {
212: switch (path.currentSegment(coords)) {
213: case PathIterator.SEG_MOVETO:
214: if (!closed) {
215: boundCount++;
216: bounds = checkBufSize(bounds, boundCount);
217: bounds[boundCount] = edgesCount;
218: }
219: addEdge((int) coords[0], (int) coords[1], boundCount);
220: closed = false;
221: break;
222: case PathIterator.SEG_LINETO:
223: addEdge((int) coords[0], (int) coords[1], boundCount);
224: break;
225: case PathIterator.SEG_CLOSE:
226: boundCount++;
227: bounds = checkBufSize(bounds, boundCount);
228: bounds[boundCount] = edgesCount;
229: closed = true;
230: break;
231: default:
232: // awt.36=Wrong segment
233: throw new RuntimeException(Messages.getString("awt.36")); //$NON-NLS-1$
234: }
235: path.next();
236: }
237: if (!closed) {
238: boundCount++;
239: bounds = checkBufSize(bounds, boundCount);
240: bounds[boundCount] = edgesCount;
241: }
242: }
243:
244: /**
245: * Sort buffers
246: */
247: void sort(int[] master, int[] slave, int length) {
248: for (int i = 0; i < length - 1; i++) {
249: int num = i;
250: int min = master[num];
251: for (int j = i + 1; j < length; j++) {
252: if (master[j] < min) {
253: num = j;
254: min = master[num];
255: }
256: }
257: if (num != i) {
258: master[num] = master[i];
259: master[i] = min;
260: min = slave[num];
261: slave[num] = slave[i];
262: slave[i] = min;
263: }
264: }
265: }
266:
267: int getNext(int cur) {
268: int n = edgesN[cur];
269: int bound = n >> 16;
270: int num = (n & 0xFFFF) + 1;
271: if (num == bounds[bound + 1]) {
272: return bounds[bound];
273: }
274: return num;
275: }
276:
277: int getPrev(int cur) {
278: int n = edgesN[cur];
279: int bound = n >> 16;
280: int num = (n & 0xFFFF) - 1;
281: if (num < bounds[bound]) {
282: return bounds[bound + 1] - 1;
283: }
284: return num;
285: }
286:
287: int getNextShape(int cur) {
288: int bound = edgesN[cur] >> 16;
289: return bounds[bound + 1];
290: }
291:
292: void init() {
293:
294: edgesYS = new int[edgesCount];
295: System.arraycopy(edgesY, 0, edgesYS, 0, edgesCount);
296: // Create edgesDY
297: edgesDY = new int[edgesCount];
298: for (int i = 0; i < edgesCount; i++) {
299: int dy = edgesY[getNext(i)] - edgesY[i];
300: edgesDY[i] = dy;
301: }
302:
303: // Create edgesExt
304: edgesExt = new boolean[edgesCount];
305: int prev = -1;
306: int i = 0;
307: int pos = 0;
308: while (i < edgesCount) {
309:
310: TOP: {
311: do {
312: if (edgesDY[i] > 0) {
313: break TOP;
314: }
315: i = getNext(i);
316: } while (i != pos);
317: i = pos = getNextShape(i);
318: continue;
319: }
320:
321: BOTTOM: {
322: do {
323: if (edgesDY[i] < 0) {
324: break BOTTOM;
325: }
326: if (edgesDY[i] > 0) {
327: prev = i;
328: }
329: i = getNext(i);
330: } while (i != pos);
331: i = pos = getNextShape(i);
332: continue;
333: }
334:
335: if (prev != -1) {
336: edgesExt[prev] = true;
337: }
338: edgesExt[i] = true;
339: }
340:
341: // Sort edgesY and edgesN
342: sort(edgesYS, edgesN, edgesCount);
343:
344: edgeCur = 0;
345: activeCount = 0;
346: activeX = new float[edgesCount];
347: activeYEnd = new int[edgesCount];
348: activeXStep = new float[edgesCount];
349: activeDY = new int[edgesCount];
350: activeExt = new boolean[edgesCount];
351:
352: crossX = new int[edgesCount];
353: crossDY = new int[edgesCount];
354: }
355:
356: /**
357: * Marks edge as active
358: */
359: void addActiveEdge(int levelY, int start, int end, boolean back) {
360: int dy = back ? -edgesDY[end] : edgesDY[start];
361: if (dy <= 0) {
362: return;
363: }
364: int x1 = edgesX[start];
365: int dx = edgesX[end] - x1;
366: activeX[activeCount] = x1;
367: activeYEnd[activeCount] = edgesY[end];
368: activeXStep[activeCount] = dx / (float) dy;
369: activeDY[activeCount] = back ? -dy : dy;
370: activeExt[activeCount] = back ? edgesExt[end] : edgesExt[start];
371: activeCount++;
372: }
373:
374: /**
375: * Find new active edges
376: */
377: int findActiveEdges(int levelY) {
378:
379: int edgeActive = edgeCur;
380: while (edgeActive < edgesCount && edgesYS[edgeActive] == levelY) {
381: edgeActive++;
382: }
383:
384: int activeNext = edgeActive;
385:
386: while (edgeActive > edgeCur) {
387: edgeActive--;
388: int num = edgesN[edgeActive] & 0xFFFF;
389: addActiveEdge(levelY, num, getPrev(edgeActive), true);
390: addActiveEdge(levelY, num, getNext(edgeActive), false);
391: }
392:
393: edgeCur = activeNext;
394:
395: if (activeNext == edgesCount) {
396: return edgesY[edgesCount - 1];
397: }
398: return edgesYS[activeNext];
399: }
400:
401: /**
402: * Rasterizes shape with particular flatness
403: * @param shape - the souze Shape to be rasterized
404: * @param flatness - the rasterization flatness
405: * @return a MultiRectArea of rasterized shape
406: */
407: public MultiRectArea rasterize(Shape shape, double flatness) {
408:
409: PathIterator path = shape.getPathIterator(null, flatness);
410:
411: // Shape is empty
412: if (path.isDone()) {
413: return new MultiRectArea();
414: }
415:
416: makeBuffer(path, flatness);
417:
418: init();
419:
420: int y = edgesYS[0];
421: int nextY = y;
422: int crossCount;
423:
424: MultiRectArea.LineCash rect = new MultiRectArea.LineCash(
425: edgesCount);
426: rect.setLine(y);
427:
428: while (y <= nextY) {
429:
430: crossCount = 0;
431:
432: if (y == nextY) {
433:
434: int i = activeCount;
435: while (i > 0) {
436: i--;
437: if (activeYEnd[i] == y) {
438:
439: activeCount--;
440: int length = activeCount - i;
441: if (length != 0) {
442: int pos = i + 1;
443: System.arraycopy(activeX, pos, activeX, i,
444: length);
445: System.arraycopy(activeYEnd, pos,
446: activeYEnd, i, length);
447: System.arraycopy(activeXStep, pos,
448: activeXStep, i, length);
449: System.arraycopy(activeDY, pos, activeDY,
450: i, length);
451: System.arraycopy(activeExt, pos, activeExt,
452: i, length);
453: }
454: }
455: }
456:
457: nextY = findActiveEdges(y);
458: }
459:
460: // Get X crossings
461: for (int i = 0; i < activeCount; i++) {
462: crossX[crossCount] = (int) Math.ceil(activeX[i]);
463: crossDY[crossCount] = activeDY[i];
464: crossCount++;
465: }
466:
467: if (crossCount == 0) {
468: rect.skipLine();
469: } else {
470: // Sort X crossings
471: sort(crossX, crossDY, crossCount);
472: filler.add(rect, crossX, crossDY, crossCount, y);
473: }
474:
475: for (int i = 0; i < activeCount; i++) {
476: activeX[i] += activeXStep[i];
477: }
478:
479: y++;
480: }
481:
482: return rect;
483: }
484:
485: }
|