[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16580] trunk/blender/extern/bullet2/src/ LinearMath/btConvexHull.cpp: added src/LinearMath/btConvexHull.cpp
Erwin Coumans
blender at erwincoumans.com
Wed Sep 17 21:58:16 CEST 2008
Revision: 16580
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16580
Author: erwin
Date: 2008-09-17 21:58:16 +0200 (Wed, 17 Sep 2008)
Log Message:
-----------
added src/LinearMath/btConvexHull.cpp
Added Paths:
-----------
trunk/blender/extern/bullet2/src/LinearMath/btConvexHull.cpp
Added: trunk/blender/extern/bullet2/src/LinearMath/btConvexHull.cpp
===================================================================
--- trunk/blender/extern/bullet2/src/LinearMath/btConvexHull.cpp (rev 0)
+++ trunk/blender/extern/bullet2/src/LinearMath/btConvexHull.cpp 2008-09-17 19:58:16 UTC (rev 16580)
@@ -0,0 +1,1153 @@
+/*
+Stan Melax Convex Hull Computation
+Copyright (c) 2003-2006 Stan Melax http://www.melax.com/
+
+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.
+*/
+
+#include <string.h>
+
+#include "btConvexHull.h"
+#include "LinearMath/btAlignedObjectArray.h"
+#include "LinearMath/btMinMax.h"
+#include "LinearMath/btVector3.h"
+
+
+
+template <class T>
+void Swap(T &a,T &b)
+{
+ T tmp = a;
+ a=b;
+ b=tmp;
+}
+
+
+//----------------------------------
+
+class int3
+{
+public:
+ int x,y,z;
+ int3(){};
+ int3(int _x,int _y, int _z){x=_x;y=_y;z=_z;}
+ const int& operator[](int i) const {return (&x)[i];}
+ int& operator[](int i) {return (&x)[i];}
+};
+
+
+//------- btPlane ----------
+
+
+inline btPlane PlaneFlip(const btPlane &plane){return btPlane(-plane.normal,-plane.dist);}
+inline int operator==( const btPlane &a, const btPlane &b ) { return (a.normal==b.normal && a.dist==b.dist); }
+inline int coplanar( const btPlane &a, const btPlane &b ) { return (a==b || a==PlaneFlip(b)); }
+
+
+//--------- Utility Functions ------
+
+btVector3 PlaneLineIntersection(const btPlane &plane, const btVector3 &p0, const btVector3 &p1);
+btVector3 PlaneProject(const btPlane &plane, const btVector3 &point);
+
+btVector3 ThreePlaneIntersection(const btPlane &p0,const btPlane &p1, const btPlane &p2);
+btVector3 ThreePlaneIntersection(const btPlane &p0,const btPlane &p1, const btPlane &p2)
+{
+ btVector3 N1 = p0.normal;
+ btVector3 N2 = p1.normal;
+ btVector3 N3 = p2.normal;
+
+ btVector3 n2n3; n2n3 = N2.cross(N3);
+ btVector3 n3n1; n3n1 = N3.cross(N1);
+ btVector3 n1n2; n1n2 = N1.cross(N2);
+
+ btScalar quotient = (N1.dot(n2n3));
+
+ btAssert(btFabs(quotient) > btScalar(0.000001));
+
+ quotient = btScalar(-1.) / quotient;
+ n2n3 *= p0.dist;
+ n3n1 *= p1.dist;
+ n1n2 *= p2.dist;
+ btVector3 potentialVertex = n2n3;
+ potentialVertex += n3n1;
+ potentialVertex += n1n2;
+ potentialVertex *= quotient;
+
+ btVector3 result(potentialVertex.getX(),potentialVertex.getY(),potentialVertex.getZ());
+ return result;
+
+}
+
+btScalar DistanceBetweenLines(const btVector3 &ustart, const btVector3 &udir, const btVector3 &vstart, const btVector3 &vdir, btVector3 *upoint=NULL, btVector3 *vpoint=NULL);
+btVector3 TriNormal(const btVector3 &v0, const btVector3 &v1, const btVector3 &v2);
+btVector3 NormalOf(const btVector3 *vert, const int n);
+
+
+btVector3 PlaneLineIntersection(const btPlane &plane, const btVector3 &p0, const btVector3 &p1)
+{
+ // returns the point where the line p0-p1 intersects the plane n&d
+ static btVector3 dif;
+ dif = p1-p0;
+ btScalar dn= dot(plane.normal,dif);
+ btScalar t = -(plane.dist+dot(plane.normal,p0) )/dn;
+ return p0 + (dif*t);
+}
+
+btVector3 PlaneProject(const btPlane &plane, const btVector3 &point)
+{
+ return point - plane.normal * (dot(point,plane.normal)+plane.dist);
+}
+
+btVector3 TriNormal(const btVector3 &v0, const btVector3 &v1, const btVector3 &v2)
+{
+ // return the normal of the triangle
+ // inscribed by v0, v1, and v2
+ btVector3 cp=cross(v1-v0,v2-v1);
+ btScalar m=cp.length();
+ if(m==0) return btVector3(1,0,0);
+ return cp*(btScalar(1.0)/m);
+}
+
+
+btScalar DistanceBetweenLines(const btVector3 &ustart, const btVector3 &udir, const btVector3 &vstart, const btVector3 &vdir, btVector3 *upoint, btVector3 *vpoint)
+{
+ static btVector3 cp;
+ cp = cross(udir,vdir).normalized();
+
+ btScalar distu = -dot(cp,ustart);
+ btScalar distv = -dot(cp,vstart);
+ btScalar dist = (btScalar)fabs(distu-distv);
+ if(upoint)
+ {
+ btPlane plane;
+ plane.normal = cross(vdir,cp).normalized();
+ plane.dist = -dot(plane.normal,vstart);
+ *upoint = PlaneLineIntersection(plane,ustart,ustart+udir);
+ }
+ if(vpoint)
+ {
+ btPlane plane;
+ plane.normal = cross(udir,cp).normalized();
+ plane.dist = -dot(plane.normal,ustart);
+ *vpoint = PlaneLineIntersection(plane,vstart,vstart+vdir);
+ }
+ return dist;
+}
+
+
+
+
+
+
+
+#define COPLANAR (0)
+#define UNDER (1)
+#define OVER (2)
+#define SPLIT (OVER|UNDER)
+#define PAPERWIDTH (btScalar(0.001))
+
+btScalar planetestepsilon = PAPERWIDTH;
+
+
+
+typedef ConvexH::HalfEdge HalfEdge;
+
+ConvexH::ConvexH(int vertices_size,int edges_size,int facets_size)
+{
+ vertices.resize(vertices_size);
+ edges.resize(edges_size);
+ facets.resize(facets_size);
+}
+
+
+int PlaneTest(const btPlane &p, const btVector3 &v);
+int PlaneTest(const btPlane &p, const btVector3 &v) {
+ btScalar a = dot(v,p.normal)+p.dist;
+ int flag = (a>planetestepsilon)?OVER:((a<-planetestepsilon)?UNDER:COPLANAR);
+ return flag;
+}
+
+int SplitTest(ConvexH &convex,const btPlane &plane);
+int SplitTest(ConvexH &convex,const btPlane &plane) {
+ int flag=0;
+ for(int i=0;i<convex.vertices.size();i++) {
+ flag |= PlaneTest(plane,convex.vertices[i]);
+ }
+ return flag;
+}
+
+class VertFlag
+{
+public:
+ unsigned char planetest;
+ unsigned char junk;
+ unsigned char undermap;
+ unsigned char overmap;
+};
+class EdgeFlag
+{
+public:
+ unsigned char planetest;
+ unsigned char fixes;
+ short undermap;
+ short overmap;
+};
+class PlaneFlag
+{
+public:
+ unsigned char undermap;
+ unsigned char overmap;
+};
+class Coplanar{
+public:
+ unsigned short ea;
+ unsigned char v0;
+ unsigned char v1;
+};
+
+
+
+
+
+
+
+
+template<class T>
+int maxdirfiltered(const T *p,int count,const T &dir,btAlignedObjectArray<int> &allow)
+{
+ btAssert(count);
+ int m=-1;
+ for(int i=0;i<count;i++)
+ if(allow[i])
+ {
+ if(m==-1 || dot(p[i],dir)>dot(p[m],dir))
+ m=i;
+ }
+ btAssert(m!=-1);
+ return m;
+}
+
+btVector3 orth(const btVector3 &v);
+btVector3 orth(const btVector3 &v)
+{
+ btVector3 a=cross(v,btVector3(0,0,1));
+ btVector3 b=cross(v,btVector3(0,1,0));
+ if (a.length() > b.length())
+ {
+ return a.normalized();
+ } else {
+ return b.normalized();
+ }
+}
+
+
+template<class T>
+int maxdirsterid(const T *p,int count,const T &dir,btAlignedObjectArray<int> &allow)
+{
+ int m=-1;
+ while(m==-1)
+ {
+ m = maxdirfiltered(p,count,dir,allow);
+ if(allow[m]==3) return m;
+ T u = orth(dir);
+ T v = cross(u,dir);
+ int ma=-1;
+ for(btScalar x = btScalar(0.0) ; x<= btScalar(360.0) ; x+= btScalar(45.0))
+ {
+ btScalar s = sinf(SIMD_RADS_PER_DEG*(x));
+ btScalar c = cosf(SIMD_RADS_PER_DEG*(x));
+ int mb = maxdirfiltered(p,count,dir+(u*s+v*c)*btScalar(0.025),allow);
+ if(ma==m && mb==m)
+ {
+ allow[m]=3;
+ return m;
+ }
+ if(ma!=-1 && ma!=mb) // Yuck - this is really ugly
+ {
+ int mc = ma;
+ for(btScalar xx = x-btScalar(40.0) ; xx <= x ; xx+= btScalar(5.0))
+ {
+ btScalar s = sinf(SIMD_RADS_PER_DEG*(xx));
+ btScalar c = cosf(SIMD_RADS_PER_DEG*(xx));
+ int md = maxdirfiltered(p,count,dir+(u*s+v*c)*btScalar(0.025),allow);
+ if(mc==m && md==m)
+ {
+ allow[m]=3;
+ return m;
+ }
+ mc=md;
+ }
+ }
+ ma=mb;
+ }
+ allow[m]=0;
+ m=-1;
+ }
+ btAssert(0);
+ return m;
+}
+
+
+
+
+int operator ==(const int3 &a,const int3 &b);
+int operator ==(const int3 &a,const int3 &b)
+{
+ for(int i=0;i<3;i++)
+ {
+ if(a[i]!=b[i]) return 0;
+ }
+ return 1;
+}
+
+
+int above(btVector3* vertices,const int3& t, const btVector3 &p, btScalar epsilon);
+int above(btVector3* vertices,const int3& t, const btVector3 &p, btScalar epsilon)
+{
+ btVector3 n=TriNormal(vertices[t[0]],vertices[t[1]],vertices[t[2]]);
+ return (dot(n,p-vertices[t[0]]) > epsilon); // EPSILON???
+}
+int hasedge(const int3 &t, int a,int b);
+int hasedge(const int3 &t, int a,int b)
+{
+ for(int i=0;i<3;i++)
+ {
+ int i1= (i+1)%3;
+ if(t[i]==a && t[i1]==b) return 1;
+ }
+ return 0;
+}
+int hasvert(const int3 &t, int v);
+int hasvert(const int3 &t, int v)
+{
+ return (t[0]==v || t[1]==v || t[2]==v) ;
+}
+int shareedge(const int3 &a,const int3 &b);
+int shareedge(const int3 &a,const int3 &b)
+{
+ int i;
+ for(i=0;i<3;i++)
+ {
+ int i1= (i+1)%3;
+ if(hasedge(a,b[i1],b[i])) return 1;
+ }
+ return 0;
+}
+
+class Tri;
+
+
+
+class Tri : public int3
+{
+public:
+ int3 n;
+ int id;
+ int vmax;
+ btScalar rise;
+ Tri(int a,int b,int c):int3(a,b,c),n(-1,-1,-1)
+ {
+ vmax=-1;
+ rise = btScalar(0.0);
+ }
+ ~Tri()
+ {
+ }
+ int &neib(int a,int b);
+};
+
+
+int &Tri::neib(int a,int b)
+{
+ static int er=-1;
+ int i;
+ for(i=0;i<3;i++)
+ {
+ int i1=(i+1)%3;
+ int i2=(i+2)%3;
+ if((*this)[i]==a && (*this)[i1]==b) return n[i2];
+ if((*this)[i]==b && (*this)[i1]==a) return n[i2];
+ }
+ btAssert(0);
+ return er;
+}
+void HullLibrary::b2bfix(Tri* s,Tri*t)
+{
+ int i;
+ for(i=0;i<3;i++)
+ {
+ int i1=(i+1)%3;
+ int i2=(i+2)%3;
+ int a = (*s)[i1];
+ int b = (*s)[i2];
+ btAssert(m_tris[s->neib(a,b)]->neib(b,a) == s->id);
+ btAssert(m_tris[t->neib(a,b)]->neib(b,a) == t->id);
+ m_tris[s->neib(a,b)]->neib(b,a) = t->neib(b,a);
+ m_tris[t->neib(b,a)]->neib(a,b) = s->neib(a,b);
+ }
+}
+
+void HullLibrary::removeb2b(Tri* s,Tri*t)
+{
+ b2bfix(s,t);
+ deAllocateTriangle(s);
+
+ deAllocateTriangle(t);
+}
+
+void HullLibrary::checkit(Tri *t)
+{
+ (void)t;
+
+ int i;
+ btAssert(m_tris[t->id]==t);
+ for(i=0;i<3;i++)
+ {
+ int i1=(i+1)%3;
+ int i2=(i+2)%3;
+ int a = (*t)[i1];
+ int b = (*t)[i2];
+
+ // release compile fix
+ (void)i1;
+ (void)i2;
+ (void)a;
+ (void)b;
+
+ btAssert(a!=b);
+ btAssert( m_tris[t->n[i]]->neib(b,a) == t->id);
+ }
+}
+
+Tri* HullLibrary::allocateTriangle(int a,int b,int c)
+{
+ void* mem = btAlignedAlloc(sizeof(Tri),16);
+ Tri* tr = new (mem)Tri(a,b,c);
+ tr->id = m_tris.size();
+ m_tris.push_back(tr);
+
+ return tr;
+}
+
+void HullLibrary::deAllocateTriangle(Tri* tri)
+{
+ btAssert(m_tris[tri->id]==tri);
+ m_tris[tri->id]=NULL;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list