Discrete Space Voxelization and Distance Fields Jian Huang CS 594 Spring 2002 Papers Huang et al Accurate Voxelization of Polygonal Meshes IEEE Symposium on Volume Visualization 1998 Huang et al CDFR IEEE Conference on Visualization 2001 Discrete Space A 3D discrete space Z3 is a set of integer grid points in a 3D Euclidean space denoted by S A 3D grid point is a zero dimensional object defined by its Cartesian coordinate x y z The Voronoi neighborhood of grid point p is the set of all points in the Euclidean space that are closer to p than to any other grid point The Voronoi neighborhood of a 3D grid point is a unit cube around it known also as a voxel Discrete Space The aggregate of all voxels is a tessellation of 3D Euclidean space A voxel s value is mapped into the set 0 1 voxels assigned the value 1 are called black or non empty voxels those assigned the value 0 are called white or empty voxels N Adjacency In 3D discrete space Two voxels are 26 adjacent if they share a vertex or an edge or a face 26 such adjacent voxels for any voxel Two voxels are 18 adjacent if they share an edge or a face 18 such adjacent voxels for any voxel Two voxels are 6 adjacent if they share a face 6 such adjacent voxels for any voxel In 2D discrete space similarly 4 adjacency and 8adjacency N Neighborhood The set of 2D pixels that are N adjacent to the dark pixel where N 4 8 The set of 3D voxels that are N adjacent to the voxel at the center where N 6 18 26 N Path An N path is a sequence of black voxels such that consecutive pairs are N adjacent Two black voxels are said to be N connected in if there exists a connecting N path consisting only of black voxels A closed N curve is an N path P that either contains a single voxel or each voxel in P has exactly two Nadjacent voxels also in P An open N curve is an N curve with two exceptions called endpoints each of which has only one N adjacent voxel in P Separability In continuous space it is impossible to pass from the region enclosed by a curve to the region outside the curve without crossing the curve itself In discrete space however the opposite is possible To avoid this discrepancy define opposite types of connectivity for white and black sets Opposite types in 2D space are 4 and 8 In 3D space 6 is opposite to 26 and 18 Separability Let A B and C be three disjoint sets of voxels A is said to N separate B and C if any N path between a voxel in B and a voxel in C meets A Separability is a topological property 4 separating and 8 separating curves Minimality A voxel belonging to an N separating surface is called an N simple voxel if deleting it will not affect the surface separability A surface is N minimal if it does not contain any N simple voxels Examples of a 4 minimal curve left 8 simple point center and a 4 simple point right Voxelization To convert continuous surface representations e g polygon mesh parametric surfaces into voxel representations Need to preserve separability and minimality Pixelizing a Line For 4 separable or 8 separable assuming the normal vector is normalized need to include all pixels with distance to the line between Voxelizing a Plane For 6 separable or 26 separable assuming the normal vector is normalized all voxels with distance to the line between abs Ax By Cz D t Voxelizing a Polygon Mesh Edges and vertices needs special handling for separability and minimality Let t denote the desired connectivity distance either t6 or t26 Rc L 2 for 6 separability for 26 separability Distance Field Discrete distance field Each element in a distance field specifies its minimum distance to a surface geometry Positive and negative distances are used to distinguish outside and inside of the shape negative values on the outside positive values on the inside Getting a Distance Field 1 First voxelize the 3D mesh to a binary surface volume Kaufman Cohen Huang Second run a distance transform on the surface volume to obtain a solid distance volume Euclidean Distance Chamfer Distance Face edge vertex sharing Manhattan Distance Face sharing Chamfer distance Getting a Distance Field 2 Brute force For every voxel in the volume compute the minimal distance to the geometric surface Euclidean distance Doable with triangle meshes but hard problem in general Time consuming Hierarchical Distance Field Distance fields can be stored hierarchically in Quadtree or Octree structures Aka adaptively sampled distance field ADF Use a smaller voxel size in areas of higher details Disadvantages of Conventional Distance Fields Need to choose an initial volume resolution the high limit of error tolerance When the user picks a tighter tolerance have to do everything from scratch again The conventional distance volume is aliased Real data sets are not smooth thus not bandlimited Volume Anti aliasing Non binary pre filtered volume Sramek Kaufmann Need higher order smoothing filters for reconstruction No idea how much detail is gone in geometric sense Not exactly sure about how geometric details are defined Corners Holes Impasse Sampling rate is limited Distance fields of complex geometric models are not band limited Impasse would desire to keep all the geometric details in a volumetric distance field Geometric details at 0 1 of an object s dimension Observation In spatial domain if all that we want to capture are the distances to a set of finite polygons Place an anchor point somewhere and record the distances from the anchor to each of the finite polygons Need New Distance Field Representation Generalize volume representation from a discretization of a continuous domain entity to a spatial data structure Try to build a spatial data structure Every voxel to have all the information necessary to capture the exact local distance field within the span of that voxel To answer a query of what s the thickness of an interior point pnt we only have to deal with the corresponding local voxel CDFR The spatial data structure is named CDFR A Complete Distance Field Representation In the CDFR deal with signed Euclidean distances from 3D points to finite triangles only Each spatial point has a base triangle which is used to determine the sign of the distance value Base Triangle Need to decide which triangle is the base triangle of a point pnt If pnt is closest to a triangle which pnt orthogonally projects into then this triangle is the base triangle Otherwise if pnt is closest to 2 triangles sharing an edge then compute pntproj on this edge connect pnt and pntproj to form a vector
View Full Document
Unlocking...