Algorithm to calculate volume from manifold STL file

[Joheinz]

Hi *,

does anyone happen to have a description of an algorithm which
calculates the volume of an STL file. I do not need the result, e.g.
please tell me that this or that software can calculate the volume,
but I need to implement it myself. My search via google did not yield
any results.

For anyone not familiar with STL files. They are basically just a set
of points which compromise triangles together with a normal vector to
distinguish in which direction the face is pointing. But I am clueless
how I could calculate the volume from this information. Any pointers
would be very beneficial,

thank you,
Markus

[Z LeHericy]

I'm not much of a programmer, certaintly not of the level that would be needed for this, but essentially what you need is computational geometry.

The process you need to do is take the integral of the surface defined by the STL, however, that's not as simple for most shapes as it would be for, say, a cube.

I wish you luck on this quest, as it's going to take some incredibly complicated code to do what you need, assuming you want to make the program yourself. Otherwise, use a peice of software like netfabb to get the number, and then plug it in from there. There's got to be some software out there that you can interface with programatically and pass an STL to get the volume.

-Zeno LeHericy

//((=:Z:=))\\
INVENTIONS
Technologies
zinventions.com

--
You received this message because you are subscribed to the Google Groups "MakerBot Operators" group.
To post to this group, send email to make...@googlegroups.com.
To unsubscribe from this group, send email to makerbot+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/makerbot?hl=en.

[Shawn]

I'm a coder, but not in this area. But I'm sure I saw somewhere that
mentioned the process was to create an SVG of each layer. So you can do
a simple 2D volume calculation * the slice height to get the volume for
one slice. Then add it up. Of course that sounds WAY simpler than it
really is. And I could be wrong. Hope I'm at least pointing you in the
right direction.

Shawn

[Jon Watte]

Here's a simple algorithm that runs in O(num triangles):

1) Pick an axis -- any axis works, so pick something easy like X or Z.

2) Calculate the minimum point along this axis (dot product axis and vertex, and choose the vertex with the lowest value -- this is the minimum)

3) Define a reference plane, which is the plane that goes through the minimum point, and has the axis as its normal (if you're really pedantic, the negative of the axis will point "out" from the prism in step 4)

4) For each triangle, calculate the signed volume of the prism between the triangle and the reference plane. Sum all of these volumes.

5) That's it!

The "signed volume" is positive if the triangle normal has a positive dot product with the axis (a proper "capping" triangle on the prism) and negative if the triangle has a negative dot product with the axis. Note that a triangle that is perpendicular to the reference plane contributes zero volume, this is OK and expected.

Sincerely,

jw

[Jordan Miller]

I would guess MeshLab could calculate volume, or Netfabb basic.

But for a quick and dirty answer immediately, put it through good ol' skeinforge at 100% infill and progressively thinner layer heights. Make sure "Statistics" is turned on. This will be taking the limit as the measured volume approaches the true volume.

Skeinforge reports calculates the volume of your object from slicing (and turn off most features, such as Stretch, Clip, etc. etc.).

jordan

> --
> You received this message because you are subscribed to the Google Groups "MakerBot Operators" group.

> To view this discussion on the web visit https://groups.google.com/d/msg/makerbot/-/0BedLBG4MnEJ.

[Jordan Miller]

NetFabb Basic (the free version) can do it very very quickly. You probably just need to do an automated repair of the file first to make it manifold. It gives you the value in cm^3 (a.k.a. mL or cc).

[hellphish]

You're not reading the question. OP needs to implement the math himself.

[James McCracken]

LMGTFY...

 

http://www.gamedev.net/topic/312027-is-it-possible-to-calculate-the-volume-for-a-mesh/ gives:

float volume = 0;
int* index = I;
for (i = 0; i < T; i++)
{
    Vector3 v0 = V[*index++];
    Vector3 v1 = V[*index++];
    Vector3 v2 = V[*index++];
    volume += Dot(v0,Cross(v1,v2));
}
volume /= 6;


This link: http://stackoverflow.com/questions/1406029/how-to-calculate-the-volume-of-a-3d-mesh-object-the-surface-of-which-is-made-up gives a better explanation of how the above math works (basically, treat each triangle as a tetrahedron volume with the extra vertex at origin.  Since the algorithm honors inside/outside volumes, assuming vertices are ordered clockwise around a face, it is actually origin agnostic; you can translate the source model to make any point the origin and it will still give the same volume.

 

Good luck, matrix math is rarely fun in my experience...

[Joheinz]

Thank you James McCracken and Jon Watten for your suggestions,
especially for the idea to look for implementations in the game engine
world using mesh instead of STL as the search phrase.
I think I will get along with that.
Markus


2012/8/30 James McCracken <merl...@gmail.com>: