Syoyo Fujita's Blog

raytracing monte carlo

Category: reference

Etymology of “normal”

surface_normal.png
(image from Wikipedia)

「法線ベクトルとは、面に垂直な方向を指すベクトルである」

よくある 3D CG の教科書に見られる、法線(normal)に間する説明の記述ですね.

でも、「法線」の「法」ってナニ?
normal って「普通」という意味なんだから、「普通のベクトル」じゃないの?なぜ CG だとこれが「法線」というという意味になるの?

CG を習い初めたひとにとっては, こんな疑問をいだきつつも、「まあこのギョーカイではそんなことになっているんだな」と妙に理解したことにしてしまって今に至るひとが多いのではないでしょうか?

私自身もまだ右も左も分からぬレンダラ一年生だったとき, なぜ normal が面に垂直なベクトルを意味し、そしてそれが法線と訳されるのか疑問でした.

そこで、ちょうど GI 本を執筆するに当たっていろいろ資料や語彙の由来などについて調査していたので、normal = 法線の謎も追ってみましたところ、結構おもしろい語源の由来だったので取り上げてみることにします.

normal の語源

まずは辞典で normal の意味を調べてみます.

http://dictionary.reference.com/browse/normal

によれば、normal とは、「通常」、「標準」、などに加え、数学においては「直角、垂直」という意味もあります. つまり normal にはそもそも垂直という意味も存在していることが分かりました.

さて、normal の語源はラテン語の norm-, normalis であり、それは carpenter’s square に由来するものとかかれています.

carpenter’s square(大工さんの四角形)って何でしょう?
じつは carpenter’s square とは直角定規のことです.
↓これです.

carpenterssquare.jpg
(image from wikipedia)

というわけで、もともとは normal は直角(垂直)というような意味だったような気がしてきます.

さらに、norma-, normalis あたりの言葉の語源を調べるたところ、以下の語源サイトがヒット.

The etymological background of the term, “normal”

http://www.wordinfo.info/words/index/info/view_unit/4403/?letter=N&spage=4

そしてついに normal の語源の由来にたどり着きます.

The basic sense of the noun norm is “an authoritative standard or model”. This is derived from the Latin norma which means “rule or pattern” as well as “a carpenter’s square”, because a square provides a standard or rule which ensures that a carpenter can regularly reproduce corners and edges that are straight and that form right angles.

norm の基本的な意味は、「信ずるべき標準やモデル」である.
norm はラテン語の norma に由来し、これは「ルールや規則」そしてまた「carpenter’s square(直角定規)」を意味する.
なぜなら四角形は、直線でありまた垂直な角をもつ「かど」や辺を規則的に作り出すことを可能にする標準やルールを大工に与えるからである.
(ちなみに、square = 直角定規なのは、直角定規があれば四角形を描画できることから)

そして、

norm-, normo- +

Latin: rule, pattern; normalis, “right angled, made according to a carpenter’s square”; then, “conforming to common standards, usual” came into English usage in about 1828

normalis: 垂直で、直角三角形により作られたもの. 転じて標準を成す、通常.

まとめ

というわけで、normal(ラテン語の norma, normalis) というのは元々は大工の垂直定規を意味しており、それがルールや規則という意味となり、転じて「通常」(規則に従っている)という意味になったわけでした.

normal は、CG で使う「法線」という意味のほうが、より語源に近かったわけですね.

あ、しかし結局日本語における法線の「法」がなにを意味するのかはまだ調べきってません. ただ、英語の normal の語源における意味の一つである rule に由来して「法」という字が当たっているのかなと推測しています.

おまけ

垂直 -> 通常

に限らず、数学的な概念から転じて意味を作り出した例は他にもあります.

回転 -> やすらぎを与える
黄金長方形(黄金比) -> なんだか無限にパワーがわいてくるぞ!
素数 -> 数えると落ち着く
じゃんけん -> うおおおおおおおおお!ガラスの破片のシャワーを浴びてもガラスが当たらないほどの強運っ!

Recently published rendering related books

As Shinji posted some recently publised rendering books,
I’d like to make up for the list of recently published rendering related books which could be benefitical for renderer writer.

Monte Carlo and Quasi-Monte Carlo Methods 2006

http://www.amazon.com/Monte-Carlo-Quasi-Monte-Methods-2006/dp/3540744959

mcqmc2006

A lot of rank-1 lattice method in this volume!.

You shouldn’t miss to read this volume if you are MC-based renderer writer since there’s quite interesting methods described in this volume, for example SFMT: SIMD-Friendly Mersenne Twister which could accelerate your MC renderer.

