| |
Cell-Based First-Hit
Ray Casting
|
|
 |
|
| Abstract:
|
Cell-based first-hit ray casting, a new technique for fast perspective volume visualization, is presented in this paper.
This technique, based on the well
known ray casting algorithm, performs iso-surfacing and supports
interactive threshold adjustment. It is accelerated by the reduction of average ray path lengths to only a few steps per pixel. The volume is divided into cubic sub volumes. Each sub volume that is
intersected by an iso-surface is projected to the image plane. A local ray
casting step within the sub volume is performed for each pixel covered by the
projection.
Cell-based first-hit ray casting is perfectly suited whenever fast perspective iso-surfacing is required. This paper describes the basic algorithm, presents possible optimizations and evaluates the performance of the algorithm for one specific application, the post-implantation assessment of endovascular stent placement. It will be shown that the algorithm, though executed on a single processor machine without any hardware acceleration, performs well for view points inside as well as outside
the stented blood vessel and outperforms an
optimized, yet more conventional ray casting technique significantly.
|
| Project:
|
This project was done in the scope of
VRVis basic research
on visualization
at
the VRVis research center
in Vienna, Austria, which is funded by an
Austrian governmental program called Kplus.
|
| Papers:
|
More details about this work
can be found in
VRVis technical report TR-VRVis-2001-027 (10 pages)
from December 2001.
A revised version of this paper
is published in the Proceedings of the 4th Joint IEEE TCVG -
EUROGRAPHICS Symposium on Visualization
(VisSym 2002),
May 27-29, 2002, in Barcelona, Spain, pp. 77-86.
|
Anims.
(to start animations, click on them) |
Animation 1: virtual flight through a stented aorta
|
Animation 2: virtual flight through a stented aorta
|
Animation 3: threshold adjustment
|
Animation 4: virtual bronchoscopy
|
Images
(to retrieve an enlarged version
of the images, click on them):
|
Below:
virtual colonoscopy (left);
virtual bronchoscopy (middle);
virtual angioscopy (right).
|
|
| Below:
stent and bones.
|
Below:
stent and inner organs.
|
|
|
| Below:
comparison of two ray-surface intersection techniques.
Left: exact intersection;
middle: fast intersection;
right: difference.
|
|
| Below:
two macro-cells:
|
| Left:
early termination (e.s.t.) is possible for all scanlines.
|
Right:
an example for a scanline which should not be terminated
early due to left facing surface normals.
|
|
|
| Below:
dangerous macro-cell faces.
|
Below:
an example for a dangerous macro-cell face confining
the applicability of early scanline termination.
|
|
|
| Below:
example situation (left):
ray numbers without (middle)
and with (right)
the usage of early scanline termination.
|
|
| Below:
two frames from a virtual flight through the stented aorta
|
|
|
| Below:
frames for thresholds 0 HU (left, soft tissue is visible)
450 HU (middle, some ribs and the stent are visible)
and 1100 HU (right, only the stent is visible).
|
|
| Algorithm: |
Cell-based first-hit ray casting performs
iso-surfacing. The data volume is divided into cubic sub
volumes, so called macro-cells. Each macro-cell consists of
n^3 cells, where n is usually a number between four and ten.
Each macro-cell containing a part of one of the iso-surfaces
is projected to the image plane. A rasterization algorithm
detects all pixels that are covered by the projection. From
each of those pixels that have not yet been assigned a color,
a ray is cast through the macro-cell. Sampling starts at the
point where the ray intersects the closest face of the
macro-cell and stops, when the ray either hits an iso-surface
or leaves the macro-cell. If the ray hits a boundary cell,
i.e., a cell that contains data values above as well as below
one of the specified thresholds, an intersection algorithm is
applied to see, if and at which position the ray intersects
the corresponding iso-surface. If the iso-surface is hit, the
gradient vector at the intersection point is calculated using
trilinear interpolation. A color value is then calculated
from the gradient and assigned to the corresponding pixel. In
order to improve performance, some techniques have been
developed that reduce the number of local rays. Macrocell
trimming identifies the smallest cuboid inside a
macro-cell, that contains all the macro-cell's portions of the
iso-surfaces. This cuboid is projected instead of the
macro-cell, yielding fewer and shorter local rays. The
topology-dependent technique early scanline termination
mangages to further reduce the number of local rays
significantly. Application of both optimization techniques
yields a reduction of the average number of ray steps per
pixels to below 4. |
This page
is maintained by Helwig Hauser.
In case of questions, comments, etc., please
mailto:Hauser@VRVis.at.
|
