Image manipulation too slow

[QushyQushy]

Godot version

3.5

System information

Apline Linux

Issue description

I am making a Jigsaw Puzzle and I have 3 difficulties. Each difficulty uses an encoded mask to break a random image into pieces. So for the first piece the mask has R=1,G=1,B=1,A=255, for the second piece it has R=2,G=2,B=2,A=255 and so on an so forth.
I am using the following code to break the image into pieces:

        var mask = Image.new();
	mask = $Viewport.get_texture().get_data();
	mask.flip_x();
	mask.lock();
	
	var pieceImage = Image.new();
	pieceImage = $"/root/GobalVars".selectedImage.get_data();
	pieceImage.resize(460,460);
	pieceImage.lock();
	
	for i in range (pieceImage.get_width()):
		for j in range (pieceImage.get_height()):
			var rgba255 = mask.get_pixel(i, j) * 255;
			var r = floor (rgba255.r);
			if (r > 0):
				if (rgba255.a == 255 && rgba255.g == rgba255.r && rgba255.b == rgba255.r):
					pieces[r-1].set_pixel(i,j, pieceImage.get_pixel(i,j));
					
					$"/root/GobalVars".pieces[r-1].minX = min ($"/root/GobalVars".pieces[r-1].minX, i);

					$"/root/GobalVars".pieces[r-1].maxX = max ($"/root/GobalVars".pieces[r-1].maxX, i);

					$"/root/GobalVars".pieces[r-1].minY = min ($"/root/GobalVars".pieces[r-1].minY, j);

					$"/root/GobalVars".pieces[r-1].maxY = max ($"/root/GobalVars".pieces[r-1].maxY, j);
	
	for i in range (len($"/root/GobalVars".pieces)):
		var pieceTexture = ImageTexture.new();
		pieceTexture.create_from_image(pieces[i]);
		$"/root/GobalVars".pieces[i].texture = pieceTexture;
		$"/root/GobalVars".pieces[i].position = Vector2 (570, 220) + Vector2 ($"/root/GobalVars".pieces[i].minX + ($"/root/GobalVars".pieces[i].maxX - $"/root/GobalVars".pieces[i].minX) /2, $"/root/GobalVars".pieces[i].minY + ($"/root/GobalVars".pieces[i].maxY - $"/root/GobalVars".pieces[i].minY) /2);
		$"/root/GobalVars".pieces[i].initialPosition = $"/root/GobalVars".pieces[i].position;
		$"/root/GobalVars".pieces[i].region_rect = Rect2($"/root/GobalVars".pieces[i].minX, $"/root/GobalVars".pieces[i].minY, $"/root/GobalVars".pieces[i].maxX - $"/root/GobalVars".pieces[i].minX, $"/root/GobalVars".pieces[i].maxY - $"/root/GobalVars".pieces[i].minY);
		pieces[i].unlock();
		yield(get_tree().create_timer(0.05), "timeout");
		var r = floor (rand_range(0,len(randomPuzzlePositions)));
		$"/root/GobalVars".pieces[i].randomPosition = Vector2 (randomPuzzlePositions[r][0], randomPuzzlePositions[r][1]);
		randomPuzzlePositions.erase(randomPuzzlePositions[r]);
		$"/root/GobalVars".pieces[i].moveToRandomPosition();
	
	mask.unlock();
	pieceImage.unlock();
	yield(get_tree().create_timer(0.05), "timeout");
	mask.queue_free();
	pieceImage.queue_free();

