How would I go about calculating the vector (direction & length) of two intersecting planes?
The image below is marked with a blue and green arrow which indicate the intersecting vector between the red transparent part & the grey block. I am trying to find a way to calculate the arrow vectors.
2 Likes
This is a long post - sorry! Hopefully helpful though.
Cuboid-Plane Intersection Theory
Take each edge of the cube. The edge is defined as a line between v1 and v2, the two vertices of the edge, represented as:
p = v1 + k( v2 - v1 )
You should end up with 12 of these equations for your 8 vertices. You can get each vertex by doing:
v1 = box.CFrame.p + 0.5 * ( box.Size.X * box.CFrame.RightVector + box.Size.Y * box.CFrame.UpVector + box.Size.Z * box.CFrame.LookVector )
Swapping the signs for each size term will get you your 8 corners:
v1: +X +Y +Z
v2: +X +Y -Z
v3: +X -Y +Z
v4: +X -Y -Z
v5: -X +Y +Z
v6: -X +Y -Z
v7: -X -Y +Z
v8: -X -Y -Z
Now you have v1 through v8 we have all we need for your 12 edges. We won’t bother explicitly defining them in code, as it’s not necessary.
We should, however, define your plane with normal vector n that passes through point p0 with the equation:
p • n - p0 • n = 0 ; where • is the dot product operation.
Okay now that we have all that knowledge good to go for any orientation, you now need to find points of intersection with the plane. There will be anywhere from 3 to 6 intersections depending on the orientation of the cuboid and how far through the plane it is.
To find the intersection points, we solve the edge and plane equations simultaneously, to obtain unknown k. If k falls in the range 0 to 1 inclusive then the edge intersects the plane. Substitute k back into the edge equation to get the coordinates of this point.
k = ( p0 - v1 ) • n / ( ( v2 - v1 ) • n )
For each k value, you must be careful to combine the correct vertices so as not to accidentally draw diagonals for your edges. Your pairs should only ever be 1 sign difference from each other.
If you used the same signs I did, then your combinations are:
k12: v1 and v2
k13: v1 and v3
k24: v2 and v4
k34: v3 and v4
k15: v1 and v5
k26: v2 and v6
k37: v3 and v7
k48: v4 and v8
k56: v5 and v6
k57: v5 and v7
k68: v6 and v8
k78: v7 and v8
Finally, once you’ve got all your points of intersection, you need to work out which points to draw between for your vectors. This is trickier, because the edges can coincident, or they could be parallel on each side of a face. The easiest way I thought of is to put all the points into a table, not caring about which edge they came from, and determine the pairings from there, using the knowledge that the polygon must be convex for a cuboid through a plane.
Example Code
Here’s my take on a script to do this. It might not be the best way but it’s the way I chose to do it:
local vSigns = { -- The vertex signs
Vector3.new( 1, 1, 1 ), -- +X +Y +Z
Vector3.new( 1, 1, -1 ), -- +X +Y -Z
Vector3.new( 1, -1, 1 ), -- +X -Y +Z
Vector3.new( 1, -1, -1 ), -- +X -Y -Z
Vector3.new( -1, 1, 1 ), -- -X +Y +Z
Vector3.new( -1, 1, -1 ), -- -X +Y -Z
Vector3.new( -1, -1, 1 ), -- -X -Y +Z
Vector3.new( -1, -1, -1 ), -- -X -Y -Z
}
local kPairings = { -- The k pairings as listed before
{ 1, 2 }, { 1, 3 }, { 2, 4 }, { 3, 4 }, { 1, 5 }, { 2, 6 }, { 3, 7 }, { 4, 8 }, { 5, 6 }, { 5, 7 }, { 6, 8 }, { 7, 8 },
}
function getYourIntersectionVectors( box, plane, point )
pos = box.CFrame.Position
size = box.Size
look = box.CFrame.LookVector
up = box.CFrame.UpVector
right = box.CFrame.RightVector
-- Create vertices
local vertices = {}
for i, s in ipairs( vSigns ) do
vertices[ i ] = pos + 0.5 * ( s.X * size.X * right + s.Y * size.Y * up + s.Z * size.Z * look )
end
-- Find intersections
local intersections = {}
for _, g in ipairs( kPairings ) do
local v1 = vertices[ g[ 1 ] ]
local v2 = vertices[ g[ 2 ] ]
local k = ( point - v1 ):Dot( plane ) / ( v2 - v1 ):Dot( plane )
if k >= 0 and k <= 1 then
table.insert( intersections, v1 + k * ( v2 - v1 ) )
end
end
-- Determine pairings for convex polygon and calculate vectors
-- This bit is a little bit convoluted and involves converting the intersection points to the
-- plane's local axes to be able to implement a two-dimensional convex hull algorithm.
-- Put intersections into local space about the plane
local planeCframe = CFrame.new( point, point + plane )
for i, p in ipairs( intersections ) do
intersections[ i ] = planeCframe:PointToObjectSpace( p )
end
-- Implement Graham scan
-- Sort by x-axis
table.sort( intersections, function ( a, b )
return a.X < b.X
end )
-- Define counter-clockwise function
local function ccw( a, b, c )
return ( b.X - a.X ) * ( c.Y - a.Y ) > ( b.Y - a.Y ) * ( c.X - a.X )
end
-- Do the loop in upper and lower hull
local pointStack = {}
-- Lower hull
for i, p in ipairs( intersections ) do
while #pointStack > 1 and not ccw( pointStack[ #pointStack - 1 ], pointStack[ #pointStack ], p ) do
table.remove( pointStack, #pointStack )
end
table.insert( pointStack, p )
end
-- Upper hull
local t = #pointStack + 1
for i = #intersections, 1, -1 do
local p = intersections[ i ]
while #pointStack >= t and not ccw( pointStack[#pointStack - 1 ], pointStack[ #pointStack ], p ) do
table.remove( pointStack, #pointStack )
end
table.insert( pointStack, p )
end
-- Pop last point to prevent duplicate
table.remove( pointStack, #pointStack )
-- Convert back to world space
for i, p in ipairs( pointStack ) do
pointStack[ i ] = planeCframe:PointToWorldSpace( p )
end
-- FINALLY calculate vectors between the pairings
local intersectionVectors = {}
for i = 1, #pointStack do
local j = i == 1 and #pointStack or i - 1
table.insert( intersectionVectors, {
Vector = pointStack[ i ] - pointStack[ j ],
Origin = pointStack[ j ],
} )
end
return intersectionVectors
end
local n = Vector3.new( 0, 2, 5 ) -- Your plane's normal vector
local p0 = Vector3.new( 1, 2, 3 ) -- A point that the plane passes through
getYourIntersectionVectors( game.Workspace.YourBox, n, p0 )
-- returns a table of tables, each containing Vector and Origin Vector3 values
Demo Place
Here’s a demo place: IntersectionsDemo.rbxl (22.1 KB)
Open in Studio, test Play Solo and then move the cube around using the move, scale and rotate tools.
Here's a video of it in action.
The deep blue lines are drawn to show the calculated vectors. At the end you will see a demonstration of it treating the plane as infinite:
https://youtu.be/dv6lKfoxfm8
Assumptions and Limitations
- The way it is currently coded is suitable for cuboid solids intersecting with an infinite plane.
- If you want to expand to more shapes including those that are concave, then you’ll need a lot more edits - this code is based on a convex hull assumption.
- If you don’t want an infinite plane, then one method could be to do it using this infinite plane algorithm, then take your intersection points and bring them within the bounds along the calculated vectors.
- If you wanted the vectors for a specific face of the cuboid, you can take the table of vectors and determine which ones sit on the face you’re concerned about by checking two points along the vector satisfy the plane of that particular face. To get a face’s plane, its normal vector can be found using the CFrame LookVector, RightVector and UpVector unit vectors, and a point on the surface can be found by adding half the size of the normal dimension, e.g.
backPoint = part.CFrame.Position - part.CFrame.LookVector * part.Size.Z / 2; backNormal = -part.CFrame.LookVector.
Hope that helps!
This post helped with a bit of the theory: http://forums.cgsociety.org/t/math-area-of-plane-intersecting-cube-given-plane-normal/776808/2
And you can read more about Graham Scan here: Graham scan - Wikipedia
Edited (20 Jan 2020): Graham scan issue caused weird answers for particular orientations - likely due to relying on atan2 to get the polar angle. Corrected using the split hull variant of Graham scan.
14 Likes
Sir you are a wizard! Thank you for the lengthy post actually, it helped me understand this much better than the articles i ran across.
This is exactly what i was trying to do!
2 Likes