From bc50d13580076a3d5997398f6797a3ffaa57d792 Mon Sep 17 00:00:00 2001 From: Peter Schaefer Date: Tue, 12 May 2015 11:39:47 +0200 Subject: [PATCH] builds mesh tree (disabled,because of some exeptions) --- Weave/GLM.cpp | 66 ++++++++++- Weave/GLM.h | 4 + Weave/Graphix/Model/IMesh.cpp | 211 +++++++++++++++++++++++++++++++--- Weave/Graphix/Model/IMesh.h | 53 ++++++--- Weave/Graphix/Model/Model.cpp | 36 ++++++ Weave/Graphix/Model/Model.h | 9 ++ 6 files changed, 345 insertions(+), 34 deletions(-) diff --git a/Weave/GLM.cpp b/Weave/GLM.cpp index b405afd..ef5ecf3 100644 --- a/Weave/GLM.cpp +++ b/Weave/GLM.cpp @@ -31,4 +31,68 @@ vec3 getScale(const mat4& matrix) vec3 orthoVec(const vec3& _direction, const vec3& _vec) { return normalize(_vec + _direction * dot(_direction, _vec)); -} \ No newline at end of file +} + + +vec3 sortVec3(const vec3& vec) +{ + vec3 sort; + if (vec[0] < vec[1]) + { + if (vec[0] < vec[2]) + { + sort[2] = 0; + if (vec[1] < vec[2]) + { + sort[0] = 2; + sort[1] = 1; + } + else + { + sort[0] = 1; + sort[1] = 2; + } + } + else + { + sort[0] = 1; + sort[1] = 0; + sort[2] = 2; + } + } + else + { + if (vec[1] < vec[2]) + { + sort[2] = 1; + if (vec[0] < vec[2]) + { + sort[0] = 2; + sort[1] = 0; + } + else + { + sort[0] = 0; + sort[1] = 2; + } + } + else + { + sort[0] = 0; + sort[1] = 1; + sort[2] = 2; + } + } + return sort; +} + +void updateVec3MinMax(vec3& updMin, vec3& updMax, const vec3& inpMin, const vec3& inpMax) +{ + for (int j = 0; j < 3; ++j) + { + if (inpMin[j] < updMin[j]) + updMin[j] = inpMin[j]; + if (inpMax[j] > updMax[j]) + updMax[j] = inpMax[j]; + } +} diff --git a/Weave/GLM.h b/Weave/GLM.h index b70bbd2..0330451 100644 --- a/Weave/GLM.h +++ b/Weave/GLM.h @@ -46,3 +46,7 @@ vec3 getScale(const mat4& matrix); vec3 orthoVec(const vec3& direction, const vec3& vec); +vec3 sortVec3(const vec3& vec); + +void updateVec3MinMax(vec3& updMin, vec3& updMax, const vec3& inpMin, const vec3& inpMax); + diff --git a/Weave/Graphix/Model/IMesh.cpp b/Weave/Graphix/Model/IMesh.cpp index f89a1a6..a87d788 100644 --- a/Weave/Graphix/Model/IMesh.cpp +++ b/Weave/Graphix/Model/IMesh.cpp @@ -7,6 +7,9 @@ #include "../../GLM.h" +#include +#include + #include "../Shader.h" #include "../Texture.h" #include "../../Message.h" @@ -14,13 +17,32 @@ #include "../Graphix.h" using std::string; - -IMesh::IMesh(const string& _modelpath, uint _mindex) : modelpath(_modelpath) +using std::list; +using std::array; +typedef Model::Triangle Triangle; +typedef IMesh::Node Node; + +// Vergleiche Unterbaum +//#define COMPARE_MTREE +// Vergleiche auch Triangles +#define COMPARE_FACE +// Fordere mindestens prozentuelles gleichgewicht .1 = 10% +#define HEAP_SCALE_BOUND .1f + +IMesh::IMesh(const string& _modelpath, uint _mindex) : modelpath(_modelpath), root(nullptr) { import(_modelpath, numvertices, numfaces, vertex, uvs, normals, index, _mindex); - updateBB(numvertices,vertex); +#ifdef COMPARE_MTREE + root = buildMeshTree(modelMat, numvertices, numfaces, vertex, normals, index); + + vec3 min, max; + root->getBBmm(min, max); + updateBB(min, max); +#else + updateBB(numvertices, vertex); +#endif genBuffer(vertexBuffer, numvertices * 3 * sizeof(float), (void*)vertex); genBuffer(normalBuffer, numvertices * 3 * sizeof(float), (void*)normals); @@ -29,12 +51,20 @@ IMesh::IMesh(const string& _modelpath, uint _mindex) : modelpath(_modelpath) } -IMesh::IMesh(const aiMesh* _mesh, const mat4& _transformation) : modelMat(_transformation), modelpath("IMesh") +IMesh::IMesh(const aiMesh* _mesh, const mat4& _transformation) : modelMat(_transformation), modelpath("IMesh"), root(nullptr) { import(_mesh, numvertices, numfaces, vertex, uvs, normals, index); - updateBB(numvertices,vertex,modelMat); +#ifdef COMPARE_MTREE + root = buildMeshTree(modelMat, numvertices, numfaces, vertex, normals, index); + + vec3 min, max; + root->getBBmm(min, max); + updateBB(min, max); +#else + updateBB(numvertices, vertex); +#endif genBuffer(vertexBuffer, numvertices * 3 * sizeof(float), (void*)vertex); genBuffer(normalBuffer, numvertices * 3 * sizeof(float), (void*)normals); @@ -43,7 +73,6 @@ IMesh::IMesh(const aiMesh* _mesh, const mat4& _transformation) : modelMat(_trans } - IMesh::~IMesh() { delete vertex, normals, uvs, index; @@ -54,11 +83,10 @@ IMesh::~IMesh() glDeleteBuffers(1, &uvBuffer); } - void IMesh::useModelMat(const mat4& _model, Shader* _shader) const { -// Model::useModelMat(_model, _shader); -// Model::useModelMat(_model * modelMat, _shader); + // Model::useModelMat(_model, _shader); + // Model::useModelMat(_model * modelMat, _shader); int tmp = _shader->getUniformLocation("uModel"); if (tmp >= 0) glUniformMatrix4fv(tmp, 1, GL_FALSE, value_ptr(_model* modelMat)); @@ -146,7 +174,7 @@ Overlap IMesh::checkColS2O(const mat4& _mMat, const Model* _model, const mat4& _ //Outer BBox Overlap firstBB = Model::checkColS2O(_mMat, _model, _modelMat); //if (!firstBB) - return firstBB; + return firstBB; //Inner Mesh //call _model->checkColO2STriangle @@ -162,7 +190,7 @@ Overlap IMesh::checkColS2O(const mat4& _mMat, const Model* _model, const mat4& _ // tmp = _model->checkColO2STriangle(_modelMat, pos, direction); // if (tmp) // secondT.update(tmp); - // } + // } //return secondT; } @@ -171,7 +199,7 @@ Overlap IMesh::checkColO2SBox(const mat4& _mMat, const vec3& _pos, const vec3& _ //Outer Mesh Overlap firstBB = Model::checkColO2SBox(_mMat, _pos, _size, _modelMat); //if (!firstBB) - return firstBB; + return firstBB; //Inner Mesh //call checkColO2STriangle @@ -182,10 +210,10 @@ Overlap IMesh::checkColO2STriangle(const mat4& _mMat, const vec3& _posB, const m { Overlap firstBB = Model::checkColO2STriangle(_mMat, _posB, _directionsB); //if (!firstBB) - return firstBB; + return firstBB; //Inner Mesh - + } IMesh::operator string() const @@ -193,12 +221,163 @@ IMesh::operator string() const return "IMesh"; } +void getPSfromNodeList(vec3& center, vec3& size, const list& TriList) +{ + vec3 BBmin, BBmax; + TriList.front()->getBBmm(BBmin, BBmax); + for (auto k = TriList.cbegin(); k != TriList.cend(); ++k) + { + (*k)->getUBBmm(BBmin, BBmax); + } + + size = (BBmax - BBmin) / 2.f; + center = (BBmin + BBmax) / 2.f; +} + +Node* IMesh::buildMeshTree(const list& _triList, vec3 center, vec3 size) +{ + //catch if list is empty + if (_triList.size() == 0) + return nullptr; + //catch if list has only one element => LEAF + if (_triList.size() == 1) + return _triList.front(); + //catch if list has only two elements => 2 LEAFS + if (_triList.size() == 2) + return new Node(center, size, _triList.front(), _triList.back()); + + //find longest dist + vec3 sort = sortVec3(size); + + //SPLIT and call self + array, 3> lower, upper; + vec3 tmpMin, tmpMax; + mat3 lMin, lMax, uMin, uMax; + int dim(0), bestDim; + float bestPerc(1), splitPerc(1); + + //try different DIM + + for (auto k = _triList.cbegin(); k != _triList.cend(); ++k) + { + (*k)->getBBmm(tmpMin, tmpMax); + vec3 mean = (*k)->getMean(); + for (dim = 0; dim < 3; ++dim) + { + if (mean[(int)sort[dim]] < center[(int)sort[dim]]) + { + if (lower[dim].size() < 1) + { + lMin[dim] = tmpMin; + lMax[dim] = tmpMax; + } + else + updateVec3MinMax(lMin[dim], lMax[dim], tmpMin, tmpMax); + lower[dim].push_back(*k); + } + else + { + if (upper[dim].size() < 1) + { + uMin[dim] = tmpMin; + uMax[dim] = tmpMax; + } + else + updateVec3MinMax(uMin[dim], uMax[dim], tmpMin, tmpMax); + upper[dim].push_back(*k); + } + } + } + for (dim = 0; dim < 3; ++dim) + { + splitPerc = abs(upper[dim].size() / (float)_triList.size() - .5f); + if (splitPerc < .4f) + break; + if (splitPerc < bestPerc) + { + bestDim = dim; + bestPerc = splitPerc; + } + + } + if (dim == 3) + dim = bestDim; + + + return new Node(center, size, buildMeshTree(lower[dim], (lMin[dim] + lMax[dim]) / 2.f, (lMax[dim] - lMin[dim]) / 2.f), + buildMeshTree(upper[dim], (uMin[dim] + uMax[dim]) / 2.f, (uMax[dim] - uMin[dim]) / 2.f)); +} + +Node* IMesh::buildMeshTree(const mat4& modelMat, const uint& numvertices, const uint& numfaces, const float* vertex, const float* normals, const uint* index) +{ + list node_list; + mat3 tmp_vert; + vec3 tmp_normal; + for (uint i = 0; i < numfaces; ++i) + { + tmp_vert[0] = (vec3)(modelMat*vec4(vertex[3 * index[3 * i]], vertex[3 * index[3 * i] + 1], vertex[3 * index[3 * i] + 2], 1.f)); + tmp_vert[1] = (vec3)(modelMat*vec4(vertex[3 * index[3 * i + 1]], vertex[3 * index[3 * i + 1] + 1], vertex[3 * index[3 * i + 1] + 2], 1.f)); + tmp_vert[2] = (vec3)(modelMat*vec4(vertex[3 * index[3 * i + 2]], vertex[3 * index[3 * i + 2] + 1], vertex[3 * index[3 * i + 2] + 2], 1.f)); + + tmp_normal = cross(tmp_vert[1] - tmp_vert[0], tmp_vert[2] - tmp_vert[0]); + if (0>dot(tmp_normal, vec3(normals[3 * index[3 * i]], normals[3 * index[3 * i] + 1], normals[3 * index[3 * i] + 2]))) + tmp_normal *= -1; + node_list.push_back(new Node(new Triangle(tmp_vert, tmp_normal))); + } + vec3 center, size; + getPSfromNodeList(center, size, node_list); + + + return buildMeshTree(node_list, center, size); +} + + +Node::Node(Triangle* tri) : element(tri), lNode(nullptr), uNode(nullptr), splitDim(-1) +{ + mean = element->getMean(); + element->getBBmm(min, max); + size = (max - min) / 2.f; + center = (min + max) / 2.f; +} + +//Node::Node(Triangle* tri, const vec3& cen, const vec3& siz, const vec3& mi, const vec3& ma) +// : element(tri), center(cen), size(siz), min(mi), max(ma), lNode(nullptr), uNode(nullptr), splitDim(-1) +//{ +//} + +Node::Node(const vec3& _center, const vec3& _size, Node* _lower, Node* _upper) + : element(nullptr), lNode(_lower), uNode(_upper), splitDim(-1), center(_center), size(_size) +{ +} + +Node::~Node() +{ + if (element != nullptr) + delete element; + else + delete lNode, uNode; +} + + +void Node::getBBcs(vec3& cen, vec3& siz) const +{ + cen = center; + siz = size; +} + +void Node::getBBmm(vec3& mi, vec3& ma) const +{ + mi = min; + ma = max; +} -IMesh::Node::Node() +void Node::getUBBmm(vec3& mi, vec3& ma) const { + updateVec3MinMax(mi, ma, min, max); } -IMesh::Node::~Node() +vec3 Node::getMean() const { + return mean; } diff --git a/Weave/Graphix/Model/IMesh.h b/Weave/Graphix/Model/IMesh.h index 7ba1d95..6fb78e8 100644 --- a/Weave/Graphix/Model/IMesh.h +++ b/Weave/Graphix/Model/IMesh.h @@ -1,6 +1,7 @@ #pragma once #include +#include #include "../../GLM.h" #include "../../Overlap.h" @@ -13,6 +14,8 @@ struct aiMesh; class IMesh : public Model { public: + class Node; + IMesh(const std::string& modelpath, uint index=0); IMesh(const aiMesh* mesh, const mat4& transformation); @@ -30,6 +33,39 @@ public: operator std::string() const override; + static Node* buildMeshTree(const mat4& modelMat, const uint& numvertices, const uint& numfaces, const float* vertex, const float* normals, const uint* index); + static Node* buildMeshTree(const std::list& triList, vec3 center, vec3 size); + + class Node + { + public: + Node(Triangle* tri); + //Node(Triangle* tri, const vec3& center, const vec3& size, const vec3& min, const vec3& max); + Node::Node(const vec3& center, const vec3& size, Node* lower, Node* upper); + ~Node(); + + /* sets center & size */ + void getBBcs(vec3& center, vec3& size) const; + /* sets min & max */ + void getBBmm(vec3& min, vec3& max) const; + /* updates min & max */ + void getUBBmm(vec3& min, vec3& max) const; + /* get mean*/ + vec3 getMean() const; + + private: + vec3 center; + vec3 size; + vec3 min; + vec3 max; + vec3 mean; + + Node *lNode, *uNode; + Model::Triangle *element; + + int splitDim; + }; + protected: std::string modelpath; @@ -42,26 +78,9 @@ protected: bool import(const std::string& modelpath, uint& numvertices, uint& numfaces, float*& vertex, float*& uvs, float*& normals, uint*& index , uint mindex = 0) const; bool import(const aiMesh* mesh, uint& numvertices, uint& numfaces, float*& vertex, float*& uvs, float*& normals, uint*& index) const; - class Node; Node* root; - class Node - { - public: - Node(); - ~Node(); - private: - vec3 center; - vec3 size_2; - - Node *lNode, *hNode; - Model::Triangle *element; - - int splitDim; - int splitCenter; - - }; }; \ No newline at end of file diff --git a/Weave/Graphix/Model/Model.cpp b/Weave/Graphix/Model/Model.cpp index 89e5088..f7bae80 100644 --- a/Weave/Graphix/Model/Model.cpp +++ b/Weave/Graphix/Model/Model.cpp @@ -523,4 +523,40 @@ Model::Triangle::Triangle(const mat3& _vertex, const vec3& _normal) : vertex(_ve Model::Triangle::~Triangle() { +} + +void Model::Triangle::getBBcs(vec3& center, vec3& size) const +{ + vec3 BBmin = vertex[0]; + vec3 BBmax = BBmin; + getUBBmm(BBmin, BBmax); + + size = (BBmax - BBmin) / 2.f; + center = (BBmin + BBmax) / 2.f; +} + +void Model::Triangle::getBBmm(vec3& min, vec3& max) const +{ + min = vertex[0]; + max = min; + getUBBmm(min, max); +} + +void Model::Triangle::getUBBmm(vec3& min, vec3& max) const +{ + for (uint i = 0; i < 3; ++i) + { + for (uint j = 0; j < 3; ++j) + { + if (vertex[i][j] < min[j]) + min[j] = vertex[i][j]; + if (vertex[i][j] > max[j]) + max[j] = vertex[i][j]; + } + } +} + +vec3 Model::Triangle::getMean() const +{ + return (vertex[0] + vertex[1] + vertex[2]) / 3.f; } \ No newline at end of file diff --git a/Weave/Graphix/Model/Model.h b/Weave/Graphix/Model/Model.h index e8ca858..106bf0e 100644 --- a/Weave/Graphix/Model/Model.h +++ b/Weave/Graphix/Model/Model.h @@ -58,6 +58,15 @@ public: Triangle(const mat3& vertex, const vec3& normal); ~Triangle(); + /* sets center & size */ + void getBBcs(vec3& center, vec3& size) const; + /* sets min & max */ + void getBBmm(vec3& min, vec3& max) const; + /* updates min & max */ + void getUBBmm(vec3& min, vec3& max) const; + /* get mean*/ + vec3 getMean() const; + const mat3 vertex; const vec3 normal; -- 2.47.3