[Drawkit] Much faster hit-testing (was: Re: Scaling issues)

[Brad Larson]

I tried it out on the really large drawing I had going before.   
Before, I would peg a CPU at 100% and cause it to beachball (all work  
is done on the main thread, so no opportunity for second core to take  
some of the load off) after selecting two large items.  With the  
qUseScaledContext define (the default), the max CPU usage was around  
35%, with almost all of that being from the drawRect: method (due to  
the refresh for the changing selection box).  The qUseCachedBitmap  
define provided a boost in performance from what was done before, but  
it still beachballed after selecting about 5 large items.

Therefore, unless crazy selection artifacts pop up somewhere from it,  
I'd say that the new default qUseScaledContext algorithm is by far the  
way to go.  It makes a huge difference.

On May 26, 2008, at 6:27 AM, Graham Cox wrote:

> I've been looking at various ways to improve the hit-testing  
> efficiency. I have come up with several alternate methods any of  
> which should be faster than the original, and in the default case,  
> *much* faster.
>
> The new default was suggested by Ken Ferry at Apple. Instead of  
> rendering the intersected area of the object and then scanning  
> through the resulting image looking for a set pixel, it scales the  
> intersected region to just one destination pixel consisting only of  
> an alpha value. If it gets set by the operation, there was a hit,  
> otherwise there wasn't. This means just one pixel ever needs to be  
> tested, no matter how large the intersected area. In addition, no  
> style substitution is needed, so that's a big saving as well, and it  
> doesn't use an NSBitmapImageRep, which I'm told is not as efficient  
> as it looks as asking for its data forces it out of the cache on the  
> GPU. There are a few other savings too, like re-using the bitmap and  
> its wrapper context for each test, so eliminating the overhead of  
> creating them. This also means that the zoom factor is irrelevant -  
> everything gets scaled to a 1x1 image regardless so it takes  
> constant time to test it no matter how large the original object on  
> screen. It's damned clever, wish I'd thought of it!
>
> This *should* show a substantial improvement in performance in the  
> case you mentioned of dragging a selection rect across very large  
> objects (or indeed when you have many small ones). So I'd suggest  
> you try it in your situation and see how well it works. I'd love to  
> see the "before and after" figures - I've profiled it briefly myself  
> but I don't think my test case is stressing it as much as yours.
>
> There's also another approach which I tried which you can try out  
> (#defines within the code will select which algorithm is used) where  
> the whole object is temporarily cached during the selection drag  
> which avoids the overhead of the repeated bitmap creation, but  
> compared to Ken's method is definitely not going to give you the  
> same gains. Chances are it'll be removed again. To use this  
> technique you need to update the DKSelectAndEditTool code because  
> the caching scheme relies on some new notifications sent by that tool.
>
> Let me know how it works out,
>
>
> cheers, Graham
>
>
>
>
> < 
> DKDrawableObject 
> .h><DKSelectAndEditTool.h><DKDrawableObject.m><DKSelectAndEditTool.m>
>
>
>
> On 24 May 2008, at 9:05 am, Brad Larson wrote:
>
>> After running the program through Instruments, it looks like the a  
>> whole lot of processor cycles are being spent in [DKDrawableObject  
>> pathBitmapInRect].  That method appears to rasterize the object  
>> shapes to perform hit detection, and the size of the bitmap seems  
>> to be set by the original zoom factor, so huge bitmaps are being  
>> created as you drag the mouse for the selection rectangle on this  
>> drawing.  Maybe the bitmap hit testing could take the scale into  
>> account, creating bitmaps whose size only matches the size in  
>> pixels of that area at the current scale factor, then translate  
>> that scaled bitmap to the hit testing coordinates being fed in.
>>
>> What caused you to go with a variant of the method described here:  http://lists.apple.com/archives/cocoa-dev/2004/Sep/msg00698.html 
>>  as opposed to the mathematical model you proposed here: http://lists.apple.com/archives/cocoa-dev/2004/Sep/msg00696.html 
>>  ?  I haven't checked fully, but did you go with some of the  
>> optimizations that Uli Kusterer suggested in that thread?
>
> _______________________________________________
> Drawkit mailing list
> Drawkit at lists.apptree.net
> http://lists.apptree.net/listinfo.cgi/drawkit-apptree.net

______________________
Brad Larson
SonoPlot, Inc.
3030 Laura Lane, Suite 120
Middleton, WI 53562