This technical journal talks about 3D image metamorphosis applied to volume-based representations of objects, also known as image morphing. The journal covers different issues concerning the basic techniques to apply volume-based representations of objects and the current 3D feature-based volume metamorphosis method.

Image morphing involves creating a smooth transition between two objects. The feature-based volume method is composed of two components in order to achieve image morphing. The first step, also known as the warping process, involves warping two input volumes of two different objects. Once this is complete, the next step, the blending process, involves the blending the two objects in order to get one combined warped volume.

The journal compares image morphing to 3D morphing. 3D morphing is where a sequence of intermediate 3D objects are generated also known as "morphs", directly from the given models. Once this is done, the morphs are rendered to "produce a sequence depicting the transformation." In 2D morphing, a new morph had to be computed every time the viewpoint or the illumination needed to be altered. Now, with 3D morphing, since creating morphs is independent of the viewing and lighting parameters, a morph can be created through only one sequence. The lighting and illumination can be adjusted during rendering. 2D morphing capabilities also lack the information on the objects spatial configuration. Therefore, the lighting and visibility can not be adjusted correctly. Often times, shadows and highlights fail to match shape changes that occur in the morph. Another problem with 2D morphing is when a feature of the 3D object is not present or visible in the original 2D image, this same feature cannot be made to appear during the morph. An example of a singer needing to open her mouth during a morph is given. The image would picture the singer's lips stretching apart, however, instead of revealing her teeth, the lips would only thicken since the teeth were not present in the initial 2D image.

Volume Morphing Method

The volume morphing method consists of having two volumes designated as S and T, representing the source and the target volumes. The volume data can be acquired through scanning, a geometric model can be voxelized, interactive modeling, or hypertexture volumes can be defined procedurally by functions over 3D space. The morphs or intermediate objects must meet the realism and smoothness conditions. The realism condition consists of having the morphs as realistic objects that have "plausible 3D geometry and that retain the essential features of the source and the target." Smoothness involves rendering the morphs to depict a smooth transition from the source to the target. In the warping method, the realism condition is met when the user quickly defines the exact shape of the new warped objects S' and T'. User input plays a key role in designing the transformations of the objects. In the blending portion, the new objects S' and T' are then combined to create one volume, the morph. The user is provided with sufficient control to create a smooth morph.

Warping

User control is a very important aspect to the warping process. In the journal, warping techniques are classified as either techniques that allows only minimal user control or techniques that gives the user control of manually specifying the warp for a collection of points in the volume. Techniques where the user has minimal control consists of a few scalar parameters that automatically determine similarities between the two volumes and then combines the two volumes. Techniques where the user manual inputs the points, the rest of the volume is warped by interpolating a warp function. An example of the two techniques is given where a circle is compressed to the shape of an ellipsoid. When the ellipsoid is stretched back to a circle, the result is three replicas of the ellipsoid. This is an example of a technique where the user has minimal control. However, if the user is able to specify the ellipsoids width in the scaling factors of the original feature lines.

Feature-Based 3D Warping can be implemented using fields. In order to obtain good morphs, a collection of element pairs that define the overall correspondence of the two objects must be specified. The element pairs which consist of lines, points, rectangles and boxes are used "like magnets" to shape a pliable volume. With the presence of these magnets, influence fields develop as a result of the volume changes. The influence fields combine to "shape the volume in complex ways." Each object consists of individual feature elements. These features have a certain spatial configuration and dimensionality.

With the presence of element pairs, the user can select two corresponding features from the target and the source. In order for the source to be transformed to the target, the source must be moved turned, and stretched to match the respectively match configurations of the corresponding feature of the target. In order to achieve this transformation, interpolation and inverse mapping must be performed. Interpolation involves interpolating the local coordinates systems and scaling factors of the two features in order to achieve intermediate positions to form S' and T'. Inverse mapping consists of using the following equations to find all of the points p that correspond with points p' in S'. Equations: px=(p'-c')*x'/sx', py=(p'-c')*y'/sy', pz=(p'-c')*z'/sz'. A "weighted averaging scheme" is used to correspond p' point in S' to every p point in S.

Blending

