Re: [Gnash-dev] Re: point test

[Sandro Santilli]

On Sun, Nov 04, 2007 at 03:19:04PM +0100, Udo Giacomozzi wrote:

> 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 belive quadratic bezier curves are already implementedin the
current gnash::path::point_test, which should be using a ray
crossing algorithm based on a few assumption we can't take
(like a path is closed).

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

Think outlines too. I added this support in gnash exposing a
withinSquareDistance interface to gnash::path.
This was while doing the Drawing API testing, which you can use
to also verify the support I added is incomplete (fails for the curve,
see the xcheck in DrawginApiTestRunner.cpp).

> BTW, what is the problem with the current implementation?

See file attached in bug #21498.

> >> 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?

Nope, but it's not correct, and if we need to normalize the paths
to make it correct then it will be worth normalizing the paths once
instead of at every hit test.

> BTW, how would the caching mechanism work?

I think the idea is that rather then calling normalize_path (which already
exists and is used by different renderers) at display time we'd call it
at first ::display and not again on next.

> 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.

The query point should be passed in "local" coordinates already,
which is the same coordinate space as the edges.

> 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.

"a way to tell" means "a function to call against the shape_character_def"
to know if he needs to rebuild the cache or not. Of course this is assuming
that it's the renderer performing the normalization, the output of which would
be cached.

> 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?

I'm not a topology expert, but the algorithms I've dealt with
only work with topologically correct representation.
For example, crossing edges break most of those algorithms.

--strk;