[CLA] Add event support with Canvas renderer

[chrism]

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

[chrism]

Collision detection module (spatial hash implementation)

[chrism]

Canvas with events/picking using collision detection algorithm

[chrism]

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.

[elazutkin]

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

[chrism]

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.