# Polygon raycasting

From a set of vertices and edges (edges defined as n to n+1 vertices, clockwise order from top-left) I’m trying to instantiate further vertices within the polygon on the world axis. To do so, from each point, I’m raycasting from that vertex in the directions [up/down/left/right] and looking for intersection points along other edges within the polygon. Unfortunately, however, my results are baffling.

Hopefully this image should explain further:

The ‘purple’ raycasts would be repeated for each vertex, and would only check for intersections with the current edge list - not the instantiated edges from the previous raycasts.

Unfortunately, I’m not getting especially far, I’m fairly certain the issue is arising from my checks to see whether the point is inside the polygon via the raycasting function - it’s returning a false positive when it’s coincidental with an edge, or it’s returning a false positive when it’s outside of the non-convex polygon.

Here is the place file for anyone who would like to help me debug (would be very much appreciated): node build.rbxl (20.3 KB)

1 Like

``````local insidePolygon do
function insidePolygon(polygon, p)
local isInside = false
local minX = polygon[1].x; local maxX = polygon[1].x
local minY = polygon[1].z; local maxY = polygon[1].z
for n = 1, #polygon do
local q = polygon[n]
minX = math.min(q.x, minX)
maxX = math.max(q.x, maxX)
minY = math.min(q.z, minY)
maxY = math.max(q.z, maxY)
end

if (p.x < minX or p.x > maxX or p.z < minY or p.z > maxY) then
return false
end

local i = 0;
local j = #polygon
for i = 1, #polygon do
if ((polygon[i].z > p.z) ~= (polygon[j].z > p.z) and
p.x < (polygon[j].x - polygon[i].x) * (p.z - polygon[i].z) / (polygon[j].z - polygon[i].z) + polygon[i].x ) then
isInside = not isInside
end
j = i
end

return isInside
end
end

local intersectRayRay do
function intersectRayRay(a1, a2, b1, b2)
local result;
local ua_t = (b2.x - b1.x) * (a1.z - b1.z) - (b2.z - b1.z) * (a1.x - b1.x)
local ub_t = (a2.x - a1.x) * (a1.z - b1.z) - (a2.z - a1.z) * (a1.x - b1.x)
local u_b  = (b2.z - b1.z) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.z - a1.z)

if ( u_b ~= 0 ) then
local ua = ua_t / u_b
result = Vector3.new(
a1.x + ua * (a2.x - a1.x),
0,
a1.z + ua * (a2.z - a1.z)
)
else
if ( ua_t == 0 or ub_t == 0 ) then
result = {txt = "coincident"}
else
result = {txt = "parallel"}
end
end

return result
end
end

local raycast do
function raycast(node, dir, nodes, verts)
for i = 0.1, 500, 0.1 do
local pos = (CFrame.new(node.Start.Value, dir) * CFrame.new(0, 0, -i)).p
if not insidePolygon(verts, pos) then
return nil
end
for j, other in next, nodes do
if other ~= node then
local intersect = intersectRayRay(node.Start.Value, pos, other.Start.Value, other.End.Value)
if intersect then
if typeof(intersect) == "Vector3" then
return {
hit   = other,
index = j,
pos   = intersect
}
end
end
end
end
end
end
end

local Line do
function Line(pA, pB, col, se)
local s = (pA - pB).magnitude
local Line = Instance.new("Part", game.Workspace)
Line.Anchored, Line.CanCollide 		= true, false
Line.TopSurface, Line.BottomSurface = "Smooth", "Smooth"
Line.Color  = col or Color3.new(1, 0, 0)
Line.Size   = Vector3.new(se or 0.1, se or 0.1, s)
Line.CFrame = CFrame.new(pA, pB) * CFrame.new(0, 0, -s/2)
return Line
end
end

-- init
local points  = game.Workspace.vertices:GetChildren()
table.sort(points, function (a, b)
end)

local edges, vertices = { }, { }
table.foreach(points, function (i, v)
local nxt = i == #points and 1 or i + 1

edges[#edges + 1] = {
Start    = {Value = v.Position * Vector3.new(1, 0, 1)};
End      = {Value = points[nxt].Position * Vector3.new(1, 0, 1)};
}
vertices[#vertices + 1]  = v.Position * Vector3.new(1, 0, 1)

-- debug
Line(edges[#edges].Start.Value, edges[#edges].End.Value, Color3.new(0, 1, 0), 0.125)
end)

for i, node in next, edges do
local dirs = {
up    = node.Start.Value + Vector3.new(   0, 0,  200);
down  = node.Start.Value + Vector3.new(   0, 0, -200);
right = node.Start.Value + Vector3.new( 200, 0,    0);
left  = node.Start.Value + Vector3.new(-200, 0,    0);
}
for dir, vec in next, dirs do
local intersect = raycast(node, vec, edges, vertices)
if intersect then
-- debug
Line(node.Start.Value, intersect.pos)
end
end
end
``````
1 Like

Hi, @Isocortex, wow, your code looks really confusing to me. So:
Why don’t you try a cube first and then a polygon? If you try with a cube, it might be easier to find the location of the problem (I hope). Thanks for reading and I hope it will help you.

Edit:
Could you send us screenshots of your confusing result? Because I don’t understand this raycasting idea. Well, you want to keep the vertices, but why do you do raycasting from one vertex to the other (So why are you doing raycasting anyway? You have the table of the polygon, so you can easily create a part for each vertex. Lol, I still don’t get this idea. With the table I mean this. I was not in Studio, but if so:

``````local Polygon = YourTableOrDictionary --Dictionary would better
for char, value in ipairs(Polygon) do
if char == "v" then --If you download your model from an OBJ file or if you have ever seen an OBJ file, you would know that "v" stands for vertex. If you need more help you can go to this link: https://en.m.wikipedia.org/wiki/Wavefront_.obj_file
local part = Instance.new("Part")
part.Parent = workspace
part.Position = value
part.Anchored = truee
part.CanCollide = false
end
end
``````

)?

Key:

• Grey bricks = the polygon vertices
• Green lines = the edge list of the polygon (n → n+1)
• Red lines = the raycast lines that have returned an intersection

The red lines should not be outside of the green shape.

In regard to your question about why, it’s because I need to separate (or decompose) the polygon into smaller sections on the world axis (hence why I’m also not performing convex polygon decomposition)

Hope that helps explain it better?

1 Like

For your purposes I believe it’s false positive-ing because you’re hitting a point really close to a vertex. You could try raycasting a slight distance away on each side from the vertex?

1 Like

I agree that may be an issue, unfortunately although I’m sure offsetting would improve it - that wouldn’t be fit for purpose for my application sadly

Slight improvement, but still having issues:

• The blue, highlighted red line (a raycast intersection) should have intersected the centre point
• The vertex on the right hand screen should have raycasted upwards and caused another red intersection line

Update code for those curious / willing to help:

node build.rbxl (21.4 KB)

What I mean is move the start point a miniscule distance away from the vertex. You could scale this by shape size if you felt like. Basically, all it’d serve to do is create a tiny “deadzone” in the center to deconflict things. Keep it otherwise normal.

Technically I do, but implemented it out of curiousity and unfortunately it still presents with the same issue:

``````		local startPos = CFrame.new(node.Start.Value, dir) * CFrame.new(0, 0, -2)
for i = 2, 500, 1 do
local pos = startPos.p + (dir - startPos.p).unit * i
``````

I’ve been re-reading your post over and over, from what I understand you’re using the already existing vertices within or on the polygon to raycast in all directions and look for an intersection on the pre-existing edges of the polygon, correct? So that’s the desired behaviour, but what’s actually happening that’s not your desire behaviour, I’m still confused about that.

Would this be the end result you’re looking for?

Correct

The undesired behaviour is as follows:

• The pink highlighting denotes a raycast from the leftmost vertex (grey block), which has intersected at the right most vertex within that pink circle (again, the other grey part). This shouldn’t have been the case as all 3 of those vertices within the pink selection are on the same line - it should have been split into two consecutive lines
• The purple highlighting denotes an area where a raycast intersection should have been found, but wasn’t

Exactly yes! That’s the exact result I’d like to get to

Haha, uh, I just realized I actually lied a bit. There’s still one or two coincidents under a couple of the vertical green lines, so it’s not quite the end result.

What I’ve done so far is instead of raycasting, I checked the possible intersections for each segment on the polygon and tried to find the closest one per cast.

There are a few edge cases here, so I’ll upload my version of the file after I clean up a bit.

1 Like

That would be wonderful, thank you - I appreciate the help.

If it’s any help, should be able to detect a coincident with the following:

``````local a1, a2 = Start_Line1, End_Line1
local b1, b2 = Start_Line2, End_Line2
local eps = 0.00001

local ua = (b2.x - b1.x) * (a1.z - b1.z) - (b2.z - b1.z) * (a1.x - b1.x)
local ub = (a2.x - a1.x) * (a1.z - b1.z) - (a2.z - a1.z) * (a1.x - b1.x)
local u_b = (b2.z - b1.z) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.z - a1.z)

if -eps < u_b and u_b < eps then
-- coincident line

end
``````
1 Like

I still can’t seem to implement the coincident detection, so I’ll just post the file in the meantime.

node build (1).rbxl (21.1 KB)

For summary, I’ve implemented one new function called “getIntersections” in the workspace script. It returns a sorted table of intersections for a line and a polygon.

1 Like

Thanks for this, this is a great step forwards! I’ll try and work on the coincident issues as well, seems the code I gave above doesn’t help and we both had the same idea of checking the slopes and the Y-intercept from your code

Alright, I think I’ve got the coincident detection working.

node build (1).rbxl (21.4 KB)

There still might be a possible edge case, but I highly doubt it at this point.

1 Like

Thank you so much - I have been wanting to face palm all day. Much appreciated

1 Like