From Solids to Volumes So far we ve considered surfaces and solids every solid is bounded by a closed surface Sometimes we want to model data with no clear boundaries like a cloud for instance Today we ll consider models of this type vs solid volume Volumes as Scalar Fields One way to think of volumes is as scalar fields at each point in space we assign some value F typically this value is probably a density value but in principle it might be any scalar value Such volume data is heavily used in several key areas medical imaging Magnetic Resonance Imaging MRI ultrasound scientific visualization weather simulation simulating aerodynamics of airplanes astrophysical simulations e g galaxy collision stress testing materials 1 Implicit Volumes This description of scalar fields sounds like implicit functions F x y z d before we only considered a single isosurface but many implicits e g blobs define density fields could model cloud as a mixture of blobs has all the usual advantages of implicits hopefully compact algebraic form continuous functions are always handy In many cases use other representations discrete grids are quite common often due to source of data acquired on a grid computational simulation on grids Volume Grids in 2 D The first natural discrete representation is the uniform grid a rectangular array of square cells each cell contains a single scalar value in other words a monochrome raster image This comparison is quite powerful image processing operations can be used to achieve many useful results have to worry about jaggies 2 Volumes in 2 D Quadtrees Uniform grids have one big weakness they re uniform this is fine if the data is uniform but what if the data is not uniform we can waste a lot of empty cells Adaptive grids solve this problem quadtrees start with a single cell and recursively partition nodes into 4 subdivide Grids in 3 D Uniform grids generalize directly to 3 D a 3 D array of cubical cells each cell is generally referred to as a voxel volume element essentially a 3 D raster image Unfortunately the problem of uniformity is even worse in 2 D grid size grows as resolution squared 256x256 image with 8 bit precision 64 KB but in 3 D size grows as resolution cubed 256x256x256 voxel grid with 8 bit precision 16 MB and we usually want good resolution to make things look nice in other words we chew through lots of memory Luckily we don t necessarily have to use uniform grids 3 Octrees Generalizing Quadtrees to 3 D Quadtrees also have a 3 D analogue octrees start with a single cubical cell divide it into 8 subcells split along each of the x y z directions do this recursively until cells are small enough There are of course many other ways of splitting space BSP trees are one we ve seen already but there are several others We ll revisit these structures later as spatial data structures for accelerating ray tracing Rendering Volume Grids One natural rendering technique is polygonization pick some density value of interest extract an isosurface containing all points with given density polygonize this isosurface say with Marching Cubes But this has some serious drawbacks extracting isosurface almost always introduces error we largely forfeit all transparency information As we ll see later on we can actually render volumes directly usually referred to as volume rendering methods 4 Example Volume Rendering from http graphics stanford edu projects volume Example Volume Rendering from http graphics stanford edu projects volume 5 Volumetric Models of Solids We began with presumably continuous density fields but what if each cell is either inside or outside in other words a binary scalar field What we have is a discrete model of a solid the solid is the set of all inside voxels In some ways this is the grand unified modeling primitive everything winds up as a discrete image in the end we could model everything with discrete volume grids just as 2 D raster displays replaced vector displays there are even a couple volume rendering PC cards available but its future dominance is far from certain at this point Constructive Solid Geometry CSG Many objects are fabricated by machining start with a block of wood drill some holes in it round off some corners glue some legs on it This can be a useful way of specifying object shapes it creates some physical intuition about object creation although it s less useful for non machined objects e g a fern 6 A More Interesting Example of CSG by Brian Wyvill http www cpsc ucalgary ca blob Boolean Point Set Operations We define pair wise Boolean operations on point sets given two sets of points combine them to form a new set just use the standard mathematical set operations Operation 1 A union B the set of all points in either A or B fuse two objects together Operation 2 A intersect B the set of all points in A and B trim off parts of A that fall outside of B Operation 3 A minus B the set of all points in A that are not in B cut out part of A using B 7 Building Objects with CSG As usual we build hierarchies binary Boolean operators recursively grouped produces binary tree Unions merge components Subtraction works like drilling and cutting Boolean Operations on Implicits There are many representations we can perform CSG on And implicit surfaces are one of them can formulate Boolean operators algebraically For an implicit function F we can negate the point set by negating F which together with intersection gives us subtraction the intersection of two implicits is MAX F G the union of two implicits is MIN F G 8 CSG on Grids It can be particularly easy to perform CSG on voxel grids no longer dealing with continuous implicit functions don t need to explicitly represent boundary of surface just need to figure out inside and outside If two voxel grids are of identical dimensions things are easy perform union and friends on each pair of corresponding cells never need to consider any neighboring cells ideal for parallelization If voxel grids are of different dimensions things are trickier could resample grids and introduce error our could formulate more sophisticated algorithm Higher Order Volume Models The volume models discussed so far were scalar fields every point cell contained a single scalar value But we can generalize this to encompass vector fields every cell has an associated vector or even an arbitrary collection of vectors Several natural application areas particularly in visualization most having to do with motion for example velocity vectors