Splatting Of Curvilinear Volumes

Splatting Of Curvilinear Volumes - Transcript

S platting
X iaoyang

of Curvilinear

Volumes

Mao Lichan Hong and Arie Kaufman

Department of Computer Science State University of New York at Stony Brook 794 4400 Stony Brook NY 1 1

A bstract
T his paper presents a splatting algorithm for volume rendering of curvilinear grids A stochastic sampling technique called Poisson sphere ellipsoid sampling is employed to adaptively resample a curvilinear grid with a set of randomly distributed points whose energy support extents are well approximated by spheres and ellipsoids Filter kernels corresponding to these spheres and ellipsoids are used to generate the volumerendered image of the curvilinear grid with a conventional footprint evaluation algorithm Ezperimental resulta show that our approach can be regarded aa an alternative to existing fast volume rendering techniques of curvilinear grids

1

I ntroduction

V olume rendering algorithms can be classified as either feed backward or feed forward that is the image is generated either by mapping the image plane back to the volume space e g ray casting 16 63 or by projecting the volume data onto the image plane The feed forward approach is further divided into two types One is usually called cell projection 7 12 201 with which a cell defined by eight neighboring sample points is projected onto the screen and its contribution to the pixels under its projection extent is calculated and cornposited with the contributions from the previously projected primitives The other method which is usually referred to as splatting 5 18 191 treats each sample point in the volume as a source of energy and projects its energy support kernel onto the screen In both types the projection primitives must be sorted with respect to the viewpoint so that the composition is in either a front to back or backto front order While ray casting has the reputation of producing high quality images cell projection and splatting are often preferable due to their advantage in achieving interactive rendering speed Although there is no consensus on the nomenclature volume data sets are commonly classified ELS rectilinear curvilinear or unstructured according to their
Current address Computer Language Section Electrotechnical Laboratory l l 4 Umeeono Tsukubs Ibaraki 305 Japan

g rid structures 21 A rectilinear grid has an orthographical grid structure where each cell is a box like hexahedron When a rectilinear grid is defined by regularly distributed sample points the grid is said to be regular A curvilinear volume which is the target structure for this paper is a regular rectilinear grid that has been subjected to non linear transformations so as to fill a volume or warp around an object of complex shape while preserving the grid topology Usually the regular grid defining the logical organization of the grid is called the computational space and the warped structure is called the physical space of the curvilinear grid Direct volume rendering of a curvilinear grid using a feed backward algorithm is particularly difficult because it is non trivial to locate a sample point in the grid Ray casting of curvilinear grids has been studied by Uselton 15 and Ramamoorthy ll among others Since a curvilinear grid may consist of cells of drastically different sizes sampling with a constant interval along a ray is undesirable and usually sample points are taken at the intersections of rays and cells However the detection of the cell through which a ray first enters the volume the identification of the face through which a ray exits a cell and the interpolation from the surrounding grid points of a sample point are among those operations that tend to be very time consuming To avoid these expensive operations Friihauf presented a different kind of approach to casting rays in computational space 3 However as mentioned by the author himself the numerical solution to the integration along the ray curves in computational space is not exact On the other hand the cell projection of curvilinear grids has special problems due to the irregularity of cell shapes Van Gelder and Wilhelms 17 have proposed three methods of different approximation levels To obtain the cell visibility ordering which may not always be possible to find without further decomposition of the cells they assume that each cell is a six sided convex polyhedra hexahedron and they extend the well known linear time topological sorting algorithm 7 221 for curvilinear grids Another class of rendering algorithms for curvilinear grids decomposes

See color plates page CP 9
1 070 2385195 4 00 Q 1995 IEEE 61

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

