Implement "paint bucket" style object fill [14]

[techninja]

Using a selected color, a user can click in the void between any overlapping lines or closed paths to create a new filled shape.

• Will need to test various shapes
• Shapes that have breaks/are open to the main griddle will refuse to fill.

[Slimmy82]

2 ways to fill an object. the snake method would give a cleaner more accurate result. once we work out the optimal thickness of the line we can easily fill within the parameters so the lines match up and slightly overlap to seal it in. Anyway just some food for thought

[techninja]

Pancake.. food for thought... :laughing:

Snake is certainly doable, just make the line based on the outside tangent and connect the ends. Will need some real world testing to see which works better.

[Slimmy82]

For sure. It is all about testing!

[techninja]

All this week I've been working hard to find a way to will using the given mathematical boolean operations on paths.. and it seems like they're just not made for non-filled/closed paths.

On the Wikipedia page for flood fill, they actually list the open source vector editor Inkscape as one that does a vector fill. I checked and it does indeed have a vector flood fill, but I believe they're definitely cheating. A flood fill of a circle does not result in a perfectly circular filled path, but.. a slightly lumpy uneven one that still does a fine job of filling it. Reading the documentation on the feature, it's purely a perceptual thing, meaning that it looks at what matches and what doesn't and converts the pixels to a vector when it's done!

If we were to use a similar method, we would get around solving the very complex math required for the boolean method, and we'll get paths that are probably more than adequate for pancake fills, if not perfectly matching the lines.

Of course the work still has to be done to convert what we have to raster, finding the closed area, run a flood fill algorithm on it, convert that to boundary points, reorder those points via distance, then convert that to a shape, then simplify that. Sheesh! And that's not even fully accounting for internal filled path occlusion. Oh well, I have my work cut out for me :)

[techninja]

Ok, looks like it's time! First, the results:

How it works:

I've implemented basically exactly what I mentioned above:

1. On click: a 1bit raster map of all non-transparent pixels is created of the entire working layer. This is limited to the actual layer contents, so there's less work to be done the smaller the line area is (and conversely, there's more work to be done for an entirely filled canvas)
2. Once the matrix is converted for area map -> raster x/y coordinate, we can run a flood fill algorithm based around that coordinate, on the raster map from step 1. I happened to find a good third party n-dimensional fill that has built in support for boundary detection!
3. With that awesome boundary detection, we simply save each pixel mapped point into a big array of boundary locations. This is totally out of order of course.
4. During flood fill, if the fill boundary reaches the edge of the layer boundary, we've reached the edge and this means the fill shape is open, therefore the entire fill is cancelled.
5. If we know we're good, we take our mixed up boundary points and using the "first" point as a start, walk through every other point and match it to the next closest one. We know this will generally work because the boundary paths are regular and can only be a maximum of 2pixel diagonal, or relative 5units away from each other.
6. If there are any boundary points farther than this away from each other in the next matching iteration, we know that it must be an island! (An island is any closed path within another path). This is then added to a secondary N group.
7. All final ordered paths are added to a compound path (internal islands are by default removed from having fill). As this is super blocky (having originated from a relatively low resolution pixel map), we then run the simplify algorithm on it, removing ~60-70% of the excess nodes. Higher values of simplification were attempted, but commonly change the shape too much.
8. At this point we're basically complete. The compound path is marked as being a fill, and is passed on to the higher level function to be assigned a color. This allows the function to simply pass already filled shapes directly to have their colors reassigned if clicked again.

Pros/Cons:

• It's reasonably fast. With only noticeable lag/slowdowns on very large fills
• It's a little wiggly. Near the edges the path does not perfectly match. This really doesn't look all that bad and almost reminds me of pancake batter. As I've said before, it very likely more than good enough.
• It doesn't matter how complex the shapes are. This is a HUGE plus as it means basically any crazy shape or path as long as it looks visually correct, is going to be able to be filled in a way that makes sense.
• Where you click matters. Because I'm using the "first" point of the boundary list, that's based on the flood fill for a given area. The same shape will always yield the same boundary point list, but in a different order. This apparently results in triangle cutouts for certain shapes, given certain starting points. I have not worked out exactly what these are or the best way to reproduce. Testing is likely needed, and I'll have to work out a better starting point.

Areas of improvement:

• The wiggly path bits can technically have their points snap to the closest path point to them... though that's possibly an extra two days of work for likely very little gain. And this may cause big issues with single path islands collapsing :/
• Only if the boundary point order issue triangle is confirmed a recurring issue, I can attempt to fix.

[techninja]

I did a little digging and found a few more instances of the triangle crossover, turns out it's partially the island grouping threshold to blame, so I doubled it and it seems to be quite happy. I think I'm going to leave this issue be, and the next build with this will be to the m4 wrap issue.