[patch][ccla] Add event support with Canvas renderer

[Chris Mitchell]

Canvas does not currently support events, but various algorithms can be used to implement events, especially since we maintain the scene graph.

[Chris Mitchell]

Collision detection module (spatial hash implementation)

[Chris Mitchell]

Canvas with events/picking using collision detection algorithm

[Chris Mitchell]

Unfortunately, the attached patches have gone a bit stale. They worked with the March 6, 2008 revision of Dojo and will need to be merged to trunk if we want to use this approach which implements events using spatial hash (for collision detection).

One benefit of the technique I've used is that the spatial hash can be reused for collision detection. Here's an overview of the basic algorithm implemented currently:

1) Create a spatial hash which conceptually is a grid of "buckets" that covers the entire surface area. The dimensions of each bucket is configurable. The spatial hash is keyed by location of a cell in the grid.

2) Each time a shape is added to the surface, compute the transformed axis-aligned bounding area, and from the aabb, compute the grid location indexes i,j that the shape's aabb intersects with. for each grid intersect, create a 2d hashcode of i,j grid location and add the shape to to that location's bucket.

3) Anytime the geometry of a shape is modified, update the buckets that the new shape's new aabb occupies.

4) for picking, using mouse position x,y, map to a grid location, i,j. Then for each shape contained in the spatial hash bucket at the grid location, check transformed bounding box against the x,y position to determine whether there's a broadband intersect. This can be further checked against actual shape geometry.

Since the map is built and adjusted dynamically, 2d collision testing for any shapes can be accomplished using the shape's bbox, rather than the mouse point, and the map is reused. The map is also useful for closest shape to arbitrary point calculations.

A suggestion for an alternative, possibly more efficient way to implement picking/events using Canvas has been suggested by Eugene. Our intention had been to implement the alternative approach described below, compare performance/features against the attached spatial map technique, and then make a decision as to which one (or both) to check in, but other things came up.

Alternative Implementation (not yet implemented): ================================================= Basically in real graphics systems the mouse picking is done like this:

1) Create a canvas 1x1 pixel. 2) Set the background to black. 3) Make sure that you set a transformation correctly for all shapes to "move" our canvas in the proper place. 4) Draw all shapes backwards using simple white color ignoring their custom colors.

4a) After you draw a shape check the canvas pixel:

4a1) If it is white, you are done --- create an event for this shape, if event handlers are attached. 4a2) If it is black --- continue.

This way you can select arbitrary complex shapes correctly regardless of anything.

Obvious improvements:

a) You can use a canvas bigger than 1x1, e.g., 3x3 to emulate an uncertainty, and use a weighting function to make sure that the selection is correct from user's point. b) Only the geometry is important (shapes, line thickness, fonts), disregard the visual information (colors, gradients, and so on). Special case: a completely transparent color. c) You can use a spacial index to select only a relevant subset of shapes. d) You can use a simple bbox intersection test to weed out irrelevant shapes. e) Create the selection canvas once (it is a singleton), and reuse for all individual canvases.

What we want to know is how expensive it is in general for our purposes.

[Eugene Lazutkin]

Dup of #6529 and #6530. Should I close them in favor of this new ticket?

[Chris Mitchell]

Yeah, sorry about that, I looked for those tickets and didnt find them last night. Let's use this one to track the implementation.

One other note on the current attached implementation:

This patch for canvas events only does rough "broadband" point-intersect tests using shape's axis-aligned bounding boxes. To implement "exact" picking, the next level of detail will require point-intersect geometry functions being added for each shape (these are general functions that probably should be mixed into the abstract renderer-independent shape superclasses). For each shape in the set of shapes that intersected a picking point using the aabb intersect, perform a point-geometry intersect test (sorted from topmost shape toward the back) that determines if the mouse point lies within or on the geometry of the shape to determine the exact shape picked.

In otherwords, it's not "exact" picking, but for many scenarios it should be good enough.

[liyang]

I made a patch which includes 1) exact picking by brute force drawing on a hidden 1x1 canvas; 2) text shape impl; 3) a small performance tuning. It shall arrive here soon through IBM internal process.

The patch was tested on FF 3.6 and Safari 4.0.4, all tests passed except for text path and line styles. The two features are not supported by current canvas spec.

Spatial hash is prototyped too, in attempt to speed up the picking. Later benchmark shows spatial hash does boost picking a lot, however it also has a significant penalty at the drawing time in order to maintain the hashed space, and the memory consumption is another concern.

My preference is the brute force picking. As its performance is very OK (though not the fastest), and it keeps the code cleaner, and most important it shall be the drawing speed that users expect from canvas, rather than the picking speed.

