Re: e3pick_hit_find

[James W. <ja...@fr...>]

Roger Holmes wrote:

> 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.

I'd like to take a broader look at the algorithms and data structures 
used for picking.  The problem you encountered is that e3pick_hit_find 
uses a linear-time search.  But I also notice that E3Pick_RecordHit does 
a linear-time search for the place to insert the next hit, which means 
that in the worst case, inserting H hits could take time on the order of 
H * H.

Here's a proposal:

1. Store the hits, or pointers to them, in a std::vector.  This will 
allow e3pick_hit_find to work in constant time with no caching.

2. Don't keep the hits sorted as they're being collected.  Instead, sort 
them all at once the first time Q3Pick_GetPickDetailData or 
Q3Pick_GetPickDetailValidMask is called after the picking is done.  The 
sorting can be used with std::sort, in time on the order of H log H.
-- 
   James W. Walker, Innoventive Software LLC
   <http://www.frameforge3d.com/>