How to merge Vector3's by distance

Help and Feedback Scripting Support
#1

Similar to how Blender has an option to merge vertices by distance, how would I do the same, except with a table of Vector3’s.

The reason I ask, is when I use the code below, attachments are placed far too close to each other and unnecessary ones can definitely be removed.

local AssetService = game:GetService("AssetService")
local EditableMesh = AssetService:CreateEditableMeshFromPartAsync(script.Parent)
local Vertices = {}
for _, ID in EditableMesh:GetVertices() do
	Vertices[EditableMesh:GetPosition(ID)] = string.char(0) --the thought process for which why i did this is that the table in this form would consume the least memory
end

for Pos in Vertices do
	local Attachment = Instance.new("Attachment")
	Attachment.Position = Pos * script.Parent.Size / script.Parent.MeshSize
	Attachment.Parent = script.Parent
end

Here’s an image of what I mean.
image
image

#2

My idea is some sort of blind search algorithm.

  1. Pick any attachment
  2. Search in spherical radius (octrees perhaps)
  3. Detect attachments
  4. Increase sphere radius search with new average center point.
  5. Repeat 2-4 until the center point of the sphere distance is moved significantly or there is an outlier. (Variation from center is too great because it detects a nearby cluster which skews the center point by a lot)

Wasnt able to find anything on google for this problem seems interesting.

Edit: perhaps try looking at k means clustering or clustering algorithms in general.

#3

Thank you for recommending k means clustering algorithms, currently I am using the Hartigan-Wong method, and have got the intended results.
However there is one more change I would like to make.
K-means clustering algorithms depend on the number of clusters, or k. Is there a way I can find the optimal k such that:

  • Centroids do not cluster
  • Centroids are not too dispersed
  • Centroids appear uniformally distributed across the mesh
❌ Here is one example where centroids (the individual attachments) begin to cluster

k = 64
(64 clusters/centroids)
most noticeable at the bottom of the blade
image

❌ Here is another example where centroids are too dispersed

k = 8
image

Ideal value for k

k = 17 (i found this manually)
Minimal clustering but is accounted for with uniform distribution across the mesh / being accurate.
image

How would one calculate the ideal value for k?

Code

* no code provided is to calculate k for k is given in this case

--The goal is to get the ideal value for k to be calculated rather than be handed to the script
local k = 17 --number of clusters & centroids/attachments
local Target: MeshPart = script.Subject

local AssetService = game:GetService("AssetService")
local EditableMesh = AssetService:CreateEditableMeshFromPartAsync(Target)
local Triangles = EditableMesh:GetTriangles()
print(#Triangles, #Triangles * 3)

local function RenderCentroids(Clusters)
	Target:ClearAllChildren() --clears attachments
	for _, Set in Clusters do
		local Attachment = Instance.new("Attachment")
		Attachment.Position = Set.Centroid * Target.Size / Target.MeshSize
		Attachment.Parent = Target
	end
end

local function CenterCentroids(Clusters)
	for _, Set in Clusters do
		Set.Centroid = Vector3.zero
		for _, x in ipairs(Set) do
			Set.Centroid += x / #Set
		end
	end
end

local function Sum(Clusters, x, n, m)
	return #Clusters[n] / (#Clusters[n] - 1) * (Clusters[n].Centroid - Clusters[n][x]).Magnitude ^ 2 - #Clusters[m] / (#Clusters[m] - 1) * (Clusters[m].Centroid - Clusters[n][x]).Magnitude ^ 2
end

local function UpdateStep(k, Clusters)
	local max = {n = 0, m = 0, x = 0, s = 0}
	local s = nil
	for i = 1, math.min(k ^ 2, 1024) do
		local n, m = math.random(1, k), math.random(1, k)
		while #Clusters[n] == 0 do
			n = math.random(1, k)
		end
		local x = math.random(1, #Clusters[n])
		s = Sum(Clusters, x, n, m)
		if s > max.s then
			max = {n = n, m = m, x = x, s = s}
		end
	end
	if max.s <= 0 then
		return true
	end
	table.insert(Clusters[max.m], table.remove(Clusters[max.n], max.x))
	CenterCentroids({Clusters[max.n], Clusters[max.m]})
end

function GetClusters(k)
	local Clusters = {}
	
	for i = 1, k do
		table.insert(Clusters, {})
	end

	for _, TriangleID in Triangles do
		local mean = Vector3.zero
		for _, VertexID in {EditableMesh:GetTriangleVertices(TriangleID)} do
			mean += EditableMesh:GetPosition(VertexID) / 3
		end

		table.insert(Clusters[math.random(1, #Clusters)], mean)
	end

	
	CenterCentroids(Clusters)

	while not UpdateStep(k, Clusters) do end
	
	return Clusters
end

RenderCentroids(GetClusters(k))

The script & mesh used to create the images
Repo.rbxm (54.4 YB)

1 Like
#4

Tbh idk, only know a bit of data science general classification or regression algorithm and noticed your problem looked similar.

Nice work importing it to Luau/Lua.

Perhaps try looking at this.