[Webkit-unassigned] [Bug 72294] Add occludes() test to Region

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=72294





--- Comment #12 from Dana Jansens <danakj at chromium.org>  2011-11-14 16:59:50 PST ---
(In reply to comment #10)
> (In reply to comment #9)
> > (In reply to comment #8)
> > > (In reply to comment #7)
> > > > misclick..
> > > > 
> > > > "... to compute."
> > > 
> > > That could be easily fixed by making the segment and span vectors have an inline capacity - then it'd just be stack allocation:
> > > 
> > > 
> > >         // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
> > >         Vector<int> m_segments;
> > >         Vector<Span> m_spans;
> > 
> > From reading the code I don't see what you are suggesting. But please correct me where I am wrong.. If a Vector is given a size, then it will call VectorBufferBase::allocateBuffer() which calls fastMalloc() which calls malloc(). Where is there a stack allocation?
> 
> You can give Vector an inline size, like so:
> 
> Vector<int, 16> m_segments;
> 
> and unless the size of the vector is greater than 16 elements, everything will be allocated as part of the Vector (which is part of the Region).

Okay, I see the inlineBuffer.  I have to admit I don't like increasing the size of all Region objects, when walking the segments is sufficient.  I expect Regions have very different use cases hence the lack of this magic inline size value. It's something we can consider, but see below regarding operator==.

> > 
> > Regarding point 1), I see nothing in Region::Shape::shapeOperation() that guarantees a single rect output for the intersection in the occludes() == true case. It simply adds segments as it goes along, there is nothing more global to consider pruning/combining segments/spans there. So, as I see it, the same test done in occludes() would need to be done on the result of the intersection() - the only change would be knowing that all segments intersect the query rect.
> 
> Region::Shape::canCoalesce has the logic for coalescing segments - but I think there's an even simpler way to do this.
> 
> Also, instead of occludes - let's call the function 'contains', because that's a more logical name. I think contains can be implemented like this:
>
> bool Region::contains(const Region& region)
> {
>     Region result = intersect(*this, region);
> 
>     return result == region;

Region::Shape::canCoalesce() enables some simple compression, to merge adjacent spans that have exactly the same segments.  There is no reason to believe that this will be the output of an intersection of an arbitrary region with a rectangle, though. In the contains() == true case, it will be a set of spans, where for each span, the union of segments within start at the query rect's left edge and end at its right edge. The same walk of the intersection must be done.

I also definitely don't want to make this more complex than it needs to be, but:

1) I don't see the ability to do this operator== comparison at the moment.
2) While I can implement the current contains() as operator==(), it will be slower than just doing a single walk (at least two, with possible mallocs/frees).  3) The operator==() method will be /more/ complex than the current contains() code.  It has to do a symmetric comparison rather than just testing one covering the other.

> }
> 
> Which is much cleaner and reuses the already existing region operations. The region code is pretty complex as-is; let's not add more complexity to it if we can avoid it.

The Region::Shape code is somewhat complex but well structured to match its citation cleanly, so I put this function in the Region class instead to separate it from the Region::Shape implementation.

The walk for Region::contains() is quite similar to Region::rects(), but simply looks for gaps between segments or spans that intersect with the query rectangle.  I think it can be a little more clear, and I had some unneeded variables left over from a previous implementation, so I will resubmit it.

>From what I see, doing operator== will make for both a more complex and costly solution, will it not?

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.