How to calculate the smallest tetrahedron that encloses a given sphere?
Author
The title basically sums it up. I have a sphere, and I need to find a tetrahedron that contains the sphere. Preferably one that is as small as possible, but I don't care about it's rotation.
I'm using this in a custom-made spacial division algo that I'm also using to render iso-surfaces (just so you don't think it's homework)
Thanks for your time.
Hi,
I just used some formulars and came up with the following:
let m be the mid-point of the sphere
let r be the radius of the sphere
let a1,a2,a3,a4 be the corners of the tetrahedron
then
a1 = m + (0|0|2*r)
a2 = m + 3/sqrt(6) * (0|2*r|-2*r)
a3 = m + 3/sqrt(6) * (sqrt(3)*r| -r | -2*r )
a4 = m + 3/sqrt(6) * (sqrt(3)*r| -r | -2*r )
let me know if this works (if not I made some error in the formulars)
I just used some formulars and came up with the following:
let m be the mid-point of the sphere
let r be the radius of the sphere
let a1,a2,a3,a4 be the corners of the tetrahedron
then
a1 = m + (0|0|2*r)
a2 = m + 3/sqrt(6) * (0|2*r|-2*r)
a3 = m + 3/sqrt(6) * (sqrt(3)*r| -r | -2*r )
a4 = m + 3/sqrt(6) * (sqrt(3)*r| -r | -2*r )
let me know if this works (if not I made some error in the formulars)
Assuming unit sphere centered on origin.
constant S = sqrt(3)
p0 = (-3, -S, -1),
p1 = ( 0, 2*S, -1),
p2 = ( 3, -S, -1),
p3 = ( 0, .5, 2)
should be the enclosing tetrahedron. (you should verify this graphically, though, I just scribbled down the math in a hurry).
So you can just scale these values by the radius.
constant S = sqrt(3)
p0 = (-3, -S, -1),
p1 = ( 0, 2*S, -1),
p2 = ( 3, -S, -1),
p3 = ( 0, .5, 2)
should be the enclosing tetrahedron. (you should verify this graphically, though, I just scribbled down the math in a hurry).
So you can just scale these values by the radius.
Quote:Original post by dragongame
a2 = m + 3/sqrt(6) * (0|2*r|-2*r)
3/sqrt(6)... did you let a 45-degree angle slip in there?
Mhhhh ...
what I did was the following
The tetrahedron is a composed of equal sided triangles.
So assume the sphere is centered at the origon.
First I just looked at the x/z Plane.
So the sphere becomes a circle and the tetrahedron a triangle.
So
The inneradius is ri with
ri = sqrt(3)/6 * tringle_side = radius of our sphere ( so now called r )
The outer radius is ru (on which the tringels point lies) with
ru = 2*ri
a1 = (0,0,2*r);
In the next step I picked the x/y plane.
Same as above
a'2 = (0,2*r,0);
For a'3,a'4 y must be -r, because ri + ru = height of triangle.
so
a'3 = (x,-r,0)
a'4 = (-x,-r,0)
To get x I used that
||a'3|| = 2*r
=> sqrt(x^2 + r^2) = 2*r
=> x^2 + r^2 = 4*r^2
=> x^2 = 3*r^2
=> x = sqrt(3)*r
=> a'3 = (sqrt(3)*r,-r,0) and a'4 = (-sqrt(3)*r,-r,0);
So but a'2, a'3 and a'4 are not what we want because that would just include the upperhalf of the sphere.
So let's translate them to the right direction.
a2 = a1 + z*(a'2 - a1);
a3 = a1 + z*(a'3 - a1);
a4 = a1 + z*(a'4 - a1);
||z*(a'2 - a1)|| = triangle size = (6/sqrt(3) ) * r
=> sqrt(4*r^2*z^2 + 4*r^2*z^2) = 6*r / sqrt(3)
=> 2*r*z*sqrt(2) = 6*r*/sqrt(3)
=> z = 3 / ( sqrt(3) * sqrt(2) ) = 3 / sqrt(6)
And that made my formulars if you find something wrong let me know
Edit: I wish the forum had a math mode (eg. latex)
what I did was the following
The tetrahedron is a composed of equal sided triangles.
So assume the sphere is centered at the origon.
First I just looked at the x/z Plane.
So the sphere becomes a circle and the tetrahedron a triangle.
So
The inneradius is ri with
ri = sqrt(3)/6 * tringle_side = radius of our sphere ( so now called r )
The outer radius is ru (on which the tringels point lies) with
ru = 2*ri
a1 = (0,0,2*r);
In the next step I picked the x/y plane.
Same as above
a'2 = (0,2*r,0);
For a'3,a'4 y must be -r, because ri + ru = height of triangle.
so
a'3 = (x,-r,0)
a'4 = (-x,-r,0)
To get x I used that
||a'3|| = 2*r
=> sqrt(x^2 + r^2) = 2*r
=> x^2 + r^2 = 4*r^2
=> x^2 = 3*r^2
=> x = sqrt(3)*r
=> a'3 = (sqrt(3)*r,-r,0) and a'4 = (-sqrt(3)*r,-r,0);
So but a'2, a'3 and a'4 are not what we want because that would just include the upperhalf of the sphere.
So let's translate them to the right direction.
a2 = a1 + z*(a'2 - a1);
a3 = a1 + z*(a'3 - a1);
a4 = a1 + z*(a'4 - a1);
||z*(a'2 - a1)|| = triangle size = (6/sqrt(3) ) * r
=> sqrt(4*r^2*z^2 + 4*r^2*z^2) = 6*r / sqrt(3)
=> 2*r*z*sqrt(2) = 6*r*/sqrt(3)
=> z = 3 / ( sqrt(3) * sqrt(2) ) = 3 / sqrt(6)
And that made my formulars if you find something wrong let me know
Edit: I wish the forum had a math mode (eg. latex)
Well this is how I would do it; a perfect tetrahedron is give by:
Unit length vertices:
v0 = (0, 0, 1)
v1 = (2 * sqr(2) /3, 0, −1/3)
v2 = (−sqr(2)/3, sqr(6)/3, −1/3)
v3 = (−sqr(2)/3, − sqr(6)/3, −1/3)
Triangle connectivity:
(0, 1, 2) (0, 2, 3) (0, 3, 1) (1, 3, 2)
Since it is perfect then the distance to the origin of any of the faces must pass by the origin of an inscribed sphere, so if you calculate the plane equation of any of the faces, the fourth term of the equation must be the distance to the origin of that smaller sphere, that is
d = distance part of Plane passing by (v[0], v[1, v[2])
now all you need to do is to scale everything by the ratio
r = sphereRadious / d
Unit length vertices:
v0 = (0, 0, 1)
v1 = (2 * sqr(2) /3, 0, −1/3)
v2 = (−sqr(2)/3, sqr(6)/3, −1/3)
v3 = (−sqr(2)/3, − sqr(6)/3, −1/3)
Triangle connectivity:
(0, 1, 2) (0, 2, 3) (0, 3, 1) (1, 3, 2)
Since it is perfect then the distance to the origin of any of the faces must pass by the origin of an inscribed sphere, so if you calculate the plane equation of any of the faces, the fourth term of the equation must be the distance to the origin of that smaller sphere, that is
d = distance part of Plane passing by (v[0], v[1, v[2])
now all you need to do is to scale everything by the ratio
r = sphereRadious / d
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
