I'm creating a game that takes an image represented by a 16x16 array of html color codes and creates a 3D object made out of rectangular cuboids. Like taking the Paint program on Windows and extruding your image into the Z axis.

// An image containing 16 columns and 16 rows of hexcodes for 256 total hexcodes
[ [ "#FF5733", "#FF5733", "#FF5733", "#FF5733", ... ], [ "#FF5733", ... ] ]

How can I create the smallest possible array of rectangles that would cover the image without creating overlapping rectangles?

// Rectangles that represent the 2D image, a blank image would have only one rectangle
rectangles = [{
 color = "#FF5733",
 x = 5,
 y = 3,
 width = 5,
 height = 5,
}, ... ] 

My first attempt at a solution --- every single pixel in the 16x16 image getting a cube (256 cubes) --- created huge load times (30 seconds) for loading 500x 3D images.

One improvement I was able to make was "reading on" past the current color in the row until I hit a different color or the end of the row in order to create long rectangular cuboids across the row. This improvement cut the cuboid count in half. Extending this trick across the y axis has proven difficult. Overlapping rectangles look really ugly.

My understanding is that this problem is NP Hard. I'd be happy if we had a solution that had fewer rectangles even if its not provably the fewest rectangles.

The Wiki Article on the problem does not give any concrete suggestions.