From fdaa2920eb21fff3320a17e9239e04dfadecdb00 Mon Sep 17 00:00:00 2001 From: Juan Linietsky Date: Sat, 18 Apr 2015 14:38:54 -0300 Subject: Updated copyright year in all headers --- core/math/triangle_mesh.cpp | 1082 +++++++++++++++++++++---------------------- 1 file changed, 541 insertions(+), 541 deletions(-) (limited to 'core/math/triangle_mesh.cpp') diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp index 111ceca18..70cb639fc 100644 --- a/core/math/triangle_mesh.cpp +++ b/core/math/triangle_mesh.cpp @@ -5,7 +5,7 @@ /* GODOT ENGINE */ /* http://www.godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2007-2015 Juan Linietsky, Ariel Manzur. */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -26,543 +26,543 @@ /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ -#include "triangle_mesh.h" -#include "sort.h" - - - -int TriangleMesh::_create_bvh(BVH*p_bvh,BVH** p_bb,int p_from,int p_size,int p_depth,int&max_depth,int&max_alloc) { - - - if (p_depth>max_depth) { - max_depth=p_depth; - } - - if (p_size==1) { - - - return p_bb[p_from]-p_bvh; - } else if (p_size==0) { - - return -1; - } - - - AABB aabb; - aabb=p_bb[p_from]->aabb; - for(int i=1;iaabb); - } - - int li=aabb.get_longest_axis_index(); - - switch(li) { - - case Vector3::AXIS_X: { - SortArray sort_x; - sort_x.nth_element(0,p_size,p_size/2,&p_bb[p_from]); - //sort_x.sort(&p_bb[p_from],p_size); - } break; - case Vector3::AXIS_Y: { - SortArray sort_y; - sort_y.nth_element(0,p_size,p_size/2,&p_bb[p_from]); - //sort_y.sort(&p_bb[p_from],p_size); - } break; - case Vector3::AXIS_Z: { - SortArray sort_z; - sort_z.nth_element(0,p_size,p_size/2,&p_bb[p_from]); - //sort_z.sort(&p_bb[p_from],p_size); - - } break; - } - - - int left = _create_bvh(p_bvh,p_bb,p_from,p_size/2,p_depth+1,max_depth,max_alloc); - int right = _create_bvh(p_bvh,p_bb,p_from+p_size/2,p_size-p_size/2,p_depth+1,max_depth,max_alloc); - - int index=max_alloc++; - BVH *_new = &p_bvh[index]; - _new->aabb=aabb; - _new->center=aabb.pos+aabb.size*0.5; - _new->face_index=-1; - _new->left=left; - _new->right=right; - - return index; - -} - - -void TriangleMesh::create(const DVector& p_faces) { - - valid=false; - - int fc=p_faces.size(); - ERR_FAIL_COND(!fc || ((fc%3) != 0)); - fc/=3; - triangles.resize(fc); - - bvh.resize(fc*3); //will never be larger than this (todo make better) - DVector::Write bw = bvh.write(); - - { - - //create faces and indices and base bvh - //except for the Set for repeated triangles, everything - //goes in-place. - - DVector::Read r = p_faces.read(); - DVector::Write w = triangles.write(); - Map db; - - for(int i=0;i::Element *E=db.find(vs); - if (E) { - vidx=E->get(); - } else { - vidx=db.size(); - db[vs]=vidx; - } - - f.indices[j]=vidx; - if (j==0) - bw[i].aabb.pos=vs; - else - bw[i].aabb.expand_to(vs); - } - - f.normal=Face3(r[i*3+0],r[i*3+1],r[i*3+2]).get_plane().get_normal(); - - bw[i].left=-1; - bw[i].right=-1; - bw[i].face_index=i; - bw[i].center=bw[i].aabb.pos+bw[i].aabb.size*0.5; - } - - vertices.resize(db.size()); - DVector::Write vw = vertices.write(); - for (Map::Element *E=db.front();E;E=E->next()) { - vw[E->get()]=E->key(); - } - - } - - DVector bwptrs; - bwptrs.resize(fc); - DVector::Write bwp = bwptrs.write(); - for(int i=0;i::Write(); //clearup - bvh.resize(max_alloc); //resize back - - valid=true; - -} - - -Vector3 TriangleMesh::get_area_normal(const AABB& p_aabb) const { - - uint32_t* stack = (uint32_t*)alloca(sizeof(int)*max_depth); - - enum { - TEST_AABB_BIT=0, - VISIT_LEFT_BIT=1, - VISIT_RIGHT_BIT=2, - VISIT_DONE_BIT=3, - VISITED_BIT_SHIFT=29, - NODE_IDX_MASK=(1<::Read trianglesr = triangles.read(); - DVector::Read verticesr=vertices.read(); - DVector::Read bvhr=bvh.read(); - - const Triangle *triangleptr=trianglesr.ptr(); - const Vector3 *vertexptr=verticesr.ptr(); - int pos=bvh.size()-1; - const BVH *bvhptr = bvhr.ptr(); - - stack[0]=pos; - while(true) { - - uint32_t node = stack[level]&NODE_IDX_MASK; - const BVH &b = bvhptr[ node ]; - bool done=false; - - switch(stack[level]>>VISITED_BIT_SHIFT) { - case TEST_AABB_BIT: { - - - bool valid = b.aabb.intersects(p_aabb); - if (!valid) { - - stack[level]=(VISIT_DONE_BIT<=0) { - - const Triangle &s=triangleptr[ b.face_index ]; - n+=s.normal; - n_count++; - - stack[level]=(VISIT_DONE_BIT<0) - n/=n_count; - - return n; - -} - - -bool TriangleMesh::intersect_segment(const Vector3& p_begin,const Vector3& p_end,Vector3 &r_point, Vector3 &r_normal) const { - - - uint32_t* stack = (uint32_t*)alloca(sizeof(int)*max_depth); - - enum { - TEST_AABB_BIT=0, - VISIT_LEFT_BIT=1, - VISIT_RIGHT_BIT=2, - VISIT_DONE_BIT=3, - VISITED_BIT_SHIFT=29, - NODE_IDX_MASK=(1<::Read trianglesr = triangles.read(); - DVector::Read verticesr=vertices.read(); - DVector::Read bvhr=bvh.read(); - - const Triangle *triangleptr=trianglesr.ptr(); - const Vector3 *vertexptr=verticesr.ptr(); - int pos=bvh.size()-1; - const BVH *bvhptr = bvhr.ptr(); - - stack[0]=pos; - while(true) { - - uint32_t node = stack[level]&NODE_IDX_MASK; - const BVH &b = bvhptr[ node ]; - bool done=false; - - switch(stack[level]>>VISITED_BIT_SHIFT) { - case TEST_AABB_BIT: { - - - bool valid = b.aabb.intersects_segment(p_begin,p_end); -// bool valid = b.aabb.intersects(ray_aabb); - - if (!valid) { - - stack[level]=(VISIT_DONE_BIT<=0) { - - const Triangle &s=triangleptr[ b.face_index ]; - Face3 f3(vertexptr[ s.indices[0] ],vertexptr[ s.indices[1] ],vertexptr[ s.indices[2] ]); - - - Vector3 res; - - if (f3.intersects_segment(p_begin,p_end,&res)) { - - - float nd = n.dot(res); - if (nd0) - r_normal=-r_normal; - } - - return inters; -} - - -bool TriangleMesh::intersect_ray(const Vector3& p_begin,const Vector3& p_dir,Vector3 &r_point, Vector3 &r_normal) const { - - - uint32_t* stack = (uint32_t*)alloca(sizeof(int)*max_depth); - - enum { - TEST_AABB_BIT=0, - VISIT_LEFT_BIT=1, - VISIT_RIGHT_BIT=2, - VISIT_DONE_BIT=3, - VISITED_BIT_SHIFT=29, - NODE_IDX_MASK=(1<::Read trianglesr = triangles.read(); - DVector::Read verticesr=vertices.read(); - DVector::Read bvhr=bvh.read(); - - const Triangle *triangleptr=trianglesr.ptr(); - const Vector3 *vertexptr=verticesr.ptr(); - int pos=bvh.size()-1; - const BVH *bvhptr = bvhr.ptr(); - - stack[0]=pos; - while(true) { - - uint32_t node = stack[level]&NODE_IDX_MASK; - const BVH &b = bvhptr[ node ]; - bool done=false; - - switch(stack[level]>>VISITED_BIT_SHIFT) { - case TEST_AABB_BIT: { - - - bool valid = b.aabb.intersects_ray(p_begin,p_dir); - if (!valid) { - - stack[level]=(VISIT_DONE_BIT<=0) { - - const Triangle &s=triangleptr[ b.face_index ]; - Face3 f3(vertexptr[ s.indices[0] ],vertexptr[ s.indices[1] ],vertexptr[ s.indices[2] ]); - - - Vector3 res; - - if (f3.intersects_ray(p_begin,p_dir,&res)) { - - - float nd = n.dot(res); - if (nd0) - r_normal=-r_normal; - } - - return inters; -} - -bool TriangleMesh::is_valid() const { - - return valid; -} - -DVector TriangleMesh::get_faces() const { - - if (!valid) - return DVector(); - - DVector faces; - int ts = triangles.size(); - faces.resize(triangles.size()); - - DVector::Write w=faces.write(); - DVector::Read r = triangles.read(); - DVector::Read rv = vertices.read(); - - for(int i=0;i::Write(); - return faces; -} - -TriangleMesh::TriangleMesh() { - - valid=false; - max_depth=0; -} +#include "triangle_mesh.h" +#include "sort.h" + + + +int TriangleMesh::_create_bvh(BVH*p_bvh,BVH** p_bb,int p_from,int p_size,int p_depth,int&max_depth,int&max_alloc) { + + + if (p_depth>max_depth) { + max_depth=p_depth; + } + + if (p_size==1) { + + + return p_bb[p_from]-p_bvh; + } else if (p_size==0) { + + return -1; + } + + + AABB aabb; + aabb=p_bb[p_from]->aabb; + for(int i=1;iaabb); + } + + int li=aabb.get_longest_axis_index(); + + switch(li) { + + case Vector3::AXIS_X: { + SortArray sort_x; + sort_x.nth_element(0,p_size,p_size/2,&p_bb[p_from]); + //sort_x.sort(&p_bb[p_from],p_size); + } break; + case Vector3::AXIS_Y: { + SortArray sort_y; + sort_y.nth_element(0,p_size,p_size/2,&p_bb[p_from]); + //sort_y.sort(&p_bb[p_from],p_size); + } break; + case Vector3::AXIS_Z: { + SortArray sort_z; + sort_z.nth_element(0,p_size,p_size/2,&p_bb[p_from]); + //sort_z.sort(&p_bb[p_from],p_size); + + } break; + } + + + int left = _create_bvh(p_bvh,p_bb,p_from,p_size/2,p_depth+1,max_depth,max_alloc); + int right = _create_bvh(p_bvh,p_bb,p_from+p_size/2,p_size-p_size/2,p_depth+1,max_depth,max_alloc); + + int index=max_alloc++; + BVH *_new = &p_bvh[index]; + _new->aabb=aabb; + _new->center=aabb.pos+aabb.size*0.5; + _new->face_index=-1; + _new->left=left; + _new->right=right; + + return index; + +} + + +void TriangleMesh::create(const DVector& p_faces) { + + valid=false; + + int fc=p_faces.size(); + ERR_FAIL_COND(!fc || ((fc%3) != 0)); + fc/=3; + triangles.resize(fc); + + bvh.resize(fc*3); //will never be larger than this (todo make better) + DVector::Write bw = bvh.write(); + + { + + //create faces and indices and base bvh + //except for the Set for repeated triangles, everything + //goes in-place. + + DVector::Read r = p_faces.read(); + DVector::Write w = triangles.write(); + Map db; + + for(int i=0;i::Element *E=db.find(vs); + if (E) { + vidx=E->get(); + } else { + vidx=db.size(); + db[vs]=vidx; + } + + f.indices[j]=vidx; + if (j==0) + bw[i].aabb.pos=vs; + else + bw[i].aabb.expand_to(vs); + } + + f.normal=Face3(r[i*3+0],r[i*3+1],r[i*3+2]).get_plane().get_normal(); + + bw[i].left=-1; + bw[i].right=-1; + bw[i].face_index=i; + bw[i].center=bw[i].aabb.pos+bw[i].aabb.size*0.5; + } + + vertices.resize(db.size()); + DVector::Write vw = vertices.write(); + for (Map::Element *E=db.front();E;E=E->next()) { + vw[E->get()]=E->key(); + } + + } + + DVector bwptrs; + bwptrs.resize(fc); + DVector::Write bwp = bwptrs.write(); + for(int i=0;i::Write(); //clearup + bvh.resize(max_alloc); //resize back + + valid=true; + +} + + +Vector3 TriangleMesh::get_area_normal(const AABB& p_aabb) const { + + uint32_t* stack = (uint32_t*)alloca(sizeof(int)*max_depth); + + enum { + TEST_AABB_BIT=0, + VISIT_LEFT_BIT=1, + VISIT_RIGHT_BIT=2, + VISIT_DONE_BIT=3, + VISITED_BIT_SHIFT=29, + NODE_IDX_MASK=(1<::Read trianglesr = triangles.read(); + DVector::Read verticesr=vertices.read(); + DVector::Read bvhr=bvh.read(); + + const Triangle *triangleptr=trianglesr.ptr(); + const Vector3 *vertexptr=verticesr.ptr(); + int pos=bvh.size()-1; + const BVH *bvhptr = bvhr.ptr(); + + stack[0]=pos; + while(true) { + + uint32_t node = stack[level]&NODE_IDX_MASK; + const BVH &b = bvhptr[ node ]; + bool done=false; + + switch(stack[level]>>VISITED_BIT_SHIFT) { + case TEST_AABB_BIT: { + + + bool valid = b.aabb.intersects(p_aabb); + if (!valid) { + + stack[level]=(VISIT_DONE_BIT<=0) { + + const Triangle &s=triangleptr[ b.face_index ]; + n+=s.normal; + n_count++; + + stack[level]=(VISIT_DONE_BIT<0) + n/=n_count; + + return n; + +} + + +bool TriangleMesh::intersect_segment(const Vector3& p_begin,const Vector3& p_end,Vector3 &r_point, Vector3 &r_normal) const { + + + uint32_t* stack = (uint32_t*)alloca(sizeof(int)*max_depth); + + enum { + TEST_AABB_BIT=0, + VISIT_LEFT_BIT=1, + VISIT_RIGHT_BIT=2, + VISIT_DONE_BIT=3, + VISITED_BIT_SHIFT=29, + NODE_IDX_MASK=(1<::Read trianglesr = triangles.read(); + DVector::Read verticesr=vertices.read(); + DVector::Read bvhr=bvh.read(); + + const Triangle *triangleptr=trianglesr.ptr(); + const Vector3 *vertexptr=verticesr.ptr(); + int pos=bvh.size()-1; + const BVH *bvhptr = bvhr.ptr(); + + stack[0]=pos; + while(true) { + + uint32_t node = stack[level]&NODE_IDX_MASK; + const BVH &b = bvhptr[ node ]; + bool done=false; + + switch(stack[level]>>VISITED_BIT_SHIFT) { + case TEST_AABB_BIT: { + + + bool valid = b.aabb.intersects_segment(p_begin,p_end); +// bool valid = b.aabb.intersects(ray_aabb); + + if (!valid) { + + stack[level]=(VISIT_DONE_BIT<=0) { + + const Triangle &s=triangleptr[ b.face_index ]; + Face3 f3(vertexptr[ s.indices[0] ],vertexptr[ s.indices[1] ],vertexptr[ s.indices[2] ]); + + + Vector3 res; + + if (f3.intersects_segment(p_begin,p_end,&res)) { + + + float nd = n.dot(res); + if (nd0) + r_normal=-r_normal; + } + + return inters; +} + + +bool TriangleMesh::intersect_ray(const Vector3& p_begin,const Vector3& p_dir,Vector3 &r_point, Vector3 &r_normal) const { + + + uint32_t* stack = (uint32_t*)alloca(sizeof(int)*max_depth); + + enum { + TEST_AABB_BIT=0, + VISIT_LEFT_BIT=1, + VISIT_RIGHT_BIT=2, + VISIT_DONE_BIT=3, + VISITED_BIT_SHIFT=29, + NODE_IDX_MASK=(1<::Read trianglesr = triangles.read(); + DVector::Read verticesr=vertices.read(); + DVector::Read bvhr=bvh.read(); + + const Triangle *triangleptr=trianglesr.ptr(); + const Vector3 *vertexptr=verticesr.ptr(); + int pos=bvh.size()-1; + const BVH *bvhptr = bvhr.ptr(); + + stack[0]=pos; + while(true) { + + uint32_t node = stack[level]&NODE_IDX_MASK; + const BVH &b = bvhptr[ node ]; + bool done=false; + + switch(stack[level]>>VISITED_BIT_SHIFT) { + case TEST_AABB_BIT: { + + + bool valid = b.aabb.intersects_ray(p_begin,p_dir); + if (!valid) { + + stack[level]=(VISIT_DONE_BIT<=0) { + + const Triangle &s=triangleptr[ b.face_index ]; + Face3 f3(vertexptr[ s.indices[0] ],vertexptr[ s.indices[1] ],vertexptr[ s.indices[2] ]); + + + Vector3 res; + + if (f3.intersects_ray(p_begin,p_dir,&res)) { + + + float nd = n.dot(res); + if (nd0) + r_normal=-r_normal; + } + + return inters; +} + +bool TriangleMesh::is_valid() const { + + return valid; +} + +DVector TriangleMesh::get_faces() const { + + if (!valid) + return DVector(); + + DVector faces; + int ts = triangles.size(); + faces.resize(triangles.size()); + + DVector::Write w=faces.write(); + DVector::Read r = triangles.read(); + DVector::Read rv = vertices.read(); + + for(int i=0;i::Write(); + return faces; +} + +TriangleMesh::TriangleMesh() { + + valid=false; + max_depth=0; +} -- cgit v1.2.3-70-g09d2