t he cells of curvilinear grids into tetrahedra and then performs tetrahedron projection 7 12 231 This approach multiplies the number of projection primitives by five Furthermore interpolating only from the four vertices of a tetrahedron may also result in some error The motivation of our work is to explore the feasibility of using splatting for curvilinear volumes As stated in 19 211 the direct extension of Westover s splatting algorithm to curvilinear grids is difficult because in many cases it is almost impossible to select a simple splatting kernel for each grid point The idea presented here is to resample the curvilinear grid with a set of new points whose energy support extents in the 3D physical space can be approximated by spheres and ellipsoids Westover splatting algorithm 18 is s extended to splat the new sample points by using these spheres and ellipsoids as the support extents of the reconstruction filter kernels To approximate the energy function represented in the original grid as accurately as possible without using too many sample points an adaptive 3D stochastic sampling method called Paid8on sphere ellipsoid Sampling is employed The reasonable rendering speed and image quality that we have achieved in our experiments suggest that our approach can be regarded as an alternative to fast volume rendering of curvilinear grids In Section 2 the detail of the Poisson sphere ellipsoid sampling technique is described The splatting algorithms for sphere ellipsoid kernels are discussed in Section 3 Section 4 demonstrates our experimental results with two curvilinear data sets

2

R esampling

2 1 P oisson Sphere Ellipsoid Sampling A v olumetric data can be viewed as a collection of sample points grid points and in volume rendering the original signal is reconstructed from these sample points While ray casting reconstructs the signal at a point by interpolating the point value from its neighboring samples splatting reconstructs the original signal by spreading the energy of each sample point into space Although a faithful reconstruction usually requires some filter kernels of infinite extents only filter kernels truncated to reasonably small sizes are used in practice to reduce the computation time Such a illter kernel of local support should be designed so that 1 the reconstructed signal does not leave any gaps in 3D space 2 the reconstructed signal is a good approximation of the original signal With the splatting of rectilinear grids this can be realized by using properly overlapping sphere ellipsoid filter kernels In the case of a curvilinear grid however each grid point can be warped to an arbitrary position in 3D physical space and the grid structure can be of any shape Therefore it is difficult to define for each grid point a filter kernel which satisfies the above two requirements simultaneously while having a simple geometric shape

and a reasonably small size The solution we provide here is to resample a curvilinear grid in 3D physical space with a set of new sample points whose energy support extents are well approximated and then splat the energy of these new points onto the image plane to generate the volume rendered image Obviously the simplest solution is to resample a curvilinear grid into a rectilinear grid As a curvilinear grid may consist of cells of greatly differing sizes e g 10 000 times difference such an approach may either cause the loss of important information or result in a huge data set 3 211 Adaptive resampling using octree data structure has been suggested as a solution to this problem 21 but again the large difference in cell sizes can easily result in a very deep octree Furthermore with rectilinear or the octree resampling imposing a regular structure on a curvilinear grid due to unmatched topology usually produces a lot of empty cells though the octree approach can alleviate the problem Another possible solution is to divide a curvilinear grid into several subregions and perform regular resampling of different resolutions for each region separately Considering the reconstruction from these sample points however the sudden change of sampling rate around the border of two adjacent regions may result in some visible artifacts 9 Based on the above observations a resampling technique tailored for the splatting of curvilinear grids should possess the following properties 1 Each resampled point has a well defined energy support extent 2 The sampling rate changes adaptively over the grid to avoid either skipping small features in the original data or using too many sample points 3 The changing of sampling rate over the whole grid is smooth in order to avoid producing artifacts in the resulting image 4 Sample points are expected to be evenly distributed within any local area to reduce the reconstruction error We found that a generalization of the well known stochastic sampling technique called Poisson disk sampling can fortunately meet all these requirements Poisson disk sampling is a Poisson stochastic point sampling process with the constraint that no two points be closer than a g iven m inimum distance In other words each sample point is surrounded by a hard disk inhibiting the existence of other sample points in that area Poisson disk sampling was originally analyzed by Yellott to model the photoreceptors of monkey retinas 24 and then has been well studied in the discipline of ray tracing 2 8 91 The main reason for adopting stochastic sampling for ray tracing is that aliasing caused by regular image plane sampling can be turned into broad band noise which is much less objectionable to the visual system of human beings than coherent aliasing defects The minimum

