e3pick_hit_find

[Roger H. <rog...@mi...>]

I have been having speed problems with marquee selection.
The application has a FOR loop going through all the hit
triangles. This can easily be 100,000 triangles. It calls a
routine which gets the details of the hit which eventually calls
e3pick_hit_find which has a WHILE loop which indexes
through the list structure looking for the item, hence this
is executed 100,000 * 100,000 / 2 = 10,000,000,000 times
and increases with the square of the complexity, taking
an unacceptable amount of time.

My solution is to cache the last list item found and its index
along with the instance data pointer to make sure we not are
comparing apples and pears. Then if the requested index
is greater than the cached index, we continue looking on
from that point. Typically for my code this is the next item.
My code used to work backwards through the list, and
this would still work, but cannot   not be optimised as the
list is not doubly linked.

I have tested this code and it seems to be OK on Mac with Cocoa.
If you think its OK, could someone check it in please.

Roger.

New version:



static TQ3PickHit *
e3pick_hit_find(TQ3PickUnionData *pickInstanceData, TQ3Uns32 n)
{	TQ3PickHit		*currentHit = pickInstanceData->pickHits;



	// Check we're not out of range
	if (n > pickInstanceData->numHits)
		return(NULL);
	
	if (pickInstanceData->data.common.numHitsToReturn != kQ3ReturnAllHits)
		{
		if (n > pickInstanceData->data.common.numHitsToReturn)
			return(NULL);
		}
	
	// Optimised for programs which read hits by increasing number.
	// As there is no previous pointer, cannot optimise for decrements
	static TQ3PickUnionData* instanceCached = NULL ;
	static TQ3Uns32 indexCached = 0xFFFFFFFF ;
	static TQ3PickHit* hitCached = NULL ;
	
	TQ3Uns32 index = n ;
	if ( instanceCached == pickInstanceData && n > indexCached &&  
hitCached != NULL )
		{
		n -= indexCached ;
		currentHit = hitCached ;
		}

	// Walk through the list to find the right item
	while (currentHit != NULL && n != 0)
		{
		--n ;
		currentHit = currentHit->nextHit;
		}

	indexCached = index ;
	instanceCached = pickInstanceData ;
	hitCached = currentHit ;

	return(currentHit);
}