Verlet integration

Verlet integration is a method used to integrate Newton’s equations of motion. This allows you to simulate cloth, rope, ragdolls, and other similar materials.

Prerequisites

  • Vector math
  • Basic understanding of physics
    • Velocity
    • Acceleration
  • Understanding of rates of change
    • For example: A car is traveling at 2 m/s after 10 second the car has traveled 20 metres
  • Understand object oriented programming
    • This isn’t a must, but it will help you not only understand the code in this article, but also write your verlet integration more efficiently.

A point[edit]

Since we are simulating physics it’s important to have something to simulate on (no duh!). When we think about things like rope or cloth which can bend or fold at any point in real life we have to reasonably understand that’s not something we can expect to achieve with Roblox parts. As a result rather than simulate every single point along a rope or piece of cloth we’ll only simulate some points and fill the in-between with parts.

Verlet 1.png


Let’s start with a basis for our point object. To apply motion to our point we’re going to simply apply our velocity to the previous position based on a change in time. Now using an Euler approach one might come up with something like this:

Verlet 2.png

A verlet approach however instead moves the object based on the idea of inertia. In other words, it assumes the point will continue in the uniform motion that it previously had. We can get the uniform change from the previous position to the current position via vector subtractions and then use that value as a substitute for velocity:

Verlet 3.png

That’s pretty much all we need to know to make out point class. We’re just going to add two extra details. The first thing we’ll add is an anchored property that will be a simple Boolean that tells us if the point is static or not. The rope, cloth, etc needs to be attached to something after all. The other thing we’ll be adding is damping. It’s simply going to be a value that slows down our velocity a bit as time goes on.

local point = {};
local gravity = 196.2;
 
function point.new(v3)
	local self = setmetatable({}, {__index = point});
 
	self.position = v3;
	self.previousPosition = v3;
	self.velocity = Vector3.new();
	self.acceleration = Vector3.new();
 
	self.anchored = false;
 
	return self;
end;
 
function point:update(delta, damping)
	if not self.anchored then
		self.acceleration = Vector3.new(0, -gravity, 0); -- x and z don't accelerate
		self.velocity = self.position - self.previousPosition;
		self.previousPosition = self.position;
		self.position = self.position + self.velocity * damping + self.acceleration * delta^2;
	else
		self.acceleration = Vector3.new();
		self.velocity = Vector3.new();
		self.previousPosition = self.position;
	end;
end;

The idea behind verlet integration is not necessarily to have perfectly accurate physics, but rather to make them believable enough that someone playing your game thinks they look real.

Constraints[edit]

Well we know a little bit about how to apply motion to our points but that’s not really all that useful. In order to build our simulations we are going to need constraints. When talking about constraints I mean limiting where the points can and cannot go. The most obvious constraint (and the one we’ll be focusing on) is keeping two points connected by a brick segment (the parts that make up our rope, cloth, etc). At the end I’ll briefly talk about one collision technique, but realistically there’s no single way to do collision so it’s kind of the wild-west algorithmically speaking.

Right so onto our constraint. The idea is simple. As mentioned above each point is going to be connected by a segment and that segment is going to have some length to it. So ideally our goal is to apply motion to our point but keep the two points distanced by that segment length (restDistance). Remember verlet integration isn’t about accuracy it’s about tricking whoever is looking at it into thinking it’s real. That means we have a bit of leeway in our simulation.

The way we are going to do this is by first updating the points, then applying the constraint. The idea behind the constraint will be some simple vector math.

Verlet 4.png


With that s value we know how much percent wise of the d vector we need to move to keep the distance between the two vectors at that rest distance. Our next step is to evenly apply that translation to both points which is pretty easy to do.

Verlet 5.png


The last thing we need to talk about regarding constraints is the concept of relaxation. If we have multiple points constrained to each other our newly calculated values might violate the ones previously calculated. The way this is fixed is by solving our constraints multiple times. This might seem like a really weird thing to do, but if we solve for the constraints multiple times they get closer and closer to being solved. For the purpose of this article we’ll solve about 15 times as that seems to be getting a good balance of results and performance for me, but you are free to play around with it and find what works best for your purposes.

Finally, our constraint in code form with once again a few minor details added. The first obviously being that functions that both draw and destroy the constraint, but they’re not the focus of this article so they won't be explained. The other thing added isn’t necessary, but if you want the cloth, rope, etc to fall apart when the constraints are broken you can do so by checking if the two points are breaking the constraint by a certain amount.

local constraint = {};
 
function constraint.new(point1, point2, distance)
	local self = setmetatable({}, {__index = constraint});
 
	self.point1 = point1;
	self.point2 = point2;
 
	self.restDistance = distance;
	self.canBreak = false;
	self.breakDistance = 5;
 
	self.line = Instance.new("Part");
	self.line.Size = Vector3.new();
	self.line.Anchored = true;
	self.line.CanCollide = false;
	self.line.BrickColor = BrickColor.new("Really black");
 
	self.mesh = Instance.new("BlockMesh", self.line);
	self.mesh.Scale = Vector3.new(0.2, 0.2, 0.2);
 
	return self;
end;
 
function constraint:solve()
	if self.point1 and self.point2 then
		local difference = (self.point1.position - self.point2.position);
		local distance = difference.magnitude;
		local scalar = (self.restDistance - distance) / distance;
		local translation = difference * 0.5 * scalar;
 
		if not self.point1.anchored then
			self.point1.position = self.point1.position + translation;
		end;
 
		if not self.point2.anchored then
			self.point2.position = self.point2.position - translation;
		end;
 
		if self.canBreak and (self.point1.position - self.point2.position).magnitude > self.restDistance + self.breakDistance then
			self:Destroy();
		end
	end;