62

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

d istance restriction of Poisson disk sampling prevents the clamping of points and enforces the random points to be distributed evenly over the whole region Such a property of Poisson disk sampling reduces the reconstruction error caused by non regular sampling and pushes the noise in the resulting image into high frequencies Theoretical analysis of Poisson disk sampling regarding its spectral property noise control and optimal reconstruction is given in 2 8 lo Poisson disk sampling can be easily generalized to higher dimensions Mitchell suggested such an extension for sampling along other parameter dimensions in distributed ray tracing lo He also mentioned the possibility of adding some anisotropic property to the spectrum of Poisson disk sampling by using an ellipse or other shapes instead of a hard disk A 3D version of Poisson disk sampling is used to generate a set of randomly distributed geometry primitives for the fast previewing of 3D volume data in 13 In this paper we extend the Poisson disk sampling to 3D space and define it as Poisson sphere ellipsoid sampling More specifically we resample a curvilinear grid with randomly distributed points each of them having a surrounding sphere or ellipsoid region which inhibits the existence of other sample points in that region The reason for using the anisotropic sampling of ellipsoids is that the original curvilinear grid usually has different sampling rates for the three dimensions and the resampling should be thus designed to capture the details along each dimension without using too many sample points Since the average sampling rate of Poisson disk sampling is decided by the inverse of the minimum distance we can adaptively change the sampling rate of our Poisson sphere ellipsoid sampling over a curvilinear grid by adjusting the sizes of the spheres or ellipsoids according to some local properties of the grid Figure 1 depicts the concept of our Poisson sphere ellipsoid disk ellipse sampling

the 3D curvilinear grid This is realized by performing the anisotropic sampling along the three dimensions of the grid structure instead of along the three coordinate axes of the 3D physical space We call the directions of three grid dimensions at an arbitrary position in 3D physical space the grid orientation of that position and the grid orientation at a grid point is measured with its Jacobian matrix Therefore given a 3D curvilinear grid whose grid structure has the three dimensions t 9 and C and the physical space coordinates for a grid point is aqk vijkc Zijk 1 5 i 2 I 1 5 j 5 m 1 2 k 5 n where I m n are the numbers of grid points along dimension t q and C respectively we first calculate the Jacobian for each grid point as the central difference between adjacent grid points

Each column of J is a vector indicating the grid orientation of that dimension The grid orientation at an arbitrary position is defined by interpolating each column of the Jacobian from its surrounding grid points For the purpose of adaptive resampling two factors should be taken into account to decide the local sampling rate One is the local grid size which is measured with the sizes of cells along each dimension of the grid structure and the other is the variance of the scalar value The erid size S and scalar value variance u at each grid poiit are calculated for each dimension separately in the following way

where 8 min
c y ci ljk u CijkJ2r QE s y z cijk 67 q Ci ljk 2 v

w here UC vi ijk v ijk Vijk V i ljk 2 H ere Vijk denotes the scalar value at each grid point The reason for choosing the smaller distance between adjacent grid nodes is to avoid skipping any small features contained in the original grid Like the grid orientation the grid size and scalar value variance at an arbitrary position are interpolated from those of the eight surrounding grid points Now the sampling rate along each dimension is given in the following way Figure 1 curvilinear Poisson sphere ellipsoid grid resampling of a X u v l s if u v otherwise

2 2 Sampling Algorithm Unlike in regular resampling in stochastic sampling it is easy to make the resampling follow the topology of

v is a threshold of scalar value variance only those values of u which exceed v will affect the sampling rate X which is independent of the local grid properties is a constant for controlling the sampling rate

63

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

