[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Analytic evaluation of the FCC Voronoi-splines

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

We propose an analytic evaluation algorithm for splines and their derivatives (gradient and Hessian) of FCC volume datasets based on the Voronoi-spline of order two and three, \(V_{1}(\varvec{x})\) and \(V_{2}(\varvec{x})\), respectively. Based on the ideas by Van De Ville et al. (IEEE Trans. Image Process 13(6), 758–772, 2004) and Mirzargar and Entezari (IEEE Trans. Signal Process 58(9), 4572–4582, 2010), we obtain the analytic formulas by merging those of the box-splines into which the Voronoi-spline basis is decomposed. The polynomial formulas of the high order box-splines are computed using a modified version of the recursive evaluation package by de Boor (Numer. Algorithms 5(1), 5–23, 1993). We also analyze the symmetries of the polynomial structure and the Voronoi-spline to minimize the number of formulas, which hugely improves the performance especially on GPUs. Our GPU isosurface raycaster, which is publicly available, shows that \(V_{1}\) and \(V_{2}\) are appropriate for high-speed and high-quality interactive FCC volume renderings, respectively. Specifically, \(V_{1}\) and \(V_{2}\) shows about 240 and 41.5 fps (frames per second), respectively, for the \(160^3\times 4\) FCC dataset rendered on the \(512^2\) framebuffer. Compared to the approximate technique based on texture look-up, ours shows \(\approx 5.7\) times better performance with superior image quality. Moreover, compared to the analytic evaluation algorithm recently proposed (Horacsek and Alim 2022), ours shows \(> 2\) times better computational performance in high-quality real-world application.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Data availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

References

  1. Van De Ville, D., Blu, T., Unser, M., Philips, W., Lemahieu, I., Van de Walle, R.: Hex-splines: a novel spline family for hexagonal lattices. IEEE Trans. Image Process. 13(6), 758–772 (2004). ISSN 1057-7149. https://doi.org/10.1109/TIP.2004.827231

  2. Mirzargar, M., Entezari, A.: Voronoi splines. IEEE Trans. Signal Process. 58(9), 4572–4582 (2010). https://doi.org/10.1109/TSP.2010.2051808

    Article  MathSciNet  MATH  Google Scholar 

  3. de Boor, C.: On the evaluation of box splines. Numer. Algorithms 5(1), 5–23 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  4. Horacsek, J., Alim, U.: FastSpline: Automatic generation of interpolants for lattice samplings. ACM Trans. Math. Softw. (2022) https://doi.org/10.1145/3577194

  5. Alireza Entezari, Ramsay Dyer, and Torsten Moller. Linear and cubic box splines for the body centered cubic lattice. In: IEEE Visualization 2004, pp. 11–18. IEEE (2004). 10.1109/VISUAL.2004.65

  6. Kim, M., Entezari, A., Peters, J.: Box spline reconstruction on the face-centered cubic lattice. IEEE Trans. Vis. Comput. Graph. 14(6), 1523–1530 (2008). https://doi.org/10.1109/TVCG.2008.115

    Article  Google Scholar 

  7. Kim, M.: Quartic box-spline reconstruction on the BCC lattice. IEEE Trans. Vis. Comput. Graph. 19(2), 319–330 (2013). https://doi.org/10.1109/TVCG.2012.130

    Article  MathSciNet  Google Scholar 

  8. de Boor, C., Höllig, K., Riemenschneider, S.: Box splines, vol. 98. Springer Science & Business Media (1993). https://doi.org/10.1007/978-1-4757-2244-4

  9. Horacsek, J., Alim, U.: A closed PP form of box splines via Green’s function decomposition. J. Approx. Theory 233, 37–57 (2018). https://doi.org/10.1016/j.jat.2018.04.002

    Article  MathSciNet  MATH  Google Scholar 

  10. Petersen, D.P., Middleton, D.: Sampling and reconstruction of wave-number-limited functions in \(N\)-dimensional Euclidean spaces. Inf. Control. 5(4), 279–323 (1962). https://doi.org/10.1016/S0019-9958(62)90633-2

    Article  MathSciNet  Google Scholar 

  11. Csébfalvi, B.: Cosine-weighted B-spline interpolation: a fast and high-quality reconstruction scheme for the body-centered cubic lattice. IEEE Trans. Vis. Comput. Graph. 19(9), 1455–1466 (2013). https://doi.org/10.1109/TVCG.2013.7

    Article  Google Scholar 

  12. Ferenc Rácz, G., Csébfalvi, B.: Cosine-weighted B-spline interpolation on the face-centered cubic lattice. Comput. Graphics Forum 37(3), 503–511 (2018). https://doi.org/10.1111/cgf.13437

    Article  Google Scholar 

  13. Kobbelt, L.: Stable evaluation of box-splines. Numer. Algorithms, 14(4), 377–382 (1997). ISSN 1572-9265. https://doi.org/10.1023/A:1019133501773

  14. McCool, M.D.: Accelerated evaluation of box splines via a parallel inverse FFT. Comput. Graphics Forum 15(1), 35–45 (1996). https://doi.org/10.1111/1467-8659.1510035

    Article  Google Scholar 

  15. Kim, M., Peters, J.: Fast and stable evaluation of box-splines via the BB-form. Numer. Algorithms 50(4), 381–399 (2009). https://doi.org/10.1007/s11075-008-9231-6

    Article  MathSciNet  MATH  Google Scholar 

  16. Finkbeiner, B., Entezari, A., Van De Ville, D., Möller, T.: Efficient volume rendering on the body centered cubic lattice using box splines. Comput. Graph. 34(4), 409–423 (2010). https://doi.org/10.1016/j.cag.2010.02.002

    Article  Google Scholar 

  17. Kim, M.: Analysis of symmetry groups of box-splines for evaluation on GPUs. Graph. Model. 93, 14–24 (2017). https://doi.org/10.1016/j.gmod.2017.08.001

    Article  MathSciNet  Google Scholar 

  18. Alim, U.R., Möller, T., Condat, L.: Gradient estimation revitalized. IEEE Trans. Vis. Comput. Graph. 16(6), 1495–1504 (2010). ISSN 1077-2626. https://doi.org/10.1109/TVCG.2010.160

  19. Farin, G.: Curves and surfaces for CAGD: a practical guide, 5th edn. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2001) ISBN 1558607374. https://doi.org/10.1016/B978-1-55860-737-8.X5000-5

  20. Kindlmann, G., Whitaker, R., Tasdizen, T., Möller, T.: Curvature-based transfer functions for direct volume rendering: methods and applications. In: Proceedings of IEEE Visualization 2003, pp. 513–520. (2003). https://doi.org/10.1109/VISUAL.2003.1250414

  21. Marschner, S.R., Lobb, R.J.: An evaluation of reconstruction filters for volume rendering. In: Proceedings Visualization ’94, pp. 100–107. IEEE (1994). https://doi.org/10.1109/VISUAL.1994.346331

  22. Kim, M.: GPU isosurface raycasting of FCC datasets. Graphical Models 75(2), 90–101 (2013). https://doi.org/10.1016/j.gmod.2012.11.001

    Article  MathSciNet  Google Scholar 

  23. Blu, T., Thévenaz, P., Unser, M.: Generalized interpolation: Higher quality at no additional cost. In: Proceedings 1999 International Conference on Image Processing (Cat. 99CH36348), vol. 3, pp. 667–671. Kobe, Japan (1999). IEEE. ISBN 978-0-7803-5467-8. https://doi.org/10.1109/ICIP.1999.817199

  24. Sigg, C., Hadwiger, M.: Fast third-order texture filtering. In: GPU Gems 2, chap. 20, pp. 313–329. Addison-Wesley Professional (2005). ISBN 0-321-33559-7

  25. Conway, J.H., Sloane, N.J.A.: Sphere packings, lattices and groups, vol. 290. Springer New York, NY (1999). https://doi.org/10.1007/978-1-4757-6568-7

Download references

Funding

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2021R1F1A1060215).

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of Seoul, 163 Seoulsiripdaero, Dongdaemun-gu, 02504, Seoul, South Korea

    Hyunjun Kim & Minho Kim

  2. Department of Urban Big Data Convergence, University of Seoul, 163 Seoulsiripdaero, Dongdaemun-gu, 02504, Seoul, South Korea

    Minho Kim

Authors
  1. Hyunjun Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Minho Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Minho Kim.

Ethics declarations

Competing interests

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (pdf 84 KB)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kim, H., Kim, M. Analytic evaluation of the FCC Voronoi-splines. Numer Algor 94, 2005–2030 (2023). https://doi.org/10.1007/s11075-023-01562-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-023-01562-5

Keywords

Search

Navigation