|
 ABSTRACT
We present a simple algorithm to generate a topology-preserving, error-bounded approximation of the outer boundary of the volume swept by a polyhedron along a parametric trajectory. Our approach uses a volumetric method that generates an adaptive volumetric grid, computes signed distance on the grid points, and extracts an isosurface from the distance field. In order to guarantee geometric and topological bounds, we present a novel sampling and front propagation algorithm for adaptive grid generation. We highlight the performance of our algorithm on many complex benchmarks that arise in geometric and solid modeling, motion planning and CNC milling applications. To the best of our knowledge, this is the first practical algorithm that can generate swept volume approximations with geometric and topological guarantees on complex polyhedral models swept along any parametric trajectory.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Abdel-Malek, K., and Othman, S. 1999. Multiple sweeping using the Denavit-Hartenber representation method. Computer-Aided Design 31, 567--583.
|
| |
2
|
Abdel-Malek, K., and Yeh, H. J. 1997. On the determination of starting points for parametric surface intersections. Computer-Aided Design 29, 1, 21--35.
|
| |
3
|
Abdel-Malek, K., Blackmore, D., and Joy, K. 2004. Swept volumes: Foundations, perspectives, and applications. International Journal of Shape Modeling 23, 5, 1--25.
|
| |
4
|
Abrams, S., and Allen, P. 1995. Swept volumes and their use in viewpoint computation in robot work-cells. In Proc. IEEE International Symposium on Assembly and Task Planning, 188--193.
|
| |
5
|
Ahn, J.-W., Kim, M.-S., and Lim, S.-B. 1993. Approximate general sweep boundary of a 2D curved objects. Graphical Models and Image Processing 55, 2.
|
| |
6
|
Aktouf, Z., Bertrand, G., and Perroton, L. 1996. A three-dimensional holes closing algorithm. In Proceedings of the 6th International Workshop on Discrete Geometry for Computer Imagery, Springer-Verlag, London, UK, 36--47.
|
| |
7
|
Bischoff, S., and Kobbelt, L. P. 2002. Isosurface reconstruction with topology control. In Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, Washington, DC, USA, 246.
|
| |
8
|
Blackmore, D., and Leu, M. C. 1990. A differential equation approach to swept volumes. In Proc. of Rensselaer's 2nd International Conference on Computer Integrated Manufacturing, 143--149.
|
| |
9
|
Blackmore, D., Leu, M., and Wang, L. 1997. Sweep-envelope differential equation algorithm and its application to NC machining verification. Computer-Aided Design 29, 629--637.
|
| |
10
|
Boissonnat, J.-D., Cohen-Steiner, D., and Vegter, G. 2004. Isotopic implicit surface meshing. In ACM Symposium on Theory of Computing.
|
| |
11
|
Bremer, P.-T., Edelsbrunner, H., Hamann, B., and Pascucci, V. 2004. A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics 10, 4.
|
| |
12
|
Chernyaev, E. 1995. Marching cubes 33: Construction of topologically correct isosurfaces. Institute for High Energy Physics, Russia, Report CN/95-17.
|
| |
13
|
Elber, G., and Kim, M.-S. 1999. Offsets, sweeps, and Minkowski sums. Computer-Aided Design 31, 3, 163.
|
| |
14
|
Erdim, H., and Ilieş, H. T. 2008. Classifying points for sweeping solids. Computer-Aided Design 40, 9, 987--998.
|
| |
15
|
Himmelstein, J. C., Ferre, E., and Laumond, J.-P. 2007. Swept volume approximation of polygon soups. In IEEE ICRA.
|
| |
16
|
Ju, T., Losasso, F., Schaefer, S., and Warren, J. 2002. Dual contouring of hermite data. In SIGGRAPH 2002, Computer Graphics Proceedings.
|
| |
17
|
Jüttler, B., and Wagner, M. 1996. Spatial rational B-spline motions. ASME Journal of Mechanical Design 118, 193--201.
|
| |
18
|
Kim, Y., Varadhan, G., Lin, M., and Manocha, D. 2003. Fast swept volume approximation of complex polyhedral models. Proc. of ACM Symposium on Solid Modeling and Applications, 11--22.
|
| |
19
|
Kobbelt, L., Botsch, M., Schwanecke, U., and Seidel, H. P. 2001. Featuresensitive surface extraction from volume data. In ACM SIGGRAPH, 57--66.
|
| |
20
|
Lee, J., Hong, S., and Kim, M. 2002. Polygonal boundary approximation for a 2D general sweep based on envelope and Boolean operations. Visual Computer 16.
|
| |
21
|
Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In Computer Graphics (SIGGRAPH '87 Proceedings), vol. 21, 163--169.
|
| |
22
|
Mangin, J.-F., Frouin, V., Bloch, I., Régis, J., and López-Krahe, J. 1995. From 3D magnetic resonance images to structural representations of the cortex topography using topology preserving deformations. Journal of Mathematical Imaging and Vision 5, 4, 297--318.
|
| |
23
|
Martin, R., and Stephenson, P. 1990. Sweeping of three-dimensional objects. Computer-Aided Design 22, 4.
|
| |
24
|
Nielson, G. 2004. Dual marching cubes. In IEEE Visualization Conference.
|
| |
25
|
Paiva, A., Lopes, H., Lewiner, T., and de Figueiredo, L. 2006. Robust adaptive meshes for implicit surfaces. 19th Brazilian Symposium on Computer Graphics and Image Processing, 205--212.
|
| |
26
|
Peternell, M., Pottmann, H., Steiner, T., and Zhao, H. 2005. Swept volumes. Computer Aided Design and Applications 2, 5, 599--608.
|
| |
27
|
Raab, S. 1999. Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes. In Proc. 15th ACM Symposium on Computational Geometry, 163--172.
|
| |
28
|
Rossignac, J., Kim, J. J., Song, S. C., Suh, K. C., and Joung, C. B. 2007. Boundary of the volume swept by a free-form solid in screw motion. Computer-Aided Design 39, 9, 745--755.
|
| |
29
|
Schaefer, S., and Warren, J. 2004. Dual marching cubes: Primal contouring of dual grids. In Pacific Graphics.
|
| |
30
|
Schroeder, W., Lorensen, W., and Linthicum, S. 1994. Implicit modeling of swept surfaces and volumes. In IEEE Visualization Conference.
|
| |
31
|
Sethian, J. 1996. A fast marching level set method for monotonically advancing fronts. In Proc. Nat. Acad. Sci., vol. 93, 1591--1595.
|
| |
32
|
Sharf, A., Lewiner, T., Shklarski, G., Toledo, S., and Cohen-Or, D. 2007. Interactive topology-aware surface reconstruction. ACM Trans. Graph. 26, 3, 43.
|
| |
33
|
Varadhan, G., and Manocha, D. 2006. Accurate Minkowski sum approximation of polyhedral models. Graphical Models 68, 4, 343--355.
|
| |
34
|
Varadhan, G., Krishnan, S., Sriram, T. V. N., and Manocha, D. 2004. Topology preserving surface extraction using adaptive subdivision. In Eurographics Symposium on Geometry Processing.
|
| |
35
|
Wang, G., Sun, J., and Hua, X. 2000. The sweep-envelope differrential equation algorithm for general deformed swept volumes. Computer Aided Geometric Design 17, 5, 399--418.
|
| |
36
|
Weld, J., and Leu, M. 1990. Geometric representation of swept volume with application to polyhedral objects. Int. J. of Robotics Research 9, 5.
|
| |
37
|
Wood, Z., Desbrun, M., Schroeder, P., and Breen, D. 2000. Semi-regular mesh extraction from volumes. In IEEE Visualization 2000 Proceedings.
|
| |
38
|
Xu, Z., Chen, Z., Ye, X., and Zhang, S. 2007. Approximate the swept volume of revolutions along curved trajectories. In ACM Symposium on Solid and Physical Modeling.
|
| |
39
|
Zhang, N., Hong, W., and Kaufman, A. 2004. Dual contouring with topology-preserving simplification using enhanced cell representation. In IEEE Visualization.
|
| |
40
|
Zhang, X. Y., Kim, Y. J., and Manocha, D. 2009. Analysis and implementation of reliable sweeps. Tech. rep., Ewha Womans University, Korea.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf