Re: [Gnash-dev] Re: point test

[Udo Giacomozzi]

Hello Sandro,


[Note I missed the original posting]


Sunday, November 4, 2007, 12:56:07 PM, you wrote:
>> I've been thinking about the point_test issue some more. In my opinion,
>> point testing should be done by the renderer, because...


Hmm, it's not a very elegant way IMHO because it forces the renderer
to deal with hit testing, while that has nothing to do with rendering
at all. So we have a different implementation (= potentially different
behaviour!) depending on what renderer you use.

A hit_test() algorithm should not be hard to implement at all. The
most difficult part is probably handling of the quadratic bezier
curves, but with some math one should find the right formula for
these.

I haven't the current implementation in mind, but essentially it would
work this way (simplified for lines only):


STEP 1: apply the world matrix to the paths

  So we have the vertices like they would appear on screen

  
STEP 2: find "edges" (=lines) crossing the requested Y coordinate

  Just browse through all lines, see if they cross the Y coordinate
  (ignore lines that do not).
  
  If it does, then calculate the X coordinate of the crossing. If it
  is smaller than the previously checked crossing, jump over to the
  next edge.

  If the X coordinate is larger than the hit test X coordinate, ignore
  the edge too.

  Otherwise check it's fill styles. If the direction of the line is
  downwards (growing Y), then check fill style 0, otherwise check fill
  style 1. Ignore the line if it is perfectly horizontal.

  If the choosen fill style is not -1 (ie. it refers to a fill style)
  then set the temporary result of the hit test to TRUE, otherwise set
  it to FALSE.

  
  With other words: Find the nearest edge at the left side of the
  requested X coordinate crossing the Y coordinate and check if the
  fill style, which directs to the hit test coordinate, is set.

  
Curves make it a *bit* more complicated because you have to
(a) calculate the crossing with the Y coordinate, and
(b) deal with two crossings


Question: Does Flash' hit test method work with thick outlines too (or
just fills)?


>> a) The renderer must know about fully qualified shapes and fill styles
>> anyway, in order to render anything.

Yes, but implementations may vary (and what is when rendering is
disabled?).


>> b) Each renderer library we currently use has a method just for this
>> purpose (Agg: hit_test(), Cairo:  cairo_in_fill(), OpenGL: selection
>> mode).

Cool. Didn't know aboud AGG's hit_test() method! :)


>> c) If we let the renderer deal with point_test, we avoid duplicating the
>> effort in the Gnash core.

Effort should be minimal.
BTW, what is the problem with the current implementation?


>> Of course we would need to design a nice interface. We might also
>> implement a caching mechanism. All this will make Gnash faster than it
>> currently is.

Is hit testing currently really a bottleneck?
BTW, how would the caching mechanism work?


>> What do you think?

SS> Seems an easy path, we may try that as a start.
SS> Doing so shouldn't preclude future changes.
SS> We do already have a caching architecture (where caches are bitmaps)
SS> so adding normalized topology to the caches shouldn't be too hard.

SS> The interface should be simple:

Agree with the interface, but matrix information should be passed just
like with draw_shape() because the AGG backend uses the internal
matrix transformation methods of the AGG lib.


SS> The renderer will need a way to tell wheter the cache was invalidated.

uuuhuuh, hold on...! The *renderer* tells when the cache was
invalidated? That's completely the wrong direction to go! The renderer
is a (mostly) stateless thing - it can draw any frame at any time if
requested. It can *use* some kind of cache but invalidation should
*always* happen in the core since that's the only place where we know
what's going on.

Again, I think it's a bad idea to let the renderer do other things
than rendering. If, at all, then caching should be implemented outside
the renderer. Still interested in the way such a cache would be
implemented.

I also think that a caching mechanism for hit_test is overkill.
Compared to the real rendering it is done really quickly.


SS> Note that taking care of normalization in the core lib would
SS> reduce memory usage (ie: the core
SS> lib won't need to keep both the normalized and source
SS> representations) and leverage eventual
SS> differences/bugs in the renderers. But could be eventually a
SS> separate step. 

What do you mean by "normalized and source representations" ? What are
you normalizing?

Udo