Japan Journal of Industrial and Applied Mathematics

A linear algorithm for Brick Wang tiling

A linear algorithm for Brick Wang tiling

Alexandre Derouet-Jourdan, Shizuo Kaji, Yoshihiro Mizoguchi

The Wang tiling is a classical problem in combinatorics. A major theoretical question is to find a (small) set of tiles which tiles the plane only aperiodically. In this case, resulting tilings are rather restrictive. On the other hand, Wang tiles are used as a tool to generate textures and patterns in computer graphics. In these applications, a set of tiles is normally chosen so that it tiles the plane or its sub-regions easily in many different ways. With computer graphics applications in mind, we introduce a class of such tileset, which we call sequentially permissive tilesets, and consider tiling problems with constrained boundary. We apply our methodology to a special set of Wang tiles, called Brick Wang tiles, introduced by Derouet-Jourdan et al. in 2016 to model wall patterns. We generalise their result by providing a linear algorithm to decide and solve the tiling problem for arbitrary planar regions with holes.


Eurographics 2019

MegaViews: Scalable Many-View Rendering with Concurrent Scene-View Hierarchy Traversal

MegaViews: Scalable Many-View Rendering with Concurrent Scene-View Hierarchy Traversal

Timothy R. Kol, Pablo Bauszat, Sungkil Lee, Elmar Eisemann

We present a scalable solution to render complex scenes from a large amount of viewpoints. While previous approaches rely either on a scene or a view hierarchy to process multiple elements together, we make full use of both, enabling sublinear performance in terms of views and scene complexity. By concurrently traversing the hierarchies, we efficiently find shared information among views to amortize rendering costs. One example application is many-light global illumination. Our solution accelerates shadow map generation for virtual point lights, whose number can now be raised to over a million while maintaining interactive rates.

Eurographics 2019

Generating Stochastic Wall Patterns On-the-Fly with Wang Tiles

Generating Stochastic Wall Patterns On-the-Fly with Wang Tiles

Alexandre Derouet-Jourdan, Marc Salvati, Théo Jonchier

The game and movie industries always face the challenge of reproducing materials. This problem is tackled by combining illumination models and various textures (painted or procedural patterns). Generating stochastic wall patterns is crucial in the creation of a wide range of backgrounds (castles, temples, ruins...). A specific Wang tile set was introduced previously to tackle this problem, in an iterative fashion. However, long lines may appear as visual artifacts. We use this tile set in a new on-the-fly procedure to generate stochastic wall patterns. For this purpose, we introduce specific hash functions implementing a constrained Wang tiling. This technique makes possible the generation of boundless textures while giving control over the maximum line length. The algorithm is simple and easy to implement, and the wall structure we get from the tiles allows to achieve visuals that reproduce all the small details of artist painted walls.


JCGT 2019

Implementation of Fast and Adaptive Procedural Cellular Noise

Implementation of Fast and Adaptive Procedural Cellular Noise

Théo Jonchier, Alexandre Derouet-Jourdan, Marc Salvati

Worley氏によって提案されたCellular noiseは肌やワニの皮や石などの自然物の表現にとても役に立ちます.Cellular noiseはテクスチャー空間中の各位置でグリッドの近傍点を求めることにより計算されます.予備研究では、2次元空間内でグリッドのセルを再分割し、最適な順番で探索することで、注目点における不均一な分布のノイズの計算法を考案しました.本論文では、これを3次元空間に拡張した場合の詳細について述べます.3次元空間における最適な順番での探索によりWorley氏のアルゴリズムよりも15-20%早く計算ができます.
Journal of Computer Graphics Techniques (JCGT), vol. 8, no. 1, 35-44, 2019

Proceedings of the Royal Society of London A

Inverse design of an isotropic suspended Kirchhoff rod

Inverse design of an isotropic suspended Kirchhoff rod: theoretical and numerical results on the uniqueness of the natural shape

Florence Bertails-Descoubes, Alexandre Derouet-Jourdan, Victor Romero and Arnaud Lazarus

キルヒホッフの弾性棒(Kirchhoff elastic rod)の方程式を解くことは、長い間数学、物理、コンピュータ科学といった広い分野での課題でした.この問題を解くことは、DNA、 頭髪、つる植物といった薄く、曲がりやすい構造を持った物のモデリングへの応用が期待できます.
The natural curvature plays an important role in the equilibrium shape of a Kirchhoff rod. In this paper, we characterize the natural curvature of a suspended isotropic rod, given an equilibrium curve. We prove that all natural curvatures that are compatible with the prescribed equilibrium are equivalent in the sense that they correspond to a unique natural shape for the rod.
Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences


