Biomedical Engineering Reference
In-Depth Information
Figure 7.11:
(a) Data set; ( b) conceptual region; (c) leve 1; and (d) final level.
into
H
consecutive chunks (
H
=
3 in Fig. 7.11). Then, for each such chunk, sort
its data points by the
y
-values and partition them into
H
consecutive chunks.
For 3D images we must repeat the procedure for the
z
-values.
That is precisely the
meta-cell
partition. Unlike octrees, meta-cell is not a hi-
erarchical structure. The partition is defined through the parameter
H
. Besides,
given a point (
q
1
,
q
2
,
q
3
), inside the domain, the corresponding meta-cell is given
by:
mcell
=
q
i
/
C
i
,
i
=
1
,
2
,
3
,
(7.28)
where
C
i
is the number of data points of each chunk of the conceptual region, in
the direction
i
. To each meta-cell is associated a set of meta-intervals (connected
components among the intervals of the cells in that meta-cell). These meta-
intervals are used to construct an interval tree, which will be used to optimize
I/O operations. Given a set of
N
meta-intervals, let
e
1
,
e
2
,...,
e
2
n
be the sorted list
of left and right endpoints of these intervals. Then, the interval tree is recursively
defined as follows:
Interval tree construction
: (i) If there is only one interval, then the current node
r
is a leaf containing that interval; (ii) else, the value
m
=
(
e
n
+
e
n
+
1
)
/
2 is stored
in
r
as a key; the intervals that contain
m
are assigned to
r
as well as pointers to
the subtrees
left
(
r
) and
right
(
r
). Go to step (i).
Now, let us take an overview of out-of-core isosurface extraction methods
based on the above structures. The methodology presented in [64] extends the
BONO for time-varying isosurface extraction. The proposed structure (
temporal