Block Division with Fast Cubic B-spline Reconstruction
Kun Zhao 1, Naohisa Sakamoto 2, and Koji Koyamada 2121

Graduate School of Engineering, Kyoto University, Japan
Institute for the Promotion of Excellence in Higher Education, Kyoto University, Japan

Introduction

In the recent years, the high performance computing (HPC)
environment has been improved. Thus, the volume dataset
generated from HPC often resulted in the high resolution withrespect to the spatial and temporal dimension. This situation
requires a good visualization method, which can handle such alarge-scale volume dataset.
In this paper, we propose a volume reconstruction methodthat employs tetrahedral cells generated at each sub-volume.
The sub-volume is defined by applying a blocking operation toan original volume with a block size. Additional vertices in thetetrahedral cells are calculated by using a cubic b-splineinterpolation function calculated in an original volume. We
confirmed the effectiveness by calculating a compression ratio
for time-varying volume dataset.
2

Related Work

Since the volume data is defined at discrete points, which
are usually sampled from a continuous scalar field, manymethods have been proposed for seeking a continuous andaccurate volume representation. Among them, the successful
application of b-spline in signal and image processing field [1]was promising and an efficient algorithm to calculate the bspline coefficients has been proposed [2][3]. Bajaj C.L.[4] et al
have verified that the cubic b-spline is also a perfect fit forvolume reconstruction since it would yield less aliasing of highfrequency compared to a quadratic b-spline and also keep asecond-order continuity.
3

Volume Reconstruction SystemIn our proposed reconstruction system, we first divide thevolume into many blocks with the same block size, and thensubdivide every block into 24 tetrahedra. Afterwards, the valueof the vertices newly generated would be evaluated by fast cubic
b-spline algorithm.
Block Division
With the original volume data, the block division is donewith two levels.
The first-level division is to divide it into many blocks withthe same block size (left figure of Figure 1). Obviously, thiswould decrease the number of the vertices greatly but it can also
make a great data loss. As a result, we also propose a secondlevel division to subdivide the block into 24 tetrahedra (rightfigure of Figure 1) so that the area inside the block can also bealso represented well. Moreover, since the block is subdivided
into tetrahedra, it would not lead too much value gap.
With the block division, center points of every faces andgravity point of the block (black dots in Figure 1) would beneeded. As a result, an evaluation method is needed to evaluate
these values.

Fig.1. Block division with block size = 3
3.2

