Implicit surfaces have various applications in computer-aided design and computer graphics, and have been actively studied due to their advantages such as their smoothness and nice mathematical properties. Among them, there exists a kind of surfaces that are computed from a point set. Such point-based implicit surfaces have gained increasing attentions in order to reconstruct smooth surfaces from point data obtained from 3D range scanning or particle-based physical simulations.

Point-based implicit surfaces can be classified into two categories according to the targets of representation. One category represents the surface of an object while another category represents a solid object. Throughout this dissertation, the former is called surface implicits, and the latter is called volumetric implicits. A main application of surface implicits is reconstruction of the smooth surface of a 3D-scanned object. On the other hand, volumetric implicits are often used to represent liquid fluids consisting of particles and electronic distributions of molecular models.

This dissertation explores efficient and high-quality methods for visualizing these point-based implicit surfaces. To develop practical algorithms, one must take the purposes of use of point-based implicit surfaces into account. Additionally, because the surface positions of implicit surfaces are expensive to compute, the key factors for fast computation include introduction of efficient data structures and utilization of graphics hardware (GPU), which has significantly improved its power of parallel computation.

Surface implicits often aim to represent static data such as 3D-scanned surfaces. Therefore, typical methods employ a preprocessing where geometric data like a polygonal mesh is computed from surface implicits, and the geometric data is then used for rendering. As such geometric data, the method proposed in this dissertation generates a point set that is sampled from surface implicits. The output point set is managed with a hierarchical data structure that is well suited for level-of-detail control because, unlike polygonal meshes, a point set does not contain information of connectivity among points. For rendering of such point set, a disk is attached for each point. Overlaps among disks are permitted in order to cover the surface without gaps. While the proposed method employs sampling of points along tangent planes of the implicit surface, unlike previous methods, it tries to reduce the overlaps of disks and thus produces fewer point samples. The proposed method can further reduce the number of output samples by changing the sizes of disks, i.e., sampling densities according to properties of the surface such as curvatures.

On the other hand, the recent, most important application of volumetric implicits seems to be representation of time-varying, dynamic objects obtained as results of particle-based physics simulations. This dissertation presents a fast and accurate method for rendering the surface of volumetric implicits consisting of a large number of moving particles by utilizing the functionality of the GPU. The present method uses a kind of volumetric implicits, namely, metaballs. A metaball has a density distribution that is isotropic and monotonically decreases from the center of the metaball, and the isosurface of the density field defined by a set of metaballs represents a smooth surface of an object. The present method computes the position of the isosurface accurately for each pixel of the screen, i.e., each viewing ray. For such computation, one must specify the metaballs that contribute to the isosurface along each viewing ray, and then set up and solve an equation for a ray-isosurface intersection test. This dissertation describes how to handle these processes efficiently with the restricted memory management system of the modern GPU. To specify the metaballs required for a ray-isosurface intersection test, the present method keeps a list of metaballs for each pixel, and then updates the list every time a sphere (bounding sphere) that represents the boundary of the density distribution of each metaball is rendered with a depth test. To solve an equation of a ray-isosurface intersection test, the present method optimizes a solver for polynomial equations, Bezier Clipping, for the GPU, and makes use of it. With further optimizations including a fast rendering technique of spheres and culling of hidden metaballs, the present method can render numerous metaballs quickly and accurately.

This dissertation also presents another method for rendering metaballs, which prioritizes the rendering speed rather than the visual quality. The present method subdivides the viewing volume into planes (slices) that are perpendicular to the viewing direction, accumulates the density values of metaballs into the slices, and then extracts isosurfaces from the slices. The density values are sparsely evaluated on the slices in a single rendering pass where the bounding volume of each metaball is rendered, and then interpolated to compute isosurfaces. To capture small metaballs with a small amount of memory, the present method first checks the distributions of metaballs in the scene by roughly voxelizing the scene, and allocates bundles of slices only to non-empty voxels. Consequently, the present method performs several times faster than the aforementioned technique proposed in this thesis.

陰関数曲面は、曲面の滑らかさや数学的に扱いやすいなどの利点により、CADやコンピューグラフィクスの分野において、幅広く利用されてきた。この陰関数表現の中に、陰関数を点群ベースで表現する手法があり、最近の3D計測や物理シミュレーションの分野で利用される場合が多くなってきている。本論文は、これらの点群ベースの陰関数表現を効率的かつ高品位に描画する手法を研究したものであり、「A Study on efficient sampling and fast rendering of point-based implicit surfaces (点群ベース陰関数曲面の効率的なサンプリングおよび高速な描画についての研究)」と題され、6章からなり英文で書かれている。

第1章は、「Introduction(序論)」と題され、研究の背景や動機、本論文の構成について述べている。引き続いて、第2章は、「Fundamentals and Related Work (基本用語と関連研究)」と題され、点群ベースの陰関数表現の分類、点群ベースの陰関数表現の表示法、関連研究、ならびに、関連研究における問題点などを整理している。

第3章は、「Efficient Sampling of Points on Surface Implicits (面表現陰関数のための点群の効果的サンプリング)」と題され、高速なレンダリングのための面表現陰関数のための点群を描画ハード(GPU)を用いて高速にサンプリングする手法を提案している。手法は、陰関数表現のための点群を入力として、これらのなかからランダムに点を選びだし、この選びだされた点を中心にSurfelと呼ばれる円盤を敷き詰め、これらの円盤で面が覆われるかをチェックし、隙間を検出し、隙間なく曲面上をカバーするために円盤を追加するという手法をGPUの上で実装し、高速なレンダリングを可能とした。

第4章は、「High Quality Ray Casting of Metaballs (メタボールの高精度レイキャスト法)」と題され、高精度に陰関数表現を描画する手法を提案している。第3章の手法が主に、3D計測で得られるような表面データを主に対象としていたのに対し、本章の手法は、物理シミュレーションなどでえられるボリュームの可視化に的をしぼり、これの高精度な描画法を提案したものである。ボリュームを表現する粒子をメタボールと名づけ、これを可視化のために使用することで、高精度な手法を達成している。

第5章は、「Fast Rendering of Metaballs using Dynamic Slicing (動的スライスを用いたメタボールの高速レンダリング)」と名づけられ、インターラクティブな使用のために、高速にメタボールを表示する手法を提案している。前章の手法においては、多数のメタボールを繰り返し処理するため、高精度ではあるものの時間がかかるという欠点があった。本章の手法では、メタボールを空間中において階層的に表現することで、現在の可視化に必要なメタボールを階層構造を利用して効率的に選択できるようにすることで高速化を達成している。

第6章は、「Conclusions and Future Work (結論と残された問題)」と題され、本論文のまとめと今後の研究の方向性につて述べている。

以上これを要するに、本論文は、3D計測などで得られるデータなど面に重点がある点群データの陰関数表現をサーフェルという表現を効率的に敷き詰めることで高速に描画する手法、物理シミュレーションの可視化など内部の粒子にも重点があるような点群データの陰関数表現のためのメタボールを高精度に描画する手法、インターラクティブシステムなどのためにメタボールを高速に描画する手法を提案したもので、コンピュータ科学上貢献するところが少なくない。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。