“Fast winding numbers for soups and clouds” by Barill, Dickson, Schmidt, Levin and Jacobson
Conference:
Type:
Entry Number: 43
Title:
- Fast winding numbers for soups and clouds
Session/Category Title: An Immersion in Computational Geometry
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Inside-outside determination is a basic building block for higher-level geometry processing operations. Generalized winding numbers provide a robust answer for triangle meshes, regardless of defects such as self-intersections, holes or degeneracies. In this paper, we further generalize the winding number to point clouds. Previous methods for evaluating the winding number are slow for completely disconnected surfaces, such as triangle soups or-in the extreme case- point clouds. We propose a tree-based algorithm to reduce the asymptotic complexity of generalized winding number computation, while closely approximating the exact value. Armed with a fast evaluation, we demonstrate the winding number in a variety of new applications: voxelization, signing distances, generating 3D printer paths, defect-tolerant mesh booleans and point set surfaces.
References:
1. M Alexa, Johannes Behr, D Cohen-Or, Shachar Fleishman, David Levin, and Cláudio T Silva. 2001. Point Set Surfaces. IEEE Visualization (2001), 21–537. Google ScholarDigital Library
2. Nina Amenta and Yong Joo Kil. 2004. Denning point-set surfaces. ACM Trans. Graph. (2004). Google ScholarDigital Library
3. James L. Andrews. 2013. User-Guided Inverse 3D Modeling. Ph.D. Dissertation. UC Berkeley.Google Scholar
4. J. Andreas Baerentzen and Henrik Aanaes. 2005. Signed Distance Computation Using the Angle Weighted Pseudonormal. IEEE TVCG (2005). Google ScholarDigital Library
5. J. Barnes and P. Hut. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature (1986).Google Scholar
6. Mikhail Belkin, Jian Sun, and Yusu Wang. 2009. Constructing Laplace Operator from Point Clouds in Rd. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’09). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1031–1040. http://dl.acm.org/citation.cfm?id=1496770.1496882 Google ScholarDigital Library
7. Matthew Berger, Andrea Tagliasacchi, Lee M. Seversky, Pierre Alliez, Gaël Guennebaud, Joshua A. Levine, Andrei Sharf, and Claudio T. Silva. 2017. A Survey of Surface Reconstruction from Point Clouds. Comput. Graph. Forum (2017). Google ScholarDigital Library
8. Guy E Blelloch and Girija J Narlikar. 1994. A practical comparison of N-body algorithms. Parallel Algorithms (1994).Google Scholar
9. Dobrina Boltcheva and Bruno Lévy. 2017. Surface reconstruction by computing restricted Voronoi cells in parallel. Computer-Aided Design (2017).Google Scholar
10. Pavel Borodin, Gabriel Zachmann, and Reinhard Klein. 2004. Consistent Normal Orientation for Polygonal Meshes. In Computer Graphics International 2004 (CGI 2004). 18–25. Google ScholarDigital Library
11. Fatih Calakli and Gabriel Taubin. 2011. SSD – Smooth Signed Distance Surface Reconstruction. Comput. Graph. Forum 30, 7 (2011), 1993–2002.Google ScholarCross Ref
12. Stéphane Calderon and Tamy Boubekeur. 2014. Point morphology. ACM Transactions on Graphics (2014). Google ScholarDigital Library
13. Jonathan C Carr, Richard K Beatson, Jon B Cherrie, Tim J Mitchell, W Richard Fright, Bruce C McCallum, and Tim R Evans. 2001. Reconstruction and representation of 3D objects with radial basis functions. Siggraph (2001), 67–76. Google ScholarDigital Library
14. F. Cazals and M. Pouget. 2003. Estimating differential quantities using polynomial fitting of osculating jets. In Proc. SGP. 177–187. Google ScholarDigital Library
15. Angel X. Chang, Thomas A. Funkhouser, Leonidas J. Guibas, Pat Hanrahan, Qi-Xing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu. 2015. ShapeNet: An Information-Rich 3D Model Repository. CoRR (2015). arXiv:1512.03012Google Scholar
16. Paolo Cignoni, Massimiliano Corsini, and Guido Ranzuglia. 2008. MeshLab: an Open-Source 3D Mesh Processing System. ERCIM News 73 (April 2008), 45–46. http://vcg.isti.cnr.it/Publications/2008/CCR08Google Scholar
17. Paolo Cignoni, Paola Marino, Claudio Montani, Enrico Puppo, and Roberto Scopigno. 1997. Speeding Up Isosurface Extraction Using Interval Trees. IEEE Trans. Vis. Comput. Graph. (1997). Google ScholarDigital Library
18. Fang Da, David Hahn, Christopher Batty, Chris Wojtan, and Eitan Grinspun. 2016. Surface-only liquids. ACM Transactions on Graphics (2016). Google ScholarDigital Library
19. Martin de Lasa. 2018. Autodesk, personal communication. (2018).Google Scholar
20. Olivier Dionne and Martin de Lasa. 2013. Voxelization using generalized winding numbers. (2013). https://vimeo.com/72468198Google Scholar
21. Olivier Dionne and Martin de Lasa. 2014. Geodesic Binding for Degenerate Character Geometry Using Sparse Voxelization. IEEE Trans. Vis. Comput. Graph. (2014).Google ScholarCross Ref
22. Lawrence C. Evans. 1997. Partial Differential Equations (1 ed.). 37 pages.Google Scholar
23. Oleg Fryazinov, Alexander A Pasko, and Valery Adzhiev. 2011. BSP-fields – An exact representation of polygonal objects by differentiable scalar fields based on binary space partitioning. Computer-Aided Design (2011). Google ScholarDigital Library
24. Simon Fuhrmann and Michael Goesele. 2014. Floating Scale Surface Reconstruction. ACM Trans. Graph. 33, 4, Article 46 (July 2014), 11 pages. Google ScholarDigital Library
25. Leslie Greengard and Zydrunas Gimbutas. 2017. fmmlib3d: Fast Multipole Method (FMM) library in R3. (2017). https://github.com/zgimbutas/fmmlib3d Version 1.2.1.Google Scholar
26. L. Greengard and V. Rokhlin. 1997. A Fast Algorithm for Particle Simulations. J. Comput. Phys. 135, 2 (1997), 280 — 292. Google ScholarDigital Library
27. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. (2010). http://eigen.tuxfamily.org.Google Scholar
28. A Ichim, P Kadlecek, L Kavan, and M Pauly. 2017. Phace: Physics-based Face Modeling and Animation. ACM Trans. Graph. (2017). Google ScholarDigital Library
29. Peter Ilbery, Luke Kendall, Cyril Concolato, and Michael McCosker. 2013. Biharmonic Diffusion Curve Images from Boundary Elements. ACM Trans. Graph. (2013). Google ScholarDigital Library
30. Alec Jacobson. 2016. Boolean Operations using Generalized Winding Numbers. CoRR abs/1601.07953 (2016). arXiv:1601.07953 http://arxiv.org/abs/1601.07953Google Scholar
31. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 32, 4 (2013), 33:1–33:12. Google ScholarDigital Library
32. Alec Jacobson, Daniele Panozzo, et al. 2017. libigl: A simple C++ geometry processing library. (2017). http://libigl.github.io/libigl/.Google Scholar
33. Chiyu Jian and Philip Marcus. 2017. Hierarchical Detail Enhancing Mesh-Based Shape Generation with 3D Generative Adversarial Network. CoRR (2017). arXiv:1709.07581Google Scholar
34. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Proc. SGP. 61–70. Google ScholarDigital Library
35. Michael Kazhdan and Hugues Hoppe. 2013. Screened poisson surface reconstruction. ACM Transactions on Graphics (TOG) 32, 3 (2013), 29. Google ScholarDigital Library
36. Binh Huy Le and Zhigang Deng. 2017. Interactive cage generation for mesh deformation. I3D (2017).Google Scholar
37. William E Lorensen and Harvey E Cline. 1987. Marching cubes – A high resolution 3D surface construction algorithm. Siggraph (1987), 163–169. Google ScholarDigital Library
38. Wenjia Lu, Zuoqiang Shi, Bin Wang, and Jian Sun. 2017. Gauss Surface Reconstruction. In Geometric Modeling and Processing.Google Scholar
39. Geoffrey Marchal. 2015. Head St Batist-decimated. (May 2015). https://sketchfab.com/models/3d3115c7db08466abbbb0dcaac2c962eGoogle Scholar
40. A.L.F Meister. 1769. Generalia de genesi figurarum planarum et inde pendentibus earum ajfectionibus. Novi Comm. Soc. Reg. Scient. Gotting. (1769), 144–180+9 plates.Google Scholar
41. Christian Mostegel, Rudolf Prettenthaler, Friedrich Fraundorfer, and Horst Bischof. 2017. Scalable Surface Reconstruction from Point Clouds with Extreme Scale and Density Diversity. CVPR (2017).Google Scholar
42. T. M. Murali and Thomas A. Funkhouser. 1997. Consistent Solid and Boundary Representations from Arbitrary Polygonal Data. In Proceedings of the 1997 Symposium on Interactive 3D Graphics (I3D ’97). ACM, New York, NY, USA, 155–ff. Google ScholarDigital Library
43. Rahul Narain. 2013. The harmonicity of the generalized winding number. (2013). http://r-to-the-n.tumblr.com/post/52752267384/Google Scholar
44. Fakir S. Nooruddin and Greg Turk. 2003. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Transactions on Visualization and Computer Graphics 9, 2 (April 2003), 191–205. Google ScholarDigital Library
45. Yutaka Ohtake, Alexander Belyaev, Marc Alexa, Greg Turk, and Hans-Peter Seidel. 2003. Multi-Level Partition of Unity Implicits. ACM Trans. Graph. (2003). Google ScholarDigital Library
46. Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. 2004. Ridge-Valley Lines on Meshes via Implicit Surface Fitting. ACM Trans. Graph. (2004). Google ScholarDigital Library
47. Alexandrina Orzan, Adrien Bousseau, Holger Winnemöller, Pascal Barla, Joëlle Thollot, and David Salesin. 2008. Diffusion curves – a vector representation for smooth-shaded images. ACM Trans. Graph. (2008). Google ScholarDigital Library
48. Mathieu Sanchez, Oleg Fryazinov, and Alexander Pasko. 2012. Efficient Evaluation of Continuous Signed Distance to a Polygonal Mesh. In Proc. SCCG. Google ScholarDigital Library
49. L. M. Seversky and L. Yin. 2012. A Global Parity Measure for Incomplete Point Cloud Data. Comput. Graph. Forum 31, 7ptl (Sept. 2012), 2097–2106. Google ScholarDigital Library
50. Shy Shalom, Ariel Shamir, Hao Zhang 0002, and D Cohen-Or. 2010. Cone carving for surface reconstruction. ACM Trans. Graph. (2010). Google ScholarDigital Library
51. C Shen, J.F. O’Brien, and J.R. Shewchuk. 2004. Interpolating and approximating implicit surfaces from polygon soup. 23, 3 (2004), 896–904. Google ScholarDigital Library
52. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering. Lecture Notes in Computer Science, Vol. 1148. Springer-Verlag, 203–222. Google ScholarDigital Library
53. Timothy Sun, Papoj Thamjaroenporn, and Changxi Zheng. 2014. Fast multipole representation of diffusion curves and points. ACM Transactions on Graphics (2014). Google ScholarDigital Library
54. Xin Sun, Guofu Xie, Yue Dong, Stephen Lin, W Xu, Wencheng Wang, Xin Tong, and Baining Guo. 2012. Diffusion curve textures for resolution independent texture mapping. ACM Transactions on Graphics (TOG) (2012). Google ScholarDigital Library
55. Kenshi Takayama, Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2014. A Simple Method for Correcting Facet Orientations in Polygon Meshes Based on Ray Casting. Journal of Computer Graphics Techniques (2014).Google Scholar
56. Jasper van de Gronde. 2010. A High Quality Solver for Diffusion Curves. PhD. Dissertation. University of Groningen.Google Scholar
57. A van Oosterom and J Strackee. 1983. The Solid Angle of a Plane Triangle. IEEE Trans. Biomedical Engineering 30, 2 (1983).Google Scholar
58. He Wang, Kirill A. Sidorov, Peter Sandilands, and Taku Komura. 2013. Harmonic Parameterization by Electrostatics. ACM Trans. Graph. (2013). Google ScholarDigital Library
59. G Wyvill, C McPheeters, and B Wyvill. 1986. Data structure for soft objects. The Visual Computer (1986).Google Scholar
60. Hongyi Xu and Jernej Barbič. 2014. Signed Distance Fields for Polygon Soup Meshes. Graphics Interface 2014 (2014). Google ScholarDigital Library
61. Lyubomir Zagorchev and A Ardeshir Goshtasby. 2012. A Curvature-Adaptive Implicit Surface Reconstruction for Irregularly Spaced Points. IEEE Trans. Vis. Comput. Graph. (2012). Google ScholarDigital Library
62. Xinxin Zhang and Robert Bridson. 2014. A PPPM fast summation method for fluids and beyond. ACM Transactions on Graphics (2014). Google ScholarDigital Library
63. Kaichi Zhou, Eugene Zhang, Jirí Bittner, and Peter Wonka. 2008. Visibility-driven Mesh Analysis and Visualization through Graph Cuts. IEEE Transactions on Visualization and Computer Graphics 14 (2008). Google ScholarDigital Library
64. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10, 000 3D-Printing Models. CoRR abs/1605.04797 (2016). arXiv:1605.04797 http://arxiv.org/abs/1605.04797Google Scholar
