Again with the getIntersectionList()

[Jeff Schiller]

I am trying to determine a few things about getIntersectionList() on
the SVGSVGElement interface. I would like to implement these functions
in WebKit and Gecko.

1) It seems that the WG has clarified that the NodeLists returned by
getIntersectionList() and getEnclosureList() are to be static and not
live [1] [2].  Just wanted confirmation.  Please say yes :)

2) There has been feedback that the second parameter to these
functions is not clear [2].  I would agree with that feedback.

It also may be that Batik implemented it this way.  This seems more
sensible to me than looking at the painters model.  Has it been
clarified in the errata or upcoming Second Edition?

    "only return elements whose drawing order has them below the given
reference element"

This suggests the painters model to me.  However, it is not clear why
this is useful.

It seems that Opera may have implemented it as the root of the subtree
that should be searched.  Erik, can you confirm?

What did Batik finally implement?

I would personally think that the subtree search is more useful than
the painters model.  If verbage were to be updated, here's my first
attempt:

    "only return elements that are in the subtree whose root is given
by the reference element"

3) Can a suitable test be added to the SE test suite using the second
argument in those functions?

Thanks,
Jeff

[1] http://www.w3.org/2003/01/REC-SVG11-20030114-errata#liveness-getintersectionlist-getenclosurelist
[2] http://dev.w3.org/SVG/profiles/1.1F2/test/harness/htmlObject/struct-dom-11-f.html
[3] http://lists.w3.org/Archives/Public/www-svg/2004Oct/0007

[Jeff Schiller]

Another confirmation.  The method getIntersectionList(rect):

"Returns the list of graphics elements whose rendered content
intersects the supplied rectangle, honoring the 'pointer-events'
property value on each candidate graphics element."

So if I have a circle whose pointer-events="stroke" and then I call
getInsersectionList(rect) where rect is in the center of the circle's
fill but does not intersect with the circle's stroke, then that circle
will not be part of the returned NodeList, correct?

Thanks,
Jeff


On Fri, Nov 6, 2009 at 8:50 AM, Jeff Schiller <codedread@...> wrote:

> I am trying to determine a few things about getIntersectionList() on
> the SVGSVGElement interface. I would like to implement these functions
> in WebKit and Gecko.
>
> 1) It seems that the WG has clarified that the NodeLists returned by
> getIntersectionList() and getEnclosureList() are to be static and not
> live [1] [2].  Just wanted confirmation.  Please say yes :)
>
> 2) There has been feedback that the second parameter to these
> functions is not clear [2].  I would agree with that feedback.
>
> It also may be that Batik implemented it this way.  This seems more
> sensible to me than looking at the painters model.  Has it been
> clarified in the errata or upcoming Second Edition?
>
>    "only return elements whose drawing order has them below the given
> reference element"
>
> This suggests the painters model to me.  However, it is not clear why
> this is useful.
>
> It seems that Opera may have implemented it as the root of the subtree
> that should be searched.  Erik, can you confirm?
>
> What did Batik finally implement?
>
> I would personally think that the subtree search is more useful than
> the painters model.  If verbage were to be updated, here's my first
> attempt:
>
>    "only return elements that are in the subtree whose root is given
> by the reference element"
>
> 3) Can a suitable test be added to the SE test suite using the second
> argument in those functions?
>
> Thanks,
> Jeff
>
> [1] http://www.w3.org/2003/01/REC-SVG11-20030114-errata#liveness-getintersectionlist-getenclosurelist
> [2] http://dev.w3.org/SVG/profiles/1.1F2/test/harness/htmlObject/struct-dom-11-f.html
> [3] http://lists.w3.org/Archives/Public/www-svg/2004Oct/0007
>

[Alex Danilo]

Hi Jeff,

--Original Message--:

>Another confirmation.  The method getIntersectionList(rect):
>
>"Returns the list of graphics elements whose rendered content
>intersects the supplied rectangle, honoring the 'pointer-events'
>property value on each candidate graphics element."
>
>So if I have a circle whose pointer-events="stroke" and then I call
>getInsersectionList(rect) where rect is in the center of the circle's
>fill but does not intersect with the circle's stroke, then that circle
>will not be part of the returned NodeList, correct?

Sounds correct to me. Well spotted.

Alex

