I am creating a pixel art editor for Android, and as for all pixel art editors, a paint bucket (fill tool) is a must need.
Before going on my venture to implement a paint bucket tool, I did some research on flood fill algorithms online.
I stumbled across the following video which explained how to implement an iterative flood fill algorithm in your code. The code used in the video was JavaScript, but I was easily able to convert the code from the video to Kotlin:
https://www.youtube.com/watch?v=5Bochyn8MMI&t=72s&ab_channel=crayoncode
Here is an excerpt of the JavaScript code from the video:
Converted code:
(Try and ignore the logging if possible.)
Tools.FILL_TOOL -> {
val seedColor = instance.rectangles[rectTapped]?.color ?: Color.WHITE
val queue = LinkedList<XYPosition>()
queue.offer(MathExtensions.convertIndexToXYPosition(rectangleData.indexOf(rectTapped), instance.spanCount.toInt()))
val selectedColor = getSelectedColor()
while (queue.isNotEmpty() && seedColor != selectedColor) { // While the queue is not empty the code below will run
val current = queue.poll()
val color = instance.rectangles.toList()[convertXYDataToIndex(instance, current)].second?.color ?: Color.WHITE
if (color != seedColor) {
continue
}
instance.extraCanvas.apply {
instance.rectangles[rectangleData[convertXYDataToIndex(instance, current)]] = defaultRectPaint // Colors in pixel with defaultRectPaint
drawRect(rectangleData[convertXYDataToIndex(instance, current)], defaultRectPaint)
for (index in expandToNeighborsWithMap(instance, current)) {
val candidate = MathExtensions.convertIndexToXYPosition(index, instance.spanCount.toInt())
queue.offer(candidate)
}
}
}
}
Now, I want to address two major issues I'm having with the code of mine:
- Performance
- Flooding glitch
Performance
A flood fill needs to be very fast and shouldn't take less than a second, the problem is, say I have a canvas of size 50 x 50, and I decide to fill in the whole canvas, it can take up to 8 seconds or more.
Here is some data I've compiled for the time it's taken to fill in a whole canvas given the spanCount value:
| spanCount |
approx time taken in seconds to fill whole canvas |
| 10 |
<1 seconds |
| 20 |
~2 seconds |
| 40 |
~6 seconds |
| 60 |
~15 seconds |
| 100 |
~115 seconds |
The conclusion from the data is that the flood fill algorithm is unusually slow.
To find out why, I decided to test out which parts of the code are taking the most time to compile. I came to the conclusion that the expandToNeighbors function is taking the most time out of all the other tasks:
Here is an excerpt of the expandToNeighbors function:
fun expandToNeighbors(instance: MyCanvasView, from: XYPosition): List<Int> {
var asIndex1 = from.x
var asIndex2 = from.x
var asIndex3 = from.y
var asIndex4 = from.y
if (from.x > 1) {
asIndex1 = xyPositionData!!.indexOf(XYPosition(from.x - 1, from.y))
}
if (from.x < instance.spanCount) {
asIndex2 = xyPositionData!!.indexOf(XYPosition(from.x + 1, from.y))
}
if (from.y > 1) {
asIndex3 = xyPositionData!!.indexOf(XYPosition(from.x, from.y - 1))
}
if (from.y < instance.spanCount) {
asIndex4 = xyPositionData!!.indexOf(XYPosition(from.x, from.y + 1))
}
return listOf(asIndex1, asIndex2, asIndex3, asIndex4)
}
To understand the use of the expandToNeighbors function, I would recommend watching the video that I linked above.
(The if statements are there to make sure you won't get an IndexOutOfBoundsException if you try and expand from the edge of the canvas.)
This function will return the index of the north, south, west, and east pixels from the xyPositionData list which contains XYPosition objects.
(The black pixel is the from parameter.)
The xyPositionData list is initialized once in the convertXYDataToIndex function, here:
var xyPositionData: List<XYPosition>? = null
var rectangleData: List<RectF>? = null
fun convertXYDataToIndex(instance: MyCanvasView, from: XYPosition): Int {
if (rectangleData == null) {
rectangleData = instance.rectangles.keys.toList()
}
if (xyPositionData == null) {
xyPositionData = MathExtensions.convertListOfSizeNToListOfXYPosition(
rectangleData!!.size,
instance.spanCount.toInt()
)
}
return xyPositionData!!.indexOf(from)
}
So, the code works fine but the expandToNeighbors function is very slow, and it is the main reason why the flood fill algorithm is taking a long time. My colleague suggested that indexOf may be slowing everything down, and that I should probably switch to a Map-based implementation with a key being XYPosition and a value being Int representing the index, so I replaced it with the following:
fun expandToNeighborsWithMap(instance: MyCanvasView, from: XYPosition): List<Int> {
var asIndex1 = from.x
var asIndex2 = from.x
var asIndex3 = from.y
var asIndex4 = from.y
if (from.x > 1) {
asIndex1 = rectangleDataMap!![XYPosition(from.x - 1, from.y)]!!
}
if (from.x < instance.spanCount) {
asIndex2 = rectangleDataMap!![XYPosition(from.x + 1, from.y)]!!
}
if (from.y > 1) {
asIndex3 = rectangleDataMap!![XYPosition(from.x, from.y - 1)]!!
}
if (from.y < instance.spanCount) {
asIndex4 = rectangleDataMap!![XYPosition(from.x, from.y + 1)]!!
}
return listOf(asIndex1, asIndex2, asIndex3, asIndex4)
}
It functions the same way, only this time it uses a Map which is initialized here:
var xyPositionData: List<XYPosition>? = null
var rectangleData: List<RectF>? = null
var rectangleDataMap: Map<XYPosition, Int>? = null
fun convertXYDataToIndex(instance: MyCanvasView, from: XYPosition): Int {
if (rectangleData == null) {
rectangleData = instance.rectangles.keys.toList()
}
if (xyPositionData == null) {
xyPositionData = MathExtensions.convertListOfSizeNToListOfXYPosition(
rectangleData!!.size,
instance.spanCount.toInt()
)
}
if (rectangleDataMap == null) {
rectangleDataMap = MathExtensions.convertListToMap(
rectangleData!!.size,
instance.spanCount.toInt()
)
}
return xyPositionData!!.indexOf(from)
}
Converting the code to use a map increased the speed by around 20%, although the algorithm is still slow.
After spending a couple of days trying to make the algorithm work faster, I'm out of ideas and I'm unsure why the expandToNeighbors function is taking a long time. Any help would be appreciated to fix this issue.
Apologies if I didn't do a good enough job of explaining the exact issue, but I have tried my best. Implementation-wise it is quite messy unfortunately because of the whole list index to XYPosition conversions, but at least it works - the only problem is the performance.
Flooding glitch
This issue is quite strange, say I draw a line like the following on my pixel grid:
Whenever I try to fill in area A it will flood to area B for an unknown reason:
On the other hand, filling in area B won't make it flood into area A:
For some reason, if I draw a perfect diagonal line like so and I try to fill in area A or B it works perfectly:
Filling in the following area will also work fine:
For some reason if the line is meeting at both edges of the screen it works fine, but if they don't, it won't fill it in properly.
Tried to debug this for some time, also couldn't figure out why this is happening. Very strange - I'm not sure if this is a common issue or not. It could be an issue with the expandToNeighbors function, although I haven't debugged this enough to be sure?
So I have two major problems, if anyone can try and find a solution for them, it would be great because I have tried to myself without much luck.
I've actually pushed the fill tool to GitHub as a KIOL (Known Issue or Limitation), so the user can use the fill tool if they want, but they need to be aware of the limitations/issues. This is so anyone who wants to help me fix this can have a look at my code and reproduce the bugs.
Link to repository:
https://github.com/realtomjoney/PyxlMoose
Edit after bounty
Yeah, I understand that this question is extremely difficult to answer and will require a lot of thinking. I've tried myself to fix these issues but haven't had much success, so I'm offering 50 reputation for anyone who can assist.
I would recommend you clone PyxlMoose and reproduce the errors, then work from there. Relying on the code snippets isn't enough.
from
Android: Iterative queue-based flood fill algorithm 'expandToNeighborsWithMap()' function is unusually slow
