OniSplit/Akira/RoomGridRasterizer.cs

using System;
using System.IO;
using System.Collections.Generic;
using Oni.Imaging;

namespace Oni.Akira
{
    internal class RoomGridRasterizer
    {
        private const int origin = -2;
        private const float tileSize = 4.0f;
        private const int margin = 3;
        private readonly int xTiles;
        private readonly int zTiles;
        private readonly byte[] data;
        private readonly Vector3 worldOrigin;
        //private readonly List<RoomGridDebugData> debugData;

        private enum RoomGridDebugType : byte
        {
            None,
            SlopedQuad,
            StairQuad,
            Wall,
            DangerQuad,
            ImpassableQuad,
            Floor
        }

        //private class RoomGridDebugData
        //{
        //    public int quadIndex;
        //    public RoomGridDebugType type;
        //    public RoomGridWeight weight;
        //    public short x, y;
        //}

        public RoomGridRasterizer(BoundingBox bbox)
        {
            this.xTiles = (int)(((bbox.Max.X - bbox.Min.X) / tileSize) + (-origin * 2) + 1) + margin * 2;
            this.zTiles = (int)(((bbox.Max.Z - bbox.Min.Z) / tileSize) + (-origin * 2) + 1) + margin * 2;
            this.data = new byte[xTiles * zTiles];
            this.worldOrigin = bbox.Min;
            //this.debugData = new List<RoomGridDebugData>();
        }

        public void Clear(RoomGridWeight weight)
        {
            for (int i = 0; i < xTiles * zTiles; i++)
                data[i] = (byte)weight;
        }

        public int XTiles => xTiles;
        public int ZTiles => ZTiles;

        public float TileSize => tileSize;

        public RoomGridWeight this[int x, int z]
        {
            get { return (RoomGridWeight)data[x + z * xTiles]; }
            set { data[x + z * xTiles] = (byte)value; }
        }

        public void DrawFloor(IEnumerable<Vector3> points)
        {
            foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
                this[point.X, point.Y] = RoomGridWeight.Clear;
        }

        public void DrawDanger(IEnumerable<Vector3> points)
        {
            foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
                this[point.X, point.Y] = RoomGridWeight.Danger;
        }

        public void DrawStairsEntry(IEnumerable<Vector3> points)
        {
            var v0 = points.First();
            var v1 = v0;

            foreach (var v in points)
            {
                if (v.X < v0.X || (v.X == v0.X && v.Z < v0.Z))
                    v0 = v;

                if (v.X > v1.X || (v.X == v1.X && v.Z > v1.Z))
                    v1 = v;
            }

            Point p0 = WorldToGrid(v0);
            Point p1 = WorldToGrid(v1);

            DrawLine(p0, p1, RoomGridWeight.Stairs);

            DrawLine(p0 - Point.UnitY, p1 - Point.UnitY, RoomGridWeight.Clear);
            DrawLine(p0 + Point.UnitY, p1 + Point.UnitY, RoomGridWeight.Clear);
            DrawLine(p0 + Point.UnitX, p1 + Point.UnitX, RoomGridWeight.Clear);
            DrawLine(p0 - Point.UnitX, p1 - Point.UnitX, RoomGridWeight.Clear);

            var pp = points.ToArray();
            Array.Sort(pp, (x, y) => x.Y.CompareTo(y.Y));
            DrawImpassable(pp[0]);
            DrawImpassable(pp[1]);
        }

        public void DrawWall(IEnumerable<Vector3> points)
        {
            var v0 = points.First();
            var v1 = v0;

            foreach (var v in points)
            {
                if (v.X < v0.X || (v.X == v0.X && v.Z < v0.Z))
                    v0 = v;

                if (v.X > v1.X || (v.X == v1.X && v.Z > v1.Z))
                    v1 = v;
            }

            Point p0 = WorldToGrid(v0);
            Point p1 = WorldToGrid(v1);

            DrawLine(p0, p1, RoomGridWeight.Impassable);

            DrawLine(p0 - Point.UnitY, p1 - Point.UnitY, RoomGridWeight.SemiPassable);
            DrawLine(p0 + Point.UnitY, p1 + Point.UnitY, RoomGridWeight.SemiPassable);
            DrawLine(p0 + Point.UnitX, p1 + Point.UnitX, RoomGridWeight.SemiPassable);
            DrawLine(p0 - Point.UnitX, p1 - Point.UnitX, RoomGridWeight.SemiPassable);
        }