The main purpose of this process is to meet the condition of a smooth transformation. In the Blending process, mismatches can often occur. This is when some features do not align correctly in certain areas of the morph. These mismatches will have to be fixed in the rendering process to maintain a smooth transformation. In the journal, two methods of blending are suggested. One method involves "cross-dissolving images rendered from S' and T' " which is called 2.5D morphing and the other involves "cross-dissolving the volumes themselves, then rendering the results" (3D morph). 2.5D morphs do not look as realistic as 3D morphs due to the result of incorrect lighting and occlusions. Cross-dissolving can be done either linearly or non-linearly. Interpolating opacities becomes a problem when using the linear-method although it works well for blending the color information from S' to T'.

PROS

The morphing technique provides a solution to the "ghosting problem" found in Beier and Neely's technique concerning feature-based imaging. The morphing technique accounts for gaps and non-linear areas. The warping portion can also make efficient approximations that can allow the real-time speed to become fifty times faster and is "computable to arbitrary accuracy.

The morphing method also provides several advantages to the user. The warping method allows "fine user control" which allows the user to see "realistic looking intermediate objects." The blending portion is under "user control" which guarantees "smooth transitions in the renderings" of objects.

CONS

The warping technique has a draw back. Each point in the warped volume is influenced by all elements. This is because the influence fields can never decay to zero. Another problem consists of time needed to warp a volume is proportional to the number of element pairs. Therefore, a C program will take an ample amount of time in order to warp an object with numerous amounts of element pairs. However, the addition of two functions will expedite the program. This includes approximating the spatially non-linear warping function with a piece linear warp and by introducing an octree subdivision over V which denotes either S or T. Piecewise Linear Approximation involves subdividing V' into a grid format and then warping the vertices in the grid to create V. Non-linear regions can be captured only if a very fine grid is used. Octree subdivision accounts for the "large empty" or transparent regions that are found by constructing an octree over V to avoid scan converting these empty regions.

FUTURE DIRECTIONS

The journal concludes by dividing 3D morphing into three primary aspects in order to provide guidance to the improvement of these areas. In the area of warping techniques, these methods could allow for finer user control, as well as smoother, possibly spline-based, interpolation of the warping function across the volume. More complex, but more expressive feature elements may also be designed. The user interface also leave many areas of improvement such as adding computer-assisted feature identification: the computer suggesting features by landmark data extraction, 3D edge identification, or, as in 2D morphing, by motion estimation. Another possible improvement may be to consider giving the user more flexible control over the movement of feature elements during the morph, the rule by which interpolated elements are constructed, perhaps by key-frame or spline-path motion. For the blending process, blending could allow local definition of the blending rate, associating an interpolation schedule with each feature element.

This technical journal proposes a method that "correctly simulates kinetic depth effect, occlusion and can resolve the missing visibility information by combining z-buffered environment maps from multiple viewpoints." Image-based rendering uses basic images to create other images. Since images are viewed from different view points, "they represent a view dependent information only for the originally generated positions." This concept presents a difficult problem to Image-based rendering. Different effects such as reflection and refraction of lighting must be dealt with. Navigation in an environment using image-based rendering is classified into four levels based upon freedom allowed in user-movement. Discrete viewpoints, discrete view directions: images are rendered or digitized for selecting positions and selected viewing directions. The one that is closest to the desired is displayed. Discrete viewpoints, continuous view directions: one image or a series of images stitched together are used to represent the environment around a certain point of view. Continuous viewpoints, discrete view directions: The user is allowed freedom to continuously translate and rotate. Continuous viewpoints, continuous view directions: Involves the constant translations of the camera view. However, smooth navigation is a problem since complex computer-generated virtual environments are slow to render. This is the category that the proposed method that the journal covers falls into.

Environment Mapping and Morphing

Precomputed views of scenes at selected points allow changes of visibility. A node refers to a selected viewpoint that consists of color and depth information for every direction. Each node has six pyramidal regions which are not normally not all visible at one time. Visibility becomes a problem with nodes when the node's direction of the visualization parameters is different and not the position. The journal presents node morphing a solution to this limitation. By combining the information concerning the depth and visual parameters of the neighboring nodes, an intermediate stage and a combined stage can be created. This approach is similar to the concept of 3D morphing described in the previous journal. The initial process begins with a scene S and a projection P, similar to the source and target of the 3D morphing technique. The combined result is a z-buffered image.

Image-Simplification

