Irregular bitmaps intersection

by Paul Hsieh

The following appeared on on 11/12/98:

> Can anyone give me a tip on designing a method to detect if the mouse is
> over an irregular shaped bitmap on screen?

Solution 1

Create a bounding box, and perhaps other bounding metrics that are precomputed for the bitmap. Use that for a trivial reject, then simply use a pixel scan (not of pixel on the screen, but of pixel in a memory copy of the bitmap, offset but the current (x,y) -- system memory is normally faster to access than graphics memory.)

Refinement 1

Create a set of "MIP MAPS" that represent the bitmap, except instead of using a filtering function to combine pixels, use the "OR" function. You can then use upper level MIP maps as further trivial reject levels.

Solution 2

Choose a pixel within the mouse cursor bounding box randomly, and test to see if that point both hits the bitmap and the cursor. Continuously call procedure with a "real time" priority. In all probability, if there is an intersection, computers being as fast as they are, will run enough possibilities to eventually encounter it. There are obviously error conditions that you would have to gage to see if they were acceptable or not.

Solution 3

If your object is a piece of geometry, then it can be decomposed into some set of subrectangles whose intersection with the object is in some sense trivial (a single line boundary, or nothing or complete intersection.) These would then be fairly easy to test for. This requires custom code for each bitmap of course.

Of course after you are done, write a paper and sumbit it to siggraph (with a credit to me I hope! :o) )