Fast Cubic B-spline Reconstruction
Ideally, we think the value of every newly generated pointshould keep continuity with the neighbour vertex points so thatless data gap would be generated. Since the good performanceof cubic b-spine, we utilize it to evaluate the value of the newly
generated vertices. The basic formula of the cubic b-spine
method can be written as:( )(∑)( )where the ( ) means the reconstructed signal, means the bspline coefficients and ( ) means the b-spline kernel. Here,the b-spline kernel can be defined as:| || |( ){ (| || |)

(2)

| |
And for the coefficients of, we use the fastalgorithm proposed by Bajaj C. L. et al [4]. The computation ofcoefficients is done with the recursive process with the initialvalues of (4). Here, ( ) is the original scalar values, andsuperscript of + and – are used to specify the recursive process.
∑ ( )

(())

( )

3.1

And then, the recursive process( )()yields exact B-spline coefficients, where.
√The computation of
can be accelerated by neglectingsmall terms. Given an error control tolerance , we compute( )[](| |)
And if,would be replaced with∑ ( )( )which can be computed using the Horner scheme for evaluatinga polynomial. This could accelerate the computation remarkably.

4Experiments and Results

In this paper, we apply our method on the time-varying
dataset obtained from a turbulent combustion simulation. The
grid structure is Cartesian with uniform spacing. There are
480 720 120 voxels, and a total of 122 time steps. The valueof the vertices is composed in the float type. The experimentresults with different block size are shown as the Table 1. And
the rendering results for different block size by Particle-Based
Volume Rendering (PBVR) [5] with phong shading are shown in
Figure 2 (as the limitation of space, the image of block size
equals 4 is omitted.). PBVR is a stochastic rendering method,which can provide a good performance for both structured
volume data and unstructured volume data by generating
particles from the volume data. The data used here is the Y
modality of time step 35. The experiment is conducted withIntel Core i7-2820QM CPU (4 cores), NVidia GeForce
GTX580M 2GB GPU, and 16GB RAM.
Here, we calculate the compression ratio by calculating
compressed data size over original data size. From the Table 1
we can see, even though tetrahedral cells are increased, thecompression ratio for all time steps performs very well since theadded coordinate and connection information for the tetrahedral
cells are needed only once for all steps. Moreover, the average
error is also computed from:∑ ||where, is the vertices number of the original volume,
isthe normalized value of the original volume at vertex , andis the normalized vertex value also at vertex interpolated
linearly from the compressed volume.
5

linear interpolation as the evaluation method is also shown inFigure 3 (local area of the same data to Figure 2 with block size2). We can see that the cubic b-spline evaluation can actuallyprovide a good image quality.
On the other hand, from equation (1) we can see, the cubic
b-spline coefficients would have a () data size, where is
the number of vertices of the original volume. As a result, after
the reconstruction is done, the coefficients of the cubic b-spline
are deleted to save the storage space. However, if we also takethese coefficients into the visualization process of thereconstructed volume, the image quality might be even better
because everywhere inside the tetrahedra cell can beinterpolated by cubic b-spline. This approach would be optimal
if we can also compress the coefficients so that it would not costso much storage space. This would be done in our future work.
In this paper, we proposed a volume reconstruction methodwith block division based on the fast cubic b-spline evaluation.
From the above experiments and results, we can see our volume
reconstruction system can provide a good compression ratio
especially for time-varying dataset with a good image quality
and a less compression error.
References
[1]

[2]
[3]

[4]

Discussion and Conclusions

The result of Figure 2 shows that when the block size issmaller than 5 our reconstruction system would provide a clear
and smooth image quality. Moreover, as we use the cubic bspline as the evaluation method to evaluate the newly generated
vertices after the block division, the comparison with using[5]

H.S. Hou and H.C. Andrews. Cubic splines for image
interpolationand digital filtering. IEEE Trans. Acoust., Speech, andSignal Processing, 26, 852–864, 1978.
M. Unser, A. Aldroubi, and M. Eden. B-spline signal processing:Part I-theory. IEEE Trans. Signal Processing, 41:821–832, 1993.
M. Unser, A. Aldroubi, and M. Eden. B-spline signal processing:Part II-efficient design and applications. IEEE Trans. SignalProcessing, 41, 834–848, 1993.
C. Bajaj, G. Xu, Q.Zhang, Bio-Molecule Surfaces Construction
Via a Higher-Order Level Set Method. Journal of Computer
Science and Technology. 23(6), 1026-1036, 2008.
T. Kawamura, N. Sakamoto and K. Koyamada, A Level-of-Detail
Rendering of a Large-Scale Irregular Volume Dataset Using
Particles, Journal of Computer Science and Technology, Vol.25,
No.5, 905-915, 2010.

Table 1. Reconstruction with different block size (Block Size
Number of Vertices

Original Volume23)
45

6

7

41,472,000

26,165,461

7,789,241

3,301,531

1,698,313

987,421624,347

0

124,416,000

36,864,000

15,552,000

7,962,524

4,608,000

1,899,656

100%

74.5%

22.1%

9.4%

4.8%

2.8%

1.7%

Processing Time

N/A

20.886s

11.581s5.174s

4.609s

3.409s

3.389sAverage Error (E)N/A

0.044%

0.081%

0.11%

0.18%

0.22%

0.30%

Number of Tetrahedras
Compression Ratio for All Steps(a) Original data(b) Block size =2(c) Block size = 3(e) Block size = 6(f) Block size = 7(a) Cubic b-spline evaluation(b) Linear evaluation(d) Block size = 5

Fig.2 Rendering Result with PBVR for different block size

Fig.3 Comparison with linear
evaluation (block size = 2)