符号付き距離関数のソースを表示

[[Image:Signed distance1.png|right|thumb|固定された円板（上、灰色）とその円板を含むxy平面（青色）上の点との間の符号付き距離の[[グラフ (数学)|グラフ]]（下、赤）]]
[[Image:Signed distance2.png|right|thumb|より複雑な集合（上）とその符号付き距離関数のグラフ（下、赤）]]

'''符号付き距離関数'''（ふごうつききょりかんすう、{{Lang-en|signed distance function}}または{{Lang-en|oriented distance function}}、'''SDF'''）は、与えられた点''x''から[[距離空間]]における集合Ωの[[境界 (位相空間論)|境界]]までの{{仮リンク|垂直距離|en|Orthogonal distance}}である。''x''がΩの[[内部 (位相空間論)|内部]]にあるかどうかによって[[符号 (数学)|符号]]が決まる。この[[関数 (数学)|関数]]は、Ωの内部の点''x''では正の値を持ち、Ωの境界に近づくにつれて値が減少し、符号付き距離関数がゼロになる場所でΩの境界に達し、Ωの外部では負の値を取る<ref>{{cite conference | title=Level set based shape prior segmentation | author1=Chan, T. | author2=Zhu, W. | year=2005 | conference=IEEE Computer Society Conference on Computer Vision and Pattern Recognition | doi=10.1109/CVPR.2005.212 }}</ref>。負の値を内部、正の値を外部とする規約が採用されることもある<ref>{{cite journal | title=Shape modeling with front propagation: a level set approach | author1=Malladi, R. | author2=Sethian, J.A. | author3=Vemuri, B.C. | journal=IEEE Transactions on Pattern Analysis and Machine Intelligence | volume=17 | issue=2 | pages=158–175 | year=1995 | doi = 10.1109/34.368173 |citeseerx = 10.1.1.33.2443| s2cid=9505101 }}</ref>。

== 定義 ==

{{math|Ω}}を[[距離空間]]{{math|''X''}}の[[部分集合]]とし、<math>\partial\Omega</math>をその[[境界 (位相空間論)|境界]]とする。{{math|''X''}}の点{{mvar|x}}と{{mvar|X}}の部分集合<math>\partial\Omega</math>との距離は自然に次のように定義される。
<math display="block"> d(x, \partial \Omega) = \inf_{y \in \partial \Omega}d(x, y),</math>
ここで<math>\inf</math>は[[下限]]を表す。

点{{mvar|x}}から{{mvar|X}}の<math>\Omega</math>までの符号付き距離関数は次のように定義される。
<math display="block">f(x) = \begin{cases}
   d(x, \partial \Omega) & \text{if } x \in \Omega \\
  -d(x, \partial \Omega) & \text{if }\, x \notin \Omega.
\end{cases}</math>

== ユークリッド空間における特性 ==

Ωが[[ユークリッド空間]]'''R'''<sup>''n''</sup>の[[区分的]]に[[滑らかな関数|滑らかな]]境界を持つ部分集合である場合、符号付き距離関数は[[ほとんど至る所]]で微分可能であり、その[[勾配 (ベクトル解析)|勾配]]は[[アイコナール方程式]]を満たす。

<math display="block">|\nabla f|=1</math>

