A Partition Approach to Interpolate Polygon Sets for Animation
Resumo
The use of animation can be a good alternative to static visualizations when communicating dynamic changes. Some approaches already represent spatiotemporal phenomena using a polygon set for each time instant. However, these representations are static and not general enough to be applied for the interpolation of arbitrary polygons. Furthermore, the problem of interpolating arbitrary polygons present a set of requirements that are not satisfied by the currently available tools. For example, the polygons are arbitrary and the interpolation should be smooth and fully automatic (not requiring user intervention). To solve this problem, we present an approach to interpolate arbitrary polygon sets that satisfy those requirements and that can be used to visualize temporal changes of different phenomena as an animation. In the proposed approach we apropriately subdivide and identify correspondences between origin and target polygon sets. Our approach is general enough so that different polygon subdivision techniques can be used. We also performed a series of experiments comparing a few different techniques and discuss the results.
Palavras-chave:
Visualization of spatiotemporal phenomena, Animation, Interpolation
Referências
M.-J. Kraak, F. Ormeling, Cartography: Visualization of Geospatial Data, Prentice-Hall, 2010.
C. Robertson, T. A. Nelson, B. Boots, M. A. Wulder, "STAMP: spatial-temporal analysis of moving polygons", Journal of Geographical Systems, vol. 9, no. 3, pp. 207-2Sep 2007.
K. C. Abhar, I. J. Walker, P. A. Hesp, P. A. Gares, "Spatialtemporal evolution of aeolian blowout dunes at Cape Cod", Geomorphology, vol. 2pp. 148-12015.
R. B. Santos, Crime Analysis With Crime Mapping, Los Angeles, California:SAGE Publications, 2013.
K. J. Bowers, S. D. Johnson, K. Pease, "Prospective Hot-Spotting: The Future of Crime Mapping?", The British Journal of Criminology, vol. pp. 641-62004.
A. Malik, R. Maciejewski, E. Hodgess, D. S. Ebert, "Describing Temporal Correlation Spatially in a Visual Analytics Environment", Proceedings of the Hawaii International Conference on System Sciences, pp. 1-8, 2011.
J. F. Queiroz Neto, E. M. d. Santos, C. A. Vidal, "MSKDE: Using Marching Squares to Quickly Make High Quality Crime Hotspot Maps", SIBGRAPI Conference on Graphics Patterns and Images (SIBGRAPI), pp. 305-32016.
B. Tversky, J. B. Morrison, M. Betrancourt, "Animation: can it facilitate?", International journal of human-computer studies, vol. no. 4, pp. 247-22002.
B. Lee, N. H. Riche, P. Isenberg, S. Carpendale, "More Than Telling a Story: Transforming Data into Visually Shared Stories", IEEE Computer Graphics and Applications, vol. no. 5, pp. 84-90, Sep. 2015.
T. H. Kim, T. J. Cova, "Tweening Grammars: Deformation Rules for Representing change between Discrete Geographic Entities", Computers Environment and Urban Systems, vol. pp. 317-32007.
R. C. Carbunescu, S. V. Wart, Polygon Vertex Set Matching Algorithm for Shapefile Tweening, University of California at Berkeley, 2008, [online] Available: http://vis.berkeley.edu/courses/cs294-10-fa08/wiki/images/d/d3/Finalpaper_rc_sv.pdf.
N. Veltman, Flubber: Tools for smoother shape animations, 20[online] Available: https://github.com/veltman/flubber.
T. W. Sederberg, E. Greenwood, "A Physically Based Approach to 2-D Shape Blending", SIGGRAPH '92 Proceedings of the 19th annual conference on Computer graphics and interactive techniques, vol. pp. 25-1992.
T. W. Sederberg, P. Gao, G. Wang, H. Mu, "2-D Shape Blending: An Intrinsic Solution to the Vertex Path Problem", SIGGRAPH '93 Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pp. 15-1993.
Y.-H. Shiao, K.-S. Chuang, T.-J. Chen, C.-Y. Chen, "Polygon interpolation for serial cross sections", Computers in Biology and Medicine, vol. pp. 1241-122007.
C. Mizutani, "Land use transition process analysis using polygon events and polygon status: A case study of Tsukuba Science City", 2009 17th International Conference on Geoinformatics, pp. 1-6, Aug 2009.
N. Salamat, E. Zahzah, "Fuzzy Spatio-temporal Relations Analysis", 2010 Seventh International Conference on Information Technology: New Generations, pp. 301-306, April 2010.
M. Alexa, "Recent Advances in Mesh Morphing", Computer Graphics forum, vol. pp. 173-197, 2002.
T. Cashman, K. Hormann, "A continuous editable representation for deforming mesh sequences with separate signals for time pose and shape", Computer Graphics Forum, vol. pp. 735-72012.
P. von Radziewsky, E. Eisemann, H.-P. Seidel, K. Hildebrandt, "Optimized subspaces for deformation-based modeling and shape interpolation", Computers & Graphics, vol. pp. 128-12016.
C. Brandt, C. von Tycowicz, K. Hildebrandt, "Geometric Flows of Curves in Shape Space for Processing Motion of Deformable Objects", Computer Graphics Forum, vol. no. 2, pp. 295-305, 2016.
C. L. Bajaj, E. J. Coyle, K.-N. Lin, "Arbitrary Topology Shape Reconstruction from Planar Cross Sections", Graphical Models and Image Processing, vol. no. 6, pp. 524-51996.
J.-D. Boissonnat, "Shape reconstruction from planar cross sections", Computer Vision Graphics and Image Processing, vol. no. 1, pp. 1-1988.
C. Giertsen, A. Halvorsen, P. R. Flood, "Graph-directed modelling from serial sections", The Visual Computer, vol. 6, no. 5, pp. 284-290, Sep 1990.
C. Mizutani, "Construction of an analytical framework for polygon-based land use transition analyses", Computers Environment and Urban Systems, vol. no. 3, pp. 270-22012.
M. Berg, M. v. Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997.
F. P. Preparata, M. I. Shamos, Computational Geometry: an Introduction, Springer-Verlag, 1985.
A. El-Hamalawi, "A 2d combined advancing front-delaunay mesh generation scheme", Finite Elements in Analysis and Design, pp. 967-989, 2004.
D. J. Mavriplis, "An advancing front Delaunay triangulation algorithm designed for robustness", Journal of Computational Physics, pp. 90-101, 1995.
J. R. Shewchuk, "Delaunay refinement algorithms for triangular mesh generation", Computational Geometry, vol. no. 1, pp. 21-2002.
A. C. Miranda, J. B. Cavalcante Neto, L. F. Martha, "An algorithm for two-dimensional mesh generation for arbitrary regions with cracks", SIBGRAPI 99: proceedings of the XII Brazilian symposium on computer graphics and image processing, pp. 29-1999.
A. Tabarraei, N. Sukumar, "Adaptive computations on conforming quadtree meshes", Finite Elements in Analysis and Design, vol. no. 7, pp. 686-702, 2005.
E. Ooi, H. Man, S. Natarajan, C. Song, "Adaptation of quadtree meshes in the scaled boundary finite element method for crack propagation modelling", Engineering Fracture Mechanics, vol. 1pp. 101-12015.
A. Tabarraei, N. Sukumar, "Extended finite element method on polygonal and quadtree meshes", Computer Methods in Applied Mechanics and Engineering, vol. 197, no. 5, pp. 425-42008.
F. Aurenhammer, "Voronoi Diagrams - a Survey of a Fundamental Geometric Data Structure", ACM Comput. Surv., vol. no. 3, pp. 345-405, Sep. 1991.
M. Sedlmair, M. Meyer, T. Munzner, "Design Study Methodology: Reflections from the Trenches and the Stacks", IEEE Trans. Visualization and Computer Graphics (Proc. InfoVis), vol. no. pp. 2431-242012.
C. Robertson, T. A. Nelson, B. Boots, M. A. Wulder, "STAMP: spatial-temporal analysis of moving polygons", Journal of Geographical Systems, vol. 9, no. 3, pp. 207-2Sep 2007.
K. C. Abhar, I. J. Walker, P. A. Hesp, P. A. Gares, "Spatialtemporal evolution of aeolian blowout dunes at Cape Cod", Geomorphology, vol. 2pp. 148-12015.
R. B. Santos, Crime Analysis With Crime Mapping, Los Angeles, California:SAGE Publications, 2013.
K. J. Bowers, S. D. Johnson, K. Pease, "Prospective Hot-Spotting: The Future of Crime Mapping?", The British Journal of Criminology, vol. pp. 641-62004.
A. Malik, R. Maciejewski, E. Hodgess, D. S. Ebert, "Describing Temporal Correlation Spatially in a Visual Analytics Environment", Proceedings of the Hawaii International Conference on System Sciences, pp. 1-8, 2011.
J. F. Queiroz Neto, E. M. d. Santos, C. A. Vidal, "MSKDE: Using Marching Squares to Quickly Make High Quality Crime Hotspot Maps", SIBGRAPI Conference on Graphics Patterns and Images (SIBGRAPI), pp. 305-32016.
B. Tversky, J. B. Morrison, M. Betrancourt, "Animation: can it facilitate?", International journal of human-computer studies, vol. no. 4, pp. 247-22002.
B. Lee, N. H. Riche, P. Isenberg, S. Carpendale, "More Than Telling a Story: Transforming Data into Visually Shared Stories", IEEE Computer Graphics and Applications, vol. no. 5, pp. 84-90, Sep. 2015.
T. H. Kim, T. J. Cova, "Tweening Grammars: Deformation Rules for Representing change between Discrete Geographic Entities", Computers Environment and Urban Systems, vol. pp. 317-32007.
R. C. Carbunescu, S. V. Wart, Polygon Vertex Set Matching Algorithm for Shapefile Tweening, University of California at Berkeley, 2008, [online] Available: http://vis.berkeley.edu/courses/cs294-10-fa08/wiki/images/d/d3/Finalpaper_rc_sv.pdf.
N. Veltman, Flubber: Tools for smoother shape animations, 20[online] Available: https://github.com/veltman/flubber.
T. W. Sederberg, E. Greenwood, "A Physically Based Approach to 2-D Shape Blending", SIGGRAPH '92 Proceedings of the 19th annual conference on Computer graphics and interactive techniques, vol. pp. 25-1992.
T. W. Sederberg, P. Gao, G. Wang, H. Mu, "2-D Shape Blending: An Intrinsic Solution to the Vertex Path Problem", SIGGRAPH '93 Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pp. 15-1993.
Y.-H. Shiao, K.-S. Chuang, T.-J. Chen, C.-Y. Chen, "Polygon interpolation for serial cross sections", Computers in Biology and Medicine, vol. pp. 1241-122007.
C. Mizutani, "Land use transition process analysis using polygon events and polygon status: A case study of Tsukuba Science City", 2009 17th International Conference on Geoinformatics, pp. 1-6, Aug 2009.
N. Salamat, E. Zahzah, "Fuzzy Spatio-temporal Relations Analysis", 2010 Seventh International Conference on Information Technology: New Generations, pp. 301-306, April 2010.
M. Alexa, "Recent Advances in Mesh Morphing", Computer Graphics forum, vol. pp. 173-197, 2002.
T. Cashman, K. Hormann, "A continuous editable representation for deforming mesh sequences with separate signals for time pose and shape", Computer Graphics Forum, vol. pp. 735-72012.
P. von Radziewsky, E. Eisemann, H.-P. Seidel, K. Hildebrandt, "Optimized subspaces for deformation-based modeling and shape interpolation", Computers & Graphics, vol. pp. 128-12016.
C. Brandt, C. von Tycowicz, K. Hildebrandt, "Geometric Flows of Curves in Shape Space for Processing Motion of Deformable Objects", Computer Graphics Forum, vol. no. 2, pp. 295-305, 2016.
C. L. Bajaj, E. J. Coyle, K.-N. Lin, "Arbitrary Topology Shape Reconstruction from Planar Cross Sections", Graphical Models and Image Processing, vol. no. 6, pp. 524-51996.
J.-D. Boissonnat, "Shape reconstruction from planar cross sections", Computer Vision Graphics and Image Processing, vol. no. 1, pp. 1-1988.
C. Giertsen, A. Halvorsen, P. R. Flood, "Graph-directed modelling from serial sections", The Visual Computer, vol. 6, no. 5, pp. 284-290, Sep 1990.
C. Mizutani, "Construction of an analytical framework for polygon-based land use transition analyses", Computers Environment and Urban Systems, vol. no. 3, pp. 270-22012.
M. Berg, M. v. Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997.
F. P. Preparata, M. I. Shamos, Computational Geometry: an Introduction, Springer-Verlag, 1985.
A. El-Hamalawi, "A 2d combined advancing front-delaunay mesh generation scheme", Finite Elements in Analysis and Design, pp. 967-989, 2004.
D. J. Mavriplis, "An advancing front Delaunay triangulation algorithm designed for robustness", Journal of Computational Physics, pp. 90-101, 1995.
J. R. Shewchuk, "Delaunay refinement algorithms for triangular mesh generation", Computational Geometry, vol. no. 1, pp. 21-2002.
A. C. Miranda, J. B. Cavalcante Neto, L. F. Martha, "An algorithm for two-dimensional mesh generation for arbitrary regions with cracks", SIBGRAPI 99: proceedings of the XII Brazilian symposium on computer graphics and image processing, pp. 29-1999.
A. Tabarraei, N. Sukumar, "Adaptive computations on conforming quadtree meshes", Finite Elements in Analysis and Design, vol. no. 7, pp. 686-702, 2005.
E. Ooi, H. Man, S. Natarajan, C. Song, "Adaptation of quadtree meshes in the scaled boundary finite element method for crack propagation modelling", Engineering Fracture Mechanics, vol. 1pp. 101-12015.
A. Tabarraei, N. Sukumar, "Extended finite element method on polygonal and quadtree meshes", Computer Methods in Applied Mechanics and Engineering, vol. 197, no. 5, pp. 425-42008.
F. Aurenhammer, "Voronoi Diagrams - a Survey of a Fundamental Geometric Data Structure", ACM Comput. Surv., vol. no. 3, pp. 345-405, Sep. 1991.
M. Sedlmair, M. Meyer, T. Munzner, "Design Study Methodology: Reflections from the Trenches and the Stacks", IEEE Trans. Visualization and Computer Graphics (Proc. InfoVis), vol. no. pp. 2431-242012.
Publicado
28/10/2019
Como Citar
RAMOS, Alexandre R. C. ; SANTOS, Emanuele M. ; CAVALCANTE-NETO, Joaquim.
A Partition Approach to Interpolate Polygon Sets for Animation. In: CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
DOI: https://doi.org/10.5753/sibgrapi.2019.9783.
