Novel 3D Binary Indexed Tree for Volume Computation of 3D Reconstructed Models from Volumetric Data

Anh-Triet Do; Quoc-Bao Nguyen-Le; Tuan-Hy Le

arxiv: 2412.10441 · v2 · submitted 2024-12-11 · 💻 cs.GR · cs.AI· cs.CV

Novel 3D Binary Indexed Tree for Volume Computation of 3D Reconstructed Models from Volumetric Data

Quoc-Bao Nguyen-Le , Tuan-Hy Le , Anh-Triet Do This is my paper

Pith reviewed 2026-05-23 07:36 UTC · model grok-4.3

classification 💻 cs.GR cs.AIcs.CV

keywords volume computationmarching cubesfenwick treebinary indexed tree3D reconstructionvolumetric datamedical imagingCT scans

0 comments

The pith

A 3D Fenwick tree built during marching-cubes reconstruction computes volumes from CT or MR data with accuracy within 0.004 cm³.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an algorithm that computes the intrinsic volume of 3D objects reconstructed from volumetric CT or MR scans. It integrates the marching-cubes algorithm for mesh generation with a binary indexed tree that is populated in scan-line order at the same time as reconstruction. This simultaneous construction supports rapid volume queries and assists with user edits such as slicing or model transformations. The method relies on 30 predefined volume configurations derived from all marching-cubes cases. Accuracy tests on simple shapes and complex anatomical structures like lungs and cardiac chambers show deviations no larger than 0.004 cubic centimeters.

Core claim

Processing volumetric data in scan-line order simultaneously with the reconstruction algorithm creates a Fenwick tree that ensures much faster query time for volume computation while achieving accuracy with deviation within ±0.004 cm³ on tested objects including lungs and cardiac chambers.

What carries the argument

The 3D binary indexed tree (Fenwick tree) constructed in scan-line order during marching-cubes reconstruction using 30 volume configurations for polygonal mesh cases.

If this is right

Volume queries complete in much less time than sequential summation over the mesh.
Slicing or transforming the reconstructed model can be performed with immediate volume updates.
The same pipeline applies to any volumetric input from CT or MR scanners.
Complex anatomical structures such as lungs and heart chambers receive volume measurements accurate to within 0.004 cm³.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The approach could support interactive medical visualization tools where volume must be recomputed after each user adjustment.
Extending the scan-line construction to other isosurface algorithms might preserve the same query speed advantage.
Large-scale datasets could benefit from parallelizing the tree build across multiple scan lines.

Load-bearing premise

The 30 proposed configurations of volume values based on the polygonal mesh generation method correctly capture the contribution of every possible marching-cubes case without omission or overlap.

What would settle it

Applying the algorithm to a volumetric dataset whose exact volume is known independently, such as a unit sphere of precisely calculated volume, and measuring a deviation exceeding 0.004 cm³.

Figures

Figures reproduced from arXiv: 2412.10441 by Anh-Triet Do, Quoc-Bao Nguyen-Le, Tuan-Hy Le.

**Figure 1.** Figure 1: Calculating the volume of the aortic duct by integrating the surface function We can determine whether the arterial duct is hypertrophied by comparing its volume to standard parameters. We intersect the aorta with two planes (P),(Q) using a symmetric ray Casting method. The limits a, b on the Ox axis of an object are (x = a, x = b, a ≤ b). A plane perpendicular to the Ox axis at point x and a ≤ x ≤ b in… view at source ↗

**Figure 3.** Figure 3: Calculating the volume of an object with triple integration The concept of triple integration originates from dividing the object volume O into n very small rectangular prisms or cubes Oi with lengths, widths, and heights denoted as dx, dy, dz respectively. Approximating the volume of the original object is straightforward by summing the volumes of all Oi with 1 ≤ i ≤ n and as n → +∞: V = lim n→+∞ Σ n i=1… view at source ↗

**Figure 2.** Figure 2: Calculating partial aortic arch volume with double integral Given a list of (x, y, z) vertices, the implementation of this approach computed the volume of tube structures accurately . However, we have to find a midsection to divide the object into two parts. Additionally, current software systems allows radiologists to perform surgical operations (e.g. slicing) or modifies the segmentation result leadin… view at source ↗

