Integral Properties of Geometric Models
Integral properties of geometric models, as the name implies, are properties of the models found by adding things up. The fundamental ones are surface-area and volume. Others are the position of the model's centroid, its moments of inertia, and its mass.
In general it's very hard to get exact answers to integral properties calculations on geometric models, and very easy to get answers within 0.5% or so. For the vast majority of engineering applications such approximations are good enough.
Generally speaking, area-type calculations are easy for b-rep modellers and hard for set-theoretic ones, and volume-type calculations are the other way round. This is not surprising when one considers that b-rep modellers are representing the boundary of a solid, and set-theoretic models are representing its interior.
Areas
Let's start with surface area. Usually the easiest way to compute this is to facet the model and add up the areas of the facets. Most modellers have faceters so that they can drive depth buffer displays, and an area function can easily be added to them. All that's needed is a procedure to work out the area of a polygon:
We scan the polygon vertices in order adding up the areas of the triangles - 012 023 034... But what about concavities? Rather neatly these get sorted out automatically if we do the area sum with vector products. Recall that the vector product of two sides of a triangle has double the area of the triangle as its magnitude, so the area of triangle 012 is |axb|/2. We just scan round the vertices of the polygon adding up the vector products of pairs of triangle edges. The neat thing is that concavities give a vector product pointing in the opposite direction (the shaded triangle) to the others and are thus automatically subtracted. We just take half the magnitude of the resultant vector.
The sum of the facet areas is only an approximation to the true area, of course. But if the facets don't overlap and don't have gaps, and if they don't make too coarse an approximation to curved faces of the model, then the aswer will be pretty accurate.
Trying to work out surface areas directly is not easy. The area of a cylinder meeting a plane isn't too hard:
But what about a cylinder meeting a cylinder:
We have the same combinatorial problem that we had when considering the types of edges that needed to be dealt with in b-rep models.
Finally, on areas, faceted approximations to parametric patches are pretty easy. We just rule a set of iso-parametric lines and add up the areas of the little (approximate) rectangles between them:
Volumes
Often, the easiest way to calculate an approximation to the volume of a geometric model is to use a Monte Carlo technique. This is really dumb, but works surprisingly well. Consider a two-dimensional example. Suppose we want the `volume' of the piano shape with an elliptical hole:
The Monte Carlo technique starts with a box round the problem. It then throws random points in the box and membership tests them against the model, keeping a count of all of them, and a count of the number testing as in solid. The approximate `volume' is then the `volume' of the box times the ratio of the two counts. This works well for set-theoretic modellers as they can do membership tests very quickly.
Why random points?
Because a regular grid may well introduce bias, especially if surfaces in the model are aligned with the coordinate directions, as they often are for real engineering.
The only problem is that membership testing in b-rep models is a pain in the neck. It has to be done by casting a ray from the point to be membership tested to infinity and counting surface intersections. If the answer is even (including 0) the point is outside; if it's odd, the point is inside.
Murphy's law dictates that sooner or later a ray will go through an edge:
probably causing a mis-count. This is not too hard to detect - another ray is then generated instead.
However, with a set-theoretic model we can use our recursive division trick to speed up the Monte Carlo calculation even more:
We get boxes that are all air (A) which we disgard, ones which are all solid (S), which we add straight into the volume calculation, and just get left with boxes containing surface for the Monte Carlo tests. This produces very fast and accurate results.
Mass is easy to compute from volume if the model's density is uniform of course. Different materials are usually specified as attributes, and a volume/mass sum is done for each.
While volume is being computed, the coordinates of the points in the Monte Carlo test can be added and averaged to find the centroid, and squares used to find the moments of intertia. This can all be done at very little extra computational cost.
© Adrian Bowyer 1996