H ierarchical sampling as described in 8 can be easily achieved by increasing the value of X successively For any position local sampling rates are always calculated separately for the three directions of the grid orientation Ideally ellipsoids should be used except for those positions where the local sampling rates along the three directions are identical Consider the splatting operation see Section 3 Since the footprint evaluation of an ellipsoid kernel is not only more time consuming than that of a sphere kernel but also an approximation with some error 19 our criterion is to use as few ellipsoids as possible However as the radius of a sphere should be determined by the highest sampling rate among the three directions a v ery l arge number of spheres may be required for those regions consisting of very thin or sliver cells Therefore to decide whether a sphere or an ellipsoid should be used for a position we check the maximum ratio of local sampling rates along the three directions and if it is larger than a given constant an ellipsoid is used instead of a sphere The constant represents a threshold such that the rendering time will not be further improved by trading the use of an ellipsoid for more spheres When an ellipsoid has to be attached to a point its orientation and size are calculated in the following way Denoting the Jacobian and the inverse of sampling rate for an arbitrary position in the 3D grid as I1 and R T T T we first sort the three elements of R into 1 2 a nd rz in descending order and choose 1 a nd its corresponding column in Jp as the length and direction of the ellipsoid major axis respectively Then we multiply 2 w ith the corresponding column in Jp and project the resulting vector onto the plane which is perpendicular to the major axis to obtain the length and direction of the second axis The third axis of the ellipsoid is obtained by multipling the remaining column in Jp with T Q a nd projecting it to the cross product of the two existing axes In summary the sampling algorithm is as follows For each cell cijk Generate a random point p t q C 7 C E 0 l Map 0 vr C t o a point P z y Z in physical space If P is not covered by existing sphere ellipsoid extents Interplate J S u to obtain Jp S up Normalize each tuple of Jp Calculate 7z from sp and uz Calculate the ratio of every two component of 7z If the maximum of the ratios is smaller than C Append the point to the sphere point list Else append the point to the ellipsoid point list A stratified sampling method lo is adopted in our algorithm In other words the generation of random points is carried out separately cell by cell For each cell three pseudo random numbers in 0 l are generated as the computational space offset of a point

Thus the position of the point in physical space and all other related values can be easily interpolated from its surrounding eight grid points This approach also has the advantage that it can spread random points into 3D space rapidly The above sampling process is repeated until the 3D grid is fiZZ which means that either the expected number of points have been generated or no point has been generated for a certain period A major disadvantage of such a so called dart throwing algorithm is that it is usually time consuming and difficult to terminate 8 lo A useful way to achieve Poisson disk distribution is to store a small pattern in a table and replicate it to fill the whole region 12 81 However as the sampling rate changes drastically over the grid this method is obviously unsuitable for our situation Another possible approach is to use the point relaxation method 14 First the required number of points are randomly generated and placed in a 3D grid F or e ach point a repulsive force is defined which falls off linearly to zero within the sphere ellipsoid extent of the point and then points are moved around according to the total repulsive force from the surrounding points Although it is easier to design a stop criterion for this process than in the dart throwing algorithm such as a bound E for the average repulsive force imposed on each point with an ideal Poisson sphere ellipsoid distribution the average repulsive force should be 0 moving a point in physical space especially crossing over cells complicates some operations such as the interpolation Fortunately the resampling is only performed once at a preprocessing stage and hence the complexity of the dart throwing algorithm is not critical

2 3

Discussion

T he Poisson sphere ellipsoid sampling possesses all the properties mentioned in Section 2 1 First the sphere ellipsoid region attached to a sample point can be naturally chosen as the energy support extent of the sample point By using splatting kernels whose support extents are identical to these spheres and ellipsoids we can prove that the generated image does not leave any gaps in 3D space Let us assume a point P is not covered by any filter kernels This means that the distance between P and any other sample points is larger than the sizes of the support extents of these points However this leads to a contradiction because a new point should be added to this position according to our sampling algorithm Therefore we can say that any position in the 3D grid is covered by the filter kernel of at least one sample point provided we have an ideal result of Poisson sphere ellipsoid resampling The sampling rate is adaptively changing based on the local grid size and scalar value variance Since these two values for an arbitrary position are obtained by interpolating from the surrounding eight grid points which are further decided by the proper

64

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

