- Source: Line-cylinder intersection
Line-cylinder intersection is the calculation of any points of intersection, given an analytic geometry description of a line and a cylinder in 3d space.
An arbitrary line and cylinder may have no intersection at all. Or there may be one or two points of intersection. Or a line may lie along the surface of a cylinder, parallel to its axis, resulting in infinitely many points of intersection. The method described here distinguishes between these cases, and when intersections exist, computes their positions.
The term “cylinder” can refer to a three-dimensional solid or, as in this article, only the curved external surface of the solid. This is why a line piercing a cylinder's volume is considered to have two points of intersection: the surface point where it enters and the one where it leaves. See § end caps.
A key intuition of this sort of intersection problem is to represent each shape as an equation which is true for all points on the shape. Solving them as a system of two simultaneous equations finds the points which belong to both shapes, which is the intersection. The equations below were solved using Maple.
This method has applications in computational geometry, graphics rendering, shape modeling, physics-based modeling, and related types of computational 3d simulations. This has led to various implementations. This method is closely related to Line–sphere intersection.
Cylinder equation, end caps excluded
Let
b
¯
=
(
b
x
,
b
y
,
b
z
)
{\displaystyle {\bar {b}}=(b_{x},b_{y},b_{z})}
be the cylinder base (or one endpoint),
a
^
=
(
a
x
,
a
y
,
a
z
)
{\displaystyle {\hat {a}}=(a_{x},a_{y},a_{z})}
be the cylinder axis unit vector,
cylinder radius
r
{\displaystyle r}
, and height (or axis length)
h
{\displaystyle h}
. The cylinder may be in any orientation.
The equation for an infinite cylinder can be written as
‖
a
^
×
(
p
¯
−
b
¯
)
‖
=
r
{\displaystyle \lVert {\hat {a}}\times ({\bar {p}}-{\bar {b}})\rVert =r}
where
p
¯
=
(
x
,
y
,
z
)
{\displaystyle {\bar {p}}=(x,\ y,\ z)}
is any point on the cylinder surface. The equation simply states that points
p
¯
{\displaystyle {\bar {p}}}
are exactly at Euclidean distance
r
{\displaystyle r}
from the axis
a
^
{\displaystyle {\hat {a}}}
starting from point
b
¯
{\displaystyle {\bar {b}}}
, where
r
{\displaystyle r}
is measured in units of
‖
a
^
‖
{\displaystyle \lVert {\hat {a}}\rVert }
. Note that
‖
a
^
‖
=
1
{\displaystyle \lVert {\hat {a}}\rVert =1}
if
a
^
{\displaystyle {\hat {a}}}
is a unit vector. Because both sides of the equation are always positive or zero, we can square it, and eliminate the square root operation in the Euclidean norm on the left side:
‖
a
^
×
(
p
¯
−
b
¯
)
‖
2
=
r
2
{\displaystyle {\lVert {\hat {a}}\times ({\bar {p}}-{\bar {b}})\rVert }^{2}=r^{2}}
Point
p
¯
{\displaystyle {\bar {p}}}
is at signed distance
t
=
a
^
⋅
(
p
¯
−
b
¯
)
{\displaystyle t={\hat {a}}\cdot ({\bar {p}}-{\bar {b}})}
from the base along the axis. Therefore, the two equations defining the cylinder, excluding the end caps, is
‖
a
^
×
(
p
¯
−
b
¯
)
‖
2
=
r
2
{\displaystyle {\lVert {\hat {a}}\times ({\bar {p}}-{\bar {b}})\rVert }^{2}=r^{2}}
0
≤
a
^
⋅
(
p
¯
−
b
¯
)
≤
h
{\displaystyle 0\leq {\hat {a}}\cdot ({\bar {p}}-{\bar {b}})\leq h}
The line
Let
p
¯
=
n
^
d
{\displaystyle {\bar {p}}={\hat {n}}d}
be a line through origin,
n
^
{\displaystyle {\hat {n}}}
being the unit vector,
and
d
{\displaystyle d}
the distance from origin.
If your line does not pass through origin but point
o
¯
{\displaystyle {\bar {o}}}
, i.e. your line is
o
¯
+
n
^
d
{\displaystyle {\bar {o}}+{\hat {n}}d}
,
replace
b
¯
{\displaystyle {\bar {b}}}
with
(
b
¯
−
o
¯
)
{\displaystyle ({\bar {b}}-{\bar {o}})}
everywhere; distance
d
{\displaystyle d}
is then the distance from
o
¯
{\displaystyle {\bar {o}}}
.
The intersection problem
The intersection between the line and the cylinder is
‖
a
^
×
(
n
^
d
−
b
¯
)
‖
2
=
r
2
{\displaystyle {\lVert {\hat {a}}\times ({\hat {n}}d-{\bar {b}})\rVert }^{2}=r^{2}}
0
≤
t
≤
h
{\displaystyle 0\leq t\leq h}
where the signed distance along the axis
t
{\displaystyle t}
is
t
=
a
^
⋅
(
n
^
d
−
b
¯
)
{\displaystyle t={\hat {a}}\cdot ({\hat {n}}d-{\bar {b}})}
Solution
Rearranging the first equation gives a quadratic equation for
d
{\displaystyle d}
. Solving that for
d
{\displaystyle d}
gives
d
=
(
n
^
×
a
^
)
⋅
(
b
¯
×
a
^
)
±
(
n
^
×
a
^
)
⋅
(
n
^
×
a
^
)
r
2
−
(
a
^
⋅
a
^
)
(
b
¯
⋅
(
n
^
×
a
^
)
)
2
(
n
^
×
a
^
)
⋅
(
n
^
×
a
^
)
{\displaystyle d={\frac {({\hat {n}}\times {\hat {a}})\cdot ({\bar {b}}\times {\hat {a}})\pm {\sqrt {({\hat {n}}\times {\hat {a}})\cdot ({\hat {n}}\times {\hat {a}})r^{2}-({\hat {a}}\cdot {\hat {a}})({\bar {b}}\cdot ({\hat {n}}\times {\hat {a}}))^{2}}}}{({\hat {n}}\times {\hat {a}})\cdot ({\hat {n}}\times {\hat {a}})}}}
where
(
a
^
⋅
a
^
)
=
1
{\displaystyle ({\hat {a}}\cdot {\hat {a}})=1}
if
a
^
{\displaystyle {\hat {a}}}
is a unit vector. If
‖
n
^
×
a
^
‖
=
0
{\displaystyle \lVert {\hat {n}}\times {\hat {a}}\rVert =0}
the line is parallel to the axis, and there is no intersection, or the intersection is a line. If
(
n
^
×
a
^
)
⋅
(
n
^
×
a
^
)
r
2
−
(
a
^
⋅
a
^
)
(
b
¯
⋅
(
n
^
×
a
^
)
)
2
<
0
{\displaystyle ({\hat {n}}\times {\hat {a}})\cdot ({\hat {n}}\times {\hat {a}})r^{2}-({\hat {a}}\cdot {\hat {a}})({\bar {b}}\cdot ({\hat {n}}\times {\hat {a}}))^{2}<0}
the line does not intersect the cylinder.
Solving
d
{\displaystyle d}
only gives you the distance at which the line intersects the infinite cylinder. To see if the intersection occurs within the part we consider the actual cylinder, we need to check if the signed distance
t
{\displaystyle t}
from the cylinder base
b
¯
{\displaystyle {\bar {b}}}
along the axis
a
^
{\displaystyle {\hat {a}}}
to the intersection
p
¯
=
n
^
d
{\displaystyle {\bar {p}}={\hat {n}}d}
is within zero and the length of the cylinder:
0
≤
t
≤
h
{\displaystyle 0\leq t\leq h}
where
t
{\displaystyle t}
is still
t
=
a
^
⋅
(
n
^
d
−
b
¯
)
{\displaystyle t={\hat {a}}\cdot ({\hat {n}}d-{\bar {b}})}
End caps
The above assumes that the cylinder does not have end caps; they must be checked for separately.
The seam where the end cap meets the cylinder is assumed to belong to the cylinder, and is excluded from the end cap.
= Hemispherical end caps
=Hemispherical end caps are just half-spheres at both ends of the cylinder. This object is sometimes called a capsule,
or possibly fixed-radius linearly-swept sphere.
Cylinder height
h
{\displaystyle h}
does not include the end caps. If
H
{\displaystyle H}
is the cylinder height including both hemispherical end caps, then
h
=
H
−
2
r
{\displaystyle h=H-2r}
.
Check if the line
p
¯
=
n
^
d
{\displaystyle {\bar {p}}={\hat {n}}d}
intersects
either sphere: center
c
¯
=
b
¯
{\displaystyle {\bar {c}}={\bar {b}}}
or
c
¯
=
b
¯
+
a
^
h
{\displaystyle {\bar {c}}={\bar {b}}+{\hat {a}}h}
and radius
r
{\displaystyle r}
:
d
=
n
^
⋅
c
¯
±
(
n
^
⋅
c
¯
)
2
+
r
2
−
(
c
¯
⋅
c
¯
)
{\displaystyle d={\hat {n}}\cdot {\bar {c}}\pm {\sqrt {({\hat {n}}\cdot {\bar {c}})^{2}+r^{2}-({\bar {c}}\cdot {\bar {c}})}}}
If
(
n
^
⋅
c
¯
)
2
+
r
2
−
(
c
¯
⋅
c
¯
)
<
0
{\displaystyle ({\hat {n}}\cdot {\bar {c}})^{2}+r^{2}-({\bar {c}}\cdot {\bar {c}})<0}
the line does not intersect the end cap sphere.
If there are solutions
d
{\displaystyle d}
, accept only those that hit the actual end cap hemisphere:
−
r
≤
t
<
0
{\displaystyle -r\leq t<0}
or
h
<
t
≤
h
+
r
{\displaystyle h
where, once again,
t
=
a
^
⋅
(
n
^
d
−
b
¯
)
{\displaystyle t={\hat {a}}\cdot ({\hat {n}}d-{\bar {b}})}
= Planar end caps
=Planar end caps are circular regions, radius
r
{\displaystyle r}
, in planes centered at
c
¯
=
b
¯
{\displaystyle {\bar {c}}={\bar {b}}}
and
c
¯
=
b
¯
+
a
^
h
{\displaystyle {\bar {c}}={\bar {b}}+{\hat {a}}h}
, with unit normal vectors
−
a
^
{\displaystyle -{\hat {a}}}
and
a
^
{\displaystyle {\hat {a}}}
, respectively. The line
n
^
d
{\displaystyle {\hat {n}}d}
intersects the plane if and only if
(
n
^
d
−
c
¯
)
⋅
a
^
=
0
{\displaystyle ({\hat {n}}d-{\bar {c}})\cdot {\hat {a}}=0}
Solving d is simple,
d
=
a
^
⋅
c
¯
a
^
⋅
n
^
{\displaystyle d={\frac {{\hat {a}}\cdot {\bar {c}}}{{\hat {a}}\cdot {\hat {n}}}}}
Note that if
a
^
⋅
n
^
=
0
{\displaystyle {\hat {a}}\cdot {\hat {n}}=0}
the line is parallel to the end cap plane (and also perpendicular to the cylinder axis). Finally, if and only if
(
n
^
d
−
c
¯
)
⋅
(
n
^
d
−
c
¯
)
<
r
2
{\displaystyle ({\hat {n}}d-{\bar {c}})\cdot ({\hat {n}}d-{\bar {c}})
the intersection point
n
^
d
{\displaystyle {\hat {n}}d}
is within the actual end cap (the circular region in the plane).
Unit normal vector at an intersection point
One of the many applications for this algorithm is in ray tracing, where the cylinder unit normal vector
v
^
{\displaystyle {\hat {v}}}
at the intersection
n
^
d
{\displaystyle {\hat {n}}d}
is needed for refracted and reflected rays and lighting.
The equations below use the signed distance
t
{\displaystyle t}
to the intersection point
n
^
d
{\displaystyle {\hat {n}}d}
from base
b
¯
{\displaystyle {\bar {b}}}
along the axis
a
^
{\displaystyle {\hat {a}}}
, which is always
t
=
a
^
⋅
(
n
^
d
−
b
¯
)
{\displaystyle t={\hat {a}}\cdot ({\hat {n}}d-{\bar {b}})}
For the cylinder surface (excluding the end caps, but including the seam),
0
≤
t
≤
h
{\displaystyle 0\leq t\leq h}
:
v
^
=
n
^
d
−
a
^
t
−
b
¯
‖
n
^
d
−
a
^
t
−
b
¯
‖
{\displaystyle {\hat {v}}={\frac {{\hat {n}}d-{\hat {a}}t-{\bar {b}}}{\lVert {\hat {n}}d-{\hat {a}}t-{\bar {b}}\rVert }}}
For a spherical end cap at the base,
−
r
≤
t
<
0
{\displaystyle -r\leq t<0}
:
v
^
=
n
^
d
−
b
¯
r
{\displaystyle {\hat {v}}={\frac {{\hat {n}}d-{\bar {b}}}{r}}}
for a spherical end cap at the other end,
h
<
t
≤
h
+
r
{\displaystyle h
:
v
^
=
n
^
d
−
b
¯
−
a
^
h
r
{\displaystyle {\hat {v}}={\frac {{\hat {n}}d-{\bar {b}}-{\hat {a}}h}{r}}}
For a planar end cap at the base,
t
=
0
{\displaystyle t=0}
:
v
^
=
−
a
^
{\displaystyle {\hat {v}}=-{\hat {a}}}
for a planar end cap at the other end,
t
=
h
{\displaystyle t=h}
:
v
^
=
a
^
{\displaystyle {\hat {v}}={\hat {a}}}
See also
Line–sphere intersection
Line–plane intersection
Intersection (geometry)
References
External links
Collections of intersection techniques for computational geometry:
Intersections (Ray Tracing Resources Page) by Eric Haines, table of links for many intersection calculations, including ray-cylinder.
collection of ray-surface intersectors for GPU shaders by Inigo Quilez, including ray-cylinder.
Derivations which require cylinder be in a constrained orientation:
line - cylinder intersection in Johannes Buchner's collection of Line-Intersection formulae
Line - Cylinder intersection - at IllusionCatalyst
Line Cylinder Intersection at Mathematics Stack Exchange (math.stackexchange.com)
Partial solution:
Calculating ray-cylinder intersection points at Mathematics Stack Exchange (math.stackexchange.com)
Kata Kunci Pencarian:
- Line-cylinder intersection
- Intersection (geometry)
- Cylinder
- Cylindrical coordinate system
- Intersection
- Intersection curve
- Cylindrical lens
- Bounding volume
- Right circular cylinder
- List of gear nomenclature