Re: e3pick_hit_find

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

On 21 Feb, 2007, at 19:18, James Walker wrote:

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

Presumably if I specify kQ3PickSortNone, it does not do the search. When
the user clicks, I do a pick on that point, sorted and I use just the  
frontmost, the
hits are few anyway. For a marquee selection I don't need to sort the  
picks, I
process all of them within the selection rectangle, but they are  
numerous.
Actually I get lots of references to the same object, and I only need  
one
reference to each object. One day it would be nice to have a pick filter
function which the application supplies, which would have access to the
pick list and a potential new pick, and it would either add the new  
pick or
not, or replace a pick with the new one. For the point pick I could  
just keep
the frontmost pick, and for the  marquee selection I could just keep the
small number I need. This way we would not need to allocate as much
memory. Anyway, lets keep it simple for now.

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

That would be great.

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

Yes, though of course there's no need to do the sort at all for  
kQ3PickSortNone.