Can we speed up the clustering for dense enough meshes? #74

Activity

1. akaszynski commented on Aug 15, 2026

   

   akaszynski

   on Aug 15, 2026

   Member

   More actions

   Short answer: subdivide isn't the slow part, so skipping it doesn't buy you speed. It's there for quality, and if your mesh is already dense relative to your target cluster count you can drop it.

   Timings on the cow from that example, fresh copy each run:

   config	input pts	pts per cluster	subdivide	cluster	total
   subdivide(3), cluster(20000)	185,729	9.3	0.09 s	0.21 s	1.75 s
   subdivide(3), cluster(2000)	185,729	92.9	0.08 s	0.14 s	0.44 s
   subdivide(2), cluster(2000)	46,433	23.2	0.02 s	0.02 s	0.21 s
   subdivide(1), cluster(2000)	11,609	5.8	0.01 s	0.00 s	0.17 s
   cluster(2000) only	2,903	1.5	—	0.00 s	0.15 s

   Subdividing to 185k points costs under 0.1 s. The cost that matters scales with the clustering itself, so removing the subdivision saves very little.

   What it does buy is somewhere to put the clusters. ACVD assigns input vertices to clusters, so a cluster can only sit where a vertex already is. The cow has 2,903 points, and asking for 20,000 clusters without subdividing would mean roughly seven clusters per available vertex — there is nothing to assign. That is what the comment means by "not dense enough": the limit is the input vertex count, not runtime.

   So the rule of thumb is input points per cluster rather than any absolute density. If yours is comfortably above ~10, skip subdivide entirely. Below that, subdivide until it is. Worth checking the output too, since undershoot is quiet — cluster(500) on the raw cow returns 493 points rather than 500.

   One thing to watch if you benchmark this yourself: Clustering.subdivide() modifies the mesh you passed to Clustering(...) in place, so reusing one mesh across runs silently feeds each run the previous run's subdivided output. I caught myself doing exactly that while measuring the table above. Filed separately as #81.