1 /* ResidualVM - A 3D game interpreter
2 *
3 * ResidualVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the AUTHORS
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "common/util.h"
24
25 #include "engines/grim/debug.h"
26 #include "engines/grim/grim.h"
27 #include "engines/grim/sector.h"
28 #include "engines/grim/textsplit.h"
29 #include "engines/grim/savegame.h"
30 #include "engines/grim/set.h"
31
32 namespace Grim {
33
Sector()34 Sector::Sector() :
35 _vertices(nullptr), _origVertices(nullptr), _sortplanes(nullptr),_invalid(false),
36 _shrinkRadius(0.f), _numVertices(0), _id(0), _numSortplanes(0),
37 _type(NoneType), _visible(false), _height(0.f) {
38 }
39
Sector(const Sector & other)40 Sector::Sector(const Sector &other) :
41 _vertices(nullptr), _origVertices(nullptr), _sortplanes(nullptr),
42 _numSortplanes(0) {
43 *this = other;
44 }
45
~Sector()46 Sector::~Sector() {
47 delete[] _vertices;
48 delete[] _origVertices;
49 delete[] _sortplanes;
50 }
51
saveState(SaveGame * savedState) const52 void Sector::saveState(SaveGame *savedState) const {
53 savedState->writeLESint32(_numVertices);
54 savedState->writeLESint32(_id);
55 savedState->writeLESint32(_type);
56 savedState->writeBool(_visible);
57 savedState->writeFloat(_height);
58
59 savedState->writeString(_name);
60
61 for (int i = 0; i < _numVertices + 1; ++i) {
62 savedState->writeVector3d(_vertices[i]);
63 }
64
65 savedState->writeVector3d(_normal);
66
67 savedState->writeFloat(_shrinkRadius);
68 savedState->writeBool(_invalid);
69 if (_shrinkRadius != 0.f && !_invalid) {
70 for (int i = 0; i < _numVertices + 1; ++i) {
71 savedState->writeVector3d(_origVertices[i]);
72 }
73 }
74
75 if (savedState->saveMinorVersion() > 8 && g_grim->getGameType() == GType_MONKEY4) {
76 savedState->writeLEUint32(_numSortplanes);
77 for (int i = 0; i < _numSortplanes; ++i) {
78 savedState->writeLEUint32(_sortplanes[i]);
79 }
80 }
81 }
82
restoreState(SaveGame * savedState)83 bool Sector::restoreState(SaveGame *savedState) {
84 _numVertices = savedState->readLESint32();
85 _id = savedState->readLESint32();
86 _type = (SectorType)savedState->readLESint32();
87 _visible = savedState->readBool();
88 _height = savedState->readFloat();
89
90 _name = savedState->readString();
91
92 _vertices = new Math::Vector3d[_numVertices + 1];
93 for (int i = 0; i < _numVertices + 1; ++i) {
94 _vertices[i] = savedState->readVector3d();
95 }
96
97 _normal = savedState->readVector3d();
98
99 _shrinkRadius = savedState->readFloat();
100 _invalid = savedState->readBool();
101 if (_shrinkRadius != 0.f && !_invalid) {
102 _origVertices = new Math::Vector3d[_numVertices + 1];
103 for (int i = 0; i < _numVertices + 1; ++i) {
104 _origVertices[i] = savedState->readVector3d();
105 }
106 } else {
107 _origVertices = nullptr;
108 }
109 if (savedState->saveMinorVersion() > 8 && g_grim->getGameType() == GType_MONKEY4) {
110 _numSortplanes = savedState->readLEUint32();
111 _sortplanes = new int[_numSortplanes];
112 for (int i = 0; i < _numSortplanes; ++i) {
113 _sortplanes[i] = savedState->readLEUint32();
114 }
115 }
116 return true;
117 }
118
load(TextSplitter & ts)119 void Sector::load(TextSplitter &ts) {
120 char buf[256];
121 int ident = 0, i = 0;
122 Math::Vector3d tempVert;
123
124 // Sector NAMES can be null, but ts isn't flexible enough
125 if (strlen(ts.getCurrentLine()) > strlen(" sector"))
126 ts.scanString(" sector %256s", 1, buf);
127 else {
128 ts.nextLine();
129 strcpy(buf, "");
130 }
131
132 ts.scanString(" id %d", 1, &ident);
133
134 _name = buf;
135 _id = ident;
136 ts.scanString(" type %256s", 1, buf);
137
138 if (strstr(buf, "walk"))
139 _type = WalkType;
140
141 else if (strstr(buf, "funnel"))
142 _type = FunnelType;
143 else if (strstr(buf, "camera"))
144 _type = CameraType;
145 else if (strstr(buf, "special"))
146 _type = SpecialType;
147 else if (strstr(buf, "chernobyl"))
148 _type = HotType;
149 else
150 Debug::error(Debug::Sets, "Unknown sector type '%s' in room setup", buf);
151
152 ts.scanString(" default visibility %256s", 1, buf);
153 if (strcmp(buf, "visible") == 0)
154 _visible = true;
155 else if (strcmp(buf, "invisible") == 0)
156 _visible = false;
157 else
158 error("Invalid visibility spec: %s", buf);
159 ts.scanString(" height %f", 1, &_height);
160 ts.scanString(" numvertices %d", 1, &_numVertices);
161 _vertices = new Math::Vector3d[_numVertices + 1];
162
163 ts.scanString(" vertices: %f %f %f", 3, &_vertices[0].x(), &_vertices[0].y(), &_vertices[0].z());
164 for (i = 1; i < _numVertices; i++)
165 ts.scanString(" %f %f %f", 3, &_vertices[i].x(), &_vertices[i].y(), &_vertices[i].z());
166
167 // Repeat the last vertex for convenience
168 _vertices[_numVertices] = _vertices[0];
169
170 _normal = Math::Vector3d::crossProduct(_vertices[1] - _vertices[0],
171 _vertices[_numVertices - 1] - _vertices[0]);
172 float length = _normal.getMagnitude();
173 if (length > 0)
174 _normal /= length;
175
176 // Remastered
177 if (!ts.checkString("numtris")) {
178 return;
179 }
180 int _numTris;
181 ts.scanString(" numtris %d", 1, &_numTris);
182 //_vertices = new Math::Vector3d[_numVertices + 1];
183 int a,b,c;
184 if (_numTris > 0) {
185 ts.scanString(" triangles: %f %f %f", 3, &a, &b, &c);
186 for (i = 1; i < _numTris; i++)
187 ts.scanString(" %f %f %f", 3, &a, &b, &c);
188 }
189 }
190
loadBinary(Common::SeekableReadStream * data)191 void Sector::loadBinary(Common::SeekableReadStream *data) {
192 _numVertices = data->readUint32LE();
193 _vertices = new Math::Vector3d[_numVertices + 1];
194 for (int i = 0; i < _numVertices; i++) {
195 _vertices[i].readFromStream(data);
196 }
197
198 // Repeat the last vertex for convenience
199 _vertices[_numVertices] = _vertices[0];
200
201 _normal = Math::Vector3d::crossProduct(_vertices[1] - _vertices[0],
202 _vertices[_numVertices - 1] - _vertices[0]);
203 float length = _normal.getMagnitude();
204 if (length > 0)
205 _normal /= length;
206
207 char name[128];
208 int nameLength = data->readUint32LE();
209
210 data->read(name, nameLength);
211 _name = name;
212
213 _id = data->readUint32LE();
214
215 _visible = data->readByte();
216
217 _type = (SectorType)data->readUint32LE();
218
219 _numSortplanes = data->readUint32LE();
220 _sortplanes = new int[_numSortplanes];
221 for (int i = 0; i < _numSortplanes; ++i) {
222 _sortplanes[i] = data->readUint32LE();
223 }
224
225 _height = data->readFloatLE();
226 }
227
setVisible(bool vis)228 void Sector::setVisible(bool vis) {
229 _visible = vis;
230 }
231
shrink(float radius)232 void Sector::shrink(float radius) {
233 if ((getType() & WalkType) == 0 || _shrinkRadius == radius)
234 return;
235
236 _shrinkRadius = radius;
237 if (!_origVertices) {
238 _origVertices = _vertices;
239 _vertices = new Math::Vector3d[_numVertices + 1];
240 }
241
242 // Move each vertex inwards by the given amount.
243 for (int j = 0; j < _numVertices; j++) {
244 Math::Vector3d shrinkDir;
245
246 for (int k = 0; k < g_grim->getCurrSet()->getSectorCount(); k++) {
247 Sector *other = g_grim->getCurrSet()->getSectorBase(k);
248 if ((other->getType() & WalkType) == 0)
249 continue;
250
251 for (int l = 0; l < other->_numVertices; l++) {
252 Math::Vector3d *otherVerts = other->_vertices;
253 if (other->_origVertices)
254 otherVerts = other->_origVertices;
255 if ((otherVerts[l] - _origVertices[j]).getMagnitude() < 0.01f) {
256 Math::Vector3d e1 = otherVerts[l + 1] - otherVerts[l];
257 Math::Vector3d e2;
258 if (l - 1 >= 0)
259 e2 = otherVerts[l] - otherVerts[l - 1];
260 else
261 e2 = otherVerts[l] - otherVerts[other->_numVertices - 1];
262 e1.normalize();
263 e2.normalize();
264 Math::Vector3d bisector = (e1 - e2);
265 bisector.normalize();
266 shrinkDir += bisector;
267 }
268 }
269 }
270
271 if (shrinkDir.getMagnitude() > 0.1f) {
272 shrinkDir.normalize();
273 _vertices[j] = _origVertices[j] + shrinkDir * radius;
274 } else {
275 _vertices[j] = _origVertices[j];
276 }
277 }
278
279 _vertices[_numVertices] = _vertices[0];
280
281 // Make sure the sector is still convex.
282 for (int j = 0; j < _numVertices; j++) {
283 Math::Vector3d e1 = _vertices[j + 1] - _vertices[j];
284 Math::Vector3d e2;
285 if (j - 1 >= 0)
286 e2 = _vertices[j] - _vertices[j - 1];
287 else
288 e2 = _vertices[j] - _vertices[_numVertices - 1];
289
290 if (e1.x() * e2.y() > e1.y() * e2.x()) {
291 // Not convex, so mark the sector invalid.
292 _invalid = true;
293 delete[] _vertices;
294 _vertices = _origVertices;
295 _origVertices = nullptr;
296 break;
297 }
298 }
299 }
300
unshrink()301 void Sector::unshrink() {
302 if (_shrinkRadius != 0.f) {
303 _shrinkRadius = 0.f;
304 _invalid = false;
305 if (_origVertices) {
306 delete[] _vertices;
307 _vertices = _origVertices;
308 _origVertices = nullptr;
309 }
310 }
311 }
312
distanceToPoint(const Math::Vector3d & point) const313 float Sector::distanceToPoint(const Math::Vector3d &point) const {
314 // The plane has equation ax + by + cz + d = 0
315 float a = _normal.x();
316 float b = _normal.y();
317 float c = _normal.z();
318 float d = -_vertices[0].x() * a - _vertices[0].y() * b - _vertices[0].z() * c;
319
320 // dist is positive if it is above the plain, negative if it is
321 // below and 0 if it is on the plane.
322 float dist = (a * point.x() + b * point.y() + c * point.z() + d);
323 dist /= sqrt(a * a + b * b + c * c);
324 return dist;
325 }
326
isPointInSector(const Math::Vector3d & point) const327 bool Sector::isPointInSector(const Math::Vector3d &point) const {
328 // Calculate the distance of the point from the plane of the sector.
329 // Return false if it isn't within a margin.
330 if (_height < 9000.f) { // No need to check when height is 9999.
331
332 float dist = distanceToPoint(point);
333
334 if (fabsf(dist) > _height + 0.01) // Add an error margin
335 return false;
336 }
337
338 // On the plane, so check if it is inside the polygon.
339 for (int i = 0; i < _numVertices; i++) {
340 Math::Vector3d edge = _vertices[i + 1] - _vertices[i];
341 Math::Vector3d delta = point - _vertices[i];
342 Math::Vector3d cross = Math::Vector3d::crossProduct(edge, delta);
343 if (cross.dotProduct(_normal) < -0.000001f) // not "< 0.f" here, since the value could be something like -7.45058e-09 and it
344 return false; // shuoldn't return. that was causing issue #610 (infinite loop in de.forklift_actor.dismount)
345 }
346 return true;
347 }
348
getBridgesTo(Sector * sector) const349 Common::List<Math::Line3d> Sector::getBridgesTo(Sector *sector) const {
350 // This returns a list of "bridges", which are edges that can be travelled
351 // through to get to another sector. 0 bridges mean the sectors aren't
352 // connected.
353
354 // The algorithm starts by considering all the edges of sector A
355 // bridges. It then narrows them down by cutting the bridges against
356 // sector B, so we end up with a list of lines which are at the border
357 // of sector A and inside sector B.
358
359 Common::List<Math::Line3d> bridges;
360 Common::List<Math::Line3d>::iterator it;
361
362 for (int i = 0; i < _numVertices; i++) {
363 bridges.push_back(Math::Line3d(_vertices[i], _vertices[i + 1]));
364 }
365
366 Math::Vector3d *sectorVertices = sector->getVertices();
367 for (int i = 0; i < sector->getNumVertices(); i++) {
368 Math::Vector3d pos, edge, delta_b1, delta_b2;
369 Math::Line3d line(sectorVertices[i], sectorVertices[i + 1]);
370 it = bridges.begin();
371 while (it != bridges.end()) {
372 Math::Line3d &bridge = (*it);
373 edge = line.end() - line.begin();
374 delta_b1 = bridge.begin() - line.begin();
375 delta_b2 = bridge.end() - line.begin();
376 Math::Vector3d cross_b1 = Math::Vector3d::crossProduct(edge, delta_b1);
377 Math::Vector3d cross_b2 = Math::Vector3d::crossProduct(edge, delta_b2);
378 bool b1_out = cross_b1.dotProduct(_normal) < 0;
379 bool b2_out = cross_b2.dotProduct(_normal) < 0;
380
381 bool useXZ = (g_grim->getGameType() == GType_MONKEY4);
382
383 if (b1_out && b2_out) {
384 // Both points are outside.
385 it = bridges.erase(it);
386 continue;
387 } else if (b1_out) {
388 if (bridge.intersectLine2d(line, &pos, useXZ)) {
389 bridge = Math::Line3d(pos, bridge.end());
390 }
391 } else if (b2_out) {
392 if (bridge.intersectLine2d(line, &pos, useXZ)) {
393 bridge = Math::Line3d(bridge.begin(), pos);
394 }
395 }
396
397 ++it;
398 }
399 }
400
401 // All the bridges should be at the same height on both sectors.
402 it = bridges.begin();
403 while (it != bridges.end()) {
404 if (g_grim->getGameType() == GType_MONKEY4) {
405 // Set pac contains sectors which are not parallel to any
406 // other sector or share any edge. Since one sector isn't
407 // a plane, finding the intersections in 3D would be complicated.
408 //
409 // Checking for bridges using a projection in 2D and having a height
410 // threshold to avoid that characters jump from lower to higher floors
411 // seems to be a good compromise.
412 //
413 // The value of at least 0.1 was chosen to fix a path finding issue
414 // in set pac when guybrush tried to reach the pile of rocks.
415 if (fabs(getProjectionToPlane((*it).begin()).y() - sector->getProjectionToPlane((*it).begin()).y()) > 0.1f ||
416 fabs(getProjectionToPlane((*it).end()).y() - sector->getProjectionToPlane((*it).end()).y()) > 0.1f) {
417 it = bridges.erase(it);
418 continue;
419 }
420 } else {
421 if (fabs(getProjectionToPlane((*it).begin()).z() - sector->getProjectionToPlane((*it).begin()).z()) > 0.01f ||
422 fabs(getProjectionToPlane((*it).end()).z() - sector->getProjectionToPlane((*it).end()).z()) > 0.01f) {
423 it = bridges.erase(it);
424 continue;
425 }
426 }
427 ++it;
428 }
429 return bridges;
430 }
431
getProjectionToPlane(const Math::Vector3d & point) const432 Math::Vector3d Sector::getProjectionToPlane(const Math::Vector3d &point) const {
433 if (_normal.getMagnitude() == 0)
434 error("Sector normal is (0,0,0)");
435
436 // Formula: return p - n * (n . (p - v_0))
437 Math::Vector3d result = point;
438 result -= _normal * _normal.dotProduct(point - _vertices[0]);
439 return result;
440 }
441
getProjectionToPuckVector(const Math::Vector3d & v) const442 Math::Vector3d Sector::getProjectionToPuckVector(const Math::Vector3d &v) const {
443 if (_normal.getMagnitude() == 0)
444 error("Sector normal is (0,0,0)");
445
446 Math::Vector3d result = v;
447 result -= _normal * _normal.dotProduct(v);
448 return result;
449 }
450
451 // Find the closest point on the walkplane to the given point
getClosestPoint(const Math::Vector3d & point) const452 Math::Vector3d Sector::getClosestPoint(const Math::Vector3d &point) const {
453 // First try to project to the plane
454 Math::Vector3d p2 = getProjectionToPlane(point);
455 if (isPointInSector(p2))
456 return p2;
457
458 // Now try to project to some edge
459 for (int i = 0; i < _numVertices; i++) {
460 Math::Vector3d edge = _vertices[i + 1] - _vertices[i];
461 Math::Vector3d delta = point - _vertices[i];
462 float scalar = Math::Vector3d::dotProduct(delta, edge) / Math::Vector3d::dotProduct(edge, edge);
463 Math::Vector3d cross = Math::Vector3d::crossProduct(delta, edge);
464 if (scalar >= 0 && scalar <= 1 && cross.dotProduct(_normal) > 0)
465 // That last test is just whether the z-component
466 // of delta cross edge is positive; we don't
467 // want to return opposite edges.
468 return _vertices[i] + scalar * edge;
469 }
470
471 // Otherwise, just find the closest vertex
472 float minDist = (point - _vertices[0]).getMagnitude();
473 int index = 0;
474 for (int i = 1; i < _numVertices; i++) {
475 float currDist = (point - _vertices[i]).getMagnitude();
476 if (currDist < minDist) {
477 minDist = currDist;
478 index = i;
479 }
480 }
481 return _vertices[index];
482 }
483
getExitInfo(const Math::Vector3d & s,const Math::Vector3d & dirVec,struct ExitInfo * result) const484 void Sector::getExitInfo(const Math::Vector3d &s, const Math::Vector3d &dirVec, struct ExitInfo *result) const {
485 Math::Vector3d start = getProjectionToPlane(s);
486 Math::Vector3d dir = getProjectionToPuckVector(dirVec);
487
488 // First find the edge the ray exits through: this is where
489 // the z-component of (v_i - start) x dir changes sign from
490 // positive to negative.
491
492 // First find a vertex such that the cross product has
493 // positive z-component.
494 int i;
495 for (i = 0; i < _numVertices; i++) {
496 Math::Vector3d delta = _vertices[i] - start;
497 Math::Vector3d cross = Math::Vector3d::crossProduct(delta, dir);
498 if (cross.dotProduct(_normal) > 0)
499 break;
500 }
501
502 // Now continue until the cross product has negative
503 // z-component.
504 while (i < _numVertices) {
505 i++;
506 Math::Vector3d delta = _vertices[i] - start;
507 Math::Vector3d cross = Math::Vector3d::crossProduct(delta, dir);
508 if (cross.dotProduct(_normal) <= 0)
509 break;
510 }
511
512 result->edgeDir = _vertices[i] - _vertices[i - 1];
513 result->angleWithEdge = Math::Vector3d::angle(dir, result->edgeDir);
514 result->edgeVertex = i - 1;
515
516 Math::Vector3d edgeNormal = Math::Vector3d::crossProduct(result->edgeDir, _normal);
517 float d = Math::Vector3d::dotProduct(dir, edgeNormal);
518 // This is 0 for the albinizod monster in the at set
519 if (!d)
520 d = 1.f;
521 result->exitPoint = start + (Math::Vector3d::dotProduct(_vertices[i] - start, edgeNormal) / d) * dir;
522 }
523
operator =(const Sector & other)524 Sector &Sector::operator=(const Sector &other) {
525 _numVertices = other._numVertices;
526 _id = other._id;
527 _name = other._name;
528 _type = other._type;
529 _visible = other._visible;
530 _vertices = new Math::Vector3d[_numVertices + 1];
531 for (int i = 0; i < _numVertices + 1; ++i) {
532 _vertices[i] = other._vertices[i];
533 }
534 if (other._origVertices) {
535 _origVertices = new Math::Vector3d[_numVertices + 1];
536 for (int i = 0; i < _numVertices + 1; ++i) {
537 _origVertices[i] = other._origVertices[i];
538 }
539 } else {
540 _origVertices = nullptr;
541 }
542 _height = other._height;
543 _normal = other._normal;
544 _shrinkRadius = other._shrinkRadius;
545 _invalid = other._invalid;
546
547 return *this;
548 }
549
operator ==(const Sector & other) const550 bool Sector::operator==(const Sector &other) const {
551 bool ok = _numVertices == other._numVertices &&
552 _id == other._id &&
553 _name == other._name &&
554 _type == other._type &&
555 _visible == other._visible;
556 for (int i = 0; i < _numVertices + 1; ++i) {
557 ok = ok && _vertices[i] == other._vertices[i];
558 }
559 ok = ok && _height == other._height &&
560 _normal == other._normal;
561
562 return ok;
563 }
564
565 } // end of namespace Grim
566