>Thanks,
>Jeff
>
>
>On Fri, Nov 6, 2009 at 8:50 AM, Jeff Schiller <codedread@...> wrote:
>> I am trying to determine a few things about getIntersectionList() on
>> the SVGSVGElement interface. I would like to implement these functions
>> in WebKit and Gecko.
>>
>> 1) It seems that the WG has clarified that the NodeLists returned by
>> getIntersectionList() and getEnclosureList() are to be static and not
>> live [1] [2].  Just wanted confirmation.  Please say yes :)
>>
>> 2) There has been feedback that the second parameter to these
>> functions is not clear [2].  I would agree with that feedback.
>>
>> It also may be that Batik implemented it this way.  This seems more
>> sensible to me than looking at the painters model.  Has it been
>> clarified in the errata or upcoming Second Edition?
>>
>>    "only return elements whose drawing order has them below the given
>> reference element"
>>
>> This suggests the painters model to me.  However, it is not clear why
>> this is useful.
>>
>> It seems that Opera may have implemented it as the root of the subtree
>> that should be searched.  Erik, can you confirm?
>>
>> What did Batik finally implement?
>>
>> I would personally think that the subtree search is more useful than
>> the painters model.  If verbage were to be updated, here's my first
>> attempt:
>>
>>    "only return elements that are in the subtree whose root is given
>> by the reference element"
>>
>> 3) Can a suitable test be added to the SE test suite using the second
>> argument in those functions?
>>
>> Thanks,
>> Jeff
>>
>> [1] http://www.w3.org/2003/01/REC-SVG11-20030114-errata#liveness-getintersectionlist-getenclosurelist
>> [2] http://dev.w3.org/SVG/profiles/1.1F2/test/harness/htmlObject/struct-dom-11-f.html
>> [3] http://lists.w3.org/Archives/Public/www-svg/2004Oct/0007
>>
>
>
>

[Andreas Neumann-7]

Hi Jeff,

I am glad that you are taking on the task of implementing this very useful
method to fill the gap until implementors are natively implementing the
method.

On the other hand this should really be natively implemented in all
compliant viewers. I guess every implementor already has the prerequisites
for this method, since they have to do hit-testing for graphical elements
anyway ... so it is mainly a matter of testing not only the top elements,
honoring the pointer-events attributes.

So is it mainly webkit and Firefox that do not implement the methods? Are
bugs filed?

Andreas


On Sat, November 7, 2009 3:54 am, Jeff Schiller wrote:

> Another confirmation.  The method getIntersectionList(rect):
>
> "Returns the list of graphics elements whose rendered content
> intersects the supplied rectangle, honoring the 'pointer-events'
> property value on each candidate graphics element."
>
> So if I have a circle whose pointer-events="stroke" and then I call
> getInsersectionList(rect) where rect is in the center of the circle's
> fill but does not intersect with the circle's stroke, then that circle
> will not be part of the returned NodeList, correct?
>
> Thanks,
> Jeff
>
>
> On Fri, Nov 6, 2009 at 8:50 AM, Jeff Schiller <codedread@...> wrote:
>> I am trying to determine a few things about getIntersectionList() on
>> the SVGSVGElement interface. I would like to implement these functions
>> in WebKit and Gecko.
>>
>> 1) It seems that the WG has clarified that the NodeLists returned by
>> getIntersectionList() and getEnclosureList() are to be static and not
>> live [1] [2].  Just wanted confirmation.  Please say yes :)
>>
>> 2) There has been feedback that the second parameter to these
>> functions is not clear [2].  I would agree with that feedback.
>>
>> It also may be that Batik implemented it this way.  This seems more
>> sensible to me than looking at the painters model.  Has it been
>> clarified in the errata or upcoming Second Edition?
>>
>>    "only return elements whose drawing order has them below the given
>> reference element"
>>
>> This suggests the painters model to me.  However, it is not clear why
>> this is useful.
>>
>> It seems that Opera may have implemented it as the root of the subtree
>> that should be searched.  Erik, can you confirm?
>>
>> What did Batik finally implement?
>>
>> I would personally think that the subtree search is more useful than
>> the painters model.  If verbage were to be updated, here's my first
>> attempt:
>>
>>    "only return elements that are in the subtree whose root is given
>> by the reference element"
>>
>> 3) Can a suitable test be added to the SE test suite using the second
>> argument in those functions?
>>
>> Thanks,
>> Jeff
>>
>> [1]
>> http://www.w3.org/2003/01/REC-SVG11-20030114-errata#liveness-getintersectionlist-getenclosurelist
>> [2]
>> http://dev.w3.org/SVG/profiles/1.1F2/test/harness/htmlObject/struct-dom-11-f.html
>> [3] http://lists.w3.org/Archives/Public/www-svg/2004Oct/0007
>>
>
>

