Revision: 16797
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16797
Author: mxcurioni
Date: 2008-09-28 22:07:59 +0200 (Sun, 28 Sep 2008)
Log Message:
-----------
soc-2008-mxcurioni: merge files correction
Modified Paths:
--------------
branches/soc-2008-mxcurioni/intern/guardedalloc/intern/mmap_win.c
branches/soc-2008-mxcurioni/intern/guardedalloc/mmap_win.h
branches/soc-2008-mxcurioni/release/Makefile
branches/soc-2008-mxcurioni/release/scripts/bpymodules/BPyAddMesh.py
Added Paths:
-----------
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvtBroadphase.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvtBroadphase.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btMultiSapBroadphase.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btMultiSapBroadphase.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btOverlappingPairCallback.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btQuantizedBvh.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btQuantizedBvh.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btBoxBoxCollisionAlgorithm.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btBoxBoxCollisionAlgorithm.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btCollisionConfiguration.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btConvexPlaneCollisionAlgorithm.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btConvexPlaneCollisionAlgorithm.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btDefaultCollisionConfiguration.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionDispatch/btDefaultCollisionConfiguration.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btConvexInternalShape.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btConvexInternalShape.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btMaterial.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btMultimaterialTriangleMeshShape.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btMultimaterialTriangleMeshShape.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btShapeHull.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btShapeHull.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btTriangleIndexVertexMaterialArray.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btTriangleIndexVertexMaterialArray.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btUniformScalingShape.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/CollisionShapes/btUniformScalingShape.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/NarrowPhaseCollision/btGjkEpa2.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/NarrowPhaseCollision/btGjkEpa2.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletDynamics/ConstraintSolver/btSliderConstraint.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletDynamics/ConstraintSolver/btSliderConstraint.h
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletDynamics/Dynamics/btContinuousDynamicsWorld.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletDynamics/Dynamics/btContinuousDynamicsWorld.h
branches/soc-2008-mxcurioni/extern/bullet2/src/LinearMath/btConvexHull.cpp
branches/soc-2008-mxcurioni/extern/bullet2/src/LinearMath/btConvexHull.h
branches/soc-2008-mxcurioni/extern/bullet2/src/LinearMath/btHashMap.h
branches/soc-2008-mxcurioni/extern/bullet2/src/LinearMath/btPoolAllocator.h
branches/soc-2008-mxcurioni/release/scripts/scripttemplate_ipo_gen.py
Added:
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp
===================================================================
---
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp
(rev 0)
+++
branches/soc-2008-mxcurioni/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp
2008-09-28 20:07:59 UTC (rev 16797)
@@ -0,0 +1,1289 @@
+/*
+Bullet Continuous Collision Detection and Physics Library
+Copyright (c) 2003-2006 Erwin Coumans http://continuousphysics.com/Bullet/
+
+This software is provided 'as-is', without any express or implied warranty.
+In no event will the authors be held liable for any damages arising from the
use of this software.
+Permission is granted to anyone to use this software for any purpose,
+including commercial applications, and to alter it and redistribute it freely,
+subject to the following restrictions:
+
+1. The origin of this software must not be misrepresented; you must not claim
that you wrote the original software. If you use this software in a product, an
acknowledgment in the product documentation would be appreciated but is not
required.
+2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
+3. This notice may not be removed or altered from any source distribution.
+*/
+///btDbvt implementation by Nathanael Presson
+
+#include "btDbvt.h"
+
+//
+typedef btAlignedObjectArray<btDbvtNode*> tNodeArray;
+typedef btAlignedObjectArray<const btDbvtNode*> tConstNodeArray;
+
+//
+struct btDbvtNodeEnumerator : btDbvt::ICollide
+{
+tConstNodeArray nodes;
+void Process(const btDbvtNode* n) { nodes.push_back(n); }
+};
+
+//
+static DBVT_INLINE int indexof(const btDbvtNode* node)
+{
+return(node->parent->childs[1]==node);
+}
+
+//
+static DBVT_INLINE btDbvtVolume merge( const btDbvtVolume& a,
+
const btDbvtVolume& b)
+{
+#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
+DBVT_ALIGN char locals[sizeof(btDbvtAabbMm)];
+btDbvtVolume& res=*(btDbvtVolume*)locals;
+#else
+btDbvtVolume res;
+#endif
+Merge(a,b,res);
+return(res);
+}
+
+// volume+edge lengths
+static DBVT_INLINE btScalar size(const btDbvtVolume& a)
+{
+const btVector3 edges=a.Lengths();
+return( edges.x()*edges.y()*edges.z()+
+ edges.x()+edges.y()+edges.z());
+}
+
+//
+static void getmaxdepth(const
btDbvtNode* node,int depth,int& maxdepth)
+{
+if(node->isinternal())
+ {
+ getmaxdepth(node->childs[0],depth+1,maxdepth);
+ getmaxdepth(node->childs[0],depth+1,maxdepth);
+ } else maxdepth=btMax(maxdepth,depth);
+}
+
+//
+static DBVT_INLINE void deletenode( btDbvt* pdbvt,
+
btDbvtNode* node)
+{
+btAlignedFree(pdbvt->m_free);
+pdbvt->m_free=node;
+}
+
+//
+static void recursedeletenode(
btDbvt* pdbvt,
+
btDbvtNode* node)
+{
+if(!node->isleaf())
+ {
+ recursedeletenode(pdbvt,node->childs[0]);
+ recursedeletenode(pdbvt,node->childs[1]);
+ }
+if(node==pdbvt->m_root) pdbvt->m_root=0;
+deletenode(pdbvt,node);
+}
+
+//
+static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt,
+
btDbvtNode* parent,
+
void* data)
+{
+btDbvtNode* node;
+if(pdbvt->m_free)
+ { node=pdbvt->m_free;pdbvt->m_free=0; }
+ else
+ { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); }
+node->parent = parent;
+node->data = data;
+node->childs[1] = 0;
+return(node);
+}
+
+//
+static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt,
+
btDbvtNode* parent,
+
const btDbvtVolume& volume,
+
void* data)
+{
+btDbvtNode* node=createnode(pdbvt,parent,data);
+node->volume=volume;
+return(node);
+}
+
+//
+static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt,
+
btDbvtNode* parent,
+
const btDbvtVolume& volume0,
+
const btDbvtVolume& volume1,
+
void* data)
+{
+btDbvtNode* node=createnode(pdbvt,parent,data);
+Merge(volume0,volume1,node->volume);
+return(node);
+}
+
+//
+static void insertleaf( btDbvt*
pdbvt,
+
btDbvtNode* root,
+
btDbvtNode* leaf)
+{
+if(!pdbvt->m_root)
+ {
+ pdbvt->m_root = leaf;
+ leaf->parent = 0;
+ }
+ else
+ {
+ if(!root->isleaf())
+ {
+ do {
+ root=root->childs[Select( leaf->volume,
+
root->childs[0]->volume,
+
root->childs[1]->volume)];
+ } while(!root->isleaf());
+ }
+ btDbvtNode* prev=root->parent;
+ btDbvtNode* node=createnode(pdbvt,prev,leaf->volume,root->volume,0);
+ if(prev)
+ {
+ prev->childs[indexof(root)] = node;
+ node->childs[0] =
root;root->parent=node;
+ node->childs[1] =
leaf;leaf->parent=node;
+ do {
+ if(!prev->volume.Contain(node->volume))
+
Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
+ else
+ break;
+ node=prev;
+ } while(0!=(prev=node->parent));
+ }
+ else
+ {
+ node->childs[0] = root;root->parent=node;
+ node->childs[1] = leaf;leaf->parent=node;
+ pdbvt->m_root = node;
+ }
+ }
+}
+
+//
+static btDbvtNode* removeleaf( btDbvt* pdbvt,
+
btDbvtNode* leaf)
+{
+if(leaf==pdbvt->m_root)
+ {
+ pdbvt->m_root=0;
+ return(0);
+ }
+ else
+ {
+ btDbvtNode* parent=leaf->parent;
+ btDbvtNode* prev=parent->parent;
+ btDbvtNode* sibling=parent->childs[1-indexof(leaf)];
+ if(prev)
+ {
+ prev->childs[indexof(parent)]=sibling;
+ sibling->parent=prev;
+ deletenode(pdbvt,parent);
+ while(prev)
+ {
+ const btDbvtVolume pb=prev->volume;
+
Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
+ if(NotEqual(pb,prev->volume))
+ {
+ prev=prev->parent;
+ } else break;
+ }
+ return(prev?prev:pdbvt->m_root);
+ }
+ else
+ {
+ pdbvt->m_root=sibling;
+ sibling->parent=0;
+ deletenode(pdbvt,parent);
+ return(pdbvt->m_root);
+ }
+ }
+}
+
+//
+static void fetchleaves(btDbvt*
pdbvt,
+
btDbvtNode* root,
+
tNodeArray& leaves,
+
int depth=-1)
+{
+if(root->isinternal()&&depth)
+ {
+ fetchleaves(pdbvt,root->childs[0],leaves,depth-1);
+ fetchleaves(pdbvt,root->childs[1],leaves,depth-1);
+ deletenode(pdbvt,root);
+ }
+ else
+ {
+ leaves.push_back(root);
+ }
+}
+
+//
+static void split( const
tNodeArray& leaves,
+
tNodeArray& left,
+
tNodeArray& right,
+
const btVector3& org,
+
const btVector3& axis)
+{
+left.resize(0);
+right.resize(0);
+for(int i=0,ni=leaves.size();i<ni;++i)
+ {
+ if(dot(axis,leaves[i]->volume.Center()-org)<0)
+ left.push_back(leaves[i]);
+ else
+ right.push_back(leaves[i]);
+ }
+}
+
+//
+static btDbvtVolume bounds( const tNodeArray&
leaves)
+{
+#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
+DBVT_ALIGN char locals[sizeof(btDbvtVolume)];
+btDbvtVolume& volume=*(btDbvtVolume*)locals;
+volume=leaves[0]->volume;
+#else
+btDbvtVolume volume=leaves[0]->volume;
+#endif
+for(int i=1,ni=leaves.size();i<ni;++i)
+ {
+ Merge(volume,leaves[i]->volume,volume);
+ }
+return(volume);
+}
+
+//
+static void bottomup( btDbvt*
pdbvt,
+
tNodeArray& leaves)
+{
+while(leaves.size()>1)
+ {
+ btScalar minsize=SIMD_INFINITY;
+ int minidx[2]={-1,-1};
+ for(int i=0;i<leaves.size();++i)
+ {
+ for(int j=i+1;j<leaves.size();++j)
+ {
+ const btScalar
sz=size(merge(leaves[i]->volume,leaves[j]->volume));
+ if(sz<minsize)
+ {
+ minsize = sz;
+ minidx[0] = i;
+ minidx[1] = j;
+ }
+ }
+ }
+ btDbvtNode* n[] = {leaves[minidx[0]],leaves[minidx[1]]};
+ btDbvtNode* p =
createnode(pdbvt,0,n[0]->volume,n[1]->volume,0);
+ p->childs[0] = n[0];
+ p->childs[1] = n[1];
+ n[0]->parent = p;
+ n[1]->parent = p;
+ leaves[minidx[0]] = p;
+ leaves.swap(minidx[1],leaves.size()-1);
+ leaves.pop_back();
+ }
+}
+
+//
+static btDbvtNode* topdown(btDbvt* pdbvt,
+
tNodeArray& leaves,
+ int
bu_treshold)
+{
+static const btVector3 axis[]={btVector3(1,0,0),
+
btVector3(0,1,0),
+
btVector3(0,0,1)};
+if(leaves.size()>1)
+ {
+ if(leaves.size()>bu_treshold)
+ {
+ const btDbvtVolume vol=bounds(leaves);
+ const btVector3 org=vol.Center();
+ tNodeArray sets[2];
+ int bestaxis=-1;
+ int
bestmidp=leaves.size();
+ int
splitcount[3][2]={{0,0},{0,0},{0,0}};
+ int i;
+ for( i=0;i<leaves.size();++i)
+ {
+ const btVector3 x=leaves[i]->volume.Center()-org;
+ for(int j=0;j<3;++j)
+ {
+ ++splitcount[j][dot(x,axis[j])>0?1:0];
+ }
+ }
+ for( i=0;i<3;++i)
+ {
+ if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
+ {
+ const int
midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1]));
+ if(midp<bestmidp)
+ {
+ bestaxis=i;
+ bestmidp=midp;
+ }
+ }
+ }
+ if(bestaxis>=0)
+ {
+ sets[0].reserve(splitcount[bestaxis][0]);
+ sets[1].reserve(splitcount[bestaxis][1]);
+ split(leaves,sets[0],sets[1],org,axis[bestaxis]);
+ }
+ else
+ {
+ sets[0].reserve(leaves.size()/2+1);
+ sets[1].reserve(leaves.size()/2);
+ for(int i=0,ni=leaves.size();i<ni;++i)
+ {
+ sets[i&1].push_back(leaves[i]);
+ }
+ }
+ btDbvtNode* node=createnode(pdbvt,0,vol,0);
+ node->childs[0]=topdown(pdbvt,sets[0],bu_treshold);
+ node->childs[1]=topdown(pdbvt,sets[1],bu_treshold);
+ node->childs[0]->parent=node;
+ node->childs[1]->parent=node;
+ return(node);
+ }
+ else
+ {
+ bottomup(pdbvt,leaves);
+ return(leaves[0]);
+ }
+ }
+return(leaves[0]);
+}
+
+//
+static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n,btDbvtNode*& r)
+{
+btDbvtNode* p=n->parent;
+btAssert(n->isinternal());
+if(p>n)
+ {
+ const int i=indexof(n);
+ const int j=1-i;
+ btDbvtNode* s=p->childs[j];
+ btDbvtNode* q=p->parent;
+ btAssert(n==p->childs[i]);
+ if(q) q->childs[indexof(p)]=n; else r=n;
+ s->parent=n;
+ p->parent=n;
+ n->parent=q;
+ p->childs[0]=n->childs[0];
+ p->childs[1]=n->childs[1];
+ n->childs[0]->parent=p;
+ n->childs[1]->parent=p;
+ n->childs[i]=p;
+ n->childs[j]=s;
+ btSwap(p->volume,n->volume);
+ return(p);
+ }
+return(n);
+}
+
+//
+static DBVT_INLINE btDbvtNode* walkup(btDbvtNode* n,int count)
+{
+while(n&&(count--)) n=n->parent;
+return(n);
+}
+
+//
+// Api
+//
+
+//
+ btDbvt::btDbvt()
+{
+m_root = 0;
+m_free = 0;
+m_lkhd = -1;
+m_leaves = 0;
+m_opath = 0;
+}
+
+//
+ btDbvt::~btDbvt()
+{
+clear();
+}
+
+//
+void btDbvt::clear()
+{
+if(m_root) recursedeletenode(this,m_root);
+btAlignedFree(m_free);
+m_free=0;
+}
+
+//
+void btDbvt::optimizeBottomUp()
+{
+if(m_root)
+ {
+ tNodeArray leaves;
+ leaves.reserve(m_leaves);
+ fetchleaves(this,m_root,leaves);
+ bottomup(this,leaves);
+ m_root=leaves[0];
+ }
+}
+
+//
+void btDbvt::optimizeTopDown(int bu_treshold)
+{
+if(m_root)
+ {
+ tNodeArray leaves;
+ leaves.reserve(m_leaves);
+ fetchleaves(this,m_root,leaves);
+ m_root=topdown(this,leaves,bu_treshold);
+ }
+}
+
+//
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