Geometric Algebra for Computer Graphics

http://www.amazon.com/Geometric-Algebra-Computer-Graphics-Vince/dp/1846289963

GAforGraphics

This is a easy introduction of geometric algebra.
I think this book is a good introduction for beginners who are intested in GA.

Geometric Algebra for Computer Science:
An Object-Oriented Approach to Geometry (The Morgan Kaufmann Series in Computer Graphics)

http://www.amazon.com/Geometric-Algebra-Computer-Science-Object-Oriented/dp/0123694655

GAforCS

Another GA book for graphics guys.
It describes ray tracing in GA space, which is the same one published in 2003.
I think GA could be used for efficient beam-based real time raytracing.

—-

And more,


Pactical introduction to how to write Global Illumination renderer with Python or Haskell:

From ray tracing to MLT and beyond
(by Syoyo, not yet published 🙂 )

I’ll definitely write this one, but who knows when will.

OoO 第二回開催予定

SIGGRAPH 2008 論文も公開され始めたようなので、
OoO 第二回を GW 空けの 5/10 あたりで開催したいと考えています.
現在日程を調整中.

Bee さんが SIGGRAPH に通ったようですね.
燃え尽きるほどヒーーート!
グラフィックスの王道であるレンダリング(光輸送)で日本人が
通ったのは、いったい何年ぶりでしょうか?(いや、ホントに. 十何年ぶり?)

他には, Parallel Poisson Disk Sampling とか興味深いですね.
自己相似性は無いものの、多次元でのサンプリング点が生成できるところがグッド.

GW 空けには Parallel Poisson Disk Sampling or
A Meshless Hierarchical Representation for Light Transport を
実装できて OoO で発表できるといいなと考えています.
もしくは今実装中の A first-order analysis of lighting, shading, and shadows の visibility gradient かな.

Ray-Triangle intersection using Affine arithmetic

Ray-Triangle intersection using Affine arithmetic
Uchimura HAJIME, Kashiwagi MASAHIDE, and Kashiwagi KEIICHIRO
http://nikq.nothing.sh/backlog/junkbox/univ/tecrep.pdf

In these days, rendering algorithms are getting complex, and target models are getting dense.Those dense triangles cause precision trouble.
so I used Affine-arithmetic(AA) as a precision-proving tool for intersection calculation.

Just for those who can read Japanese 🙂
(Or if you are intersted in, let me know. I or the author will try to illustrate it in English)

I am very interested in this problem, i.e. how to do numerically robust ray-trianble intersection computation.
I think many people in production rendering and almost all practical raytracer writer are suffering from this precision problem.

Hmm. I’d like to comment it. I think it’d be much better to use gappa to formally verify their result.

Quasi-Monte Carlo light transport simulation by efficient ray tracing

(from ompf.org/forum)

Quite interesting and fresh thesis was published, from the author of BIH.

Quasi-Monte Carlo light transport simulation by efficient ray tracing
http://vts.uni-ulm.de/query/longview.meta.asp?document_id=6265

I didn’t read it yet, I have to read it soon.

# but nowdays, there are a lot of papers I have to read.
# 1 paper per day is absolutely not enough. Dozens of papers per day may be needed to catch up the trend in the literature.

Programming Graphics Processors Functionally

[En]
Programming Graphics Processors Functionally
http://conal.net/papers/Vertigo/

Haskell DSL based approach for shaders. Quite interesting!

[Ja]

… 唖然!何だよオレが関数型でシェーダ言語いいんじゃね、ちょっとやってみっかと思った矢先、
3 年も前にもうやられてるじゃねーか!

まあそんな程度の(他人もすぐ思い浮かぶような)浅はかなアイデアしか浮かばない薄っぺらな自分だったってことですね…

「27 年間の結果が、これですよ。うすっぺらなんだよ、syoyo」

…世界って広いわ…

RT07 papers on the web.

http://kesen.huang.googlepages.com/rt2007Papers.htm

[En]

Ke-Sen Huan kindly organizes RT07 papers list.

I granted some paper, and found it’s quite interesting.
There seems a lot of advances compared to RT06.

[Ja]

毎度おなじみ、Ke-Sen Huan 氏による RT07 の論文リストページです。
いくつか公開されているものをちらりと見てみましたが、面白そうな論文ばっかりです。

これは SBR07 を開くしかありませんね。

今年は SBR の本場(?)ということでサンディエゴで開催できないかと企画していたのでアナウンスが
遅れていましたが、まぁなんだかんだで企画倒れになってやはり日本で開催ということにしたいと思います。
続報は寝て待て!?

