A classic KMeans clustering thingy … but working on 2 Lists: the first is the mesh Vertices. The second is the vertices colors as Point3d (in a RGB cube 256x256x256 where x coord is the color.R, y is the color.G and z is the color.B):
So let’s call the vertices List vList and the other vCList (C for color). Then you need a KMeans clustering on the vCList … PLUS … for each point sampled in a cluster you sample in another cluster the “equivalent” point from vList.
Since at the end you need to cluster faces and not vertices is imperative to use MTV indexing and get the MV indexing (used in colors, normals etc etc: that’s nerve braking and rather confusing) via the Method shown above. Why? because a conn Tree that contains the clustered vertices indices (MTV indexing) is very handy for the final phase (make the faces). Remember that a FV conn tree is using MTV indexing.
In fact you can greatly simplify the whole workflow if you use a face center and the “equivalent” centerColorPoint (so to speak) as the (vC1+vC2+vC3)/3.0 etc etc.
All in all : either you get the colors (per vertex in MTV indexing) “as points” and you cluster them and then you extract the related faces using MV connectivity … OR … you work on a per face basis : i.e. get the “average” of the face vertices (also MTV indexing) colors (In both ways you’ll need an indexing [MTV>MV] mapping strategy since colors are using MV indexing).
The latter approach deals with more stuff (vertices are fewer than faces … even by half) but you gain speed since you don’t have to ask any question after the clustering phase.
That said there’s a simpler (and maybe less cryptic) to KMeans clustering approach with regard your colors “as points”: assume that x, y, z are 255 in the attached … then spot how you can classify (i.e. cluster) any XYZ value (0 to 255 since we are talking colors “as points”) in a given subbox (without any Box/Pt inclusion test [hence the speed in the real thing: 5 - 7 milliseconds max for the test posted above]) > clusters done.
Well … anything related with pro level stuff (graphs, graph connectivity, clusters, short paths, island detection, ball pivot, concave hulls, closet cirquits, nested instances, offset polycurves,tensile membranes, trusses, // stuff … the list is rather big) is strictly internal.
For the clustering thingy:
Imagine a vertex with color RGB (i.e. values 0-255). Then we use that as … er … hmm … a Point3d that (with the rest) can being clustered according their Euclidean distance - or classified in a subBox as in the “concept” C# provited above: If you classify indices in parallel as well … you have the actual vertices since colors and vertices match (in MV indexing - never forget that). On the other hand … if you want to deal with faces instead … then you can use the mesh face centers indexing (same as MF) and “map” the adjacent colors (ex colors … now these RGB points) accordingly to an imaginary “center” point from the ex vertices and now RGB points (LOL+LOL). For instance and for a tri face the (p1+p2+p3)/3.0 is the center. The only freaky thing is that the coordinates are the RGB values of the equivalent vertices (LOL). The logic for that is captured in the C# above. For all that Greek stuff you need to fully understand what mesh connectivity is.
But all in all … using the box classification as explained in the latest reply of mine (plus the screen shots) is more or less “the same” thing (almost … but who’s gonna notice the difference? you tell me). That is the reason for posting the related demo … just get the gist of what it does, forget KMeans … and off you go.
A hint: imagine that you have a line 255 units long. Within a given (var) resolution … what is the position of the pink sphere (at Point3d(D,0,0)? That is the logic (in 3D) of the C# posted and the “clustering” of the RGB “points” (ex vertex colors or face centers) in subBoxes instead of the 1D thingy pictured here.