From daaba487704577efc014bdd0ef268eccd0f872a7 Mon Sep 17 00:00:00 2001 From: Eunki Hong Date: Mon, 30 Jan 2023 00:07:00 +0900 Subject: [PATCH] Add PathFinder algorithm using SPFA Add new default algorithm using SPFA. And also, SPFA with doubleway to reduce memory usage per query. Change-Id: Ia8f7bf98fbc6e94c2e0e47251814b61cf8f9b9d2 Signed-off-by: Eunki Hong --- .../src/dali-scene3d/utc-Dali-PathFinding.cpp | 173 +++++--- .../algorithm/path-finder-spfa-double-way.cpp | 476 +++++++++++++++++++++ .../algorithm/path-finder-spfa-double-way.h | 105 +++++ .../internal/algorithm/path-finder-spfa.cpp | 310 ++++++++++++++ dali-scene3d/internal/algorithm/path-finder-spfa.h | 89 ++++ dali-scene3d/internal/file.list | 2 + dali-scene3d/public-api/algorithm/path-finder.cpp | 26 +- dali-scene3d/public-api/algorithm/path-finder.h | 13 +- 8 files changed, 1118 insertions(+), 76 deletions(-) create mode 100644 dali-scene3d/internal/algorithm/path-finder-spfa-double-way.cpp create mode 100644 dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h create mode 100644 dali-scene3d/internal/algorithm/path-finder-spfa.cpp create mode 100644 dali-scene3d/internal/algorithm/path-finder-spfa.h diff --git a/automated-tests/src/dali-scene3d/utc-Dali-PathFinding.cpp b/automated-tests/src/dali-scene3d/utc-Dali-PathFinding.cpp index c75074a..8866f36 100644 --- a/automated-tests/src/dali-scene3d/utc-Dali-PathFinding.cpp +++ b/automated-tests/src/dali-scene3d/utc-Dali-PathFinding.cpp @@ -28,12 +28,40 @@ bool CompareResults( const std::vector& nodes, const WayPointList& way { if(nodes.size() != waypoints.size()) { + std::ostringstream oss; + oss << "expect indexs : ["; + for(const auto& index : nodes) + { + oss << index << ", "; + } + oss << "]\n"; + oss << "your indexs : ["; + for(const auto& waypoint : waypoints) + { + oss << waypoint.GetNavigationMeshFaceIndex() << ", "; + } + oss << "]\n"; + tet_printf("%s\n",oss.str().c_str()); return false; } for(auto i = 0u; i < nodes.size(); ++i ) { if(nodes[i] != waypoints[i].GetNavigationMeshFaceIndex()) { + std::ostringstream oss; + oss << "expect indexs : ["; + for(const auto& index : nodes) + { + oss << index << ", "; + } + oss << "]\n"; + oss << "your indexs : ["; + for(const auto& waypoint : waypoints) + { + oss << waypoint.GetNavigationMeshFaceIndex() << ", "; + } + oss << "]\n"; + tet_printf("%s\n",oss.str().c_str()); return false; } } @@ -76,97 +104,116 @@ void printWaypointForPython( WayPointList& waypoints) tet_printf( "]"); } -int UtcDaliPathFinderDjikstraFindPath0(void) +int UtcDaliPathFinderFindShortestPath0(void) { auto navmesh = NavigationMeshFactory::CreateFromFile( "resources/navmesh-test.bin"); - auto pathfinder = PathFinder::New( *navmesh, PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH ); - - DALI_TEST_CHECK(navmesh); - DALI_TEST_CHECK(pathfinder); + std::vector testAlgorithms = { + PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH, + PathFinderAlgorithm::SPFA, + }; + for(const auto& algorithm : testAlgorithms) { - auto waypoints = pathfinder->FindPath(18, 139); - DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION); + tet_printf("Test algorithm type : %d\n", static_cast(algorithm)); + auto pathfinder = PathFinder::New( *navmesh, algorithm ); - // Results are verified in the Blender - std::vector expectedResults = - {18, 97, 106, 82, 50, 139}; + DALI_TEST_CHECK(navmesh); + DALI_TEST_CHECK(pathfinder); - DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION); - } - //printWaypointForPython(waypoints); - - { - // Top floor middle to the tree + { + auto waypoints = pathfinder->FindPath(18, 139); + DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION); - auto waypoints = pathfinder->FindPath(18, 157); - DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION); + // Results are verified in the Blender + std::vector expectedResults = + {18, 97, 106, 82, 50, 139}; + DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION); + } //printWaypointForPython(waypoints); - // Results are verified in the Blender - std::vector expectedResults = - {18, 97, 106, 82, 50, 6, 89, 33, 157}; + { + // Top floor middle to the tree + + auto waypoints = pathfinder->FindPath(18, 157); + DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION); + + //printWaypointForPython(waypoints); - DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION); + // Results are verified in the Blender + std::vector expectedResults = + {18, 97, 106, 82, 50, 6, 89, 33, 157}; + DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION); + + } } END_TEST; } -int UtcDaliPathFinderDjikstraFindPath1(void) +int UtcDaliPathFinderFindShortestPath1(void) { auto navmesh = NavigationMeshFactory::CreateFromFile( "resources/navmesh-test.bin"); // All coordinates in navmesh local space navmesh->SetSceneTransform( Matrix(Matrix::IDENTITY)); - auto pathfinder = PathFinder::New( *navmesh, PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH ); - - DALI_TEST_CHECK(navmesh); - DALI_TEST_CHECK(pathfinder); + std::vector testAlgorithms = { + PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH, + PathFinderAlgorithm::SPFA, + PathFinderAlgorithm::SPFA_DOUBLE_WAY, /* Note : Even this algorithm doesn't found shortest path, UTC will pass. */ + }; + for(const auto& algorithm : testAlgorithms) { - Vector3 from(-6.0767, -1.7268, 0.1438); // ground floor - Vector3 to(-6.0767, -1.7268, 4.287); // first floor - - auto waypoints = pathfinder->FindPath(from, to); - DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION); - - // Results are verified in the Blender - std::vector expectedResults = - {154, 58, 85, 106, 128, 132, 137}; + tet_printf("Test algorithm type : %d\n", static_cast(algorithm)); + auto pathfinder = PathFinder::New( *navmesh, algorithm ); - DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION); + DALI_TEST_CHECK(navmesh); + DALI_TEST_CHECK(pathfinder); - // Verify last and first points by finding floor points { - Vector3 verifyPos = Vector3::ZERO; - uint32_t verifyIndex = NavigationMesh::NULL_FACE; - auto result = navmesh->FindFloor(from, verifyPos, verifyIndex); - - DALI_TEST_EQUALS(result, true, TEST_LOCATION); - DALI_TEST_EQUALS(verifyPos, waypoints[0].GetScenePosition(), TEST_LOCATION); - DALI_TEST_EQUALS(verifyIndex, waypoints[0].GetNavigationMeshFaceIndex(), TEST_LOCATION); - - // Verified with Blender - Vector2 local(1.064201f, -0.273200f); - DALI_TEST_EQUALS(local, waypoints[0].GetFaceLocalSpacePosition(), TEST_LOCATION); - } - - { - Vector3 verifyPos = Vector3::ZERO; - uint32_t verifyIndex = NavigationMesh::NULL_FACE; - auto result = navmesh->FindFloor(to, verifyPos, verifyIndex); - - DALI_TEST_EQUALS(result, true, TEST_LOCATION); - DALI_TEST_EQUALS(verifyPos, waypoints.back().GetScenePosition(), TEST_LOCATION); - DALI_TEST_EQUALS(verifyIndex, waypoints.back().GetNavigationMeshFaceIndex(), TEST_LOCATION); - - // Verified with Blender - Vector2 local(0.165907f, 0.142597f); - DALI_TEST_EQUALS(local, waypoints.back().GetFaceLocalSpacePosition(), TEST_LOCATION); + Vector3 from(-6.0767, -1.7268, 0.1438); // ground floor + Vector3 to(-6.0767, -1.7268, 4.287); // first floor + + auto waypoints = pathfinder->FindPath(from, to); + DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION); + + // Results are verified in the Blender + std::vector expectedResults = + {154, 58, 85, 106, 128, 132, 137}; + + DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION); + + // Verify last and first points by finding floor points + { + Vector3 verifyPos = Vector3::ZERO; + uint32_t verifyIndex = NavigationMesh::NULL_FACE; + auto result = navmesh->FindFloor(from, verifyPos, verifyIndex); + + DALI_TEST_EQUALS(result, true, TEST_LOCATION); + DALI_TEST_EQUALS(verifyPos, waypoints[0].GetScenePosition(), TEST_LOCATION); + DALI_TEST_EQUALS(verifyIndex, waypoints[0].GetNavigationMeshFaceIndex(), TEST_LOCATION); + + // Verified with Blender + Vector2 local(1.064201f, -0.273200f); + DALI_TEST_EQUALS(local, waypoints[0].GetFaceLocalSpacePosition(), TEST_LOCATION); + } + + { + Vector3 verifyPos = Vector3::ZERO; + uint32_t verifyIndex = NavigationMesh::NULL_FACE; + auto result = navmesh->FindFloor(to, verifyPos, verifyIndex); + + DALI_TEST_EQUALS(result, true, TEST_LOCATION); + DALI_TEST_EQUALS(verifyPos, waypoints.back().GetScenePosition(), TEST_LOCATION); + DALI_TEST_EQUALS(verifyIndex, waypoints.back().GetNavigationMeshFaceIndex(), TEST_LOCATION); + + // Verified with Blender + Vector2 local(0.165907f, 0.142597f); + DALI_TEST_EQUALS(local, waypoints.back().GetFaceLocalSpacePosition(), TEST_LOCATION); + } } } diff --git a/dali-scene3d/internal/algorithm/path-finder-spfa-double-way.cpp b/dali-scene3d/internal/algorithm/path-finder-spfa-double-way.cpp new file mode 100644 index 0000000..d29a6f2 --- /dev/null +++ b/dali-scene3d/internal/algorithm/path-finder-spfa-double-way.cpp @@ -0,0 +1,476 @@ +/* + * Copyright (c) 2023 Samsung Electronics Co., Ltd. + * + * 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. + */ + +// INTERNAL INCLUDES +#include +#include +#include + +// EXTERNAL INCLUDES +#include +#include +#include + +using WayPointList = Dali::Scene3D::Algorithm::WayPointList; + +namespace +{ +constexpr float PRIORITY_SCALE_FACTOR = 0.7f; ///< The value of heuristic factor that how much will you consider + /// direction of source --> target. If 0.0f, we will use only dist. + +/** + * @brief Get the Component Id object + * + * @param[in,out] components Container of components id stored. + * @param[in] index index what we want to get components's id. + * @return uint32_t top-value of this components. + */ +uint32_t GetComponentId(std::vector& components, uint32_t index) +{ + if(components[index] == index) + { + return index; + } + // Get my parent's components id, and update myself. + uint32_t ret = GetComponentId(components, components[index]); + return components[index] = ret; +} + +/** + * @brief Combine two elements by Union-Find algorithm. + * + * @param[in,out] components Container of components id stored. + * @param[in,out] componentsLevel Container of components level stored. + * @param[in] index0 index of components what we want to be combined. + * @param[in] index1 index of components what we want to be combined. + */ +void ComponentsCombine(std::vector& components, std::vector& componentsLevel, uint32_t index0, uint32_t index1) +{ + uint32_t p0 = GetComponentId(components, index0); + uint32_t p1 = GetComponentId(components, index1); + if(p0 == p1) + { + return; + } + + if(componentsLevel[p0] < componentsLevel[p1]) + { + components[p0] = p1; + } + else + { + components[p1] = p0; + if(componentsLevel[p0] == componentsLevel[p1]) + { + ++componentsLevel[p0]; + } + } +} +} // namespace + +namespace Dali::Scene3D::Internal::Algorithm +{ +PathFinderAlgorithmSPFADoubleWay::PathFinderAlgorithmSPFADoubleWay(Dali::Scene3D::Algorithm::NavigationMesh& navMesh) +: mNavigationMesh(&GetImplementation(navMesh)) +{ + PrepareData(); +} + +PathFinderAlgorithmSPFADoubleWay::~PathFinderAlgorithmSPFADoubleWay() = default; + +float PathFinderAlgorithmSPFADoubleWay::DistancePanaltyCalculate(uint32_t index) const noexcept +{ + return dist[index] - priority[index] * PRIORITY_SCALE_FACTOR; +} + +Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFADoubleWay::FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo) +{ + Dali::Vector3 outPosFrom; + uint32_t polyIndexFrom; + auto result = mNavigationMesh->FindFloor(positionFrom, outPosFrom, polyIndexFrom); + + Scene3D::Algorithm::WayPointList waypoints; + + if(result) + { + Dali::Vector3 outPosTo; + uint32_t polyIndexTo; + result = mNavigationMesh->FindFloor(positionTo, outPosTo, polyIndexTo); + + if(result) + { + // Get waypoints + waypoints = FindPath(polyIndexFrom, polyIndexTo); + + // replace first and last waypoint + auto& wpFrom = static_cast(waypoints[0]); + auto& wpTo = static_cast(waypoints.back()); + + Vector2 fromCenter(wpFrom.point3d.x, wpFrom.point3d.y); + wpFrom.point3d = outPosFrom; + wpFrom.point2d = fromCenter - Vector2(outPosFrom.x, outPosFrom.y); + + Vector2 toCenter(wpTo.point3d.x, wpTo.point3d.y); + wpTo.point3d = outPosTo; + wpTo.point2d = toCenter - Vector2(outPosTo.x, outPosTo.y); + wpTo.point3d = outPosTo; + } + } + + // Returns waypoints with non-zero size of empty vector in case of failure (no path to be found) + return waypoints; +} + +Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFADoubleWay::FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) +{ + // Fast return if source and target index is same. + if(sourcePolyIndex == targetPolyIndex) + { + WayPointList waypoints; + waypoints.resize(1); + + auto& wp = static_cast(waypoints[0]); + wp.face = mNavigationMesh->GetFace(sourcePolyIndex); + wp.nodeIndex = sourcePolyIndex; + wp.edge = nullptr; + + return OptimizeWaypoints(waypoints); + } + + // Fast return if source and target index is not in same components. + // That mean, there is no path. Return empty list. + if(GetComponentId(componentIds, sourcePolyIndex) != GetComponentId(componentIds, targetPolyIndex)) + { + return WayPointList(); + } + + // pair + using queueItem = std::pair; + + std::list nodeQueue; + + std::unordered_set usedPolyIndexs[2]; + + // Set distance of source and target + dist[sourcePolyIndex] = 0.0f; + dist[targetPolyIndex] = 0.0f; + priority[sourcePolyIndex] = 0.0f; + priority[targetPolyIndex] = 0.0f; + queued[sourcePolyIndex] = true; + queued[targetPolyIndex] = true; + nodeQueue.push_back(std::make_pair(sourcePolyIndex, 0)); + nodeQueue.push_back(std::make_pair(targetPolyIndex, 1)); + usedPolyIndexs[0].insert(sourcePolyIndex); + usedPolyIndexs[1].insert(targetPolyIndex); + + bool foundPath = false; + uint32_t forwardEndIndex = Scene3D::Algorithm::NavigationMesh::NULL_FACE; + uint32_t backwardStartIndex = Scene3D::Algorithm::NavigationMesh::NULL_FACE; + + const auto sourcePos = Dali::Vector3(Face(sourcePolyIndex)->center); + const auto targetPos = Dali::Vector3(Face(targetPolyIndex)->center); + Vector3 direction = targetPos - sourcePos; + direction.Normalize(); + + // Note : we always success to found path since source and target is in same components. + while(!foundPath) + { + // find minimum distance + auto minDistIndex = nodeQueue.front().first; + auto isBackward = nodeQueue.front().second; + nodeQueue.pop_front(); + queued[minDistIndex] = false; + + // check the neighbours + for(auto i = 0u; i < 3 && !foundPath; ++i) + { + auto nIndex = mNodes[minDistIndex].faces[i]; + if(nIndex != Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + if(usedPolyIndexs[!isBackward].count(nIndex)) + { + // We found path! + foundPath = true; + if(isBackward) + { + forwardEndIndex = nIndex; + backwardStartIndex = minDistIndex; + } + else + { + forwardEndIndex = minDistIndex; + backwardStartIndex = nIndex; + } + break; + } + + usedPolyIndexs[isBackward].insert(nIndex); + + auto alt = dist[minDistIndex] + mNodes[minDistIndex].weight[i]; + if(alt < dist[nIndex]) + { + dist[nIndex] = alt; + + if(isBackward) + { + prevBackward[nIndex] = minDistIndex; + if(priority[nIndex] < 0.0f) + { + const auto currentPos = Dali::Vector3(Face(nIndex)->center); + Vector3 diff = currentPos - targetPos; + priority[nIndex] = std::max(0.0f, -direction.Dot(diff)); + } + } + else + { + prevForward[nIndex] = minDistIndex; + if(priority[nIndex] < 0.0f) + { + const auto currentPos = Dali::Vector3(Face(nIndex)->center); + Vector3 diff = currentPos - sourcePos; + priority[nIndex] = std::max(0.0f, direction.Dot(diff)); + } + } + + if(!queued[nIndex]) + { + queued[nIndex] = true; + if(!nodeQueue.empty() && DistancePanaltyCalculate(nIndex) < DistancePanaltyCalculate(nodeQueue.front().first)) + { + nodeQueue.push_front(std::make_pair(nIndex, isBackward)); + } + else + { + nodeQueue.push_back(std::make_pair(nIndex, isBackward)); + } + } + } + } + } + } + + // Build path of face index + std::list q; + { + uint32_t u = forwardEndIndex; + while(u != Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + q.push_front(u); + u = prevForward[u]; + } + } + { + uint32_t u = backwardStartIndex; + while(u != Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + q.push_back(u); + u = prevBackward[u]; + } + } + + WayPointList waypoints; + waypoints.resize(q.size()); + + auto index = 0u; + auto prevN = 0u; + for(auto n : q) + { + auto& wp = static_cast(waypoints[index]); + wp.face = mNavigationMesh->GetFace(n); + wp.nodeIndex = n; + + wp.edge = nullptr; + // set the common edge with previous node + if(index > 0) + { + const auto& node = mNodes[prevN]; + for(auto i = 0u; i < 3; ++i) + { + if(node.faces[i] == wp.nodeIndex) + { + wp.edge = mNavigationMesh->GetEdge(node.edges[i]); + break; + } + } + } + + prevN = n; + index++; + } + + // Reset informations what we used. + // Forward indexes + for(const auto& i : usedPolyIndexs[0]) + { + dist[i] = std::numeric_limits::infinity(); + priority[i] = -1.0f; // Initialize by negative value, that we didn't calculate yet. + prevForward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + prevBackward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + queued[i] = false; + } + // Backward indexes + for(const auto& i : usedPolyIndexs[1]) + { + dist[i] = std::numeric_limits::infinity(); + priority[i] = -1.0f; // Initialize by negative value, that we didn't calculate yet. + prevForward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + prevBackward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + queued[i] = false; + } + + return OptimizeWaypoints(waypoints); +} + +void PathFinderAlgorithmSPFADoubleWay::PrepareData() +{ + // Build the list structure connecting the nodes + auto faceCount = mNavigationMesh->GetFaceCount(); + + mNodes.resize(faceCount); + dist.resize(faceCount); + priority.resize(faceCount); + prevForward.resize(faceCount); + prevBackward.resize(faceCount); + componentIds.resize(faceCount); + queued.resize(faceCount); + + // Temperal container for components level. It will be used for Union-Find algorithm. + std::vector componentLevels(faceCount); + + // Initialize path informations. + for(auto i = 0u; i < faceCount; ++i) + { + dist[i] = std::numeric_limits::infinity(); + priority[i] = -1.0f; // Initialize by negative value, that we didn't calculate yet. + prevForward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + prevBackward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + queued[i] = false; + + componentIds[i] = i; // Components id should be initialized by itself. + componentLevels[i] = 0u; + } + + // for each face build the list + for(auto i = 0u; i < faceCount; ++i) + { + auto& node = mNodes[i]; + const auto* face = mNavigationMesh->GetFace(i); + auto c0 = Dali::Vector3(face->center); + + // for each edge add neighbouring face and compute distance to set the weight of node + for(auto edgeIndex = 0u; edgeIndex < 3; ++edgeIndex) + { + const auto* edge = mNavigationMesh->GetEdge(face->edge[edgeIndex]); + auto p1 = edge->face[0]; + auto p2 = edge->face[1]; + + // One of faces is current face so ignore it + auto p = ((p1 != i) ? p1 : p2); + node.faces[edgeIndex] = p; + if(p != ::Dali::Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + node.edges[edgeIndex] = face->edge[edgeIndex]; + auto c1 = Dali::Vector3(mNavigationMesh->GetFace(p)->center); + node.weight[edgeIndex] = (c1 - c0).Length(); + + // Connect two components + ComponentsCombine(componentIds, componentLevels, i, p); + } + } + } +} + +[[maybe_unused]] static float ccw(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C) +{ + return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x); +} + +[[maybe_unused]] static bool intersect(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C, const Dali::Vector2& D) +{ + return ccw(A, C, D) != ccw(B, C, D) && ccw(A, B, C) != ccw(A, B, D); +} + +Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFADoubleWay::OptimizeWaypoints(WayPointList& waypoints) const +{ + WayPointList optimizedWaypoints; + optimizedWaypoints.emplace_back(waypoints[0]); + optimizedWaypoints.reserve(waypoints.size()); + + auto startIndex = 1u; + + bool finished = false; + for(auto j = 0; !finished; ++j) + { + auto& startWaypoint = optimizedWaypoints.back(); + const auto& startWaypointData = static_cast(startWaypoint); + + // add new-last waypoint which will be overriden as long as intersection takes place + optimizedWaypoints.emplace_back(); + for(auto wpIndex = startIndex; wpIndex < waypoints.size(); ++wpIndex) + { + if(wpIndex == waypoints.size() - 1) + { + optimizedWaypoints.back() = waypoints.back(); + finished = true; + continue; + } + // Points between centres of faces + + const auto& wpData = static_cast(waypoints[wpIndex]); + + auto Pa0 = Dali::Vector2(startWaypointData.face->center[0], startWaypointData.face->center[1]); + auto Pa1 = Dali::Vector2(wpData.face->center[0], wpData.face->center[1]); + + bool doesIntersect = true; + for(auto i = startIndex; i < wpIndex; ++i) + { + const auto& wp = static_cast(waypoints[i]); + // Skip starting waypoint + if(wp.face == startWaypointData.face) + { + continue; + } + auto Pb0 = mNavigationMesh->GetVertex(wp.edge->vertex[0]); + auto Pb1 = mNavigationMesh->GetVertex(wp.edge->vertex[1]); + auto vPb0 = Dali::Vector2(Pb0->x, Pb0->y); + auto vPb1 = Dali::Vector2(Pb1->x, Pb1->y); + + doesIntersect = intersect(Pa0, Pa1, vPb0, vPb1); + if(!doesIntersect) + { + break; + } + } + + if(!doesIntersect) + { + optimizedWaypoints.back() = waypoints[wpIndex - 1]; + startIndex = wpIndex - 1; + break; + } + } + } + + for(auto& wp : optimizedWaypoints) + { + auto& wpData = static_cast(wp); + wpData.point3d = mNavigationMesh->PointLocalToScene(Dali::Vector3(wpData.face->center)); + wpData.point2d = Vector2::ZERO; + } + + return optimizedWaypoints; +} +} // namespace Dali::Scene3D::Internal::Algorithm diff --git a/dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h b/dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h new file mode 100644 index 0000000..32e04b9 --- /dev/null +++ b/dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h @@ -0,0 +1,105 @@ +#ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H +#define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H + +/* + * Copyright (c) 2023 Samsung Electronics Co., Ltd. + * + * 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. + */ + +// INTERNAL INCLUDES +#include +#include + +namespace Dali::Scene3D::Internal::Algorithm +{ +class PathFinderAlgorithmSPFADoubleWay : public Dali::Scene3D::Algorithm::PathFinderBase +{ +public: + /** + * @brief Constructor + * + * @param[in] navMesh Navigation mesh to associate with the algorithm + */ + explicit PathFinderAlgorithmSPFADoubleWay(Dali::Scene3D::Algorithm::NavigationMesh& navMesh); + + /** + * @brief Destructor + */ + ~PathFinderAlgorithmSPFADoubleWay() override; + + /** + * @brief Looks for a path from point A to point B. + * + * @param[in] positionFrom source position in NavigationMesh parent space + * @param[in] positionTo target position in NavigationMesh parent space + * @return List of waypoints for path + */ + Scene3D::Algorithm::WayPointList FindPath(const Dali::Vector3& PositionFrom, const Dali::Vector3& PositionTo) override; + + /** + * @brief Finds path between NavigationMesh faces + * + * @param[in] polyIndexFrom Index of start polygon + * @param[in] polyIndexTo Index of end polygon + * @return List of waypoints for path + */ + Scene3D::Algorithm::WayPointList FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) override; + + [[nodiscard]] inline const NavigationMesh::Face* Face(uint32_t i) const + { + return mNavigationMesh->GetFace(i); + } + + /** + * Build the graph of nodes + * distance between nodes is weight of node + */ + void PrepareData(); + + Scene3D::Algorithm::WayPointList OptimizeWaypoints(Scene3D::Algorithm::WayPointList& waypoints) const; + + /** + * @brief Calculate the panalty of node index. Low panalty "might" be calculated earlier. + * @pre dist and priority should be calculated. + * + * @param[in] index index of node what we want to calculate panantly. + */ + float DistancePanaltyCalculate(uint32_t index) const noexcept; + + /** + * Structure describes single node of pathfinding algorithm + */ + struct FaceNode + { + uint32_t faceIndex; ///< Index of face which is associated with node + + // neighbours + uint32_t faces[3]; ///< List of neighbouring faces (max 3 for a triangle) + uint32_t edges[3]; ///< List of edges (max 3 for a triangle) + float weight[3]; ///< List of weights (by distance) to each neighbour + }; + + NavigationMesh* mNavigationMesh; ///< Pointer to a valid NavigationMesh + std::vector mNodes; ///< List of nodes + +private: + std::vector dist; + std::vector priority; ///< Cached priority value. It will be calculated by source & target poly index per every queries. + std::vector prevForward; + std::vector prevBackward; + std::vector componentIds; ///< Id of connected components per each nodes. It should be one of node's index. + std::vector queued; +}; +} // namespace Dali::Scene3D::Internal::Algorithm +#endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H diff --git a/dali-scene3d/internal/algorithm/path-finder-spfa.cpp b/dali-scene3d/internal/algorithm/path-finder-spfa.cpp new file mode 100644 index 0000000..977eb90 --- /dev/null +++ b/dali-scene3d/internal/algorithm/path-finder-spfa.cpp @@ -0,0 +1,310 @@ +/* + * Copyright (c) 2023 Samsung Electronics Co., Ltd. + * + * 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. + */ + +// INTERNAL INCLUDES +#include +#include +#include + +// EXTERNAL INCLUDES +#include +#include + +using WayPointList = Dali::Scene3D::Algorithm::WayPointList; + +namespace Dali::Scene3D::Internal::Algorithm +{ +PathFinderAlgorithmSPFA::PathFinderAlgorithmSPFA(Dali::Scene3D::Algorithm::NavigationMesh& navMesh) +: mNavigationMesh(&GetImplementation(navMesh)) +{ + PrepareData(); +} + +PathFinderAlgorithmSPFA::~PathFinderAlgorithmSPFA() = default; + +Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFA::FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo) +{ + Dali::Vector3 outPosFrom; + uint32_t polyIndexFrom; + auto result = mNavigationMesh->FindFloor(positionFrom, outPosFrom, polyIndexFrom); + + Scene3D::Algorithm::WayPointList waypoints; + + if(result) + { + Dali::Vector3 outPosTo; + uint32_t polyIndexTo; + result = mNavigationMesh->FindFloor(positionTo, outPosTo, polyIndexTo); + + if(result) + { + // Get waypoints + waypoints = FindPath(polyIndexFrom, polyIndexTo); + + // replace first and last waypoint + auto& wpFrom = static_cast(waypoints[0]); + auto& wpTo = static_cast(waypoints.back()); + + Vector2 fromCenter(wpFrom.point3d.x, wpFrom.point3d.y); + wpFrom.point3d = outPosFrom; + wpFrom.point2d = fromCenter - Vector2(outPosFrom.x, outPosFrom.y); + + Vector2 toCenter(wpTo.point3d.x, wpTo.point3d.y); + wpTo.point3d = outPosTo; + wpTo.point2d = toCenter - Vector2(outPosTo.x, outPosTo.y); + wpTo.point3d = outPosTo; + } + } + + // Returns waypoints with non-zero size of empty vector in case of failure (no path to be found) + return waypoints; +} + +Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFA::FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) +{ + auto nodeCount = uint32_t(mNodes.size()); + std::vector dist; + std::vector prev; + std::vector queued; + + dist.resize(mNodes.size()); + prev.resize(mNodes.size()); + queued.resize(mNodes.size()); + + std::list nodeQueue; + + [[maybe_unused]] auto sourcePos = Dali::Vector3(Face(sourcePolyIndex)->center); + + for(auto i = 0u; i < nodeCount; ++i) + { + dist[i] = std::numeric_limits::infinity(); + prev[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon + queued[i] = false; + } + + // Set distance of source + dist[sourcePolyIndex] = 0.0f; + queued[sourcePolyIndex] = true; + nodeQueue.push_back(sourcePolyIndex); + + while(!nodeQueue.empty()) + { + // find minimum distance + auto minDistIndex = nodeQueue.front(); + nodeQueue.pop_front(); + queued[minDistIndex] = false; + + // Skip operator when minDistIndex is target + if(minDistIndex == targetPolyIndex) + { + continue; + } + + // check the neighbours + for(auto i = 0u; i < 3; ++i) + { + auto nIndex = mNodes[minDistIndex].faces[i]; + if(nIndex != Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + auto alt = dist[minDistIndex] + mNodes[minDistIndex].weight[i]; + if(alt < dist[nIndex]) + { + dist[nIndex] = alt; + prev[nIndex] = minDistIndex; + + if(!queued[nIndex]) + { + queued[nIndex] = true; + if(!nodeQueue.empty() && dist[nIndex] < dist[nodeQueue.front()]) + { + nodeQueue.push_front(nIndex); + } + else + { + nodeQueue.push_back(nIndex); + } + } + } + } + } + } + + // Compute distances for each node back to the source + auto u = targetPolyIndex; + std::list q; + if(prev[u] != Scene3D::Algorithm::NavigationMesh::NULL_FACE || u == sourcePolyIndex) + { + while(u != Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + q.push_front(u); + u = prev[u]; + } + } + + WayPointList waypoints; + waypoints.resize(q.size()); + + if(q.size() == 0) + { + // Fail to found path. Return empty list. + return waypoints; + } + + auto index = 0u; + auto prevN = 0u; + for(auto n : q) + { + auto& wp = static_cast(waypoints[index]); + wp.face = mNavigationMesh->GetFace(n); + wp.nodeIndex = n; + + wp.edge = nullptr; + // set the common edge with previous node + if(index > 0) + { + const auto& node = mNodes[prevN]; + for(auto i = 0u; i < 3; ++i) + { + if(node.faces[i] == wp.nodeIndex) + { + wp.edge = mNavigationMesh->GetEdge(node.edges[i]); + break; + } + } + } + + prevN = n; + index++; + } + + return OptimizeWaypoints(waypoints); +} + +void PathFinderAlgorithmSPFA::PrepareData() +{ + // Build the list structure connecting the nodes + auto faceCount = mNavigationMesh->GetFaceCount(); + + mNodes.resize(faceCount); + + // for each face build the list + for(auto i = 0u; i < faceCount; ++i) + { + auto& node = mNodes[i]; + const auto* face = mNavigationMesh->GetFace(i); + auto c0 = Dali::Vector3(face->center); + + // for each edge add neighbouring face and compute distance to set the weight of node + for(auto edgeIndex = 0u; edgeIndex < 3; ++edgeIndex) + { + const auto* edge = mNavigationMesh->GetEdge(face->edge[edgeIndex]); + auto p1 = edge->face[0]; + auto p2 = edge->face[1]; + + // One of faces is current face so ignore it + auto p = ((p1 != i) ? p1 : p2); + node.faces[edgeIndex] = p; + if(p != ::Dali::Scene3D::Algorithm::NavigationMesh::NULL_FACE) + { + node.edges[edgeIndex] = face->edge[edgeIndex]; + auto c1 = Dali::Vector3(mNavigationMesh->GetFace(p)->center); + node.weight[edgeIndex] = (c1 - c0).Length(); + } + } + } +} + +[[maybe_unused]] static float ccw(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C) +{ + return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x); +} + +[[maybe_unused]] static bool intersect(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C, const Dali::Vector2& D) +{ + return ccw(A, C, D) != ccw(B, C, D) && ccw(A, B, C) != ccw(A, B, D); +} + +Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFA::OptimizeWaypoints(WayPointList& waypoints) const +{ + WayPointList optimizedWaypoints; + optimizedWaypoints.emplace_back(waypoints[0]); + optimizedWaypoints.reserve(waypoints.size()); + + auto startIndex = 1u; + + bool finished = false; + for(auto j = 0; !finished; ++j) + { + auto& startWaypoint = optimizedWaypoints.back(); + const auto& startWaypointData = static_cast(startWaypoint); + + // add new-last waypoint which will be overriden as long as intersection takes place + optimizedWaypoints.emplace_back(); + for(auto wpIndex = startIndex; wpIndex < waypoints.size(); ++wpIndex) + { + if(wpIndex == waypoints.size() - 1) + { + optimizedWaypoints.back() = waypoints.back(); + finished = true; + continue; + } + // Points between centres of faces + + const auto& wpData = static_cast(waypoints[wpIndex]); + + auto Pa0 = Dali::Vector2(startWaypointData.face->center[0], startWaypointData.face->center[1]); + auto Pa1 = Dali::Vector2(wpData.face->center[0], wpData.face->center[1]); + + bool doesIntersect = true; + for(auto i = startIndex; i < wpIndex; ++i) + { + const auto& wp = static_cast(waypoints[i]); + // Skip starting waypoint + if(wp.face == startWaypointData.face) + { + continue; + } + auto Pb0 = mNavigationMesh->GetVertex(wp.edge->vertex[0]); + auto Pb1 = mNavigationMesh->GetVertex(wp.edge->vertex[1]); + auto vPb0 = Dali::Vector2(Pb0->x, Pb0->y); + auto vPb1 = Dali::Vector2(Pb1->x, Pb1->y); + + doesIntersect = intersect(Pa0, Pa1, vPb0, vPb1); + if(!doesIntersect) + { + break; + } + } + + if(!doesIntersect) + { + optimizedWaypoints.back() = waypoints[wpIndex - 1]; + startIndex = wpIndex - 1; + break; + } + } + } + + for(auto& wp : optimizedWaypoints) + { + auto& wpData = static_cast(wp); + wpData.point3d = mNavigationMesh->PointLocalToScene(Dali::Vector3(wpData.face->center)); + wpData.point2d = Vector2::ZERO; + } + + return optimizedWaypoints; +} +} // namespace Dali::Scene3D::Internal::Algorithm diff --git a/dali-scene3d/internal/algorithm/path-finder-spfa.h b/dali-scene3d/internal/algorithm/path-finder-spfa.h new file mode 100644 index 0000000..99fc4af --- /dev/null +++ b/dali-scene3d/internal/algorithm/path-finder-spfa.h @@ -0,0 +1,89 @@ +#ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H +#define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H + +/* + * Copyright (c) 2023 Samsung Electronics Co., Ltd. + * + * 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. + */ + +// INTERNAL INCLUDES +#include +#include + +namespace Dali::Scene3D::Internal::Algorithm +{ +class PathFinderAlgorithmSPFA : public Dali::Scene3D::Algorithm::PathFinderBase +{ +public: + /** + * @brief Constructor + * + * @param[in] navMesh Navigation mesh to associate with the algorithm + */ + explicit PathFinderAlgorithmSPFA(Dali::Scene3D::Algorithm::NavigationMesh& navMesh); + + /** + * @brief Destructor + */ + ~PathFinderAlgorithmSPFA() override; + + /** + * @brief Looks for a path from point A to point B. + * + * @param[in] positionFrom source position in NavigationMesh parent space + * @param[in] positionTo target position in NavigationMesh parent space + * @return List of waypoints for path + */ + Scene3D::Algorithm::WayPointList FindPath(const Dali::Vector3& PositionFrom, const Dali::Vector3& PositionTo) override; + + /** + * @brief Finds path between NavigationMesh faces + * + * @param[in] polyIndexFrom Index of start polygon + * @param[in] polyIndexTo Index of end polygon + * @return List of waypoints for path + */ + Scene3D::Algorithm::WayPointList FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) override; + + [[nodiscard]] inline const NavigationMesh::Face* Face(uint32_t i) const + { + return mNavigationMesh->GetFace(i); + } + + /** + * Build the graph of nodes + * distance between nodes is weight of node + */ + void PrepareData(); + + Scene3D::Algorithm::WayPointList OptimizeWaypoints(Scene3D::Algorithm::WayPointList& waypoints) const; + + /** + * Structure describes single node of pathfinding algorithm + */ + struct FaceNode + { + uint32_t faceIndex; ///< Index of face which is associated with node + + // neighbours + uint32_t faces[3]; ///< List of neighbouring faces (max 3 for a triangle) + uint32_t edges[3]; ///< List of edges (max 3 for a triangle) + float weight[3]; ///< List of weights (by distance) to each neighbour + }; + + NavigationMesh* mNavigationMesh; ///< Pointer to a valid NavigationMesh + std::vector mNodes; ///< List of nodes +}; +} // namespace Dali::Scene3D::Internal::Algorithm +#endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H diff --git a/dali-scene3d/internal/file.list b/dali-scene3d/internal/file.list index 30ebe95..b5386c3 100644 --- a/dali-scene3d/internal/file.list +++ b/dali-scene3d/internal/file.list @@ -3,6 +3,8 @@ set(scene3d_internal_dir "${scene3d_dir}/internal") set(scene3d_src_files ${scene3d_src_files} ${scene3d_internal_dir}/algorithm/navigation-mesh-impl.cpp ${scene3d_internal_dir}/algorithm/path-finder-djikstra.cpp + ${scene3d_internal_dir}/algorithm/path-finder-spfa.cpp + ${scene3d_internal_dir}/algorithm/path-finder-spfa-double-way.cpp ${scene3d_internal_dir}/common/environment-map-load-task.cpp ${scene3d_internal_dir}/common/model-load-task.cpp ${scene3d_internal_dir}/controls/model/model-impl.cpp diff --git a/dali-scene3d/public-api/algorithm/path-finder.cpp b/dali-scene3d/public-api/algorithm/path-finder.cpp index 42d227f..f48ffb3 100644 --- a/dali-scene3d/public-api/algorithm/path-finder.cpp +++ b/dali-scene3d/public-api/algorithm/path-finder.cpp @@ -19,6 +19,8 @@ // default algorithm #include +#include +#include namespace Dali::Scene3D::Algorithm { @@ -26,9 +28,23 @@ std::unique_ptr PathFinder::New(NavigationMesh& navigationMesh, Path { PathFinderBase* impl = nullptr; - if(algorithm == PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH) + switch(algorithm) { - impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmDjikstra(navigationMesh); + case PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH: + { + impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmDjikstra(navigationMesh); + break; + } + case PathFinderAlgorithm::SPFA: + { + impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmSPFA(navigationMesh); + break; + } + case PathFinderAlgorithm::SPFA_DOUBLE_WAY: + { + impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmSPFADoubleWay(navigationMesh); + break; + } } if(!impl) @@ -43,19 +59,17 @@ std::unique_ptr PathFinder::New(NavigationMesh& navigationMesh, Path WayPointList PathFinder::FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo) { - return mImpl->FindPath( positionFrom, positionTo ); + return mImpl->FindPath(positionFrom, positionTo); } WayPointList PathFinder::FindPath(uint32_t polyIndexFrom, uint32_t polyIndexTo) { - return mImpl->FindPath( polyIndexFrom, polyIndexTo ); + return mImpl->FindPath(polyIndexFrom, polyIndexTo); } - PathFinder::PathFinder(std::unique_ptr&& baseImpl) { mImpl = std::move(baseImpl); } - } // namespace Dali::Scene3D::Algorithm diff --git a/dali-scene3d/public-api/algorithm/path-finder.h b/dali-scene3d/public-api/algorithm/path-finder.h index e1791bc..ee37d5e 100644 --- a/dali-scene3d/public-api/algorithm/path-finder.h +++ b/dali-scene3d/public-api/algorithm/path-finder.h @@ -18,13 +18,12 @@ */ // INTERNAL INCLUDES -#include #include #include +#include namespace Dali::Scene3D::Algorithm { - using WayPointList = std::vector; /** @@ -34,6 +33,9 @@ using WayPointList = std::vector; enum class PathFinderAlgorithm { DJIKSTRA_SHORTEST_PATH, ///< Using A* variant (Djikstra) finding a shortest path + SPFA, ///< Using SPFA-SLF (Shortest Path Fast Algorithm with Short Label First) finding a shortest path. + SPFA_DOUBLE_WAY, ///< Using SPFA-SLF double way. It might not find shortest, but will use less memory. + DEFAULT = DJIKSTRA_SHORTEST_PATH, ///< Default algorithm to use }; @@ -45,7 +47,6 @@ enum class PathFinderAlgorithm class DALI_SCENE3D_API PathFinderBase { public: - /** * @brief Destructor */ @@ -79,14 +80,13 @@ public: class DALI_SCENE3D_API PathFinder { public: - /** * @brief Creates new instance of path finder * @param[in] navigationMesh Navigation mesh to associate with * @param[in] algorithm algorithm to use * @return Valid pointer to PathFinder object or nullptr */ - static std::unique_ptr New( NavigationMesh& navigationMesh, PathFinderAlgorithm algorithm ); + static std::unique_ptr New(NavigationMesh& navigationMesh, PathFinderAlgorithm algorithm); /** * @brief Looks for a path from point A to point B. @@ -122,7 +122,6 @@ public: WayPointList FindPath(uint32_t faceIndexFrom, uint32_t faceIndexTo); private: - PathFinder() = delete; DALI_INTERNAL explicit PathFinder(std::unique_ptr&& baseImpl); @@ -130,6 +129,6 @@ private: std::unique_ptr mImpl; }; -} +} // namespace Dali::Scene3D::Algorithm #endif // DALI_SCENE3D_PATH_FINDER_H -- 2.7.4