aboutsummaryrefslogtreecommitdiff
path: root/engines/sword25/math/region.cpp
blob: 7681ef6d9f38b58548cd407540d035f10e781d41 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.

 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 */

/*
 * This code is based on Broken Sword 2.5 engine
 *
 * Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsdoerfer
 *
 * Licensed under GNU GPL v2
 *
 */

#include "sword25/kernel/inputpersistenceblock.h"
#include "sword25/kernel/outputpersistenceblock.h"

#include "sword25/math/region.h"
#include "sword25/math/walkregion.h"
#include "sword25/math/regionregistry.h"

namespace Sword25 {

Region::Region() : _valid(false), _type(RT_REGION) {
	RegionRegistry::instance().registerObject(this);
}

Region::Region(InputPersistenceBlock &reader, uint handle) : _valid(false), _type(RT_REGION) {
	RegionRegistry::instance().registerObject(this, handle);
	unpersist(reader);
}

uint Region::create(REGION_TYPE type) {
	Region *regionPtr = NULL;
	switch (type) {
	case RT_REGION:
		regionPtr = new Region();
		break;

	case RT_WALKREGION:
		regionPtr = new WalkRegion();
		break;

	default:
		assert(true);
	}

	return RegionRegistry::instance().resolvePtr(regionPtr);
}

uint Region::create(InputPersistenceBlock &reader, uint handle) {
	// Read type
	uint type;
	reader.read(type);

	// Depending on the type, create a new BS_Region or BS_WalkRegion object
	Region *regionPtr = NULL;
	if (type == RT_REGION) {
		regionPtr = new Region(reader, handle);
	} else if (type == RT_WALKREGION) {
		regionPtr = new WalkRegion(reader, handle);
	} else {
		assert(false);
	}

	return RegionRegistry::instance().resolvePtr(regionPtr);
}

Region::~Region() {
	RegionRegistry::instance().deregisterObject(this);
}

bool Region::init(const Polygon &contour, const Common::Array<Polygon> *pHoles) {
	// Reset object state
	_valid = false;
	_position = Vertex(0, 0);
	_polygons.clear();

	// Reserve sufficient  space for countour and holes in the polygon list
	if (pHoles)
		_polygons.reserve(1 + pHoles->size());
	else
		_polygons.reserve(1);

	// The first polygon will be the contour
	_polygons.push_back(Polygon());
	_polygons[0].init(contour.vertexCount, contour.vertices);
	// Make sure that the Vertecies in the Contour are arranged in a clockwise direction
	_polygons[0].ensureCWOrder();

	// Place the hole polygons in the following positions
	if (pHoles) {
		for (uint i = 0; i < pHoles->size(); ++i) {
			_polygons.push_back(Polygon());
			_polygons[i + 1].init((*pHoles)[i].vertexCount, (*pHoles)[i].vertices);
			_polygons[i + 1].ensureCWOrder();
		}
	}


	// Initialize bounding box
	updateBoundingBox();

	_valid = true;
	return true;
}

void Region::updateBoundingBox() {
	if (_polygons[0].vertexCount) {
		int minX = _polygons[0].vertices[0].x;
		int maxX = _polygons[0].vertices[0].x;
		int minY = _polygons[0].vertices[0].y;
		int maxY = _polygons[0].vertices[0].y;

		for (int i = 1; i < _polygons[0].vertexCount; i++) {
			if (_polygons[0].vertices[i].x < minX) minX = _polygons[0].vertices[i].x;
			else if (_polygons[0].vertices[i].x > maxX) maxX = _polygons[0].vertices[i].x;
			if (_polygons[0].vertices[i].y < minY) minY = _polygons[0].vertices[i].y;
			else if (_polygons[0].vertices[i].y > maxY) maxY = _polygons[0].vertices[i].y;
		}

		_boundingBox = Common::Rect(minX, minY, maxX + 1, maxY + 1);
	}
}

// Position Changes
void Region::setPos(int x, int y) {
	// Calculate the difference between the old and new position
	Vertex delta(x - _position.x, y - _position.y);

	// Save the new position
	_position = Vertex(x, y);

	// Move all the vertecies
	for (uint i = 0; i < _polygons.size(); ++i) {
		_polygons[i] += delta;
	}

	// Update the bounding box
	updateBoundingBox();
}

void Region::setPosX(int x) {
	setPos(x, _position.y);
}

void Region::setPosY(int y) {
	setPos(_position.x, y);
}

// Point-Region Tests
bool Region::isPointInRegion(int x, int y) const {
	// Test whether the point is in the bounding box
	if (_boundingBox.contains(x, y)) {
		// Test whether the point is in the contour
		if (_polygons[0].isPointInPolygon(x, y, true)) {
			// Test whether the point is in a hole
			for (uint i = 1; i < _polygons.size(); i++) {
				if (_polygons[i].isPointInPolygon(x, y, false))
					return false;
			}

			return true;
		}
	}

	return false;
}

bool Region::isPointInRegion(const Vertex &vertex) const {
	return isPointInRegion(vertex.x, vertex.y);
}

Vertex Region::findClosestRegionPoint(const Vertex &point) const {
	// Determine whether the point is inside a hole. If that is the case, the closest
	// point on the edge of the hole is determined
	int polygonIdx = 0;
	{
		for (uint i = 1; i < _polygons.size(); ++i) {
			if (_polygons[i].isPointInPolygon(point)) {
				polygonIdx = i;
				break;
			}
		}
	}

	const Polygon &polygon = _polygons[polygonIdx];

	assert(polygon.vertexCount > 1);

	// For each line of the polygon, calculate the point that is cloest to the given point
	// The point of this set with the smallest distance to the given point is the result.
	Vertex closestVertex = findClosestPointOnLine(polygon.vertices[0], polygon.vertices[1], point);
	int closestVertexDistance2 = closestVertex.distance(point);
	for (int i = 1; i < polygon.vertexCount; ++i) {
		int j = (i + 1) % polygon.vertexCount;

		Vertex curVertex = findClosestPointOnLine(polygon.vertices[i], polygon.vertices[j], point);
		if (curVertex.distance(point) < closestVertexDistance2) {
			closestVertex = curVertex;
			closestVertexDistance2 = curVertex.distance(point);
		}
	}

	// Determine whether the point is really within the region. This must not be so, as a result of rounding
	// errors can occur at the edge of polygons
	if (isPointInRegion(closestVertex))
		return closestVertex;
	else {
		// Try to construct a point within the region - 8 points are tested in the immediate vacinity
		// of the point
		if (isPointInRegion(closestVertex + Vertex(-2, -2)))
			return closestVertex + Vertex(-2, -2);
		else if (isPointInRegion(closestVertex + Vertex(0, -2)))
			return closestVertex + Vertex(0, -2);
		else if (isPointInRegion(closestVertex + Vertex(2, -2)))
			return closestVertex + Vertex(2, -2);
		else if (isPointInRegion(closestVertex + Vertex(-2, 0)))
			return closestVertex + Vertex(-2, 0);
		else if (isPointInRegion(closestVertex + Vertex(0, 2)))
			return closestVertex + Vertex(0, 2);
		else if (isPointInRegion(closestVertex + Vertex(-2, 2)))
			return closestVertex + Vertex(-2, 2);
		else if (isPointInRegion(closestVertex + Vertex(-2, 0)))
			return closestVertex + Vertex(2, 2);
		else if (isPointInRegion(closestVertex + Vertex(2, 2)))
			return closestVertex + Vertex(2, 2);

		// If no point could be found that way that lies within the region, find the next point
		closestVertex = polygon.vertices[0];
		int shortestVertexDistance2 = polygon.vertices[0].sqrDist(point);
		{
			for (int i = 1; i < polygon.vertexCount; i++) {
				int curDistance2 = polygon.vertices[i].sqrDist(point);
				if (curDistance2 < shortestVertexDistance2) {
					closestVertex = polygon.vertices[i];
					shortestVertexDistance2 = curDistance2;
				}
			}
		}

		warning("Clostest vertex forced because edgepoint was outside region.");
		return closestVertex;
	}
}

Vertex Region::findClosestPointOnLine(const Vertex &lineStart, const Vertex &lineEnd, const Vertex point) const {
	float vector1X = static_cast<float>(point.x - lineStart.x);
	float vector1Y = static_cast<float>(point.y - lineStart.y);
	float vector2X = static_cast<float>(lineEnd.x - lineStart.x);
	float vector2Y = static_cast<float>(lineEnd.y - lineStart.y);
	float vector2Length = sqrtf(vector2X * vector2X + vector2Y * vector2Y);
	vector2X /= vector2Length;
	vector2Y /= vector2Length;
	float distance = sqrtf(static_cast<float>((lineStart.x - lineEnd.x) * (lineStart.x - lineEnd.x) +
	                       (lineStart.y - lineEnd.y) * (lineStart.y - lineEnd.y)));
	float dot = vector1X * vector2X + vector1Y * vector2Y;

	if (dot <= 0)
		return lineStart;
	if (dot >= distance)
		return lineEnd;

	Vertex vector3(static_cast<int>(vector2X * dot + 0.5f), static_cast<int>(vector2Y * dot + 0.5f));
	return lineStart + vector3;
}

// Line of Sight
bool Region::isLineOfSight(const Vertex &a, const Vertex &b) const {
	assert(_polygons.size());

	// The line must be within the contour polygon, and outside of any hole polygons
	Common::Array<Polygon>::const_iterator iter = _polygons.begin();
	if (!(*iter).isLineInterior(a, b)) return false;
	for (iter++; iter != _polygons.end(); iter++)
		if (!(*iter).isLineExterior(a, b)) return false;

	return true;
}

// Persistence
bool Region::persist(OutputPersistenceBlock &writer) {
	bool Result = true;

	writer.write(static_cast<uint>(_type));
	writer.write(_valid);
	writer.write(_position.x);
	writer.write(_position.y);

	writer.write(_polygons.size());
	Common::Array<Polygon>::iterator It = _polygons.begin();
	while (It != _polygons.end()) {
		Result &= It->persist(writer);
		++It;
	}

	writer.write(_boundingBox.left);
	writer.write(_boundingBox.top);
	writer.write(_boundingBox.right);
	writer.write(_boundingBox.bottom);

	return Result;
}

bool Region::unpersist(InputPersistenceBlock &reader) {
	reader.read(_valid);
	reader.read(_position.x);
	reader.read(_position.y);

	_polygons.clear();
	uint PolygonCount;
	reader.read(PolygonCount);
	for (uint i = 0; i < PolygonCount; ++i) {
		_polygons.push_back(Polygon(reader));
	}

	reader.read(_boundingBox.left);
	reader.read(_boundingBox.top);
	reader.read(_boundingBox.right);
	reader.read(_boundingBox.bottom);

	return reader.isGood();
}

Vertex Region::getCentroid() const {
	if (_polygons.size() > 0)
		return _polygons[0].getCentroid();
	return
	    Vertex();
}

} // End of namespace Sword25