Re: Faster way to test pixels?

FROM : Gary L. Wade
DATE : Sun May 25 18:52:24 2008

I've not explored Velocity Engine programming under the PowerPC or its
equivalent under the Intel processor family, but your needs seem like
they might be solved by using that as a solution to further improve the
performance.

Graham Cox wrote:
>
> On 25 May 2008, at 5:13 pm, Jens Alfke wrote:
>

>> There are geometric techniques for doing this, that wouldn't require
>> working with pixels. Computing the bounding box of a Bézier curve is
>> very easy, so you can usually trivially reject most of them by
>> checking the rects for intersection. For the rest, you have to flatten
>> them into polygons and test each segment. (Doesn't Quartz 2D have
>> functions to do this?)

>
> I already do basic geometric testing to weed out obvious non-hits, but
> beyond that I have to test pixels because I'm not just dealing with a
> simple stroke and/or fill of the path (for example distributing
> arbitrary images with varying scales and angles along a path).
>
>

>>> Is there any faster way of doing this than just iterating over the
>>> pixels like this? I can't think of anything but someone might have a
>>> bright idea.

>>
>> If you do test against pixels, work with the raw pixmap instead of
>> making an Obj-C call to get every pixel. Get the pointer to its pixel
>> data, and use the rowbytes and the pixel size to iterate over pixels.
>> If the pixmap is always in a known format, it's pretty easy. (Sounds
>> like it's 8-bit grayscale, which is as easy as it gets, with one byte
>> per pixel.)

>
> Yep, this is a good idea (and also thanks to Ken who suggested the same
> thing). I see a ~10x speed-up doing this:
>
>            NSBitmapImageRep* bits = [self pathBitmapInRect:ir];
>           
>            // if any pixels in this bitmap are set, we have a hit.
>            // fast method tests 4 pixels at a time in the raw data:
>           
>            unsigned    dataLength = ([bits bytesPerRow] * [bits
> pixelsHigh]) >> 2;
>            unsigned*      data = (unsigned*)[bits bitmapData];
>            unsigned    k = 0;
>           
>            // scan until we hit a non-white value or reach the end
>           
>            while(( k < dataLength ) && ( data[k++] == 0xFFFFFFFF ));
>           
>            hit = ( k < dataLength );
>
>
> a good improvement for now - thanks. If it needs more the vImage stuff
> looks like a good option.
>
> G._______________________________________________
>
> Cocoa-dev mailing list (<email_removed>)
>
> Please do not post admin requests or moderator comments to the list.
> Contact the moderators at cocoa-dev-admins(at)lists.apple.com
>
> Help/Unsubscribe/Update your Subscription:
> http://lists.apple.com/mailman/options/cocoa-dev/<email_removed>
>
>
> This email sent to <email_removed>