Hit detection for GWT canvas - which strategy for drawings?

[membersound]

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?

[RyanZA]

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.

[Ümit Seren]

All methods are viable. 

I know that the color based hit detection is widely used and supposed to be quite efficient. 

There are a couple of stackoverflow threads about that: 

http://stackoverflow.com/questions/31158/resources-of-techniques-use-for-collision-detection-in-2d

http://stackoverflow.com/questions/12618734/hit-detect-canvas-js

You can also think about using one of the canvas frameworks/libraries (like kinetic.js, etc). They have hit detection and also user interaction built in. 

[Dean S. Jones]

I had posted, why reason it was deleted?

[Alfredo Quiroga-Villamil]

In Lienzo, we opted for a Color Map approach. Detecting bounding boxes as previously suggested in the thread is not a trivial task, more so for non geometrical shapes.

http://wiki.emitrom.com/wiki/index.php/Picking

Lienzo is only 4 months old and already surpasses in functionality and efficiency all the JS based frameworks we've seen out there, that includes Kinetic. An example is, in Kinetic you have to handle dragging yourself to make it efficient. In Lienzo, you simply call setDraggable on the "shape" and we do the rest for you.

My suggestion would be to save you lots of time, coding and go with a GWT only based solution that has an incredible number of features already. While you are at it you can also provide us with feedback and help us make it better. It's Apache 2 and we are using it to build a few things.

A ton more of features are in the pipeline. We are as we speak for example in the process of adding zoom support. Via different mediators you'll be able to zoom in/out your entire viewport.

Take a look at the explorer here:

http://www.emitrom-lienzo.appspot.com/

Regards,

Alfredo

--
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/-/tPJuPlAJED4J.
To post to this group, send email to google-we...@googlegroups.com.
To unsubscribe from this group, send email to google-web-tool...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-web-toolkit?hl=en.

--
Alfredo Quiroga-Villamil

AOL/Yahoo/Gmail/MSN IM:  lawwton

[Dean S. Jones]

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.

[RyanZA]

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. :)

[Dean S. Jones]

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 ;-)

[RyanZA]

Ah awesome, I didn't realize you were behind Lienzo. :)
You should have mentioned - it came across that your advice to him was an impossibly difficult solution considering his question. As you say, using Lienzo for this is definitely the right answer!

However regarding the inner/outer boxes problem - this isn't a problem - you only use the AABB box as an initial check, and then you do a proper match using the shape itself. So in your example, the AABB box would match for the large unfilled rectangle, but then the actual check on the shape would fail. It would then check AABB on the smaller box which would pass, and then do an actual check against the shape of the smaller box which would also pass - and the smaller shape would be selected.

It does break down for very complex scenes - say a 3d model of a city - but it works very well for UML and other basic low density situations (which are very common on the web) - and can be easily extended with B-trees in the future if time allows / performance requires it. Most of the HTML5 stuff you see on the web using canvas uses this approach after all.

[Dean S. Jones]

I was taking a larger view, in the sense of the thread itself, ( over and above his question ) of the practicalities and pitfalls of hit detection in Canvas as a whole. Section 4.8.11.2.15 of the Canvas specification mentions Hit Regions, sadly, they are for bitmaps, not shapes, and do not seem to be implemented anyway.

Outside of something like a UML diagram, taking into account various Curved types, and possible Affine Transforms, bounding boxes becomes more and more expensive to calculate, well, true minimum bounding boxes.

Now, we have all seen UML diagrams, and unless it's the most trivial UML diagram that ever existed, it's not going to fit on the screen. So, your going to need at least a scale transform. And probably panning support. They will be in Lienzo 1.1.

I have a few algorithmic solutions to paring the search space down, B-Trees, Red Black Trees, Quadtrees, but I haven't used them because the color key approach ( so far ) has proved that we don't need bounding boxes for hit detection.

I'm not alone in Lienzo, we have a team of 4, two of us have worked in structured graphics since the 80's ( yea, I'm old ), I think I have a reference on ray tracing the Utah Raster Teapot from 88' 

https://groups.google.com/forum/?fromgroups#!search/Dean$20S$20Jones$20Teapot/comp.graphics/QJ4OFnM-R-A/l2A9azlc3WEJ

So, yea, been doing this a LONG TIME.

[Alfredo Quiroga-Villamil]

Yeah something else that I have been silently playing with is a "scrollable layer" :) that would also help in this case.

I think it's safe to say that the guys behind Lienzo are all well rounded engineers that have been around the block. Biggest issue is as Dean said, time constraints since we all have other responsibilities and day jobs. But I think some of the things we are considering for 1.1 are sure to be nothing short of amazing, we are really pushing the boundaries and as Ryan said the limitations start to become what the browser/devices can handle. We are also very much aware of "Mobile", so many of our decisions and debates are centered around cpu cycles and memory. As Dean pointed out, we even use our own implementation of Maps and Lists.

--

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/-/O9Foj0GE6z4J.

To post to this group, send email to google-we...@googlegroups.com.
To unsubscribe from this group, send email to google-web-tool...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-web-toolkit?hl=en.

[Philippe Lhoste]

On 20/12/2012 15:15, Dean S. Jones wrote:
> Of course, as Umit says, there are other FREE Frameworks that have figured it out, like
> Lienzo, that take care of it all for you, http://www.emitrom.com/lienzo

Hey, I didn't know this one! Looks cool. Thanks for sharing.
(Even if I discovered you are involved with this company, which is perfectly OK, of
course. As you wrote, it is free, after all.)

--
Philippe Lhoste
-- (near) Paris -- France
-- http://Phi.Lho.free.fr
-- -- -- -- -- -- -- -- -- -- -- -- -- --