t ies of their neighboring grid points the changing of the sampling rate over the grid can be expected to be smooth Finally as mentioned in Section 2 1 a nice property of Poisson sampling with minimum distance constraint is that it can prevent the clamping of sample points and reduce the reconstruction error caused by the non regular resampling

The equation of the ellipse is Ax2 By2 Dxy 1 D d 2 where A a B b The equation can be rewritten as XTQX 0 where X Q 2 Di2 i

1

3

S platting

A fter a curvilinear grid is resampled to a set of new points whose energy support extents are defined as spheres and ellipsoids Westover fast footprint evals uation technique 18 can be extended for the splatting of curvilinear data set To accelerate the rendering speed Westover suggested precomputing a generic footprint lookup table which represents the integral of a unit sphere kernel along the p direction Then during the rendering phase the footprint table of a view transformed kernel can be obtained by establishing a mapping between the kernel projection extent on the screen and the generic footprint table In our approach since the sizes and orientations of the kernels can be drastically different there is no way to compute a common footprint table for all sample points as in the case of rectilinear grids That is the footprint of every kernel has to be computed on the fly during the rendering process Therefore effort has to be made to improve the computation time at every stage of the footprint evaluation 3 1 E xtents and Mappings T he footprint evaluation of a sphere kernel is trivial because it is a mapping from a scaled circle to a unit circle and is performed in the same way as in 18 The projection of an ellipsoid onto the viewing plane is an ellipse The footprint table for an ellipsoid filter kernel can be obtained by mapping the ellipse to the unit circle From the resampling phase described in Section 2 we can obtain the equations for ellipsoids in object space During the rendering phase every ellipsoid is transformed from object space into viewing space Whenever the viewpoint changes the transformation matrix needs to be computed once for the whole volume and the multiplication of the transformation matrix with the object space ellipsoid equation needs to be performed for each ellipsoid According to Westover 18 denoting the ellipsoid equation in viewing space as ax2 by2 a2 day ext fyz 1 the x and y extents of the ellipse on the viewing plane are

The ellipse can be obtained from the transformation of a unit circle with the following operations First the unit circle is scaled by the length of the two axes and then rotated about the viewing direction the z axis of the viewing coordinate system with angle 8 In other words the ellipse equation can be defined as XTRTpUSRX l s where S R 1 0 0 09 2

I9 i Jl Here so and sy are the length of the two ellipse axes From Equations 1 and 2 we have Q RTpUSR Thus we obtain the following equations

If D 0 or A B the ellipse is simply a scaled circle Therefore 8 0 and s sy a Otherwise from Equations 3 and 5 we have A B cos28 And from Equation 4 we have D sin28 Thus we can eliminate lowing equation

s and 8 and obtain the fol

tan28 A That is 0 0 5arctan Knowing the value of 8 we can then solve for ii and sv as follows

65

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

I n the case of 6 0 the renderer cheats and rotates the ellipse an additional 0 01 degree about the viewing direction to make s8 and sy computable After we calculate the values of 8 sa and sy the mapping from a point of the ellipse to the unit circle becomes M SEX This time consuming calculation of the mapping matrix needs to be performed once for each projected ellipsoid in the rendering phase Notice that our method of solving 0 sg and sy is slightly different from that given in 18 and is obviously more efficient

3 2

Special

Considerations

