Thursday, December 20, 2012

Re: Hit detection for GWT canvas - which strategy for drawings?

As long as the shapes are simple, in a UML diagram you have mostly boxes, some arrows, and text, AABB bounding boxes are easy to compute, as long as your not worrying about overlapping shapes which could be hollow:, i.e. you have a large rectangle with a small rectangle inside, the large
one is NOT filled, but has a higher z-index, the inside-outsize line projection is reasonable and efficient. The question is, if the higher z-order rectangle in hollow ( you didn't fill it ), and your mouse falls within the smaller one inside, which did you mean to pick?

 I knows Alfredo is right as I wrote most of Lienzo ;-) I have about 30 years working in structured graphics. It was EXACTLY for this reason, that it's not always trivial to do this kind of stuff if you are a beginner, that we decided to write it and make it Apache 2 and give it away, and would love if people used it and gave us feedback.

Hey, it's free.

Also, soon, we will be adding optimal DAG layout in a toolkit on top of Lienzo. Right now were taking a breather after getting 1.0 out the door and enjoying the holidays and family, as Lienzo was written after we got home from our day jobs, sometimes tlll 3 or 4am, much to the dismay of our loved ones ;-)

On Thursday, December 20, 2012 1:00:15 PM UTC-5, RyanZA wrote:
The check itself is obviously O(1) per check, as opposed to O(num of lines) for his original proposal (iterate all shape components) - and the 'etc'  should have kind of implied to you there were 4 checks and not 2...

Also, he is not making a 3d engine here and is very unlikely to need anything more than AABB bounding boxes. You don't need a minimum bounding box for this, just a general one.
He is making flowcharts/UML diagrams, and is unlikely to have more than a few hundred shapes - which performs exceptionally well on AABB bounding boxes and simple polygon checks.
If he is implementing this himself, then spending the next year developing a perfect object selection engine feels a bit overkill for his needs?

Alfredo has the right idea though - nearly always best to go with a library that has already had all of this done for him - provided he can fit his flowchart/UML code into the Lienzo scene graph. :)

On Thursday, December 20, 2012 6:28:54 PM UTC+2, Dean S. Jones wrote:
A bounding box check isn't O(1), it's O(n) for n shapes, THEN you have to run edge detection, and only then if all your shapes are Polygons. The issue with bounding boxes is that, in all but the most trivial cases, they are expensive to compute. If you add in any Affine Transforms ( rotate, scale, shear ) the task becomes even worse, and worse still is the bounding boxes of Quadratic or Bezier curves.

With a large number of shapes, you can gain some speed using Quadtree's http://en.wikipedia.org/wiki/Quadtree and other types of spatial indexing. But you have 4 checks per "primitive", not 2 (x > box.left && x < box.right && y > box.top && y < box.bottom), so you need to keep 4 coordinates. For a large number of shapes, this uses memory, more memory if you choose to use a Quadtree or similar spatial indexing.

So, I have found the color indexing option the best, it's not quite O(1), as it's performance depends on the hashmap lookup time. The downside is you only have 167772316 possible color keys, I feel this is acceptable limitation. This could be helped by having multiple "layers" with each layer having it's own full colorspace. Hashmap lookup time should be near optimal
since an analysis of collisions with out keys yeilds about 1100 out of 167772316, which is pretty good. As a side note, HashMap in GWT is not an optimal implementation for this case. The other downside is you have to draw also in the "ghost canvas", but we found our drawing time so fast it was not a concern.

isPointInPath only works while the Path is CURRENT in the Canvas context 2d, which you lose after drawing another shape or context.restore(), so it's only possible to test IMMEDIATELY after you draw the shape, before you do any context.restore(), which means you have to be drawing somewhere while your doing hit testing, probably another ghost canvas. This also only works for "closed shapes", not something like a PolyLine or Arc.


On Thursday, December 20, 2012 8:29:40 AM UTC-5, RyanZA wrote:
First option is definitely best, but you need to expand it slightly:

Use a bounding box around every shape, so you can do an O(1) check if the click is inside the bounding box (click.x < box.left, click.x > box.right, etc)
If the click is inside the bounding box, then you can run normal edge detect O(number of lines per poly) -- (drop a line to the axis, count number of line intersections - check stackoverflow or similar for code)

If you have Z index on your shapes, then start from the biggest Z index and take the first match.
If you are drawing in a list, then start from the bottom of the list and work upwards and take the first match.

On Thursday, December 20, 2012 1:14:43 PM UTC+2, membersound wrote:
I'm creating some kind of drawings/flowchart/UML-diagram like tool with GWT Canvas (Java).
For hit-detection of my drawings I could imagine 3 different strategies, but I do not know which would work best for my goal.

-  Just keep track of all Shape coordinates and iterate all objects on mouseclick
-  draw all objects on a ghost-canvas on mouseclick, and use isPointInPath() after every object drawing
- using a ghost-canvas and draw each object with its own color (like #000001, #000002), and keep reference of them in a Map<Color, Shape>. Then just detecting the mouseclick on the ghost-canvas and get the object belonging to the pixelcolor under mouse

What would you prefer, and why?

--
You received this message because you are subscribed to the Google Groups "Google Web Toolkit" group.
To view this discussion on the web visit https://groups.google.com/d/msg/google-web-toolkit/-/zuzz4QjRyf4J.
To post to this group, send email to google-web-toolkit@googlegroups.com.
To unsubscribe from this group, send email to google-web-toolkit+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-web-toolkit?hl=en.

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home


Real Estate