1 // Copyright © 2008-2021 Pioneer Developers. See AUTHORS.txt for details
2 // Licensed under the terms of the GPL v3. See licenses/GPL-3.txt
3
4 #include "GeomTree.h"
5 #include "../libs.h"
6 #include "BVHTree.h"
7 #include "Weld.h"
8 #include "scenegraph/Serializer.h"
9
10 #pragma GCC optimize("O3")
11
~GeomTree()12 GeomTree::~GeomTree()
13 {
14 }
15
GeomTree(const int numVerts,const int numTris,const std::vector<vector3f> & vertices,const Uint32 * indices,const Uint32 * triflags)16 GeomTree::GeomTree(const int numVerts, const int numTris, const std::vector<vector3f> &vertices, const Uint32 *indices, const Uint32 *triflags) :
17 m_numVertices(numVerts),
18 m_numTris(numTris),
19 m_vertices(vertices)
20 {
21 PROFILE_SCOPED()
22 assert(static_cast<int>(vertices.size()) == m_numVertices);
23 Profiler::Timer timer;
24 timer.Start();
25
26 const int numIndices = numTris * 3;
27 m_indices.reserve(numIndices);
28 for (int i = 0; i < numIndices; ++i) {
29 m_indices.push_back(indices[i]);
30 }
31
32 m_triFlags.reserve(numTris);
33 for (int i = 0; i < numTris; ++i) {
34 m_triFlags.push_back(triflags[i]);
35 }
36
37 m_aabb.min = vector3d(FLT_MAX, FLT_MAX, FLT_MAX);
38 m_aabb.max = vector3d(-FLT_MAX, -FLT_MAX, -FLT_MAX);
39
40 // activeTris = tris we are still trying to put into leaves
41 std::vector<int> activeTris;
42 activeTris.reserve(numTris);
43 for (int i = 0; i < numTris; i++) {
44 activeTris.push_back(i * 3);
45 }
46
47 typedef std::map<std::pair<int, int>, int> EdgeType;
48 EdgeType edges;
49 #define ADD_EDGE(_i1, _i2, _triflag) \
50 if ((_i1) < (_i2)) \
51 edges[std::pair<int, int>(_i1, _i2)] = _triflag; \
52 else if ((_i1) > (_i2)) \
53 edges[std::pair<int, int>(_i2, _i1)] = _triflag;
54
55 // eliminate duplicate vertices
56 {
57 std::vector<Uint32> xrefs;
58 nv::Weld<vector3f> weld;
59 weld(m_vertices, xrefs);
60 m_numVertices = m_vertices.size();
61
62 //Output("--- %d vertices welded\n", count - newCount);
63
64 // Remap faces.
65 const Uint32 faceCount = numTris;
66 for (Uint32 f = 0; f < faceCount; f++) {
67 const Uint32 idx = (f * 3);
68 m_indices[idx + 0] = xrefs.at(m_indices[idx + 0]);
69 m_indices[idx + 1] = xrefs.at(m_indices[idx + 1]);
70 m_indices[idx + 2] = xrefs.at(m_indices[idx + 2]);
71 }
72 }
73
74 // Get radius, m_aabb, and merge duplicate edges
75 m_radius = 0;
76 for (int i = 0; i < numTris; i++) {
77 const Uint32 triflag = m_triFlags[i];
78 const int vi1 = m_indices[3 * i + 0];
79 const int vi2 = m_indices[3 * i + 1];
80 const int vi3 = m_indices[3 * i + 2];
81
82 ADD_EDGE(vi1, vi2, triflag);
83 ADD_EDGE(vi1, vi3, triflag);
84 ADD_EDGE(vi2, vi3, triflag);
85
86 vector3d v[3];
87 v[0] = vector3d(m_vertices[vi1]);
88 v[1] = vector3d(m_vertices[vi2]);
89 v[2] = vector3d(m_vertices[vi3]);
90 m_aabb.Update(v[0]);
91 m_aabb.Update(v[1]);
92 m_aabb.Update(v[2]);
93 for (int j = 0; j < 3; j++) {
94 const double rad = v[j].x * v[j].x + v[j].y * v[j].y + v[j].z * v[j].z;
95 if (rad > m_radius) m_radius = rad;
96 }
97 }
98 m_radius = sqrt(m_radius);
99
100 {
101 Aabb *aabbs = new Aabb[activeTris.size()];
102 for (Uint32 i = 0; i < activeTris.size(); i++) {
103 const vector3d v1 = vector3d(m_vertices[m_indices[activeTris[i] + 0]]);
104 const vector3d v2 = vector3d(m_vertices[m_indices[activeTris[i] + 1]]);
105 const vector3d v3 = vector3d(m_vertices[m_indices[activeTris[i] + 2]]);
106 aabbs[i].min = aabbs[i].max = v1;
107 aabbs[i].Update(v2);
108 aabbs[i].Update(v3);
109 }
110
111 //int t = SDL_GetTicks();
112 m_triTree.reset(new BVHTree(activeTris.size(), &activeTris[0], aabbs));
113 delete[] aabbs;
114 }
115 //Output("Tri tree of %d tris build in %dms\n", activeTris.size(), SDL_GetTicks() - t);
116
117 m_numEdges = edges.size();
118 m_edges.resize(m_numEdges);
119 // to build Edge bvh tree with.
120 m_aabbs.resize(m_numEdges);
121 int *edgeIdxs = new int[m_numEdges];
122
123 int pos = 0;
124 typedef EdgeType::iterator MapPairIter;
125 for (MapPairIter i = edges.begin(), iEnd = edges.end(); i != iEnd; ++i, pos++) {
126 // precalc some jizz
127 const std::pair<int, int> &vtx = (*i).first;
128 const int triflag = (*i).second;
129 const vector3f &v1 = m_vertices[vtx.first];
130 const vector3f &v2 = m_vertices[vtx.second];
131 vector3f dir = (v2 - v1);
132 const float len = dir.Length();
133 dir *= 1.0f / len;
134
135 m_edges[pos].v1i = vtx.first;
136 m_edges[pos].v2i = vtx.second;
137 m_edges[pos].triFlag = triflag;
138 m_edges[pos].len = len;
139 m_edges[pos].dir = dir;
140
141 edgeIdxs[pos] = pos;
142 m_aabbs[pos].min = m_aabbs[pos].max = vector3d(v1);
143 m_aabbs[pos].Update(vector3d(v2));
144 }
145
146 //t = SDL_GetTicks();
147 m_edgeTree.reset(new BVHTree(m_numEdges, edgeIdxs, &m_aabbs[0]));
148 delete[] edgeIdxs;
149 //Output("Edge tree of %d edges build in %dms\n", m_numEdges, SDL_GetTicks() - t);
150
151 timer.Stop();
152 //Output(" - - GeomTree::GeomTree took: %lf milliseconds\n", timer.millicycles());
153 }
154
GeomTree(Serializer::Reader & rd)155 GeomTree::GeomTree(Serializer::Reader &rd)
156 {
157 PROFILE_SCOPED()
158 m_numVertices = rd.Int32();
159 m_numEdges = rd.Int32();
160 m_numTris = rd.Int32();
161 m_radius = rd.Double();
162
163 m_aabb.max = rd.Vector3d();
164 m_aabb.min = rd.Vector3d();
165 m_aabb.radius = rd.Double();
166
167 const Uint32 numAabbs = rd.Int32();
168 m_aabbs.resize(numAabbs);
169 for (Uint32 iAabb = 0; iAabb < numAabbs; ++iAabb) {
170 rd >> m_aabbs[iAabb];
171 }
172
173 {
174 PROFILE_SCOPED_DESC("GeomTree::LoadEdges")
175 m_edges.resize(m_numEdges);
176 for (Sint32 iEdge = 0; iEdge < m_numEdges; ++iEdge) {
177 auto &ed = m_edges[iEdge];
178 rd >> ed.v1i >> ed.v2i >> ed.len >> ed.dir >> ed.triFlag;
179 }
180 }
181
182 m_vertices.resize(m_numVertices);
183 for (Sint32 iVert = 0; iVert < m_numVertices; ++iVert) {
184 m_vertices[iVert] = rd.Vector3f();
185 }
186
187 const int numIndicies(m_numTris * 3);
188 m_indices.resize(numIndicies);
189 for (Sint32 iIndi = 0; iIndi < numIndicies; ++iIndi) {
190 m_indices[iIndi] = rd.Int32();
191 }
192
193 m_triFlags.resize(m_numTris);
194 for (Sint32 iTri = 0; iTri < m_numTris; ++iTri) {
195 m_triFlags[iTri] = rd.Int32();
196 }
197
198 // activeTris = tris we are still trying to put into leaves
199 std::vector<int> activeTris;
200 activeTris.reserve(m_numTris);
201 for (int i = 0; i < m_numTris; i++) {
202 activeTris.push_back(i * 3);
203 }
204
205 // regenerate the aabb data
206 Aabb *aabbs = new Aabb[activeTris.size()];
207 for (Uint32 i = 0; i < activeTris.size(); i++) {
208 const vector3d v1 = vector3d(m_vertices[m_indices[activeTris[i] + 0]]);
209 const vector3d v2 = vector3d(m_vertices[m_indices[activeTris[i] + 1]]);
210 const vector3d v3 = vector3d(m_vertices[m_indices[activeTris[i] + 2]]);
211 aabbs[i].min = aabbs[i].max = v1;
212 aabbs[i].Update(v2);
213 aabbs[i].Update(v3);
214 }
215 m_triTree.reset(new BVHTree(activeTris.size(), &activeTris[0], aabbs));
216 delete[] aabbs;
217
218 //
219 int *edgeIdxs = new int[m_numEdges];
220 memset(edgeIdxs, 0, sizeof(int) * m_numEdges);
221 for (int i = 0; i < m_numEdges; i++) {
222 edgeIdxs[i] = i;
223 }
224 m_edgeTree.reset(new BVHTree(m_numEdges, edgeIdxs, &m_aabbs[0]));
225 }
226
SlabsRayAabbTest(const BVHNode * n,const vector3f & start,const vector3f & invDir,isect_t * isect)227 static bool SlabsRayAabbTest(const BVHNode *n, const vector3f &start, const vector3f &invDir, isect_t *isect)
228 {
229 // PROFILE_SCOPED()
230 float
231 l1 = (n->aabb.min.x - start.x) * invDir.x,
232 l2 = (n->aabb.max.x - start.x) * invDir.x,
233 lmin = std::min(l1, l2),
234 lmax = std::max(l1, l2);
235
236 l1 = (n->aabb.min.y - start.y) * invDir.y;
237 l2 = (n->aabb.max.y - start.y) * invDir.y;
238 lmin = std::max(std::min(l1, l2), lmin);
239 lmax = std::min(std::max(l1, l2), lmax);
240
241 l1 = (n->aabb.min.z - start.z) * invDir.z;
242 l2 = (n->aabb.max.z - start.z) * invDir.z;
243 lmin = std::max(std::min(l1, l2), lmin);
244 lmax = std::min(std::max(l1, l2), lmax);
245
246 return ((lmax >= 0.f) & (lmax >= lmin) & (lmin < isect->dist));
247 }
248
TraceRay(const vector3f & start,const vector3f & dir,isect_t * isect) const249 void GeomTree::TraceRay(const vector3f &start, const vector3f &dir, isect_t *isect) const
250 {
251 PROFILE_SCOPED()
252 TraceRay(m_triTree->GetRoot(), start, dir, isect);
253 }
254
TraceRay(const BVHNode * currnode,const vector3f & a_origin,const vector3f & a_dir,isect_t * isect) const255 void GeomTree::TraceRay(const BVHNode *currnode, const vector3f &a_origin, const vector3f &a_dir, isect_t *isect) const
256 {
257 PROFILE_SCOPED()
258 BVHNode *stack[32];
259 int stackpos = -1;
260 const vector3f invDir( // avoid division by zero please
261 is_zero_exact(a_dir.x) ? 0.0f : (1.0f / a_dir.x),
262 is_zero_exact(a_dir.y) ? 0.0f : (1.0f / a_dir.y),
263 is_zero_exact(a_dir.z) ? 0.0f : (1.0f / a_dir.z));
264
265 for (;;) {
266 while (!currnode->IsLeaf()) {
267 if (!SlabsRayAabbTest(currnode, a_origin, invDir, isect)) goto pop_bstack;
268
269 stackpos++;
270 stack[stackpos] = currnode->kids[1];
271 currnode = currnode->kids[0];
272 }
273 // triangle intersection jizz
274 for (int i = 0; i < currnode->numTris; i++) {
275 RayTriIntersect(1, a_origin, &a_dir, currnode->triIndicesStart[i], isect);
276 }
277 pop_bstack:
278 if (stackpos < 0) break;
279 currnode = stack[stackpos];
280 stackpos--;
281 }
282 }
283
RayTriIntersect(int numRays,const vector3f & origin,const vector3f * dirs,int triIdx,isect_t * isects) const284 void GeomTree::RayTriIntersect(int numRays, const vector3f &origin, const vector3f *dirs, int triIdx, isect_t *isects) const
285 {
286 // PROFILE_SCOPED()
287 const vector3f a(m_vertices[m_indices[triIdx + 0]]);
288 const vector3f b(m_vertices[m_indices[triIdx + 1]]);
289 const vector3f c(m_vertices[m_indices[triIdx + 2]]);
290
291 const vector3f n = (c - a).Cross(b - a);
292 const float nominator = n.Dot(a - origin);
293
294 const vector3f v0_cross((c - origin).Cross(b - origin));
295 const vector3f v1_cross((b - origin).Cross(a - origin));
296 const vector3f v2_cross((a - origin).Cross(c - origin));
297
298 for (int i = 0; i < numRays; i++) {
299 const float v0d = v0_cross.Dot(dirs[i]);
300 const float v1d = v1_cross.Dot(dirs[i]);
301 const float v2d = v2_cross.Dot(dirs[i]);
302
303 if (((v0d > 0) && (v1d > 0) && (v2d > 0)) ||
304 ((v0d < 0) && (v1d < 0) && (v2d < 0))) {
305 const float dist = nominator / dirs[i].Dot(n);
306 if ((dist > 0) && (dist < isects[i].dist)) {
307 isects[i].dist = dist;
308 isects[i].triIdx = triIdx / 3;
309 }
310 }
311 }
312 }
313
GetTriNormal(int triIdx) const314 vector3f GeomTree::GetTriNormal(int triIdx) const
315 {
316 PROFILE_SCOPED()
317 const vector3f a(m_vertices[m_indices[3 * triIdx + 0]]);
318 const vector3f b(m_vertices[m_indices[3 * triIdx + 1]]);
319 const vector3f c(m_vertices[m_indices[3 * triIdx + 2]]);
320
321 return (b - a).Cross(c - a).Normalized();
322 }
323
Save(Serializer::Writer & wr) const324 void GeomTree::Save(Serializer::Writer &wr) const
325 {
326 PROFILE_SCOPED()
327 wr.Int32(m_numVertices);
328 wr.Int32(m_numEdges);
329 wr.Int32(m_numTris);
330 wr.Double(m_radius);
331
332 wr.Vector3d(m_aabb.max);
333 wr.Vector3d(m_aabb.min);
334 wr.Double(m_aabb.radius);
335
336 wr.Int32(m_numEdges);
337 for (Sint32 iAabb = 0; iAabb < m_numEdges; ++iAabb) {
338 wr << m_aabbs[iAabb];
339 }
340
341 for (Sint32 iEdge = 0; iEdge < m_numEdges; ++iEdge) {
342 auto &ed = m_edges[iEdge];
343 wr << ed.v1i << ed.v2i << ed.len << ed.dir << ed.triFlag;
344 }
345
346 for (Sint32 iVert = 0; iVert < m_numVertices; ++iVert) {
347 wr.Vector3f(m_vertices[iVert]);
348 }
349
350 for (Sint32 iIndi = 0; iIndi < (m_numTris * 3); ++iIndi) {
351 wr.Int32(m_indices[iIndi]);
352 }
353
354 for (Sint32 iTri = 0; iTri < m_numTris; ++iTri) {
355 wr.Int32(m_triFlags[iTri]);
356 }
357 }
358