From 393b5cd1dc438872af89d334ef6e5fcc59f27d47 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Sun, 13 Jan 2013 17:24:39 +1000 Subject: Added Irrlicht 1.8, but without all the Windows binaries. --- .../source/Irrlicht/COctreeTriangleSelector.cpp | 265 +++++++++++++++++++++ 1 file changed, 265 insertions(+) create mode 100644 libraries/irrlicht-1.8/source/Irrlicht/COctreeTriangleSelector.cpp (limited to 'libraries/irrlicht-1.8/source/Irrlicht/COctreeTriangleSelector.cpp') diff --git a/libraries/irrlicht-1.8/source/Irrlicht/COctreeTriangleSelector.cpp b/libraries/irrlicht-1.8/source/Irrlicht/COctreeTriangleSelector.cpp new file mode 100644 index 0000000..657f911 --- /dev/null +++ b/libraries/irrlicht-1.8/source/Irrlicht/COctreeTriangleSelector.cpp @@ -0,0 +1,265 @@ +// Copyright (C) 2002-2012 Nikolaus Gebhardt +// This file is part of the "Irrlicht Engine". +// For conditions of distribution and use, see copyright notice in irrlicht.h + +#include "COctreeTriangleSelector.h" +#include "ISceneNode.h" + +#include "os.h" + +namespace irr +{ +namespace scene +{ + +//! constructor +COctreeTriangleSelector::COctreeTriangleSelector(const IMesh* mesh, + ISceneNode* node, s32 minimalPolysPerNode) + : CTriangleSelector(mesh, node), Root(0), NodeCount(0), + MinimalPolysPerNode(minimalPolysPerNode) +{ + #ifdef _DEBUG + setDebugName("COctreeTriangleSelector"); + #endif + + if (!Triangles.empty()) + { + const u32 start = os::Timer::getRealTime(); + + // create the triangle octree + Root = new SOctreeNode(); + Root->Triangles = Triangles; + constructOctree(Root); + + c8 tmp[256]; + sprintf(tmp, "Needed %ums to create OctreeTriangleSelector.(%d nodes, %u polys)", + os::Timer::getRealTime() - start, NodeCount, Triangles.size()); + os::Printer::log(tmp, ELL_INFORMATION); + } +} + + +//! destructor +COctreeTriangleSelector::~COctreeTriangleSelector() +{ + delete Root; +} + + +void COctreeTriangleSelector::constructOctree(SOctreeNode* node) +{ + ++NodeCount; + + node->Box.reset(node->Triangles[0].pointA); + + // get bounding box + const u32 cnt = node->Triangles.size(); + for (u32 i=0; iBox.addInternalPoint(node->Triangles[i].pointA); + node->Box.addInternalPoint(node->Triangles[i].pointB); + node->Box.addInternalPoint(node->Triangles[i].pointC); + } + + const core::vector3df& middle = node->Box.getCenter(); + core::vector3df edges[8]; + node->Box.getEdges(edges); + + core::aabbox3d box; + core::array keepTriangles; + + // calculate children + + if (!node->Box.isEmpty() && (s32)node->Triangles.size() > MinimalPolysPerNode) + for (s32 ch=0; ch<8; ++ch) + { + box.reset(middle); + box.addInternalPoint(edges[ch]); + node->Child[ch] = new SOctreeNode(); + + for (s32 i=0; i<(s32)node->Triangles.size(); ++i) + { + if (node->Triangles[i].isTotalInsideBox(box)) + { + node->Child[ch]->Triangles.push_back(node->Triangles[i]); + //node->Triangles.erase(i); + //--i; + } + else + { + keepTriangles.push_back(node->Triangles[i]); + } + } + memcpy(node->Triangles.pointer(), keepTriangles.pointer(), + sizeof(core::triangle3df)*keepTriangles.size()); + + node->Triangles.set_used(keepTriangles.size()); + keepTriangles.set_used(0); + + if (node->Child[ch]->Triangles.empty()) + { + delete node->Child[ch]; + node->Child[ch] = 0; + } + else + constructOctree(node->Child[ch]); + } +} + + +//! Gets all triangles which lie within a specific bounding box. +void COctreeTriangleSelector::getTriangles(core::triangle3df* triangles, + s32 arraySize, s32& outTriangleCount, + const core::aabbox3d& box, + const core::matrix4* transform) const +{ + core::matrix4 mat(core::matrix4::EM4CONST_NOTHING); + core::aabbox3d invbox = box; + + if (SceneNode) + { + SceneNode->getAbsoluteTransformation().getInverse(mat); + mat.transformBoxEx(invbox); + } + + if (transform) + mat = *transform; + else + mat.makeIdentity(); + + if (SceneNode) + mat *= SceneNode->getAbsoluteTransformation(); + + s32 trianglesWritten = 0; + + if (Root) + getTrianglesFromOctree(Root, trianglesWritten, + arraySize, invbox, &mat, triangles); + + outTriangleCount = trianglesWritten; +} + + +void COctreeTriangleSelector::getTrianglesFromOctree( + SOctreeNode* node, s32& trianglesWritten, + s32 maximumSize, const core::aabbox3d& box, + const core::matrix4* mat, core::triangle3df* triangles) const +{ + if (!box.intersectsWithBox(node->Box)) + return; + + const u32 cnt = node->Triangles.size(); + + for (u32 i=0; iTriangles[i]; + // This isn't an accurate test, but it's fast, and the + // API contract doesn't guarantee complete accuracy. + if (srcTri.isTotalOutsideBox(box)) + continue; + + core::triangle3df& dstTri = triangles[trianglesWritten]; + mat->transformVect(dstTri.pointA, srcTri.pointA ); + mat->transformVect(dstTri.pointB, srcTri.pointB ); + mat->transformVect(dstTri.pointC, srcTri.pointC ); + ++trianglesWritten; + + // Halt when the out array is full. + if (trianglesWritten == maximumSize) + return; + } + + for (u32 i=0; i<8; ++i) + if (node->Child[i]) + getTrianglesFromOctree(node->Child[i], trianglesWritten, + maximumSize, box, mat, triangles); +} + + +//! Gets all triangles which have or may have contact with a 3d line. +// new version: from user Piraaate +void COctreeTriangleSelector::getTriangles(core::triangle3df* triangles, s32 arraySize, + s32& outTriangleCount, const core::line3d& line, + const core::matrix4* transform) const +{ +#if 0 + core::aabbox3d box(line.start); + box.addInternalPoint(line.end); + + // TODO: Could be optimized for line a little bit more. + COctreeTriangleSelector::getTriangles(triangles, arraySize, outTriangleCount, + box, transform); +#else + + core::matrix4 mat ( core::matrix4::EM4CONST_NOTHING ); + + core::vector3df vectStartInv ( line.start ), vectEndInv ( line.end ); + if (SceneNode) + { + mat = SceneNode->getAbsoluteTransformation(); + mat.makeInverse(); + mat.transformVect(vectStartInv, line.start); + mat.transformVect(vectEndInv, line.end); + } + core::line3d invline(vectStartInv, vectEndInv); + + mat.makeIdentity(); + + if (transform) + mat = (*transform); + + if (SceneNode) + mat *= SceneNode->getAbsoluteTransformation(); + + s32 trianglesWritten = 0; + + if (Root) + getTrianglesFromOctree(Root, trianglesWritten, arraySize, invline, &mat, triangles); + + outTriangleCount = trianglesWritten; +#endif +} + +void COctreeTriangleSelector::getTrianglesFromOctree(SOctreeNode* node, + s32& trianglesWritten, s32 maximumSize, const core::line3d& line, + const core::matrix4* transform, core::triangle3df* triangles) const +{ + if (!node->Box.intersectsWithLine(line)) + return; + + s32 cnt = node->Triangles.size(); + if (cnt + trianglesWritten > maximumSize) + cnt -= cnt + trianglesWritten - maximumSize; + + s32 i; + + if ( transform->isIdentity() ) + { + for (i=0; iTriangles[i]; + ++trianglesWritten; + } + } + else + { + for (i=0; iTriangles[i]; + transform->transformVect(triangles[trianglesWritten].pointA); + transform->transformVect(triangles[trianglesWritten].pointB); + transform->transformVect(triangles[trianglesWritten].pointC); + ++trianglesWritten; + } + } + + for (i=0; i<8; ++i) + if (node->Child[i]) + getTrianglesFromOctree(node->Child[i], trianglesWritten, + maximumSize, line, transform, triangles); +} + + +} // end namespace scene +} // end namespace irr + -- cgit v1.1