 |
|
| Computers Forum Index » Computer - Graphics (Algorithms) » Volume of a polyhedron... |
|
Page 1 of 1 |
|
| Author |
Message |
| Till Kranz... |
 Posted: Sat Sep 05, 2009 1:44 pm |
|
|
|
Guest
|
Hi,
given all the surface normals as well as the areas of all the sides of a
convex polyhedron. Is there a way to calculate its volume without first
determining all the vertices and edges?
Unfortunately I know next to nothing about polyhedra. My naive approaches
based on Gauss theorem only helped to convince me that this is a
nontrivial problem.
Does anyone know any algorithms or any pointers to papers/books that might
discuss this problem?
Thanks in advance
Till |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
| Posted: Sat Sep 05, 2009 6:42 pm |
|
|
|
Guest
|
"Till Kranz" <kranz at (no spam) theorie.physik.uni-goettingen.de> wrote in message
news:alpine.LMD.2.00.0909051141390.27023 at (no spam) Gene.theorie.physik.uni-goettingen.de...
Quote: given all the surface normals as well as the areas of all the sides of a
convex polyhedron. Is there a way to calculate its volume without first
determining all the vertices and edges?
You need to know a point per face of the polyhedron. Let face k have
area A[k], outer-pointing unit-length normal N[k], and a point P[k][1].
If you have m faces for 0 <= k < m, then the volume can be computed
from the Divergence Theorem as
V = sum_{k=0}^{m-1} A[k]*Dot(N[k], P[k][1])
How were you able to compute the face areas without knowing the
ordered lists of vertices per face? If face k has n[k] vertices
P[k][0] through P[k][n[k]-1], ordered counterclockwise as you view
the face from outside the polyhedron, then
A[k] = (1/6)*Dot(N[k], sum_{j=0}^{n[k]-1} Cross(P[k][j], P[k][j+1]))
where the j-indexing is modulo n[k]; that is, P[k][n[k]] is the same point
as P[k][0].
These formulas also work for non-convex polyhedra.
--
Dave Eberly
http://www.geometrictools.com |
|
|
| Back to top |
|
|
|
| Till Kranz... |
| Posted: Sat Sep 05, 2009 7:08 pm |
|
|
|
Guest
|
On Sat, 5 Sep 2009, Dave Eberly wrote:
Quote: You need to know a point per face of the polyhedron. Let face k have
area A[k], outer-pointing unit-length normal N[k], and a point P[k][1].
If you have m faces for 0 <= k < m, then the volume can be computed
from the Divergence Theorem as
V = sum_{k=0}^{m-1} A[k]*Dot(N[k], P[k][1])
I did not realize that I obviously need to know only one point per face.
The problem is that I know no point at all.
Quote:
How were you able to compute the face areas without knowing the
ordered lists of vertices per face?
A description of the whole problem is too long. The short version is: I
have a set of vectors and when I interpret them as the normals of a
polyhedron with their magnitude giving the area of the faces then I know
that the volume of this polyhedron is a quantity I am looking for. That's
why I have no vertices.
Thanks a lot anyway
Till |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
| Posted: Sat Sep 05, 2009 7:46 pm |
|
|
|
Guest
|
"Till Kranz" <kranz at (no spam) theorie.physik.uni-goettingen.de> wrote in message
news:alpine.LMD.2.00.0909051702050.10146 at (no spam) Gene.theorie.physik.uni-goettingen.de...
Quote: I did not realize that I obviously need to know only one point per face.
The problem is that I know no point at all.
If all you have is the plane normal and the area of the face, you
cannot know where in space the plane is. Thus, you need to know
a point on the face (or plane).
--
Dave Eberly
http://www.geometrictools.com |
|
|
| Back to top |
|
|
|
| Kenneth Sloan... |
| Posted: Sat Sep 05, 2009 9:26 pm |
|
|
|
Guest
|
Dave Eberly wrote:
Quote: "Till Kranz" <kranz at (no spam) theorie.physik.uni-goettingen.de> wrote in message
news:alpine.LMD.2.00.0909051702050.10146 at (no spam) Gene.theorie.physik.uni-goettingen.de...
I did not realize that I obviously need to know only one point per face.
The problem is that I know no point at all.
If all you have is the plane normal and the area of the face, you
cannot know where in space the plane is. Thus, you need to know
a point on the face (or plane).
--
Dave Eberly
http://www.geometrictools.com
The parenthetical comment is important! Don't hide it!
Indeed - you can use any point on the plane. It doesn't have to be a
vertex, and it doesn't need to be in (or even close to) the "face".
It seems to me that if you have the normals and points (on the planes),
then you don't really need the areas - in the sense that you could, in
principle, construct the polyhedron and determine the areas.
Which means that normals, points on the planes, and areas must have some
redundancy.
So...what can you remove? Well, you might know the (signed) distance
from the origin (any origin, pick an origin) to the planes. That's only
one scalar per face, instead of the 3 necessary to nail down a specific
point.
And...if you know the (signed) distance to the plane and the area of the
face in the plane - do you need the surface normal? I don't think so.
In the usual formula, you use the point on the plane and the surface
normal to compute the (signed) distance to the plane.
So...does the original problem allow you to specify:
a) area of face
b) signed distance from Origin to the plane of the face
That appears to be the minimal information required to compute a volume.
That's two scalars per face.
In the alternative, you could use:
a) the planes (everything else can be derived from this)
That's 3 (independent) scalars per face. Is there redundancy here, or
did I make a horrible mistake, above?
the answer (I think) is that "areas/distances" only nails down an
equivalence class of shapes, all with the same volume (and perhaps other
properties...), while "planes" nails down a unique shape.
Back over to the OP to see if his original problem needs unique shapes,
or if it's abstract enough that the family of same volume (plus other
things) shapes is sufficient.
Everyone else can ponder: what properties other than volume are shared
by the class of shapes identified by "areas/distances".
--
Kenneth Sloan KennethRSloan at (no spam) gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/ |
|
|
| Back to top |
|
|
|
| Hans-Bernhard Bröker... |
| Posted: Sun Sep 06, 2009 4:26 pm |
|
|
|
Guest
|
Till Kranz wrote:
Quote: I have a set of vectors and when I interpret them as the normals of a
polyhedron with their magnitude giving the area of the faces then I
know that the volume of this polyhedron is a quantity I am looking
for.
That's a little hard to believe, since normals and areas alone just
don't define a polyhedron unambiguously. So how could the volume of an
un-defined polyhedron be useful for anything? The answer you're looking
for isn't defined by the data you have. |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Sun Sep 06, 2009 6:39 pm |
|
|
|
Guest
|
Kenneth Sloan wrote:
Quote: a) area of face
b) signed distance from Origin to the plane of the face
That appears to be the minimal information required to compute a volume.
That's two scalars per face.
Counter-example in 2D, where planes are lines. Take x and y axes, and
then take a line that is r units away from origin. The set of the latter
type of lines can be parametrized by the angle that its normal forms
with the x axis. The volume (area) of the convex shape bounded by the
lines varies with that angle.
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
| Posted: Sun Sep 06, 2009 7:34 pm |
|
|
|
Guest
|
"Kaba" <none at (no spam) here.com> wrote in message
news:MPG.250df635db4a7f4898983a at (no spam) news.cc.tut.fi...
Quote: Kenneth Sloan wrote:
a) area of face
b) signed distance from Origin to the plane of the face
That appears to be the minimal information required to compute a volume.
That's two scalars per face.
Counter-example in 2D, where planes are lines. Take x and y axes, and
then take a line that is r units away from origin. The set of the latter
type of lines can be parametrized by the angle that its normal forms
with the x axis. The volume (area) of the convex shape bounded by the
lines varies with that angle.
The area does vary with angle, but why do you believe this contradicts
what Ken said? I posted the volume of a polyhedron, but I was missing
a factor. It should be
V = (1/3)*sum_{k=0}^{m-1} A[k]*Dot(N[k], P[k])
where N[k] is an outer-pointing unit-length normal for the plane of face k,
P[k] is a point on the face, and A[k] is the area of the face. Note that
this is
V = (1/3)*sum_{k=0}^{m-1} A[k]*d[k]
where d[k] is the signed distance from the origin of the plane of face k.
For each face, you need only (a) and (b) as Ken posted.
In 2D, the area of a polygon is
A = (1/2)*sum_{k=0}^{m-1} L[k]*Dot(N[k],P[k])
= (1/2)*sum_{k=0}^{m-1} L[k]*d[k]
where N[k] is an outer-pointing unit-length normal for the line of edge k,
P[k] is a point on the edge, L[k] is the length of the edge, and d[k] is the
signed distance from the origin of the line of edge k.
In your example, let the triangle be in the first quadrant and have normals
N[0] = (1,0), N[1] = (c,s), and N[2] = (0,1). The vertices are P[0] =
(0,0), P[1] = (r/c,0), and P[2] = (0,r/s). The lengths are L[0] = r/c,
L[1] = r*sqrt(1/c^2 + 1/s^2), and L[2] = r/s. The signed distances are
d[0] = 0, d[1] = r, and d[2] = 0. The area is
A = (1/2)*(L[0]*d[0] + L[1]*d[1] + L[2]*d[2])
= (1/2)*r^2*sqrt(1/c^2 + 1/s^2)
--
Dave Eberly
http://www.geometrictools.com |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Sun Sep 06, 2009 10:04 pm |
|
|
|
Guest
|
Dave Eberly wrote:
Quote: The area does vary with angle, but why do you believe this contradicts
what Ken said? I posted the volume of a polyhedron, but I was missing
a factor. It should be
V = (1/3)*sum_{k=0}^{m-1} A[k]*Dot(N[k], P[k])
where N[k] is an outer-pointing unit-length normal for the plane of face k,
P[k] is a point on the face, and A[k] is the area of the face. Note that
this is
V = (1/3)*sum_{k=0}^{m-1} A[k]*d[k]
where d[k] is the signed distance from the origin of the plane of face k.
For each face, you need only (a) and (b) as Ken posted.
Oops, I was ignoring the area requirements, so never mind.
Let me try to check that formula.
f(x) = [x_1, ..., x_3] / 3
=>
(div f)(x) = 1
By Gauss's theorem:
volume
= int_V 1 dV
= int_V (div f)(x) dV
= int_A dot(f(x), dA)
= sum_{k = 0}^{m - 1} int_{A_k} dot(f(x), dA)
= (1 / 3) sum_{k = 0}^{m - 1} int_{A_k} dot(x, dA)
For a given triangle with vertices (p1, p2, p3), parametrize it by:
x(u, v) = p1 + u(p2 - p1) + v(p3 - p1)
Thus
(dx/du)(u, v) = p2 - p1 = e1
(dx/dv)(u, v) = p3 - p1 = e2
n = n(u, v) = cross(p2 - p1, p3 - p1)
and
int_{A_k} dot(x, dA)
= int_0^1 int_0^{1 - u} dot(x(u, v), n(u, v)) dv du
= int_0^1 int_0^{1 - u} dot(x(u, v), n) dv du
= int_0^1 int_0^{1 - u} dot(p1 + u e1 + v e2, n) dv du
= int_0^1 int_0^{1 - u} dot(p1 + u e1, n) + v dot(e2, n) dv du
= int_0^1 (1 - u) dot(p1 + u e1, n) + (1/2) (1 - u)^2 dot(e2, n) du
= int_0^1 (1 - u) dot(p1, n) + (1 - u)u dot(e1, n) +
(1/2) (1 - u)^2 dot(e2, n) du
= int_0^1 u dot(p1, n) + u(1 - u) dot(e1, n) + (1/2) u^2 dot(e2, n) du
= int_0^1 u dot(p1, n) + (u - u^2) dot(e1, n) + (1/2) u^2 dot(e2, n) du
= int_0^1 u dot(p2, n) - u^2 dot(e1, n) + (1 / 2) u^2 dot(e2, n) du
= (1 / 2) dot(p2, n) - (1 / 3) dot(e1, n) + (1 / 2) (1 / 3) dot(e2, n)
= (1 / 6) (dot(p1, n) + dot(p2, n) + dot(p3, n))
= (1 / 2) dot(c, n)
where c = (p1 + p2 + p3) / 3, i.e. the center point. If N is the unit
vector corresponding to n, then
n = |cross(p2 - p1, p3 - p1)| N = 2 a_k N
where a_k is the area of the triangle k.
Thus
int_{A_k} dot(x, dA) = a_k dot(c, N)
and the final result is:
volume
= (1 / 3) sum_{k = 0}^{m - 1} int_{A_k} dot(x, dA)
= (1 / 3) sum_{k = 0}^{m - 1} a_k dot(c_k, N)
However, we can move each c_k in its plane without affecting the dot
product and thus we can relax the requirement for c_k: it only needs to
lie on the triangle's plane. Further, one can define
d_k = dot(c_k, N)
where d_k is the signed distance of the triangle's plane from the
origin, in which case
volume
= (1 / 3) sum_{k = 0}^{m - 1} a_k d_k
So.. Agreed:) It's a bit unintuitive that the given information is
enough.
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Sun Sep 06, 2009 10:25 pm |
|
|
|
Guest
|
Kaba wrote:
Quote: volume
= (1 / 3) sum_{k = 0}^{m - 1} a_k d_k
So.. Agreed:) It's a bit unintuitive that the given information is
enough.
.... although for the convex polyhedra the result is very intuitive. Each
term (1/3) a_k d_k is the volume of a pyramid whose tip is in the origin
and the base is the triangle. The faces of polyhedra can be triangulized
and then it can be partitioned into m pyramids. That would have given a
much shorter derivation for convex polyhedra, but by Gauss the result
generalizes to concave polyhedra also.
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Mon Sep 07, 2009 1:15 am |
|
|
|
Guest
|
Kenneth Sloan wrote:
Quote: Everyone else can ponder: what properties other than volume are shared
by the class of shapes identified by "areas/distances".
Before that: are there area-distance combinations which do not
correspond to any polyhedron?
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| Dave Eberly... |
| Posted: Mon Sep 07, 2009 4:02 am |
|
|
|
Guest
|
"Kaba" <none at (no spam) here.com> wrote in message
news:MPG.250e52d5f25c837298983d at (no spam) news.cc.tut.fi...
Quote: Before that: are there area-distance combinations which do not
correspond to any polyhedron?
The same question may be asked for the 2D problem. The answer
is "yes". Consider three lengths, L0 = 1, L1 = 0.1, and L2 = 0.1.
It does not matter how you specify the signed distances. It is not
possible to construct a triangle with edges of these lengths.
--
Dave Eberly
http://www.geometrictools.com |
|
|
| Back to top |
|
|
|
| Kaba... |
| Posted: Mon Sep 07, 2009 8:15 pm |
|
|
|
Guest
|
Dave Eberly wrote:
Quote: "Kaba" <none at (no spam) here.com> wrote in message
news:MPG.250e52d5f25c837298983d at (no spam) news.cc.tut.fi...
Before that: are there area-distance combinations which do not
correspond to any polyhedron?
The same question may be asked for the 2D problem. The answer
is "yes". Consider three lengths, L0 = 1, L1 = 0.1, and L2 = 0.1.
It does not matter how you specify the signed distances. It is not
possible to construct a triangle with edges of these lengths.
That's right. Checking if an area-distance combination forms some
polyhedron is probably a hard problem too. So it seems OP's problem
statement needs to be reconsidered, even if he had the distance
information.
--
http://kaba.hilvi.org |
|
|
| Back to top |
|
|
|
| mike... |
| Posted: Tue Sep 08, 2009 3:54 am |
|
|
|
Guest
|
In article <MPG.250f5e26b0d4f9b498983e at (no spam) news.cc.tut.fi>, none at (no spam) here.com
says...
Quote: Dave Eberly wrote:
"Kaba" <none at (no spam) here.com> wrote in message
news:MPG.250e52d5f25c837298983d at (no spam) news.cc.tut.fi...
Before that: are there area-distance combinations which do not
correspond to any polyhedron?
The same question may be asked for the 2D problem. The answer
is "yes". Consider three lengths, L0 = 1, L1 = 0.1, and L2 = 0.1.
It does not matter how you specify the signed distances. It is not
possible to construct a triangle with edges of these lengths.
That's right. Checking if an area-distance combination forms some
polyhedron is probably a hard problem too. So it seems OP's problem
statement needs to be reconsidered, even if he had the distance
information.
True - and even if, for the sake of arguement, the data is consistent is
still doesn't define a unique polyhedron. For example, 6 faces with
areas of 1 square unit each and with two each having normals (1,0,0),
(0,1,0), and (0,0,1) could form a 1x1x1 cube with volume 1 unit cubed,
or could form a shape like a 'corner-cube' (or 'cube'corner' according
to some) with zero volume.
Mike |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Wed Nov 25, 2009 2:44 pm
|
|