Selection.cpp: SimplifySelection() needs to be improved

[dsizzle]

Selection::SimplifySelection() is a method that deconstructs a pixel selection into polygons but currently it doesn't do a great job. Even for a simple rectangular selection, it generates a huge number of points. The lowest I saw in quick testing was 500 and I've seen multiple thousands. A rectangular selection should ideally be a 4-point polygon!

Look into raster->vector conversion algorithms, or add a way to deduplicate/reduce (Douglas-Peucker?) the points in selection.

[humdingerb]

This is probably off-topic for this ticket, but would it be at all possible to keep selections as vector? That is, always have handles around the rect/ellipse like in the crop manipulator. Then you could easily adjust a selection pixel-precise, resize, rotate.

I suppose it may not be possible for the other selection tools. Or maybe a sort of bounding box could work.

[dsizzle]

Yes, I don’t think this is a good idea overall. However, I do think we need the ability to transform selections. #156 is a prerequisite for that.

[dsizzle]

This might actually be the cause of #286.

[dsizzle]

I’m working on “Moore’s Neighborhood” contour tracing - seems to be well known and at least my first attempt feels a lot easier to understand vs. the existing method. Not sure about performance.

[humdingerb]

I’m working on “Moore’s Neighborhood”

Careful. Make sure to stay off Moore's Law(n)... /me ducks

[dsizzle]

After a bunch of work I decided SimplifySelection actually works really well. I refactored a bit in #366 but still think there should be a way to reduce the number of points generated - but I don't think it needs a different algorithm now that #286 is solved.

[dsizzle]

I have working code that does this simplification, but I can't decide if it's actually worth anything. Whenever a pixel is tested for inclusion in a selection, we just check the selection map pixels directly, which is likely always faster than a polygon check. Therefore I don't know if having a minimal number of points (like 4 points for a rectangular selection) really matters at all. It may provide some performance benefits in some operations but might not be worth it overall... still thinking about this one...

[humdingerb]

Can't help you there...

[dsizzle]

Ok, I have been looking into this because I think this same code can be used to generate UI elements for any current and future brushes (i.e. a representation of the brush when painting) to solve #128. I originally thought the current code was good enough as stated above

I don't think it needs a different algorithm now that https://github.com/HaikuArchives/ArtPaint/issues/286 is solved.

However, it is really pretty bad in certain situations. For example:

• create an elliptical selection; it's fine except for those little lines at the top/bottom/left/right

• but then rotate the selection and fill it and it starts to get a bit rough:

• if you add to the selection and rotate it more, it starts to become quite a hairy mess:

there are other issues too - a 3 x 3 ellipse selection is just a big cross:

I did get the aforementioned Moore's neighborhood code working and it's much better but it's a polygonal representation so it doesn't follow the pixel outlines exactly:

current:

new:

but the selections don't get hairy, and at small sizes it's better. Here's a 3 x 3 ellipse with the new algorithm:

Can't decide if the 'exact pixel' representation is necessary. I tried to push this new algorithm to work that way but it started to have some of the hairy-ness problems like the current algorithm.

[humdingerb]

Dunno either... Hairy selections are bad, but elliptic selections becoming more angular the smaller they get isn't ideal either. Difficult choice... :)

[dsizzle]

Ok, I think I have the "exact pixel" representations working; coming soon to a Pull Request near you (I need to clean up the code and test more).

However, in the investigation I realized that this isn't the reason the rotated selections get hairy; selection rotation is incorrect - filed #525

[humdingerb]

Perseverance! :)

[dsizzle]

It might take more perseverance yet. It works but the selection outline is like a half pixel wider than it needs to be in every direction, but I tried to tighten it in and it was giving me headaches.

[humdingerb]

Frustrating, but I have full confidence in you. Half a pixel isn't much... :)

[dsizzle]

Half a pixel isn't much... :)

This is coming from a person who keeps a magnifying glass handy at all times... :laughing:

[dsizzle]

I solved it by scaling down the polygon slightly at the end and it seems to actually work very well. I filed a PR #526 so it can be tested more but I think it seems to be much better than trunk and I haven't been able to break it yet - but I'm not the best at breaking things

[humdingerb]

Luckily I have a sledge hammer on the other side of my magnifying glass to give things a wack...

[dsizzle]

Closing as fixed by #526