T he generic footprint table represents the integral of a unit sphere kernel along direction The mapping for generating the footprint table for an arbitrary kernel simply selects or interpolates the value from the generic footprint table and gives no consideration to the thickness of the kernel along the viewing direction This is not a problem in the case of rectilinear volumes where a common kernel is used for every sample point With our approach however since we have to deal with sphere ellipsoid kernels of different sizes and orientations the thickness of the kernels along the viewing direction should be taken into account when the color and opacity values are accumulated For a sphere kernel the effect of thickness can be calculated by simply multiplying the entries of the footprint table by the diameter of the sphere For an ellipsoid defined as ax2 by2 cz2 dxy exz fyt 1 we approximate the thickness as the distance between the two points where the ellipsoid and the ray passing through the center of the ellipsoid intersect In the view coordinate system the ray can be described in the following parametric format a 0 y 0 a t T herefore the distance is 214 As a feed forward volume rendering technique the splatting algorithm requires a visibility ordering of the projected kernels to perform the composition on the image plane either in a back to front or a fiont toback order Here we approximate the visibility order of splatting kernels with the ordering of their centers Unlike rectilinear grids there is no implicit ordering for the sample points used in our approach and thus the sorting of sample points according to their positions with respect to the viewpoint becomes necessary Since computing the sorting order on the fly in the rendering phase is obviously too time consuming and unacceptable we pre compute and store three sorted lists of the sample points for the 2 y and z directions respectively in the object coordinate system At the rendering stage based on the viewing direction one of these three sorted list is selected and traversed in either a back to front or front to back order

Recalling the property of our resampling algorithm see Section Z it can be expected that within any local area the sample points are evenly distributed and there is no significant change in the sizes and orientations in the case of ellipsoids of the kernels Therefore for an area entirely covered by either sphere or ellipsoid kernels the approximation of visibility ordering based on the kernel centers can be expected to be correct except for the overlapping regions This has been known to be a problem even in the conventional splatting algorithms for rectilinear grids 19 For the area containing both the sphere and ellipsoid kernels such an approximation may introduce some errors since a sphere may be occluded by an ellipsoid even when the center of the sphere is in the front of the center of the ellipsoid However such a rare situation only occurs at the border between a sphere kernel area and an ellipsoid kernel area where the radius of a sphere kernel is close to the smallest axis of an ellipsoid This situation can be rectified by easing the transition between spheres and ellipsoids through the use of small ellipsoids around the border

4

E xperimental

Results

O ur curvilinear splatting algorithm has been implemented in the VolVis system version 2 0 l on an SGI Onyx workstation with two R4400 1OOMNZ CPUs and 6Pmegabyte memory running Iris 5 2 operating system VolVis is a comprehensive diversified and high performance volume visualization system developed at SUNY Stony Brook It supports a variety of volume rendering algorithms ranging from fast rough approximations to accurate volumetric ray tracing on various grid structures Our new splatting algorithm adds yet another rendering option to VolVis The first volume data set used in our experiments is the NASA blunt fin data set The original curvilinear data set of 40 x 32 x 32 is resampled with 79971 sphere points and 5041 ellipsoid points Plates la and lb show the distribution of these sphere points and ellipsoid points respectively The threshold of the maximum sampling rate ratio C was set to 10 and we can see that ellipsoids are used only in the regions near the back plate and bottom fin which consist of very thin cells The bound of scalar value variance Y is specified as 4 that is for those regions where the scalar value variance is larger than 4 times the average variance in the grid sampling rates will be raised accordingly As we can see in both Plates la and lb more sample points are placed in the area near the entry of air Plates lc through lf are the images generated with our splatting algorithm The transfer functions which map low density values to blue and high values to red are shown on the right side of each image Plates lc and Id show the images from the two opposite sides of the grid and Plate le is obtained by rotating Plate Id 30 about the a axis The render

66

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

