Voxel-based modeling techniques are known for their robustness and flexibility. However, they have three major shortcomings: (1) Memory intensive, since a large number of voxels are needed to represent high-resolution models (2) Computationally expensive, since a large number of voxels need to be visited (3) Computationally expensive isosurface extraction is needed to visualize the results. We describe techniques which alleviate these by taking advantage of self-similarity in the data making voxel-techniques practical and attractive. We describe algorithms for MEMS process emulation, isosurface extraction and visualization which utilize these techniques.

Issue Section:
Technical Papers
Keywords:
micromechanical devices, solid modelling, data visualisation, computational geometry, feature extraction, spatial data structures, octrees, fractals, Voxel-based data structures and algorithms, MEMS process emulation, Isosurface Extraction, Visualization
Topics:
Algorithms, Geometry, Microelectromechanical systems, Octrees, Solid modeling, Visualization
1.
Kolb, A., and John, L., 2001, “Volumetric Model Repair for Virtual Reality Applications,” Proceedings of Eurographics, Short paper presentation, Chalmers. A. and Rhyne. M., T, eds., Manchester, UK.
2.
Wood, Z., Hoppe, H., Desburn, M., and Schroder P., 2002, “Isosurface Topology Simplification,” Microsoft Technical Report MSR-TR-2002-28, Seattle, WA.
3.
Frisken, F., and Perry, R., 2001, “Kizamu: A System for Sculpting Digital Characters,” Proceedings of the 28th annual conference on Computer graphics and interactive techniques, Pocock L., ed., ACM Press, pp. 47–56.
4.
Kaufman, A., and Shimony, E., 1986, “3D Scan-Conversion Algorithms for Voxel-Based Graphics,” Proceedings of 1986 Workshop on Interactive 3D Graphics, Chapel Hill, NC, pp. 45–75.
5.
Sra´mek
,
M.
, and
Kaufman
,
A.
,
2000
, “
Alias-Free Voxelization of Geometric Objects
,”
IEEE Trans. Vis. Comput. Graph.
,
3
(
6
), pp.
236
–
252
.
6.
Udeshi, T., 2003, “Tetrahedral Mesh Generation from Segmented Voxel Data,” Proceedings of the 12th International Meshing Roundtable, Santa Fe, NM, pp. 425–436.
7.
Kaufman
,
A.
,
Cohen
,
D.
, and
Yagel
,
R.
,
1993
, “
Volume Graphics
,”
IEEE Trans. Comput.
,
26
(
7
), pp.
51
–
64
.
8.
Samet, H., 1990, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading.
9.
Noh, W., and Woodward, P., 1976, “Simple Line Interface Calculation,” Lecture Notes in Physics, 59, Springer-Verlag, pp. 330–340.
10.
Hanan
,
S.
,
1985
, “
Data Structures for Quadtree Approximation and Compression
,”
Commun. ACM
,
28
(
9
), pp.
973
–
993
.
11.
Gosper
,
R.
,
1984
, “
Exploiting Regularities in Large Cellular Spaces
,”
Physica D
,
10
, pp.
75
–
80
.
12.
Webber
,
R. E.
, and
Dillencourt
,
M. B.
,
1989
, “
Compressing Quadtrees via Common Subtree Merging
,”
Pattern Recogn. Lett.
,
9
(
3
), pp.
193
–
2000
.
13.
Parker, E., and Udeshi, T., 2003, “Exploiting Self-Similarity in Voxel-Based Solid Modeling,” 8th ACM Symposium on Solid Modeling and Applications, Gershin, E. and Shapiro, V., eds., Seattle, WA, pp. 157–166.
14.
Serra, J., 1984, Image Analysis and Mathematical Morphology, Academic Press, New York, NY.
15.
Yarberry, V., 2002, “Meeting the MEMS ‘Design-to-Analysis’ Challenge: The SUMMIT® V Design Tool Environment,” Proceedings of ASME International Mechanical Engineering Congress & Exposition, Micro-Electro-Mechanical Systems (MEMS), New Orleans, LA, pp. 547–553.
16.
Tan, Z., Furmanczyk, M., Turowski, M., and Przekwas, A. J., 2001, “CFD-Micromesh: A Fast Geometrical Modeling and Mesh Generation Tool for 3D Microsystem Simulations,” Technical Proceedings of the 2000 International Conference on Modeling and Simulation of Microsystems, San Diego, CA, pp. 712–715.
17.
Lorensen, W., and Cline, H., 1987, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics,” Proceedings of the 14th annual conference on Computer graphics and interactive techniques, Stone, M. C. ed., ACM Press, pp. 163–169.
18.
Schroeder, W., Zarge, J., and Lorensen, W., 1992, “Decimation of Triangle Meshes,” Proceedings of the 19th annual conference on Computer graphics and interactive techniques, Thomas, J., ed., ACM Press, pp. 65–70.
19.
Tao, J., Losasso, F., Schaefer, S., and Warren J., 2002, “Dual Contouring of Hermite Data,” Proceedings of the 29th annual conference on Computer graphics and interactive techniques, Appolloni, T., ed., ACM Press, pp. 339–346.
20.
Rusinkiewicz, S. and Levoy, M., 2000, “QSplat: A Multiresolution Point Rendering System for Large Meshes,” Proceedings of the 2001 symposium on Interactive 3D graphics Computer Graphics, Hughes J.F., and Sequin, C. H., eds., ACM Press, pp. 353–358.
21.
Aho, A., Hopcroft, J., and Ullman, J., 1983, Data Structures and Algorithms, Addison-Wesley, Reading.
Copyright © 2004
 by ASME
You do not currently have access to this content.