**Figure 4.** Figure 4: Vertex indexing & binary representation However, [1] reduced the problem from 256 cases to 14 patterns by utilizing symmetrical property, rotational symmetry. From original 3D array, the algorithm create the boolean 3D array with the same size speculating that a vertex is false if locates inside the model and vice versa. Therefore, the volume of the model within a cube is limited from the mesh generated t… view at source ↗

**Figure 4.** Figure 4: The updated binary indexed tree [6] In BIT, the element ith stores the result F[i] of the subproblem containing 2k elements starting/ending at position i, where k is the lowest set bit in the binary representation of i. Observing the representation of the tree above, we can easily see that nodes with odd indices manage only themselves, while nodes with index id will have a parent with index id + 2k . Fin… view at source ↗

**Figure 5.** Figure 5: Query a region in 3D BIT with inclusion-exclusion principle This is a novel application of binary indexed trees into three-dimensional arrays. We employ the principle of inclusion and exclusion to query the sum of elements over a 3D space by excluding surrounding parts, similar to slicing but without data loss). We can perform updates on a 3D space (altering the mesh reconstruction) with minimal complexit… view at source ↗

read the original abstract

In the burgeoning field of medical imaging, precise computation of 3D volume holds a significant importance for subsequent qualitative analysis of 3D reconstructed objects. Combining multivariate calculus, marching cube algorithm, and binary indexed tree data structure, we developed an algorithm for efficient computation of intrinsic volume of any volumetric data recovered from computed tomography (CT) or magnetic resonance (MR). We proposed the 30 configurations of volume values based on the polygonal mesh generation method. Our algorithm processes the data in scan-line order simultaneously with reconstruction algorithm to create a Fenwick tree, ensuring query time much faster and assisting users' edition of slicing or transforming model. We tested the algorithm's accuracy on simple 3D objects (e.g., sphere, cylinder) to complicated structures (e.g., lungs, cardiac chambers). The result deviated within $\pm 0.004 \text{cm}^3$ and there is still room for further improvement.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper builds a 3D Fenwick tree on the fly during marching-cubes reconstruction for fast volume queries and claims ±0.004 cm³ accuracy, but the reduction to 30 volume configurations is the unshown step that determines if the error bound holds.

read the letter

The paper's main move is to run marching cubes in scan-line order while building a 3D binary indexed tree so that volume queries on the resulting mesh become fast and support edits like slicing. They also define 30 volume values tied to the mesh cases and test the whole thing on spheres, cylinders, lungs, and heart chambers, reporting deviation within ±0.004 cm³. That combination has clear practical use in medical imaging pipelines where repeated volume checks matter. The simultaneous build and the reported error on real anatomy are the parts that stand out as useful. The 30 configurations are the part that needs checking. Marching cubes has 256 sign patterns; if the mapping to 30 scalars leaves gaps or overlaps, any mesh hitting an uncovered case will carry a systematic volume error that the reported bound would not catch. The abstract gives no derivation, table, or completeness argument for how the 30 values were chosen, so the accuracy claim rests on an unverified reduction. No baseline comparisons appear either, such as against direct voxel summation or other spatial trees, which makes it hard to judge the speed gain in practice. The tests cover both simple and complex shapes, which is positive, but without details on ground-truth measurement or edge-case handling the result stays provisional. This work is aimed at people who already use marching cubes on CT/MR data and want faster queries inside an editing loop. A reader who needs exactly that speed-up could extract value once the configuration step is shown to be complete. The paper deserves a serious referee to verify the 30-case mapping against the full 256 patterns and to see whether the implementation details hold up under additional tests.

Referee Report

2 major / 2 minor

Summary. The paper presents an algorithm that integrates the marching cubes method for 3D surface reconstruction from volumetric CT/MR data with a 3D Fenwick tree (binary indexed tree) built in scan-line order. It proposes 30 volume configurations derived from the polygonal mesh generation process and claims that this enables fast volume queries while achieving numerical accuracy with deviation within ±0.004 cm³ on both simple geometric objects and complex anatomical structures such as lungs and cardiac chambers.

