Abstract

The Monte Carlo (MC) method is a popular approach to modeling photon propagation inside general turbid media, such as human tissue. Progress had been made in the past year with the independent proposals of two mesh-based Monte Carlo methods employing ray-tracing techniques. Both methods have shown improvements in accuracy and efficiency in modeling complex domains. A recent paper by Shen and Wang [Biomed. Opt. Express 2, 44 (2011)] reported preliminary results towards the cross-validation of the two mesh-based MC algorithms and software implementations, showing a 3–6 fold speed difference between the two software packages. In this comment, we share our views on unbiased software comparisons and discuss additional issues such as the use of pre-computed data, interpolation strategies, impact of compiler settings, use of Russian roulette, memory cost and potential pitfalls in measuring algorithm performance. Despite key differences between the two algorithms in handling of non-tetrahedral meshes, we found that they share similar structure and performance for tetrahedral meshes. A significant fraction of the observed speed differences in the mentioned article was the result of inconsistent use of compilers and libraries.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol. 55(4), 947–962 (2010).
    [CrossRef] [PubMed]
  2. Q. Fang, “Mesh-based Monte Carlo method using fast ray-tracing in Plücker coordinates,” Biomed. Opt. Express 1(1), 165–175 (2010).
    [CrossRef] [PubMed]
  3. E. Margallo-Balbás and P. J. French, “Shape based Monte Carlo code for light transport in complex heterogeneous Tissues,” Opt. Express 15(21), 14086–14098 (2007).
    [CrossRef] [PubMed]
  4. C. Wächter, “Quasi-Monte Carlo light transport simulation by efficient ray tracing,” Ph.D. dissertation (Ulm University, 2007)
  5. N. Ren, J. Liang, X. Qu, J. Li, B. Lu, and J. Tian, “GPU-based Monte Carlo simulation for light propagation in complex heterogeneous tissues,” Opt. Express 18(7), 6811–6823 (2010).
    [CrossRef] [PubMed]
  6. I. Wald, “Realtime ray tracing and interactive global illumination,” Ph.D. dissertation (Saarland University, 2004).
  7. D. Badouel, “An efficient ray-polygon intersection,” Graphics Gems, S.A. Glassner, ed. (Academic Press Professional, 1990), pp. 390–393.
  8. N. Platis and T. Theoharis, “Fast ray-tetrahedron intersection using Plücker coordinates,” J. Graph. Tools 8(4), 37–48 (2003).
  9. M. Shevtsov, A. Soupikov, and A. Kapustin, “Ray-triangle intersection algorithm for modern CPU architectures,” in Proceedings of GraphiCon 2007, (2007), pp. 33–39.
  10. H. Shen and G. Wang, “TIM-OS Project Site,” https://sites.google.com/a/imaging.sbes.vt.edu/tim-os/ .
  11. Q. Fang, “Mesh-based Monte Carlo—the software,” http://mcx.sourceforge.net/mmc/ .
  12. H. Shen and G. Wang, “A study on tetrahedron-based inhomogeneous Monte Carlo optical simulation,” Biomed. Opt. Express 2(1), 44–57 (2011).
    [CrossRef] [PubMed]
  13. J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Vis. Comput. Graph. 16(3), 434–438 (2010).
    [CrossRef] [PubMed]
  14. K. H. Huebner, The Finite Element Method for Engineers (Wiley, 2001), Section 10.6.4.
  15. Intel Knowledge Base, “New fast basic random number generator SFMT19937 in Intel MKL,” (2010), http://software.intel.com/en-us/articles/new-fast-basic-random-number-generator-sfmt19937-in-intel-mkl/ .

2011

2010

J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Vis. Comput. Graph. 16(3), 434–438 (2010).
[CrossRef] [PubMed]

H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol. 55(4), 947–962 (2010).
[CrossRef] [PubMed]

Q. Fang, “Mesh-based Monte Carlo method using fast ray-tracing in Plücker coordinates,” Biomed. Opt. Express 1(1), 165–175 (2010).
[CrossRef] [PubMed]

N. Ren, J. Liang, X. Qu, J. Li, B. Lu, and J. Tian, “GPU-based Monte Carlo simulation for light propagation in complex heterogeneous tissues,” Opt. Express 18(7), 6811–6823 (2010).
[CrossRef] [PubMed]

2007

2003

N. Platis and T. Theoharis, “Fast ray-tetrahedron intersection using Plücker coordinates,” J. Graph. Tools 8(4), 37–48 (2003).

