“MeshGit: diffing and merging meshes for polygonal modeling” by Denning and Pellacini
Conference:
Type:
Title:
- MeshGit: diffing and merging meshes for polygonal modeling
Session/Category Title: Geometry & Topology
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This paper presents MeshGit, a practical algorithm for diffing and merging polygonal meshes typically used in subdivision modeling workflows. Inspired by version control for text editing, we introduce the mesh edit distance as a measure of the dissimilarity between meshes. This distance is defined as the minimum cost of matching the vertices and faces of one mesh to those of another. We propose an iterative greedy algorithm to approximate the mesh edit distance, which scales well with model complexity, providing a practical solution to our problem. We translate the mesh correspondence into a set of mesh editing operations that transforms the first mesh into the second. The editing operations can be displayed directly to provide a meaningful visual difference between meshes. For merging, we compute the difference between two versions and their common ancestor, as sets of editing operations. We robustly detect conflicting operations, automatically apply non-conflicting edits, and allow the user to choose how to merge the conflicting edits. We evaluate MeshGit by diffing and merging a variety of meshes and find it to work well for all.
References:
1. Blender Foundation, 2011. Sintel. www.sintel.org.Google Scholar
2. Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Transactions on Graphics 26, 3 (July), 21:1–21:9. Google ScholarDigital Library
3. Bunke, H. 1998. On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters 18, 689–694. Google ScholarDigital Library
4. Chang, W., and Zwicker, M. 2008. Automatic registration for articulated shapes. Computer Graphics Forum 27, 5, 1459–1468. Google ScholarDigital Library
5. Chang, W., Li, H., Mitra, N., Pauly, M., Rusinkiewicz, S., and Wand, M. 2011. Computing correspondences in geometric data sets. In Eurographics Tutorial Notes.Google Scholar
6. Chaudhuri, S., and Koltun, V. 2010. Data-driven suggestions for creativity support in 3d modeling. ACM Transactions on Graphics 26, 6, 183:1–183:10. Google ScholarDigital Library
7. Chaudhuri, S., Kalogerakis, E., Guibas, L., and Koltun, V. 2011. Probabilistic reasoning for assembly-based 3D modeling. ACM Transactions on Graphics 30, 4, 35:1–35:10. Google ScholarDigital Library
8. Chen, H.-T., Wei, L.-Y., and Chang, C.-F. 2011. Nonlinear revision control for images. ACM Transaction on Graphics 30, 4, 105:1–105:10. Google ScholarDigital Library
9. Cour, T., Srinivasan, P., and Shi, J. 2006. Balanced graph matching. In NIPS, 313–320.Google Scholar
10. Denning, J. D., Kerr, W. B., and Pellacini, F. 2011. Mesh-flow: interactive visualization of mesh construction sequences. ACM Transaction on Graphics 30, 4, 66:1–66:8. Google ScholarDigital Library
11. Doboš, J., and Steed, A. 2012. 3D Diff: an interactive approach to mesh differencing and conflict resolution. In SIGGRAPH Asia 2012 Technical Briefs, ACM, New York, NY, USA, SA ’12, 20:1–20:4. Google ScholarDigital Library
12. Dubrovina, A., and Kimmel, R. 2010. Matching shapes by eigendecomposition of the laplace-beltrami operator. In Proc. 3DPVT.Google Scholar
13. Eppstein, D., Goodrich, M. T., Kim, E., and Tamstorf, R. 2009. Approximate topological matching of quad meshes. The Visual Computer, 771–783. Google ScholarDigital Library
14. Gao, X., Xiao, B., Tao, D., and Li, X. 2010. A survey of graph edit distance. Pattern Analysis and Applications 13, 113–129. Google ScholarDigital Library
15. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. SIGGRAPH, 79:1–79:12. Google ScholarDigital Library
16. Leordeanu, M., and Hebert, M. 2005. A spectral technique for correspondence problems using pairwise constraints. In International Conference on Computer Vision, 1482–1489. Google ScholarDigital Library
17. Levenshtein, V. I. 1965. Binary codes capable of correcting spurious insertions and deletions of ones. Probl. Inf. Transmission 1, 8–17.Google Scholar
18. Neuhaus, M., and Bunke, H. 2007. Bridging the gap between graph edit distance and kernel machines. World Scientific. Google ScholarDigital Library
19. Riesen, K., and Bunke, H. 2009. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing 27, 950–959. Google ScholarDigital Library
20. Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the icp algorithm. International Conference on 3D Digital Imaging and Modeling.Google Scholar
21. Sharf, A., Blumenkrants, M., Shamir, A., and Cohen-Or, D. 2006. Snappaste: an interactive technique for easy mesh composition. The Visual Computer 22, 835–844. Google ScholarDigital Library
22. Sharma, A., von Lavante, E., and Horaud, R. P. 2010. Learning shape segmentation using constrained spectral clustering and probabilistic label transfer. In European Conference on Computer Vision, 743–756. Google ScholarDigital Library
23. Sharma, A., Horaud, R. P., Cech, J., and Boyer, E. 2011. Topologically-robust 3d shape matching based on diffusion geometry and seed growing. In Computer Vision and Pattern Recognition, 2481–2488. Google ScholarDigital Library
24. VisTrails, 2010. VisTrails Provenance Explorer for Maya. www.vistrails.com/maya.html.Google Scholar
25. Zeng, Y., Wang, C., Wang, Y., Gu, X., Samaras, D., and Paragios, N. 2010. Dense non-rigid surface registration using high-order graph matching. In Computer Vision and Pattern Recognition, 382–389.Google Scholar
