[webkit-dev] Table hit testing

[David Hyatt]

You can't binary search if there are overflowing cells in any section.  You have to go in order (from last to first) in that case, since you may hit test something.

In general you won't find binary searches, etc. in most hit testing code because of overflow concerns.

http://www.zazzle.com/css_is_awesome_mug-168716435071981928

I strongly recommend not writing code that deviates from what the paint methods do.  In general the nodeAtPoint version of a function should be just like the paint version of a function, just from last to first rather than first to last.

Any time hit testing and painting deviate, you have a problem, since the painting stack order and the hit testing stack order obviously need to agree.

Basically I'd expect a first patch to synchronize the two methods (paint and nodeAtPoint), and then if you want to optimize further, I'd expect to see optimizations to both painting and hit testing made together.

dave
(hyatt at apple.com)

On May 20, 2010, at 10:58 AM, Fady Samuel wrote:

> So I have an implementation that seems to be working (still testing edge cases). I found that m_grid, in RenderTableSection, is a Vector<RowStruct> and each RowStruct contains a row which knows about the columns of that row.
> 
> Thus this is effectively a dense 2D table of Cells. I use this for hit testing. By the time nodeAtPoint has been called we've already computed the dimensions and location of the rows and cells and all RenderTableCells are reachable through m_grid. Thus, I do a binary search on the rows, comparing their y position with the mouse's y pos to find which row to consider. 
> 
> Then once a row has been picked, I do a binsearch on the columns within that row, looking at the x positions, and then I pass the event to the nearest cell. Of course, the actual mouse position may fall just outside of a cell (it may lie over spacing between cells for example) but in that case the RenderTableCell node would simply ignore the event. 
> 
> I'm still doing testing (regression + perf). For cells with rowspan > 1, it seems that the a pointer to the Cell node is placed in each row its associated with in m_grid. For cells with colspan > 1, it seems that only the first column that the cell occupies is not NULL...so I just linear scan back to the first non NULL position if I encounter that. I suppose I could optimize that further by filling all of m_grid appropriately and changing code elsewhere to accommodate. 
> 
> CSS transformations on tables seem to all automagically work, it seems all the coordinate system transformation code all happens before we reach RenderTableSection::nodeAtPoint.
> 
> Does it sound like I'm missing anything important? I've just started playing with the webkit source a couple of weeks ago, so I may have missed something silly.
> 
> Thanks,
> 
> Fady
> 
> On Tue, May 18, 2010 at 3:03 PM, Fady Samuel <fsamuel at google.com> wrote:
> Ohh I see, I was confused about this line in RenderTable:
> 
> 1138     if (!hasOverflowClip() || overflowClipRect(tx, ty).contains(xPos, yPos)) {
> 
> It seems that the default case is to visit all the children as hasOverflowClip() is false.
> 
> Thanks for the explanation David. 
> 
> I will look into optimizing hit testing to avoid visiting all children. 
> 
> Thanks again,
> 
> Fady
> 
> 
> On Tue, May 18, 2010 at 2:57 PM, David Hyatt <hyatt at apple.com> wrote:
> 
> On May 18, 2010, at 12:52 PM, Fady Samuel wrote:
> > Hi all,
> >
> > I'm looking at table hit testing, and in all the simple test cases I've tried, it seems to show that RenderTable never has the flag m_hasOverflowClip set to true. What this means is that all the table's children are ALWAYS checked on all mouse events. For large tables, or pages with many tables, this sounds awfully taxing on the processor for no good reason.
> >
> > See RenderTable::nodeAtPoint in third_party/WebKit/WebCore/rendering/RenderTable.cpp . It seems "hasOverflowClip()" is always false.
> >
> > Can we not compute a bounding box for the table on layout? Are there any complications here that I should be aware of that resulted in this inefficient solution?
> 
> m_hasOverflowClip is about overflow:auto/scroll/hidden.  The default value for overflow is visible, so that's not going to be set and isn't really relevant to your problem.
> 
> Both RenderTable and RenderTableSection need to have their nodeAtPoint methods patched to be like their paint methods instead.  Both of those methods would get much more efficient if we did that.
> 
> dave
> (hyatt at apple.com)
> 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20100520/18832724/attachment.html>