Load to MUDA. SIMD code generation, domain specific language, automatic optimization, functional programming, etc.

[En]

To realize my MUDA lanuage idea[1], I started research on portable SIMD code generation.
And I found a lot of and good previous work about it, and also find a keyoword to express such a research topic in that field.

The keyword to express MUDA is Domain Specific Language.

Domain Specific Language(DSL, from wikipedia)

DSL is a problem specific langauge. It isn’t a generic language, but useful for some problem to express it.
Usually DSL is implemented with LEX/YACC, ANTLR and functional programming langauges such like Haskell or Ocaml.

Here is some lists of previous works of SIMD code generation with DSL(or dynamic code generation) I found.

A Domain-Specific Language for the Generation of Optimized SIMD-Parallel Assembly Code
Christopher Kumar Anand, Wolfram Kahl.
SQRL Report No. 43.
http://www.cas.mcmaster.ca/~anand/papers/preprints.html

They reported how optimized tanh(hyperbolic tangent) function can be mapped to native codes
with DSL enbedded in Haskell.
They doesn’t uses SSE, but the idea can be valuable to code MUDA.

Page linked also contains a lot of interesting papers.

Efficient Utilization of SIMD Extensions
Franchetti, F. Kral, S. Lorenz, J. Ueberhuber, C.W.
Proceedings of the IEEE Special Issue on “Program Generation, Optimization, and Adaptation,” Vol. 93, No. 2, 2005, pages 409-425.
http://www.ece.cmu.edu/~franzf/publications.htm

This paper is a summary/survey paper on SIMD code geneation and automatic optimzation.
It includes a lot of pointers for this research topic, thus it’s a good paper to start with doing reaserch on
SIMD code genration and automatic optimzation.

CorePy
http://www.corepy.org/
CorePy doesn’t support SSE, but their design are useful for me to code MUDA language.
Writing efficient SIMD code with script language seems good.

FFTW
http://www.fftw.org/

Instead of statically optimized code, FFTW uses their FFT language and compiler for dynamic code generation and automatic optimizer for high perfomance FFT computation on various platform.
Performance of produced codes are comparable or overcomes vendor tuned FFT code.
Their FFT language and compiler is implemented with Ocaml.

Their technique is also published as below(see FFTW’s site).
Matteo Frigo and Steven G. Johnson, “The Design and Implementation of FFTW3,” Proceedings of the IEEE 93 (2), 216–231 (2005). Invited paper, Special Issue on Program Generation, Optimization, and Platform Adaptation.

SAC(Single Assignment C)
http://www.sac-home.org

SaC is an array programming language predominantly suited for application areas such as numerically intensive applications and signal processing. Its distinctive feature is that it combines high-level program specifications with runtime efficiency similar to that of hand-optimized low-level specifications

SAC provides their prerelease compiler for array based application and hosts a lot of research papers.

Conclusions at present

Playing with FFTW’s genfft might be a good point to start with
learning SIMD code generation technique.

And more, common language used in this research topic seem functional programming(FP) language, especially Haskell and Ocaml.
It would be a good time for me to learn FP language.
thus I decided, in front of playing with FFTW, I must learn about FP language. Ocaml for first, then Haskell.
(Because FFTW’s genfft uses Ocaml 😉 )

[Ja]

詳細は英語の方を見てもらうとして、まとめますと以下の通り。

– FFTW すげぇ。中身は結構 cutting edge なことやっているのね。FFTW の code は必読だ。
– MUDA に限らず自分の頭の中にあるアイデアを実現するには、やっぱオレ様言語(DSL)を作るのがよさそうだ。
一番費用対コストが高いのと、トータルでみたときの coding 時間の節約になる、気がする。
今まで何でもなるべく C で書いてきたが、実はいままでとても効率が悪いことをやっていたのではなかっただろうか。
– とにもかくにも Ocaml や Haskell を習う必要を感じた。論文のいたるところで関数型言語が出てくるし、
FFTW の FFT compiler が ocaml だし。
– というわけでまずは関数型言語の習得から…

[1] Idea: MUDA, MUltiple Data Accelerator language for high performance computing
http://lucille.atso-net.jp/blog/?p=322

RT07 papers

http://www.uni-ulm.de/rt07/Program.html

[En]

Now list of RT07 papers is released!

There seems a lot of interesting papers. I can’t wait to read papers 🙂

[Ja]

RT07 の論文リストが発表されています。
今年もなかなか面白そうな論文が多そうです。

タイトルだけみて、気になった論文を挙げておきます。

– RTSL: a Ray Tracing Shading Language
おおついにレイトレ言語ですか。GLSL に trace() が追加されただけ、とかじゃないですよね…

– Sampling and Shading
セッション自体は RT^2 とあまり関係なさそうですが、リストされている論文自体は興味深そう。

– Towards Hardware Ray Tracing using Fixed Point Arithmetic
固定小数点にすることで、10倍高速化される、みたいな展開でも無い限り、
今どきハードウェアだからってわざわざ固定小数点を使うこともないような気もします。

– Realtime Ray Tracing on GPU with BVH-based Packet Traversal
BVH on GPU ですね。stackless kd-tree で地位を失った Slusallek 復権なるか?…

– Faster Ray Packets – Triangle Intersection through Vertex Culling
頂点カリングで交差判定? Reshetov なので、ラスタライザの機能は使わなそう?

– Deep Coherent Ray Tracing
もっとコヒーレンスを出す何かか?

A Comparison of Methods for Generating Poisson Disk Distributions

A Comparison of Methods for Generating Poisson Disk Distributions
http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW459.abs.html

タイルサンプラー野郎 Ares Lagae [1] による貴重な Poisson disk サンプリング手法の比較レポートを読みました。

まずレポートでは、結論として、

– 一様密度なら著者が提案した corner based poisson disk tiles が最強!
– インポータンスサンプリングするならしょうがねー、 recursive wang tiles に軍配をやるよ
(RWT を一様密度に使うと corner based より分布は悪いけどね)

です[2]。

以下、各種比較した手法に対する著者の主張をまとめると以下の通り。

– ダーツ投げ(dart throwing)系
遅いのでインタラクティブ系には使えない。[Jones 06], [Dunbar and Humphreys 06] は高速化手法を提案
しているが、それでも tile ベースの手法に比べれば遅い。また品質(半径)を上げようとすると Lloyd の緩和法
を使うことになってしまい、やっぱり遅くなってしまう。

– Tiled blue noise sampler [Hiller et al 2001]

品質が悪い(半径が小さい、スペクトル分布が悪い)ので勧めない。
タイルの境界と境界でないところで半径に差がある。

# 個人的には当時はこれ最強の blue noise sampler じゃね?と思っていましたが、
# 手法は常に古くなって新しいもので改善されていくものだなぁと実感。

– Penrose tile sampler [Ostromoukhov et al 2004]
– Recursive Wang Tiles [Kopf et al 2006]

どちらもスペクトルの品質は平均以下。
また、RWT の半径はおどろくほど低い。
RWT は一様密度に対しては使うべきでない。

私は [Hiller et al 01] でブルーノイズに出会ってから、Penrose tile sampler で衝撃を受けて、RWT, SWP で
さらに衝撃を受けてきました。

このサンプラーの分野はことごとく新発の手法が既存手法の欠点を明らかにし、それらを改善する手法が提案されてきました。
この分野ほど、毎年のようにその当時まで最強のサンプラーだったものが、
差分レベルではなくほとんど完全に新しい提案手法で更なる最強のサンプラーに
ドラマティックに塗り替えられていくのは、なかなか他の CG 分野でもなかったのではないか思います。
(SHexp までの PRT はこれに近いものがありますが)
この激動の(?)最強サンプラー合戦時代をリアルタイムで目の当たりにすることができて、
私はとても運がよかったと思います。

[1] http://www.cs.kuleuven.be/~ares/
[2] このレポートが出たのは Sampling with Polyominoes が発表されるまえであることに注意。
一様分布の場合に SWP と corner based ではどちらがよいかは調べてみる必要がある。

[Jones 06] Thouis Jones, Efficient Generation of Poisson-Disk Sampling Patterns.
http://people.csail.mit.edu/thouis/

[Dunbar and Humphreys 06] Daniel Dunbar and Greg Humphreys, A Spatial Data Structure for Fast Poisson-Disk Sample Generation.
http://www.cs.virginia.edu/~gfx/pubs/antimony/

[Hiller et al 2001] Stefan Hiller, Oliver Deussen and Alexander Keller, Tiled blue noise samples.
http://citeseer.ist.psu.edu/493970.html

[Ostromoukhov et al 04] Victor Ostromoukhov, Charles Donohue and Pierre-Marc Jodoin 2004, Fast Hierarchical Importance Sampling With Blue Noise Properties.
http://www.iro.umontreal.ca/~ostrom/publications/

[Kopf et al 2006] Johannes Kopf, Daniel Cohen-Or, Oliver Deussen and Dani Lischinski, Recursive Wang Tiles for Real-Time Blue Noise
http://johanneskopf.de/publications/blue_noise/