Fang, Q.

French, P. J.

Havel, J.

J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Vis. Comput. Graph. 16(3), 434–438 (2010).
[CrossRef] [PubMed]

Herout, A.

J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Vis. Comput. Graph. 16(3), 434–438 (2010).
[CrossRef] [PubMed]

Li, J.

Liang, J.

Lu, B.

Margallo-Balbás, E.

Platis, N.

N. Platis and T. Theoharis, “Fast ray-tetrahedron intersection using Plücker coordinates,” J. Graph. Tools 8(4), 37–48 (2003).

Qu, X.

Ren, N.

Shen, H.

H. Shen and G. Wang, “A study on tetrahedron-based inhomogeneous Monte Carlo optical simulation,” Biomed. Opt. Express 2(1), 44–57 (2011).
[CrossRef] [PubMed]

H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol. 55(4), 947–962 (2010).
[CrossRef] [PubMed]

Theoharis, T.

N. Platis and T. Theoharis, “Fast ray-tetrahedron intersection using Plücker coordinates,” J. Graph. Tools 8(4), 37–48 (2003).

Tian, J.

Wang, G.

H. Shen and G. Wang, “A study on tetrahedron-based inhomogeneous Monte Carlo optical simulation,” Biomed. Opt. Express 2(1), 44–57 (2011).
[CrossRef] [PubMed]

H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol. 55(4), 947–962 (2010).
[CrossRef] [PubMed]

Biomed. Opt. Express

IEEE Trans. Vis. Comput. Graph.

J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Vis. Comput. Graph. 16(3), 434–438 (2010).
[CrossRef] [PubMed]

J. Graph. Tools

N. Platis and T. Theoharis, “Fast ray-tetrahedron intersection using Plücker coordinates,” J. Graph. Tools 8(4), 37–48 (2003).

Opt. Express

Phys. Med. Biol.

H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol. 55(4), 947–962 (2010).
[CrossRef] [PubMed]

Other

C. Wächter, “Quasi-Monte Carlo light transport simulation by efficient ray tracing,” Ph.D. dissertation (Ulm University, 2007)

I. Wald, “Realtime ray tracing and interactive global illumination,” Ph.D. dissertation (Saarland University, 2004).

D. Badouel, “An efficient ray-polygon intersection,” Graphics Gems, S.A. Glassner, ed. (Academic Press Professional, 1990), pp. 390–393.

M. Shevtsov, A. Soupikov, and A. Kapustin, “Ray-triangle intersection algorithm for modern CPU architectures,” in Proceedings of GraphiCon 2007, (2007), pp. 33–39.

H. Shen and G. Wang, “TIM-OS Project Site,” https://sites.google.com/a/imaging.sbes.vt.edu/tim-os/ .

Q. Fang, “Mesh-based Monte Carlo—the software,” http://mcx.sourceforge.net/mmc/ .

K. H. Huebner, The Finite Element Method for Engineers (Wiley, 2001), Section 10.6.4.

Intel Knowledge Base, “New fast basic random number generator SFMT19937 in Intel MKL,” (2010), http://software.intel.com/en-us/articles/new-fast-basic-random-number-generator-sfmt19937-in-intel-mkl/ .

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (1)

Fig. 1
Fig. 1

Absolute and relative errors of the solutions using different interpolation strategies. Here we define e mmc = y mmc - y truth and e timos = y timos - y truth.

Tables (2)

Tables Icon

Table 1 The Pseudo-Code for a Ray-Tetrahedron Intersection Test using Shevtsov’s (Plücker-Based) Methoda

Tables Icon

Table 2 Comparison of Run-Times for Various mmc and timos Builds with Different Compilers and Optimizations

Equations (1)

Equations on this page are rendered with MathJax. Learn more.

y truth = ( i 1 / 2 ) Δ x ( i + 1 / 2 ) Δ x f ( x ) d x = ln ( ( 2 i + 1 ) / ( 2 i 1 ) ) y mmc = ( i 1 ) Δ x ( i + 1 ) Δ x f ( x ) ϕ i ( x ) d x = ( i + 1 ) ln ( i + 1 ) + ( i 1 ) ln ( i 1 ) 2 i ln ( i ) y timos = 1 2 ( ( i 1 ) Δ x i Δ x f ( x ) d x + i Δ x ( i + 1 ) Δ x f ( x ) d x ) = 1 2 ln ( ( i + 1 ) / ( i 1 ) )

Metrics