end;
 
function constraint:draw()
	if self.point1 and self.point2 and self.line then
		local distance = (self.point1.position - self.point2.position).magnitude;
		self.line.CFrame = CFrame.new(self.point1.position, self.point2.position) * CFrame.new(0, 0, -distance / 2);
		self.mesh.Scale = Vector3.new(.2, .2, distance) / 0.2;
	end;
end;
 
function constraint:Destroy()
	self.point1 = nil;
	self.point2 = nil;
	self.mesh:Destroy();
	self.line:Destroy();
end;

Supplementary: Collision[edit]

Okay, as mentioned there are many ways to do collision. In this article we'll only be going over a single “rag-tag” thrown together method. All we're going to do is define a plane, and if the point is above that plane let the verlet integration do its thing, otherwise we're going to update the point and then project the point onto the plane surface and finally solve. This is what the math looks like:

Verlet 7.png

Here's a simple plane class:

local plane = {};
 
function plane.new(cframe, normal, point, scalar)
	local self = setmetatable({}, {__index = plane});
 
	self.cframe = cframe;
	self.normal = normal;
	self.point = point;
	self.scalar = scalar;
 
	return self;
end;
 
function plane:isAbove(point)
	local h = ((point - self.cframe.p):Dot(self.normal)) - self.scalar;
	return h > 0, h;
end;
 
function plane:pointToPlane(point)
	return point - (point - self.point):Dot(self.normal) * self.normal;
end;

With some simple logic we can apply 6 infinite planes to create a 3D rectangle and with some of the simple rules of geometry we can calculate box collision:

local collision = {};
 
function collision.new(part)
	local self = setmetatable({}, {__index = collision});
 
	self.planes = {};
	self.origin = part.CFrame;
 
	for _, enum in next, Enum.NormalId:GetEnumItems() do
		local lnorm = Vector3.FromNormalId(enum);
		local normal = part.CFrame:vectorToWorldSpace(lnorm);
		local tosurface = (part.Size/2 * lnorm).magnitude;
		table.insert(self.planes, plane.new(part.CFrame, normal, part.Position + normal * tosurface, tosurface));
	end;
 
	return self;
end;
 
function collision:pointIn(point)
	local set = {};
	for _, planey in ipairs(self.planes) do
		local above, h = planey:isAbove(point);
		if above then
			return false;
		end;
		table.insert(set, {math.abs(h), planey})
	end;
	return set;
end;
 
function collision:pointToPlanes(point)
	local set = self:pointIn(point)
	if set then
		table.sort(set, function(a, b) return a[1] < b[1]; end);
		return set[1][2]:pointToPlane(point);
	end;
end;

Applying this allows you to do some very simply collisions like this. it's not perfect, but as was mentioned there are many ways to approach collision and this is one of the easiest ones that came to mind.

Verlet 8.gif

Conclusion[edit]

That’s pretty much it in terms of the math stuff, now it’s just a matter of applying it in game. From this point on it's all about structuring points and their constraints to create objects. It's pretty straight forward and from this point doesn't require any complex math. As a result I'll leave you the reader to pull apart the below code . Good luck and enjoy!

local apart = game.Workspace.AnchorPart;
local ppart = game.Workspace.PlanePart;
local previousTime = tick();
 
function cloth(corner, width, height, length)	
	local points = {};
	local constraints = {};
	local m = math.sqrt(length^2 + length^2);
	for y = 0, height do
		for x = 0, width do
			points[y] = points[y] or {};
			points[y][x] = point.new((corner * CFrame.new(x, y, 0)).p);
			if x ~= 0 then
				local c = constraint.new(points[y][x], points[y][x-1], length);
				c.line.Parent = game.Workspace.CurrentCamera;
				table.insert(constraints, c);
			end;
			if y ~= 0 then
				local c = constraint.new(points[y][x], points[y-1][x], length);
				c.line.Parent = game.Workspace.CurrentCamera;
				table.insert(constraints, c);
				--[[
				-- structure makes a difference!
				if x < width then
					local c = constraint.new(points[y][x], points[y-1][x+1], m);
					c.line.Parent = game.Workspace.CurrentCamera;
					table.insert(constraints, c);
				end;
				--]]
			end;
			if y == 0 then
				points[y][x].anchored = true;
			end;
		end;
	end;
	return points, constraints;	
end;
 
local width, height, length = 10, 10, 2;
local cpoints, cconstraints = cloth(apart.CFrame, width, height, length);
 
function update()
	local delta = tick() - previousTime;
	previousTime = tick();
	local col = collision.new(ppart);
	for i = 0, height do
		if i == 0 then
			for i2 = 0, width do
				local x = cpoints[i][i2];
				x.position = (apart.CFrame * CFrame.new(i2 * length, 0, 0)).p;
			end;
		end;
		for i2 = 0, width do
			local x = cpoints[i][i2];
			x:update(delta, 0.9985);
			--[[
			-- collision
			local lide = col:pointToPlanes(x.position);
			if lide then
				x.position = lide;
			end;
			--]]
		end;
	end;
	for i = 1, 15 do
		for _, c in ipairs(cconstraints) do
			c:solve();
		end;
	end;
	for _, c in ipairs(cconstraints) do
		c:draw();
	end;
end;
 
game:getService("RunService").Stepped:connect(update);