Why, when attempting to find the winding order of an arbitrary rectilinear polygon, does the formula return the opposite winding order?

Help and Feedback Scripting Support
1

Hey,

Basically for a floor generation algorithm, I’m allowing users to place points in any order they would want, which is not a problem, I’ve commissioned someone to help with the more math-heavy concepts and they wrote a triangulation and rectilinear decomposition algorithm, it was just my job to actually implement it which is going fine thus far.

The problem I’m having is that, when determining the winding order of this polygon, it gets marked as the opposite of what it actually is, so a counterclockwise polygon is marked as clockwise and clockwise marked as counterclockwise. This isn’t the issue, I can just return the inverse so the winding order is correct. What I need is someone to explain why it returns the inverse.

For reference, I’m using this solution for finding the winding order. In essence, you need to do (x1 - x2) * (y1 + y2) for one and the next vertex of the polygon, then add each of the results. If the final sum is greater than 0, clockwise, if less than 0, counterclockwise. Implementing this seems to work fine, however the result appears to always be the inverse of what it needs to be, why is this?

Here’s my implementation:

local function getWindingOrder(...: Vector3)
	local packed = {...}
	local sumNow = 0
	for i = 1,#packed do
		local x1,y1,x2,y2 = 
			packed[i].X, 
			packed[i].Z, -- we take z because the plot can be summarized into a 2D plane by using z instead of y
			packed[i + 1] and packed[i + 1].X or packed[1].X, -- in case it's the final iteration we need to loop back to the beginning
			packed[i + 1] and packed[i + 1].Z or packed[1].Z
		local x, y = x2 - x1, y2 + y1
		sumNow += x * y
	end
	print(sumNow > 0 and 'Clockwise' or 'Counter clockwise') -- this is where the issue arises. if I place points in clockwise it'll get marked as ccw as well as ccw marked as cw 
end

For example, these points are placed in counter clockwise but the output says “clockwise” (ignore the part that’s generated):
image
If placed in the opposite order, output says “counter clockwise”:
image

I saw in the replies of the solution that if you are working with a plane whose Y (in our case Z bc translating 3D to 2D) axis is reversed, the opposite is true; >0 is ccw, <0 is cw. I think this might be the case but I wasn’t able to find anything on the CFrame documentation. Could anyone confirm/deny/offer an explanation

1 Like
2

The difference is that the algorithm is built for a Cartesian coordinate plane like this:

Y
┃
┗━━ X

But because you’re using Roblox’s Z axis, which points toward the “back” of world space, your coordinate plane instead looks like:

┏━━ X
┃
Y (really +Z)

All this to say, you can fix it by inverting your Y coordinates: that means negating both y1 and y2, negating the x * y term, or negating the whole sum. All would have the same effect.

3

BTW there’s also another answer that gives a faster and simpler solution IMO:

-- you could also store this info as the polygon is built to avoid the loop completely
local function GetPointOnConvexHull(points: {Vector3})
  local idx = -1
  local p = Vector3.new(math.huge, 0)
  for i, v in points do
    if v.X < min.X then
      p = v
      idx = i
    end
  end
  return idx, p
end

-- returns positive number if clockwise
local function GetWindingOrder(points: {Vector3})
  local idx, p = GetPointOnConvexHull(points)
  local before = points[idx - 1] or points[#points]
  local after = points[idx + 1] or points[1]
  return (after - p):Cross(before - p)
end
1 Like
4

That’s quite a bit faster actually, did some benchmarks if you’re interested (although now realizing I mixed up x1 and x2 but ignore that):

local function getWindingOrder(points: {Vector3})
	local sumNow = 0
	for i = 1,#points do
		local x1,y1,x2,y2 = 
			points[i].X, 
			points[i].Z, 
			points[i + 1] and points[i + 1].X or points[1].X,
			points[i + 1] and points[i + 1].Z or points[1].Z
		local x, y = x2 - x1, y2 + y1
		sumNow += x * y
	end
	return sumNow
	--return sumNow < 0 and WindingOrders.Clockwise or WindingOrders.Anticlockwise
end

local function GetPointOnConvexHull(points: {Vector3})
	local idx = -1
	local min = Vector3.new(math.huge, 0, math.huge)
	for i, v in points do
		if v.X < min.X then
			min = v
			idx = i
		end
	end
	return idx, min
end

-- returns positive number if clockwise
local function GetWindingOrder(points: {Vector3})
	local idx, p = GetPointOnConvexHull(points)
	local before = points[idx - 1] or points[#points]
	local after = points[idx + 1] or points[1]
	return (after - p):Cross(before - p).Y
	--return (after - p):Cross(before - p).Y < 0 and WindingOrders.Clockwise or WindingOrders.Anticlockwise
end

Basic test:

local init = os.clock()

for i = 1,50000 do
	local rndX, rndZ = math.random(1,500), math.random(1,500)
	local vectors = {Vector3.new(rndX, 0, rndZ), Vector3.new(0, 0, rndZ), Vector3.new(rndX, 0, 0), Vector3.new()}
	getWindingOrder(vectors)
end

local now = os.clock()
print('(x1-x2)(y1+y2) took', now - init)

task.wait(3)

local init = os.clock()

for i = 1,50000 do
	local rndX, rndZ = math.random(1,500), math.random(1,500)
	local vectors = {Vector3.new(rndX, 0, rndZ), Vector3.new(0, 0, rndZ), Vector3.new(rndX, 0, 0), Vector3.new()}
	GetWindingOrder(vectors)
end

local now = os.clock()
print('cross took', now - init)

One from stack overflow:
(x1-x2)(y1+y2) took 0.01704720000270754

Yours:
cross took 0.014948399970307946

More extreme test, yours saved nearly two entire seconds:

local init1 = os.clock()

for i = 1,50000 do
	local vectors = {}
	for i = 1, math.random(1,2500) do
		table.insert(vectors, Vector3.new(math.random(1,500), 0, math.random(500)))
	end
	getWindingOrder(vectors)
end

local now1 = os.clock()
print('(x1-x2)(y1+y2) took', now1 - init1)

task.wait(3)

local init2 = os.clock()

for i = 1,50000 do
	local vectors = {}
	for i = 1, math.random(1,2500) do
		table.insert(vectors, Vector3.new(math.random(1,500), 0, math.random(500)))
	end
	GetWindingOrder(vectors)
end

local now2 = os.clock()
print('cross took', now2 - init2)

(x1-x2)(y1+y2) took 6.3958394000073895
cross took 4.537635599961504

1 Like