3D （three-dimensional） surface scanning is widely used in the industry recently. It is applied in the reverse engineering field and dimensional inspection field mainly. The advantage using 3D surface scanning is its high measurement speed and wide surface of the measurement range. At the same time with the development of surface scanning techniques the scanning accuracy has been greatly improved.

However it is actually a time-consuming process to scan an object though the scanning speed itself is high. The reason is that it usually requires taking several tens or hundreds of scans （shots） to measure an object surface and thus need to plan scanning positions of the scanning device. It is very difficult to define the best scanning positions that achieve sufficient scanning accuracy. It is also taken into account to avoid occlusions in the sensing area, collisions between the scanners and the objects, and leak of scanned surface. Generally expert engineers spend tremendous amount of time on planning carefully with these conditions depending on the shapes of the object surfaces, scanning sensor specification.

This research aims at developing a planning system for automatically generating such scanning positions and a scanning path to continuously scan an object at these scanning positions. This is based on two technological backgrounds. One is a CNC-driven 3D surface scanning machine by which the positions （locations and orientations） of a scanning device can be numerically controlled from a computer system. Thus once the scanning positions are defined by the planning system, they can be fed to control the CNC-driven 3D surface scanning machine. The other is 3D CAD （Computer Aided Design） model of objects to be scanned. In industry, products are now designed by using 3D CAD systems. So it can be assumed that the 3D CAD models of the parts are available for the scanning process. Our planning system fully utilizes this 3D CAD model information of the object to be scanned to generate scanning positions and paths. Specifically, we use triangular mesh representations of 3D CAD models.

The system architecture consists of three parts. The first one is a scanning simulation. A multi-axis scanning machine simulator is constructed. A 3D mesh model of a scanned object surface is inputted into this simulator. The simulator executes not only a visualization process, but also three other functions. A visualization process is that motion commands can be executed by executing the simulator with visualization functions. The other three functions of the simulator include data acquisition, collision detection and occlusion detection. Data acquisition can be used to capture the scanned triangle IDs and coordinates of the object surfaces. This function is based on a graphics hardware acceleration algorithm. The occlusion detection is also based on the graphics hardware acceleration algorithm. The collision detection can be used to detect collisions between the scanning machine and the object surface. In this way, the computation time can be balanced between GPU （graphic processing unit） and CPU （central processing unit） in order to improve computing speed significantly.

The second part is sensor position planning to generate scanning positions （we call them sensor configuration positions hereafter.） based on 3D mesh model of the scanned object. First the model is divided into a set of cubic cells each of which contains a set of triangles representing a part of the object surface. Then a sensor configuration position is determined to each cell by taking into account the above mentioned factors such as scanning accuracy, occlusions, collisions and leaks by using the simulator. This cell decomposition is made in two levels for rough position planning and fine planning. At the rough position planning the object is uniformly decomposed into an array of cells whose size is determined by the maximum sensor scanning scope. The fine position planning is needed to achieve good coverage and accuracy for complex shape surface. These cells are further subdivided if a valid sensor configuration position cannot be defined and thus form a multi-root octree structure. The multi-root octree cells are made up of those un-completed scanned cells from rough position planning. Again, a sensor configuration position is defined to each of the cells in this multi-root octree structure.

The third part of the research is measurement path generation. With the sensor position planning mentioned above, a set of sensor configuration positions is calculated. This is the measurement path generation that links these sensor configuration positions to generate a scanning path. The difficult problem here is to find an optimal path in terms of various aspects of scanning procedures. Particularly, we consider scanning time and accuracy and introduce cost functions to evaluate these factors. Then an optimization method to find the best path to minimize these cost functions is proposed based on a "divide and conquer" approach. For "divide", the entire sensor configuration positions are divided into several clusters. It is called a clustering procedure in this research. Then the local optimal scanning path is calculated for each cluster. Path generation of each cluster can be considered as the same problem as TSP （traveling salesman problem）. For "conquer", the optimization goal is decided first. To realize the optimization goal, two different kinds of evaluation cost functions are established. A GA （genetic algorithm）-based method is adopted for calculating the optimal measurement path generation. The speed of implementation is improved with a multi-thread method in order to reducing calculating time. The sensor configuration positions of the global cluster consist of the head and tail sensor configuration positions of each local optimized path. The global path is generated with the same method of the local path generation and the same evaluation cost functions are used, and besides, the cost between the two head and tail sensor configuration positions from the same local cluster is considered as zero.

