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

[Ondřej Žižka]

----- Original Message ----- 
From: "Philip Taylor" <excors+whatwg at gmail.com>
To: "Ondřej Žižka" <ondra at dynawest.cz>
Cc: <whatwg at whatwg.org>
Sent: Saturday, June 21, 2008 2:16 AM
Subject: Re: [whatwg] '' <canvas> element "selection buffer"


> On 07/06/2008, Ondřej Žižka <ondra at dynawest.cz> wrote:
>> Hi,
>>
>>  I've been looking for something similar to OpenGL's selection buffer - 
>> that is, you can get some object ID for the given coordinates.
>>
>>  E.g.,  Jacob Seidelin's chess game 
>> http://blog.nihilogic.dk/search/label/chess could use it, but instead, 
>> keyboard control had to be used.
>>
>>  isPointInPath() does not solve the problem effectively if the path would 
>> be too complex - e.g. pixel-based sprites in several layers.
>>
>>  For an example of what I want to implement, see e.g.
>> 
>> http://www.openttd.org/screens.php?image=images/screens/0.5.0/japan_national_railway_3_aug_1984 .
>>  Mathematical computation of the object is principially impossible (or 
>> too complex in best case).
>
> 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.

> What problems does that approach have, that could be better solved by
> a different approach (like selection buffers)?
>
> 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.

> The selection buffer would help if you're doing a lot of
> lookups compared to the amount of drawing and have a lot of
> overlapping sprites, but I would expect it to be worse (since the
> additional drawing cost would exceed the cost of the object-selection
> code) in the much more common cases where you're only doing a single
> lookup per frame or only have a few sprites overlapping any given
> point. Are there other issues I'm missing?

I don't know the internals of canvas, but considering the mousemove events, 
which can be fired very frequently, storing the ID into the selection buffer 
would be much more effective, especially if we drew once with ID buffering 
ON, then switched it OFF, and then re-used the filled buffer for other 
rounds, until we know we need to re-fill it -- using the mentioned picture 
as an example, this would occur when the map has moved.

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.

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.

Ondra