Operations on Signed Distance Functions

Keywords: Singed Distance Functions, Sphere Tracing, Computer Graphics

Abstract

We present a theoretical overview of signed distance functions and analyze how this representation changes when applying an offset transformation. First, we analyze the properties of signed distance and the sets they describe.

Second, we introduce our main theorem regarding the distance to an offset set in (X,||.||) strictly normed Banach spaces. An offset set of D in X is the set of points equidistant to D. We show when such a set can be represented by f(x)-c=0, where c denotes the radius of the offset. Finally, we explain these results for applications that offset signed distance functions.

References

Aaltonen, Sebastian. GPU-based clay simulation and ray-tracing tech in Claybook. San Francisco, CA, March 2018. Game Developers Conference.

Angles, Baptiste, Tarini, Marco, Wyvill, Brian, Barthe, Loic, and Tagliasacchi, Andrea. Sketch-based implicit blending. ACM Trans. Graph., 36(6):181:1--181:13, November 2017. DOI: 10.1145/3130800.3130825.

Bernhardt, Adrien, Barthe, Loic, Cani, Marie-Paule, and Wyvill, Brian. Implicit blending revisited. In Computer Graphics Forum, volume~29, pages 367--375. Wiley Online Library, 2010.

Bloomenthal, Jules and Wyvill, Brian, editors. Introduction to Implicit Surfaces. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997.

Dyer, R.H. and Edmunds, D.E. From Real to Complex Analysis. Springer Undergraduate Mathematics Series. Springer International Publishing, 2014.

Evans, Alex. Learning from failure: a survey of promising, unconventional and mostly abandoned renderers for ‘dreams ps4’, a geometrically dense, painterly ugc game. In Advances in Real-Time Rendering in Games. MediaMolecule, SIGGRAPH, 2015.

Gomes, Abel, Voiculescu, Irina, Jorge, Joaquim, Wyvill, Brian, and Galbraith, Callum. Implicit Curves and Surfaces: Mathematics, Data Structures and Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2009.

Gourmel, Olivier, Pajot, Anthony, Paulin, Mathias, Barthe, Loic, and Poulin, Pierre. {Fitted BVH for Fast Raytracing of Metaballs}. Computer Graphics Forum, 2010. DOI: 10.1111/j.1467-8659.2009.01597.x.

Hansen, C., Hijazi, Y., Hagen, H., Knoll, A., and Wald, I. Interactive ray tracing of arbitrary implicits with simd interval arithmetic. In IEEE/ EG Symposium on Interactive Ray Tracing 2007(RT), volume~00, pages 11-18, 09 2007. DOI: 10.1109/RT.2007.4342585.

Hart, John C. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer, 12:527--545, 1994.

Hutchinson, John E. Introduction to Mathematical Analysis. Australian National University Lecture Notes, 1994.

Malladi, Ravikanth, Sethian, James A., and Vemuri, Baba C. Shape modeling with front propagation: A level set approach. IEEE Trans. Pattern Anal. Mach. Intell., 17(2):158--175, February 1995. DOI: 10.1109/34.368173.

Pasko, A., Adzhiev, V., Sourin, A., and Savchenko, V. Function representation in geometric modeling: concepts, implementation and applications.

The Visual Computer, 11(8):429--446, Aug 1995. DOI: 10.1007/BF02464333.

Ricci, A. A Constructive Geometry for Computer Graphics. The Computer Journal, 16(2):157--160, May 1973. DOI: http://dx.doi.org/10.1093/comjnl/16.2.157.

Shapiro, Vadim. Semi-analytic geometry with r-functions. Acta Numerica, 16:239–303, 2007. DOI: 10.1017/S096249290631001X.

Sherstyuk, Andrei. Fast ray tracing of implicit surfaces. Computer Graphics Forum, 18(2):139-147. DOI: 10.1111/1467-8659.00364.

Szécsi, László and Illés, Dávid. Real-time metaball ray casting with fragment lists.. In Andújar, Carlos and Puppo, Enrico, editors, Eurographics (Short Papers), pages 93-96. Eurographics Association, 2012.

Wright, Daniel. Dynamic occlusion with signed distance fields. In Advances in Real-Time Rendering in Games. Epic Games (Unreal Engine), SIGGRAPH, 2015.

Wyvill, Brian, Guy, Andrew, and Galin, Eric. Extending the CSG Tree. Warping, Blending and Boolean Operations in an Implicit Surface Modeling System. Computer Graphics Forum, 1999. DOI: 10.1111/1467-8659.00365.

Published
2019-05-21
How to Cite
Bálint, C., Valasek, G., & Gergó, L. (2019). Operations on Signed Distance Functions. Acta Cybernetica, 24(1), 17-28. https://doi.org/10.14232/actacyb.24.1.2019.3
Section
Special Issue of the 11th Conference of PhD Students in Computer Science