1 /*
2 Copyright (C) 2010-2014 Kristian Duske
3
4 This file is part of TrenchBroom.
5
6 TrenchBroom is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 TrenchBroom is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with TrenchBroom. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #ifndef Polyhedron_Queries_h
21 #define Polyhedron_Queries_h
22
23 template <typename T, typename FP, typename VP>
contains(const V & point,const Callback & callback)24 bool Polyhedron<T,FP,VP>::contains(const V& point, const Callback& callback) const {
25 if (!bounds().contains(point))
26 return false;
27
28 const Face* firstFace = m_faces.front();
29 const Face* currentFace = firstFace;
30 do {
31 const Plane<T,3> plane = callback.plane(currentFace);
32 if (plane.pointStatus(point) == Math::PointStatus::PSAbove)
33 return false;
34 currentFace = currentFace->next();
35 } while (currentFace != firstFace);
36 return true;
37 }
38
39 template <typename T, typename FP, typename VP>
contains(const Polyhedron & other,const Callback & callback)40 bool Polyhedron<T,FP,VP>::contains(const Polyhedron& other, const Callback& callback) const {
41 if (!bounds().contains(other.bounds()))
42 return false;
43 const Vertex* theirFirst = other.vertices().front();
44 const Vertex* theirCurrent = theirFirst;
45 do {
46 if (!contains(theirCurrent->position()))
47 return false;
48 theirCurrent = theirCurrent->next();
49 } while (theirCurrent != theirFirst);
50 return true;
51 }
52
53 template <typename T, typename FP, typename VP>
intersects(const Polyhedron & other,const Callback & callback)54 bool Polyhedron<T,FP,VP>::intersects(const Polyhedron& other, const Callback& callback) const {
55 if (!bounds().intersects(other.bounds()))
56 return false;
57
58 // separating axis theorem
59 // http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf
60
61 if (separate(m_faces.front(), other.vertices().front(), callback))
62 return false;
63 if (separate(other.faces().front(), m_vertices.front(), callback))
64 return false;
65
66 const Edge* myFirstEdge = m_edges.front();
67 const Edge* myCurrentEdge = myFirstEdge;
68 const Edge* theirFirstEdge = other.edges().front();
69 do {
70 const V myEdgeVec = myCurrentEdge->vector();
71 const V& origin = myCurrentEdge->firstVertex()->position();
72
73 const Edge* theirCurrentEdge = theirFirstEdge;
74 do {
75 const V theirEdgeVec = theirCurrentEdge->vector();
76 const V direction = crossed(myEdgeVec, theirEdgeVec);
77 const Plane<T,3> plane(origin, direction);
78
79 const Math::PointStatus::Type myStatus = pointStatus(plane, m_vertices.front());
80 if (myStatus != Math::PointStatus::PSInside) {
81 const Math::PointStatus::Type theirStatus = pointStatus(plane, other.vertices().front());
82 if (theirStatus != Math::PointStatus::PSInside) {
83 if (myStatus != theirStatus)
84 return false;
85 }
86 }
87
88 theirCurrentEdge = theirCurrentEdge->next();
89 } while (theirCurrentEdge != theirFirstEdge);
90 myCurrentEdge = myCurrentEdge->next();
91 } while (myCurrentEdge != myFirstEdge);
92
93 return true;
94 }
95
96 template <typename T, typename FP, typename VP>
separate(const Face * firstFace,const Vertex * firstVertex,const Callback & callback)97 bool Polyhedron<T,FP,VP>::separate(const Face* firstFace, const Vertex* firstVertex, const Callback& callback) const {
98 const Face* currentFace = firstFace;
99 do {
100 const Plane<T,3> plane = callback.plane(currentFace);
101 if (pointStatus(plane, firstVertex) == Math::PointStatus::PSAbove)
102 return true;
103 currentFace = currentFace->next();
104 } while (currentFace != firstFace);
105 return false;
106 }
107
108 template <typename T, typename FP, typename VP>
pointStatus(const Plane<T,3> & plane,const Vertex * firstVertex)109 Math::PointStatus::Type Polyhedron<T,FP,VP>::pointStatus(const Plane<T,3>& plane, const Vertex* firstVertex) const {
110 size_t above = 0;
111 size_t below = 0;
112 const Vertex* currentVertex = firstVertex;
113 do {
114 const Math::PointStatus::Type status = plane.pointStatus(currentVertex->position());
115 if (status == Math::PointStatus::PSAbove)
116 ++above;
117 else if (status == Math::PointStatus::PSBelow)
118 ++below;
119 if (above > 0 && below > 0)
120 return Math::PointStatus::PSInside;
121 currentVertex = currentVertex->next();
122 } while (currentVertex != firstVertex);
123 return above > 0 ? Math::PointStatus::PSAbove : Math::PointStatus::PSBelow;
124 }
125
126 #endif /* Polyhedron_Queries_h */
127