In order to simplify the image-space-based rendering, a proposal to represent the environment as linear polygons is suggested. By taking into account all of the node's depth and color parameter properties, a polygonal mesh can be formed in the surrounding environment. This effect creates a spider web effect. Each triangle in the mesh represents an object or part of an object at a certain depth. Image warping is then used to make appropriate projective transformations and to create a realistic morphing effect in the environment. Problems such as "mesh foldovers" can occur, however, the hardware z-buffer is used to resolve these problems. By combining z-buffered images from various nodes using alpha blending and the stencil or the accumulation buffer, multiple nodes are used to fill in gaps or "mesh tears" that develop. The quality of the images is by a pixel-by-pixel basis. The z values for each pixel is compared. If the values are significantly different, the pixel closest to the observer will have better quality. Otherwise, the pixel that is output to the final image will have higher quality. This method as yielded good results. Simple weighted blending is also mentioned in this journal in terms of quality and positioning. The quality of the output pixels relies on a quality-weighted average between triangles. The weighted average of the distance from pixel to pixel accounts for the new pixel positioning.

Triangular Step

This is the step that takes the z-buffered image space and transfers it into object space. This is accomplished in two steps. First, match the object profiles as accurately as possible. Then detect the areas in the depth information that are almost linear and approximate them by triangles. Non-linear areas must be treated seperately. Tecture mapping is implemented by using the same warping process, but texture coordinates must be assigned to each vertex of the 3D triangular image.

PREVIOUS APPROACHES

Prior related works for graphics acceleration in a three-dimensional environment include the traditional methods of reducing the geometric complexity of the scene, reducing the rendering complexity by texture mapping and by various levels of complexity in shading and lighting models, and exploiting of frame to frame coherence with one of the above.

Previous choices of environment map geometry also posed several problems in the past. Methods such as cubical and cylindrical maps have been used, however, spheres are difficult to represent digitally without significant variation in the information density. Cylinders also pose as a problem since they have limiting fields of view to avoid dealing with the "caps", however, they are effective for panoramic views. Cubes do not represent texture information homogeneously, but it is the easiest to represent synthetic images.

This journal describes a method for three-dimensional geometric metamorphosis based on Harmonic Map for any two objects. These objects are topologically equivalent to a sphere or to a disk. Interpolation between these objects must be controlled by specifying a boundary loop and a vertex on the boundary. An advantage to this method is that it works very quickly which allows more time to be spent for interpolation. Although these objects must have the same topology as a sphere or disk, they will be represented as a triangular mesh, or a polyhedron with triangular faces. The journal represents the two objects in a similar format to the previous journals. The objects are referred to as M1 and M2. The initial step to transformation is to find corresponding points between the objects. Once this is done, a series of intermediate objects can be creating by interpolating corresponding points from their original positions to the target. The first step of the proposed algorithm to find the correspondence between points is the development of M1 and M2 to a two-dimensional unit disk D2. Next, the creation of embeddings by Harmonic Map. Harmonic Map creates these embedding through a piecewise linear approximation method developed by Eck et al. These embedding are then labeled as H1 and H2. The objects H1 and H2 are then merged to create a new object Hc. Continuous intermediate objects are then create more easily by interpolation by using Hc. Eck's method involves the positioning of n vertices which make up the boundary segment of the object H on the disk in R2 whose center point is the origin. From my understanding, an object is basically simplified to a circular boundary while still maintaining adjacent relations of vertices, edges, and faces. Interpolation between the source object and the target is calculated by applying simple linear method. This however, seems to present a problem if non-linear areas are present. Therefore, it must have been concluded that this method is only valid for simple linear problems. A prototype system was developed on a Silicon Graphics workstation where Harmonic Map is possible. The user can manually operate transformations, rotations, scaling of objects by using a mouse. The user must specify a boundary loop for both objects in order to calculate embeddings. Each boundary loop is composed of edges and must contain more than three vertices. The direction of the loops must also be the same. A vertex on each boundary loop must also be specified. These vertices will define the relative position of the two boundary loops. These are all conditions that must be met and show the limitations of this method when it is implemented.

FUTURE DIRECTIONS