        private void DrawLine(Point p0, Point p1, RoomGridWeight weight)
        {
            foreach (Point p in ScanLine(p0, p1))
            {
                if (weight > this[p.X, p.Y])
                {
                    this[p.X, p.Y] = weight;

                    //debugData.Add(new RoomGridDebugData {
                    //    x = (short)p.X,
                    //    y = (short)p.Y,
                    //    weight = weight
                    //});
                }
            }
        }

        private void FillPolygon(IEnumerable<Vector3> points, RoomGridWeight weight)
        {
            foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
            {
                if (weight > this[point.X, point.Y])
                    this[point.X, point.Y] = weight;
            }
        }

        public void DrawImpassable(IEnumerable<Vector3> points)
        {
            FillPolygon(points, RoomGridWeight.Impassable);
        }

        public void DrawImpassable(Vector3 position)
        {
            var point = WorldToGrid(position);
            int x = point.X;
            int y = point.Y;

            DrawTile(x, y, RoomGridWeight.Impassable);

            DrawTile(x - 1, y, RoomGridWeight.SemiPassable);
            DrawTile(x + 1, y, RoomGridWeight.SemiPassable);
            DrawTile(x, y - 1, RoomGridWeight.SemiPassable);
            DrawTile(x, y + 1, RoomGridWeight.SemiPassable);
            DrawTile(x - 1, y - 1, RoomGridWeight.SemiPassable);
            DrawTile(x + 1, y - 1, RoomGridWeight.SemiPassable);
            DrawTile(x + 1, y + 1, RoomGridWeight.SemiPassable);
            DrawTile(x - 1, y + 1, RoomGridWeight.SemiPassable);
        }

        private void DrawTile(int x, int y, RoomGridWeight weight)
        {
            if (0 <= x && x < xTiles && 0 <= y && y < zTiles)
            {
                if (weight > this[x, y])
                    this[x, y] = weight;
            }
        }

        public void AddBorders()
        {
            AddBorder(RoomGridWeight.Danger, RoomGridWeight.Clear, RoomGridWeight.Border4);
            AddBorder(RoomGridWeight.Border4, RoomGridWeight.Clear, RoomGridWeight.Border3);
            AddBorder(RoomGridWeight.Border3, RoomGridWeight.Clear, RoomGridWeight.Border2);
            AddBorder(RoomGridWeight.Border2, RoomGridWeight.Clear, RoomGridWeight.Border1);
            AddBorder(RoomGridWeight.SemiPassable, RoomGridWeight.Clear, RoomGridWeight.NearWall);
        }

        private void AddBorder(RoomGridWeight aroundOf, RoomGridWeight onlyIf, RoomGridWeight border)
        {
            for (int z = 0; z < zTiles; z++)
            {
                for (int x = 0; x < xTiles; x++)
                {
                    if (this[x, z] != aroundOf)
                        continue;

                    if (x - 1 >= 0 && this[x - 1, z] == onlyIf)
                        this[x - 1, z] = border;

                    if (x + 1 < xTiles && this[x + 1, z] == onlyIf)
                        this[x + 1, z] = border;

                    if (z - 1 >= 0 && this[x, z - 1] == onlyIf)
                        this[x, z - 1] = border;

                    if (z + 1 < zTiles && this[x, z + 1] == onlyIf)
                        this[x, z + 1] = border;
                }
            }
        }

        private Point WorldToGrid(Vector3 world)
        {
            return new Point(
                FMath.TruncateToInt32((world.X - worldOrigin.X) / tileSize) - origin + margin,
                FMath.TruncateToInt32((world.Z - worldOrigin.Z) / tileSize) - origin + margin);
        }

        public RoomGrid GetGrid()
        {
            int gridXTiles = xTiles - 2 * margin;
            int gridZTiles = zTiles - 2 * margin;

            var gridData = new byte[gridXTiles * gridZTiles];

            for (int z = margin; z < zTiles - margin; z++)
            {
                for (int x = margin; x < xTiles - margin; x++)
                    gridData[(x - margin) + (z - margin) * gridXTiles] = data[x + z * xTiles];
            }

            //var debugStream = new MemoryStream(debugData.Count * 16);

            //using (var writer = new BinaryWriter(debugStream))
            //{
            //    foreach (var data in debugData)
            //    {
            //        writer.WriteByte((byte)data.type);
            //        writer.WriteByte(0);
            //        writer.Write(data.x);
            //        writer.Write(data.y);
            //        writer.WriteInt16(0);
            //        writer.Write(data.quadIndex);
            //        writer.Write((int)data.weight);
            //    }
            //}

            return new RoomGrid(gridXTiles, gridZTiles, gridData, null);
        }

        private IEnumerable<Point> ScanLine(Point p0, Point p1)
        {
            return ScanLine(p0.X, p0.Y, p1.X, p1.Y);
        }

        private IEnumerable<Point> ScanLine(int x0, int y0, int x1, int y1)
        {
            int dx = (x0 < x1) ? x1 - x0 : x0 - x1;
            int dy = (y0 < y1) ? y1 - y0 : y0 - y1;
            int sx = (x0 < x1) ? 1 : -1;
            int sy = (y0 < y1) ? 1 : -1;
            int err = dx - dy;

            while (true)
            {
                if (0 <= x0 && x0 < xTiles && 0 <= y0 && y0 < zTiles)
                    yield return new Point(x0, y0);

                if (x0 == x1 && y0 == y1)
                    break;

                int derr = 2 * err;

                if (derr > -dy)
                {
                    err = err - dy;
                    x0 = x0 + sx;
                }

                if (derr < dx)
                {
                    err = err + dx;
                    y0 = y0 + sy;
                }
            }
        }

        private IEnumerable<Vector2> ScanLine(Vector2 p0, Vector2 p1)
        {
            return ScanLine(p0.X, p0.Y, p1.X, p1.Y);
        }

        private IEnumerable<Vector2> ScanLine(float x0, float y0, float x1, float y1)
        {
            float dx = (x0 < x1) ? x1 - x0 : x0 - x1;
            float dy = (y0 < y1) ? y1 - y0 : y0 - y1;
            float sx = (x0 < x1) ? 1 : -1;
            float sy = (y0 < y1) ? 1 : -1;
            float err = dx - dy;

            while (true)
            {
                if (0 <= x0 && x0 < xTiles && 0 <= y0 && y0 < zTiles)
                    yield return new Vector2(x0, y0);

                if (x0 == x1 && y0 == y1)
                    break;

                float derr = 2 * err;

                if (derr > -dy)
                {
                    err = err - dy;
                    x0 = x0 + sx;
                }

                if (derr < dx)
                {
                    err = err + dx;
                    y0 = y0 + sy;
                }
            }
        }

        private IEnumerable<Point> ScanPolygon(IList<Point> points)
        {
            var activeEdgeList = new List<Edge>();
            var activeEdgeTable = new List<List<Edge>>();
            int minY = BuildActiveEdgeTable(points, activeEdgeTable);

            for (int y = 0; y < activeEdgeTable.Count; y++)
            {
                for (int i = 0; i < activeEdgeTable[y].Count; i++)
                    activeEdgeList.Add(activeEdgeTable[y][i]);

                for (int i = 0; i < activeEdgeList.Count; i++)
                {
                    if (activeEdgeList[i].maxY <= y + minY)
                    {
                        activeEdgeList.RemoveAt(i);
                        i--;
                    }
                }

                activeEdgeList.Sort((a, b) => (a.currentX == b.currentX ? a.slopeRecip.CompareTo(b.slopeRecip) : a.currentX.CompareTo(b.currentX)));

                for (int i = 0; i < activeEdgeList.Count; i += 2)
                {
                    int yLine = minY + y;

                    if (0 <= yLine && yLine < zTiles)
                    {
                        int xStart = Math.Max(0, (int)Math.Ceiling(activeEdgeList[i].currentX));
                        int xEnd = Math.Min(xTiles - 1, (int)activeEdgeList[i + 1].currentX);

                        for (int x = xStart; x <= xEnd; x++)
                            yield return new Point(x, yLine);
                    }
                }

                for (int i = 0; i < activeEdgeList.Count; i++)
                    activeEdgeList[i].Next();
            }
        }

