aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/src/others/irrlicht-1.8.1/source/Irrlicht/COctreeTriangleSelector.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/others/irrlicht-1.8.1/source/Irrlicht/COctreeTriangleSelector.cpp')
-rw-r--r--src/others/irrlicht-1.8.1/source/Irrlicht/COctreeTriangleSelector.cpp265
1 files changed, 265 insertions, 0 deletions
diff --git a/src/others/irrlicht-1.8.1/source/Irrlicht/COctreeTriangleSelector.cpp b/src/others/irrlicht-1.8.1/source/Irrlicht/COctreeTriangleSelector.cpp
new file mode 100644
index 0000000..657f911
--- /dev/null
+++ b/src/others/irrlicht-1.8.1/source/Irrlicht/COctreeTriangleSelector.cpp
@@ -0,0 +1,265 @@
1// Copyright (C) 2002-2012 Nikolaus Gebhardt
2// This file is part of the "Irrlicht Engine".
3// For conditions of distribution and use, see copyright notice in irrlicht.h
4
5#include "COctreeTriangleSelector.h"
6#include "ISceneNode.h"
7
8#include "os.h"
9
10namespace irr
11{
12namespace scene
13{
14
15//! constructor
16COctreeTriangleSelector::COctreeTriangleSelector(const IMesh* mesh,
17 ISceneNode* node, s32 minimalPolysPerNode)
18 : CTriangleSelector(mesh, node), Root(0), NodeCount(0),
19 MinimalPolysPerNode(minimalPolysPerNode)
20{
21 #ifdef _DEBUG
22 setDebugName("COctreeTriangleSelector");
23 #endif
24
25 if (!Triangles.empty())
26 {
27 const u32 start = os::Timer::getRealTime();
28
29 // create the triangle octree
30 Root = new SOctreeNode();
31 Root->Triangles = Triangles;
32 constructOctree(Root);
33
34 c8 tmp[256];
35 sprintf(tmp, "Needed %ums to create OctreeTriangleSelector.(%d nodes, %u polys)",
36 os::Timer::getRealTime() - start, NodeCount, Triangles.size());
37 os::Printer::log(tmp, ELL_INFORMATION);
38 }
39}
40
41
42//! destructor
43COctreeTriangleSelector::~COctreeTriangleSelector()
44{
45 delete Root;
46}
47
48
49void COctreeTriangleSelector::constructOctree(SOctreeNode* node)
50{
51 ++NodeCount;
52
53 node->Box.reset(node->Triangles[0].pointA);
54
55 // get bounding box
56 const u32 cnt = node->Triangles.size();
57 for (u32 i=0; i<cnt; ++i)
58 {
59 node->Box.addInternalPoint(node->Triangles[i].pointA);
60 node->Box.addInternalPoint(node->Triangles[i].pointB);
61 node->Box.addInternalPoint(node->Triangles[i].pointC);
62 }
63
64 const core::vector3df& middle = node->Box.getCenter();
65 core::vector3df edges[8];
66 node->Box.getEdges(edges);
67
68 core::aabbox3d<f32> box;
69 core::array<core::triangle3df> keepTriangles;
70
71 // calculate children
72
73 if (!node->Box.isEmpty() && (s32)node->Triangles.size() > MinimalPolysPerNode)
74 for (s32 ch=0; ch<8; ++ch)
75 {
76 box.reset(middle);
77 box.addInternalPoint(edges[ch]);
78 node->Child[ch] = new SOctreeNode();
79
80 for (s32 i=0; i<(s32)node->Triangles.size(); ++i)
81 {
82 if (node->Triangles[i].isTotalInsideBox(box))
83 {
84 node->Child[ch]->Triangles.push_back(node->Triangles[i]);
85 //node->Triangles.erase(i);
86 //--i;
87 }
88 else
89 {
90 keepTriangles.push_back(node->Triangles[i]);
91 }
92 }
93 memcpy(node->Triangles.pointer(), keepTriangles.pointer(),
94 sizeof(core::triangle3df)*keepTriangles.size());
95
96 node->Triangles.set_used(keepTriangles.size());
97 keepTriangles.set_used(0);
98
99 if (node->Child[ch]->Triangles.empty())
100 {
101 delete node->Child[ch];
102 node->Child[ch] = 0;
103 }
104 else
105 constructOctree(node->Child[ch]);
106 }
107}
108
109
110//! Gets all triangles which lie within a specific bounding box.
111void COctreeTriangleSelector::getTriangles(core::triangle3df* triangles,
112 s32 arraySize, s32& outTriangleCount,
113 const core::aabbox3d<f32>& box,
114 const core::matrix4* transform) const
115{
116 core::matrix4 mat(core::matrix4::EM4CONST_NOTHING);
117 core::aabbox3d<f32> invbox = box;
118
119 if (SceneNode)
120 {
121 SceneNode->getAbsoluteTransformation().getInverse(mat);
122 mat.transformBoxEx(invbox);
123 }
124
125 if (transform)
126 mat = *transform;
127 else
128 mat.makeIdentity();
129
130 if (SceneNode)
131 mat *= SceneNode->getAbsoluteTransformation();
132
133 s32 trianglesWritten = 0;
134
135 if (Root)
136 getTrianglesFromOctree(Root, trianglesWritten,
137 arraySize, invbox, &mat, triangles);
138
139 outTriangleCount = trianglesWritten;
140}
141
142
143void COctreeTriangleSelector::getTrianglesFromOctree(
144 SOctreeNode* node, s32& trianglesWritten,
145 s32 maximumSize, const core::aabbox3d<f32>& box,
146 const core::matrix4* mat, core::triangle3df* triangles) const
147{
148 if (!box.intersectsWithBox(node->Box))
149 return;
150
151 const u32 cnt = node->Triangles.size();
152
153 for (u32 i=0; i<cnt; ++i)
154 {
155 const core::triangle3df& srcTri = node->Triangles[i];
156 // This isn't an accurate test, but it's fast, and the
157 // API contract doesn't guarantee complete accuracy.
158 if (srcTri.isTotalOutsideBox(box))
159 continue;
160
161 core::triangle3df& dstTri = triangles[trianglesWritten];
162 mat->transformVect(dstTri.pointA, srcTri.pointA );
163 mat->transformVect(dstTri.pointB, srcTri.pointB );
164 mat->transformVect(dstTri.pointC, srcTri.pointC );
165 ++trianglesWritten;
166
167 // Halt when the out array is full.
168 if (trianglesWritten == maximumSize)
169 return;
170 }
171
172 for (u32 i=0; i<8; ++i)
173 if (node->Child[i])
174 getTrianglesFromOctree(node->Child[i], trianglesWritten,
175 maximumSize, box, mat, triangles);
176}
177
178
179//! Gets all triangles which have or may have contact with a 3d line.
180// new version: from user Piraaate
181void COctreeTriangleSelector::getTriangles(core::triangle3df* triangles, s32 arraySize,
182 s32& outTriangleCount, const core::line3d<f32>& line,
183 const core::matrix4* transform) const
184{
185#if 0
186 core::aabbox3d<f32> box(line.start);
187 box.addInternalPoint(line.end);
188
189 // TODO: Could be optimized for line a little bit more.
190 COctreeTriangleSelector::getTriangles(triangles, arraySize, outTriangleCount,
191 box, transform);
192#else
193
194 core::matrix4 mat ( core::matrix4::EM4CONST_NOTHING );
195
196 core::vector3df vectStartInv ( line.start ), vectEndInv ( line.end );
197 if (SceneNode)
198 {
199 mat = SceneNode->getAbsoluteTransformation();
200 mat.makeInverse();
201 mat.transformVect(vectStartInv, line.start);
202 mat.transformVect(vectEndInv, line.end);
203 }
204 core::line3d<f32> invline(vectStartInv, vectEndInv);
205
206 mat.makeIdentity();
207
208 if (transform)
209 mat = (*transform);
210
211 if (SceneNode)
212 mat *= SceneNode->getAbsoluteTransformation();
213
214 s32 trianglesWritten = 0;
215
216 if (Root)
217 getTrianglesFromOctree(Root, trianglesWritten, arraySize, invline, &mat, triangles);
218
219 outTriangleCount = trianglesWritten;
220#endif
221}
222
223void COctreeTriangleSelector::getTrianglesFromOctree(SOctreeNode* node,
224 s32& trianglesWritten, s32 maximumSize, const core::line3d<f32>& line,
225 const core::matrix4* transform, core::triangle3df* triangles) const
226{
227 if (!node->Box.intersectsWithLine(line))
228 return;
229
230 s32 cnt = node->Triangles.size();
231 if (cnt + trianglesWritten > maximumSize)
232 cnt -= cnt + trianglesWritten - maximumSize;
233
234 s32 i;
235
236 if ( transform->isIdentity() )
237 {
238 for (i=0; i<cnt; ++i)
239 {
240 triangles[trianglesWritten] = node->Triangles[i];
241 ++trianglesWritten;
242 }
243 }
244 else
245 {
246 for (i=0; i<cnt; ++i)
247 {
248 triangles[trianglesWritten] = node->Triangles[i];
249 transform->transformVect(triangles[trianglesWritten].pointA);
250 transform->transformVect(triangles[trianglesWritten].pointB);
251 transform->transformVect(triangles[trianglesWritten].pointC);
252 ++trianglesWritten;
253 }
254 }
255
256 for (i=0; i<8; ++i)
257 if (node->Child[i])
258 getTrianglesFromOctree(node->Child[i], trianglesWritten,
259 maximumSize, line, transform, triangles);
260}
261
262
263} // end namespace scene
264} // end namespace irr
265
generated by cgit v1.1 at 2024-06-27 09:18:17 +0000