He journal concludes by offering areas of improvement in the Harmonic Map method. A new method is desired that allows a part of an object be transformed at one time. This can replace the current method where all of the vertices at a correspondence object are transformed simultaneously. The number of boundary controlled vertices is also suggested to be increased in order to account for more complicated objects. I also propose that a more complex non-linear method be utilized during interpolation so that no gapping occurs. Another improvement that was suggested was to develop a method that would "decrease the number of faces of an object without losing any surface features." One possible way may be to implement more algorithms to do more complicated calculations so that the faces can be simplified and they can combined to one larger face more easily. An example of simplifying current methods is given in the next technical journal.

This journal presents another method to performing adaptive real-time rendering for triangulated polygonal models. This method is fairly simplified utilizing image-space, object-space, and frame-to-frame coherences. The unique quality of this method that is different from traditional methods involves "statically generating a continuous level-of-detail representation for the object. Higher detailed representations are used when an object's perception is more important and the lower level detailed representations are used when object is perceptually less significant. The overall purpose of this method is to improve upon the real-time speed of previous works in order to deal with larger or more complicated objects. This can be accomplished by reducing the geometric complexity of a three-dimensional environment. In order to make this simplification, different levels of dynamically computed level-of-hierarchies must be used. By separating the rendering schemes into different parts, run time can be improved since each level will be examined separately. An object can be simplified by applying local algorithms that rely on a local set of rules. If global algorithms are applied, they will optimize the simplification process over the whole object. The simplification of the genus of an object is dependent upon whether the algorithms use global or local rules, or both. These simplification algorithms can be iteratively updated and checked in order to achieve higher quality frame updating and "good visual realism." In order for this method of forming different levels of hierarchy to work, two criteria must be met. It should be possible to "select the appropriate levels of detail across different regions of the same object in real time and different levels of detail in different regions across an object should merge seamlessly with another without introducing any cracks or other discontinuities."

Simplification with Image-Space Feedback

Previous methods of alpha blending have been used to show the representations of changing from one level of detail to another. However, "alpha blending is not the solution since it does not solve the problems of lack of sufficient image-space feedback." Sufficient feedback is important to select the appropriate local level of detail in the object space. It merely tries to disregard any complex areas of detail. Increasing detail in a direction perpendicular to, and proportional to, the illumination gradient across a surface would improve details in regions that constantly change in different lighting. Suggestions of improvements in screen-spaced projection, visibility culling, and silhouette boundaries is also offered.

Merge Tree

A proposed method called merge tree that permits adaptive refinement around any vertex is discussed. A merge tree is constructed upwards from the high detailed mesh to a low detailed mesh by storing parent-child relationships in a hierarchical manner over the surface of an object. A vertex is combined with another as a result of "collapsing an edge." The merging vertex is designated as the child and the other vertex is referred to as the parent. These merge trees, once computed statically, are used during run-time to take advantage of incremental changes in the triangulation. Merge trees can account for vertex deletion and vertex collapsing. These are problems that exist in the previous document concerning Harmonic Mapping. The disadvantage of merge trees, however, is that they do not account for storing color ranges at the nodes of the merge trees. If improvements are made in this area, significant improvements in the quality of the visualization will be the result. Another problem in merge trees can be found in the accuracy of depth. The trees are not perfectly balanced, but are closely within the optimal depths. This is the penalty that is made when trying to improve real time speed of a simulation. The technical journal ends by stating "all of these areas that have been established as still having areas of improvements will be further investigated."

Real-time Triangulation

This task is simplified once merge trees are created. An adaptive level-of-detail mesh representation at real time can be created. Mesh reconstruction involves two steps. The first step is the determination of vertices that will be needed for reconstruction. This is accomplished by determining the primary vertices using screen-space projections and normal vector cones associated with merge trees. Once this is done, the secondary display vertices that are needed to avoid mesh fold-overs can be found. The next step would be the determination of the triangulation amongst them.

PRIOR WORKS

Most of the simplifications suggested within this document stem from prior research. Prior works concerning the formation of different levels of detail include works by Grosse et al. Grosse et al devise a wavelet decomposition method of the input data samples. This method involves the defining of "wavelet space filters that allow changes to the quality of the surface approximations in locally-defined regions" which allows the level of detail around any region to adaptively refine in real time. Other past works include the simplifications in the area of general surfaces. Progressive meshing has also proved to be an important contribution to providing a continuous resolution representation of polygon meshes. However, there still remain areas of improvement in adapting progressive meshing for performing selective refinement in an efficient manner. AN example is that there is still no efficient method for incrementally updating the selective refinements from one frame to another.