Dappled tiling

Dappled tiling

Shizuo Kaji, Alexandre Derouet-Jourdan, and Hiroyuki Ochiai

縦/横に複数回同じタイルを並べないようにタイルを並べる (タイリング) 問題を解く方法です.タイルの数は2つ以上でどのような タイリングでもその条件を保証するように提案するアルゴリズムは組まれています.
Symposium MEIS2016: Mathematical Progress in Expressive Image Synthesis



Procedural Non Uniform Cellular Noise

Theo Jonchier, Marc Salvati and Alexandre Derouet-Jourdan

Symposium MEIS2016: Mathematical Progress in Expressive Image Synthesis



Fluid Volume Modeling from Sparse Multi-view Images by Appearance Transfer

Makoto Okabe, Yoshinori Dobashi, Ken Anjyo, Rikio Onai

疎な多視点動画から、3次元の流体アニメーションを作るモデリング技術です. 単一視点や直交2視点といった疎な動画からでも自然な見た目の流体(炎、煙、爆発、水しぶき)のボリュームが得られます.実用性を考慮し、流体シミュレータ(Autodesk Maya)などを用いて、流体の見た目や動きを編集できるようになっています.
ACM Transactions on Graphics (Proc. SIGGRAPH 2015), Vol 34, No 4, pp. 93:1-93:10

EGSR 2015


MBVH Child Node Sorting for Fast Occlusion Test

Shinji Ogaki, Alexandre Derouet-Jourdan

Eurographics Symposium on Rendering (EGSR 2015) - Experimental Ideas & Implementations

EUROGRAPHICS 2014 | STAR – State of The Art Report


Practice and Theory of Blendshape Facial Models

J.P. Lewis, Ken Anjyo, Taehyun Rhee, Mengjie Zhang, Fred Pighin, Zhigang Deng

ブレンドシェイプはシンプルな線形モデルで、リアルなフェイシャルアニメーション制作に使われる技術です.プレンドシェイプアプローチは映像業界で生まれ、比較的最近になってから学術研究の対象となりました.このレポートは、 学術研究および産業界それぞれで技術発表された最先端の文献をカバーしています.ブレンドシェイプアプローチは、数学的な基礎技術に関連したオープンな問題が残っていることも示しています.
EUROGRAPHICS 2014 State of the Art Reports, pp. 199-218, 2014.4

JGT 2013


Line Selection Tool for 3D Artists

Jaewoo Seo, Ken Anjyo

Journal of Graphics Tools, Volume 16, Issue 4, pp.233-244

JGT 2012


A Practical Approach to Direct Manipulation Blendshapes

Ken Anjyo, Hideki Todo, J.P. Lewis

前著 "Direct Manipulation Blendshapes"で提案した手法に、より実用的な技術を加え、Maya Plug-Inとしての実装に関する詳細を追加しました.さらに統計的アルゴリズムを導入することで、アニメーションデータを"学習"する機能を加え、そのデータから読みとれる顔の動きの特徴を活かした表情アニメーションが作成できるようになりました.
Journal of Graphics Tools, Volume 16, Issue 3, 2012, pp. 160-176

Journal of Math-for-Industry (JMI) 2011


RBF interpolation and Gaussian process regression through an RKHS formulation

Ken Anjyo, J. P. Lewis

Journal of Math-for-Industry, Vol. 3 (2011A-6), pp. 63–71, 2011.2




Direct Manipulation Blendshapes

J.P. Lewis, Ken Anjyo

IEEE Computer Graphics and Applications Special Issue: Digital Human Faces, Vol. 30(4), p.42-50

CASA 2009


Stylized Lighting for Cartoon Shader

Hideki Todo, Ken Anjyo, Takeo Igarashi

3Dモデルの陰影やハイライトを、手描きアニメ風に強調することができるトゥーンシェーダ技術です.「鋭さを強調するための輪郭付近に出る陰影やハイライト」 「凹凸を強調するための陰影やハイライト」などをトゥーンシェーダ上でも実現できます.既存の手法では手間がかかったり、複数の特徴を強調したりすることは困難でしたが、本手法では少数のパラメータにより、インタラクティブに効率よく特徴の強調の仕方をデザインすることができます.
The Journal of Computer Animation and Virtual World (CASA 2009), Vol. 20, issue 2-3, pp.143-152

CASA 2009


N-way morphing for 2D animation

William Baxter, Pascal Barla, Ken Anjyo

The Journal of Computer Animation and Virtual World (CASA 2009), Vol. 20, issue 2-3, pp. 79-87

TVCG 2009 | テクニカルレポート(英語版) OLMTRE-2008-001

Compatible Embedding for 2D Shape Animation

Compatible Embedding for 2D Shape Animation

William Baxter, Pascal Barla, Ken Anjyo

Visualization and Computer Graphics, IEEE Transactions, Vol.15 , Issue 5, pp. 867-879




Animating Pictures of Fluid using Video Examples

Makoto Okabe, Ken Anjyo, Takeo Igarashi, Hans-Peter Seidel

Computer Graphics Forum (EUROGRAPHICS 2009 Special Issue), vol.28. No.2, pp.677-686

CASA 2008


Directable Animation of Elastic Bodies with Point-Constraints

Ryo Kondo, Ken Anjyo

The Journal of Computer Animation and Virtual World (CASA 2008), Vol. 19, Issue 3-4, pp.165-173

NPAR 2008


Rigid Shape Interpolation Using Normal Equations

William Baxter, Pascal Barla, Ken Anjyo

2次元のモーフィングや形状補間のための新しい剛体補間手法を提案しました.従来手法の問題点を克服し、(1) ポリゴン分割の仕方による影響を極力減らして補間できる、(2) ソースとターゲットとの指定順序に関係なく安定したモーフィングを生成できる、(3)ソースとターゲット上の対応する頂点の変化(頂点の移動パス)も指定できる、(4) 180度以上の回転など、回転時に破綻するという従来の問題を解決した、の特徴があります.
Proc. The 6th International Symposium on Non-Photorealistic Animation and Rendering (NPAR 2008), pp.59-64



Locally Controllable Stylized Shading

Hideki Todo, Ken Anjyo, William Baxter, Takeo Igarashi

3Dモデルの陰影部分(Shaded area)をリアルタイムに編集制御できる"局所制御可能なトゥーンシェーダ"技術です.3Dのカメラとライトを通常の方法で制御しつつ、陰影の細部をユーザがレタッチしてアニメーションをつくるという新しいアニメーション作成方式です.
ACM Transactions on Graphics (SIGGRAPH2007) Vol. 26, Issue 3, Article No.17



Latent Doodle Space

William Baxter, Ken Anjyo

アニメの背景などでは、木の葉や花畑の花々、群集など、同じような形状でありながらも微妙に異なる絵を大量に描く必要があります.この論文では、数個程度のサンプルをもとに、それと似ていながらも少し異なる絵を"簡単に" "大量に"作る技術を提案しています.今回は、手描きの線画表現をとり上げ、新しい学習モデルを構築しました.使いやすいインタフェースを導入することで、少ない入力例から多数の類似した出力をインタラクティブに生成できるようになりました.
Computer Graphics Forum (Eurographics2006), Vol.25(3), pp.477-485,

NPAR 2006


Tweakable Light and Shade for Cartoon Animation

Ken-ichi Anjyo , Shuhei Wemler , William Baxter

アニメのハイライトや影には演出的な意味合いが強くあります.たとえば、刀が"鋭利"、窓からの光が "映りこんでいる"、車が"猛スピードで動く"などは、ハイライトや影のかたちや動き方で表現できます.これを実現するには、物理的にではなく、演出意図に応じてハイライトや影をアニメーションさせることが必要です.この論文ではアニメ風のハイライトや陰影のアニメーションを、ユーザのドラッグ操作のみで生成できる技術を提案しています.分離、四角形化、平行移動、方向性のある拡大縮小など、すべてドラッグ操作で指定できます.光源の制御や数値パラメータの入力なしに、ダイナミックな陰影変化をもつアニメーションを作れます.
Proc. of NPAR 2006, The 4th International Symposium on Non-Photorealistic Animation and Rendering, pp.133-139

SCA 2005


Directable Animation of Elastic Objects

Ryo Kondo, Takashi Kanai, Ken Anjyo

Proc. ACM SIGGRAPH/ Eurographics Symposium on Computer Animation (SCA2005), pp.127-134



Stylized Highlights for Cartoon Rendering and Animation

Ken Anjyo, Katsuaki Hiramitsu

IEEE Computer Graphics and Applications Vol.23 No. 4 (Special issue on Non-Photorealistic Rendering) pp.54-61


テクニカルレポート(英語版) OLMTRE-2008-002

Notes on Compatible 2D Shape Embedding

Notes on Compatible 2D Shape Embedding

William Baxter, Pascal Barla, Ken Anjyo

技術解説ノート(日本語) OLMNOTE-2004-001


Highlight Shader

Ken Anjyo