On Sat Feb 10 13:59:41 2024 +0000, Jinoh Kang wrote:
checking whether a point is within a polygon should also not be too
difficult to implement in an efficient way A path region is not always a polygon.[^p] For example, it may have a bézier curve along the path.
a point is within a polygon should also not be too difficult to
implement in an efficient way Right, this is useful for implementing GdipIsVisibleRegionPoint *specifically*, but that's not the point of this MR.[^1] This patchset intends to introduce a generic bounding box calculation mechanism so that plenty of other HRgn-computing functions can benefit in the future. GdipIsVisibleRegionPoint is merely an example.[^e] [^p]: Yes, technically everything is a polygon after rasterization, but this is not very useful here. [^1]: From paragraph 3-4 of the MR description: "The rasterization should be limited to a specific integer rectangle, which in the case of GdipIsVisibleRegionPoint can be 1x1 pixel. We should then be able to eliminate all internal uses of GdipGetRegionHRgn, except when we have to return an HRGN to the application. This would also be useful for implementing anti-aliasing, as we could keep the memory usage down by only rasterizing the part we need for each scanline at a time." [^e]: For 1x1 case only.
I think my reasoning for not precomputing bounding boxes was that in practice we'll likely be transforming the regions a lot, which will require recomputing them, so it's not clear to me whether precomputing would really be more efficient or not.
The case where we fall down now in particular (as I mentioned in the MR description) is working with a very large path region that doesn't have perfectly vertical edges. This gets converted into many rectangles with small height that are unnecessary when point-testing or rendering to e.g. a window with finite size. We could do this more efficiently by only handling the points that will be in the final output.
But I am reconsidering now whether it's worth doing a bounding box calculation separately from the conversion to a list of rectangles. Maybe the way to do this is to reimplement GdipGetRegionScans first, and do it in a way that tracks intersections as it goes. Then GdipIsVisibleRegionPoint can be implemented by intersecting a 1x1 rectangle with the region I want to point-test and converting that to scans. It would be simpler. The drawbacks of that approach are: * It's sensitive to the order in which regions are combined. A large region intersected with a small one will be slower than a small region intersected with a large one. We can try to set up our internal usage so that single points, Graphics bounding boxes, and Graphics clipping regions are first, but in some cases it won't be as efficient with large curvy regions as it could be. * It'll use more memory. For paths I'll need 1 byte for each pixel in the output to track where the polygon's edges are, and I'll need memory for every rectangle in the result. It won't be possible to "stream" the result to the function using it, which if it's a rendering function will be building one scanline at a time. * Cases involving xor, exclude, or complement with multiple infinities won't be handled as efficiently as they could be. It's unlikely that those will show up in practice though.