Making a faster rayTest?

Chen111
Posts: 3
Joined: Fri Jun 16, 2017 5:36 am

Re: Making a faster rayTest?

Post by Chen111 » Mon Jun 26, 2017 8:05 am

Pintea wrote:
benelot wrote:Maybe somebody could contribute the faster version of ClosestRayResultCallback which does not calculate all other ray results?
Someone should definitely do that :)

For the moment I'm just playing around with it, but when we'll have to be production ready with our game I'll try to do a proper version. Hopefully someone with deeper Bullet understanding will have already done it by then.

My requirements would be:
- parse the bounding volume hierarchy in a front-to-back order, starting from the ray's origin
- do specialized ray-vs-primitive (obb, sphere, cylinder etc.) tests where possible instead of the iterative shape-sweeping algorithm it's now using
- stop at first hit

PS:
Is it called shape-sweeping if it's iterative? Why iterative? There's an actual while (iterations < 30) in the code right now in btSubsimplexConvexCast::btSubsimplexConvexCast
Met the same problem, any progress,thanks

Pintea
Posts: 8
Joined: Tue Feb 14, 2017 2:14 pm

Re: Making a faster rayTest?

Post by Pintea » Mon Oct 02, 2017 9:33 am

Haven't gotten around to implement it the proper way yet (hopefully this year...).
I can send you my current implementation, which I talked about earlier in the thread, which walks the ray front-to-back and stops at the first hit. Much faster than the current implementation but still far away from ideal.

jt0199
Posts: 1
Joined: Mon Mar 05, 2018 8:25 am
Location: Taipei, Taiwan

Re: Making a faster rayTest?

Post by jt0199 » Mon Mar 05, 2018 8:42 am

Pintea wrote:
Mon Oct 02, 2017 9:33 am
Haven't gotten around to implement it the proper way yet (hopefully this year...).
I can send you my current implementation, which I talked about earlier in the thread, which walks the ray front-to-back and stops at the first hit. Much faster than the current implementation but still far away from ideal.
Apologize for my pool english first.

Raytest performance problem is a primary problem in our project too, we tried to improve it, but it only get a little bit improvement.
Could you send us your implementation.

Pintea
Posts: 8
Joined: Tue Feb 14, 2017 2:14 pm

Re: Making a faster rayTest?

Post by Pintea » Mon Mar 05, 2018 11:32 am

Look into the btDbvt.h file, the function is btDbvt::rayTestInternal(...)
I added a few lines of code to make it parse the bounding volume front-to-back. The process() function callbacks the user for each collision (as it already did). If the user returns true, the process should stop (which it never did before).

Anyway, it's still a really bad/unfinished implementation, but should give you a good performance boost.

I never continued with this since we switched to another library. Bullet is simply too bad for performance. Also the 'sweep' implementations that do it by taking discrete moves... Also countless dynamic memory allocations for each cast... not usable if you're doing a lot of ray/geometry casts per frame (like you would in any kind of game actually, I'm not even talking about the actual physics/dynamics part, just bullet/projectile tracing).


Before:

Code: Select all

if(node->isinternal())
{
	if(depth>treshold)
	{
		stack.resize(stack.size()*2);
		treshold=stack.size()-2;
	}
	stack[depth++]=node->childs[0];
	stack[depth++]=node->childs[1];
}
else
{
	policy.Process(node);
}
After:

Code: Select all

if(result1)
{
if(node->isinternal())
{
	if(depth>treshold)
	{
		stack.resize(stack.size()*2);
		treshold=stack.size()-2;
	}

	// sort closest to farthest
	btVector3 center1 = (node->childs[0]->volume.Mins() + node->childs[0]->volume.Maxs()) * 0.5f;
	btVector3 center2 = (node->childs[1]->volume.Mins() + node->childs[1]->volume.Maxs()) * 0.5f;
	float dist1 = (center1-rayFrom).length2();
	float dist2 = (center2-rayFrom).length2();
	if (dist1 < dist2)
	{
		stack[depth++]=node->childs[1];
		stack[depth++]=node->childs[0];
	}
	else
	{
		stack[depth++]=node->childs[0];
		stack[depth++]=node->childs[1];
	}
}
else
{
	// pass to user and let him decide if we should stop or not
	if (!policy.Process(node))
		break;
}

Actual in-game usage:

Code: Select all

struct sMyFilterClosestRayResultCallback : public btCollisionWorld::ClosestRayResultCallback
{
	public:
		sMyFilterClosestRayResultCallback( const btVector3& _rayFromWorld,
										   const btVector3& _rayToWorld,
										   unsigned int		_uiColFlags )
			: ClosestRayResultCallback( _rayFromWorld, _rayToWorld )
			, uiColFlags( _uiColFlags ) {
		}

	public:
		unsigned int uiColFlags;

	public:
		virtual bool needsCollision( btBroadphaseProxy* proxy0 ) const
		{
			bool bBaseResult = ClosestRayResultCallback::needsCollision( proxy0 );
			if( bBaseResult ) // if collision test passed, further test with our own criteria
			{
				btCollisionObject* pColObj = (btCollisionObject*)proxy0->m_clientObject;
				sCollisionObject* pMyColObj = (sCollisionObject*)pColObj->getUserPointer();

				// game collision info ref; related to visibility / movement / bullet hits etc
				if( pMyColObj->GetFlags() & uiColFlags )
				{
					//btVector3 from = this->m_rayFromWorld;
					//btVector3 to = this->m_rayToWorld;
					//btScalar closestHit = this->m_closestHitFraction;
					//to = from + (to - from) * closestHit;

					//bool bCollided = Math::SegmentVsAABB(BV3ToVector3(from), BV3ToVector3(to), BV3ToVector3(proxy0->m_aabbMin), BV3ToVector3(proxy0->m_aabbMax));
					//if (bCollided)
					//	return true;
					return true;
				}
				return false;
			}
			return false;
		}
};

sMyFilterClosestRayResultCallback singleResult( from, to, uiColFlags );
m_pWorld->rayTest( from, to, singleResult );

Post Reply