16 Feb 2018
(No, there won’t beryllium jokes.)
The pursuing presents a accelerated algorithm for measurement computation of a simple, closed, triangulated 3D mesh. This presumption is simply a consequence of the divergence theorem. Further extensions whitethorn generalise to other meshes arsenic well, though that is presently retired of scope.
We statesman pinch the meaning of measurement arsenic the triple integral complete a region of the changeless one:
V=∭R1dVV = \iiint_R 1 \mathrm{d}V
Let 𝐅\mathbf{F} be a usability in ℝ3\mathbb{R}^3 such that its divergence is adjacent to one. For the purposes of this paper, we choose:
𝐅(x,y,z)=<x,0,0>\mathbf{F}(x, y, z) = <x, 0, 0>
It tin easy beryllium verified that
div𝐅=∂F∂x+∂F∂y+∂F∂z=1+0+0=1\mathrm{div} \mathbf{F} = \frac{\partial F}{\partial x} + \frac{\partial F}{\partial y} + \frac{\partial F}{\partial z} = 1 + 0 + 0 = 1
Therefore,
V=∭R1dV=∭Rdiv𝐅(x,y,z)dVV = \iiint_R 1 dV = \iiint_R \mathrm{div} \mathbf{F}(x, y, z) \mathrm{d}V
By the Divergence Theorem, this is adjacent to the aboveground integral:
V=∬S𝐅(x,y,z)d𝐒V = \iint_S \mathbf{F}(x, y, z) \mathrm{d}\mathbf{S}
This aboveground integral, defined complete the aboveground S of the 3D mesh, is equal to the sum of its piecewise triangle parts. Let TiT_i denote the aboveground of the ii’th triangle successful the mesh. Then,
V=∑i=0∬Ti𝐅(x,y,z)d𝐒V = \sum_{i = 0} \iint_{T_i} \mathbf{F}(x, y, z) \mathrm{d}\mathbf{S}
Let TinT_{in} represent the nn’th vertex of the ii’th triangle. Let Δ1\Delta_1 equal the vector quality between Ti1T_{i1} and Ti0T_{i0}, and Δ2\Delta_2 likewise adjacent to Ti2−Ti0T_{i2} - T{i0}. Each individual triangle TiT_i may frankincense beryllium parametrised as:
𝐫(u,v)=Ti0+uΔ1+vΔ2\mathbf{r}(u, v) = T_{i0} + u\Delta_1 + v\Delta_2
Then, elemental differentiation yields:
𝐫u=Δ1\mathbf{r}_u = \Delta_1 𝐫v=Δ2\mathbf{r}_v = \Delta_2
Therefore,
𝐫u×𝐫v=Δ1×Δ2\mathbf{r}_u \times \mathbf{r}_v = \Delta_1 \times \Delta_2
Thus, the aboveground integral tin beryllium rewritten successful position of this parametrisation, substituting successful the meaning of 𝐅\mathbf{F} as needed:
V=∑i=0∬Ti𝐅(x,y,z)(𝐫u×𝐫v)dAV = \sum_{i = 0} \iint_{T_i} \mathbf{F}(x, y, z) (\mathbf{r}_u \times \mathbf{r}_v) dA =∑i=0∬Ti𝐅(x,y,z)(̇Δi1×Δi2)dA= \sum_{i = 0} \iint_{T_i} \mathbf{F}(x, y, z) \dot (\Delta_{i1} \times \Delta_{i2}) dA =∑i=0∬Ti<x,0,0>(̇Δi1×Δi2)dA= \sum_{i = 0} \iint_{T_i} <x, 0, 0> \dot (\Delta_{i1} \times \Delta_{i2}) dA
This transverse merchandise is changeless passim the triangle and easy to calculate from the vertex data. Only the X constituent of the cross product should beryllium calculated; the others are adjacent to zero owed to the dot merchandise pinch the zero components of 𝐅\mathbf{F}. VV can beryllium frankincense beryllium rewritten as:
V=∑i=0(Δi1×Δi2)x∬TixdAV = \sum_{i = 0} (\Delta_{i1} \times \Delta_{i2})_x \iint_{T_i} x dA
We now attraction connected the aboveground integral ∬TixdA\iint_{T_i} x dA. Expanding pinch the parametrisation yields:
∬TixdA=∫01∫0uxdvdu=∫01∫0u(Ti0x+uΔi1x+vΔi2x)dvdu\iint_{T_i} x dA = \int_{0}^{1} \int_{0}^{u} x dv du = \int_{0}^{1} \int_{0}^{u} (T_{i0x} + u \Delta_{i1x} + v \Delta_{i2x}) dv du
This integral tin beryllium straight evaluated, treating vertex information as constants:
∫01∫01−u(Ti0x+uΔi1x+vΔi2x)dvdu\int_{0}^{1} \int_{0}^{1-u} (T_{i0x} + u \Delta_{i1x} + v \Delta_{i2x}) dv du =Ti0x∫01∫01−udvdu+Δi1x∫01∫01−uudvdu+Δi2x)∫01∫01−uvdvdu= T_{i0x} \int_{0}^{1} \int_{0}^{1-u} dv du + \Delta_{i1x} \int_{0}^{1} \int_{0}^{1-u} u dv du + \Delta_{i2x}) \int_{0}^{1} \int_{0}^{1-u} v dv du =Ti0x(12)+Δi1x(16)+Δi2x(16)= T_{i0x} (\frac{1}{2}) + \Delta_{i1x} (\frac{1}{6}) + \Delta_{i2x} (\frac{1}{6}) =Ti0x(12)+(Ti1x−Ti0x)(16)+(Ti2x−Ti0x)(16)= T_{i0x} (\frac{1}{2}) + (T_{i1x} - T_{i0x})(\frac{1}{6}) + (T_{i2x} - T_{i0x})(\frac{1}{6}) =Ti0x(16)+(Ti1x)(16)+(Ti2x)(16)= T_{i0x} (\frac{1}{6}) + (T_{i1x})(\frac{1}{6}) + (T_{i2x})(\frac{1}{6}) =16(Ti0x+Ti1x+Ti2x)= \frac{1}{6}(T_{i0x} + T_{i1x} + T_{i2x})
Substituting into the original sum and pulling retired a changeless factor of 16\frac{1}{6} to debar the soul loop division, this yields the pursuing compact formula for the volume:
V=16∑i=0(Δi1×Δi2)x(Ti0x+Ti1x+Ti2x)V = \frac{1}{6} \sum_{i = 0} (\Delta_{i1} \times \Delta_{i2})_x (T_{i0x} + T_{i1x} + T_{i2x})
Performance analysis
The last algorithm contains nary numerical integration nor differentiation. In opposition to communal naive algorithms for volume, which are balanced to rendering the mesh and past sampling the render, an costly operation, location is only a azygous loop successful this algorithm, over the triangles. Thus, this algorithm for measurement computation is O(n) to the number of the triangles. Furthermore, the per-triangle calculation is likewise efficient: fixed the earthy description of the cross product, the soul portion contains 7 additions and three multiplications. On the extracurricular of the loop is only a single multiplication. Thus, for a mesh of nn triangles, the algorithm requires 8n−18n - 1 additions and 3n+13n + 1 multiplications, or 11n11n floating constituent operations. This is very fast.
For a ballpark number, if measurement needs to beryllium calculated each frame in a high-performance 60 frames per 2nd application, without the aid of a GPU, only utilizing the CPU capabilities of a $35 Raspberry Pi, astir 30 cardinal triangles could beryllium measured every frame.
Motivation
The vector calculus exam is soon, and I request to study. Plus, who doesn’t emotion 3D graphics?!
I would beryllium (pleasantly) amazed if the algorithm is novel. Further investigation after posting reveals the paper Efficient Feature Extraction for 2D/3D Objects successful Mesh Representation by Cha Zheng and Tsuhan Chen, which appears to picture the aforesaid algorithm, although the derivation is different. It was nosy while it lasted!
Retourner à l’acceuil
English (US) · 
Indonesian (ID) · 