i ng time for generating Plates lc to le whose sizes are 300 x 300 is about 14 seconds Plate lf is produced by mapping the sample points of low density values to 0 opacity The rendering time for this image is dramatically reduced to 5 seconds by skipping all the transparent sample points This is also a very plausible result which can only be achieved with a feed forward algorithm In many cases large parts of the volume data set are not of interest to the user and it is desirable to quickly skip over these parts Our second data set is obtained from a fluid dynamics simulation of the flow around a butterfly valve in a pipe 4 The purpose of the simulation is to investigate the distribution of pressure around the butterfly valve which is known to be the main cause of the shaking of an open valve The resolution of the data is 30 x 1 8 x 1 9 and the grid structure can be partially understood from its bounding box and cross sections shown in Plates 2c and 2d Water flows through the open valve from right and causes some uneven distribution of pressure around the valve The original data set is sampled to 17352 sphere points Plate 2a and 394 ellipsoid points Plate 2 b P lates 2e and 2f are the two volume rendered images of pressure using our splatting algorithm corresponding to the viewing angles shown in Plates 2c and 2d respectively The rendering time for the splatting of this data set image size 300 x 300 is 4 seconds For all the images shown here a 100 x 100 generic footprint table containing the integral of a unit sphere linear filter is precomputed and used for the fast footprint evaluation of the splatting kernels The extent of the splatting kernel is identical to the sphere ellipsoid region of the point though changing the sizes of the splatting kernel is a tradeoff between image quality and rendering time Shading is not considered in our current implementation although it is not impossible because the offset of each sample point in computational space is known and the normal can be easily interpolated from its surrounding grid points Further improvement of image quality can be expected by using other filter kernels such as Gaussian filters As for the space requirement of the algorithm a sphere point requires 17 bytes to store its radius and position and an ellipsoid point requires 49 bytes to store its s calar v alue position and the lengths and directions of its three axes Also we need three lists of the points for the purpose of the visibility ordering The total memory space required for the blunt fin data set is about 3 megabytes and for the valve data set is less than 2 megabytes

5

C oncluding

Remarks

A n ew splatting algorithm for the direct volume rendering of curvilinear grids is presented With the proposed approach a curvilinear grid is resampled with a set of new sample points whose energy support ex

tents are well approximated with spheres or ellipsoids and thus the conventional splatting algorithm can be extended for rendering the curvilinear grid A stochastic sampling technique called Poisson sphere ellipsoid sampling is employed to adaptively resample the grid without losing detailed information and significantly raising the sampling rate Experimental results show that both the image quality and rendering time of our algorithm are close to or competitive with other existing feed forward volume rendering techniques for curvilinear volumes The most attractive advantage of direct volume rendering is that it allows users to view different parts of a 3D data set simultaneously and hence helps them to quickly find an area of interest for further exploration Since curvilinear volume data are commonly acquired as the simulation result from CFD and FEA a fast volume rendering algorithm which enables users to interactively change viewing angles map data in different ways and animate the different simulation steps is more important than slower algorithms that generate high quality images Therefore the new splatting technique presented in this paper has a potential to be a very effective tool for the fast and interactive preview of curvilinear volumes A major issue left for future research is how to reduce the error from the following three aspects resampling non regular resampling and the overlapping of splatting kernels Theoretically higher order interpolation such as cubic interpolation is more desirable for reducing reconstruction errors 19 As the resampling is performed at a preprocessing stage this kind of interpolation method can be used Although Poisson disk sampling can prevent high level errors a reconstruction from non regular sample points usually needs to be normalized by the reconstruction filter Since the splatting is a feed forward algorithm there is no direct way to enforce such a normalization Actually the splatting algorithm for rectilinear grids also has the same problem which is mainly caused by the truncation of filter support extents It is also referred to as not summing to one problem by some researchers Increasing the size of the splatting kernels may improve the situation but this is a trade off between image quality and rendering speed Therefore exploration of other solutions is required To accelerate the rendering speed the splatting algorithm actually approximates the integral of each kernel along the viewing direction separately and then composites them either in a front to back or back to front order Therefore the visibility order for the overlapping area of filter kernels is incorrect Westover suggested the sheet buffer technique to partially solve this problem A s imilar concept may be adopted for our approach b y dividing the sample points into subregions Currently the splatting algorithm is implemented through software A further improvement of render

67

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE

i ng speed can be expected with the use of hardwareassisted polygon approximation as described in 5 Another direction of future research is to extend the algorithm for rendering other kinds of volume data such as unstructured cell data and scattered data Exploring the proposed stochastic resampling technique for solving other visualization problems of curvilinear grids is also one of our major concerns

D P O1

Mitchell 1991 Spectrally Optimal Sampling for Distributed Ray Tracing Computer Graphics 25 4 157 164

