[whatwg] '' Re: '' <canvas> element "selection buffer"

[Philip Taylor]

On 21/06/2008, Ondřej Žižka <ondra at dynawest.cz> wrote:
> > To hande sprites, you could draw each sprite onto its own canvas
> > (during the initial loading process) and test
> > spriteCtx.getImageData(x, y, 1, 1).data[3] > 127 to see if it's
> > sufficiently non-transparent. Quickly skip any sprites whose bounding
> > box does not contain (x,y), then test the remaining ones from front to
> > back to find the first that's solid under the given point, and that
> > should give the answer.
> >
>
>  Thanks for the idea, crossed my mind too, but I guessed this would cause
> very poor performance - imagine performing such search upon "mousemove"
> event.

I guessed otherwise :-)
To see if I was wrong, I tried implementing this at
http://philip.html5.org/demos/canvas/spritepick/example.html

That example doesn't do anything very clever - on mousemove, it loops
through every sprite and first checks against the bounding box and
then uses getImageData to see if the sprite is transparent at that
point. When the display changes, it just draws every sprite, clipped
to the area that changed.

In Firefox (3.0) and WebKit (nightly) on Windows, it seems to be
easily fast enough with a thousand sprites on the screen. As the
number of sprites increases, performance seems to be affected almost
entirely by the rendering, and the sprite-picking takes very little
time. In Firefox on Linux, and in Opera (9.5) on Linux and Windows,
the drawing speed is rubbish and it doesn't work smoothly with more
than a hundred sprites.

The drawing code could probably be made faster by redrawing as few
sprites as possible per frame, or by not redrawing them at all (and
using some other UI to indicate the selected object). The
sprite-picking code could probably be made faster too, e.g. by doing
some kind of quadtree thing to quickly get a list of all sprites that
might overlap the given point.

So, I don't think I see any evidence that this method of selecting
sprites has unacceptable performance.

> > The main issue I can think of is performance: using getImageData()
> > means you have to test every sprite that's possibly under the given
> > point, which could be expensive if you have a very large number of
> > them, whereas selectionBuffer.getIdAt() takes constant time but
> > introduces a (probably quite large) constant overhead to all drawing
> > operations.
> >
>
>  Not for all operations, only those drawn when "ID buffering" is on. Not all
> objects must be "clickable".
>  Second, these operations performed in native functions would be
> incomparably faster than lookups in JS.

But the ID-buffering operations in native functions would have to be
performed on every pixel that is drawn (while ID-buffering is
enabled), and there will be millions of pixels; whereas the JS lookups
would have to be performed once per sprite-that-is-under-the-mouse for
each frame, and there will only be a few sprites to check each time,
so it's doing much less work than the native functions and so it can
be much faster overall.

>  The other issue is inconvenience. Programming pixel-based sprite look-ups
> using all offsets is much more tedious than simply reading a value with an
> one-line command.

Another issue is that canvas implementations are usually quite buggy
(I found new bugs in Opera and WebKit while writing the earlier
example...), and the selection buffer would add a lot of complexity
and a lot of new bugs, since it would have to interact with clipping
and composite operations and alpha and all the optimisations that
implementations perform. Buggy implementations are very inconvenient
for authors, so it may be more convenient to use the existing simple
APIs instead of relying on the browsers to provide a complex new API
:-)

>  I'm quite surprised this has not been discussed - or was it? I haven't
> found any discussion. IMHO canvas element will support this kind of
> interactivity some day - it would be very natural complement of it's
> displaying purposes.

I don't remember any previous discussion about this specific topic. In
general discussions about interactivity, the answer is usually to use
SVG instead of canvas - SVG is designed for interactive graphical
documents, while canvas is designed for non-interactive
dynamically-generated images, so in many cases it's better to use SVG
rather than to reinvent SVG's features inside canvas. (That may not
apply to this specific case, though.)

-- 
Philip Taylor
excors at gmail.com