Unstructured Volume Rendering Jian Huang CS 594 Spring 2002 This set of slides reference slides developed by Prof Torsten Moeller SFU Canada Grid Types Structured Grids uniform regular rectilinear curvilinear Unstructured Grids regular irregular hybrid curved Unstructured Grids still assume scalar data translation as before translation matrix still the same classification as before because it is still a scalar data type shading same shading model s interpolation problematic compositing still BTF or FTB problem how to sort Ray Casting Garrity 1990 needs to figure out where the ray is going then needs to figure out how to integrate along that ray assumes arbitrary polyhedra as opposed to just tetrahedra as many other algorithm image order FTB Ray Casting basic algorithm For each ray find intersection with first cell interpolate a color opacity value while not outside the volume find exit point of ray in cell interpolate a color opacity value integrate opacity color along ray within cell Ray Casting intersection point just look at all faces compute the intersection with all faces of the current cell and take the nearest requires cell organized data structure first cell only consider faces that belong to only D one cell A C B Ray Casting intersection point Intersection of ray defined by point d and direction vector e n a n d t n e n b a c a e b a d c Ray Casting rendering integral classify scalar values at nodes into color opacity it then linearly interpolates these values within a plane for the intersection points integrate along the cell by multiplying the average with the distance another linear interpolation at work needs the gradient for shading D A C B Ray Casting gradients Vertices are not nicely aligned in x y z direction hence we need to solve an equation system using any three pairs of neighboring points x0 x1 x 2 y0 y1 y2 z0 x f z1 y f z 2 z f f 0 f1 f 2 Ray Casting conclusion Bottleneck size of image of pixels results for 5122 image 960 cells 81 6 seconds 1490 cells 147 6 seconds 16 896 cells 149 2 seconds 381 548 cells 591 6 seconds may miss small polyhedra Cell Projection Max Hanrahan Crawfis 1990 Shirley Tuchman 1990 object order cannot miss small structures makes sense if one cell projects to many pixels based on tetrahedral decomposition Cell Projection basic algorithm Decompose volume into tetrahedral cells classify each tetrahedron according to its projected profile relative to a viewpoint find the positions of the tetrahedra vertices after the perspective transformation decompose projections of the tetrahedra into triangles find color and opacity values for the triangle vertices using ray integration in the original world coordinates scan convert the triangles on a graphics workstation Cell Projection tetrahedra Decompose volume into tetrahedral cells 5 or 6 tetrahedra are possible want least amount of computation for 5 need to make sure that there will be no cracks Cell Projection tetrahedra for 5 need to make sure that there will be no cracks I e edges need to line up properly Cell Projection projection classify each tetrahedron according to its projected profile relative to a viewpoint find the positions of the tetrahedra vertices after the perspective transformation Projected Tetrahedra decompose decompose projections of the tetrahedra into triangles Cell Integration find color and opacity values for the triangle vertices using ray integration in the original world coordinates Sabella assumes that volume density x y z glows with an energy of C per unit length and absorbs with an optical density of C and are constants for a fixed material I C P t exp a b dt P u du a t Cell Integration How can we evaluate the rendering integral t C b I P t exp P u du dt a a t C bd exp P u du dt a a dt b C 1 exp P u du a C 1 exp D Cell Integration How can we evaluate D linear interpolation A P a P is the ray equation f P u f A f B f A u a b a and now gu h b b a a D P u du f P u du b gb h a ga h gu h du v dv t S t u du 0 S gb h S ga h S f B S f A g g Cell Integration t S t u du How can we find S 0 u is basically the transfer function it s integral S t over a linear function could be precomputed there is no restriction to the transfer function really scan convert the triangles on a graphics workstation Projected Tetrahedra Shirley et al find color and opacity values for the triangle vertices using ray integration in the original world coordinates at the thickest point scan convert the triangles on a graphics workstation then linearly interpolate this integral on the scanline can be implemented in hardware I 0 Cell Integration Max et al the integral is computed for each pixel object scanline along the front and back face to determine front and back values of S u then we evaluate I with our formula Depth Sorting But we need to repeat all these steps for all cells how to sort those cells Max et al topological sort first create a directed graph nodes cells edges faces direction of edge means in front of Depth Sorting do a topological sort of this graph in linear time linear in the order of the number of edges only works if there are no cycles Rendering by Slicing Yagel et al 1996 uses the texture mapping hardware only implemented for tetrahedral grids cannot use the same algorithm as for regular grids where the slices are aligned along major axis we have to intersect the underlying geometry Slicing basic algorithm For any change in the viewing parameters transform grid points into image space determine zmin and zmax dz zmin zmax NumSlices for i 1 to NumSlices do slice the transformed cells with plane zslice render 2D polymesh and compose hardware zslice zslice dz for any change in the viewing parameters re render polylist Slicing adaptive slicing Problem might miss small detail idea just keep adaptively subdividing until we sliced every polyhedra in that particular interval the compositing step must take care of different distance of slices Slicing progressive slicing Problem How many slices do we need for a good image Idea time quality tradeoff start with very few slices interactive display as long as the user isn t changing the viewing parameters keep refining hence progressively better images Splatting Mao Hong Kaufman 1995 96 extends the regular splatting ideas to irregular domain based on a resampling step based on Poisson distribution of new sample points Splatting basic algorithm For each cell compute a random point compute its extent sphere ellipse by interpolating the
View Full Document
Unlocking...