1 /* Copyright 2012 Jukka Jyl�nki
2
3    Licensed under the Apache License, Version 2.0 (the "License");
4    you may not use this file except in compliance with the License.
5    You may obtain a copy of the License at
6
7        http://www.apache.org/licenses/LICENSE-2.0
8
9    Unless required by applicable law or agreed to in writing, software
10    distributed under the License is distributed on an "AS IS" BASIS,
11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12    See the License for the specific language governing permissions and
13    limitations under the License. */
14
15 /** @file PBVolume.h
16         @author Jukka Jyl�nki
17         @brief Implements a convex polyhedron data structure. */
18
19 #pragma once
20
21 #include "../Math/float3.h"
22 #include "../Math/assume.h"
23 #include "AABB.h"
24 #include "Plane.h"
25 #include "Sphere.h"
26 #include "Polyhedron.h"
27
28 MATH_BEGIN_NAMESPACE
29
30 /// Reports a result from an approximate culling operation.
31 enum CullTestResult
32 {
33         // The tested objects don't intersect - they are fully disjoint.
34         TestOutside,
35
36         // The tested object is at least not fully contained inside the other object, but no other information is known.
37         // The objects might intersect or be disjoint.
38         TestNotContained,
39
40         // The tested object is fully contained inside the other object.
41         TestInside
42 };
43
44 /// PBVolume is a "plane bounded volume", a convex polyhedron represented by a set
45 /// of planes. The number of planes is fixed at compile time so that compilers are able to perfectly unroll the loops for
46 /// best performance. As a fixed convention, the plane normals of the volume point outwards from the plane, so the
47 /// negative halfspaces are inside the convex volume.
48 template<int N>
49 class PBVolume
50 {
51 public:
52         Plane p[N];
53
54         int NumPlanes() const { return N; }
55
56         bool Contains(const vec &point) const
57         {
58                 for(int i = 0; i < N; ++i)
59                         if (p[i].SignedDistance(point) > 0.f)
60                                 return false;
61                 return true;
62         }
63
64         /// Performs an *approximate* intersection test between this PBVolume and the given AABB.
65         /** This function is best used for high-performance object culling purposes, e.g. for frustum-aabb culling, when
66                 a small percentage of false positives do not matter.
67                 @return An enum denoting whether the given object is inside or intersects this PBVolume. See the CullTestResult enum 
68                         for the interpretation of the return values. */
69         CullTestResult InsideOrIntersects(const AABB &aabb) const
70         {
71                 CullTestResult result = TestInside;
72
73                 for(int i = 0; i < N; ++i)
74                 {
75                         vec nPoint;
76                         vec pPoint;
77                         nPoint.x = (p[i].normal.x < 0.f ? aabb.maxPoint.x : aabb.minPoint.x);
78                         nPoint.y = (p[i].normal.y < 0.f ? aabb.maxPoint.y : aabb.minPoint.y);
79                         nPoint.z = (p[i].normal.z < 0.f ? aabb.maxPoint.z : aabb.minPoint.z);
80 #ifdef MATH_VEC_IS_FLOAT4
81                         nPoint.w = 1.f;
82 #endif
83
84                         pPoint.x = (p[i].normal.x >= 0.f ? aabb.maxPoint.x : aabb.minPoint.x);
85                         pPoint.y = (p[i].normal.y >= 0.f ? aabb.maxPoint.y : aabb.minPoint.y);
86                         pPoint.z = (p[i].normal.z >= 0.f ? aabb.maxPoint.z : aabb.minPoint.z);
87 #ifdef MATH_VEC_IS_FLOAT4
88                         pPoint.w = 1.f;
89 #endif
90
91                         /*
92                         // Find the n and p points of the aabb. (The nearest and farthest corners relative to the plane)
93                         const vec &sign = npPointsSignLUT[((p[i].normal.z >= 0.f) ? 4 : 0) +
94                                                                                                  ((p[i].normal.y >= 0.f) ? 2 : 0) +
95                                                                                                  ((p[i].normal.x >= 0.f) ? 1 : 0)];
96                         const vec nPoint = c + sign*r;
97                         const vec pPoint = c - sign*r;
98                         */
99
100                         float a = p[i].SignedDistance(nPoint);
101                         if (a >= 0.f)
102                                 return TestOutside; // The AABB is certainly outside this PBVolume.
103                         a = p[i].SignedDistance(pPoint);
104                         if (a >= 0.f)
105                                 result = TestNotContained; // At least one vertex is outside this PBVolume. The whole AABB can't possibly be contained in this PBVolume.
106                 }
107
108                 // We can return here either TestInside or TestNotContained, but it's possible that the AABB was outside the frustum, and we
109                 // just failed to find a separating axis.
110                 return result;
111         }
112
113         CullTestResult InsideOrIntersects(const Sphere &sphere) const
114         {
115                 CullTestResult result = TestInside;
116                 for(int i = 0; i < N; ++i)
117                 {
118                         float d = p[i].SignedDistance(sphere.pos);
119                         if (d >= sphere.r)
120                                 return TestOutside;
121                         else if (d >= -sphere.r)
122                                 result = TestNotContained;
123                 }
124                 return result;
125         }
126
127 private:
128         struct CornerPt // A helper struct used only internally in ToPolyhedron.
129         {
130                 int ptIndex; // Index to the Polyhedron list of vertices.
131                 int j, k; // The two plane faces in addition to the main plane that make up this point.
132         };
133
134         bool ContainsExcept(const vec &point, int i, int j, int k) const
135         {
136                 for(int l = 0; l < N; ++l)
137                         if (l != i && l != j && l != k && p[l].SignedDistance(point) > 0.f)
138                                 return false;
139                 return true;
140         }
141
142 public:
143         Polyhedron ToPolyhedron() const
144         {
145                 Polyhedron ph;
146                 std::vector<CornerPt> faces[N];
147                 for(int i = 0; i < N-2; ++i)
148                         for(int j = i+1; j < N-1; ++j)
149                                 for(int k = j+1; k < N; ++k)
150                                 {
151                                         vec corner;
152                                         bool intersects = p[i].Intersects(p[j], p[k], 0, &corner);
153                                         if (intersects && ContainsExcept(corner, i, j, k))
154                                         {
155                                                 CornerPt pt;
156
157                                                 // Find if this vertex is duplicate of an existing vertex.
158                                                 bool found = false;
159                                                 for(size_t m = 0; m < ph.v.size(); ++m)
160                                                         if (vec(ph.v[m]).Equals(corner))
161                                                         {
162                                                                 found = true;
163                                                                 pt.ptIndex = (int)m;
164                                                                 break;
165                                                         }
166
167                                                 if (!found) // New vertex?
168                                                 {
169 //                                                      LOGI("New point at corner (%d,%d,%d): %s", i, j, k, corner.ToString().c_str());
170                                                         ph.v.push_back(corner);
171                                                         pt.ptIndex = (int)ph.v.size()-1;
172                                                 }
173                                                 else
174                                                 {
175 //                                                      LOGI("Existing point at corner (%d,%d,%d): %s", i, j, k, corner.ToString().c_str());
176                                                 }
177
178                                                 pt.j = j;
179                                                 pt.k = k;
180                                                 faces[i].push_back(pt);
181
182                                                 pt.j = i;
183                                                 pt.k = k;
184                                                 faces[j].push_back(pt);
185
186                                                 pt.j = i;
187                                                 pt.k = j;
188                                                 faces[k].push_back(pt);
189                                         }
190                                 }
191
192                 // Check if we got a degenerate polyhedron?
193                 if (ph.v.size() <= 1)
194                         return ph;
195                 else if (ph.v.size() == 2)
196                 {
197                         // Create a degenerate face that's an edge.
198                         Polyhedron::Face f;
199                         f.v.push_back(0);
200                         f.v.push_back(1);
201                         ph.f.push_back(f);
202                         return ph;
203                 }
204                 else if (ph.v.size() == 3)
205                 {
206                         // Create a degenerate face that's a triangle.
207                         Polyhedron::Face f;
208                         f.v.push_back(0);
209                         f.v.push_back(1);
210                         f.v.push_back(2);
211                         ph.f.push_back(f);
212                         return ph;
213                 }
214
215                 // Connect the edges in each face using selection sort.
216                 for(int i = 0; i < N; ++i)
217                 {
218                         std::vector<CornerPt> &p = faces[i];
219                         if (p.size() < 3)
220                                 continue;
221                         for(size_t j = 0; j < p.size()-1; ++j)
222                         {
223                                 CornerPt &prev = p[j];
224                                 bool found = false;
225                                 for(size_t k = j+1; k < p.size(); ++k)
226                                 {
227                                         CornerPt &cur = p[k];
228                                         if (cur.j == prev.k)
229                                         {
230                                                 Swap(cur, p[j+1]);
231                                                 found = true;
232                                                 break;
233                                         }
234                                         if (cur.k == prev.k)
235                                         {
236                                                 Swap(cur.j, cur.k);
237                                                 Swap(cur, p[j+1]);
238                                                 found = true;
239                                                 break;
240                                         }
241                                 }
242                                 assert(found);
243                                 MARK_UNUSED(found);
244                         }
245                         assert(p[0].j == p[p.size()-1].k);
246                         if (p.size() >= 3)
247                         {
248                                 Polyhedron::Face f;
249                                 for(size_t j = 0; j < p.size(); ++j)
250                                 {
251                                         f.v.push_back(p[j].ptIndex);
252                                 }
253                                 ph.f.push_back(f);
254                         }
255                 }
256
257                 // Fix up winding directions.
258                 for(size_t i = 0; i < ph.f.size(); ++i)
259                 {
260                         Plane p = ph.FacePlane((int)i);
261                         for(size_t j = 0; j < ph.v.size(); ++j)
262                         {
263                                 if (p.SignedDistance(ph.v[j]) > 1e-3f)
264                                 {
265                                         ph.f[i].FlipWindingOrder();
266                                         break;
267                                 }
268                         }
269                 }
270                 return ph;
271         }
272
273         /// Computes the set intersection of this PBVolume and the PBVolume rhs.
274         /// That is, returns the convex set of points that are contained in both this and rhs.
275         /// Set intersection is symmetric, so a.SetIntersection(b) is the same as b.SetIntersection(a).
276         /// @note The returned PBVolume may contain redundant planes, these are not pruned.
277         template<int M>
278         PBVolume<N+M> SetIntersection(const PBVolume<M> &rhs) const
279         {
280                 PBVolume<N+M> res;
281                 for(int i = 0; i < N; ++i)
282                         res.p[i] = p[i];
283                 for(int i = 0; i < M; ++i)
284                         res.p[N+i] = rhs.p[i];
285                 return res;
286         }
287 };
288
289 MATH_END_NAMESPACE