ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

sector.cpp

Go to the documentation of this file.
00001 /* ResidualVM - A 3D game interpreter
00002  *
00003  * ResidualVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the AUTHORS
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #include "common/util.h"
00024 
00025 #include "engines/grim/debug.h"
00026 #include "engines/grim/grim.h"
00027 #include "engines/grim/sector.h"
00028 #include "engines/grim/textsplit.h"
00029 #include "engines/grim/savegame.h"
00030 #include "engines/grim/set.h"
00031 
00032 namespace Grim {
00033 
00034 Sector::Sector() :
00035         _vertices(nullptr), _origVertices(nullptr), _sortplanes(nullptr),_invalid(false),
00036         _shrinkRadius(0.f), _numVertices(0), _id(0), _numSortplanes(0),
00037         _type(NoneType), _visible(false), _height(0.f) {
00038  }
00039 
00040 Sector::Sector(const Sector &other) :
00041         _vertices(nullptr), _origVertices(nullptr), _sortplanes(nullptr),
00042         _numSortplanes(0) {
00043     *this = other;
00044 }
00045 
00046 Sector::~Sector() {
00047     delete[] _vertices;
00048     delete[] _origVertices;
00049     delete[] _sortplanes;
00050 }
00051 
00052 void Sector::saveState(SaveGame *savedState) const {
00053     savedState->writeLESint32(_numVertices);
00054     savedState->writeLESint32(_id);
00055     savedState->writeLESint32(_type);
00056     savedState->writeBool(_visible);
00057     savedState->writeFloat(_height);
00058 
00059     savedState->writeString(_name);
00060 
00061     for (int i = 0; i < _numVertices + 1; ++i) {
00062         savedState->writeVector3d(_vertices[i]);
00063     }
00064 
00065     savedState->writeVector3d(_normal);
00066 
00067     savedState->writeFloat(_shrinkRadius);
00068     savedState->writeBool(_invalid);
00069     if (_shrinkRadius != 0.f && !_invalid) {
00070         for (int i = 0; i < _numVertices + 1; ++i) {
00071             savedState->writeVector3d(_origVertices[i]);
00072         }
00073     }
00074 
00075     if (savedState->saveMinorVersion() > 8 && g_grim->getGameType() == GType_MONKEY4) {
00076         savedState->writeLEUint32(_numSortplanes);
00077         for (int i = 0; i < _numSortplanes; ++i) {
00078             savedState->writeLEUint32(_sortplanes[i]);
00079         }
00080     }
00081 }
00082 
00083 bool Sector::restoreState(SaveGame *savedState) {
00084     _numVertices = savedState->readLESint32();
00085     _id          = savedState->readLESint32();
00086     _type        = (SectorType)savedState->readLESint32();
00087     _visible     = savedState->readBool();
00088     _height      = savedState->readFloat();
00089 
00090     _name        = savedState->readString();
00091 
00092     _vertices = new Math::Vector3d[_numVertices + 1];
00093     for (int i = 0; i < _numVertices + 1; ++i) {
00094         _vertices[i] = savedState->readVector3d();
00095     }
00096 
00097     _normal = savedState->readVector3d();
00098 
00099     _shrinkRadius = savedState->readFloat();
00100     _invalid = savedState->readBool();
00101     if (_shrinkRadius != 0.f && !_invalid) {
00102         _origVertices = new Math::Vector3d[_numVertices + 1];
00103         for (int i = 0; i < _numVertices + 1; ++i) {
00104             _origVertices[i] = savedState->readVector3d();
00105         }
00106     } else {
00107         _origVertices = nullptr;
00108     }
00109     if (savedState->saveMinorVersion() > 8 && g_grim->getGameType() == GType_MONKEY4) {
00110         _numSortplanes = savedState->readLEUint32();
00111         _sortplanes = new int[_numSortplanes];
00112         for (int i = 0; i < _numSortplanes; ++i) {
00113             _sortplanes[i] = savedState->readLEUint32();
00114         }
00115     }
00116     return true;
00117 }
00118 
00119 void Sector::load(TextSplitter &ts) {
00120     char buf[256];
00121     int ident = 0, i = 0;
00122     Math::Vector3d tempVert;
00123 
00124     // Sector NAMES can be null, but ts isn't flexible enough
00125     if (strlen(ts.getCurrentLine()) > strlen(" sector"))
00126         ts.scanString(" sector %256s", 1, buf);
00127     else {
00128         ts.nextLine();
00129         strcpy(buf, "");
00130     }
00131 
00132     ts.scanString(" id %d", 1, &ident);
00133 
00134     _name = buf;
00135     _id = ident;
00136     ts.scanString(" type %256s", 1, buf);
00137 
00138     if (strstr(buf, "walk"))
00139         _type = WalkType;
00140 
00141     else if (strstr(buf, "funnel"))
00142         _type = FunnelType;
00143     else if (strstr(buf, "camera"))
00144         _type = CameraType;
00145     else if (strstr(buf, "special"))
00146         _type = SpecialType;
00147     else if (strstr(buf, "chernobyl"))
00148         _type = HotType;
00149     else
00150         Debug::error(Debug::Sets, "Unknown sector type '%s' in room setup", buf);
00151 
00152     ts.scanString(" default visibility %256s", 1, buf);
00153     if (strcmp(buf, "visible") == 0)
00154         _visible = true;
00155     else if (strcmp(buf, "invisible") == 0)
00156         _visible = false;
00157     else
00158         error("Invalid visibility spec: %s", buf);
00159     ts.scanString(" height %f", 1, &_height);
00160     ts.scanString(" numvertices %d", 1, &_numVertices);
00161     _vertices = new Math::Vector3d[_numVertices + 1];
00162 
00163     ts.scanString(" vertices: %f %f %f", 3, &_vertices[0].x(), &_vertices[0].y(), &_vertices[0].z());
00164     for (i = 1; i < _numVertices; i++)
00165         ts.scanString(" %f %f %f", 3, &_vertices[i].x(), &_vertices[i].y(), &_vertices[i].z());
00166 
00167     // Repeat the last vertex for convenience
00168     _vertices[_numVertices] = _vertices[0];
00169 
00170     _normal = Math::Vector3d::crossProduct(_vertices[1] - _vertices[0],
00171                                            _vertices[_numVertices - 1] - _vertices[0]);
00172     float length = _normal.getMagnitude();
00173     if (length > 0)
00174         _normal /= length;
00175 }
00176 
00177 void Sector::loadBinary(Common::SeekableReadStream *data) {
00178     _numVertices = data->readUint32LE();
00179     _vertices = new Math::Vector3d[_numVertices + 1];
00180     for (int i = 0; i < _numVertices; i++) {
00181         _vertices[i].readFromStream(data);
00182     }
00183 
00184     // Repeat the last vertex for convenience
00185     _vertices[_numVertices] = _vertices[0];
00186 
00187     _normal = Math::Vector3d::crossProduct(_vertices[1] - _vertices[0],
00188                                            _vertices[_numVertices - 1] - _vertices[0]);
00189     float length = _normal.getMagnitude();
00190     if (length > 0)
00191         _normal /= length;
00192 
00193     char name[128];
00194     int nameLength = data->readUint32LE();
00195 
00196     data->read(name, nameLength);
00197     _name = name;
00198 
00199     _id = data->readUint32LE();
00200 
00201     _visible = data->readByte();
00202 
00203     _type = (SectorType)data->readUint32LE();
00204 
00205     _numSortplanes = data->readUint32LE();
00206     _sortplanes = new int[_numSortplanes];
00207     for (int i = 0; i < _numSortplanes; ++i) {
00208         _sortplanes[i] = data->readUint32LE();
00209     }
00210 
00211     _height = data->readFloatLE();
00212 }
00213 
00214 void Sector::setVisible(bool vis) {
00215     _visible = vis;
00216 }
00217 
00218 void Sector::shrink(float radius) {
00219     if ((getType() & WalkType) == 0 || _shrinkRadius == radius)
00220         return;
00221 
00222     _shrinkRadius = radius;
00223     if (!_origVertices) {
00224         _origVertices = _vertices;
00225         _vertices = new Math::Vector3d[_numVertices + 1];
00226     }
00227 
00228     // Move each vertex inwards by the given amount.
00229     for (int j = 0; j < _numVertices; j++) {
00230         Math::Vector3d shrinkDir;
00231 
00232         for (int k = 0; k < g_grim->getCurrSet()->getSectorCount(); k++) {
00233             Sector *other = g_grim->getCurrSet()->getSectorBase(k);
00234             if ((other->getType() & WalkType) == 0)
00235                 continue;
00236 
00237             for (int l = 0; l < other->_numVertices; l++) {
00238                 Math::Vector3d *otherVerts = other->_vertices;
00239                 if (other->_origVertices)
00240                     otherVerts = other->_origVertices;
00241                 if ((otherVerts[l] - _origVertices[j]).getMagnitude() < 0.01f) {
00242                     Math::Vector3d e1 = otherVerts[l + 1] - otherVerts[l];
00243                     Math::Vector3d e2;
00244                     if (l - 1 >= 0)
00245                         e2 = otherVerts[l] - otherVerts[l - 1];
00246                     else
00247                         e2 = otherVerts[l] - otherVerts[other->_numVertices - 1];
00248                     e1.normalize();
00249                     e2.normalize();
00250                     Math::Vector3d bisector = (e1 - e2);
00251                     bisector.normalize();
00252                     shrinkDir += bisector;
00253                 }
00254             }
00255         }
00256 
00257         if (shrinkDir.getMagnitude() > 0.1f) {
00258             shrinkDir.normalize();
00259             _vertices[j] = _origVertices[j] + shrinkDir * radius;
00260         } else {
00261             _vertices[j] = _origVertices[j];
00262         }
00263     }
00264 
00265     _vertices[_numVertices] = _vertices[0];
00266 
00267     // Make sure the sector is still convex.
00268     for (int j = 0; j < _numVertices; j++) {
00269         Math::Vector3d e1 = _vertices[j + 1] - _vertices[j];
00270         Math::Vector3d e2;
00271         if (j - 1 >= 0)
00272             e2 = _vertices[j] - _vertices[j - 1];
00273         else
00274             e2 = _vertices[j] - _vertices[_numVertices - 1];
00275 
00276         if (e1.x() * e2.y() > e1.y() * e2.x()) {
00277             // Not convex, so mark the sector invalid.
00278             _invalid = true;
00279             delete[] _vertices;
00280             _vertices = _origVertices;
00281             _origVertices = nullptr;
00282             break;
00283         }
00284     }
00285 }
00286 
00287 void Sector::unshrink() {
00288     if (_shrinkRadius != 0.f) {
00289         _shrinkRadius = 0.f;
00290         _invalid = false;
00291         if (_origVertices) {
00292             delete[] _vertices;
00293             _vertices = _origVertices;
00294             _origVertices = nullptr;
00295         }
00296     }
00297 }
00298 
00299 float Sector::distanceToPoint(const Math::Vector3d &point) const {
00300     // The plane has equation ax + by + cz + d = 0
00301     float a = _normal.x();
00302     float b = _normal.y();
00303     float c = _normal.z();
00304     float d = -_vertices[0].x() * a - _vertices[0].y() * b - _vertices[0].z() * c;
00305 
00306     // dist is positive if it is above the plain, negative if it is
00307     // below and 0 if it is on the plane.
00308     float dist = (a * point.x() + b * point.y() + c * point.z() + d);
00309     dist /= sqrt(a * a + b * b + c * c);
00310     return dist;
00311 }
00312 
00313 bool Sector::isPointInSector(const Math::Vector3d &point) const {
00314     // Calculate the distance of the point from the plane of the sector.
00315     // Return false if it isn't within a margin.
00316     if (_height < 9000.f) { // No need to check when height is 9999.
00317 
00318         float dist = distanceToPoint(point);
00319 
00320         if (fabsf(dist) > _height + 0.01) // Add an error margin
00321             return false;
00322     }
00323 
00324     // On the plane, so check if it is inside the polygon.
00325     for (int i = 0; i < _numVertices; i++) {
00326         Math::Vector3d edge = _vertices[i + 1] - _vertices[i];
00327         Math::Vector3d delta = point - _vertices[i];
00328         Math::Vector3d cross = Math::Vector3d::crossProduct(edge, delta);
00329         if (cross.dotProduct(_normal) < -0.000001f) // not "< 0.f" here, since the value could be something like -7.45058e-09 and it
00330             return false;                        // shuoldn't return. that was causing issue #610 (infinite loop in de.forklift_actor.dismount)
00331     }
00332     return true;
00333 }
00334 
00335 Common::List<Math::Line3d> Sector::getBridgesTo(Sector *sector) const {
00336     // This returns a list of "bridges", which are edges that can be travelled
00337     // through to get to another sector. 0 bridges mean the sectors aren't
00338     // connected.
00339 
00340     // The algorithm starts by considering all the edges of sector A
00341     // bridges. It then narrows them down by cutting the bridges against
00342     // sector B, so we end up with a list of lines which are at the border
00343     // of sector A and inside sector B.
00344 
00345     Common::List<Math::Line3d> bridges;
00346     Common::List<Math::Line3d>::iterator it;
00347 
00348     for (int i = 0; i < _numVertices; i++) {
00349         bridges.push_back(Math::Line3d(_vertices[i], _vertices[i + 1]));
00350     }
00351 
00352     Math::Vector3d *sectorVertices = sector->getVertices();
00353     for (int i = 0; i < sector->getNumVertices(); i++) {
00354         Math::Vector3d pos, edge, delta_b1, delta_b2;
00355         Math::Line3d line(sectorVertices[i], sectorVertices[i + 1]);
00356         it = bridges.begin();
00357         while (it != bridges.end()) {
00358             Math::Line3d &bridge = (*it);
00359             edge = line.end() - line.begin();
00360             delta_b1 = bridge.begin() - line.begin();
00361             delta_b2 = bridge.end() - line.begin();
00362             Math::Vector3d cross_b1 = Math::Vector3d::crossProduct(edge, delta_b1);
00363             Math::Vector3d cross_b2 = Math::Vector3d::crossProduct(edge, delta_b2);
00364             bool b1_out = cross_b1.dotProduct(_normal) < 0;
00365             bool b2_out = cross_b2.dotProduct(_normal) < 0;
00366 
00367             bool useXZ = (g_grim->getGameType() == GType_MONKEY4);
00368 
00369             if (b1_out && b2_out) {
00370                 // Both points are outside.
00371                 it = bridges.erase(it);
00372                 continue;
00373             } else if (b1_out) {
00374                 if (bridge.intersectLine2d(line, &pos, useXZ)) {
00375                     bridge = Math::Line3d(pos, bridge.end());
00376                 }
00377             } else if (b2_out) {
00378                 if (bridge.intersectLine2d(line, &pos, useXZ)) {
00379                     bridge = Math::Line3d(bridge.begin(), pos);
00380                 }
00381             }
00382 
00383             ++it;
00384         }
00385     }
00386 
00387     // All the bridges should be at the same height on both sectors.
00388     it = bridges.begin();
00389     while (it != bridges.end()) {
00390         if (g_grim->getGameType() == GType_MONKEY4) {
00391             // Set pac contains sectors which are not parallel to any
00392             // other sector or share any edge. Since one sector isn't
00393             // a plane, finding the intersections in 3D would be complicated.
00394             //
00395             // Checking for bridges using a projection in 2D and having a height
00396             // threshold to avoid that characters jump from lower to higher floors
00397             // seems to be a good compromise.
00398             //
00399             // The value of at least 0.1 was chosen to fix a path finding issue
00400             // in set pac when guybrush tried to reach the pile of rocks.
00401             if (fabs(getProjectionToPlane((*it).begin()).y() - sector->getProjectionToPlane((*it).begin()).y()) > 0.1f ||
00402                     fabs(getProjectionToPlane((*it).end()).y() - sector->getProjectionToPlane((*it).end()).y()) > 0.1f) {
00403                 it = bridges.erase(it);
00404                 continue;
00405             }
00406         } else {
00407             if (fabs(getProjectionToPlane((*it).begin()).z() - sector->getProjectionToPlane((*it).begin()).z()) > 0.01f ||
00408                     fabs(getProjectionToPlane((*it).end()).z() - sector->getProjectionToPlane((*it).end()).z()) > 0.01f) {
00409                 it = bridges.erase(it);
00410                 continue;
00411             }
00412         }
00413         ++it;
00414     }
00415     return bridges;
00416 }
00417 
00418 Math::Vector3d Sector::getProjectionToPlane(const Math::Vector3d &point) const {
00419     if (_normal.getMagnitude() == 0)
00420         error("Sector normal is (0,0,0)");
00421 
00422     // Formula: return p - n * (n . (p - v_0))
00423     Math::Vector3d result = point;
00424     result -= _normal * _normal.dotProduct(point - _vertices[0]);
00425     return result;
00426 }
00427 
00428 Math::Vector3d Sector::getProjectionToPuckVector(const Math::Vector3d &v) const {
00429     if (_normal.getMagnitude() == 0)
00430         error("Sector normal is (0,0,0)");
00431 
00432     Math::Vector3d result = v;
00433     result -= _normal * _normal.dotProduct(v);
00434     return result;
00435 }
00436 
00437 // Find the closest point on the walkplane to the given point
00438 Math::Vector3d Sector::getClosestPoint(const Math::Vector3d &point) const {
00439     // First try to project to the plane
00440     Math::Vector3d p2 = getProjectionToPlane(point);
00441     if (isPointInSector(p2))
00442         return p2;
00443 
00444     // Now try to project to some edge
00445     for (int i = 0; i < _numVertices; i++) {
00446         Math::Vector3d edge = _vertices[i + 1] - _vertices[i];
00447         Math::Vector3d delta = point - _vertices[i];
00448         float scalar = Math::Vector3d::dotProduct(delta, edge) / Math::Vector3d::dotProduct(edge, edge);
00449         Math::Vector3d cross = Math::Vector3d::crossProduct(delta, edge);
00450         if (scalar >= 0 && scalar <= 1 && cross.dotProduct(_normal) > 0)
00451             // That last test is just whether the z-component
00452             // of delta cross edge is positive; we don't
00453             // want to return opposite edges.
00454             return _vertices[i] + scalar * edge;
00455     }
00456 
00457     // Otherwise, just find the closest vertex
00458     float minDist = (point - _vertices[0]).getMagnitude();
00459     int index = 0;
00460     for (int i = 1; i < _numVertices; i++) {
00461         float currDist = (point - _vertices[i]).getMagnitude();
00462         if (currDist < minDist) {
00463             minDist = currDist;
00464             index = i;
00465         }
00466     }
00467     return _vertices[index];
00468 }
00469 
00470 void Sector::getExitInfo(const Math::Vector3d &s, const Math::Vector3d &dirVec, struct ExitInfo *result) const {
00471     Math::Vector3d start = getProjectionToPlane(s);
00472     Math::Vector3d dir = getProjectionToPuckVector(dirVec);
00473 
00474     // First find the edge the ray exits through: this is where
00475     // the z-component of (v_i - start) x dir changes sign from
00476     // positive to negative.
00477 
00478     // First find a vertex such that the cross product has
00479     // positive z-component.
00480     int i;
00481     for (i = 0; i < _numVertices; i++) {
00482         Math::Vector3d delta = _vertices[i] - start;
00483         Math::Vector3d cross = Math::Vector3d::crossProduct(delta, dir);
00484         if (cross.dotProduct(_normal) > 0)
00485             break;
00486     }
00487 
00488     // Now continue until the cross product has negative
00489     // z-component.
00490     while (i < _numVertices) {
00491         i++;
00492         Math::Vector3d delta = _vertices[i] - start;
00493         Math::Vector3d cross = Math::Vector3d::crossProduct(delta, dir);
00494         if (cross.dotProduct(_normal) <= 0)
00495             break;
00496     }
00497 
00498     result->edgeDir = _vertices[i] - _vertices[i - 1];
00499     result->angleWithEdge = Math::Vector3d::angle(dir, result->edgeDir);
00500     result->edgeVertex = i - 1;
00501 
00502     Math::Vector3d edgeNormal = Math::Vector3d::crossProduct(result->edgeDir, _normal);
00503     float d = Math::Vector3d::dotProduct(dir, edgeNormal);
00504     // This is 0 for the albinizod monster in the at set
00505     if (!d)
00506         d = 1.f;
00507     result->exitPoint = start + (Math::Vector3d::dotProduct(_vertices[i] - start, edgeNormal) / d) * dir;
00508 }
00509 
00510 Sector &Sector::operator=(const Sector &other) {
00511     _numVertices = other._numVertices;
00512     _id = other._id;
00513     _name = other._name;
00514     _type = other._type;
00515     _visible = other._visible;
00516     _vertices = new Math::Vector3d[_numVertices + 1];
00517     for (int i = 0; i < _numVertices + 1; ++i) {
00518         _vertices[i] = other._vertices[i];
00519     }
00520     if (other._origVertices) {
00521         _origVertices = new Math::Vector3d[_numVertices + 1];
00522         for (int i = 0; i < _numVertices + 1; ++i) {
00523             _origVertices[i] = other._origVertices[i];
00524         }
00525     } else {
00526         _origVertices = nullptr;
00527     }
00528     _height = other._height;
00529     _normal = other._normal;
00530     _shrinkRadius = other._shrinkRadius;
00531     _invalid = other._invalid;
00532 
00533     return *this;
00534 }
00535 
00536 bool Sector::operator==(const Sector &other) const {
00537     bool ok = _numVertices == other._numVertices &&
00538               _id == other._id &&
00539               _name == other._name &&
00540               _type == other._type &&
00541               _visible == other._visible;
00542     for (int i = 0; i < _numVertices + 1; ++i) {
00543         ok = ok && _vertices[i] == other._vertices[i];
00544     }
00545     ok = ok && _height == other._height &&
00546          _normal == other._normal;
00547 
00548     return ok;
00549 }
00550 
00551 } // end of namespace Grim


Generated on Sat Feb 16 2019 05:01:03 for ResidualVM by doxygen 1.7.1
curved edge   curved edge