--
Andreas Neumann
http://www.carto.net/neumann/
http://www.svgopen.org/

[Boris Zbarsky]

Andreas Neumann wrote:
> I guess every implementor already has the prerequisites
> for this method, since they have to do hit-testing for graphical elements
> anyway ... so it is mainly a matter of testing not only the top elements,
> honoring the pointer-events attributes.

Which means a complete rewrite of the hit-testing algorithm, since the
hit-testing algorithm bails out once you get a hit, right?

-Boris

[Andreas Neumann-7]

ok - in that case I was way too naive with my thinking. I apologize.

I just wanted to add that this is a very important method for many
interactive applications. Think about maps/GIS, interactive graphics
editors, applications where you need to select elements to manipulate
them, etc

BTW: Jeff (codedread) let me know that he is working on a native
implementation (Webkit), not a Javascript shim as I was thinking.

So, hopefully, along with the implementation(s) ambiguous or missing parts
in the spec could be addded/clarified.

Best,
Andreas


On Sat, November 7, 2009 2:58 pm, Boris Zbarsky wrote:

> Andreas Neumann wrote:
>> I guess every implementor already has the prerequisites
>> for this method, since they have to do hit-testing for graphical
>> elements
>> anyway ... so it is mainly a matter of testing not only the top
>> elements,
>> honoring the pointer-events attributes.
>
> Which means a complete rewrite of the hit-testing algorithm, since the
> hit-testing algorithm bails out once you get a hit, right?
>
> -Boris
>
>

--
Andreas Neumann
http://www.carto.net/neumann/
http://www.svgopen.org/

[Alex Danilo]

Boris Zbarsky wrote:
>Andreas Neumann wrote:
>> I guess every implementor already has the prerequisites
>> for this method, since they have to do hit-testing for graphical elements
>> anyway ... so it is mainly a matter of testing not only the top elements,
>> honoring the pointer-events attributes.
>
>Which means a complete rewrite of the hit-testing algorithm, since the
>hit-testing algorithm bails out once you get a hit, right?

Well almost.

Yes you do bail out when you get a hit, that's true.

But the code to walk the tree and hit-test is there
already. So a bit of refactoring to handle that case
could inhibit the bail out, and instead accumulate
a list of hit nodes. The top most node in that list
is the traditionally hit node that would normally
cause a bail out.

Normally, when you bail out it saves walking the rest
of the tree, but worst case requires a full walk of
the tree. Accumulating a list in the process of the
walk is the same cost, so it could be pretty cheap.
Much better to do this in the UA than trying to make
script authors walk through (slow) hoops.

This discussion does bring up an interesting aside
with relation to the proposals for rendering order.
Current hit-testing is based in the tree/document order.
If rendering order changes come in, there will be
serious performance hits for the changed render model
so that needs to be included as part of all this too.

In any case, what makes author's lives easier is
what we really want as much as poor implementors
have to suffer - but they only suffer the
implementation pain once...

Alex


>-Boris
>
>
>

[Jeff Schiller]

All of this discussion misses the fact that we are not hit-testing a point, we have to hit-test a rectangle for checkIntersection.  This means we really need to determine if the sides of the rectangle intersect any shape's fill or stroke depending on the value of pointer-events on that shape.  Doesn't that make it a totally different algorithm altogether?

On Nov 7, 2009 7:37 PM, "Alex Danilo" <alex@...> wrote:

Boris Zbarsky wrote: >Andreas Neumann wrote: >> I guess every implementor already has the prerequis...

Well almost.

Yes you do bail out when you get a hit, that's true.

But the code to walk the tree and hit-test is there
already. So a bit of refactoring to handle that case
could inhibit the bail out, and instead accumulate
a list of hit nodes. The top most node in that list
is the traditionally hit node that would normally
cause a bail out.

Normally, when you bail out it saves walking the rest
of the tree, but worst case requires a full walk of
the tree. Accumulating a list in the process of the
walk is the same cost, so it could be pretty cheap.
Much better to do this in the UA than trying to make
script authors walk through (slow) hoops.

This discussion does bring up an interesting aside
with relation to the proposals for rendering order.
Current hit-testing is based in the tree/document order.
If rendering order changes come in, there will be
serious performance hits for the changed render model
so that needs to be included as part of all this too.

In any case, what makes author's lives easier is
what we really want as much as poor implementors
have to suffer - but they only suffer the
implementation pain once...

Alex


>-Boris
>
>
>

[Alex Danilo]

Yes, good point.

Totally different, and a lot more work too...

The original post with the subject 'Pointer-events
Suggestion' was about hit-testing from a point.

checkIntersection adds a whole new level of pain
for the implementer. That introduces polygonal
intersections which generally are expensive
operations (although the rectangle case makes
things a bit less onerous).

Alex

--Original Message--:

>All of this discussion misses the fact that we are not hit-testing a point, we have to hit-test a rectangle for checkIntersection.  This means we really need to determine if the sides of the rectangle intersect any shape's fill or stroke depending on the value of pointer-events on that shape.  Doesn't that make it a totally different algorithm altogether?
>
>
>On Nov 7, 2009 7:37 PM, "Alex Danilo" <alex@...> wrote:
>
>Boris Zbarsky wrote: >Andreas Neumann wrote: >> I guess every implementor already has the prerequis...
>
>Well almost.
>
>Yes you do bail out when you get a hit, that's true.
>
>But the code to walk the tree and hit-test is there
>already. So a bit of refactoring to handle that case
>could inhibit the bail out, and instead accumulate
>a list of hit nodes. The top most node in that list
>is the traditionally hit node that would normally
>cause a bail out.
>
>Normally, when you bail out it saves walking the rest
>of the tree, but worst case requires a full walk of
>the tree. Accumulating a list in the process of the
>walk is the same cost, so it could be pretty cheap.
>Much better to do this in the UA than trying to make
>script authors walk through (slow) hoops.
>
>This discussion does bring up an interesting aside
>with relation to the proposals for rendering order.
>Current hit-testing is based in the tree/document order.
>If rendering order changes come in, there will be
>serious performance hits for the changed render model
>so that needs to be included as part of all this too.
>
>In any case, what makes author's lives easier is
>what we really want as much as poor implementors
>have to suffer - but they only suffer the
>implementation pain once...
>
>Alex
>
>
>>-Boris
>>
>>
>>
>
>
>
>
>
>

[Jeff Schiller]

On Fri, Nov 6, 2009 at 8:50 AM, Jeff Schiller <codedread@...> wrote:

> 2) There has been feedback that the second parameter to these
> functions is not clear [2].  I would agree with that feedback.
>
>    "only return elements whose drawing order has them below the given
> reference element"
>
> This suggests the painters model to me.  However, it is not clear why
> this is useful.
>
> It seems that Opera may have implemented it as the root of the subtree
> that should be searched.  Erik, can you confirm?
>

Can someone please clarify for me what the second parameter in
getIntersectionList() is?  If not, can it be added for your next
telcon agenda?

Thank you,
Jeff

[Doug Schepers-3]

Hi, Jeff-

Jeff Schiller wrote (on 11/12/09 9:28 PM):

> On Fri, Nov 6, 2009 at 8:50 AM, Jeff Schiller<codedread@...>  wrote:
>>  2) There has been feedback that the second parameter to these
>>  functions is not clear [2].  I would agree with that feedback.
>>
>>      "only return elements whose drawing order has them below the given
>>  reference element"
>>
>>  This suggests the painters model to me.  However, it is not clear why
>>  this is useful.
>>
>>  It seems that Opera may have implemented it as the root of the subtree
>>  that should be searched.  Erik, can you confirm?
>>
>
> Can someone please clarify for me what the second parameter in
> getIntersectionList() is?  If not, can it be added for your next
> telcon agenda?

According to SVG 1.1 [1]:

