Retrieving all objects inside a big sphere

[aymar.fisherman]

I'm implementing an object that pulses away any other object within a radius.

What's the best (high performance) way to do this search?

P.S.: Iterating over all objects and checking if it's distance from my pulsing object is lesser than the radius is obvious...I'm trying not to do this!

P.S. 2: Collisions with a sphere covering this radius are faulty, mainly because this sphere is huge comparing to the other objects.

Thanks in advance guys!

My code looks like this right now:

Code: Select all

Transform from = this->object->getCollisionObject()->getWorldTransform();
Transform to = from;
to.setOrigin(to.getOrigin() + btVector3(0.0f, 0.1f, 0.0f));

AllButMeConvexResultCallback callback(this->object->getCollisionObject().get());
callback.m_collisionFilterGroup = btBroadphaseProxy::DefaultFilter;
callback.m_collisionFilterMask = btBroadphaseProxy::AllFilter;

// this->range = 20.0f;
ConvexShapePtr shape(new SphereShape(this->range));

if (this->collisionTester->convexSweepTest(shape, from, to, callback)) {
	foreach (CollisionObject* collisionObject, callback.hits) {
		if (!collisionObject->isStaticOrKinematicObject()) {
			Vector3dPtr pulseDirection = Vector3dPtr(new BulletVector3Adapter(collisionObject->getWorldTransform().getOrigin())) - this->object->getPosition();
			float distance = pulseDirection->norm();
			btVector3 objectImpulse = toBullet(this->impulse*(1.0f - distance/this->range)*pulseDirection); //linear		
			RigidBody::upcast(collisionObject)->applyCentralImpulse(objectImpulse);
		}
	}
}

[Erwin Coumans]

The best way depends on how your objects are distributed, and if you need to query the sphere multiple times at similar locations.

In general, the best way is to query the broadphase for all objects that overlap with an AABB, and then cull the results further manually.

See Bullet/src/BulletCollision/BroadphaseCollision/btBroadphaseInterface.h

Code: Select all

virtual void	btBroadphaseInterface::aabbTest(const btVector3& aabbMin, const btVector3& aabbMax, btBroadphaseAabbCallback& callback);

[aymar.fisherman]

Thank you Erwin!

Using the broadphase callback solved my problem perfectly (culling out the remaining objects is effortless!).

My code looks like this now:

Code: Select all

struct AllButMeAabbResultCallback : public btBroadphaseAabbCallback {
	AllButMeAabbResultCallback(CollisionObject* me) : me(me) {}

	virtual bool process(const btBroadphaseProxy* proxy) {
		CollisionObject* collisionObject = static_cast<CollisionObject*>(proxy->m_clientObject);
		if (collisionObject == this->me) {
			return true;
		}
		this->hits.push_back(collisionObject);
		return true;
	}

	CollisionObject* me;
	CollisionObjectPtrList hits;
};

...

AllButMeAabbResultCallback callback(this->object->getCollisionObject());

btVector3 center = toBullet(this->object->getPosition());
btVector3 aabbMin = center - this->range*btVector3(1.0f, 1.0f, 1.0f);
btVector3 aabbMax = center + this->range*btVector3(1.0f, 1.0f, 1.0f);

collisionTester->aabbTest(aabbMin, aabbMax, callback); //here my collisionTester sends all the data to the BroadphaseInterface::aabbTest, I won't trouble you with this code, 'cause it's straightforward;

this->cullResults(callback.hits); //Simple sphere culling using the center of each hit (I don't care for errors involving big objects, but if you do, you just need to implement a better culling system);

foreach (CollisionObject* collisionObject, callback.hits) {
	if (!collisionObject->isStaticOrKinematicObject()) {
		Vector3dPtr pulseDirection = Vector3dPtr(new BulletVector3Adapter(collisionObject->getWorldTransform().getOrigin())) - center;
		float distance = pulseDirection->norm();
		btVector3 objectImpulse = toBullet(this->impulse*(1.0f - distance/this->range)*pulseDirection); //linear		
		RigidBody::upcast(collisionObject)->applyCentralImpulse(objectImpulse);
	}
}