Author: eudoxos
Date: 2009-05-23 09:23:56 +0200 (Sat, 23 May 2009)
New Revision: 1772
Modified:
trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.cpp
trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.hpp
Log:
Handle boundingVolume-less bodies gracefully in InsertionSortCollider
Modified: trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.cpp
===================================================================
--- trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.cpp
2009-05-22 22:06:02 UTC (rev 1771)
+++ trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.cpp
2009-05-23 07:23:56 UTC (rev 1772)
@@ -34,7 +34,6 @@
if((!overlap && !hasInter) || (overlap && hasInter)) return;
// create interaction if not yet existing
if(overlap && !hasInter){ // second condition only for readability
- // FIXME: if(!Collider::mayCollide(bi.get(),bj.get())) return;
if(!Collider::mayCollide(Body::byId(id1,rb).get(),Body::byId(id2,rb).get()))
return;
LOG_TRACE("Creating new interaction #"<<id1<<"+#"<<id2);
shared_ptr<Interaction> newI=shared_ptr<Interaction>(new
Interaction(id1,id2));
@@ -51,10 +50,11 @@
void InsertionSortCollider::insertionSort(vector<Bound>& v,
InteractionContainer* interactions, MetaBody* rb){
long size=v.size();
for(long i=0; i<size; i++){
- Bound viInit=v[i]; long j=i-1;
+ Bound viInit=v[i]; long j=i-1; /* cache hasBB(); otherwise 1%
overall performance hit */ bool viInitBB=viInit.hasBB();
while(j>=0 && v[j]>viInit){
v[j+1]=v[j];
- handleBoundInversion(viInit.id,v[j].id,interactions,rb);
+ // no collisions without bounding boxes
+ if(viInitBB && v[j].hasBB())
handleBoundInversion(viInit.id,v[j].id,interactions,rb);
j--;
}
v[j+1]=viInit;
@@ -76,6 +76,7 @@
if(XX.size()!=2*nBodies){
LOG_DEBUG("Resize bounds containers from
"<<XX.size()<<" to "<<nBodies*2<<", will std::sort.");
// bodies deleted; clear the container completely, and
do as if all bodies were added (rather slow…)
+ // future possibility: insertion sort with such
operator that deleted bodies would all go to the end, then just trim bounds
if(2*nBodies<XX.size()){ XX.clear(); YY.clear();
ZZ.clear(); }
// more than 100 bodies was added, do initial sort again
// maybe: should rather depend on ratio of added bodies
to those already present...?
@@ -84,9 +85,9 @@
assert((XX.size()%2)==0);
for(size_t id=XX.size()/2; id<nBodies; id++){
// add lower and upper bounds; coord is not
important, will be updated from bb shortly
- XX.push_back(Bound(0,id,true));
XX.push_back(Bound(0,id,false));
- YY.push_back(Bound(0,id,true));
YY.push_back(Bound(0,id,false));
- ZZ.push_back(Bound(0,id,true));
ZZ.push_back(Bound(0,id,false));
+ XX.push_back(Bound(0,id,0|Bound::FLAG_MIN));
XX.push_back(Bound(0,id,0|0 /* no Bound::FLAG_MIN */));
+ YY.push_back(Bound(0,id,0|Bound::FLAG_MIN));
YY.push_back(Bound(0,id,0|0 /* no Bound::FLAG_MIN */));
+ ZZ.push_back(Bound(0,id,0|Bound::FLAG_MIN));
ZZ.push_back(Bound(0,id,0|0 /* no Bound::FLAG_MIN */));
}
}
if(minima.size()!=3*nBodies){ minima.resize(3*nBodies);
maxima.resize(3*nBodies); }
@@ -98,16 +99,13 @@
for(size_t i=0; i<2*nBodies; i++){
const body_id_t& idXX=XX[i].id; const body_id_t&
idYY=YY[i].id; const body_id_t& idZZ=ZZ[i].id;
const shared_ptr<BoundingVolume>&
bvXX=Body::byId(idXX,rb)->boundingVolume; const shared_ptr<BoundingVolume>&
bvYY=Body::byId(idYY,rb)->boundingVolume; const shared_ptr<BoundingVolume>&
bvZZ=Body::byId(idZZ,rb)->boundingVolume;
- // if(!bvXX){ LOG_FATAL("InsertionSortCollider doesn't
handle boundingVolume-less bodies."); throw
runtime_error("InsertionSortCollider encountered boundingVolume-less body."); }
- XX[i].coord=bvXX ? (XX[i].isMin ? bvXX->min[0] :
bvXX->max[0]) : Body::byId(idXX,rb)->physicalParameters->se3.position[0];
- YY[i].coord=bvYY ? (YY[i].isMin ? bvYY->min[1] :
bvYY->max[1]) : Body::byId(idYY,rb)->physicalParameters->se3.position[1];
- ZZ[i].coord=bvZZ ? (ZZ[i].isMin ? bvZZ->min[2] :
bvZZ->max[2]) : Body::byId(idZZ,rb)->physicalParameters->se3.position[2];
- //YY[i].coord=(YY[i].isMin ?
Body::byId(YY[i].id,rb)->boundingVolume->min[1] :
Body::byId(YY[i].id,rb)->boundingVolume->max[1]);
- //ZZ[i].coord=(ZZ[i].isMin ?
Body::byId(ZZ[i].id,rb)->boundingVolume->min[2] :
Body::byId(ZZ[i].id,rb)->boundingVolume->max[2]);
+ // copy bounds from boundingVolume if there is one (and
call setBB() to mark that), otherwise use position (setNoBB() marks absence of
bb)
+ XX[i].coord=bvXX ? (XX[i].setBB(), XX[i].isMin() ?
bvXX->min[0] : bvXX->max[0]) : (XX[i].setNoBB(),
Body::byId(idXX,rb)->physicalParameters->se3.position[0]);
+ YY[i].coord=bvYY ? (YY[i].setBB(), YY[i].isMin() ?
bvYY->min[1] : bvYY->max[1]) : (YY[i].setNoBB(),
Body::byId(idYY,rb)->physicalParameters->se3.position[1]);
+ ZZ[i].coord=bvZZ ? (ZZ[i].setBB(), ZZ[i].isMin() ?
bvZZ->min[2] : bvZZ->max[2]) : (ZZ[i].setNoBB(),
Body::byId(idZZ,rb)->physicalParameters->se3.position[2]);
// and for each body, copy its minima and maxima arrays
as well
- if(XX[i].isMin){
+ if(XX[i].isMin()){
BOOST_STATIC_ASSERT(sizeof(Vector3r)==3*sizeof(Real));
- //minima[3*id]=bvXX->min[0];
minima[3*id+1]=bvXX->min[1]; minima[3*id+2]=bvXX->min[2];
maxima[3*id]=bvXX->max[0]; maxima[3*id+1]=bvXX->max[1];
maxima[3*id+2]=bvXX->max[2];
if(bvXX) {
memcpy(&minima[3*idXX],&bvXX->min,3*sizeof(Real));
memcpy(&maxima[3*idXX],&bvXX->max,3*sizeof(Real)); } // ⇐ faster than 6
assignments
else{ const Vector3r&
pos=Body::byId(idXX,rb)->physicalParameters->se3.position;
memcpy(&minima[3*idXX],pos,3*sizeof(Real));
memcpy(&maxima[3*idXX],pos,3*sizeof(Real)); }
}
@@ -118,6 +116,7 @@
// sort
if(!doInitSort){
+ /* each inversion in insertionSort calls
handleBoundInversion, which in turns may add/remove interaction */
insertionSort(XX,interactions,rb);
insertionSort(YY,interactions,rb);
insertionSort(ZZ,interactions,rb);
@@ -132,7 +131,8 @@
// go through potential aabb collisions, create
interactions as necessary
for(size_t i=0; i<2*nBodies; i++){
// start from the lower bound
- if(!V[i].isMin) continue;
+ // skip bodies without bbox since we would
possibly never meet the upper bound again (std::sort may not be stable) and we
don't want to collide those anyway
+ if(!(V[i].isMin() && V[i].hasBB())) continue;
const body_id_t& iid=V[i].id;
// TRVAR3(i,iid,V[i].coord);
// go up until we meet the upper bound
@@ -140,7 +140,8 @@
// skip bodies with smaller (arbitrary,
could be greater as well) id,
// since they will detect us when their
turn comes
const body_id_t& jid=V[j].id;
- if(jid<iid) { /* LOG_TRACE("Skip
#"<<V[j].id<<(V[j].isMin?"(min)":"(max)")<<" with "<<iid<<" (smaller id)"); */
continue; }
+ if(jid<iid) { /* LOG_TRACE("Skip
#"<<V[j].id<<(V[j].isMin()?"(min)":"(max)")<<" with "<<iid<<" (smaller id)");
*/ continue; }
+ /* abuse the same function here; since
it does spatial overlap check first, it is OK to use it */
handleBoundInversion(iid,jid,interactions,rb);
}
}
Modified: trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.hpp
===================================================================
--- trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.hpp
2009-05-22 22:06:02 UTC (rev 1771)
+++ trunk/pkg/common/Engine/StandAloneEngine/InsertionSortCollider.hpp
2009-05-23 07:23:56 UTC (rev 1772)
@@ -11,9 +11,8 @@
calls checkOverlap which then handles either overlap (by creating
interaction if necessary) or its absence (by deleting
interaction if it exists and is only potential (!isReal && isNew).
- Note that not all interactions are traversed at one run, therefore an
overlap miss also has to check the interaction container.
+ Bodies without bounding volume are ahndle gracefully and never collide.
- For performance reasons, we require all bodies to have boundingVolume.
*/
@@ -25,12 +24,15 @@
//! id of the body this bound belongs to
body_id_t id;
//! is it the minimum (true) or maximum (false) bound?
- bool isMin;
- Bound(Real coord_, body_id_t id_, bool isMin_): coord(coord_),
id(id_), isMin(isMin_){}
- //Bound(const Bound& b): coord(b.coord), id(b.id),
isMin(b.isMin){}
- //Bound& operator=(const Bound& b){ coord=b.coord; id=b.id;
isMin=b.isMin; cerr<<"!=!"<<endl; return *this;}
+ char type;
+ Bound(Real coord_, body_id_t id_, char type_): coord(coord_),
id(id_), type(type_){}
bool operator<(const Bound& b) const {return coord<b.coord;}
bool operator>(const Bound& b) const {return coord>b.coord;}
+ enum { FLAG_MIN=1, FLAG_BB=2 };
+ inline bool hasBB() const {return type&FLAG_BB;}
+ inline bool isMin() const {return type&FLAG_MIN;}
+ inline void setBB(){type|=FLAG_BB;}
+ inline void setNoBB(){type&=type^FLAG_BB;}
};
//! storage for bounds
std::vector<Bound> XX,YY,ZZ;
_______________________________________________
Mailing list: https://launchpad.net/~yade-dev
Post to : [email protected]
Unsubscribe : https://launchpad.net/~yade-dev
More help : https://help.launchpad.net/ListHelp
_______________________________________________
yade-dev mailing list
[email protected]
https://lists.berlios.de/mailman/listinfo/yade-dev