[[
getIntersectionList
Returns the list of graphics elements whose rendered content intersects
the supplied rectangle, honoring the 'pointer-events' property value on
each candidate graphics element.

Parameters
in SVGRect rect: The test rectangle. The values are in the initial
coordinate system for the current 'svg' element.
in SVGElement referenceElement: If not null, then only return elements
whose drawing order has them below the given reference element.

Return value
NodeList: A list of Elements whose content intersects the supplied
rectangle.

No Exceptions
]]

So, the first parameter is an SVGRect object (not an element), while the
second parameter is a reference to an element that allows the author to
filter the results by their document order.

This seems like a strange API design to me, though actually it could be
useful.  Consider a few examples of use, given this fragment (note that
I'm using <rect> elements for clarity, but it could be any elements):

<svg xmlns="http://www.w3.org/2000/svg">
   <rect id="r1" x="5" y="5" width="40" height="40"/>
   <rect id="r2" x="105" y="105" width="40" height="40"/>
   <rect id="r3" x="5" y="5" width="40" height="40"/>
   <rect id="r4" x="5" y="5" width="40" height="40"/>
   <rect id="r5" x="5" y="5" width="40" height="40"/>
</svg>


A) SVGRect1 {x:20, y:20, width:0, height:0}
    getIntersectionList( SVGRect1 );

This is essentially a point that will return everything that intersects
that point, regardless of document order; thus, it will return r1, r3,
r4, & r5.  It will not return r2, because that rectangle doesn't
intersect that point.  This would be useful for getting every element at
the coordinates of a mouse click, for example.


B) SVGRect1 {x:20, y:20, width:100, height:100}
    getIntersectionList( SVGRect1 );

This is a rectangular area that will return everything that intersects
that area, regardless of document order; thus, it will return all of the
rectangles, because it intersects them all.  This would be useful for
finding elements inside a certain viewport (either a real viewport as
established by an <svg> element, or a virtual one created by a clipPath,
etc.).


C) SVGRect1 {x:20, y:20, width:0, height:0}
    getIntersectionList( SVGRect1, r4ref );

This is the same as (A), but with the constraint that it only returns
those elements that come before r4 in document order; thus, it will
return r1 & r3.  It will not return r5, because that rectangle comes
later in document order.  This would be useful for getting every element
below the event target element (e.g. r4) at the coordinates of a mouse
click.

Not exactly the way I would have designed it, but it still has sensible
use cases.


[1]
http://www.w3.org/TR/2003/REC-SVG11-20030114/struct.html#InterfaceSVGSVGElement

Regards-
-Doug Schepers
W3C Team Contact, SVG and WebApps WGs

[Boris Zbarsky]

On 11/13/09 3:49 AM, Doug Schepers wrote:
> A) SVGRect1 {x:20, y:20, width:0, height:0}
> getIntersectionList( SVGRect1 );
>
> This is essentially a point that will return everything that intersects
> that point, regardless of document order

I would have actually expected this to return nothing, since all
intersections are empty (zero area)...

If that's not what's intended, the spec needs to be _very_ clear on
this, and then all sorts of interesting issues are raised.  For example,
does a rectangle with x=0,y=0,width=5,height=5 intersect a rectangle
with x=5,y=5,width=5,height=5?  I posit the intuitive answer that most
people would want is "no".  How is this different from the case above?

For what it's worth, in Gecko rectangles in the css renderer are
effectively considered closed on top and left and open on bottom and
right; so a rectangle with x=0,y=0,width=5,height=5 is described by the
inequalities: 0 <= x < 5, 0 <= y < 5.  Hence the two rectangles I
describe above do not in fact intersect, and any rectangle with width=0
or height=0 is the empty set.

I'm not sure what Gecko's svg implementation does in this regard, though
I suspect it's similar.

-Boris

[Rick-2]

Boris

The scenario you describe below is useful for finite integer math, in
rendering engines for example, where you are dealing with pixel sets.
In floating point Cartesian math, they all all intersect.  Euclid said
so.


---------- Forwarded message ----------
From: Boris Zbarsky <bzbarsky@...>
Date: Fri, Nov 13, 2009 at 11:26 AM
Subject: Re: Again with the getIntersectionList()
To: Doug Schepers <schepers@...>
Cc: www-svg <www-svg@...>, Jeff Schiller <codedread@...>


On 11/13/09 3:49 AM, Doug Schepers wrote:
>
> A) SVGRect1 {x:20, y:20, width:0, height:0}
> getIntersectionList( SVGRect1 );
>
> This is essentially a point that will return everything that intersects
> that point, regardless of document order