Significance. If the 30 configurations are shown to be complete and the accuracy bound is reproducible, the approach would offer a practical efficiency gain for volume computation during or after reconstruction, particularly when interactive slicing or editing is required. The use of a Fenwick tree for prefix-sum queries is a standard technique that could be valuable in graphics pipelines handling large volumetric datasets.

major comments (2)

[section on the 30 configurations of volume values] The section proposing the 30 configurations: the reduction of the 256 possible marching-cubes vertex sign patterns to exactly 30 volume scalars is presented without a derivation, enumeration, or completeness argument. Because the headline accuracy claim (±0.004 cm³) is obtained by summing per-voxel contributions from these scalars, any omitted or overlapping case produces a systematic bias in the integrated volume for meshes containing that pattern; this mapping is therefore load-bearing for the central numerical result.
[testing and results] The experimental validation section: the manuscript states that the result “deviated within ±0.004 cm³” on tested objects but supplies no description of ground-truth volume computation, number of trials, handling of ambiguous marching-cubes cases, or comparison against direct integration or other established volume estimators. Without this methodology the reported bound cannot be assessed for robustness or generality.

minor comments (2)

[introduction] The abstract and introduction mention “multivariate calculus” but never specify which integral or theorem is being discretized; a brief equation or reference would clarify the connection to the per-voxel volume values.
[algorithm description] Notation for the Fenwick tree (binary indexed tree) should be introduced once and used consistently; the current text alternates between “binary indexed tree,” “Fenwick tree,” and “3D Binary Indexed Tree” without a defining equation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the insightful comments on our manuscript. We address each of the major comments below and will incorporate revisions to strengthen the presentation of our method and results.

read point-by-point responses

Referee: The section proposing the 30 configurations: the reduction of the 256 possible marching-cubes vertex sign patterns to exactly 30 volume scalars is presented without a derivation, enumeration, or completeness argument. Because the headline accuracy claim (±0.004 cm³) is obtained by summing per-voxel contributions from these scalars, any omitted or overlapping case produces a systematic bias in the integrated volume for meshes containing that pattern; this mapping is therefore load-bearing for the central numerical result.

Authors: We agree that a detailed derivation and completeness argument for the 30 configurations is essential and was insufficiently detailed in the original manuscript. In the revised manuscript, we will add a new subsection that derives the 30 volume scalars by analyzing the contribution of each triangle generated by the marching cubes algorithm to the voxel volume. We will provide an enumeration showing the mapping from all 256 sign patterns to these 30 scalars, grouped by equivalent volume contributions, and include a proof of completeness by demonstrating that every possible configuration is accounted for without overlap or omission in the volume calculation. This will directly support the accuracy of the integrated volume. revision: yes
Referee: The manuscript states that the result “deviated within ±0.004 cm³” on tested objects but supplies no description of ground-truth volume computation, number of trials, handling of ambiguous marching-cubes cases, or comparison against direct integration or other established volume estimators. Without this methodology the reported bound cannot be assessed for robustness or generality.

Authors: We acknowledge the need for more rigorous experimental methodology. In the revised version, we will expand the experimental validation section to include: (1) details on ground-truth computation, using analytical volume formulas for simple geometric objects and a high-resolution reference integration for anatomical structures; (2) the number of trials and datasets used; (3) our approach to handling ambiguous marching cubes cases, such as using a consistent convention for zero-value vertices; and (4) comparisons against alternative methods including direct summation of voxel contributions and surface integration via the divergence theorem. These additions will allow readers to evaluate the robustness of the reported accuracy bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard algorithms and empirical validation

full rationale

The paper proposes 30 volume configurations derived from the marching-cubes polygonal mesh method, builds a Fenwick tree in scan-line order during reconstruction, and reports empirical accuracy within ±0.004 cm³ on test objects. No quoted step shows a claimed prediction or result reducing by construction to a parameter fitted from the same computation, a self-citation chain, or an ansatz smuggled via prior work. The central volume summation is presented as an independent algorithmic combination of multivariate calculus, marching cubes, and binary indexed trees, with completeness of the 30 cases treated as a modeling choice rather than internally forced. This leaves the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The approach appears to rest on the standard correctness of marching cubes and Fenwick tree operations without additional postulates identified.

