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

A Partial Differential Equation Obstacle Problem for the Level Set Approach to Visibility

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

In this article we consider the problem of finding the visibility set from a given point when the obstacles are represented as the level set of a given function. Although the visibility set can be computed efficiently by ray tracing, there are advantages to using a level set representation for the obstacles, and to characterizing the solution using a partial differential equation (PDE). A nonlocal PDE formulation was proposed in Tsai et al. (J Comput Phys 199(1):260–290. https://doi.org/10.1016/j.jcp.2004.02.015, 2004): in this article we propose a simpler PDE formulation, involving a nonlinear obstacle problem. We present a simple numerical scheme and show its convergence using the framework of Barles and Souganidis. Numerical examples in both two and three dimensions are presented.

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

Similar content being viewed by others

References

  1. Agarwal, P.K., Sharir, M.: Ray shooting amidst convex polygons in 2d. J. Algorithms 21(3), 508–519 (1996). https://doi.org/10.1006/jagm.1996.0056

    Article  MathSciNet  MATH  Google Scholar 

  2. Agarwal, P.K., Sharir, M.: Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions. SIAM J. Comput. 25(1), 100–116 (1996). https://doi.org/10.1137/S0097539793244368

    Article  MathSciNet  MATH  Google Scholar 

  3. Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Anal. 4(3), 271–283 (1991)

    Article  MathSciNet  Google Scholar 

  4. Cheng, L.T., Tsai, Y.H.: Visibility optimization using variational approaches. Commun. Math. Sci. 3(3), 425–451 (2005)

    Article  MathSciNet  Google Scholar 

  5. Coorg, S., Teller, S.: Real-time occlusion culling for models with large occluders. In: Proceedings of the 1997 Symposium on Interactive 3D Graphics, I3D ’97, pp. 83–ff. ACM, New York (1997). https://doi.org/10.1145/253284.253312

  6. Crandall, M.G., Ishii, H., Lions, P.L.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. (N.S.) 27(1), 1–67 (1992)

    Article  MathSciNet  Google Scholar 

  7. Durand, F., Drettakis, G., Thollot, J., Puech, C.: Conservative visibility preprocessing using extended projections. In: Proceedings of SIGGRAPH 2000. Held in New Orleans, Louisiana

  8. Hertzmann, A., Zorin, D.: Illustrating smooth surfaces. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’00), pp. 517–526. ACM Press/Addison-Wesley Publishing Co., USA (2000). https://doi.org/10.1145/344779.345074

  9. Kao, C.Y., Tsai, R.: Properties of a level set algorithm for the visibility problems. J. Sci. Comput. 35(2), 170–191 (2008). https://doi.org/10.1007/s10915-008-9197-5

    Article  MathSciNet  MATH  Google Scholar 

  10. Koike, S.: A Beginner’s Guide to the Theory of Viscosity Solutions, MSJ Memoirs, vol. 13. Mathematical Society of Japan, Tokyo (2004)

    MATH  Google Scholar 

  11. Landa, Y., Tsai, R., Cheng, L.T.: Visibility of point clouds and mapping of unknown environments. In: Blanc-Talon, J., Philips, W., Popescu, D., Scheunders, P. (eds.) Advanced Concepts for Intelligent Vision Systems, pp. 1014–1025. Springer, Berlin (2006)

    Chapter  Google Scholar 

  12. Ly, L., Tsai, Y.R.: Autonomous exploration, reconstruction, and surveillance of 3d environments aided by deep learning. In: CoRR. arXiv:1809.06025 (2018)

  13. Oberman, A.M.: Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton–Jacobi equations and free boundary problems. SIAM J. Numer. Anal. 44(2), 879–895 (2006)

    Article  MathSciNet  Google Scholar 

  14. Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79(1), 12–49 (1988)

    Article  MathSciNet  Google Scholar 

  15. Sethian, J.A.: Level set methods and fast marching methods. Cambridge Monographs on Applied and Computational Mathematics, vol. 3, 2nd edn. In: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, Cambridge (1999)

  16. Sethian, J.A., Adalsteinsson, D.: An overview of level set methods for etching, deposition, and lithography development. IEEE Trans. Semicond. Manuf. 10(1), 167–184 (1997). https://doi.org/10.1109/66.554505

    Article  Google Scholar 

  17. Tsai, Y.H.R., Cheng, L.T., Osher, S., Burchard, P., Sapiro, G.: Visibility and its dynamics in a pde based implicit framework. J. Comput. Phys. 199(1), 260–290 (2004). https://doi.org/10.1016/j.jcp.2004.02.015

    Article  MathSciNet  MATH  Google Scholar 

  18. Valente, L., Tsai, Y.H.R., Soatto, S.: Information-seeking control under visibility-based uncertainty. J. Math. Imaging Vis. 48(2), 339–358 (2014). https://doi.org/10.1007/s10851-013-0423-x

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The second author thanks the hospitality of the Mathematics and Statistics department of McGill University during its visit where the work for this paper was carried out.

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street West, Montreal, Quebec, H3A 0G4, Canada

    Adam Oberman

  2. Department of Mathematics, University of Michigan, 530 Church St., Ann Arbor, MI, 48105, USA

    Tiago Salvador

Authors
  1. Adam Oberman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tiago Salvador
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tiago Salvador.

Additional information

Publisher's Note

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

This material is based upon work supported by the Air Force Office of Scientific Research under Award Number FA9550-18-1-0167.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Oberman, A., Salvador, T. A Partial Differential Equation Obstacle Problem for the Level Set Approach to Visibility. J Sci Comput 82, 14 (2020). https://doi.org/10.1007/s10915-019-01106-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-019-01106-x

Keywords

Mathematics Subject Classification

Search

Navigation