I would have actually expected this to return nothing, since all
intersections are empty (zero area)...

If that's not what's intended, the spec needs to be _very_ clear on
this, and then all sorts of interesting issues are raised.  For
example, does a rectangle with x=0,y=0,width=5,height=5 intersect a
rectangle with x=5,y=5,width=5,height=5?  I posit the intuitive answer
that most people would want is "no".  How is this different from the
case above?

For what it's worth, in Gecko rectangles in the css renderer are
effectively considered closed on top and left and open on bottom and
right; so a rectangle with x=0,y=0,width=5,height=5 is described by
the inequalities: 0 <= x < 5, 0 <= y < 5.  Hence the two rectangles I
describe above do not in fact intersect, and any rectangle with
width=0 or height=0 is the empty set.

I'm not sure what Gecko's svg implementation does in this regard,
though I suspect it's similar.

-Boris




--
Cheers!
Rick

[Boris Zbarsky]

On 11/14/09 12:33 AM, Rick wrote:
> The scenario you describe below is useful for finite integer math, in
> rendering engines for example, where you are dealing with pixel sets.
> In floating point Cartesian math, they all all intersect.  Euclid said
> so.

Yes, I'm well aware of the different definitions of intersection
involved.  Or more precisely the different definitions of "rectangle".

How about addressing the substance of my comments (which is that the
spec needs to explicitly call out how intersections work here, since on
the web they often work in a somewhat different way)?  That's assuming
that is in fact the way we want them to work, of course.  I take your
comments to be a roundabout way of saying that we do want them to work
that way.

-Boris

P.S.  Strictly speaking, Euclid never defined what he meant by
"intersect" (he assumed it was obvious), nor did he define whether his
quadrilaterals are open or closed (or equivalent, since he didn't have
those concepts).  He doesn't much talk about intersections of
quadrilaterals with each other.

[Erik Dahlstrom]

On Fri, 13 Nov 2009 03:28:35 +0100, Jeff Schiller <codedread@...>  
wrote:

> On Fri, Nov 6, 2009 at 8:50 AM, Jeff Schiller <codedread@...>  
> wrote:
>> 2) There has been feedback that the second parameter to these
>> functions is not clear [2].  I would agree with that feedback.
>>
>>    "only return elements whose drawing order has them below the given
>> reference element"
>>
>> This suggests the painters model to me.  However, it is not clear why
>> this is useful.
>>
>> It seems that Opera may have implemented it as the root of the subtree
>> that should be searched.  Erik, can you confirm?

Yes, that's an accurate observation of what Opera does at the moment. One  
might also express it as:
"Any intersected element that doesn't have the reference-element as  
ancestor must not be included in the returned NodeList"

Cheers
/Erik

--
Erik Dahlstrom, Core Technology Developer, Opera Software
Co-Chair, W3C SVG Working Group
Personal blog: http://my.opera.com/macdev_ed

[Jonathan Watt-3]

On 2009-11-08 3:42 AM, Jeff Schiller wrote:
> All of this discussion misses the fact that we are not hit-testing a
> point, we have to hit-test a rectangle for checkIntersection.  This
> means we really need to determine if the sides of the rectangle
> intersect any shape's fill or stroke depending on the value of
> pointer-events on that shape.  Doesn't that make it a totally different
> algorithm altogether?

Note that interpreting "intersects" as "intersects the sides of" would imply
that getIntersectionList only returns elements that actually intersect the
perimeter of the given rectangle - NOT elements that are fully inside the rectangle.

Jonathan

[Doug Schepers-3]

Hi, Boris-

You're right, these methods certainly need more attention and
clarification.  We'll talk about this today... thanks for your valuable
feedback.

Regards-
-Doug Schepers
W3C Team Contact, SVG and WebApps WGs


Boris Zbarsky wrote (on 11/13/09 11:26 AM):

> On 11/13/09 3:49 AM, Doug Schepers wrote:
>> A) SVGRect1 {x:20, y:20, width:0, height:0}
>> getIntersectionList( SVGRect1 );
>>
>> This is essentially a point that will return everything that intersects
>> that point, regardless of document order
>
> I would have actually expected this to return nothing, since all
> intersections are empty (zero area)...
>
> If that's not what's intended, the spec needs to be _very_ clear on
> this, and then all sorts of interesting issues are raised. For example,
> does a rectangle with x=0,y=0,width=5,height=5 intersect a rectangle
> with x=5,y=5,width=5,height=5? I posit the intuitive answer that most
> people would want is "no". How is this different from the case above?
>
> For what it's worth, in Gecko rectangles in the css renderer are
> effectively considered closed on top and left and open on bottom and
> right; so a rectangle with x=0,y=0,width=5,height=5 is described by the
> inequalities: 0 <= x < 5, 0 <= y < 5. Hence the two rectangles I
> describe above do not in fact intersect, and any rectangle with width=0
> or height=0 is the empty set.
>
> I'm not sure what Gecko's svg implementation does in this regard, though
> I suspect it's similar.
>
> -Boris
>

[Jonathan Watt-3]

On 2009-11-06 3:50 PM, Jeff Schiller wrote:
> 1) It seems that the WG has clarified that the NodeLists returned by
> getIntersectionList() and getEnclosureList() are to be static and not
> live [1] [2].  Just wanted confirmation.  Please say yes :)

yes

I'm curious what use cases people see for functionality along the lines of
getIntersectionList/getEnclosureList. In any use case you may have:

 * Would you want to get elements that are "below" a given element
   in rendering order, or would you rather want elements that
   are descendants of a given element.

 * If you want the elements that are "below", should 'z-index' be
   taken into account in deciding what's "below" an element, or
   do you really just want "comes before in document order"?

 * Would you really want 'pointer-events' to be taken into account?

 * Would you want 'visibility' or 'display' to be taken into account?

 * How about opacity, markers, masking or filters?

 * Would you want elements that are fully inside the rectangle
   that you specify?

 * Would you want elements that have overlap with the rectangle
   that you specify?

 * Would you only want elements that intersect with the *edges*
   of the rectangle that you specify (i.e. not elements that are
   fully inside)?

 * Would bbox intersection checking be sufficient?

Of course I'd be most interested to hear of *specific* things that people have
actually found themselves wanting to do but couldn't (or not well) because of
the lack of getIntersectionList/getEnclosureList or similar in SVG implementations.

The use case I see for getEnclosureList is implementation of a selection tool in
online SVG editors. I wonder if taking stroke into account in necessary though,
or if bbox calculations (only taking fill into account) would be sufficient. I
think bbox would probably be okay.

The use case I see for getIntersectionList is again online SVG editor specific:
image copping. When cropping an image you'd want to throw away any elements that
are fully outside the bounds of the SVG image to save space. In this case
though, you'd not only want to take into account stroke, but also marker,
filter, and anything else that increases the bounds of a graphic element over
stroke bounds. getIntersectionList doesn't take this into account though, and
therefore doesn't satisfy this use case. Maybe cropping optimization is better
done on the server?

So neither of these use cases are strongly completely to me for
keeping/implementing getIntersectionList/getEnclosureList. Any better ones? :-)

Jonathan

[Jeff Schiller]

On Thu, Nov 19, 2009 at 11:38 AM, Jonathan Watt <jwatt@...> wrote:

>  * Would you really want 'pointer-events' to be taken into account?

nah

>  * Would you want 'visibility' or 'display' to be taken into account?

nah

>  * Would you want elements that are fully inside the rectangle
>   that you specify?

To me intersection should mean "does this element's area intersect
with this other area".  It's not about whether it crosses this other
border.  Thus, {x:20, y:20, width:20, height:20} intersects with {x:0,
y:0, width:50, height:50}.

>  * Would you want elements that have overlap with the rectangle
>   that you specify?

That's what 'intersection' means. I must have misunderstood you.

>  * Would you only want elements that intersect with the *edges*
>   of the rectangle that you specify (i.e. not elements that are
>   fully inside)?

No.

>  * Would bbox intersection checking be sufficient?

For the most part, yes.  See below.

> Of course I'd be most interested to hear of *specific* things that people have
> actually found themselves wanting to do but couldn't (or not well) because of
> the lack of getIntersectionList/getEnclosureList or similar in SVG implementations.

Actually in SVG-edit we're after the functionality in
getIntersectionList().  I want to know when my rubber-band box
visually touches another element when selecting multiple elements.
Currently I brute force check all element bboxes for this in
JavaScript.  I'd like the browser to do this super-fast for me using
space partitioning algorithms and highly optimized machine code :)

