OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Lévy , Bruno; Liu , Yang (2010)
Publisher: Association for Computing Machinery
Languages: English
Types: Article
Subjects: centroidal voronoi tesselations, ACM : I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling, hex-dominant meshing, [ INFO.INFO-CG ] Computer Science [cs]/Computational Geometry [cs.CG]
International audience; This paper introduces Lp -Centroidal Voronoi Tessellation (Lp -CVT), a generalization of CVT that minimizes a higher-order moment of the coordinates on the Voronoi cells. This generalization allows for aligning the axes of the Voronoi cells with a predefined background tensor field (anisotropy). Lp -CVT is computed by a quasi-Newton optimization framework, based on closed-form derivations of the objective function and its gradient. The derivations are given for both surface meshing (Ω is a triangulated mesh with per-facet anisotropy) and volume meshing (Ω is the interior of a closed triangulated mesh with a 3D anisotropy field). Applications to anisotropic, quad-dominant surface remeshing and to hex-dominant volume meshing are presented. Unlike previous work, Lp -CVT captures sharp features and intersections without requiring any pre-tagging.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • ALLIEZ, P., COHEN-STEINER, D., DEVILLERS, O., L E´VY, B., AND DESBRUN, M. 2003. Anisotropic polygonal remeshing. ACM Transactions on Graphics 22, 3, 485-493.
    • ALLIEZ, P., COHEN-STEINER, D., YVINEC, M., AND DESBRUN, M. 2005. Variational tetrahedral meshing. ACM Transactions on Graphics 24, 3, 617-625.
    • BOISSONNAT, J.-D., AND OUDOT, S. 2006. Provably good sampling and meshing of Lipschitz surfaces. In SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry, 337-346.
    • BOMMES, D., ZIMMER, H., AND KOBBELT, L. 2009. Mixedinteger quadrangulation. ACM Transactions on Graphics 28, 3, 1-10.
    • BUSARYEV, O., DEY, T. K., AND LEVINE, J. A. 2009. Repairing and meshing imperfect shapes with Delaunay refinement. In SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, 25-33.
    • CHEN, L., AND XU, J. 2004. Optimal Delaunay triangulations. Journal of Computational Mathematics 22, 2, 299-308.
    • COHEN-STEINER, D., ALLIEZ, P., AND DESBRUN, M. 2004. Variational shape approximation. ACM Transactions on Graphics 23, 905-914.
    • DANIELS-II, J., SILVA, C. T., AND COHEN, E. 2009. Localized quadrilateral coarsening. Computer Graphics Forum 28, 1437- 1444.
    • DEY, T. K., AND LEVINE, J. A. 2008. Delaunay meshing of piecewise smooth complexes without expensive predicates. Algorithms 2, 1327-1349. OSU-CISRC-7/08-TR40.
    • DONG, S., BREMER, P.-T., GARLAND, M., PASCUCCI, V., AND HART, J. C. 2006. Spectral surface quadrangulation. ACM Transactions on Graphics 25, 1057-1066.
    • DU, Q., AND EMELIANENKO, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numerical Linear Algebra with Applications 13, 2-3, 173-192.
    • DU, Q., AND WANG, D. 2003. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. International Journal for Numerical Methods in Engineering 56, 1355- 1373.
    • DU, Q., AND WANG, D. 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM Journal on Scientific Computing 26, 3, 737-761.
    • DU, Q., FABER, V., AND GUNZBURGER, M. 1999. Centroidal Voronoi tessellations: applications and algorithms. SIAM Review 41, 4, 637-676.
    • EDELSBRUNNER, H., AND SHAH, N. R. 1997. Triangulating topological spaces. International Journal of Computational Geometry & Applications 7, 4, 365-378.
    • HUANG, J., ZHANG, M., MA, J., LIU, X., KOBBELT, L., AND BAO, H. 2008. Spectral quadrangulation with orientation and alignment control. ACM Transactions on Graphics 27.
    • IRI, M., MUROTA, K., AND OHYA, T. 1984. A fast Voronoidiagram algorithm with applications to geographical optimization problems. In Proc. IFIP, 273-288.
    • ITOH, T., AND SHIMADA, K. 2001. Automatic conversion of triangular meshes into quadrilateral meshes with directionality. International Journal of CAD/CAM.
    • KALBERER, F., NIESER, M., AND POLTHIER, K. 2007. Quadcover - surface parameterization using branched coverings. Computer Graphics Forum 26, 375-384.
    • LABELLE, F., AND SHEWCHUK, J. R. 2003. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry, 191-200.
    • LAI, Y.-K., KOBBELT, L., AND HU, S.-M. 2008. An incremental approach to feature aligned quad dominant remeshing. In ACM SPM conference proceedings.
    • LASSERRE, J., AND AVRACHENKOV, K. 2001. Integration on a simplex: The multi-dimensional version of Rab xpdx. American
    • Mathematics Monthly 108, 151-154.
    • LIU, Y., WANG, W., L E´VY, B., SUN, F., YAN, D.-M., LU, L., AND YANG, C. 2009. On centroidal Voronoi tessellationenergy smoothness and fast computation. ACM Transactions on Graphics 28, 4, 1-17.
    • LLOYD, S. P. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129-137.
    • MAR E´CHAL, L. 2009. Advances in octree-based all-hexahedral mesh generation: handling sharp features. In 18th International Meshing Roundtable conference proceedings.
    • MARTIN, T., COHEN, E., AND KIRBY, M. 2008. Volumetric parameterization and trivariate B-spline fitting using harmonic functions. In SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling, 269-280.
    • MESHKAT, S., AND TALMOR, D. 2000. Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh. International Journal for Numerical Methods in Engineering 49, 17-30.
    • MINKA, T. 1997. Old and new matrix algebra useful for statistics. Tech. rep., MIT Media Lab. revised 12/00.
    • MOUNT, D. M., AND ARYA, S. 1997. ANN: A library for approximate nearest neighbor searching. In Proceedings CGC Workshop on Computational Geometry, 33-40.
    • OWEN, S. J., AND SAIGAL, S. 2000. H-Morph: An indirect approach to advancing front hex meshing. International Journal for Numerical Methods in Engineering 49, 289-312.
    • RAY, N., LI, W. C., L E´VY, B., SHEFFER, A., AND ALLIEZ, P. 2006. Periodic global parameterization. ACM Transactions on Graphics 25, 4, 1460-1485.
    • SHEPHERD, J. F., AND JOHNSON, C. R. 2008. Hexahedral mesh generation constraints. Engineering with Computers 24, 3, 195- 213.
    • SHEPHERD, J., MITCHELL, S. A., KNUPP, P., AND WHITE, D. 2000. Methods for multisweep automation. In 9th Intl. Meshing Roundtable conference proceedings.
    • STATEN, M. L., OWEN, S. J., AND BLACKER, T. D. 2005. Unconstrained paving and plastering: A new idea for all hexahedral mesh generation. In International Meshing Roundtable conference proceedings.
    • STEINER, D., AND FISCHER, A. 2005. Planar parameterization for closed manifold genus-g meshes using any type of positive weights. Journal of Computational Methods in Information Science and Engineering 5, 2.
    • TCHON, K.-F., AND CAMARERO, R. 2006. Quad-dominant mesh adaptation using specialized simplicial optimization. In 15th International Meshing Roundtable conference proceedings.
    • TONG, Y., ALLIEZ, P., COHEN-STEINER, D., AND DESBRUN, M. 2006. Designing quadrangulations with discrete harmonic forms. In SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, 201-210.
    • TOURNOIS, J., WORMSER, C., ALLIEZ, P., AND DESBRUN, M. 2009. Interleaving delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Transactions on Graphics 28, 75:1-75:9.
    • VALETTE, S., CHASSERY, J.-M., AND PROST, R. 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Transactions on Visualization and Computer Graphics 14, 2, 369-381.
    • VYAS, V., AND SHIMADA, K. 2009. Tensor-guided hex-dominant mesh generation with targeted all-hex regions. In 18th International Meshing Roundtable conference proceedings.
    • YAMAKAWA, S., AND SHIMADA, K. 2003. Anisotropic tetrahedral meshing via bubble packing and advancing front. International Journal for Numerical Methods in Engineering 57.
    • YAMAKAWA, S., AND SHIMADA, K. 2003. Fully-automated hexdominant mesh generation with directionality control via packing rectangular solid cells. International Journal for Numerical Methods in Engineering 57, 2099-2129.
    • YAN, D.-M., L E´VY, B., LIU, Y., SUN, F., AND WANG, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer Graphics Forum 28, 5, 1445-1454.
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects


Cite this article

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok