source: OniSplit/Akira/RoomGridRasterizer.cs@ 1124

Last change on this file since 1124 was 1114, checked in by iritscen, 5 years ago

Adding OniSplit source code (v0.9.99.0). Many thanks to Neo for all his work over the years.
File size: 14.2 KB
Line 
1using System;
2using System.IO;
3using System.Collections.Generic;
4using Oni.Imaging;
5
6namespace 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}
Note: See TracBrowser for help on using the repository browser.