The code works just fine, the problem is that on a Tablet on Chrome it takes about 20 seconds for Godot to do the calculation. I have made the same game in Construct with Javascript and the pieces were made instantaneously (but the game didn't work on all Tablets so that's why we're moving to Godot).

Any advice that could help make this faster would be much appreciated, otherwise I think the Godot devs should look into this as it may be a hindrance for some projects.

Steps to reproduce

Just try to manipulate a lot of pixels in WebGL.

Minimal reproduction project

Minimal reproduction project here,

[Calinou]

@QushyQushy Please upload a minimal reproduction project to make this easier to troubleshoot. We can't do anything without one, as the code sample you provided is not a standalone project.

Also, which tablet model did you test this on? Is performance better on desktop?

[aaronfranke]

There's some low hanging fruit to improve the performance of your code.

$"/root/GobalVars"

GDScript $ statements are not cached, so it gets the node every time. You can use onready var to cache them. Also, you misspelled Global as Gobal.

You could also skip the multiplication by 255 and just work with Godot's raw color values on the range of 0.0 to 1.0.

[QushyQushy]

@QushyQushy Please upload a minimal reproduction project to make this easier to troubleshoot. We can't do anything without one, as the code sample you provided is not a standalone project.

Also, which tablet model did you test this on? Is performance better on desktop?

Unfortunately I really can't share the project. I will try to make a really minimal one and upload it if I can.

There's some low hanging fruit to improve the performance of your code.

$"/root/GobalVars"

GDScript $ statements are not cached, so it gets the node every time. You can use onready var to cache them. Also, you misspelled Global as Gobal.

You could also skip the multiplication by 255 and just work with Godot's raw color values on the range of 0.0 to 1.0.

I will try to fix the node caching issue. The Gobal is a long standing mispell but doesn't affect the code so I'm not changing ti cause it will take a considerably long time in all the projects we have.
The multiplication needs to be done cause of the encoding of the image. I can't tell the graphic designers to use floats as it will get seriously complicated and I'm afraid it may not even work properly with floats due to precision issues.

[QushyQushy]

PuzzleCalculation.zip

Here is the minimal project. For some reason it won't let me update the original post. If you need anything else let me know. :)
@Calinou

Also, which tablet model did you test this on? Is performance better on desktop?

Any tablet or mobile. I have tried on a HotWav T5 Pro mobile and a Samsung tablet, not sure about the model. Testers also report that on their tablet it's equally slow.

[QushyQushy]

I also uploaded it to my Itch page if you want to test on mobile, just test how long it takes to load, it's about the same time it takes to change scenes in the original game. Here is the HTML build.

[MGilleronFJ]

Any way you could use shaders instead of per-pixel operations in GDScript? Or a different approach? (being limited to 256 pieces with the current code doesnt seem right) I dont understand the code well yet, but to make a jigsaw puzzle I feel there should be a more efficient way to do this without involving that much image manipulation. Perhaps even the way they are rendered in the first place (without having to create individual images for every piece). Is every piece an image covering the entire puzzle with only the piece filtered in it? (if so that's probably a big time sink, and should rather consider processing only an area around the piece, which in turn could mean you dont need to identify them all with colors but only a few local colors). Image pixel manipulation is far from the fastest on earth, but your algorithm very likely can be optimized by an order of magnitude.
I have no time to look in more details right now but I could investigate it later.

[QushyQushy]

Any way you could use shaders instead of per-pixel operations in GDScript? Or a different approach? (being limited to 256 pieces with the current code doesnt seem right) I dont understand the code well yet, but to make a jigsaw puzzle I feel there should be a more efficient way to do this without involving that much image manipulation. Perhaps even the way they are rendered in the first place (without having to create individual images for every piece). Is every piece an image covering the entire puzzle with only the piece filtered in it? (if so that's probably a big time sink, and should rather consider processing only an area around the piece, which in turn could mean you dont need to identify them all with colors but only a few local colors). Image pixel manipulation is far from the fastest on earth, but your algorithm very likely can be optimized by an order of magnitude. I have no time to look in more details right now but I could investigate it later.

Every piece is an image as big as the entire puzzle. I then transfer this Image to an ImageTexture and set a Sprite texture with a specific region to be rendered.
What happens now is that it passes though the whole image one single time and according to the color of the mask on a particular pixel it automatically finds the correct piece Image and transfers the color of the original image to it. I really don't think I can go faster than that.

[MGilleronFJ]

I think you could use a shader then (on my desktop it takes 0.117ms, your device CPU would then be 200 times slower, at this rate you'd need native code dedicated to the task instead of a script language with a high-level Image interface).
Instead of baking an image for every piece, use the same one for each of your sprites. Then you can use a fragment shader on them that filters the pieces by mask color, that will be instant, and it will spare some memory as there is no need to create 36 textures. With a better mask some checks could also be removed, and with a bumpmap it could be given some antialias.

For larger puzzles with hundreds or thousands of pieces, there is probably even a way to render all the pieces with a single draw call, which is nice on mobiles. A lookup texture could be used to tell which piece is present and hide the others (convert piece index into X and Y to read the value, array uniforms arent supported so a texture is the only way).

---

Yet another approach would be to pre-bake mask pieces ahead of running the game (as an asset), and then somehow use blit_rect_mask, but I think shaders could be more scalable.

[Calinou]

@QushyQushy Did you manage to apply one of the solutions outlined above?

[QushyQushy]

@QushyQushy Did you manage to apply one of the solutions outlined above?

No the game i still extremely slow on mobile and it's a problem. I'm waiting for Godot 4.0 to come out to tweak it and export it there in case it works faster.

[Calinou]

No the game i still extremely slow on mobile and it's a problem. I'm waiting for Godot 4.0 to come out to tweak it and export it there in case it works faster.

I'd be surprised if upgrading to 4.0 made your project run any faster on low-end mobile devices. If anything, low-end mobile devices are more likely to struggle on 4.0 projects compared to 3.x (due to higher baseline requirements, such as GLES3 and more RAM).

You will have to find another way to optimize your code. Try pinpointing which line of code is actually causing the slowness by using microbenchmarking as follows:

var begin = Time.get_ticks_usec()
# Do stuff here...
print("Took %d microseconds" % (Time.get_ticks_usec() - begin))

Then export the project and open the browser developer tools to view console output. This requires using a divide-and-conquer approach to perform microbenchmarking on increasingly smaller portions of code, until you can find the line that probably takes much more time than the others.

[Calinou]

Closing, as there is nothing actionable we can do on our end. In the future, please use one of the other community channels for support questions, as this issue tracker is now used for bug reports only.