This research is aiming at the application to the scanning in automotive industry, such as measuring stamping die models and car body parts. Some examples are implemented with our developed planning system. The automation and high calculating speed show the efficiency of this system. The experiments on real CNC-driven surface scanning machine have also proofed the effectiveness of our proposed methods with the cooperation of maker experiments.

伍　鵬（WU PENG）提出の本論文は「CNC駆動3Dサーフェーススキャニングに適したモデルベースプランニングシステムに関するする研究」と題し、全7章よりなり、CADモデルデータを入力とし、自動計測プランニングによって計測パスを生成する問題を扱っている。

第1章では、3次元サーフェーススキャニング技術の概要を述べ、現在工業上に実際の計測フローを紹介した。現状の計測手法の問題点を指摘し、それを課題として本研究の目標・応用される分野と計測対象物について述べた。本研究に関連する先行研究として、モデルを使わない計測プランニングとモデルベース計測プランニングに関する研究紹介した。モデルベース先行研究は主に特定対象に対する内容であった。最後に、本研究と先行研究の関係を明らかにした。本研究と類似のものはなかった。

第2章では、本研究の課題として、3次元サーフェーススキャニングセンサと、CNC駆動計測機の角度から議論を行い、課題の特徴を述べた。3次元サーフェーススキャニングセンサの光学特性によって生じる干渉またはオクルージョンなどが生じ、マルチ計測ポジションが存在する場合CNC駆動に適した最適計測パスが必要とすることを論じた。この議論から、入力としてCADモデルデータを与えられ、スキャニングシミュレータとパスジェネレータを構築し、その二つのステップの計算を行い、出力としては、スキャニングの経路を生成するというアプローチを提案した。

第3章では、スキャニングシミュレーションシステムについて、どのような課題が存在するかを明確にし、この問題を解決する手法を提案した。

まず最初にシミュレーションをするためのマニピュレータと、サーフェーススキャニングセンサの原理と対応したセンサモデルを構築した。構築したシミュレータはグラフィックスハードウェアを利用し、高速化を図った。このスキャニングシミュレーションシステムによって以下の手法を提案した。

コンピュータ上にマニピュレータのモーションシミュレーション

計測対象モデルに測れられた三角形IDのキャプチャ。これは非測定範囲の計算に使う

計測対象モデルに測れられた3次元座標データのキャプチャ

マニピュレータと計測対象物間の干渉チェックの検出

スキャニングセンサと計測対象物間のオクルージョンの検出

以上の手法はCPUとGPUの分担計算されており、高速かつ正確な計算ができた。このシミュレーションシステムをベースにして次のポジションプランニングへ進む。

第4章では、センサポジションプランニングについて述べた。ラフープランニングとファインプランニングの2段階に分けられ、ラフープランニングではセル分割というメソッドを用いてセルごとのベスト計測ポジションを計算した。ファインプランニングではラフープランニングで計測不十分だったセルに対してマルチルートのオクトリー構造で細分を行い、細分されたオクトリーのセルに対してベスト計測ポジションを計算した。そしてシミュレーションによって被計測範囲の算出を行い、このように求められた被計測範囲が充足するか、決められた細分回数まで細分を繰り返した。この2段階のプランニングによってセンサポジション群が求められた。

第5章では、計算されたセンサポジション群を繋いで最適なパスを生成する手法を述べた。まず、最適な計測パスを生成するための評価要素及び評価関数を述べた。それからセンサポジション群のクラスターリングによって子クラスタに分け、子クラスタごとのローカル的に問題を効率的に解くため最適なパス生成手法を提案した。クラスタの最適なパス生成はTSPの問題となり、GA手法を用いて高速に計算ができた。最後に各ローカルクラスタのパスを繋がってグロバールパスを計算を行った。

第6章では、本研究で提案した手法の実装と実験を行った。本研究のためのソフトを作り、プレス金型モデル及び車モデルなどのデータを入力してプランニングを行い、シミュレーションシステムとパスプランニングシステムによって最適な計測パスの計算ができた。メーカ側の協力を実験中の結果を述べた。

第7章では、本研究の成果をまとめ、総括し、今後の課題に関して論述した。

以上を総括すると、本研究は、CADモデルデータを入力として、シミュレーションシステムとパスプランニングシステムを構築し、完全自動な計測プランニングによって高速に処理することができることを示した。主に自動車分野、例えば車ボディ、プレス金型などのモデルに応用されたと考えられ、デジタルエンジニアリングにおける3次元計測プランニング問題を効率的に解く手法を提案し、大きな貢献を行った。

よって本論文は博士（工学）学位請求論文として合格と認められる。