        private class Edge
        {
            public float maxY;
            public float currentX;
            public float slopeRecip;

            public Edge(Point current, Point next)
            {
                maxY = Math.Max(current.Y, next.Y);
                slopeRecip = (current.X - next.X) / (float)(current.Y - next.Y);

                if (current.Y == maxY)
                    currentX = next.X;
                else
                    currentX = current.X;
            }

            public void Next()
            {
                currentX += slopeRecip;
            }
        }

        private static int BuildActiveEdgeTable(IList<Point> points, List<List<Edge>> activeEdgeTable)
        {
            activeEdgeTable.Clear();

            int minY = points.Min(p => p.Y);
            int maxY = points.Max(p => p.Y);

            for (int i = minY; i <= maxY; i++)
                activeEdgeTable.Add(new List<Edge>());

            for (int i = 0; i < points.Count; i++)
            {
                Point current = points[i];
                Point next = points[(i + 1) % points.Count];

                if (current.Y == next.Y)
                    continue;

                var e = new Edge(current, next);

                if (current.Y == e.maxY)
                    activeEdgeTable[next.Y - minY].Add(e);
                else
                    activeEdgeTable[current.Y - minY].Add(e);
            }

            return minY;
        }
    }
}
Revision:	1114
Committed:	Wed Jan 22 14:08:57 2020 UTC (5 years, 9 months ago) by iritscen
File size:	14552 byte(s)
Log Message:	Adding OniSplit source code (v0.9.99.0). Many thanks to Neo for all his work over the years.
#	Content
1	using System;
2	using System.IO;
3	using System.Collections.Generic;
4	using Oni.Imaging;
5
6	namespace Oni.Akira
7	{
8	internal class RoomGridRasterizer
9	{
10	private const int origin = -2;
11	private const float tileSize = 4.0f;
12	private const int margin = 3;
13	private readonly int xTiles;
14	private readonly int zTiles;
15	private readonly byte[] data;
16	private readonly Vector3 worldOrigin;
17	//private readonly List<RoomGridDebugData> debugData;
18
19	private enum RoomGridDebugType : byte
20	{
21	None,
22	SlopedQuad,
23	StairQuad,
24	Wall,
25	DangerQuad,
26	ImpassableQuad,
27	Floor
28	}
29
30	//private class RoomGridDebugData
31	//{
32	// public int quadIndex;
33	// public RoomGridDebugType type;
34	// public RoomGridWeight weight;
35	// public short x, y;
36	//}
37
38	public RoomGridRasterizer(BoundingBox bbox)
39	{
40	this.xTiles = (int)(((bbox.Max.X - bbox.Min.X) / tileSize) + (-origin * 2) + 1) + margin * 2;
41	this.zTiles = (int)(((bbox.Max.Z - bbox.Min.Z) / tileSize) + (-origin * 2) + 1) + margin * 2;
42	this.data = new byte[xTiles * zTiles];
43	this.worldOrigin = bbox.Min;
44	//this.debugData = new List<RoomGridDebugData>();
45	}
46
47	public void Clear(RoomGridWeight weight)
48	{
49	for (int i = 0; i < xTiles * zTiles; i++)
50	data[i] = (byte)weight;
51	}
52
53	public int XTiles => xTiles;
54	public int ZTiles => ZTiles;
55
56	public float TileSize => tileSize;
57
58	public RoomGridWeight this[int x, int z]
59	{
60	get { return (RoomGridWeight)data[x + z * xTiles]; }
61	set { data[x + z * xTiles] = (byte)value; }
62	}
63
64	public void DrawFloor(IEnumerable<Vector3> points)
65	{
66	foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
67	this[point.X, point.Y] = RoomGridWeight.Clear;
68	}
69
70	public void DrawDanger(IEnumerable<Vector3> points)
71	{
72	foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
73	this[point.X, point.Y] = RoomGridWeight.Danger;
74	}
75
76	public void DrawStairsEntry(IEnumerable<Vector3> points)
77	{
78	var v0 = points.First();
79	var v1 = v0;
80
81	foreach (var v in points)
82	{
83	if (v.X < v0.X \|\| (v.X == v0.X && v.Z < v0.Z))
84	v0 = v;
85
86	if (v.X > v1.X \|\| (v.X == v1.X && v.Z > v1.Z))
87	v1 = v;
88	}
89
90	Point p0 = WorldToGrid(v0);
91	Point p1 = WorldToGrid(v1);
92
93	DrawLine(p0, p1, RoomGridWeight.Stairs);
94
95	DrawLine(p0 - Point.UnitY, p1 - Point.UnitY, RoomGridWeight.Clear);
96	DrawLine(p0 + Point.UnitY, p1 + Point.UnitY, RoomGridWeight.Clear);
97	DrawLine(p0 + Point.UnitX, p1 + Point.UnitX, RoomGridWeight.Clear);
98	DrawLine(p0 - Point.UnitX, p1 - Point.UnitX, RoomGridWeight.Clear);
99
100	var pp = points.ToArray();
101	Array.Sort(pp, (x, y) => x.Y.CompareTo(y.Y));
102	DrawImpassable(pp[0]);
103	DrawImpassable(pp[1]);
104	}
105
106	public void DrawWall(IEnumerable<Vector3> points)
107	{
108	var v0 = points.First();
109	var v1 = v0;
110
111	foreach (var v in points)
112	{
113	if (v.X < v0.X \|\| (v.X == v0.X && v.Z < v0.Z))
114	v0 = v;
115
116	if (v.X > v1.X \|\| (v.X == v1.X && v.Z > v1.Z))
117	v1 = v;
118	}
119
120	Point p0 = WorldToGrid(v0);
121	Point p1 = WorldToGrid(v1);
122
123	DrawLine(p0, p1, RoomGridWeight.Impassable);
124
125	DrawLine(p0 - Point.UnitY, p1 - Point.UnitY, RoomGridWeight.SemiPassable);
126	DrawLine(p0 + Point.UnitY, p1 + Point.UnitY, RoomGridWeight.SemiPassable);
127	DrawLine(p0 + Point.UnitX, p1 + Point.UnitX, RoomGridWeight.SemiPassable);
128	DrawLine(p0 - Point.UnitX, p1 - Point.UnitX, RoomGridWeight.SemiPassable);
129	}
130
131	private void DrawLine(Point p0, Point p1, RoomGridWeight weight)
132	{
133	foreach (Point p in ScanLine(p0, p1))
134	{
135	if (weight > this[p.X, p.Y])
136	{
137	this[p.X, p.Y] = weight;
138
139	//debugData.Add(new RoomGridDebugData {
140	// x = (short)p.X,
141	// y = (short)p.Y,
142	// weight = weight
143	//});
144	}
145	}
146	}
147
148	private void FillPolygon(IEnumerable<Vector3> points, RoomGridWeight weight)
149	{
150	foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
151	{
152	if (weight > this[point.X, point.Y])
153	this[point.X, point.Y] = weight;
154	}
155	}
156
157	public void DrawImpassable(IEnumerable<Vector3> points)
158	{
159	FillPolygon(points, RoomGridWeight.Impassable);
160	}
161
162	public void DrawImpassable(Vector3 position)
163	{
164	var point = WorldToGrid(position);
165	int x = point.X;
166	int y = point.Y;
167
168	DrawTile(x, y, RoomGridWeight.Impassable);
169
170	DrawTile(x - 1, y, RoomGridWeight.SemiPassable);
171	DrawTile(x + 1, y, RoomGridWeight.SemiPassable);
172	DrawTile(x, y - 1, RoomGridWeight.SemiPassable);
173	DrawTile(x, y + 1, RoomGridWeight.SemiPassable);
174	DrawTile(x - 1, y - 1, RoomGridWeight.SemiPassable);
175	DrawTile(x + 1, y - 1, RoomGridWeight.SemiPassable);
176	DrawTile(x + 1, y + 1, RoomGridWeight.SemiPassable);
177	DrawTile(x - 1, y + 1, RoomGridWeight.SemiPassable);
178	}
179
180	private void DrawTile(int x, int y, RoomGridWeight weight)
181	{
182	if (0 <= x && x < xTiles && 0 <= y && y < zTiles)
183	{
184	if (weight > this[x, y])
185	this[x, y] = weight;
186	}
187	}
188
189	public void AddBorders()
190	{
191	AddBorder(RoomGridWeight.Danger, RoomGridWeight.Clear, RoomGridWeight.Border4);
192	AddBorder(RoomGridWeight.Border4, RoomGridWeight.Clear, RoomGridWeight.Border3);
193	AddBorder(RoomGridWeight.Border3, RoomGridWeight.Clear, RoomGridWeight.Border2);
194	AddBorder(RoomGridWeight.Border2, RoomGridWeight.Clear, RoomGridWeight.Border1);
195	AddBorder(RoomGridWeight.SemiPassable, RoomGridWeight.Clear, RoomGridWeight.NearWall);
196	}
197
198	private void AddBorder(RoomGridWeight aroundOf, RoomGridWeight onlyIf, RoomGridWeight border)
199	{
200	for (int z = 0; z < zTiles; z++)
201	{
202	for (int x = 0; x < xTiles; x++)
203	{
204	if (this[x, z] != aroundOf)
205	continue;
206
207	if (x - 1 >= 0 && this[x - 1, z] == onlyIf)
208	this[x - 1, z] = border;
209
210	if (x + 1 < xTiles && this[x + 1, z] == onlyIf)
211	this[x + 1, z] = border;
212
213	if (z - 1 >= 0 && this[x, z - 1] == onlyIf)
214	this[x, z - 1] = border;
215
216	if (z + 1 < zTiles && this[x, z + 1] == onlyIf)
217	this[x, z + 1] = border;
218	}
219	}
220	}
221
222	private Point WorldToGrid(Vector3 world)
223	{
224	return new Point(
225	FMath.TruncateToInt32((world.X - worldOrigin.X) / tileSize) - origin + margin,
226	FMath.TruncateToInt32((world.Z - worldOrigin.Z) / tileSize) - origin + margin);
227	}
228
229	public RoomGrid GetGrid()
230	{
231	int gridXTiles = xTiles - 2 * margin;
232	int gridZTiles = zTiles - 2 * margin;
233
234	var gridData = new byte[gridXTiles * gridZTiles];
235
236	for (int z = margin; z < zTiles - margin; z++)
237	{
238	for (int x = margin; x < xTiles - margin; x++)
239	gridData[(x - margin) + (z - margin) * gridXTiles] = data[x + z * xTiles];
240	}
241
242	//var debugStream = new MemoryStream(debugData.Count * 16);
243
244	//using (var writer = new BinaryWriter(debugStream))
245	//{
246	// foreach (var data in debugData)
247	// {
248	// writer.WriteByte((byte)data.type);
249	// writer.WriteByte(0);
250	// writer.Write(data.x);
251	// writer.Write(data.y);
252	// writer.WriteInt16(0);
253	// writer.Write(data.quadIndex);
254	// writer.Write((int)data.weight);
255	// }
256	//}
257
258	return new RoomGrid(gridXTiles, gridZTiles, gridData, null);
259	}
260
261	private IEnumerable<Point> ScanLine(Point p0, Point p1)
262	{
263	return ScanLine(p0.X, p0.Y, p1.X, p1.Y);
264	}
265
266	private IEnumerable<Point> ScanLine(int x0, int y0, int x1, int y1)
267	{
268	int dx = (x0 < x1) ? x1 - x0 : x0 - x1;
269	int dy = (y0 < y1) ? y1 - y0 : y0 - y1;
270	int sx = (x0 < x1) ? 1 : -1;
271	int sy = (y0 < y1) ? 1 : -1;
272	int err = dx - dy;
273
274	while (true)
275	{
276	if (0 <= x0 && x0 < xTiles && 0 <= y0 && y0 < zTiles)
277	yield return new Point(x0, y0);
278
279	if (x0 == x1 && y0 == y1)
280	break;
281
282	int derr = 2 * err;
283
284	if (derr > -dy)
285	{
286	err = err - dy;
287	x0 = x0 + sx;
288	}
289
290	if (derr < dx)
291	{
292	err = err + dx;
293	y0 = y0 + sy;
294	}
295	}
296	}
297
298	private IEnumerable<Vector2> ScanLine(Vector2 p0, Vector2 p1)
299	{
300	return ScanLine(p0.X, p0.Y, p1.X, p1.Y);
301	}
302
303	private IEnumerable<Vector2> ScanLine(float x0, float y0, float x1, float y1)
304	{
305	float dx = (x0 < x1) ? x1 - x0 : x0 - x1;
306	float dy = (y0 < y1) ? y1 - y0 : y0 - y1;
307	float sx = (x0 < x1) ? 1 : -1;
308	float sy = (y0 < y1) ? 1 : -1;
309	float err = dx - dy;
310
311	while (true)
312	{
313	if (0 <= x0 && x0 < xTiles && 0 <= y0 && y0 < zTiles)
314	yield return new Vector2(x0, y0);
315
316	if (x0 == x1 && y0 == y1)
317	break;
318
319	float derr = 2 * err;
320
321	if (derr > -dy)
322	{
323	err = err - dy;
324	x0 = x0 + sx;
325	}
326
327	if (derr < dx)
328	{
329	err = err + dx;
330	y0 = y0 + sy;
331	}
332	}
333	}
334
335	private IEnumerable<Point> ScanPolygon(IList<Point> points)
336	{
337	var activeEdgeList = new List<Edge>();
338	var activeEdgeTable = new List<List<Edge>>();
339	int minY = BuildActiveEdgeTable(points, activeEdgeTable);
340
341	for (int y = 0; y < activeEdgeTable.Count; y++)
342	{
343	for (int i = 0; i < activeEdgeTable[y].Count; i++)
344	activeEdgeList.Add(activeEdgeTable[y][i]);
345
346	for (int i = 0; i < activeEdgeList.Count; i++)
347	{
348	if (activeEdgeList[i].maxY <= y + minY)
349	{
350	activeEdgeList.RemoveAt(i);
351	i--;
352	}
353	}
354
355	activeEdgeList.Sort((a, b) => (a.currentX == b.currentX ? a.slopeRecip.CompareTo(b.slopeRecip) : a.currentX.CompareTo(b.currentX)));
356
357	for (int i = 0; i < activeEdgeList.Count; i += 2)
358	{
359	int yLine = minY + y;
360
361	if (0 <= yLine && yLine < zTiles)
362	{
363	int xStart = Math.Max(0, (int)Math.Ceiling(activeEdgeList[i].currentX));
364	int xEnd = Math.Min(xTiles - 1, (int)activeEdgeList[i + 1].currentX);
365
366	for (int x = xStart; x <= xEnd; x++)
367	yield return new Point(x, yLine);
368	}
369	}
370
371	for (int i = 0; i < activeEdgeList.Count; i++)
372	activeEdgeList[i].Next();
373	}
374	}
375
376	private class Edge
377	{
378	public float maxY;
379	public float currentX;
380	public float slopeRecip;
381
382	public Edge(Point current, Point next)
383	{
384	maxY = Math.Max(current.Y, next.Y);
385	slopeRecip = (current.X - next.X) / (float)(current.Y - next.Y);
386
387	if (current.Y == maxY)
388	currentX = next.X;
389	else
390	currentX = current.X;
391	}
392
393	public void Next()
394	{
395	currentX += slopeRecip;
396	}
397	}
398
399	private static int BuildActiveEdgeTable(IList<Point> points, List<List<Edge>> activeEdgeTable)
400	{
401	activeEdgeTable.Clear();
402
403	int minY = points.Min(p => p.Y);
404	int maxY = points.Max(p => p.Y);
405
406	for (int i = minY; i <= maxY; i++)
407	activeEdgeTable.Add(new List<Edge>());
408
409	for (int i = 0; i < points.Count; i++)
410	{
411	Point current = points[i];
412	Point next = points[(i + 1) % points.Count];
413
414	if (current.Y == next.Y)
415	continue;
416
417	var e = new Edge(current, next);
418
419	if (current.Y == e.maxY)
420	activeEdgeTable[next.Y - minY].Add(e);
421	else
422	activeEdgeTable[current.Y - minY].Add(e);
423	}
424
425	return minY;
426	}
427	}
428	}