GameDev.netArea and Volume Calculations

Area and Volume Calculations
## MotivationIn recent months, the indie game programming scene has witnessed the rising popularity of a pressure volume model described in a paper written by Maciej Matyka and Mark Ollila. The paper can be found here: http://panoramix.ift.uni.wroc.pl/~maq/eng/index.php. In the model's first presentation the authors used an axis aligned bounding box to approximate the volume of a body. Such a rough approximation is easily computed but highly inaccurate. A second paper followed sometime later describing a two dimensional implementation that employed Gauss's Theorem to calculate the exact area of a simulated body. The author mentioned the possibility of a three dimensional version using the same technique but restricted his presentation to the two dimensional case. It would seem that a three dimensional volume calculator should have surfaced shortly afterward; however, no such algorithm has been detailed by Matyka or Ollila at the time of this writing. The goal of this article is to fill in the details left out of Matyka's second paper. ## Problem SpaceThe two dimensional case: Given a set of edges that form a closed loop calculate the enclosed area. The three dimensional case: Given a set of triangles that form a closed surface calculate the enclosed volume. ## Derivation (2D)Gauss's Theorem relates the divergence of a vector field within an area to the flux of a vector field through a closed path by the following:
where the path
When
the innards of the double integral in equation 1.1 can be reduced to one. This reduction lets us write:
which equates to the area of
Equation 1.4 tells us that the flux of the vector field v} is given by:_{2}
v
_{1}
e
where the evaluation of
The flux of v} now follows:_{2}Φ = ∫ Φ = ∫ - _{x} + te_{x})dt
where the integral is evaluated through t on [0, 1]. The analytical solution to equation 1.10 can be written as: Φ = ½ ∙ ( _{y} – v_{2}_{y}) ∙ (v_{1}_{x} +v_{2}_{x})
The right hand side of equation 1.11 yields the flux of v}. Given a closed and clockwise wound edge set {_{2}v, _{i1}v} for i = {0, 1, 2,…,n} the enclosed area is computed by evaluating the following sum:_{i2}area = ½ ∑ ( _{y} – v_{i2}_{y}) ∙ (v_{i1}_{x} +v_{i2}_{x})
## C++ Implementation (2D)// v: A pointer to the array of vertices // i: A pointer to the array of indices // n: The number of indices (multiple of 2) // This function uses Gauss's Theorem to calculate the area (or field) // of a body enclosed by a set of edges. The edge set must form a // closed path in R2 and be outward facing. An outward facing edge set // wraps clockwise around the body where the x-axis points left and the // y-axis points up. float CalculateArea(const VECTOR2 *v, const unsigned int *i, const unsigned int n) { unsigned int j; VECTOR2 v1; VECTOR2 v2; float area = 0.0f; for(j = 0; j < n; j+=2) { v1 = v[i[j ]]; v2 = v[i[j+1]]; area += (v1.y-v2.y) * (v1.x+v2.x); } return area / 2.0f; } ## Derivation (3D)Gauss's Theorem relates the divergence of a vector field within a volume to the flux of a vector field through a closed surface by the following:
where the surface
When
the innards of the triple integral in equation 1.1 can be reduced to one. This reduction lets us write:
which equates to the volume of
Equation 2.4 tells us that the flux of the vector field v, _{2}v} is given by:_{3}
v – _{2}v
_{1}
v – _{3}v
_{1}
e + v_{1}e
_{2}where the evaluation of
e)dvdu
_{2}The flux of v, _{2}v} now follows:_{3}Φ = ∫∫ e)dvdu
_{2}Φ = ∫∫ ( e + v_{1x}e)(_{2x}e – _{1y}e_{2z}e)dvdu
_{1z}e_{2y}where the integral is evaluated through u on [0, 1] and v on [0, 1-u]. The analytical solution to equation 2.11 can be written as: Φ = 1/6 (( _{y}–v_{1}_{y})(v_{3}_{z}–v_{1}_{z}) – (v_{2}_{z}–v_{1}_{z})(v_{3}_{y}–v_{1}_{y}))(v_{1}_{x} + v_{2}_{x} + v_{3}_{x})
The right hand side of equation 2.12 yields the flux of v, _{2}v}. Given a closed and clockwise wound triangle set {_{3}v, _{i1}v, _{i2}v} for i = {0, 1, 2,…,n} the enclosed volume is computed by evaluating the following sum:_{i3}volume = 1/6 ∑ (( _{y}–v_{i1}_{y})(v_{i3}_{z}–v_{i1}_{z}) – (v_{i2}_{z}–v_{i1}_{z})(v_{i3}_{y}–v_{i1}_{y}))(v_{i1}_{x} + v_{i2}_{x} + v_{i3}_{x})## C++ Implementation (3D)// v: A pointer to the array of vertices // i: A pointer to the array of indices // n: The number of indices (multiple of 3) // This function uses Gauss's Theorem to calculate the volume of a body // enclosed by a set of triangles. The triangle set must form a closed // surface in R3 and be outward facing. Outward facing triangles index // their vertices in a counterclockwise order where the x-axis points // left, the y-axis point up and the z-axis points toward you (rhs). float CalculateVolume(const VECTOR3 *v, const unsigned int *i, const unsigned int n) { unsigned int j; VECTOR3 v1; VECTOR3 v2; VECTOR3 v3; float volume = 0.0f; for(j = 0; j < n; j+=3) { v1 = v[i[j ]]; v2 = v[i[j+1]]; v3 = v[i[j+2]]; volume += ((v2.y-v1.y)*(v3.z-v1.z)– (v2.z-v1.z)*(v3.y-v1.y) )*(v1.x+v2.x+v3.x); } return volume / 6.0f; } ## ConclusionAnd there you have it, a fast and precise way to find the area or volume of a body given its edge or triangle set. I have tested the code on a variety of basic primitives and am 99% certain it is bug free. You can contact me with question, comments and bug reports at kwoxrf@umr.edu.
© 1999-2011 Gamedev.net. All rights reserved. |