diff options
Diffstat (limited to 'thirdparty')
| -rw-r--r-- | thirdparty/README.md | 18 | ||||
| -rw-r--r-- | thirdparty/rvo2/LICENSE | 202 | ||||
| -rw-r--r-- | thirdparty/rvo2/README.md | 32 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/API.h | 71 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/Agent.cpp | 425 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/Agent.h | 121 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/Definitions.h | 55 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/KdTree.cpp | 152 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/KdTree.h | 124 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/RVO.h | 406 | ||||
| -rw-r--r-- | thirdparty/rvo2/src/Vector3.h | 335 |
11 files changed, 1940 insertions, 1 deletions
diff --git a/thirdparty/README.md b/thirdparty/README.md index 7c3378dec3..8143b4af56 100644 --- a/thirdparty/README.md +++ b/thirdparty/README.md @@ -432,7 +432,7 @@ Files extracted from upstream source: ## recastnavigation - Upstream: https://github.com/recastnavigation/recastnavigation -- version: git (ef3ea40f, 2017) +- Version: git (ef3ea40f, 2017) - License: zlib Files extracted from upstream source: @@ -441,6 +441,22 @@ Files extracted from upstream source: - License.txt +## Rvo2 + +- Upstream: http://gamma.cs.unc.edu/RVO2/ +- Version: 3D - 1.0.1 +- License: Apache 2.0 + +Files extracted from upstream source: + +- All .cpp and .h files in the `src/` folder except for RVOSimulator.cpp and RVOSimulator.h +- LICENSE + +Important: Some files have Godot-made changes; so to enrich the features +originally proposed by this library and better integrate this library with +Godot. Please check the file to know what's new. + + ## squish - Upstream: https://sourceforge.net/projects/libsquish diff --git a/thirdparty/rvo2/LICENSE b/thirdparty/rvo2/LICENSE new file mode 100644 index 0000000000..d645695673 --- /dev/null +++ b/thirdparty/rvo2/LICENSE @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright [yyyy] [name of copyright owner] + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/thirdparty/rvo2/README.md b/thirdparty/rvo2/README.md new file mode 100644 index 0000000000..96af597cb6 --- /dev/null +++ b/thirdparty/rvo2/README.md @@ -0,0 +1,32 @@ +Optimal Reciprocal Collision Avoidance in Three Dimensions +========================================================== + +<http://gamma.cs.unc.edu/RVO2/> + +[](https://travis-ci.org/snape/RVO2-3D) +[](https://ci.appveyor.com/project/snape/rvo2-3d) + +Copyright 2008 University of North Carolina at Chapel Hill + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +<http://www.apache.org/licenses/LICENSE-2.0> + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. + +Please send all bug reports to [geom@cs.unc.edu](mailto:geom@cs.unc.edu). + +The authors may be contacted via: + +Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha +Dept. of Computer Science +201 S. Columbia St. +Frederick P. Brooks, Jr. Computer Science Bldg. +Chapel Hill, N.C. 27599-3175 +United States of America diff --git a/thirdparty/rvo2/src/API.h b/thirdparty/rvo2/src/API.h new file mode 100644 index 0000000000..c63a5a383c --- /dev/null +++ b/thirdparty/rvo2/src/API.h @@ -0,0 +1,71 @@ +/* + * API.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +/** + * \file API.h + * \brief Contains definitions related to Microsoft Windows. + */ + +#ifndef RVO_API_H_ +#define RVO_API_H_ + +#ifdef _WIN32 +#include <SDKDDKVer.h> +#define WIN32_LEAN_AND_MEAN +#define NOCOMM +#define NOIMAGE +#define NOIME +#define NOKANJI +#define NOMCX +#ifndef NOMINMAX +#define NOMINMAX +#endif +#define NOPROXYSTUB +#define NOSERVICE +#define NOSOUND +#define NOTAPE +#define NORPC +#define _USE_MATH_DEFINES +#include <windows.h> +#undef CONNECT_DEFERRED // Avoid collision with the Godot Object class +#undef CreateDialog // Avoid collision with the Godot CreateDialog class +#endif + +#ifdef RVO_EXPORTS +#define RVO_API __declspec(dllexport) +#elif defined(RVO_IMPORTS) +#define RVO_API __declspec(dllimport) +#else +#define RVO_API +#endif + +#endif /* RVO_API_H_ */ diff --git a/thirdparty/rvo2/src/Agent.cpp b/thirdparty/rvo2/src/Agent.cpp new file mode 100644 index 0000000000..851d780758 --- /dev/null +++ b/thirdparty/rvo2/src/Agent.cpp @@ -0,0 +1,425 @@ +/* + * Agent.cpp + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +#include "Agent.h" + +#include <algorithm> +#include <cmath> + +#include "Definitions.h" +#include "KdTree.h" + +namespace RVO { +/** + * \brief A sufficiently small positive number. + */ +const float RVO_EPSILON = 0.00001f; + +/** + * \brief Defines a directed line. + */ +class Line { +public: + /** + * \brief The direction of the directed line. + */ + Vector3 direction; + + /** + * \brief A point on the directed line. + */ + Vector3 point; +}; + +/** + * \brief Solves a one-dimensional linear program on a specified line subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param planeNo The plane on which the line lies. + * \param line The line on which the 1-d linear program is solved + * \param radius The radius of the spherical constraint. + * \param optVelocity The optimization velocity. + * \param directionOpt True if the direction should be optimized. + * \param result A reference to the result of the linear program. + * \return True if successful. + */ +bool linearProgram1(const std::vector<Plane> &planes, size_t planeNo, const Line &line, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); + +/** + * \brief Solves a two-dimensional linear program on a specified plane subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param planeNo The plane on which the 2-d linear program is solved + * \param radius The radius of the spherical constraint. + * \param optVelocity The optimization velocity. + * \param directionOpt True if the direction should be optimized. + * \param result A reference to the result of the linear program. + * \return True if successful. + */ +bool linearProgram2(const std::vector<Plane> &planes, size_t planeNo, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); + +/** + * \brief Solves a three-dimensional linear program subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param radius The radius of the spherical constraint. + * \param optVelocity The optimization velocity. + * \param directionOpt True if the direction should be optimized. + * \param result A reference to the result of the linear program. + * \return The number of the plane it fails on, and the number of planes if successful. + */ +size_t linearProgram3(const std::vector<Plane> &planes, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); + +/** + * \brief Solves a four-dimensional linear program subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param beginPlane The plane on which the 3-d linear program failed. + * \param radius The radius of the spherical constraint. + * \param result A reference to the result of the linear program. + */ +void linearProgram4(const std::vector<Plane> &planes, size_t beginPlane, float radius, Vector3 &result); + +Agent::Agent() : + id_(0), maxNeighbors_(0), maxSpeed_(0.0f), neighborDist_(0.0f), radius_(0.0f), timeHorizon_(0.0f), ignore_y_(false) {} + +void Agent::computeNeighbors(KdTree *kdTree_) { + agentNeighbors_.clear(); + if (maxNeighbors_ > 0) { + kdTree_->computeAgentNeighbors(this, neighborDist_ * neighborDist_); + } +} + +#define ABS(m_v) (((m_v) < 0) ? (-(m_v)) : (m_v)) +void Agent::computeNewVelocity(float timeStep) { + orcaPlanes_.clear(); + const float invTimeHorizon = 1.0f / timeHorizon_; + + /* Create agent ORCA planes. */ + for (size_t i = 0; i < agentNeighbors_.size(); ++i) { + const Agent *const other = agentNeighbors_[i].second; + + Vector3 relativePosition = other->position_ - position_; + Vector3 relativeVelocity = velocity_ - other->velocity_; + const float combinedRadius = radius_ + other->radius_; + + // This is a Godot feature that allow the agents to avoid the collision + // by moving only on the horizontal plane relative to the player velocity. + if (ignore_y_) { + // Skip if these are in two different heights + if (ABS(relativePosition[1]) > combinedRadius * 2) { + continue; + } + relativePosition[1] = 0; + relativeVelocity[1] = 0; + } + + const float distSq = absSq(relativePosition); + const float combinedRadiusSq = sqr(combinedRadius); + + Plane plane; + Vector3 u; + + if (distSq > combinedRadiusSq) { + /* No collision. */ + const Vector3 w = relativeVelocity - invTimeHorizon * relativePosition; + /* Vector from cutoff center to relative velocity. */ + const float wLengthSq = absSq(w); + + const float dotProduct = w * relativePosition; + + if (dotProduct < 0.0f && sqr(dotProduct) > combinedRadiusSq * wLengthSq) { + /* Project on cut-off circle. */ + const float wLength = std::sqrt(wLengthSq); + const Vector3 unitW = w / wLength; + + plane.normal = unitW; + u = (combinedRadius * invTimeHorizon - wLength) * unitW; + } else { + /* Project on cone. */ + const float a = distSq; + const float b = relativePosition * relativeVelocity; + const float c = absSq(relativeVelocity) - absSq(cross(relativePosition, relativeVelocity)) / (distSq - combinedRadiusSq); + const float t = (b + std::sqrt(sqr(b) - a * c)) / a; + const Vector3 w = relativeVelocity - t * relativePosition; + const float wLength = abs(w); + const Vector3 unitW = w / wLength; + + plane.normal = unitW; + u = (combinedRadius * t - wLength) * unitW; + } + } else { + /* Collision. */ + const float invTimeStep = 1.0f / timeStep; + const Vector3 w = relativeVelocity - invTimeStep * relativePosition; + const float wLength = abs(w); + const Vector3 unitW = w / wLength; + + plane.normal = unitW; + u = (combinedRadius * invTimeStep - wLength) * unitW; + } + + plane.point = velocity_ + 0.5f * u; + orcaPlanes_.push_back(plane); + } + + const size_t planeFail = linearProgram3(orcaPlanes_, maxSpeed_, prefVelocity_, false, newVelocity_); + + if (planeFail < orcaPlanes_.size()) { + linearProgram4(orcaPlanes_, planeFail, maxSpeed_, newVelocity_); + } + + if (ignore_y_) { + // Not 100% necessary, but better to have. + newVelocity_[1] = prefVelocity_[1]; + } +} + +void Agent::insertAgentNeighbor(const Agent *agent, float &rangeSq) { + if (this != agent) { + const float distSq = absSq(position_ - agent->position_); + + if (distSq < rangeSq) { + if (agentNeighbors_.size() < maxNeighbors_) { + agentNeighbors_.push_back(std::make_pair(distSq, agent)); + } + + size_t i = agentNeighbors_.size() - 1; + + while (i != 0 && distSq < agentNeighbors_[i - 1].first) { + agentNeighbors_[i] = agentNeighbors_[i - 1]; + --i; + } + + agentNeighbors_[i] = std::make_pair(distSq, agent); + + if (agentNeighbors_.size() == maxNeighbors_) { + rangeSq = agentNeighbors_.back().first; + } + } + } +} + +bool linearProgram1(const std::vector<Plane> &planes, size_t planeNo, const Line &line, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { + const float dotProduct = line.point * line.direction; + const float discriminant = sqr(dotProduct) + sqr(radius) - absSq(line.point); + + if (discriminant < 0.0f) { + /* Max speed sphere fully invalidates line. */ + return false; + } + + const float sqrtDiscriminant = std::sqrt(discriminant); + float tLeft = -dotProduct - sqrtDiscriminant; + float tRight = -dotProduct + sqrtDiscriminant; + + for (size_t i = 0; i < planeNo; ++i) { + const float numerator = (planes[i].point - line.point) * planes[i].normal; + const float denominator = line.direction * planes[i].normal; + + if (sqr(denominator) <= RVO_EPSILON) { + /* Lines line is (almost) parallel to plane i. */ + if (numerator > 0.0f) { + return false; + } else { + continue; + } + } + + const float t = numerator / denominator; + + if (denominator >= 0.0f) { + /* Plane i bounds line on the left. */ + tLeft = std::max(tLeft, t); + } else { + /* Plane i bounds line on the right. */ + tRight = std::min(tRight, t); + } + + if (tLeft > tRight) { + return false; + } + } + + if (directionOpt) { + /* Optimize direction. */ + if (optVelocity * line.direction > 0.0f) { + /* Take right extreme. */ + result = line.point + tRight * line.direction; + } else { + /* Take left extreme. */ + result = line.point + tLeft * line.direction; + } + } else { + /* Optimize closest point. */ + const float t = line.direction * (optVelocity - line.point); + + if (t < tLeft) { + result = line.point + tLeft * line.direction; + } else if (t > tRight) { + result = line.point + tRight * line.direction; + } else { + result = line.point + t * line.direction; + } + } + + return true; +} + +bool linearProgram2(const std::vector<Plane> &planes, size_t planeNo, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { + const float planeDist = planes[planeNo].point * planes[planeNo].normal; + const float planeDistSq = sqr(planeDist); + const float radiusSq = sqr(radius); + + if (planeDistSq > radiusSq) { + /* Max speed sphere fully invalidates plane planeNo. */ + return false; + } + + const float planeRadiusSq = radiusSq - planeDistSq; + + const Vector3 planeCenter = planeDist * planes[planeNo].normal; + + if (directionOpt) { + /* Project direction optVelocity on plane planeNo. */ + const Vector3 planeOptVelocity = optVelocity - (optVelocity * planes[planeNo].normal) * planes[planeNo].normal; + const float planeOptVelocityLengthSq = absSq(planeOptVelocity); + + if (planeOptVelocityLengthSq <= RVO_EPSILON) { + result = planeCenter; + } else { + result = planeCenter + std::sqrt(planeRadiusSq / planeOptVelocityLengthSq) * planeOptVelocity; + } + } else { + /* Project point optVelocity on plane planeNo. */ + result = optVelocity + ((planes[planeNo].point - optVelocity) * planes[planeNo].normal) * planes[planeNo].normal; + + /* If outside planeCircle, project on planeCircle. */ + if (absSq(result) > radiusSq) { + const Vector3 planeResult = result - planeCenter; + const float planeResultLengthSq = absSq(planeResult); + result = planeCenter + std::sqrt(planeRadiusSq / planeResultLengthSq) * planeResult; + } + } + + for (size_t i = 0; i < planeNo; ++i) { + if (planes[i].normal * (planes[i].point - result) > 0.0f) { + /* Result does not satisfy constraint i. Compute new optimal result. */ + /* Compute intersection line of plane i and plane planeNo. */ + Vector3 crossProduct = cross(planes[i].normal, planes[planeNo].normal); + + if (absSq(crossProduct) <= RVO_EPSILON) { + /* Planes planeNo and i are (almost) parallel, and plane i fully invalidates plane planeNo. */ + return false; + } + + Line line; + line.direction = normalize(crossProduct); + const Vector3 lineNormal = cross(line.direction, planes[planeNo].normal); + line.point = planes[planeNo].point + (((planes[i].point - planes[planeNo].point) * planes[i].normal) / (lineNormal * planes[i].normal)) * lineNormal; + + if (!linearProgram1(planes, i, line, radius, optVelocity, directionOpt, result)) { + return false; + } + } + } + + return true; +} + +size_t linearProgram3(const std::vector<Plane> &planes, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { + if (directionOpt) { + /* Optimize direction. Note that the optimization velocity is of unit length in this case. */ + result = optVelocity * radius; + } else if (absSq(optVelocity) > sqr(radius)) { + /* Optimize closest point and outside circle. */ + result = normalize(optVelocity) * radius; + } else { + /* Optimize closest point and inside circle. */ + result = optVelocity; + } + + for (size_t i = 0; i < planes.size(); ++i) { + if (planes[i].normal * (planes[i].point - result) > 0.0f) { + /* Result does not satisfy constraint i. Compute new optimal result. */ + const Vector3 tempResult = result; + + if (!linearProgram2(planes, i, radius, optVelocity, directionOpt, result)) { + result = tempResult; + return i; + } + } + } + + return planes.size(); +} + +void linearProgram4(const std::vector<Plane> &planes, size_t beginPlane, float radius, Vector3 &result) { + float distance = 0.0f; + + for (size_t i = beginPlane; i < planes.size(); ++i) { + if (planes[i].normal * (planes[i].point - result) > distance) { + /* Result does not satisfy constraint of plane i. */ + std::vector<Plane> projPlanes; + + for (size_t j = 0; j < i; ++j) { + Plane plane; + + const Vector3 crossProduct = cross(planes[j].normal, planes[i].normal); + + if (absSq(crossProduct) <= RVO_EPSILON) { + /* Plane i and plane j are (almost) parallel. */ + if (planes[i].normal * planes[j].normal > 0.0f) { + /* Plane i and plane j point in the same direction. */ + continue; + } else { + /* Plane i and plane j point in opposite direction. */ + plane.point = 0.5f * (planes[i].point + planes[j].point); + } + } else { + /* Plane.point is point on line of intersection between plane i and plane j. */ + const Vector3 lineNormal = cross(crossProduct, planes[i].normal); + plane.point = planes[i].point + (((planes[j].point - planes[i].point) * planes[j].normal) / (lineNormal * planes[j].normal)) * lineNormal; + } + + plane.normal = normalize(planes[j].normal - planes[i].normal); + projPlanes.push_back(plane); + } + + const Vector3 tempResult = result; + + if (linearProgram3(projPlanes, radius, planes[i].normal, true, result) < projPlanes.size()) { + /* This should in principle not happen. The result is by definition already in the feasible region of this linear program. If it fails, it is due to small floating point error, and the current result is kept. */ + result = tempResult; + } + + distance = planes[i].normal * (planes[i].point - result); + } + } +} +} // namespace RVO diff --git a/thirdparty/rvo2/src/Agent.h b/thirdparty/rvo2/src/Agent.h new file mode 100644 index 0000000000..16f75a08f6 --- /dev/null +++ b/thirdparty/rvo2/src/Agent.h @@ -0,0 +1,121 @@ +/* + * Agent.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +/** + * \file Agent.h + * \brief Contains the Agent class. + */ +#ifndef RVO_AGENT_H_ +#define RVO_AGENT_H_ + +#include "API.h" + +#include <cstddef> +#include <utility> +#include <vector> + +#include "Vector3.h" + +// Note: Slightly modified to work better in Godot. +// - The agent can be created by anyone. +// - The simulator pointer is removed. +// - The update function is removed. +// - The compute velocity function now need the timeStep. +// - Moved the `Plane` class here. +// - Added a new parameter `ignore_y_` in the `Agent`. This parameter is used to control a godot feature that allows to avoid collisions by moving on the horizontal plane. +namespace RVO { +/** + * \brief Defines a plane. + */ +class Plane { +public: + /** + * \brief A point on the plane. + */ + Vector3 point; + + /** + * \brief The normal to the plane. + */ + Vector3 normal; +}; + +/** + * \brief Defines an agent in the simulation. + */ +class Agent { + +public: + /** + * \brief Constructs an agent instance. + * \param sim The simulator instance. + */ + explicit Agent(); + + /** + * \brief Computes the neighbors of this agent. + */ + void computeNeighbors(class KdTree *kdTree_); + + /** + * \brief Computes the new velocity of this agent. + */ + void computeNewVelocity(float timeStep); + + /** + * \brief Inserts an agent neighbor into the set of neighbors of this agent. + * \param agent A pointer to the agent to be inserted. + * \param rangeSq The squared range around this agent. + */ + void insertAgentNeighbor(const Agent *agent, float &rangeSq); + + Vector3 newVelocity_; + Vector3 position_; + Vector3 prefVelocity_; + Vector3 velocity_; + size_t id_; + size_t maxNeighbors_; + float maxSpeed_; + float neighborDist_; + float radius_; + float timeHorizon_; + std::vector<std::pair<float, const Agent *> > agentNeighbors_; + std::vector<Plane> orcaPlanes_; + /// This is a godot feature that allows the Agent to avoid collision by mooving + /// on the horizontal plane. + bool ignore_y_; + + friend class KdTree; +}; +} // namespace RVO + +#endif /* RVO_AGENT_H_ */ diff --git a/thirdparty/rvo2/src/Definitions.h b/thirdparty/rvo2/src/Definitions.h new file mode 100644 index 0000000000..a73aca9908 --- /dev/null +++ b/thirdparty/rvo2/src/Definitions.h @@ -0,0 +1,55 @@ +/* + * Definitions.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +/** + * \file Definitions.h + * \brief Contains functions and constants used in multiple classes. + */ + +#ifndef RVO_DEFINITIONS_H_ +#define RVO_DEFINITIONS_H_ + +#include "API.h" + +namespace RVO { + /** + * \brief Computes the square of a float. + * \param scalar The float to be squared. + * \return The square of the float. + */ + inline float sqr(float scalar) + { + return scalar * scalar; + } +} + +#endif /* RVO_DEFINITIONS_H_ */ diff --git a/thirdparty/rvo2/src/KdTree.cpp b/thirdparty/rvo2/src/KdTree.cpp new file mode 100644 index 0000000000..bc224614f0 --- /dev/null +++ b/thirdparty/rvo2/src/KdTree.cpp @@ -0,0 +1,152 @@ +/* + * KdTree.cpp + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +#include "KdTree.h" + +#include <algorithm> + +#include "Agent.h" +#include "Definitions.h" + +namespace RVO { +const size_t RVO_MAX_LEAF_SIZE = 10; + +KdTree::KdTree() {} + +void KdTree::buildAgentTree(std::vector<Agent *> agents) { + agents_.swap(agents); + + if (!agents_.empty()) { + agentTree_.resize(2 * agents_.size() - 1); + buildAgentTreeRecursive(0, agents_.size(), 0); + } +} + +void KdTree::buildAgentTreeRecursive(size_t begin, size_t end, size_t node) { + agentTree_[node].begin = begin; + agentTree_[node].end = end; + agentTree_[node].minCoord = agents_[begin]->position_; + agentTree_[node].maxCoord = agents_[begin]->position_; + + for (size_t i = begin + 1; i < end; ++i) { + agentTree_[node].maxCoord[0] = std::max(agentTree_[node].maxCoord[0], agents_[i]->position_.x()); + agentTree_[node].minCoord[0] = std::min(agentTree_[node].minCoord[0], agents_[i]->position_.x()); + agentTree_[node].maxCoord[1] = std::max(agentTree_[node].maxCoord[1], agents_[i]->position_.y()); + agentTree_[node].minCoord[1] = std::min(agentTree_[node].minCoord[1], agents_[i]->position_.y()); + agentTree_[node].maxCoord[2] = std::max(agentTree_[node].maxCoord[2], agents_[i]->position_.z()); + agentTree_[node].minCoord[2] = std::min(agentTree_[node].minCoord[2], agents_[i]->position_.z()); + } + + if (end - begin > RVO_MAX_LEAF_SIZE) { + /* No leaf node. */ + size_t coord; + + if (agentTree_[node].maxCoord[0] - agentTree_[node].minCoord[0] > agentTree_[node].maxCoord[1] - agentTree_[node].minCoord[1] && agentTree_[node].maxCoord[0] - agentTree_[node].minCoord[0] > agentTree_[node].maxCoord[2] - agentTree_[node].minCoord[2]) { + coord = 0; + } else if (agentTree_[node].maxCoord[1] - agentTree_[node].minCoord[1] > agentTree_[node].maxCoord[2] - agentTree_[node].minCoord[2]) { + coord = 1; + } else { + coord = 2; + } + + const float splitValue = 0.5f * (agentTree_[node].maxCoord[coord] + agentTree_[node].minCoord[coord]); + + size_t left = begin; + + size_t right = end; + + while (left < right) { + while (left < right && agents_[left]->position_[coord] < splitValue) { + ++left; + } + + while (right > left && agents_[right - 1]->position_[coord] >= splitValue) { + --right; + } + + if (left < right) { + std::swap(agents_[left], agents_[right - 1]); + ++left; + --right; + } + } + + size_t leftSize = left - begin; + + if (leftSize == 0) { + ++leftSize; + ++left; + ++right; + } + + agentTree_[node].left = node + 1; + agentTree_[node].right = node + 2 * leftSize; + + buildAgentTreeRecursive(begin, left, agentTree_[node].left); + buildAgentTreeRecursive(left, end, agentTree_[node].right); + } +} + +void KdTree::computeAgentNeighbors(Agent *agent, float rangeSq) const { + queryAgentTreeRecursive(agent, rangeSq, 0); +} + +void KdTree::queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const { + if (agentTree_[node].end - agentTree_[node].begin <= RVO_MAX_LEAF_SIZE) { + for (size_t i = agentTree_[node].begin; i < agentTree_[node].end; ++i) { + agent->insertAgentNeighbor(agents_[i], rangeSq); + } + } else { + const float distSqLeft = sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[0] - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].left].maxCoord[0])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[1] - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].left].maxCoord[1])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[2] - agent->position_.z())) + sqr(std::max(0.0f, agent->position_.z() - agentTree_[agentTree_[node].left].maxCoord[2])); + + const float distSqRight = sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[0] - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].right].maxCoord[0])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[1] - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].right].maxCoord[1])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[2] - agent->position_.z())) + sqr(std::max(0.0f, agent->position_.z() - agentTree_[agentTree_[node].right].maxCoord[2])); + + if (distSqLeft < distSqRight) { + if (distSqLeft < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left); + + if (distSqRight < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right); + } + } + } else { + if (distSqRight < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right); + + if (distSqLeft < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left); + } + } + } + } +} +} // namespace RVO diff --git a/thirdparty/rvo2/src/KdTree.h b/thirdparty/rvo2/src/KdTree.h new file mode 100644 index 0000000000..1dbad00ea4 --- /dev/null +++ b/thirdparty/rvo2/src/KdTree.h @@ -0,0 +1,124 @@ +/* + * KdTree.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ +/** + * \file KdTree.h + * \brief Contains the KdTree class. + */ +#ifndef RVO_KD_TREE_H_ +#define RVO_KD_TREE_H_ + +#include "API.h" + +#include <cstddef> +#include <vector> + +#include "Vector3.h" + +// Note: Slightly modified to work better with Godot. +// - Removed `sim_`. +// - KdTree things are public +namespace RVO { +class Agent; +class RVOSimulator; + +/** + * \brief Defines <i>k</i>d-trees for agents in the simulation. + */ +class KdTree { +public: + /** + * \brief Defines an agent <i>k</i>d-tree node. + */ + class AgentTreeNode { + public: + /** + * \brief The beginning node number. + */ + size_t begin; + + /** + * \brief The ending node number. + */ + size_t end; + + /** + * \brief The left node number. + */ + size_t left; + + /** + * \brief The right node number. + */ + size_t right; + + /** + * \brief The maximum coordinates. + */ + Vector3 maxCoord; + + /** + * \brief The minimum coordinates. + */ + Vector3 minCoord; + }; + + /** + * \brief Constructs a <i>k</i>d-tree instance. + * \param sim The simulator instance. + */ + explicit KdTree(); + + /** + * \brief Builds an agent <i>k</i>d-tree. + */ + void buildAgentTree(std::vector<Agent *> agents); + + void buildAgentTreeRecursive(size_t begin, size_t end, size_t node); + + /** + * \brief Computes the agent neighbors of the specified agent. + * \param agent A pointer to the agent for which agent neighbors are to be computed. + * \param rangeSq The squared range around the agent. + */ + void computeAgentNeighbors(Agent *agent, float rangeSq) const; + + void queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const; + + std::vector<Agent *> agents_; + std::vector<AgentTreeNode> agentTree_; + + friend class Agent; + friend class RVOSimulator; +}; +} // namespace RVO + +#endif /* RVO_KD_TREE_H_ */ diff --git a/thirdparty/rvo2/src/RVO.h b/thirdparty/rvo2/src/RVO.h new file mode 100644 index 0000000000..81c9cbd8d3 --- /dev/null +++ b/thirdparty/rvo2/src/RVO.h @@ -0,0 +1,406 @@ +/* + * RVO.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +#ifndef RVO_RVO_H_ +#define RVO_RVO_H_ + +#include "API.h" +#include "RVOSimulator.h" +#include "Vector3.h" + +/** + + \file RVO.h + \brief Includes all public headers in the library. + + \namespace RVO + \brief Contains all classes, functions, and constants used in the library. + + \mainpage RVO2-3D Library + + \author Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, and Dinesh Manocha + + <b>RVO2-3D Library</b> is an easy-to-use C++ implementation of the + <a href="http://gamma.cs.unc.edu/CA/">Optimal Reciprocal Collision Avoidance</a> + (ORCA) formulation for multi-agent simulation in three dimensions. <b>RVO2-3D Library</b> + automatically uses parallelism for computing the motion of the agents if your machine + has multiple processors and your compiler supports <a href="http://www.openmp.org/"> + OpenMP</a>. + + Please follow the following steps to install and use <b>RVO2-3D Library</b>. + + - \subpage whatsnew + - \subpage building + - \subpage using + - \subpage params + + See the documentation of the RVO::RVOSimulator class for an exhaustive list of + public functions of <b>RVO2-3D Library</b>. + + <b>RVO2-3D Library</b>, accompanying example code, and this documentation is + released for educational, research, and non-profit purposes under the following + \subpage terms "terms and conditions". + + + \page whatsnew What Is New in RVO2-3D Library + + \section localca Three Dimensions + + In contrast to RVO2 Library, <b>RVO2-3D Library</b> operates in 3D workspaces. It uses + a three dimensional implementation of <a href="http://gamma.cs.unc.edu/CA/">Optimal + Reciprocal Collision Avoidance</a> (ORCA) for local collision avoidance. <b>RVO2-3D + Library</b> does not replace RVO2 Library; for 2D applications, RVO2 Library should + be used. + + \section structure Structure of RVO2-3D Library + + The structure of <b>RVO2-3D Library</b> is similar to that of RVO2 Library. + Users familiar with RVO2 Library should find little trouble in using <b>RVO2-3D + Library</b>. <b>RVO2-3D Library</b> currently does not support static obstacles. + + \page building Building RVO2-3D Library + + We assume that you have downloaded <b>RVO2-3D Library</b> and unpacked the ZIP + archive to a path <tt>$RVO_ROOT</tt>. + + \section xcode Apple Xcode 4.x + + Open <tt>$RVO_ROOT/RVO.xcodeproj</tt> and select the <tt>Static Library</tt> scheme. A static library <tt>libRVO.a</tt> will be built in the default build directory. + + \section cmake CMake + + Create and switch to your chosen build directory, e.g. <tt>$RVO_ROOT/build</tt>. + Run <tt>cmake</tt> inside the build directory on the source directory, e.g. + <tt>cmake $RVO_ROOT/src</tt>. Build files for the default generator for your + platform will be generated in the build directory. + + \section make GNU Make + + Switch to the source directory <tt>$RVO_ROOT/src</tt> and run <tt>make</tt>. + Public header files (<tt>API.h</tt>, <tt>RVO.h</tt>, <tt>RVOSimulator.h</tt>, and <tt>Vector3.h</tt>) will be copied to the <tt>$RVO_ROOT/include</tt> directory and a static library <tt>libRVO.a</tt> will be compiled into the + <tt>$RVO_ROOT/lib</tt> directory. + + \section visual Microsoft Visual Studio 2010 + + Open <tt>$RVO_ROOT/RVO.sln</tt> and select the <tt>RVOStatic</tt> project and a + configuration (<tt>Debug</tt> or <tt>Release</tt>). Public header files (<tt>API.h</tt>, <tt>RVO.h</tt>, <tt>RVOSimulator.h</tt>, and <tt>Vector3.h</tt>) will be copied to the <tt>$RVO_ROOT/include</tt> directory and a static library, e.g. <tt>RVO.lib</tt>, will be compiled into the + <tt>$RVO_ROOT/lib</tt> directory. + + + \page using Using RVO2-3D Library + + \section structure Structure + + A program performing an <b>RVO2-3D Library</b> simulation has the following global + structure. + + \code + #include <RVO.h> + + std::vector<RVO::Vector3> goals; + + int main() + { + // Create a new simulator instance. + RVO::RVOSimulator* sim = new RVO::RVOSimulator(); + + // Set up the scenario. + setupScenario(sim); + + // Perform (and manipulate) the simulation. + do { + updateVisualization(sim); + setPreferredVelocities(sim); + sim->doStep(); + } while (!reachedGoal(sim)); + + delete sim; + } + \endcode + + In order to use <b>RVO2-3D Library</b>, the user needs to include RVO.h. The first + step is then to create an instance of RVO::RVOSimulator. Then, the process + consists of two stages. The first stage is specifying the simulation scenario + and its parameters. In the above example program, this is done in the method + setupScenario(...), which we will discuss below. The second stage is the actual + performing of the simulation. + + In the above example program, simulation steps are taken until all + the agents have reached some predefined goals. Prior to each simulation step, + we set the preferred velocity for each agent, i.e. the + velocity the agent would have taken if there were no other agents around, in the + method setPreferredVelocities(...). The simulator computes the actual velocities + of the agents and attempts to follow the preferred velocities as closely as + possible while guaranteeing collision avoidance at the same time. During the + simulation, the user may want to retrieve information from the simulation for + instance to visualize the simulation. In the above example program, this is done + in the method updateVisualization(...), which we will discuss below. It is also + possible to manipulate the simulation during the simulation, for instance by + changing positions, radii, velocities, etc. of the agents. + + \section spec Setting up the Simulation Scenario + + A scenario that is to be simulated can be set up as follows. A scenario consists + of a set of agents that can be manually specified. Agents may be added anytime + before or during the simulation. The user may also want to define goal positions + of the agents, or a roadmap to guide the agents around obstacles. This is not done + in <b>RVO2-3D Library</b>, but needs to be taken care of in the user's external + application. + + The following example creates a scenario with eight agents exchanging positions. + + \code + void setupScenario(RVO::RVOSimulator* sim) { + // Specify global time step of the simulation. + sim->setTimeStep(0.25f); + + // Specify default parameters for agents that are subsequently added. + sim->setAgentDefaults(15.0f, 10, 10.0f, 2.0f, 2.0f); + + // Add agents, specifying their start position. + sim->addAgent(RVO::Vector3(-50.0f, -50.0f, -50.0f)); + sim->addAgent(RVO::Vector3(50.0f, -50.0f, -50.0f)); + sim->addAgent(RVO::Vector3(50.0f, 50.0f, -50.0f)); + sim->addAgent(RVO::Vector3(-50.0f, 50.0f, -50.0f)); + sim->addAgent(RVO::Vector3(-50.0f, -50.0f, 50.0f)); + sim->addAgent(RVO::Vector3(50.0f, -50.0f, 50.0f)); + sim->addAgent(RVO::Vector3(50.0f, 50.0f, 50.0f)); + sim->addAgent(RVO::Vector3(-50.0f, 50.0f, 50.0f)); + + // Create goals (simulator is unaware of these). + for (size_t i = 0; i < sim->getNumAgents(); ++i) { + goals.push_back(-sim->getAgentPosition(i)); + } + } + \endcode + + See the documentation on RVO::RVOSimulator for a full overview of the + functionality to specify scenarios. + + \section ret Retrieving Information from the Simulation + + During the simulation, the user can extract information from the simulation for + instance for visualization purposes, or to determine termination conditions of + the simulation. In the example program above, visualization is done in the + updateVisualization(...) method. Below we give an example that simply writes + the positions of each agent in each time step to the standard output. The + termination condition is checked in the reachedGoal(...) method. Here we give an + example that returns true if all agents are within one radius of their goals. + + \code + void updateVisualization(RVO::RVOSimulator* sim) { + // Output the current global time. + std::cout << sim->getGlobalTime() << " "; + + // Output the position for all the agents. + for (size_t i = 0; i < sim->getNumAgents(); ++i) { + std::cout << sim->getAgentPosition(i) << " "; + } + + std::cout << std::endl; + } + \endcode + + \code + bool reachedGoal(RVO::RVOSimulator* sim) { + // Check whether all agents have arrived at their goals. + for (size_t i = 0; i < sim->getNumAgents(); ++i) { + if (absSq(goals[i] - sim->getAgentPosition(i)) > sim->getAgentRadius(i) * sim->getAgentRadius(i)) { + // Agent is further away from its goal than one radius. + return false; + } + } + return true; + } + \endcode + + Using similar functions as the ones used in this example, the user can access + information about other parameters of the agents, as well as the global + parameters, and the obstacles. See the documentation of the class + RVO::RVOSimulator for an exhaustive list of public functions for retrieving + simulation information. + + \section manip Manipulating the Simulation + + During the simulation, the user can manipulate the simulation, for instance by + changing the global parameters, or changing the parameters of the agents + (potentially causing abrupt different behavior). It is also possible to give the + agents a new position, which make them jump through the scene. + New agents can be added to the simulation at any time. + + See the documentation of the class RVO::RVOSimulator for an exhaustive list of + public functions for manipulating the simulation. + + To provide global guidance to the agents, the preferred velocities of the agents + can be changed ahead of each simulation step. In the above example program, this + happens in the method setPreferredVelocities(...). Here we give an example that + simply sets the preferred velocity to the unit vector towards the agent's goal + for each agent (i.e., the preferred speed is 1.0). + + \code + void setPreferredVelocities(RVO::RVOSimulator* sim) { + // Set the preferred velocity for each agent. + for (size_t i = 0; i < sim->getNumAgents(); ++i) { + if (absSq(goals[i] - sim->getAgentPosition(i)) < sim->getAgentRadius(i) * sim->getAgentRadius(i) ) { + // Agent is within one radius of its goal, set preferred velocity to zero + sim->setAgentPrefVelocity(i, RVO::Vector3()); + } else { + // Agent is far away from its goal, set preferred velocity as unit vector towards agent's goal. + sim->setAgentPrefVelocity(i, normalize(goals[i] - sim->getAgentPosition(i))); + } + } + } + \endcode + + \section example Example Programs + + <b>RVO2-3D Library</b> is accompanied by one example program, which can be found in the + <tt>$RVO_ROOT/examples</tt> directory. The example is named Sphere, and + contains the following demonstration scenario: + <table border="0" cellpadding="3" width="100%"> + <tr> + <td valign="top" width="100"><b>Sphere</b></td> + <td valign="top">A scenario in which 812 agents, initially positioned evenly + distributed on a sphere, move to the antipodal position on the + sphere. </td> + </tr> + </table> + + + \page params Parameter Overview + + \section globalp Global Parameters + + <table border="0" cellpadding="3" width="100%"> + <tr> + <td valign="top" width="150"><strong>Parameter</strong></td> + <td valign="top" width="150"><strong>Type (unit)</strong></td> + <td valign="top"><strong>Meaning</strong></td> + </tr> + <tr> + <td valign="top">timeStep</td> + <td valign="top">float (time)</td> + <td valign="top">The time step of the simulation. Must be positive.</td> + </tr> + </table> + + \section agent Agent Parameters + + <table border="0" cellpadding="3" width="100%"> + <tr> + <td valign="top" width="150"><strong>Parameter</strong></td> + <td valign="top" width="150"><strong>Type (unit)</strong></td> + <td valign="top"><strong>Meaning</strong></td> + </tr> + <tr> + <td valign="top">maxNeighbors</td> + <td valign="top">size_t</td> + <td valign="top">The maximum number of other agents the agent takes into + account in the navigation. The larger this number, the + longer the running time of the simulation. If the number is + too low, the simulation will not be safe.</td> + </tr> + <tr> + <td valign="top">maxSpeed</td> + <td valign="top">float (distance/time)</td> + <td valign="top">The maximum speed of the agent. Must be non-negative.</td> + </tr> + <tr> + <td valign="top">neighborDist</td> + <td valign="top">float (distance)</td> + <td valign="top">The maximum distance (center point to center point) to + other agents the agent takes into account in the + navigation. The larger this number, the longer the running + time of the simulation. If the number is too low, the + simulation will not be safe. Must be non-negative.</td> + </tr> + <tr> + <td valign="top" width="150">position</td> + <td valign="top" width="150">RVO::Vector3 (distance, distance)</td> + <td valign="top">The current position of the agent.</td> + </tr> + <tr> + <td valign="top" width="150">prefVelocity</td> + <td valign="top" width="150">RVO::Vector3 (distance/time, distance/time) + </td> + <td valign="top">The current preferred velocity of the agent. This is the + velocity the agent would take if no other agents or + obstacles were around. The simulator computes an actual + velocity for the agent that follows the preferred velocity + as closely as possible, but at the same time guarantees + collision avoidance.</td> + </tr> + <tr> + <td valign="top">radius</td> + <td valign="top">float (distance)</td> + <td valign="top">The radius of the agent. Must be non-negative.</td> + </tr> + <tr> + <td valign="top" width="150">timeHorizon</td> + <td valign="top" width="150">float (time)</td> + <td valign="top">The minimum amount of time for which the agent's velocities + that are computed by the simulation are safe with respect + to other agents. The larger this number, the sooner this + agent will respond to the presence of other agents, but the + less freedom the agent has in choosing its velocities. + Must be positive. </td> + </tr> + <tr> + <td valign="top" width="150">velocity</td> + <td valign="top" width="150">RVO::Vector3 (distance/time, distance/time) + </td> + <td valign="top">The (current) velocity of the agent.</td> + </tr> + </table> + + + \page terms Terms and Conditions + + <b>RVO2-3D Library</b> + + Copyright 2008 University of North Carolina at Chapel Hill + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + + */ + +#endif /* RVO_RVO_H_ */ diff --git a/thirdparty/rvo2/src/Vector3.h b/thirdparty/rvo2/src/Vector3.h new file mode 100644 index 0000000000..8c8835c865 --- /dev/null +++ b/thirdparty/rvo2/src/Vector3.h @@ -0,0 +1,335 @@ +/* + * Vector3.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to <geom@cs.unc.edu>. + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * <http://gamma.cs.unc.edu/RVO2/> + */ + +/** + * \file Vector3.h + * \brief Contains the Vector3 class. + */ +#ifndef RVO_VECTOR3_H_ +#define RVO_VECTOR3_H_ + +#include "API.h" + +#include <cmath> +#include <cstddef> +#include <ostream> + +namespace RVO { + /** + * \brief Defines a three-dimensional vector. + */ + class Vector3 { + public: + /** + * \brief Constructs and initializes a three-dimensional vector instance to zero. + */ + RVO_API inline Vector3() + { + val_[0] = 0.0f; + val_[1] = 0.0f; + val_[2] = 0.0f; + } + + /** + * \brief Constructs and initializes a three-dimensional vector from the specified three-element array. + * \param val The three-element array containing the xyz-coordinates. + */ + RVO_API inline explicit Vector3(const float val[3]) + { + val_[0] = val[0]; + val_[1] = val[1]; + val_[2] = val[2]; + } + + /** + * \brief Constructs and initializes a three-dimensional vector from the specified xyz-coordinates. + * \param x The x-coordinate of the three-dimensional vector. + * \param y The y-coordinate of the three-dimensional vector. + * \param z The z-coordinate of the three-dimensional vector. + */ + RVO_API inline Vector3(float x, float y, float z) + { + val_[0] = x; + val_[1] = y; + val_[2] = z; + } + + /** + * \brief Returns the x-coordinate of this three-dimensional vector. + * \return The x-coordinate of the three-dimensional vector. + */ + RVO_API inline float x() const { return val_[0]; } + + /** + * \brief Returns the y-coordinate of this three-dimensional vector. + * \return The y-coordinate of the three-dimensional vector. + */ + RVO_API inline float y() const { return val_[1]; } + + /** + * \brief Returns the z-coordinate of this three-dimensional vector. + * \return The z-coordinate of the three-dimensional vector. + */ + RVO_API inline float z() const { return val_[2]; } + + /** + * \brief Returns the specified coordinate of this three-dimensional vector. + * \param i The coordinate that should be returned (0 <= i < 3). + * \return The specified coordinate of the three-dimensional vector. + */ + RVO_API inline float operator[](size_t i) const { return val_[i]; } + + /** + * \brief Returns a reference to the specified coordinate of this three-dimensional vector. + * \param i The coordinate to which a reference should be returned (0 <= i < 3). + * \return A reference to the specified coordinate of the three-dimensional vector. + */ + RVO_API inline float &operator[](size_t i) { return val_[i]; } + + /** + * \brief Computes the negation of this three-dimensional vector. + * \return The negation of this three-dimensional vector. + */ + RVO_API inline Vector3 operator-() const + { + return Vector3(-val_[0], -val_[1], -val_[2]); + } + + /** + * \brief Computes the dot product of this three-dimensional vector with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the dot product should be computed. + * \return The dot product of this three-dimensional vector with a specified three-dimensional vector. + */ + RVO_API inline float operator*(const Vector3 &vector) const + { + return val_[0] * vector[0] + val_[1] * vector[1] + val_[2] * vector[2]; + } + + /** + * \brief Computes the scalar multiplication of this three-dimensional vector with the specified scalar value. + * \param scalar The scalar value with which the scalar multiplication should be computed. + * \return The scalar multiplication of this three-dimensional vector with a specified scalar value. + */ + RVO_API inline Vector3 operator*(float scalar) const + { + return Vector3(val_[0] * scalar, val_[1] * scalar, val_[2] * scalar); + } + + /** + * \brief Computes the scalar division of this three-dimensional vector with the specified scalar value. + * \param scalar The scalar value with which the scalar division should be computed. + * \return The scalar division of this three-dimensional vector with a specified scalar value. + */ + RVO_API inline Vector3 operator/(float scalar) const + { + const float invScalar = 1.0f / scalar; + + return Vector3(val_[0] * invScalar, val_[1] * invScalar, val_[2] * invScalar); + } + + /** + * \brief Computes the vector sum of this three-dimensional vector with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector sum should be computed. + * \return The vector sum of this three-dimensional vector with a specified three-dimensional vector. + */ + RVO_API inline Vector3 operator+(const Vector3 &vector) const + { + return Vector3(val_[0] + vector[0], val_[1] + vector[1], val_[2] + vector[2]); + } + + /** + * \brief Computes the vector difference of this three-dimensional vector with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector difference should be computed. + * \return The vector difference of this three-dimensional vector with a specified three-dimensional vector. + */ + RVO_API inline Vector3 operator-(const Vector3 &vector) const + { + return Vector3(val_[0] - vector[0], val_[1] - vector[1], val_[2] - vector[2]); + } + + /** + * \brief Tests this three-dimensional vector for equality with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which to test for equality. + * \return True if the three-dimensional vectors are equal. + */ + RVO_API inline bool operator==(const Vector3 &vector) const + { + return val_[0] == vector[0] && val_[1] == vector[1] && val_[2] == vector[2]; + } + + /** + * \brief Tests this three-dimensional vector for inequality with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which to test for inequality. + * \return True if the three-dimensional vectors are not equal. + */ + RVO_API inline bool operator!=(const Vector3 &vector) const + { + return val_[0] != vector[0] || val_[1] != vector[1] || val_[2] != vector[2]; + } + + /** + * \brief Sets the value of this three-dimensional vector to the scalar multiplication of itself with the specified scalar value. + * \param scalar The scalar value with which the scalar multiplication should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator*=(float scalar) + { + val_[0] *= scalar; + val_[1] *= scalar; + val_[2] *= scalar; + + return *this; + } + + /** + * \brief Sets the value of this three-dimensional vector to the scalar division of itself with the specified scalar value. + * \param scalar The scalar value with which the scalar division should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator/=(float scalar) + { + const float invScalar = 1.0f / scalar; + + val_[0] *= invScalar; + val_[1] *= invScalar; + val_[2] *= invScalar; + + return *this; + } + + /** + * \brief Sets the value of this three-dimensional vector to the vector + * sum of itself with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector sum should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator+=(const Vector3 &vector) + { + val_[0] += vector[0]; + val_[1] += vector[1]; + val_[2] += vector[2]; + + return *this; + } + + /** + * \brief Sets the value of this three-dimensional vector to the vector difference of itself with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector difference should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator-=(const Vector3 &vector) + { + val_[0] -= vector[0]; + val_[1] -= vector[1]; + val_[2] -= vector[2]; + + return *this; + } + + private: + float val_[3]; + }; + + + /** + * \relates Vector3 + * \brief Computes the scalar multiplication of the specified three-dimensional vector with the specified scalar value. + * \param scalar The scalar value with which the scalar multiplication should be computed. + * \param vector The three-dimensional vector with which the scalar multiplication should be computed. + * \return The scalar multiplication of the three-dimensional vector with the scalar value. + */ + inline Vector3 operator*(float scalar, const Vector3 &vector) + { + return Vector3(scalar * vector[0], scalar * vector[1], scalar * vector[2]); + } + + /** + * \relates Vector3 + * \brief Computes the cross product of the specified three-dimensional vectors. + * \param vector1 The first vector with which the cross product should be computed. + * \param vector2 The second vector with which the cross product should be computed. + * \return The cross product of the two specified vectors. + */ + inline Vector3 cross(const Vector3 &vector1, const Vector3 &vector2) + { + return Vector3(vector1[1] * vector2[2] - vector1[2] * vector2[1], vector1[2] * vector2[0] - vector1[0] * vector2[2], vector1[0] * vector2[1] - vector1[1] * vector2[0]); + } + + /** + * \relates Vector3 + * \brief Inserts the specified three-dimensional vector into the specified output stream. + * \param os The output stream into which the three-dimensional vector should be inserted. + * \param vector The three-dimensional vector which to insert into the output stream. + * \return A reference to the output stream. + */ + inline std::ostream &operator<<(std::ostream &os, const Vector3 &vector) + { + os << "(" << vector[0] << "," << vector[1] << "," << vector[2] << ")"; + + return os; + } + + /** + * \relates Vector3 + * \brief Computes the length of a specified three-dimensional vector. + * \param vector The three-dimensional vector whose length is to be computed. + * \return The length of the three-dimensional vector. + */ + inline float abs(const Vector3 &vector) + { + return std::sqrt(vector * vector); + } + + /** + * \relates Vector3 + * \brief Computes the squared length of a specified three-dimensional vector. + * \param vector The three-dimensional vector whose squared length is to be computed. + * \return The squared length of the three-dimensional vector. + */ + inline float absSq(const Vector3 &vector) + { + return vector * vector; + } + + /** + * \relates Vector3 + * \brief Computes the normalization of the specified three-dimensional vector. + * \param vector The three-dimensional vector whose normalization is to be computed. + * \return The normalization of the three-dimensional vector. + */ + inline Vector3 normalize(const Vector3 &vector) + { + return vector / abs(vector); + } +} + +#endif |