Discretise mesh but keep valid groups/topology

I have one value per vertex and based on these I’d like to split the mesh into n valid groups.There can be multiple non-connected meshes within a group.

As you can see highlighted with a black pen in the image below sometimes I get some invalid areas which I need to mitigate.

Ideally if the vertex value is high then I’d like to expand and make it valid, conversely if it’s low let the neighbors take over.

Can someone point me in the right direction?

My initial assumption is a group would be valid if:

  • All faces are connected by at least two edges
  • the total area of an “island” is greater than a threshold (two faces would be too small for an entity)

C# or Python solutions would be much appreciated!

PS: this algorithm will scale to 3D tetrahedron meshes to export watertight poly meshes.

test_two.gh (17.7 KB)

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.

I wonder if switching to the dual could help you here.
I once did this to resolve non manifold boundary problems for some scalar field stuff

(You can still potentially get some isolated faces, but those might be easier to fix than the non manifold vertices)


Thanks Peter, could you clarify the acronyms? I’m not familiar with MTV, MV and FV.

Aside from that your explanation is clear. Regarding your last statement. Is this because it allows us to consider each face as a single entity as opposed to its vertices?

Fascinating stuff Daniel, I’ll have to take some time and check the files you shared. I’ve just started exploring the level set for topology optimisation.

MTV = MeshTopologyVertex
MV = MeshVertex
FV = FaceVertex (for connectivity trees).

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.

Box_AsDomainForXYZValues_V1.gh (118.7 KB)

Here’s the above demo as implemented in the real thing using vertices (spot the indexing tree):

4 milliseconds more are required using faces, centers etc etc:

Thanks peter.

I’m looking at the K-means implementation in the Accord library but it’s not clear how I would sort the faces alongside the (averaged) face colour?

May I ask which implementation of Kmeans you’re using and if you’re happy to share it?


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.

Let’s say something remotely close to this: