In a mesh made of cubes with different colors, how do I find the matching clusters?

Question

Defining cluster

Any group of cubes of the same color, touching face planes, not their corners.

A cluster would form a solid geometric shape.

To help visualize the problem

Let's assume each one of these Legos is 1x1 units large.

In a simplified code example - let's look at a 2x2x2 mesh made of 1x1x1 cubes:

var mesh = [ 

  // First layer   ( x, y, z )
  new THREE.Vector3( 0, 0, 0 ),
  new THREE.Vector3( 0, 0, 1 ),
  new THREE.Vector3( 1, 0, 0 ),
  new THREE.Vector3( 1, 0, 1 )

  //Second layer   ( x, y, z )
  new THREE.Vector3( 0, 1, 0 ),
  new THREE.Vector3( 0, 1, 1 ),
  new THREE.Vector3( 1, 1, 0 ),
  new THREE.Vector3( 1, 1, 1 )
];

Each cube in the mesh has a color:

//Indexes of mesh array sorted by color
var colors = {
  red: [0, 1, 4, 6],
  green: [2, 3, 5, 7]
}

Answer 1

This can be solved with flood fill. The Wikipedia page is instructive for two dimensions:

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

You can extend this to three dimensions by observing that two cells are adjacent if their distance is 1, or more simply if they differ by one in exactly one dimension, so you can iterate over all six neighbors instead of the four for two dimensions.