Ωの境界が''k'' ≥ 2で''C''<sup>''k''</sup>（[[滑らかな関数#滑らかさの分類]]を参照）である場合、''d''はΩの境界に十分に近い点で''C''<sup>''k''</sup>である。{{sfn|Gilbarg|Trudinger|1983|loc=Lemma 14.16}} 特に、境界''f'''''上'''においては

<math display="block">\nabla f(x) = N(x)</math>

を満たす。ここで''N''は内向きの[[法ベクトル]]場である。したがって、符号付き距離関数は法ベクトル場の微分可能な拡張である。特に、Ωの境界における符号付き距離関数の[[ヘッセ行列]]は{{仮リンク|形作要素|en|Differential_geometry_of_surfaces#Shape_operator}}を与える。

さらに、Ωの境界に十分に近く''f''がその上で2回連続的に微分可能である領域Γに対し、符号付き距離関数と最も近い境界点の変数変換のヤコビアンには形作用素''W''<sub>''x''</sub>を用いた公式が存在する。特に、''T''(''∂''Ω, ''μ'')がΩの境界から距離''μ''以内の点の集合（つまり、半径''μ''の[[管状近傍]]）であり、''g''がΓ上の[[絶対可積分関数]]である場合、

<math display="block">\int_{T(\partial\Omega,\mu)} g(x)\,dx = \int_{\partial\Omega}\int_{-\mu}^\mu g(u+\lambda N(u))\, \det(I-\lambda W_u) \,d\lambda \,dS_u</math>

が成り立つ。ここで{{math|det}}は[[行列式]]を示し、''dS''<sub>''u''</sub>は[[面積分]]を取ることを示す{{sfn|Gilbarg|Trudinger|1983|loc=Equation (14.98)}}。

== アルゴリズム ==
符号付き距離関数を計算するための[[アルゴリズム]]には、効率的な{{仮リンク|ファストマーチング法|en|fast marching method}}、{{仮リンク|ファストスウィーピング法|en|fast sweeping method}}<ref>Zhao Hongkai. [https://www.ams.org/mcom/2005-74-250/S0025-5718-04-01678-3/S0025-5718-04-01678-3.pdf A fast sweeping method for eikonal equations]. Mathematics of Computation, 2005, 74. Jg., Nr. 250, S. 603-627.</ref> およびより一般的な{{仮リンク|レベルセット法|en|level-set method}}がある。

[[ボクセル]]レンダリング向けには、[[マンハッタン距離|タクシー幾何学]]でSDFを計算するために{{仮リンク|範囲総和表|en|Summed-area table}}を使用する高速アルゴリズムが存在する<ref>{{Cite web |last=Nilsson |first=Tobias |date=2019 |title=Optimization Methods for Direct Volume Rendering on the Client Side Web |url=https://www.diva-portal.org/smash/get/diva2:1330460/FULLTEXT01.pdf |access-date=2022-07-08 |website=Digitala Vetenskapliga Arkivet}}</ref>。

== 応用 ==
[[File:Signed distance field duck.svg|thumb|right|ラスタ画像として保存された符号付き距離場を使用して形状を表現することができる。]]
符号付き距離関数が利用される分野の例としては、{{仮リンク|リアルタイムレンダリング|en|real-time rendering}}<ref name="̈llerHaines2018">{{cite book|author1=Tomas Akenine-Möller|author2=Eric Haines|author3=Naty Hoffman|title=Real-Time Rendering, Fourth Edition|url=https://books.google.com/books?id=0g1mDwAAQBAJ|date=6 August 2018|publisher=CRC Press|isbn=978-1-351-81615-1}}</ref>、{{仮リンク|SDFレイマーチング|en|Ray marching#Sphere_tracing}}、[[コンピュータビジョン]]などがある<ref>{{Cite book|last1=Perera|first1=S.|last2=Barnes|first2=N.|last3=He|first3=X.|last4=Izadi|first4=S.|last5=Kohli|first5=P.|last6=Glocker|first6=B.|title=2015 IEEE Winter Conference on Applications of Computer Vision |chapter=Motion Segmentation of Truncated Signed Distance Function Based Volumetric Surfaces |date=January 2015|pages=1046–1053|doi=10.1109/WACV.2015.144|isbn=978-1-4799-6683-7|s2cid=16811314}}</ref><ref>{{Cite book|last1=Izadi|first1=Shahram|last2=Kim|first2=David|last3=Hilliges|first3=Otmar|last4=Molyneaux|first4=David|last5=Newcombe|first5=Richard|last6=Kohli|first6=Pushmeet|last7=Shotton|first7=Jamie|last8=Hodges|first8=Steve|last9=Freeman|first9=Dustin|title=Proceedings of the 24th annual ACM symposium on User interface software and technology |chapter=KinectFusion |date=2011|series=UIST '11|location=New York, NY, USA|publisher=ACM|pages=559–568|doi=10.1145/2047196.2047270|isbn=9781450307161|s2cid=3345516}}</ref>。

SDFは2000年代半ばからレイマーチングの実装においてリアルタイムレンダリングにおけるオブジェクトのジオメトリを記述するために使用され始めた。2007年には[[Valve Corporation|Valve]]が、SDFを使用して大きなピクセルサイズ（または[[ピクセル密度#名前付きピクセル密度|高DPI]]）の[[滑らかなフォント]]を[[Graphics Processing Unit|GPU]]アクセラレーションでレンダリングしている<ref>{{cite book | doi = 10.1145/1281500.1281665 | pages=9–18 | date=2007 | first=Chris | last=Green| title=ACM SIGGRAPH 2007 courses | chapter=Improved alpha-tested magnification for vector textures and special effects | isbn=9781450318235 | citeseerx=10.1.1.170.9418 | s2cid=7479538 }}</ref>。Valveの手法は（連続的な）ベクタ空間での問題を解く計算複雑性を避けるためにラスタ空間で実行されるため完璧ではなく、レンダリングされたテキストは角が丸まってしまうことが多い。2014年には、[[:en:Behdad Esfahbod]]によって改良された手法が発表された。BehdadのGLyphyはフォントの[[ベジエ曲線]]をスプライン曲線で近似し、グリッドベースの[[離散化]]手法（遠すぎる点をカリングする）によってリアルタイムで実行する<ref>{{cite AV media|author= Behdad Esfahbod | url-status = live| archive-url = https://ghostarchive.org/varchive/youtube/20211211/7tHv6mcIIeo| archive-date = 2021-12-11| url = https://www.youtube.com/watch?v=7tHv6mcIIeo| title = GLyphy: high-quality glyph rendering using OpenGL ES2 shaders [linux.conf.au 2014] | website=[[YouTube]]}}{{cbignore}} [https://github.com/behdad/glyphy Source Code]</ref>。

複数のオブジェクトをレンダリングする際のピクセルの侵入エラーを最小化するための[[損失関数]]としてSDFの修正版が使われている<ref>{{cite arXiv|last1=Jiang|first1=Wen|last2=Kolotouros|first2=Nikos|last3=Pavlakos|first3=Georgios|last4=Zhou|first4=Xiaowei|last5=Daniilidis|first5=Kostas|date=2020-06-15|title=Coherent Reconstruction of Multiple Humans from a Single Image|class=cs.CV|eprint=2006.08586}}</ref>。オブジェクトに属さないピクセルに対して、それがレンダリング時にオブジェクトの外側にある場合はペナルティは課さず、内部にある場合はその距離に比例した正の値を課すというものである。

<math display="block">f(x) = \begin{cases}
0                    & \text{if }\, x \in \Omega^c\\
d(x, \partial\Omega) & \text{if }\, x \in \Omega
\end{cases}</math>

2020年には、[[FLOSS|FOSS]]のゲームエンジン[[Godot (ゲームエンジン)|Godot 4.0]]がSDFベースのリアルタイム[[グローバルイルミネーション|GI]]（SDFGI）を実装した<ref name="godot4">{{cite web |last1=Engine |first1=Godot |title=Godot 4.0 gets SDF based real-time global illumination |url=https://godotengine.org/article/godot-40-gets-sdf-based-real-time-global-illumination/ |website=Godot Engine |language=en |accessdate=2024-05-28}}</ref>。既存のボクセルベースのGIよりパフォーマンスは劣るものの<ref>{{cite web|author=Godot Engine|title=Signed distance field global illumination (SDFGI)|url=https://docs.godotengine.org/en/stable/tutorials/3d/global_illumination/using_sdfgi.html|accessdate=2024-05-29}}</ref>、広い空間に適用可能であるため[[オープンワールド]]ゲームの開発に用いることができる<ref name="godot4" />。

2023年には、すべてのUI要素をGPUを使用して描画する「GPUI」UIフレームワークがリリースされ、120 fpsでレンダリングを行う''Zed''コードエディタを開発したと発表された。このフレームワークは多くの部分でSDFを使用し、Inigo QuilezによるSDF向け幾何学図形プリミティブ、Evan Wallace（[[Figma (ソフトウェア)|Figma]]の共同創設者）のSDFにおける近似[[ガウシアンぼかし]]、および丸みを帯びた長方形のSDFを利用している<ref>{{cite web |last1=Scandurra |first1=Antonio |title=Leveraging Rust and the GPU to render user interfaces at 120 FPS - Zed Blog |url=https://zed.dev/blog/videogame |website=Zed |date=7 March 2023|accessdate=2024-05-28}}</ref>。

== 脚注 ==

{{reflist}}

== 関連項目 ==

* [[距離関数]]
* {{仮リンク|レベルセット法|en|Level-set method}}
* [[アイコナール方程式]]
* [[平行曲線]]
* {{仮リンク|符号付き弧長|en|Signed arc length}}
* {{仮リンク|符号付き面積|en|Signed area}}
* [[符号付き測度]]
* {{仮リンク|符号付き体積|en|Signed volume}}

{{DEFAULTSORT:ふこうつききよりかんすう}}

[[Category:応用数学]]
[[Category:距離]]
[[Category:数学に関する記事]]