WI

S Ramamoorthy and J Wilhelms 1992 An Analysis of Approaches to Ray Tracing Curvilinear Grids Technical Report UCSC CRL 92 07 University of California at Santa Crux P Shirley and A Tuchman 1990 A Polygonal Approximation to Direct Scalar Volume Rendering 1990 Workshop on Volume Visualization 63 69

A cknowledgments
T his work has been supported by the National Science Foundation under grant CCR 9205047 and by the Department of Energy under the PICS grant Special thanks to Issei Fujishiro Taosong He Claudia Silva Hanspeter Pfister and Sidney Wang for helpful discussions We would also like to thank Akio Kimura of Kubota Inc in Japan for the valve data set VolVis can be obtained by sending email to volvisOcs sunysb edu

WI

I31 T Saito 1990 Real time Previewing for Volume Visualization 1994 Symposium on Volume VisuaZization 99 104

P4 WI

G Turk 1991 Generating Textures on Arbitrary Surface Using Reaction Diffusion Computer Graphics 25 4 289 298 S Uselton 1990 Volume Rendering of Computational Fluid Dynamics Initial Results Technical Report RNR 91 026 NAS NASA Ames Research Center MoflCett Field California Upson and M Keeler 1988 The V Buffer Visible Volume Rendering Computer Graphics 22 4 59 64 Van Gelder and J Wilhelms 1993 Rapid Exploration of Curvilinear Grids Using Direct Volume Rendering Visualization 93 70 77 IEEE Computer Society Press

R eferences

P I R

Avila T He L Hong A Kaufman II Pfister C Silva L Sobierajski and S Wang 1994 VolVis A Diversified Volume Visualization Sys94 31 38 IEEE Computer tern Visualization Society Press Dippe 1985 Antialiasing Through Stochastic Sampling Computer Graphics 19 3 69 78 Friihauf 1994 Raycasting of Nonregularly Structured Volume Data EUROGRAPHICS 13 3 C294 2303 94

D61C P71A PI

PI M PI T

PI A

Kimura 1991 Computational Fluid Dynamics applied to Butterfly Valve TechnicaZ Report No 3s Kubota Inc

L Westover 1990 Footprint Evaluation for Volume Rendering Computer Graphics 24 4 367 376 Westover 1992 Splatting A Parallel FeedForward Volume Rendering Algorithm Ph D Thesis University o f N orth CaroHna at Chapel HilI Wilhelms 1991 A Coherent Projection Approach for Direct Volume Rendering Computer Graphics 25 4 275 284 J Wilhelms 1993 Pursuing Interactive Visualization of Irregular Grids The Visual Computer 9 450 458 1993 Williams 1992 Visibility ordering meshed polyhedra ACM Bansactions on Graphica 11 2 103 126

L El91

D 151

Laur and P Hanrahan 1991 Hierarchical Splatting A Progressive Refinement Algorithm for Volume Rendering Computer Graphics 25 4 285 288 Levoy 1988 Display of Surfaces from Volume Data IEEE Computer Graphics and Applications 8 3 29 37 1988

J PO1

PI M PI N

WI

Max P Hanrahan and R Crawfis 1990 Area and Volume Coherence for Efficient Visualization of 3D Scalar Functions 1990 Workshop on Volume Visualization 27 33 McCool and E Fiume 1992 Hierarchical Poisson Disk Sampling Distributions Graphics Interface 94 105 92

P 21P

PI M PI D

P 31 P Wiiams

1992 Interactive Splatting of Nonrectilinear Volumes Visualization 92 37 44 IEEE Computer Society Press

Mitchell 1987 Generating Antialiased Images at Low Sampling Densities Computer Graphics 21 4 65 72

241 J Yellott 1983 Spectral Consequences of Photoreceptor Sampling in the Rhesus Retina Science 221 382 385

68

Proceedings of the 6th IEEE Visualization Conference VISUALIZATION 95 1070 2385 95 10 00 1995 IEEE