“SceneGit: a practical system for diffing and merging 3D environments” by Carra and Pellacini
Conference:
Type(s):
Title:
- SceneGit: a practical system for diffing and merging 3D environments
Session/Category Title: Geometry Brekkie
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Version control systems are the foundation of collaborative workflows for text documents. For 3D environments though, version control is still an open problem due to the heterogeneous data of 3D scenes and their size. In this paper, we present a practical version control system for 3D scenes comprised of shapes, materials, textures, and animations, combined together in scene graphs. We version objects at their finest granularity, to make repositories smaller and to allow artists to work concurrently on the same object. Since, for some scene data, computing an optimal set of changes between versions is not computationally feasible, version control systems use heuristics. Compared to prior work, we propose heuristics that are efficient, robust, and independent of the application. We test our system on a variety of large scenes edited with different workflows, and show that our approach can handle all cases well while remaining efficient as scene size increases. Compared to prior work, we are significantly faster and more robust. A user study confirms that our system aids collaboration.
References:
1. Jyrki Alakuijala, Andrea Farruggia, Paolo Ferragina, Eugene Kliuchnikov, Robert Obryk, Zoltan Szabadka, and Lode Vandevenne. 2018. Brotli: A General-Purpose Data Compressor. ACM Trans. Inf. Syst. 37, 1 (2018).Google ScholarDigital Library
2. Benedikt Bitterli. 2016. Rendering resources. (2016). https://benedikt-bitterli.me/resources/Google Scholar
3. H. Bunke. 1997. On a Relation Between Graph Edit Distance and Maximum Common Subgraph. Pattern Recogn. Lett. 18, 9 (1997).Google ScholarDigital Library
4. Claudio Calabrese, Gabriele Salvati, Marco Tarini, and Fabio Pellacini. 2016. cSculpt: a system for collaborative sculpting. ACM Trans. Graph. 35, 4 (2016).Google ScholarDigital Library
5. Scott Chacon. 2009. Pro Git. Apress.Google Scholar
6. Will Chang, Hao Li, Niloy Mitra, Mark Pauly, Szymon Rusinkiewicz, and Michael Wand. 2011. Computing Correspondences in Geometric Data Sets. Eurographics 2011 Tutorial (2011).Google Scholar
7. Will Chang and Matthias Zwicker. 2008. Automatic Registration for Articulated Shapes. Computer Graphics Forum 27, 5 (2008).Google Scholar
8. Hsiang-Ting Chen, Tovi Grossman, Li-Yi Wei, Ryan M. Schmidt, Björn Hartmann, George Fitzmaurice, and Maneesh Agrawala. 2014. History Assisted View Authoring for 3D Models. In Proc. SIGCHI.Google ScholarDigital Library
9. Hsiang-Ting Chen, Li-Yi Wei, and Chun-Fa Chang. 2011. Nonlinear revision control for images. ACM Trans. Graph. 30 (2011).Google Scholar
10. Fernando Chirigati, Juliana Freire, David Koop, and Cláudio Silva. 2013. VisTrails provenance traces for benchmarking. In ACM International Conference Proceeding Series.Google ScholarDigital Library
11. Clara.io. 2014. Browser and cloud based modelling. https://clara.io/. (2014).Google Scholar
12. CodiceSoftware. 2005. Plastic SCM. https://plasticscm.com/. (2005).Google Scholar
13. Timothee Cour, Praveen Srinivasan, and Jianbo Shi. 2007. Balanced Graph Matching. In Advances in Neural Information Processing Systems 19, B. Schölkopf, J. C. Platt, and T. Hoffman (Eds.).Google Scholar
14. Jonathan D. Denning, William B. Kerr, and Fabio Pellacini. 2011. MeshFlow: Interactive Visualization of Mesh Construction Sequences. ACM Trans. Graph. 30, 4 (2011).Google ScholarDigital Library
15. Jonathan D. Denning and Fabio Pellacini. 2013. MeshGit: Diffing and Merging Meshes for Polygonal Modeling. ACM Trans. Graph. 32, 4 (2013).Google ScholarDigital Library
16. Jonathan D. Denning, Valentina Tibaldo, and Fabio Pellacini. 2015. 3DFlow: Continuous Summarization of Mesh Editing Workflows. ACM Trans. Graph. 34, 4 (2015).Google ScholarDigital Library
17. Jozef Doboš, Carmen Fan, Sebastian Friston, and Charence Wong. 2018. Screen Space 3D Diff: A Fast and Reliable Method for Real-time 3D Differencing on the Web. In Proceedings of the 23rd International ACM Conference on 3D Web Technology (Web3D ’18).Google ScholarDigital Library
18. Jozef Doboš, Niloy J. Mitra, and Anthony Steed. 2014. 3D Timeline: Reverse Engineering of a Part-based Provenance from Consecutive 3D Models. Computer Graphics Forum (2014).Google Scholar
19. Jozef Doboš, Kristian Sons, Dmitri Rubinstein, Philipp Slusallek, and Anthony Steed. 2013. XML3DRepo: a REST API for version controlled 3D assets on the web. In Web3D.Google Scholar
20. Jozef Doboš and Anthony Steed. 2012a. 3D Diff: an interactive approach to mesh differencing and conflict resolution. In SIGGRAPH Asia Technical Briefs.Google Scholar
21. Jozef Doboš and Anthony Steed. 2012b. 3D revision control framework. In Web3D.Google Scholar
22. Benjamín Eidelman. 2006. jsondiffpatch: Diff & patch JavaScript objects. (2006). https://github.com/benjamine/jsondiffpatchGoogle Scholar
23. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf. 2008. Approximate topological matching of quadrilateral meshes. (2008).Google Scholar
24. Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. 2010. A Survey of Graph Edit Distance. Pattern Analysis and Applications 13, 1 (2010).Google Scholar
25. Shiry Ginosar, De Pombo, Luis Fernando, Maneesh Agrawala, and Bjorn Hartmann. 2013. Authoring multi-stage code examples with editable code histories. In Proc. UIST.Google ScholarDigital Library
26. Google. 2016. Google Documents. http://docs.google.com. (2016).Google Scholar
27. Google. 2018. Abseil Swiss Tables. (2018). https://abseil.io/blog/20180927-swisstablesGoogle Scholar
28. Floraine Grabler, Maneesh Agrawala, Wilmot Li, Mira Dontcheva, and Takeo Igarashi. 2009. Generating Photo Manipulation Tutorials by Demonstration. ACM Trans. Graph. 28, 3 (2009).Google ScholarDigital Library
29. Tovi Grossman, Justin Matejka, and George W. Fitzmaurice. 2010. Chronicle: capture, exploration, and playback of document workflow histories. In UIST.Google Scholar
30. Shi-Min Hu, Kun Xu, Li-Qian Ma, Bin Liu, Bi-Ye Jiang, and Jue Wang. 2013. Inverse Image Editing: Recovering a Semantic Editing History from a Before-and-after Image Pair. ACM Trans. Graph. 32, 6 (2013).Google ScholarDigital Library
31. Oliver van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A Survey on Shape Correspondence. Computer Graphics Forum (2011).Google Scholar
32. KhronosGroup. 2016. gltf efficient, interoperable transmission of 3d scenes and models.Google Scholar
33. Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended Intrinsic Maps. ACM Trans. Graph. 30, 4 (2011).Google ScholarDigital Library
34. Nicholas Kong, Tovi Grossman, Björn Hartmann, Maneesh Agrawala, and George Fitzmaurice. 2012. Delta: A Tool for Representing and Comparing Workflows. In Proc. SIGCHI (CHI ’12).Google ScholarDigital Library
35. VI Levenshtein. 1966. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady 10 (1966).Google Scholar
36. Amazon Lumberyard. 2017. Amazon Lumberyard Bistro, Open Research Content Archive (ORCA). (2017). http://developer.nvidia.com/orca/amazon-lumberyard-bistroGoogle Scholar
37. Morgan McGuire. 2017. Computer Graphics Archive. (2017). https://casual-effects.com/dataGoogle Scholar
38. Michel Neuhaus and Horst Bunke. 2007. Bridging the Gap between Graph Edit Distance and Kernel Machines. World Scientific Publishing.Google Scholar
39. Onshape. 2014. Full-cloud 3d cad system. https://www.onshape.com/. (2014).Google Scholar
40. Bryan O’Sullivan. 2009. Mercurial: The Definitive Guide. O’Reilly Media.Google ScholarDigital Library
41. Maks Ovsjanikov, Michael Bronstein, Emanuele RodolÃă, Leonidas Guibas, Mirela Ben-Chen, Etienne Corman, Frederic Chazal, and Alex Bronstein. 2017. Computing and Processing Correspondances with Functional Maps. In SIGGRAPH ’17 Courses.Google Scholar
42. Jakob Pharr and Humphreys. 2004. Scenes for pbrtv3. (2004). https://pbrt.org/scenes-v3.htmlGoogle Scholar
43. Kaspar Riesen and Horst Bunke. 2009. Approximate graph edit distance computation by means of bipartite graph matching. In Image and Vision Computing. Vol. 27.Google Scholar
44. Gabriele Salvati, Christian Santoni, Valentina Tibaldo, and Fabio Pellacini. 2015. Mesh-Histo: collaborative modeling by sharing and retargeting editing histories. ACM Trans. Graph. 34, 6 (2015).Google ScholarDigital Library
45. Christian Santoni, Gabriele Salvati, Valentina Tibaldo, and Fabio Pellacini. 2018. LevelMerge: Collaborative Game Level Editing by Merging Labeled Graphs. IEEE CG&A 38, 4 (2018).Google Scholar
46. Avinash Sharma, Radu Horaud, Jan Cech, and Edmond Boyer. 2011. Topologically-Robust 3D Shape Matching Based on Diffusion Geometry and Seed Growing. In Computer Vision and Pattern Recognition.Google Scholar
47. Sketchfab. 2011. Sketchfab. (2011). https://sketchfab.comGoogle Scholar
48. University Stanford. 1994. The Stanford 3D Scanning Repository. (1994). http://www.graphics.stanford.edu/data/3Dscanrep/Google Scholar
49. Y Wang, D.J. DeWitt, and J.Y. Cai. 2003. X-Diff: An effective change detection algorithm for XML documents. Proc. International Conference on Data Engineering.Google Scholar
50. WavefrontTechnologies. 1980. OBJ File Format.Google Scholar
51. Kaizhong Zhang. 1989. The editing distance between trees: algorithms and applications. Ph.D. thesis, New York University (1989).Google Scholar
52. K. Zhang and D. Shasha. 1989. Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. SIAM J. Comput. 18, 6 (1989).Google ScholarDigital Library
