|
|
Our technique of automatically generating a flythrough animation involves the following steps: extracting the region of interest from the whole colon; specifying the first and last points of the flythrough; computing the flight path along the inside of the colon; determining the viewing directions for the key frames of the animation; and finally, generating the flythrough animation by interpolating the eye positions and viewing directions between the key frames.
Figure 1 shows a 2D cross-section of a volumetric colon, upon which a regular grid is superimposed. In the first step, the user employs the "blocking" operations of VolVis to extract the region of interest, as shown in Figure 2. In other words, with these operations, the user is able to focus attention on the region enclosed by the colon surface and the blocking walls. For simplicity, the blocking walls can be specified while the user studies the colon data set slice by slice, along the X, Y, or Z direction. This scheme has been implemented in the Object Control component of VolVis.
In addition to specifying the blocking walls, the user needs to select the first as well as the last points of the flight path, as shown in Figure 3. Again, this is accomplished while the user views the colon slices using the Object Control of VolVis. The rest of the flight path is automatically computed with our algorithm, as described below. Note that the specifications of the blocking walls and the two end points of the flight path are the only operations that the user has to perform, which not only greatly alleviates the burden on the user, but also provides helpful flexibilities for generating various flythrough animations.
After the user specifies the region of interest and the two end points of the flight path, those grid points that are reachable from either the first or the last fly point along the grid lines, without penetrating the colon surface or the blocking walls, are automatically identified. In this way, the discrete sub-volume which is enclosed by the colon surface and the blocking walls is reconstructed, as indicated in dark grey in Figure 4.
Next, the "peel onion" technique [6] is employed on the reconstructed sub-volume to compute a flight path from the first fly point to the last fly point (This technique has been successfully applied in 2D Optical Character Recognition (OCR) to extract the skeleton of a digital character). With this technique, at each step the outermost layer of the sub-volume is peeled off, until there is only one layer of grid points left, which essentially is the skeleton of the colon and becomes the desired flight path for the flythrough animation. More specifically, each grid point on the current outermost layer of the sub-volume (except the first and the last fly points) is deleted if the deletion does not lead to the disconnection of the first fly point and the last fly point. A sequence of deletions for the sub-volume in Figure 4 is shown in Figure 5 through 7. A flight path from the first fly point to the last fly point is thus created, and each grid point on the flight path consequently corresponds to the eye position of a key frame.
For the viewing parameters of each key frame, in addition to the eye position, there are three degrees of freedom for the viewing direction which have to be determined. From our experiments, we have noticed that simply using the vector from the current eye position to the eye position in the next key frame is undesirable. One of the problems is that, due to the discrete nature of the flight path, the viewing direction may point at the side wall of the colon surface (see Figure 7). Another problem is that, again because of the discrete nature of the flight path, the current viewing direction is always parallel to a main axis and could be 90-degree rotationally different from the viewing direction of the previous key frame, which may lead to a jerky animation (see Figure 7).
In general, for an informative flythrough animation, the user's eye should always focus at the end of the currently visible colon segment, expecting new features to come next. In our implementation, instead of letting the current viewing direction focus on the eye position of the next key frame, we compute the viewing direction by using the eye positions of the next 5n to 10n key frames, where n is the number of "onion" layers in the original sub-volume, as shown in dark grey in Figure 4. If all the eye positions from the next 5n to 10n key frames are visible to the current eye position, the vector from the current eye position to the eye position of the next 5n key frame is used as the viewing direction of the current key frame. Otherwise, we backtrack one step and test the visibilities of the eye positions at the next 5n-1 to 10n-1 key frames. This procedure is recursively performed until we find the viewing direction.
The visibility of a certain point from the current eye position is determined by shooting a ray from the current eye position towards the target point. If there is an intersection between the ray and the colon surface, and the intersection point lies between the current eye position and the target point, then the target point is invisible to the current eye position. Otherwise, the target point can be seen by the current viewing eye. In this way, we can determine the viewing directions for all the key frames of the flythrough animation. It can be seen from the video segment in the video proceedings that this heuristic worked very well for our case studies.
After the eye positions and viewing directions for the key frames have beed determined, the Animator of VolVis is applied to create a smooth camera-motion animation by interpolating the eye positions and the viewing directions between two consecutive key frames using cubic splines [3]. Since the animation is generated off-line without user interaction, high-quality images can be rendered with the volumetric ray tracing technique implemented in VolVis. The animation can be subsequently played back on a workstation or recorded on a video tape. Notice that the key frames of the animation can act as the basis of the interactive flythrough when further analysis of the colon is needed. For example, the user can rotate the viewing direction of a certain key frame to look around in a search for interesting features, which is especially helpful at those positions close to a potential tumor.