The spatial hash prototype will be attached here too, so whoever has the need can find it.

[Chris Mitchell]

Comments from 4/15/2010:

Date: 2010-04-15 01:33 EDT Sender: Yang Li

Sorry for my absentminded mistake. Please review the updated version. Date: 2010-04-14 10:16 EDT Sender: Jared Jurkiewicz

The brute force patch doesn't quite meet style guidelines.

Issues:

No brackets around if/else one-liners. thi is bad as it can lead to bugs down the line if they are modified later and brackets are no added.

See: + if (pickingMode) + ctx.fillRect(s.x, s.y, s.width, s.height); + else + ctx.drawImage(this.canvasImage, s.x, s.y, s.width, s.h

Those both need {} around their content.

Docs for function not entirely complete.

+ _render: function(/* Object */ ctx, /* Function */ pickingMode){

summary: render the group ctx.save();

These need to define what the params are. Should look like:

+ _render: function(/* Object */ ctx, /* Function */ pickingMode){

summary: render the group ctx: What CTX is. pickingMode: What pickingMode is

And so on. There are numerous examples of the function docs not being quite to dojo spec.

New functions have been added and they have no documentation. Even internal functions should have a bsic summary and definitions for what the parameters are.

Can you address these isues in both implementations?

[Chris Mitchell]

The attached patches worked with Dojo 1.5 release. Need to be tested (possibly updated to Dojo 1.6 level. Here's the result of spatial hash vs. brute force:

On Firefox 3.6: Drawing time in ms Selecting time in ms

Brute force 240 2459 Spatial hash 941 303

For Safari 4.0: Drawing time in ms Selecting time in ms

Brute force 147 1535 Spatial hash 684 230

The time is of a drawing a sample 50 times and checking which shape is under mouse 3000 times. The result is as expected, spatial hash saves time at selection but with a penalty at drawing plus additional memory consumption. Both the save and the penalty are significant. Note that the current spatial hash impl is still experimental, there are still problems known and unsolved in the spatial hash implementation, mainly 1) text shapes does not provide bbox (due to canvas API limitation) thus ignore by spatial hash; 2) with a very thick stroke, a shape would be larger than its reported bbox, making spatial hash miss events nears the shape's border.

At this time, the brute force approach is simpler and complete (but out of date--dojo 1.5).

Thanks go to Yang Li, IBM for these patches.

[Patrick Ruzand]

Patch to add input events support to canvas

[Patrick Ruzand]

The new attached patch above (code from Eduardo Abe (IBM, CCLA) and Patrick Ruzand (IBM, CCLA) provides the following improvements:

1/input events on canvas. It is an improved version of the brute-force patch to rely on the HTML5 canvas.isPointInPath() method when applicable (ie when the shape is a path and is filled). This method performs a geometry-based hittest and is much faster that a pixel-based hittest.

2/ add a gfxTarget property to the input events (for all renderers). Because the events source in the case of the canvas is the canvas DOM element itself, it is impossible to get the gfx shape from the event target (it can be done when the target matches a shape definition as in SVG/VML but not in the case of the canvas). To make this possible, a reference to the gfx shape is added to the shape's rawnode and a new gfxTarget property is added to the event.

[Patrick Ruzand]

This new patch fixes the touch event support, including in multitouches scenario. It also includes various bug fixes related to the bubbling chain.

[Patrick Ruzand]

improved version with multi touch scenario support

[Patrick Ruzand]

bug fix when firing touch events under iOS

[Patrick Ruzand]

fix patch base directory (base dir. was dojox/gfx/, now root of dojox/)

[Patrick Ruzand]

fix base dir

[Patrick Ruzand]

bug fix (bubbling) + test (dojox/gfx/tests/test_bubbling.html)

[Patrick Ruzand]

fix surface.connect('touchXXX') scenarios (specific touch bubbling was bypassed)

[Patrick Ruzand]

Fix conflict with patch 12561. Patch 12561 must now be applied to fix 12561and 12391 issues. and

[Patrick Ruzand]

bug fix: Shape.getEventSource() should return the real event source (aka surface.rawNode) for consistency', instead of the shape itself

[Chris Mitchell]

bumping up priority, as this patch is critical for android support.

[Patrick Ruzand]

Refactor the patch following Eugene's review to minimize its footprint on the gfx code. *NOTE: 7782 requires the patch 12819 before it is applied.

[Patrick Ruzand]

rename the extended renderer (canvasWithEvents.js).

[Chris Mitchell]

(In [24608]) fixes #7782 - canvas event support lands! android gfx ftw !strict

[Patrick Ruzand]

#6529 is a duplicate of this ticket.