001: /*
002: * Copyright (C) 2005, 2006 data2c GmbH (www.data2c.com)
003: *
004: * Author: Wolfgang S. Kechel - wolfgang.kechel@data2c.com
005: */
006:
007: package org.graphics;
008:
009: //#ifdef j2se
010: import java.awt.Graphics;
011: import java.awt.Point; //#else
012: import javax.microedition.lcdui.Graphics;
013: import org.awt.Point; //#endif
014:
015: import java.util.Hashtable;
016:
017: public class Draw {
018: public static void drawPolygon(Graphics g, int n, Point[] points,
019: boolean filled) {
020: if (n < 2)
021: return;
022: if (filled) {
023: fillPolygon(g, n, points, true);
024: }
025: for (int i = 0, j = 1; j < n; ++i, ++j) {
026: g.drawLine(points[i].x, points[i].y, points[j].x,
027: points[j].y);
028: }
029: g.drawLine(points[n - 1].x, points[n - 1].y, points[0].x,
030: points[0].y);
031: }
032:
033: public static void translate(Graphics g, int x, int y) {
034: //#ifdef j2se
035: // Is this really not cumulative??????
036: g.translate(x, y);
037: //#else
038: g.translate(x - g.getTranslateX(), y - g.getTranslateY());
039: //#endif
040: }
041:
042: public static void translate(Graphics g, Point p) {
043: translate(g, p.x, p.y);
044: }
045:
046: protected static void fillSpans(Graphics g, int count,
047: Point[] points, int[] width) {
048: //System.err.println("drawing "+count+" spans");
049: for (int i = 0; i < count; ++i) {
050: int len = width[i];
051:
052: if (len > 0) {
053: int x = points[i].x;
054: int y = points[i].y;
055:
056: //#ifdef notdef
057: int last = x + len;
058: // clip if completely outside
059: if (y < 0 || y >= h || x >= w || last < 0)
060: continue;
061: drawSpan(y, x, last, '*');
062: //#else
063: g.drawLine(x, y, x + len, y);
064: //#endif
065: }
066: }
067: }
068:
069: protected static void fillPolygon(Graphics g, int count,
070: Point[] ptsIn, boolean evenoddrule) {
071: if (count < 3)
072: return;
073: //#ifndef j2se
074: if (count == 3) {
075: g.fillTriangle(ptsIn[0].x, ptsIn[0].y, ptsIn[1].x,
076: ptsIn[1].y, ptsIn[2].x, ptsIn[2].y);
077: return;
078: }
079: //#endif
080:
081: //#ifdef notdef
082: // Desktop code, does not work for J2ME
083: // we currently use our own code!
084: Polygon poly = new Polygon();
085:
086: for (int i = 0; i < count; ++i)
087: poly.addPoint(ptsIn[i]);
088: g.fillPolygon(poly);
089: //#endif
090:
091: //System.err.println("building edgetable...");
092: EdgeTable ET = new EdgeTable(count, ptsIn);
093: //System.err.println("edgetable done!");
094:
095: ScanLineList pSLL = ET.scanlines.next;
096: EdgeTableEntry pPrevAET = null;
097: EdgeTableEntry pAET = null;
098:
099: Point[] ptsOut = new Point[NUMPTSTOBUFFER];
100: int[] width = new int[NUMPTSTOBUFFER];
101: int nPts = 0;
102:
103: if (evenoddrule) {
104: /*
105: * for each scanline
106: */
107: for (int y = ET.ymin; y < ET.ymax; y++) {
108: //System.err.println("etmin="+ET.ymin+", etmax="+ET.ymax+", y="+y);
109:
110: /*
111: * Add a new edge to the active edge table when we
112: * get to the next edge.
113: */
114: if (pSLL != null && y == pSLL.scanline) {
115: //System.err.println("loading AET...");
116: ET.loadAET(pSLL.edgelist);
117: pSLL = pSLL.next;
118: //System.err.println("AET loaded!");
119: }
120: pPrevAET = ET.aet;
121: pAET = ET.aet.next;
122:
123: /*
124: * for each active edge
125: */
126: while (pAET != null) {
127: if (ptsOut[nPts] == null)
128: ptsOut[nPts] = new Point(pAET.bres.minor, y);
129: else
130: ptsOut[nPts].move(pAET.bres.minor, y);
131: width[nPts] = pAET.next.bres.minor
132: - pAET.bres.minor;
133: //System.err.println("Point["+nPts+"]=(" + ptsOut[nPts].x+", "+ptsOut[nPts].y + "), w="+width[nPts]);
134: nPts++;
135:
136: /*
137: * send out the buffer when its full
138: */
139: if (nPts == NUMPTSTOBUFFER) {
140: fillSpans(g, nPts, ptsOut, width);
141: nPts = 0;
142: }
143:
144: if (pAET.ymax == y) {
145: /* leaving this edge */
146: pPrevAET.next = pAET.next;
147: pAET = pPrevAET.next;
148: if (pAET != null)
149: pAET.back = pPrevAET;
150: } else {
151: pAET.bres.increment();
152: pPrevAET = pAET;
153: pAET = pAET.next;
154: }
155: if (pAET.ymax == y) {
156: /* leaving this edge */
157: pPrevAET.next = pAET.next;
158: pAET = pPrevAET.next;
159: if (pAET != null)
160: pAET.back = pPrevAET;
161: } else {
162: pAET.bres.increment();
163: pPrevAET = pAET;
164: pAET = pAET.next;
165: }
166: }
167: //System.err.println("insertionSort...");
168: ET.insertionSort();
169: }
170: } else {
171: // default to windingrule
172: boolean fixWAET = false;
173: EdgeTableEntry pWETE = null;
174:
175: // for each scanline
176: for (int y = ET.ymin; y < ET.ymax; y++) {
177: /*
178: * Add a new edge to the active edge table when we
179: * get to the next edge.
180: */
181: if (pSLL != null && y == pSLL.scanline) {
182: ET.loadAET(pSLL.edgelist);
183: ET.computeWAET();
184: pSLL = pSLL.next;
185: }
186: pPrevAET = ET.aet;
187: pAET = ET.aet.next;
188: pWETE = pAET;
189:
190: // for each active edge
191: while (pAET != null) {
192: /*
193: * if the next edge in the active edge table is
194: * also the next edge in the winding active edge
195: * table.
196: */
197: if (pWETE == pAET) {
198: if (ptsOut[nPts] == null)
199: ptsOut[nPts] = new Point(pAET.bres.minor, y);
200: else
201: ptsOut[nPts].move(pAET.bres.minor, y);
202: width[nPts] = pAET.nextWETE.bres.minor
203: - pAET.bres.minor;
204: nPts++;
205:
206: // send out the buffer
207: if (nPts == NUMPTSTOBUFFER) {
208: fillSpans(g, nPts, ptsOut, width);
209: nPts = 0;
210: }
211:
212: pWETE = pWETE.nextWETE;
213: while (pWETE != pAET) {
214: if (pAET.ymax == y) {
215: // leaving this edge
216: pPrevAET.next = pAET.next;
217: pAET = pPrevAET.next;
218: fixWAET = true;
219: if (pAET != null)
220: pAET.back = pPrevAET;
221: } else {
222: pAET.bres.increment();
223: pPrevAET = pAET;
224: pAET = pAET.next;
225: }
226: }
227: pWETE = pWETE.nextWETE;
228: }
229: while (pWETE != pAET) {
230: if (pAET.ymax == y) {
231: // leaving this edge
232: pPrevAET.next = pAET.next;
233: pAET = pPrevAET.next;
234: fixWAET = true;
235: if (pAET != null)
236: pAET.back = pPrevAET;
237: } else {
238: pAET.bres.increment();
239: pPrevAET = pAET;
240: pAET = pAET.next;
241: }
242: }
243: }
244:
245: /*
246: * reevaluate the Winding active edge table if we
247: * just had to resort it or if we just exited an edge.
248: */
249: if (ET.insertionSort() || fixWAET) {
250: ET.computeWAET();
251: fixWAET = false;
252: }
253: }
254: }
255: /* Get any spans that we missed by buffering */
256: fillSpans(g, nPts, ptsOut, width);
257: }
258:
259: static class BresInfo {
260: /*
261: * In scan converting polygons, we want to choose those pixels
262: * which are inside the polygon. Thus, we add .5 to the starting
263: * x coordinate for both left and right edges. Now we choose the
264: * first pixel which is inside the pgon for the left edge and the
265: * first pixel which is outside the pgon for the right edge.
266: * Draw the left pixel, but not the right.
267: *
268: * How to add .5 to the starting x coordinate:
269: * If the edge is moving to the right, then subtract dy from the
270: * error term from the general form of the algorithm.
271: * If the edge is moving to the left, then add dy to the error term.
272: *
273: * The reason for the difference between edges moving to the left
274: * and edges moving to the right is simple: If an edge is moving
275: * to the right, then we want the algorithm to flip immediately.
276: * If it is moving to the left, then we don't want it to flip until
277: * we traverse an entire pixel.
278: */
279: BresInfo() {
280: minor = Integer.MIN_VALUE;
281: d = m = m1 = incr1 = incr2 = 0;
282: }
283:
284: BresInfo(int dy, int x1, int x2) {
285: /*
286: * if the edge is horizontal, then it is ignored
287: * and assumed not to be processed. Otherwise, do this stuff.
288: */
289: if (dy != 0) {
290: minor = x1;
291: int dx = x2 - minor;
292: if (dx < 0) {
293: m = dx / dy;
294: m1 = m - 1;
295: incr1 = -2 * dx + 2 * dy * m1;
296: incr2 = -2 * dx + 2 * dy * m;
297: d = 2 * m * dy - 2 * dx - 2 * dy;
298: } else {
299: m = dx / dy;
300: m1 = m + 1;
301: incr1 = 2 * dx - 2 * dy * m1;
302: incr2 = 2 * dx - 2 * dy * m;
303: d = -2 * m * dy + 2 * dx;
304: }
305: }
306: }
307:
308: void increment() {
309: if (m1 > 0) {
310: if (d > 0) {
311: minor += m1;
312: d += incr1;
313: } else {
314: minor += m;
315: d += incr2;
316: }
317: } else {
318: if (d >= 0) {
319: minor += m1;
320: d += incr1;
321: } else {
322: minor += m;
323: d += incr2;
324: }
325: }
326: }
327:
328: int minor; /* minor axis */
329: int d; /* decision variable */
330: int m, m1; /* slope and slope+1 */
331: int incr1, incr2; /* error increments */
332: }
333:
334: static class EdgeTableEntry {
335: EdgeTableEntry() {
336: ymax = -1;
337: next = back = null;
338: nextWETE = null;
339: ClockWise = false;
340: bres = new BresInfo();
341: }
342:
343: EdgeTableEntry(int y, int dy, int topx, int bottomx,
344: boolean clockwise) {
345: ymax = y;
346: bres = new BresInfo(dy, topx, bottomx);
347: next = back = null;
348: nextWETE = null;
349: ClockWise = clockwise;
350: }
351:
352: int ymax; /* ycoord at which we exit this edge. */
353: BresInfo bres; /* Bresenham info to run the edge */
354: EdgeTableEntry next; /* next in the list */
355: EdgeTableEntry back; /* for insertion sort */
356: EdgeTableEntry nextWETE; /* for winding num rule */
357: boolean ClockWise; /* flag for winding number rule */
358: }
359:
360: static class ScanLineList {
361: ScanLineList(int y, ScanLineList xnext) {
362: scanline = y;
363: edgelist = null;
364: next = xnext;
365: }
366:
367: int scanline; /* the scanline represented */
368: EdgeTableEntry edgelist; /* header node */
369: ScanLineList next; /* next in the list */
370: };
371:
372: static class EdgeTable {
373: public EdgeTable(int count, Point[] ptsIn) {
374: ymax = Integer.MIN_VALUE;
375: ymin = Integer.MAX_VALUE;
376: aet = new EdgeTableEntry();
377: // create head of scanlinelist with dummy entry
378: scanlines = new ScanLineList(0, null);
379:
380: Point bottom = null;
381: Point top = null;
382: boolean clockwise = false;
383:
384: for (int currpt = 0, prevpt = count - 1; currpt < count; ++currpt) {
385:
386: if (ptsIn[prevpt].y > ptsIn[currpt].y) {
387: bottom = ptsIn[prevpt];
388: top = ptsIn[currpt];
389: clockwise = false;
390: } else {
391: bottom = ptsIn[currpt];
392: top = ptsIn[prevpt];
393: clockwise = true;
394: }
395:
396: /*
397: * don't add horizontal edges to the Edge table.
398: */
399: if (bottom.y != top.y) {
400: /*
401: * initialize integer edge algorithm
402: */
403: int dy = bottom.y - top.y;
404: /* -1 for y so we don't get last scanline */
405: insertEdge(new EdgeTableEntry(bottom.y - 1, dy,
406: top.x, bottom.x, clockwise), top.y);
407: if (ptsIn[prevpt].y > ymax)
408: ymax = ptsIn[prevpt].y;
409: if (ptsIn[prevpt].y < ymin)
410: ymin = ptsIn[prevpt].y;
411: }
412: prevpt = currpt;
413: }
414: }
415:
416: void insertEdge(EdgeTableEntry ETE, int scanline) {
417: /*
418: * find the right bucket to put the edge into
419: */
420: ScanLineList pPrevSLL = scanlines;
421: ScanLineList pSLL = pPrevSLL.next;
422: while (pSLL != null && (pSLL.scanline < scanline)) {
423: pPrevSLL = pSLL;
424: pSLL = pSLL.next;
425: }
426:
427: /*
428: * reassign pSLL (pointer to ScanLineList) if necessary
429: */
430: if (pSLL == null || pSLL.scanline > scanline) {
431: pSLL = new ScanLineList(scanline, pPrevSLL.next);
432: pPrevSLL.next = pSLL;
433: }
434: //pSLL.scanline = scanline;
435:
436: /*
437: * now insert the edge in the right bucket
438: */
439: EdgeTableEntry prev = null;
440: EdgeTableEntry start = pSLL.edgelist;
441: //System.err.println("adding edge to bucket");
442: while (start != null && (start.bres.minor < ETE.bres.minor)) {
443: prev = start;
444: start = start.next;
445: }
446: ETE.next = start;
447:
448: if (prev != null)
449: prev.next = ETE;
450: else
451: pSLL.edgelist = ETE;
452: }
453:
454: /*
455: * loadAET
456: *
457: * This routine moves EdgeTableEntries from the
458: * EdgeTable into the Active Edge Table,
459: * leaving them sorted by smaller x coordinate.
460: */
461: void loadAET(EdgeTableEntry ETEs) {
462: EdgeTableEntry pPrevAET = aet;
463: EdgeTableEntry AET = aet.next;
464: while (ETEs != null) {
465: while (AET != null
466: && (AET.bres.minor < ETEs.bres.minor)) {
467: pPrevAET = AET;
468: AET = AET.next;
469: }
470: EdgeTableEntry tmp = ETEs.next;
471: ETEs.next = AET;
472: if (AET != null)
473: AET.back = ETEs;
474: ETEs.back = pPrevAET;
475: pPrevAET.next = ETEs;
476: pPrevAET = ETEs;
477: ETEs = tmp;
478: }
479: }
480:
481: /*
482: * computeWAET
483: *
484: * This routine links the AET by the
485: * nextWETE (winding EdgeTableEntry) link for
486: * use by the winding number rule. The final
487: * Active Edge Table (AET) might look something
488: * like:
489: *
490: * AET
491: * ---------- --------- ---------
492: * |ymax | |ymax | |ymax |
493: * | ... | |... | |... |
494: * |next |->|next |->|next |->...
495: * |nextWETE| |nextWETE| |nextWETE|
496: * --------- --------- ^--------
497: * | | |
498: * V-------------------> V---> ...
499: *
500: */
501: void computeWAET() {
502: boolean inside = true;
503: int isInside = 0;
504: EdgeTableEntry AET = aet;
505: AET.nextWETE = null;
506: EdgeTableEntry pWETE = aet;
507: AET = AET.next;
508: while (AET != null) {
509: if (AET.ClockWise)
510: isInside++;
511: else
512: isInside--;
513:
514: if ((!inside && isInside == 0)
515: || (inside && isInside != 0)) {
516: pWETE.nextWETE = AET;
517: pWETE = AET;
518: inside = !inside;
519: }
520: AET = AET.next;
521: }
522: pWETE.nextWETE = null;
523: }
524:
525: /*
526: * InsertionSort
527: *
528: * Just a simple insertion sort using
529: * pointers and back pointers to sort the Active
530: * Edge Table.
531: *
532: */
533: boolean insertionSort() {
534: EdgeTableEntry pETEchase;
535: EdgeTableEntry pETEinsert;
536: EdgeTableEntry pETEchaseBackTMP;
537: boolean changed = false;
538:
539: for (EdgeTableEntry AET = aet.next; AET != null;) {
540: pETEinsert = AET;
541: pETEchase = AET;
542: while (pETEchase.back.bres.minor > AET.bres.minor)
543: pETEchase = pETEchase.back;
544:
545: AET = AET.next;
546: if (pETEchase != pETEinsert) {
547: pETEchaseBackTMP = pETEchase.back;
548: pETEinsert.back.next = AET;
549: if (AET != null)
550: AET.back = pETEinsert.back;
551: pETEinsert.next = pETEchase;
552: pETEchase.back.next = pETEinsert;
553: pETEchase.back = pETEinsert;
554: pETEinsert.back = pETEchaseBackTMP;
555: changed = true;
556: }
557: }
558: return changed;
559: }
560:
561: int ymax; /* ymax for the polygon */
562: int ymin; /* ymin for the polygon */
563: ScanLineList scanlines; /* header node */
564: EdgeTableEntry aet;
565: }
566:
567: private static final int NUMPTSTOBUFFER = 100;
568:
569: }
|