At the moment I don't have any strong preferences for anything fancy
beyond that - but that's just me and that's just right now.

If I am only able to get across one message to the WG it's this:

* getIntersectionList() and getEnclosureList() are the visual
equivalent of getElementsByTagName/ClassName/etc.  SVG _is_ a visual
language, right? :)

Letting developers query/filter elements is incredibly powerful.  See jQuery.

The fact that the current SVG ecosystem doesn't have something
available in a cross-platform sense is really disappointing, imo.

Regards,
Jeff

[Andreas Neumann-7]

Hi all,

Yes, editing and selecting elements would be the main use case for both.
But I think that this is the case for many applications, not just full
blown editors.

Most decent drawing tools also allow to customize the selection mode:
* select all elements that are completely inside a selection rectangle
(.getEnclosureList())
* select all elements that intersect with a selection rectangle
(.getIntersectionList())

You would need it for:
* Full-blown drawing tools/editors
* GIS: e.g. select all polygons where you want to sum up areas,
population; calculate different things based on the selection, etc.
* Games
* multimedia-apps: think about a photo light-room board where you have a
couple of photos floating around - you want to grab some photos and
apply some effects on them, or tag them, or remove them ...
* Technical Drawings: select elements and get a part-list
* flow charts and mind maps where you want to drag around groups of elements

Here is a nice flash-based mapping-app:
http://www.emc3dev.com/usa_demo/carto.php?lang=en - in the toolbar on
the top you may find two different selection tools: polygonal and
circular selection. After the selection you get a list with all the
counties and associated data of elements that intersected.

----------------

More comments inline:
> I'm curious what use cases people see for functionality along the lines of
> getIntersectionList/getEnclosureList. In any use case you may have:
>
>  * Would you want to get elements that are "below" a given element
>    in rendering order, or would you rather want elements that
>    are descendants of a given element.
>  
I think it would be very useful if the user can specify the parent node
in the DOM where the search algorithm should start with and traverse
down the DOM tree. In some cases it could be a group node (representing
a layer in a drawing app or GIS app), or it could be the root node (the
whole document).

I think the author of a drawing or GIS app would want to start the
search at a given group/parent node (such as the drawing canvas or the
map root)

I think the resulting node list should be in the order the elements
appear in the DOM. The question is then if you only get shapes or also
group/container nodes? Did you discuss that?

>  * If you want the elements that are "below", should 'z-index' be
>    taken into account in deciding what's "below" an element, or
>    do you really just want "comes before in document order"?
>  
hm - not so sure if I need the "what's" below. Would you use that mode,
Jeff?

>  * Would you really want 'pointer-events' to be taken into account?
>  
I think there should be a parameter in the two methods that specify the
behavior. I think there use-cases for both modes - taking them into
account or not.

>  * Would you want 'visibility' or 'display' to be taken into account?
>  
display should be taken into account - definitely. If you switch of a
layer in a drawing app or GIS, you don't want invisible elements to get
selected. Besides, display means "not part of the rendering tree", anyway?

>  * How about opacity, markers, masking or filters?
>  
not so sure. I would say no. I am mostly interested in the "raw"
geometry, not the decorations.

>  * Would you want elements that are fully inside the rectangle
>    that you specify?
>  
yes - with getEnclosureList()

>  * Would you want elements that have overlap with the rectangle
>    that you specify?
>  
yes - with getIntersectionList()

>  * Would you only want elements that intersect with the *edges*
>    of the rectangle that you specify (i.e. not elements that are
>    fully inside)?
>  
For getIntersectionList() I would want both: elements that are inside
the selection rectangle and elements that intersect. Both cases are
actually intersection. Inside is also an intersection of the two areas
(the shapes and the selection rectangle)

>  * Would bbox intersection checking be sufficient?
>  
Not for all cases. I think there should be a parameter: bounding box
checks (faster) and checks on full geometries (slower, but more accurate)

I hope that the use cases above are strong enough to be properly
specified by the SVG WG and picked up by the implementors.

Thank you for discussing and working on this! I think there would be a
lot of applications that would benefit from proper and compatible
.getIntersectionList() and .getEnclosureList()


Andreas