Document Open Access Logo

Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm

Authors Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, Ahmad A. Rushdi

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.1.pdf
  • Filesize: 3.38 MB
  • 16 pages

Document Identifiers

Author Details

Ahmed Abdelkader
Chandrajit L. Bajaj
Mohamed S. Ebeida
Ahmed H. Mahmoud
Scott A. Mitchell
John D. Owens
Ahmad A. Rushdi

Cite As Get BibTex

Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi. Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.1

Abstract

We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from alpha-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given an epsilon-sample on the bounding surface, with a weak sigma-sparsity condition, we work with the balls of radius delta times the local feature size centered at each sample. The corners of this union of balls are the Voronoi sites, on both sides of the surface. The facets common to cells on opposite sides reconstruct the surface. For appropriate values of epsilon, sigma and delta, we prove that the surface reconstruction is isotopic to the bounding surface. With the surface protected, the enclosed volume can be further decomposed into an isotopic volume mesh of fat Voronoi cells by generating a bounded number of sites in its interior. Compared to state-of-the-art methods based on clipping, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured grids or random samples.

Subject Classification

Keywords
  • sampling conditions
  • surface reconstruction
  • polyhedral meshing
  • Voronoi

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Abdelkader, C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi. Sampling conditions for conforming Voronoi meshing by the VoroCrust algorithm. CoRR, arXiv:1803.06078, 2018. URL: http://arxiv.org/abs/1803.06078.
  2. A. Abdelkader, C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi. VoroCrust Illustrated: Theory and Challenges (Multimedia Contribution). In 34th International Symposium on Computational Geometry (SoCG 2018), pages 77:1-77:4, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.77.
  3. A. Abdelkader, C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi. VoroCrust: Voronoi meshing without clipping. Manuscript, In preparation. Google Scholar
  4. A. Abdelkader, C. Bajaj, M. Ebeida, and S. Mitchell. A Seed Placement Strategy for Conforming Voronoi Meshing. In Canadian Conference on Computational Geometry, 2017. Google Scholar
  5. A. Abdelkader, A. Mahmoud, A. Rushdi, S. Mitchell, J. Owens, and M. Ebeida. A constrained resampling strategy for mesh improvement. Computer Graphics Forum, 36(5):189-201, 2017. Google Scholar
  6. O. Aichholzer, F. Aurenhammer, B. Kornberger, S. Plantinga, G. Rote, A. Sturm, and G. Vegter. Recovering structure from r-sampled objects. Computer Graphics Forum, 28(5):1349-1360, 2009. Google Scholar
  7. N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete &Computational Geometry, 22(4):481-504, dec 1999. Google Scholar
  8. N. Amenta, M. Bern, and D. Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical models and image processing, 60(2):125-135, 1998. Google Scholar
  9. N. Amenta, M. Bern, and D. Eppstein. Optimal point placement for mesh smoothing. Journal of Algorithms, 30(2):302-322, 1999. Google Scholar
  10. N. Amenta, M. Bern, and M. Kamvysselis. A new Voronoi-based surface reconstruction algorithm. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, pages 415-421, 1998. Google Scholar
  11. N. Amenta, S. Choi, T. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. In 16th Annual Symposium on Computational Geometry, pages 213-222, 2000. Google Scholar
  12. N. Amenta, S. Choi, and R.-K. Kolluri. The power crust. In Proceedings of the Sixth ACM Symp. on Solid Modeling and Applications, pages 249-266, 2001. Google Scholar
  13. N. Amenta, S. Choi, and R.-K. Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry, 19(2):127-153, 2001. Google Scholar
  14. N. Amenta and T. Dey. Normal variation for adaptive feature size. CoRR, abs/1408.0314, 2014. Google Scholar
  15. N. Amenta and R.-K. Kolluri. The medial axis of a union of balls. Computational Geometry, 20(1):25-37, 2001. Selected papers from the 12th Annual Canadian Conference. Google Scholar
  16. N. Amenta, T. Peters, and A. Russell. Computational topology: ambient isotopic approximation of 2-manifolds. Theoretical Computer Science, 305(1):3-15, 2003. Topology in Computer Science. Google Scholar
  17. L. Beirão da Veiga, F. Brezzi, L.-D. Marini, and A. Russo. The hitchhiker’s guide to the virtual element method. Mathematical Models and Methods in Applied Sciences, 24(08):1541-1573, 2014. Google Scholar
  18. N. Bellomo, F. Brezzi, and G. Manzini. Recent techniques for PDE discretizations on polyhedral meshes. Mathematical Models and Methods in Applied Sciences, 24(08):1453-1455, 2014. Google Scholar
  19. F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, and G. Taubin. The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, 5(4):349-359, Oct 1999. Google Scholar
  20. J. Bishop. Simulating the pervasive fracture of materials and structures using randomly close packed Voronoi tessellations. Computational Mechanics, 44(4):455-471, sep 2009. Google Scholar
  21. J.-D. Boissonnat and S. Oudot. Provably good sampling and meshing of surfaces. Graphical Models, 67(5):405-451, 2005. Solid Modeling and Applications. Google Scholar
  22. T. Brochu, C. Batty, and R. Bridson. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph., 29(4):47:1-47:9, 2010. Google Scholar
  23. F. Cazals, T. Dreyfus, S. Sachdeva, and N. Shah. Greedy geometric algorithms for collection of balls, with applications to geometric approximation and molecular coarse-graining. Computer Graphics Forum, 33(6):1-17, 2014. Google Scholar
  24. F. Cazals, H. Kanhere, and S. Loriot. Computing the volume of a union of balls: A certified algorithm. ACM Trans. Math. Softw., 38(1):3:1-3:20, 2011. Google Scholar
  25. F. Chazal and D. Cohen-Steiner. A condition for isotopic approximation. Graphical Models, 67(5):390-404, 2005. Solid Modeling and Applications. Google Scholar
  26. F. Chazal and A. Lieutier. Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees. Computational Geometry, 40(2):156-170, 2008. Google Scholar
  27. S.-W. Cheng, T. Dey, H. Edelsbrunner, M. Facello, and S.-H. Teng. Silver exudation. J. ACM, 47(5):883-904, 2000. Google Scholar
  28. S.-W. Cheng, T. Dey, and J. Shewchuk. Delaunay Mesh Generation. CRC Press, 2012. Google Scholar
  29. D. Cohen-Steiner, É.-C. de Verdière, and M. Yvinec. Conforming Delaunay triangulations in 3D. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, SCG '02, pages 199-208, 2002. Google Scholar
  30. K. Sykes D. Letscher. On the stability of medial axis of a union of disks in the plane. In 28th Canadian Conference on Computational Geometry, CCCG 2016, pages 29-33, 2016. Google Scholar
  31. T. Dey. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, New York, NY, USA, 2006. Google Scholar
  32. T. Dey, K. Li, E. Ramos, and R. Wenger. Isotopic reconstruction of surfaces with boundaries. In Computer Graphics Forum, volume 28:5, pages 1371-1382, 2009. Google Scholar
  33. T. Dey and L. Wang. Voronoi-based feature curves extraction for sampled singular surfaces. Computers &Graphics, 37(6):659-668, 2013. Shape Modeling International (SMI) Conference 2013. Google Scholar
  34. L. Duan and F. Lafarge. Image partitioning into convex polygons. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3119-3127, June 2015. Google Scholar
  35. M. Ebeida and S. Mitchell. Uniform random Voronoi meshes. In International Meshing Roundtable (IMR), pages 258-275, 2011. Google Scholar
  36. H. Edelsbrunner. Weighted alpha shapes. University of Illinois at Urbana-Champaign, Department of Computer Science, 1992. Google Scholar
  37. H. Edelsbrunner. The union of balls and its dual shape. Discrete & Computational Geometry, 13(3):415-440, Jun 1995. Google Scholar
  38. H. Edelsbrunner and E.-P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph., 9(1):66-104, 1990. Google Scholar
  39. R. Eymard, T. Gallouët, and R. Herbin. Finite volume methods. In Techniques of Scientific Computing (Part 3), volume 7 of Handbook of Numerical Analysis, pages 713-1018. Elsevier, 2000. Google Scholar
  40. Ø. Klemetsdal, R. Berge, K.-A. Lie, H. Nilsen, and O. Møyner. SPE-182666-MS, chapter Unstructured Gridding and Consistent Discretizations for Reservoirs with Faults and Complex Wells. Society of Petroleum Engineers, 2017. Google Scholar
  41. D. Kuzmin. A guide to numerical methods for transport equations. University Erlangen-Nuremberg, 2010. Google Scholar
  42. G. Manzini, A. Russo, and N. Sukumar. New perspectives on polygonal and polyhedral finite element methods. Mathematical Models and Methods in Applied Sciences, 24(08):1665-1699, 2014. Google Scholar
  43. R. Merland, G. Caumon, B. Lévy, and P. Collon-Drouaillet. Voronoi grids conforming to 3D structural features. Computational Geosciences, 18(3):373-383, 2014. Google Scholar
  44. G. Miller, D. Talmor, and S.-H. Teng. Data generation for geometric algorithms on non-uniform distributions. International Journal of Computational Geometry and Applications, 09(06):577-597, 1999. Google Scholar
  45. M. Murphy, D. Mount, and C. Gable. A point-placement strategy for conforming Delaunay tetrahedralization. International Journal of Computational Geometry &Applications, 11(06):669-682, 2001. Google Scholar
  46. P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete &Computational Geometry, 39(1-3):419-441, 2008. Google Scholar
  47. A. Okabe, B. Boots, K. Sugihara, and S.-N. Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, volume 501. John Wiley &Sons, 2009. Google Scholar
  48. M. Peric and S. Ferguson. The advantage of polyhedral meshes. Dynamics - Issue 24, page 4–5, Spring 2005. The customer magazine of the CD-adapco Group, currently maintained by Siemens at http://siemens.com/mdx. The issue is available at http://mdx2.plm.automation.siemens.com/magazine/dynamics-24 (accessed March 29, 2018).
  49. A. Rand and N. Walkington. Collars and intestines: Practical conforming Delaunay refinement. In Proceedings of the 18th International Meshing Roundtable, pages 481-497, 2009. Google Scholar
  50. C. Rycroft. Voro++: A three-dimensional Voronoi cell library in C++. Chaos, 19(4):-, 2009. Software available online at URL: http://math.lbl.gov/voro++/.
  51. M. Sents and C. Gable. Coupling LaGrit Unstructured Mesh Generation and Model Setup with TOUGH2 Flow and Transport. Comput. Geosci., 108(C):42-49, 2017. Google Scholar
  52. H. Si, K. Gärtner, and J. Fuhrmann. Boundary conforming Delaunay mesh generation. Computational Mathematics and Mathematical Physics, 50(1):38-53, 2010. Google Scholar
  53. D. Sieger, P. Alliez, and M. Botsch. Optimizing Voronoi diagrams for polygonal finite element computations. In International Meshing Roundtable (IMR), pages 335-350. Springer, 2010. Google Scholar
  54. P. Stelldinger. Topologically correct surface reconstruction using alpha shapes and relations to ball-pivoting. In Pattern Recognition, 2008. ICPR 2008. 19th International Conference on, pages 1-4. IEEE, 2008. Google Scholar
  55. D.-M. Yan, W. Wang, B. Lévy, and Y. Liu. Efficient computation of clipped Voronoi diagram for mesh generation. Computer-Aided Design, 45(4):843-852, 2013. Google Scholar
  56. Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer Graphics Forum, 28(5):1445-1454, jul 2009. Google Scholar
  57. M. Yip, J. Mohle, and J. Bolander. Automated modeling of three‐dimensional structural components using irregular lattices. Computer-Aided Civil and Infrastructure Engineering, 20(6):393-407, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact