1 /**
2 * Copyright (c) 2011, The University of Southampton and the individual contributors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * * Neither the name of the University of Southampton nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.openimaj.image.renderer;
31
32 import java.util.Arrays;
33 import java.util.List;
34
35 import org.openimaj.math.geometry.point.Point2d;
36
37 /**
38 * Implementation of the scan-line rasterisation algorithm for filling polygons.
39 *
40 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
41 */
42 public class ScanRasteriser {
43 /**
44 * Listen for scans.
45 *
46 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
47 */
48 public static interface ScanLineListener {
49 /**
50 * Process the given scan
51 *
52 * @param x1
53 * starting x (inclusive)
54 * @param x2
55 * ending x (inclusive)
56 * @param y
57 * the y ordinate
58 */
59 public abstract void process(int x1, int x2, int y);
60 }
61
62 private ScanRasteriser() {
63 // not instantiable
64 }
65
66 /**
67 * The scan-fill algorithm. Scans are reported via the
68 * {@link ScanLineListener}.
69 *
70 * @param p
71 * the connected points to rasterise
72 * @param listener
73 * the {@link ScanLineListener}
74 */
75 public static void scanFill(List<Point2d> p, ScanLineListener listener) {
76 int nScans;
77
78 final int n = p.size();
79 int miny = Integer.MAX_VALUE;
80 int maxy = Integer.MIN_VALUE;
81 for (int i = 0; i < n; i++) {
82 final Point2d pt = p.get(i);
83
84 miny = Math.min(miny, Math.round(pt.getY()));
85 maxy = Math.max(maxy, Math.round(pt.getY()));
86 }
87
88 final float[] scans = new float[n];
89
90 for (int y = miny; y <= maxy; y++) {
91 nScans = 0;
92
93 for (int i = 0; i < n; i++) {
94 final int index1, index2;
95 if (i == 0) {
96 index1 = n - 1;
97 index2 = 0;
98 } else {
99 index1 = i - 1;
100 index2 = i;
101 }
102
103 final Point2d p1 = p.get(index1);
104 final Point2d p2 = p.get(index2);
105
106 float y1 = p1.getY();
107 float y2 = p2.getY();
108
109 float x1, x2;
110 if (y1 < y2) {
111 x1 = p1.getX();
112 x2 = p2.getX();
113 } else if (y1 > y2) {
114 y2 = p1.getY();
115 y1 = p2.getY();
116 x2 = p1.getX();
117 x1 = p2.getX();
118 } else {
119 continue;
120 }
121
122 if ((y >= y1) && (y < y2)) {
123 scans[nScans++] = (y - y1) * (x2 - x1) / (y2 - y1) + x1;
124 } else if ((y == maxy) && (y > y1) && (y <= y2)) {
125 scans[nScans++] = (y - y1) * (x2 - x1) / (y2 - y1) + x1;
126 }
127 }
128
129 Arrays.sort(scans, 0, nScans);
130
131 for (int i = 0; i < nScans; i += 2) {
132 if (i + 1 < nScans)
133 listener.process(Math.round(scans[i]), Math.round(scans[i + 1]), y);
134 }
135 }
136 }
137 }