Re: [pyGEF-develop] Clicking and hit regions

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

Hi

On 07 Jul 2007, at 11:32 PM, pyg...@li... wrote:

>
> On 7/8/07, pyg...@li... < pygef-=20
> de...@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, =20
> this boundingbox is stored in the untransformed form, just like the =20=

> Graphic. So to draw the Graphic, I concatenate their Affine with =20
> the GC's and draw them in the own coordinate system. I can =20
> therefore use their boundingbox to draw a selection region around =20
> the selected object.
>
> When i added the SelectionManager, things had to change slightly, =20
> because when multiple Graphics are selected the bounding region =20
> must be square with the axis, this will also be used to identify =20
> dirty regions when the view needs repainting.
>
> To simplify things I made the boundingbox to always be square with =20
> the axis. However when only one is selected and when a hit is =20
> tested the original transformed boundingbox should be used.
>
>
> Do you actually have a performance problem with hit testing?  Or =20
> are you just worried that you will?
> If you do an early reject using bounding boxes you can avoid the =20
> most expensive part of the testing.  Then the only case to worry =20
> about is the one where thousands of objects are all piled on top of =20=

> one another.  But a) that's not that likely a case and b) it still =20
> 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 =20
> problem with hit testing --
>
I don't have any performance problems per say, but it is the =20
operation that probably will be performed the most,  so it should be =20
done as effectively as possible.
>
>
> Another performance issue is that a lot of inverse transforms are =20
> 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 =20
> Graphics that were hit, this way a hit on the same point will =20
> 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 =20
> 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 =20
> forward transform would probably help.
> But I also think sticking in a bbox check at step 3 will help a lot =20=

> too.  You do maintain a bounding box in doc coordinates for each =20
> object already, right?
>
You just gave me an idea that I did not think of before. Thanks. I =20
will just have to update my dirty region slightly as it fits around =20
the objects inside the graphic, not the actual bbox. Currently some =20
of the corners of a rotated object could get missed. This is probably =20=

also the better way of handing the dirty region.

>
> Could you consider adding the following functionality to your geom =20
> 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. =20
> This also defines a "standard" interface and we can later play with =20=

> the implementation.
>
> So that would do an inverse transform of the point and then test it =20=

> 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.
>
So the method calls do not add that much overhead?
> --bb
>

I think I have found some bugs in your geom lib:
	1. rect.intersects returns None if there is an intersection a =
return =20
True is probably all that is missing from the end of the method.
	2. affine.shearing is missing, affine.scaling is there

Other comments on geom:
	1. If affine.scaling returns a point then AffineScale should =20
probably also be allowed to accept a point as constructor argument, =20
even though this might not make any sense it will make the API =20
uniform as most other accepts points. Just a thought.
	2. the some applies to AffineShear

--retief
> ----------------------------------------------------------------------=20=

> ---
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/=20
> _______________________________________________
> pyGEF-develop mailing list
> pyG...@li...
> https://lists.sourceforge.net/lists/listinfo/pygef-develop

Retief Gerber
Lektor
Lecturer
Departement Elektriese en Elektroniese Ingenieurswese
Department of Electrical and Electronic Engineering

Tel: +27 21 808 4011  I  Faks/Fax: +27 21 808 4981
E-pos/E-mail: hrg...@su...

Universiteit Stellenbosch University
Privaat Sak/Private Bag X1 Matieland 7602
Suid-Afrika/South Africa
www.eng.sun.ac.za


=EF=BF=BC