The Marching Cubes Polygonization Algorithm The Marching Cubes MC algorithm converts a volume into a polygonal model this model approximates a chosen iso surface by a mesh of polygons the polygonal model can then be rendered for example using a fast z buffer algorithm if another iso surface is desired then MC has to be run again Steps imagine all voxels above the iso value are set to 1 all others are set to 0 the goal is to find a polygonal surface that includes all 1 voxels and excludes all 0 voxels look at one volume cell a cube at a time hence the term Marching Cubes here are 2 of 256 possible configurations the reverse case only 1 voxel iso value the polygon that separates inside from outside 7 voxels iso value the same polygon results 21 Marching Cubes 2 One can identify 15 base cases Use symmetry and reverses to get the other 241 cases The exact position of the polygon vertex on a cube edge is found by linear interpolation iso v 1 1 u v 2 u v 1 iso u v1 v2 Now interpolate the vertex color by c 1 uc 2 1 u c 1 Interpolate the vertex normal by n 1 ug 2 1 u g 1 v2 v1 u 1 u the g1 and g2 are the gradient vectors at v1 and v2 obtained by central differencing 22 Ambiguous Cases 2D ambiguous case both versions are plausible 3D what happens when cases are arbitrarily chosen case 3 case 6 complementary hole connected Remedy add 6 alternative cases for 3 6 7 10 12 13 to prevent holes Example case 3c 23 Remove Ambiguities Using the Asymptotic Decider Method Explain in 2D surface created by bilinear interpolation function 1 s s B 00 B 01 1 t t B 10 B 11 gives rise to two hyperbolas B s t isovalue ambiguity both hyperbolas intersect domain 0 0 1 1 resolve ambiguity by comparing B S T with exterior interior similar cases in 3D B 00 B 01 S B 00 B 11 B 01 B 10 B 00 B 10 T B 00 B 11 B 01 B 10 24
View Full Document
Unlocking...