pith-pipeline@v0.9.0 · 5705 in / 1112 out tokens · 21281 ms · 2026-05-23T07:36:16.256350+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

Marching cubes: A high resolution 3d surface construc- tion algorithm,

W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3d surface construc- tion algorithm,” in Seminal graphics: pio- neering efforts that shaped the field, 1998, pp. 347–353

work page 1998
[2]

Mea- suring intrinsic volumes in digital 3d images,

K. Schladitz, J. Ohser, and W. Nagel, “Mea- suring intrinsic volumes in digital 3d images,” in Discrete Geometry for Computer Imagery: 13th International Conference, DGCI 2006, Szeged, Hungary, October 25-27, 2006. Pro- ceedings 13. Springer, 2006, pp. 247–258

work page 2006
[3]

Shape and dimensions of cardiac chambers: importance of ct section thickness and orientation

E. A. Hoffman and E. L. Ritman, “Shape and dimensions of cardiac chambers: importance of ct section thickness and orientation.” Ra- diology, vol. 155, no. 3, pp. 739–744, 1985

work page 1985
[4]

Efficient implementation of marching cubes’ cases with topological guar- antees,

T. Lewiner, H. Lopes, A. W. Vieira, and G. Tavares, “Efficient implementation of marching cubes’ cases with topological guar- antees,” Journal of graphics tools , vol. 8, no. 2, pp. 1–15, 2003

work page 2003
[5]

A system for limb-volume measure- ment using 3d models from an infrared depth sensor,

G. Lu, G. Desouza, B. Anderson, and C.-R. Shyu, “A system for limb-volume measure- ment using 3d models from an infrared depth sensor,” 04 2013, pp. 64–69

work page 2013
[6]

A new data structure for cu- mulative frequency tables,

P. M. Fenwick, “A new data structure for cu- mulative frequency tables,” Software: Prac- tice and experience , vol. 24, no. 3, pp. 327– 336, 1994. 8

work page 1994

[1] [1]

Marching cubes: A high resolution 3d surface construc- tion algorithm,

W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3d surface construc- tion algorithm,” in Seminal graphics: pio- neering efforts that shaped the field, 1998, pp. 347–353

work page 1998

[2] [2]

Mea- suring intrinsic volumes in digital 3d images,

K. Schladitz, J. Ohser, and W. Nagel, “Mea- suring intrinsic volumes in digital 3d images,” in Discrete Geometry for Computer Imagery: 13th International Conference, DGCI 2006, Szeged, Hungary, October 25-27, 2006. Pro- ceedings 13. Springer, 2006, pp. 247–258

work page 2006

[3] [3]

Shape and dimensions of cardiac chambers: importance of ct section thickness and orientation

E. A. Hoffman and E. L. Ritman, “Shape and dimensions of cardiac chambers: importance of ct section thickness and orientation.” Ra- diology, vol. 155, no. 3, pp. 739–744, 1985

work page 1985

[4] [4]

Efficient implementation of marching cubes’ cases with topological guar- antees,

T. Lewiner, H. Lopes, A. W. Vieira, and G. Tavares, “Efficient implementation of marching cubes’ cases with topological guar- antees,” Journal of graphics tools , vol. 8, no. 2, pp. 1–15, 2003

work page 2003

[5] [5]

A system for limb-volume measure- ment using 3d models from an infrared depth sensor,

G. Lu, G. Desouza, B. Anderson, and C.-R. Shyu, “A system for limb-volume measure- ment using 3d models from an infrared depth sensor,” 04 2013, pp. 64–69

work page 2013

[6] [6]

A new data structure for cu- mulative frequency tables,

P. M. Fenwick, “A new data structure for cu- mulative frequency tables,” Software: Prac- tice and experience , vol. 24, no. 3, pp. 327– 336, 1994. 8

work page 1994