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

[Graham Cox]

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




-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKDrawableObject.h
Type: application/octet-stream
Size: 7925 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080526/c71daeb1/attachment-0004.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKSelectAndEditTool.h
Type: application/octet-stream
Size: 4735 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080526/c71daeb1/attachment-0005.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKDrawableObject.m
Type: application/octet-stream
Size: 87654 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080526/c71daeb1/attachment-0006.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKSelectAndEditTool.m
Type: application/octet-stream
Size: 37967 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080526/c71daeb1/attachment-0007.obj>
-------------- next part --------------




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?