Re: [pyGEF-develop] Clicking and hit regions

[<pyg...@li...>]

On 7/8/07, pyg...@li... <
pyg...@li...> wrote:
>
> Hi
> I'm trying to optimize the hitting and selection of graphical objects.
> I can't quite make up my mind, maybe you can help.
>
> In the previous design a Graphic object can define a boundingbox, this
> boundingbox is stored in the untransformed form, just like the Graphic. So
> to draw the Graphic, I concatenate their Affine with the GC's and draw them
> in the own coordinate system. I can therefore use their boundingbox to draw
> a selection region around the selected object.
>
> When i added the SelectionManager, things had to change slightly, because
> when multiple Graphics are selected the bounding region must be square with
> the axis, this will also be used to identify dirty regions when the view
> needs repainting.
>
> To simplify things I made the boundingbox to always be square with the
> axis. However when only one is selected and when a hit is tested the
> original transformed boundingbox should be used.
>


Do you actually have a performance problem with hit testing?  Or are you
just worried that you will?
If you do an early reject using bounding boxes you can avoid the most
expensive part of the testing.  Then the only case to worry about is the one
where thousands of objects are all piled on top of one another.  But a)
that's not that likely a case and b) it still may be fast enough for GUI
speeds without doing anything special.

Ok, but I'll assume for now that you really do have a performance problem
with hit testing --



Another performance issue is that a lot of inverse transforms are needed to
> identify a hit, as shown in the example:
> 1. Mouse is pressed at XY
> 2. XY gets transformed to DOCUMENT coordinates
> 3. Loop over all hitable Graphics (as a make a list of all the Graphics
> that were hit, this way a hit on the same point will select the next one in
> the list)
> 4. Inverse transform the DOCXY to the coordinates of the Graphic
> 5. Use contains to see of the Graphic was hit
>
> Any other clever way of avoiding this constant inverse transformation,
> other than making boundingboxes square with the axis.
> Would cashing the inverse transform provide any performance increases.
>

Yes, I think always storing the inverse transform along with the forward
transform would probably help.
But I also think sticking in a bbox check at step 3 will help a lot too.
You do maintain a bounding box in doc coordinates for each object already,
right?


Could you consider adding the following functionality to your geom library.
>
> def HitTest(Point p, Rect rect, Affine transform):
> """ must return True if the rectangle is hit """
>
> If this is done with pyrex it could really help with performance. This
> also defines a "standard" interface and we can later play with the
> implementation.
>

So that would do an inverse transform of the point and then test it against
the rect?  I don't think that's going to be much faster than
   rect.contains(transform.inv_transform(p))

because the contains() and inv_transform() are already in pyrex.

--bb