Polygon Triangulation

Hey there :slight_smile:

So yeah, I’ve worked on this thing for probably about an hour? I don’t have much use for it but it was a fun project and if anyone wants the source code, I’ll open source it. Anyways here are some examples of what it does:

image

image

Inspect the source code and critique at will haha:
Polygon Triangulation [open source[ - Roblox
I’m aware it’s a bit clunky and also requires each node to be connected directly in terms of the numbering. Don’t overlap nodes!

37 Likes

Looks awesome! :hushed:

Would’ve used the same thing for my floor building system, but it seems a bit too complicated for me to wrap my head around ahaha

I’d love to check it out myself if you don’t mind!

3 Likes

Good work! Which polygon triangulation algorithm did you use?

1 Like

I’ve attached a link in the post. :slight_smile:

@AstroCode Honestly… I don’t know if anyone has coined it with a name yet. It’s fairly standard in the sense that the algorithm removes ears from the polygon up until it considers the polygon complete. There’s quite a few inefficiencies because honestly, I’m not so good with computer graphics yet :frowning:

I used these resources:

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/TwoEar/two-ear.htm

https://math.oregonstate.edu/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/crossprod/crossprod.html

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

4 Likes

That’s called the ear clipping method. I used it in a program a couple months back and found the Wikipedia article an interesting read. Polygon triangulation - Wikipedia

I’m using this resource, but how can I fix this hole?

here is my script

local function CreatePolygonFromPoints(Points)
	local Polygon = {}
	local First = Polygon
	
	for i = 1, #Points do
		Polygon.Position = Points[i]
		Polygon.NodeId = i
		
		if i ~= #Points then
			Polygon.Next = {Previous = Polygon}
			Polygon = Polygon.Next
		end
		
		local A, B, C = GetPoint("Behind", i, Points), Points[i], GetPoint("Front", i, Points)
		drawTriangle(A, B, C, workspace.Debug)
	end
	
	Polygon.Next, First.Previous = First, Polygon
	return First
end

function GetPoint(Type, Point, ListofPoint)
	if Type == "Behind" then
		if Point == 1 then
			return ListofPoint[#ListofPoint]
		else
			return ListofPoint[Point - 1]
		end
		
	elseif Type == "Front" then
		if Point == #ListofPoint then
			return ListofPoint[1]
		else
			return ListofPoint[Point + 1]
		end
	end
	return false
end

local wedge = Instance.new("WedgePart")
wedge.Material = Enum.Material.SmoothPlastic
wedge.Transparency = 0
wedge.Anchored = true
wedge.CanCollide = false
wedge.TopSurface = Enum.SurfaceType.Smooth
wedge.BottomSurface = Enum.SurfaceType.Smooth
wedge.Color = Color3.fromRGB(125, 125, 125)
local wedgeMesh = Instance.new("SpecialMesh", wedge)
wedgeMesh.MeshType = Enum.MeshType.Wedge
wedgeMesh.Scale = Vector3.new(1,1,1)

function drawTriangle(a, b, c, parent)
	local edges = {
		{longest = (c - b), other = (a - b), position = b};
		{longest = (a - c), other = (b - c), position = c};
		{longest = (b - a), other = (c - a), position = a};
	};
	table.sort(edges, function(a, b) return a.longest.magnitude > b.longest.magnitude end);
	local edge = edges[1];
	
	local theta = math.acos(edge.longest.unit:Dot(edge.other.unit))
	local s1 = Vector2.new(edge.other.magnitude * math.cos(theta), edge.other.magnitude * math.sin(theta));
	local s2 = Vector2.new(edge.longest.magnitude - s1.x, s1.y);

	local p1 = edge.position + edge.other * 0.5
	local p2 = edge.position + edge.longest + (edge.other - edge.longest) * 0.5
	
	local right = edge.longest:Cross(edge.other).unit;
	local up = right:Cross(edge.longest).unit;
	local back = edge.longest.unit;
	
	local cf1 = CFrame.new(
		p1.x, p1.y, p1.z,
		-right.x, up.x, back.x,
		-right.y, up.y, back.y,
		-right.z, up.z, back.z
	);
	local cf2 = CFrame.new(
		p2.x, p2.y, p2.z,
		right.x, up.x, -back.x,
		right.y, up.y, -back.y,
		right.z, up.z, -back.z
	);
	
	local w1 = wedge:Clone();
	local w2 = wedge:Clone();
	w1.Parent = parent;
	w2.Parent = parent;
	w1.Size = Vector3.new(0.01, s1.y, s1.x);
	w2.Size = Vector3.new(0.01, s2.y, s2.x);
	w1.CFrame = cf1;
	w2.CFrame = cf2;
end;

local points = {}

for i, v in next, workspace.Model:GetChildren() do table.insert(points, v.Position) end
CreatePolygonFromPoints(points)

I have no idea how to fix this

1 Like

anhtuan159, that script is partially correct in choosing the closest two points. However, to fill the whole area (… or to fill the hole, same same), the triangle drawing algorithm needs to additively progress from a starting point.

Think of following along the circumference of a circle in a constant direction of rotation, either clockwise or counter-clockwise, but you have to pick one direction and stick with it in order to fill the polygon using triangles connecting an existing set of points.

So, you can’t just accept the order of the table of children returned from workspace.Model:GetChildren() and then draw triangles (wedge parts) between a part and its closest two parts. You need to determine a specific order of parts around the perimeter.

Once this is done, a new point created at a later time can be added to the polygon by drawing a triangle from this new point to its closest two neighbour points, continuing the fill process.

OP’s source script does this progressive rotation triangle fill. Try editing the place posted at the top of this thread to see how its done. Just slow down the wait to watch it happen. On line 109, change wait() to wait(1) or some higher value.

function TriangulatePolygon(points)
	local folder = Instance.new("Folder", game.Workspace)
	while true do
		local newTable = points
		local done = false
		while #newTable > 2 do
			done,newTable = GetEarOfPolygon(newTable, -1, folder)
			table.sort(newTable, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end)
			wait(1) -- set to 1 or higher to watch triangles fill the polygon
		end
		wait(2)
		folder:ClearAllChildren()
	end
end
3 Likes

Instead of while loops I feel like this could be done easier with recursion.

1 Like

Right? Also avoid Wait()

I’m just responding to the posted code examples and answering to the general idea of polygon fill using triangles.

1 Like

Meant to state specifically the order of points for additively filling the polygon is:

  1. Current Point
  2. Previously Used Point (used as current point on previous iteration)
  3. Original Starting Point

After a polygon is filled and then a new point is added, the procedure is no longer rotating around the perimeter, so it can switch to using the current point and the closest two points.

1 Like

Thanks for the clarity! I admit I posted this code partially to help out and also partially because I wanted more experienced members to weigh in on what to improve. You’ve helped a bunch :smile:

1 Like

Hi,
for some reason, it’s not working properly for me. It doesn’t work in one direction at all, and when I have more than 5 points then it starts to bug for me. And is there a way how to detect that it’s not possible to construct the triangles?

btw I’m using the original code Polygon Triangulation [open source[ - Roblox, I didn’t change anything.

robloxapp-20220416-0912112.wmv (2.5 MB)

thanks for any help!

This code is most likely outdated and probably not up to date. You should use other methods or use a plugin

Came across this post, proved to be pretty useful but encountered the same problem as a few others.

To solve this, I added a method to check if the points inside the table are clockwise or anti-clockwise then you can determine the direction based on if the number is negative or positive. This will probably solve most peoples issues with finding the direction and table sorting errors.

function CheckIsClockwise(points)
	local Sum = 0
	for i=1, #points do
		if points[i+1] then
			Sum += (math.abs(points[i+1].Position.X) - math.abs(points[i].Position.X))*(math.abs(points[i+1].Position.Z) + math.abs(points[i].Position.Z))
		else
			Sum += (math.abs(points[1].Position.X) - math.abs(points[i].Position.X))*(math.abs(points[1].Position.Z) + math.abs(points[i].Position.Z))
		end
	end
	return Sum
end

function TriangulatePolygon(points)
	local Direction = CheckIsClockwise(points)
	if Direction > 0 then
		Direction = 1
	else
		Direction = -1
	end
	
	table.sort(points, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end)
	local folder = Instance.new("Folder", game.Workspace)
	while true do
		local newTable = points
		local done = false
		while #newTable > 2 do
			done,newTable = GetEarOfPolygon(newTable, Direction, folder)
			table.sort(newTable, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end)
		end
		break
	end
end
4 Likes

amazing work! that will help me a lot!