Discrete Space, Voxelization and Distance FieldsPapersDiscrete SpaceSlide 4N-AdjacencyN-NeighborhoodN-PathSeparabilitySlide 9MinimalityVoxelizationPixelizing a LineVoxelizing a PlaneVoxelizing a Polygon MeshDistance FieldGetting a Distance Field (1)Getting a Distance Field (2)Hierarchical Distance FieldDisadvantages of Conventional Distance FieldsVolume Anti-aliasingImpasseObservationNeed New Distance Field RepresentationCDFRBase TriangleSlide 26How much information do we need on each voxel?Constructing a CDFRDistance TransformAnswering a QueryExtracting a Distance ContourOn Convex Test ModelsOn Concave Test ModelsOn Practical PartsSlide 35Storage SizeCDFR Storage Size and Construction TimeTesting PlatformContour Extraction TimeThe Engine Cylinder HeadDiscrete Space, Voxelization and Distance FieldsJian Huang, CS 594, Spring 2002Papers•Huang et al, ‘Accurate Voxelization of Polygonal Meshes’, IEEE Symposium on Volume Visualization, 1998•Huang et al, ‘CDFR’, IEEE Conference on Visualization, 2001Discrete 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'' voxelsN-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 8-adjacency.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, 26N-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 N-adjacent 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 PSeparability•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 18Separability•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 property4-separating and 8-separating curvesMinimality•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 voxelsExamples 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 minimalityPixelizing 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) <= tVoxelizing 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.•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 sharingGetting a Distance Field (1)Chamfer distanceGetting 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 consumingHierarchical 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 detailsDisadvantages 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 band-limitedVolume 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–HolesImpasse•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 dimensionObservation•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
View Full Document
Unlocking...