/* 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 #include "btConvexHull.h" #include "LinearMath/btAlignedObjectArray.h" #include "LinearMath/btMinMax.h" #include "LinearMath/btVector3.h" template 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 int maxdirfiltered(const T *p,int count,const T &dir,btAlignedObjectArray &allow) { btAssert(count); int m=-1; for(int i=0;idot(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 int maxdirsterid(const T *p,int count,const T &dir,btAlignedObjectArray &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; tri->~Tri(); btAlignedFree(tri); } void HullLibrary::extrude(Tri *t0,int v) { int3 t= *t0; int n = m_tris.size(); Tri* ta = allocateTriangle(v,t[1],t[2]); ta->n = int3(t0->n[0],n+1,n+2); m_tris[t0->n[0]]->neib(t[1],t[2]) = n+0; Tri* tb = allocateTriangle(v,t[2],t[0]); tb->n = int3(t0->n[1],n+2,n+0); m_tris[t0->n[1]]->neib(t[2],t[0]) = n+1; Tri* tc = allocateTriangle(v,t[0],t[1]); tc->n = int3(t0->n[2],n+0,n+1); m_tris[t0->n[2]]->neib(t[0],t[1]) = n+2; checkit(ta); checkit(tb); checkit(tc); if(hasvert(*m_tris[ta->n[0]],v)) removeb2b(ta,m_tris[ta->n[0]]); if(hasvert(*m_tris[tb->n[0]],v)) removeb2b(tb,m_tris[tb->n[0]]); if(hasvert(*m_tris[tc->n[0]],v)) removeb2b(tc,m_tris[tc->n[0]]); deAllocateTriangle(t0); } Tri* HullLibrary::extrudable(btScalar epsilon) { int i; Tri *t=NULL; for(i=0;iriserise)) { t = m_tris[i]; } } return (t->rise >epsilon)?t:NULL ; } int4 HullLibrary::FindSimplex(btVector3 *verts,int verts_count,btAlignedObjectArray &allow) { btVector3 basis[3]; basis[0] = btVector3( btScalar(0.01), btScalar(0.02), btScalar(1.0) ); int p0 = maxdirsterid(verts,verts_count, basis[0],allow); int p1 = maxdirsterid(verts,verts_count,-basis[0],allow); basis[0] = verts[p0]-verts[p1]; if(p0==p1 || basis[0]==btVector3(0,0,0)) return int4(-1,-1,-1,-1); basis[1] = cross(btVector3( btScalar(1),btScalar(0.02), btScalar(0)),basis[0]); basis[2] = cross(btVector3(btScalar(-0.02), btScalar(1), btScalar(0)),basis[0]); if (basis[1].length() > basis[2].length()) { basis[1].normalize(); } else { basis[1] = basis[2]; basis[1].normalize (); } int p2 = maxdirsterid(verts,verts_count,basis[1],allow); if(p2 == p0 || p2 == p1) { p2 = maxdirsterid(verts,verts_count,-basis[1],allow); } if(p2 == p0 || p2 == p1) return int4(-1,-1,-1,-1); basis[1] = verts[p2] - verts[p0]; basis[2] = cross(basis[1],basis[0]).normalized(); int p3 = maxdirsterid(verts,verts_count,basis[2],allow); if(p3==p0||p3==p1||p3==p2) p3 = maxdirsterid(verts,verts_count,-basis[2],allow); if(p3==p0||p3==p1||p3==p2) return int4(-1,-1,-1,-1); btAssert(!(p0==p1||p0==p2||p0==p3||p1==p2||p1==p3||p2==p3)); if(dot(verts[p3]-verts[p0],cross(verts[p1]-verts[p0],verts[p2]-verts[p0])) <0) {Swap(p2,p3);} return int4(p0,p1,p2,p3); } int HullLibrary::calchullgen(btVector3 *verts,int verts_count, int vlimit) { if(verts_count <4) return 0; if(vlimit==0) vlimit=1000000000; int j; btVector3 bmin(*verts),bmax(*verts); btAlignedObjectArray isextreme; isextreme.reserve(verts_count); btAlignedObjectArray allow; allow.reserve(verts_count); for(j=0;jn=int3(2,3,1); Tri *t1 = allocateTriangle(p[3],p[2],p[0]); t1->n=int3(3,2,0); Tri *t2 = allocateTriangle(p[0],p[1],p[3]); t2->n=int3(0,1,3); Tri *t3 = allocateTriangle(p[1],p[0],p[2]); t3->n=int3(1,0,2); isextreme[p[0]]=isextreme[p[1]]=isextreme[p[2]]=isextreme[p[3]]=1; checkit(t0);checkit(t1);checkit(t2);checkit(t3); for(j=0;jvmax<0); btVector3 n=TriNormal(verts[(*t)[0]],verts[(*t)[1]],verts[(*t)[2]]); t->vmax = maxdirsterid(verts,verts_count,n,allow); t->rise = dot(n,verts[t->vmax]-verts[(*t)[0]]); } Tri *te; vlimit-=4; while(vlimit >0 && ((te=extrudable(epsilon)) != 0)) { int3 ti=*te; int v=te->vmax; btAssert(v != -1); btAssert(!isextreme[v]); // wtf we've already done this vertex isextreme[v]=1; //if(v==p0 || v==p1 || v==p2 || v==p3) continue; // done these already j=m_tris.size(); while(j--) { if(!m_tris[j]) continue; int3 t=*m_tris[j]; if(above(verts,t,verts[v],btScalar(0.01)*epsilon)) { extrude(m_tris[j],v); } } // now check for those degenerate cases where we have a flipped triangle or a really skinny triangle j=m_tris.size(); while(j--) { if(!m_tris[j]) continue; if(!hasvert(*m_tris[j],v)) break; int3 nt=*m_tris[j]; if(above(verts,nt,center,btScalar(0.01)*epsilon) || cross(verts[nt[1]]-verts[nt[0]],verts[nt[2]]-verts[nt[1]]).length()< epsilon*epsilon*btScalar(0.1) ) { Tri *nb = m_tris[m_tris[j]->n[0]]; btAssert(nb);btAssert(!hasvert(*nb,v));btAssert(nb->idvmax>=0) break; btVector3 n=TriNormal(verts[(*t)[0]],verts[(*t)[1]],verts[(*t)[2]]); t->vmax = maxdirsterid(verts,verts_count,n,allow); if(isextreme[t->vmax]) { t->vmax=-1; // already done that vertex - algorithm needs to be able to terminate. } else { t->rise = dot(n,verts[t->vmax]-verts[(*t)[0]]); } } vlimit --; } return 1; } int HullLibrary::calchull(btVector3 *verts,int verts_count, TUIntArray& tris_out, int &tris_count,int vlimit) { int rc=calchullgen(verts,verts_count, vlimit) ; if(!rc) return 0; btAlignedObjectArray ts; int i; for(i=0;i(ts[i]); } m_tris.resize(0); return 1; } bool HullLibrary::ComputeHull(unsigned int vcount,const btVector3 *vertices,PHullResult &result,unsigned int vlimit) { int tris_count; int ret = calchull( (btVector3 *) vertices, (int) vcount, result.m_Indices, tris_count, static_cast(vlimit) ); if(!ret) return false; result.mIndexCount = (unsigned int) (tris_count*3); result.mFaceCount = (unsigned int) tris_count; result.mVertices = (btVector3*) vertices; result.mVcount = (unsigned int) vcount; return true; } void ReleaseHull(PHullResult &result); void ReleaseHull(PHullResult &result) { if ( result.m_Indices.size() ) { result.m_Indices.clear(); } result.mVcount = 0; result.mIndexCount = 0; result.mVertices = 0; } //********************************************************************* //********************************************************************* //******** HullLib header //********************************************************************* //********************************************************************* //********************************************************************* //********************************************************************* //******** HullLib implementation //********************************************************************* //********************************************************************* HullError HullLibrary::CreateConvexHull(const HullDesc &desc, // describes the input request HullResult &result) // contains the resulst { HullError ret = QE_FAIL; PHullResult hr; unsigned int vcount = desc.mVcount; if ( vcount < 8 ) vcount = 8; btAlignedObjectArray vertexSource; vertexSource.resize(static_cast(vcount)); btVector3 scale; unsigned int ovcount; bool ok = CleanupVertices(desc.mVcount,desc.mVertices, desc.mVertexStride, ovcount, &vertexSource[0], desc.mNormalEpsilon, scale ); // normalize point cloud, remove duplicates! if ( ok ) { // if ( 1 ) // scale vertices back to their original size. { for (unsigned int i=0; i(i)]; v[0]*=scale[0]; v[1]*=scale[1]; v[2]*=scale[2]; } } ok = ComputeHull(ovcount,&vertexSource[0],hr,desc.mMaxVertices); if ( ok ) { // re-index triangle mesh so it refers to only used vertices, rebuild a new vertex table. btAlignedObjectArray vertexScratch; vertexScratch.resize(static_cast(hr.mVcount)); BringOutYourDead(hr.mVertices,hr.mVcount, &vertexScratch[0], ovcount, &hr.m_Indices[0], hr.mIndexCount ); ret = QE_OK; if ( desc.HasHullFlag(QF_TRIANGLES) ) // if he wants the results as triangle! { result.mPolygons = false; result.mNumOutputVertices = ovcount; result.m_OutputVertices.resize(static_cast(ovcount)); result.mNumFaces = hr.mFaceCount; result.mNumIndices = hr.mIndexCount; result.m_Indices.resize(static_cast(hr.mIndexCount)); memcpy(&result.m_OutputVertices[0], &vertexScratch[0], sizeof(btVector3)*ovcount ); if ( desc.HasHullFlag(QF_REVERSE_ORDER) ) { const unsigned int *source = &hr.m_Indices[0]; unsigned int *dest = &result.m_Indices[0]; for (unsigned int i=0; i(ovcount)); result.mNumFaces = hr.mFaceCount; result.mNumIndices = hr.mIndexCount+hr.mFaceCount; result.m_Indices.resize(static_cast(result.mNumIndices)); memcpy(&result.m_OutputVertices[0], &vertexScratch[0], sizeof(btVector3)*ovcount ); // if ( 1 ) { const unsigned int *source = &hr.m_Indices[0]; unsigned int *dest = &result.m_Indices[0]; for (unsigned int i=0; i bmax[j] ) bmax[j] = p[j]; } } } btScalar dx = bmax[0] - bmin[0]; btScalar dy = bmax[1] - bmin[1]; btScalar dz = bmax[2] - bmin[2]; btVector3 center; center[0] = dx*btScalar(0.5) + bmin[0]; center[1] = dy*btScalar(0.5) + bmin[1]; center[2] = dz*btScalar(0.5) + bmin[2]; if ( dx < EPSILON || dy < EPSILON || dz < EPSILON || svcount < 3 ) { btScalar len = FLT_MAX; if ( dx > EPSILON && dx < len ) len = dx; if ( dy > EPSILON && dy < len ) len = dy; if ( dz > EPSILON && dz < len ) len = dz; if ( len == FLT_MAX ) { dx = dy = dz = btScalar(0.01); // one centimeter } else { if ( dx < EPSILON ) dx = len * btScalar(0.05); // 1/5th the shortest non-zero edge. if ( dy < EPSILON ) dy = len * btScalar(0.05); if ( dz < EPSILON ) dz = len * btScalar(0.05); } btScalar x1 = center[0] - dx; btScalar x2 = center[0] + dx; btScalar y1 = center[1] - dy; btScalar y2 = center[1] + dy; btScalar z1 = center[2] - dz; btScalar z2 = center[2] + dz; addPoint(vcount,vertices,x1,y1,z1); addPoint(vcount,vertices,x2,y1,z1); addPoint(vcount,vertices,x2,y2,z1); addPoint(vcount,vertices,x1,y2,z1); addPoint(vcount,vertices,x1,y1,z2); addPoint(vcount,vertices,x2,y1,z2); addPoint(vcount,vertices,x2,y2,z2); addPoint(vcount,vertices,x1,y2,z2); return true; // return cube } else { if ( scale ) { scale[0] = dx; scale[1] = dy; scale[2] = dz; recip[0] = 1 / dx; recip[1] = 1 / dy; recip[2] = 1 / dz; center[0]*=recip[0]; center[1]*=recip[1]; center[2]*=recip[2]; } } vtx = (const char *) svertices; for (unsigned int i=0; igetX(); btScalar py = p->getY(); btScalar pz = p->getZ(); if ( scale ) { px = px*recip[0]; // normalize py = py*recip[1]; // normalize pz = pz*recip[2]; // normalize } // if ( 1 ) { unsigned int j; for (j=0; j dist2 ) { v[0] = px; v[1] = py; v[2] = pz; } break; } } if ( j == vcount ) { btVector3& dest = vertices[vcount]; dest[0] = px; dest[1] = py; dest[2] = pz; vcount++; } m_vertexIndexMapping.push_back(j); } } // ok..now make sure we didn't prune so many vertices it is now invalid. // if ( 1 ) { btScalar bmin[3] = { FLT_MAX, FLT_MAX, FLT_MAX }; btScalar bmax[3] = { -FLT_MAX, -FLT_MAX, -FLT_MAX }; for (unsigned int i=0; i bmax[j] ) bmax[j] = p[j]; } } btScalar dx = bmax[0] - bmin[0]; btScalar dy = bmax[1] - bmin[1]; btScalar dz = bmax[2] - bmin[2]; if ( dx < EPSILON || dy < EPSILON || dz < EPSILON || vcount < 3) { btScalar cx = dx*btScalar(0.5) + bmin[0]; btScalar cy = dy*btScalar(0.5) + bmin[1]; btScalar cz = dz*btScalar(0.5) + bmin[2]; btScalar len = FLT_MAX; if ( dx >= EPSILON && dx < len ) len = dx; if ( dy >= EPSILON && dy < len ) len = dy; if ( dz >= EPSILON && dz < len ) len = dz; if ( len == FLT_MAX ) { dx = dy = dz = btScalar(0.01); // one centimeter } else { if ( dx < EPSILON ) dx = len * btScalar(0.05); // 1/5th the shortest non-zero edge. if ( dy < EPSILON ) dy = len * btScalar(0.05); if ( dz < EPSILON ) dz = len * btScalar(0.05); } btScalar x1 = cx - dx; btScalar x2 = cx + dx; btScalar y1 = cy - dy; btScalar y2 = cy + dy; btScalar z1 = cz - dz; btScalar z2 = cz + dz; vcount = 0; // add box addPoint(vcount,vertices,x1,y1,z1); addPoint(vcount,vertices,x2,y1,z1); addPoint(vcount,vertices,x2,y2,z1); addPoint(vcount,vertices,x1,y2,z1); addPoint(vcount,vertices,x1,y1,z2); addPoint(vcount,vertices,x2,y1,z2); addPoint(vcount,vertices,x2,y2,z2); addPoint(vcount,vertices,x1,y2,z2); return true; } } return true; } void HullLibrary::BringOutYourDead(const btVector3* verts,unsigned int vcount, btVector3* overts,unsigned int &ocount,unsigned int *indices,unsigned indexcount) { btAlignedObjectArraytmpIndices; tmpIndices.resize(m_vertexIndexMapping.size()); int i; for (i=0;i(vcount)); memset(&usedIndices[0],0,sizeof(unsigned int)*vcount); ocount = 0; for (i=0; i= 0 && v < vcount ); if ( usedIndices[static_cast(v)] ) // if already remapped { indices[i] = usedIndices[static_cast(v)]-1; // index to new array } else { indices[i] = ocount; // new index mapping overts[ocount][0] = verts[v][0]; // copy old vert to new vert array overts[ocount][1] = verts[v][1]; overts[ocount][2] = verts[v][2]; for (int k=0;k=0 && ocount <= vcount ); usedIndices[static_cast(v)] = ocount; // assign new index remapping } } }