[en] We propose a method that computes a piecewise constant approximation of a
function defined on a mesh. The approximation is associated with the cells of a
restricted Voronoï diagram. Our method optimizes an objective function measuring
the quality of the approximation. This objective function depends on the
placement of the samples that define the restricted Voronoï diagram and their
associated function values. We study the continuity of the objective function,
derive the closed-form expression of its derivatives and use them to design a
numerical solution mechanism. The method can be applied to a function that has
discontinuities, and the result aligns the boundaries of the Voronoï cells with
the discontinuities. Some examples are shown, suggesting potential applications
in image vectorization and compact representation of lighting.
Disciplines :
Computer science
Author, co-author :
Nivoliers, Vincent ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Applied and Computational Electromagnetics (ACE)
Lévy, Bruno; LORIA -- INRIA Nancy Grand Est > Équipe projet ALICE
Language :
English
Title :
Approximating Functions on a Mesh with Restricted Voronoï Diagrams
Alternative titles :
[fr] Approximation de fonctions sur un maillages par des diagrammes de Voronoï restreints
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Bruno, L., Bonneel, N., Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration (2012) IMR-21st International Meshing Roundtable-2012, 2
Carrier Baudouin, T., Remacle, J.-F.C., Marchandise, E., Lambrechts, J., Henrotte, F., Lloyd's energy minimization in the Lp norm for quadrilateral surface mesh generation (2012) Engineering with Computers, pp. 1-14. , doi:10.1007s00366-012-0290-x. 4
Cortes, J., Martinez, S., Bullo, F., Spatially-distributed coverage optimization and control with limited-range interactions (2005) ESAIM Contrôle Optimisation et Calcul des Variations, 11. , 691. 4, 10
Cohen-Steiner, D., Alliez, P., Desbrun, M., Variational shape approximation (2004) ACM Transactions on Graphics (TOG), 23, pp. 905-914. , ACM, 2
De Goes, F., Breeden, K., Ostromoukhov, V., Desbrun, M., Blue noise through optimal transport (2012) ACM Transactions on Graphics (TOG), 31 (6). , 171. 2, 4
Dunavant, D.A., High degree efficient symmetrical gaussian quadrature rules for the triangle (1985) International Journal for Numerical Methods in Engineering, 21 (6), pp. 1129-1148
Edelsbrunner Herbert, Mucke Ernst Peter, Simulation of simplicity. A technique to cope with degenerate cases in geometric algorithms (1990) ACM Transactions on Graphics, 9 (1), pp. 66-104. , DOI 10.1145/77635.77639
Felzenszwalb, P.F., Huttenlocher, D.P., Efficient graph-based image segmentation (2004) International Journal of Computer Vision, 59 (2), pp. 167-181. , 2
Holzschuch, N., Alonso, L., Combining higher-order wavelets and discontinuity meshing: A compact representation for radiosity (2004) Eurographics Symposium on Rendering, 2, pp. 275-286
Heckbert, P., Discontinuity meshing for radiosity (1992) Third Eurographics Workshop on Rendering, 2, pp. 203-226
Hoiem, D., Efros, A.A., Hebert, M., Automatic photo pop-up (2005) ACM Transactions on Graphics (TOG), 24, pp. 577-584. , ACM, 2
Hoff III, K.E., Keyser, J., Lin, M., Manocha, D., Culver, T., Fast computation of generalized voronoi diagrams using graphics hardware (1999) Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, pp. 277-286. , ACM Press/Addison-Wesley Publishing Co. 3
Lecot, G., Lévy, B., Ardeco: Automatic region detection and conversion (2006) Proceedings of the 17th Eurographics Conference on Rendering Techniques, pp. 349-360. , Eurographics Association, 2
Lévy, B., Liu, Y., Lp centroidal voronoi tesselation and its applications (2010) ACM Transactions on Graphics, 29. , 4. 4
Lischinski Dani, Tampieri Filippo, Greenberg Donald, P., Discontinuity meshing for accurate radiosity (1992) IEEE Computer Graphics and Applications, 12 (6), pp. 25-39. , DOI 10.1109/38.163622
Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D., Lu, L., Yang, C., On centroidal voronoi tessellation - Energy smoothness and fast computation (2009) ACM Transactions on Graphics (ToG), 28 (4). , 101. 2
Lehtinen, J., Zwicker, M., Turquin, E., Kontkanen, J., Durand, F., Sillion, F.X., Aila, T., A meshless hierarchical representation for light transport (2008) ACM Transactions on Graphics (TOG), 27, p. 37. , ACM, p. 2, 3
Mount, D.M., Arya, S., ANN: A library for approximate nearest neighbor searching (1997) CGC Workshop on Computational Geometry, 3, pp. 33-40
Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., Salesin, D., Diffusion curves: A vector representation for smooth-shaded images (2008) ACM Transactions on Graphics (TOG), 27, p. 92. , ACM, p. 2, 8
Okabe, A., Suzuki, A., Locational optimization problems solved through Voronoi diagrams (1997) European Journal of Operational Research, 98 (3), pp. 445-456. , PII S0377221796003724
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P., (2007) Numerical Recipes 3rd Edition: The Art of Scientific Computing, , Cambridge university press, 6
Pocchiola, M., Vegter, G., The visibility complex (1993) Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 328-337. , ACM, 2
Reynolds, O., (1903) Papers on Mechanical and Physical Subjects, 3. , The University Press, 4
Sud, A., Govindaraju, N., Gayle, R., Andersen, E., Manocha, D., Surface distance maps (2007) Proceedings - Graphics Interface, pp. 35-42. , Proceedings - Graphics Interface 2007
Sun, J., Liang, L., Wen, F., Shum, H.-Y., Image vectorization using optimized gradient meshes (2007) ACM Transactions on Graphics (TOG), 26, p. 11. , ACM, p. 2
Yan, D.-M., Lévy, B., Liu, Y., Sun, F., Wang, W., Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram (2009) Computer Graphics Forum, 28 (5), pp. 1445-1454. , doi:10.1111j.1467-8659.2009.01521.x. 3, 6
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.