“Fast winding numbers for soups and clouds” by Barill, Dickson, Schmidt, Levin and Jacobson

  • ©Gavin Barill, Neil G. Dickson, Ryan Schmidt, David I. W. Levin, and Alec Jacobson



Entry Number: 43

Session Title:

    An Immersion in Computational Geometry


    Fast winding numbers for soups and clouds




    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.


    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

ACM Digital Library Publication: