JP6802702B2 - Shape deformation device and shape deformation program - Google Patents
Shape deformation device and shape deformation program Download PDFInfo
- Publication number
- JP6802702B2 JP6802702B2 JP2016241037A JP2016241037A JP6802702B2 JP 6802702 B2 JP6802702 B2 JP 6802702B2 JP 2016241037 A JP2016241037 A JP 2016241037A JP 2016241037 A JP2016241037 A JP 2016241037A JP 6802702 B2 JP6802702 B2 JP 6802702B2
- Authority
- JP
- Japan
- Prior art keywords
- deformation
- shape
- sphere
- mapping
- unit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Landscapes
- Image Processing (AREA)
Description
本発明は、形状変形装置および形状変形用プログラムに関し、特に、測定等により得られた点群・ポリゴンにより表された３次元形状の表面を平滑化するための技術に関するものである。 The present invention relates to a shape deformation device and a shape deformation program, and more particularly to a technique for smoothing a surface of a three-dimensional shape represented by a point cloud / polygon obtained by measurement or the like.
今日、製品の設計を行う際には、ＣＡＤ（Computer Aided Design）によって製品の形状データを生成することが一般的に行われている。伝統的なＣＡＤシステムでは、ＮＵＲＢＳあるいはＢスプライン関数で表された曲線・曲面を用いて物体形状が表されていた。これに対し、最近では、多数の点の集合である点群データ、または、三角形や四角形の形状をした複数のポリゴンの集合（ポリゴンメッシュ）として物体形状を表す形状モデリングシステムが増えてきている。 Today, when designing a product, it is common practice to generate shape data of the product by CAD (Computer Aided Design). In a traditional CAD system, an object shape is represented using a curve / curved surface represented by a NURBS or B-spline function. On the other hand, recently, a shape modeling system that represents an object shape as a point cloud data which is a set of a large number of points or a set of a plurality of polygons (polygon mesh) in the shape of a triangle or a quadrangle is increasing.
この種の形状モデリングシステムにおいて、目的とする物体形状に近づけるために、表面形状を適宜変形することは必須である。例えば、物体表面に存在する凹凸をなくすような形状変形を施すことにより、滑らかな曲面形状を生成することが行われる。従来、滑らかな曲面形状を生成するための標準的な技術として、スムージングと呼ばれる手法が知られている。 In this kind of shape modeling system, it is indispensable to appropriately deform the surface shape in order to approach the target object shape. For example, a smooth curved surface shape is generated by performing shape deformation so as to eliminate unevenness existing on the surface of the object. Conventionally, a method called smoothing is known as a standard technique for generating a smooth curved surface shape.
本出願人は、点群データまたはポリゴンメッシュの何れにより表される物体形状に対しても適用でき、かつ、物体形状の広領域を「うねり」のない（曲がり方の変化が少ない）滑らかな形状に変形可能にしたスムージングに関する形状変形装置に係る発明について、特許出願をしている（特許文献１参照）。 Applicants can apply to an object shape represented by either point cloud data or a polygon mesh, and a wide area of the object shape can be covered with a smooth shape without "waviness" (less change in bending). A patent application has been filed for an invention relating to a shape deforming device related to smoothing that has been made deformable (see Patent Document 1).
特許文献１に記載した形状変形装置では、放射基底関数（ＲＢＦ）の１次結合で表わした位置連続に関する項を含む変形写像式と、移動元位置を変形写像式で写像した位置と目標とする移動先位置との距離を表した「位置近似」および移動先位置における「曲率変化率最小化」に関する拘束条件方程式とを設定し、当該拘束条件方程式を解いて、変形写像式に含まれる未知数を求めることにより、位置近似および曲率変化率最小化を満たす変形写像を確定させる。そして、確定された変形写像を用いて、形状データにより表された物体形状を変形させる処理を実行するようにしている。 In the shape deforming device described in Patent Document 1, a deformed mapping equation including a term relating to position continuity represented by a linear combination of radiation basis functions (RBF) and a position and a target at which the moving source position is mapped by the deforming mapping equation are used. Set a "position approximation" that expresses the distance to the destination position and a constraint condition equation related to "minimization of the rate of change in curvature" at the destination position, solve the constraint condition equation, and find the unknown number included in the modified mapping equation. By obtaining, a deformed map that satisfies the position approximation and the minimization of the rate of change in curvature is determined. Then, using the determined deformation map, the process of deforming the object shape represented by the shape data is executed.
特許文献１に記載の技術によれば、移動元位置および移動先位置という点のデータを用いて、物体形状を近似変形することができる。そのため、物体形状の形状データが点群データにより表される場合は、各点のデータを移動させて物体形状を近似変形させることが可能である。また、物体形状の形状データがポリゴンメッシュにより表される場合は、メッシュの各頂点のデータを移動させて物体形状を近似変形させることが可能である。ここで、物体形状の近似変形は、位置近似および曲率変化率最小化を満たす変形写像に基づき行われるので、曲がり方の変化の少ない形状、つまり「うねり」のない滑らかな形状に変形される。 According to the technique described in Patent Document 1, the shape of an object can be approximately deformed by using data of points of a movement source position and a movement destination position. Therefore, when the shape data of the object shape is represented by the point cloud data, it is possible to approximate and deform the object shape by moving the data of each point. Further, when the shape data of the object shape is represented by the polygon mesh, it is possible to approximate and deform the object shape by moving the data of each vertex of the mesh. Here, since the approximate deformation of the object shape is performed based on the deformation mapping that satisfies the position approximation and the minimum curvature change rate, the object shape is deformed into a shape with little change in bending, that is, a smooth shape without "waviness".
また、物体形状の広い範囲に複数の移動元位置が分布しているような場合でも、それら複数の移動元位置を表す各点のデータと、複数の移動元位置に対応する複数の移動先位置を表す各点のデータとを用いて拘束条件方程式を設定し、当該拘束条件方程式を解いて、変形写像式に含まれる未知数を求めれば、物体形状を近似変形することができる。つまり、広領域に含まれる点データを用いて表現した拘束条件方程式を解くだけで、物体形状を近似変形することができる。 Further, even when a plurality of movement source positions are distributed over a wide range of the object shape, the data of each point representing the plurality of movement source positions and the plurality of movement destination positions corresponding to the plurality of movement source positions If the constraint condition equation is set using the data of each point representing the above, the constraint condition equation is solved, and the unknown number included in the deformation mapping equation is obtained, the object shape can be approximately deformed. That is, the shape of the object can be approximated and deformed only by solving the constraint equation expressed by using the point data included in the wide area.
以上により、特許文献１に記載の技術によれば、点群データまたはポリゴンメッシュの何れにより表される物体形状に対しても適用でき、かつ、物体形状の広領域を滑らかな形状に変形することが可能である。 As described above, according to the technique described in Patent Document 1, it can be applied to an object shape represented by either point cloud data or a polygon mesh, and a wide area of the object shape can be transformed into a smooth shape. Is possible.
なお、高品質なレンダリングを実現するための手法として、ＳＬＩＭ（Sparse Low-degree IMplicit）曲面を用いた描画方法が知られている（例えば、非特許文献１参照）。ＳＬＩＭ曲面は、中心位置、半径、基底変換の回転行列、多項式関数の情報を持ったサポート球の集合で構成され、関数はサポート球の持つローカル座標系により表現されている。曲面上の点の位置を求めるときは、ローカル座標系での座標値を回転行列によりグローバル座標系での座標値に変換してから、重み付き和を計算する。 As a method for realizing high-quality rendering, a drawing method using a SLIM (Sparse Low-degree IMplicit) curved surface is known (see, for example, Non-Patent Document 1). The SLIM curved surface is composed of a set of support spheres having information on the center position, radius, rotation matrix of basis transformation, and polynomial function, and the function is represented by the local coordinate system of the support sphere. When finding the position of a point on a curved surface, the coordinate value in the local coordinate system is converted into the coordinate value in the global coordinate system by a rotation matrix, and then the weighted sum is calculated.
上記特許文献１に記載した形状変形装置は、物体形状の比較的広い領域を対象として滑らかな形状に変形することを可能にするものであるが、物体形状の中から変形対象領域を指定する必要があり、指定された領域内だけをスムージングするものであった。特許文献１に記載の技術では、変形対象領域内から複数のサンプル点を抽出し、抽出した複数のサンプル点に対する近似平面を生成する処理を行うため、サンプル点の位置のばらつきが大きくなると、誤差の少ない近似平面を生成することが難しくなる。そのため、サンプル点の位置のばらつきがあまり大きくならない比較的平坦な領域に絞って変形対象領域を指定する必要があった。 The shape deforming device described in Patent Document 1 makes it possible to deform a relatively wide area of an object shape into a smooth shape, but it is necessary to specify a deformation target area from the object shape. There was, and it was intended to smooth only within the specified area. In the technique described in Patent Document 1, a plurality of sample points are extracted from the deformation target region and an approximate plane is generated for the extracted plurality of sample points. Therefore, if the variation in the positions of the sample points becomes large, an error occurs. It becomes difficult to generate an approximate plane with few. Therefore, it is necessary to specify the deformation target area by narrowing down to a relatively flat area where the variation in the position of the sample point does not become so large.
そこで、本発明は、ユーザが変形対象領域を指定しなくても、物体形状の広領域を滑らかな形状に変形することができるようにすることを目的とする。 Therefore, an object of the present invention is to enable a user to transform a wide region of an object shape into a smooth shape without designating a deformation target region.
上記した課題を解決するために、本発明では、物体形状を表す形状データに対して、隣接する領域間でオーバーラップする複数の変形対象領域を設定し、複数の変形対象領域のそれぞれにおいて、当該変形対象領域内に含まれる物体形状の各構成点の移動元位置を移動先位置へと変形させるための変形写像を算出し、変形対象領域ごとに算出した変形写像を用いて、変形対象領域内に含まれる物体形状を変形させる処理を実行する。ここで、変形対象領域がオーバーラップする重複領域内に含まれる形状部分の構成点については、各変形対象領域について算出された変形写像によるそれぞれの移動先の重み付き平均により移動先位置を決定するようにしている。 In order to solve the above-mentioned problems, in the present invention, a plurality of deformation target regions that overlap between adjacent regions are set for the shape data representing the object shape, and the deformation target regions are set in each of the plurality of deformation target regions. A deformation mapping for transforming the movement source position of each constituent point of the object shape included in the deformation target area to the movement destination position is calculated, and the deformation mapping calculated for each deformation target area is used in the deformation target area. The process of deforming the object shape included in is executed. Here, with respect to the constituent points of the shape portion included in the overlapping region where the deformation target regions overlap, the movement destination position is determined by the weighted average of each movement destination by the deformation mapping calculated for each deformation target region. I am doing it.
上記のように構成した本発明によれば、処理対象の物体形状が複数の互いにオーバーラップする変形対象領域に分割され、それぞれの変形対象領域内において変形写像による物体形状の変形が行われることにより、滑らかな形状に平滑化される。また、変形対象領域どうしのオーバーラップ部分に関しては、各変形対象領域の変形写像により算出される移動先の重み付き平均により移動先位置が決定されるので、オーバーラップ部分で段差や折れが生じないようにすることができる。これにより、本発明によれば、ユーザが変形対象領域を指定しなくても、物体形状の広領域を滑らかな形状に変形することができる。 According to the present invention configured as described above, the object shape to be processed is divided into a plurality of deformation target regions that overlap each other, and the object shape is deformed by the deformation mapping in each deformation target region. , Smoothed into a smooth shape. Further, regarding the overlapping portion between the deformation target regions, the movement destination position is determined by the weighted average of the movement destination calculated by the deformation mapping of each deformation target region, so that no step or break occurs in the overlapping portion. Can be done. Thereby, according to the present invention, it is possible to transform a wide region of the object shape into a smooth shape without the user specifying the deformation target region.
以下、本発明の一実施形態を図面に基づいて説明する。本実施形態の形状変形装置は、点群データまたはポリゴンメッシュにより表される物体形状の広領域（例えば、物体形状の全体）の構成面を滑らかな形状に変形するためのスムージング処理を行うものである。本実施形態の形状変形装置において処理対象とする物体形状は、大きな凹凸や屈曲部、突出部などが比較的少ない単純な形状とすることが可能なことはもちろん、例えば図１３に示すような複雑な立体形状とすることも可能である。 Hereinafter, an embodiment of the present invention will be described with reference to the drawings. The shape deforming device of the present embodiment performs a smoothing process for transforming a constituent surface of a wide area (for example, the entire object shape) of the object shape represented by point cloud data or polygon mesh into a smooth shape. is there. The object shape to be processed in the shape deforming device of the present embodiment can be a simple shape having relatively few large irregularities, bent portions, protruding portions, etc., and is of course complicated as shown in FIG. 13, for example. It is also possible to have a three-dimensional shape.
本実施形態の形状変形装置では、スムージングの処理対象とする物体形状の全体に対して、互いにオーバーラップする複数の変形対象領域を設定し、それぞれの変形対象領域内において、特許文献１に記載した手法により変形写像を算出する。そして、それぞれの変形対象領域において、変形写像を用いた形状変形を行う。このとき、変形対象領域が互いにオーバーラップする部分については、領域ごとに算出された変形写像による移動先位置を重み付け平均化することにより、隣接する変形対象領域間を滑らかに接続するようにする。 In the shape deformation device of the present embodiment, a plurality of deformation target regions that overlap each other are set for the entire object shape to be processed for smoothing, and the deformation target regions are described in Patent Document 1. The deformation mapping is calculated by the method. Then, in each deformation target region, shape deformation is performed using the deformation mapping. At this time, for the portions where the deformation target regions overlap with each other, the movement destination positions calculated for each region by the deformation mapping are weighted and averaged so that the adjacent deformation target regions are smoothly connected.
＜本実施形態による形状変形装置の概略構成＞
図１は、本実施形態による形状変形装置の基本的な機能構成例を示すブロック図である。図１に示すように、本実施形態の形状変形装置は、その機能構成として、領域設定部１０、変形写像算出部２０および形状変形部３０を備えて構成されている。変形写像算出部２０は、具体的な機能構成として、変形写像設定部２１、拘束条件設定部２２および変形写像確定部２３を備えている。
<Rough configuration of shape deforming device according to this embodiment>
FIG. 1 is a block diagram showing a basic functional configuration example of the shape deforming device according to the present embodiment. As shown in FIG. 1, the shape deforming device of the present embodiment includes a region setting unit 10, a deformation mapping calculation unit 20, and a shape deformation unit 30 as its functional configuration. The modified map calculation unit 20 includes a modified map setting unit 21, a constraint condition setting unit 22, and a modified map determining unit 23 as specific functional configurations.
図１に示した各機能ブロックは、ハードウェア、ＤＳＰ（Digital Signal Processor）、ソフトウェアの何れによっても構成することが可能である。例えばソフトウェアによって構成する場合、上記各機能ブロックは、実際にはコンピュータのＣＰＵ、ＲＡＭ、ＲＯＭなどを備えて構成され、ＲＡＭやＲＯＭ、ハードディスクまたは半導体メモリ等の記録媒体に記憶されたプログラムが動作することによって実現される。 Each functional block shown in FIG. 1 can be configured by any of hardware, DSP (Digital Signal Processor), and software. For example, when configured by software, each of the above functional blocks is actually configured to include a computer CPU, RAM, ROM, etc., and a program stored in a recording medium such as RAM, ROM, hard disk, or semiconductor memory operates. It is realized by.
領域設定部１０は、スムージング対象とする物体形状を表す形状データに対して、隣接する領域間でオーバーラップする複数の変形対象領域を設定する。本実施形態では、領域設定部１０は、変形対象領域として球形状の領域を設定する。物体形状のうち、比較的平坦な形状のところには大きな半径の球を設定し、凹凸部、屈曲部、突出部といった比較的複雑な形状のところには小さな半径の球を設定する。 The area setting unit 10 sets a plurality of deformation target areas that overlap between adjacent areas with respect to the shape data representing the shape of the object to be smoothed. In the present embodiment, the area setting unit 10 sets a spherical region as a deformation target region. Among the object shapes, a sphere with a large radius is set for a relatively flat shape, and a sphere with a small radius is set for a relatively complicated shape such as an uneven portion, a bent portion, and a protruding portion.
図２は、隣接する領域間でオーバーラップする複数の球（変形対象領域）を設定した様子を示している。ここでは図示の便宜上、物体形状の一部２０１のみを示している。実際は、領域設定部１０は、物体形状の全体を覆うように複数の球２０２を設定する。図２において、球２０２の中に描かれている複数の点２０３は、物体形状を構成している各構成点である。物体形状の形状データが点群データにより表される場合は、各点が物体形状の構成点２０３となる。また、物体形状の形状データがポリゴンメッシュにより表される場合は、メッシュの各頂点が物体形状の構成点２０３となる。 FIG. 2 shows a state in which a plurality of spheres (deformation target regions) that overlap between adjacent regions are set. Here, for convenience of illustration, only a part 201 of the object shape is shown. Actually, the area setting unit 10 sets a plurality of spheres 202 so as to cover the entire object shape. In FIG. 2, a plurality of points 203 drawn in the sphere 202 are each constituent points constituting the object shape. When the shape data of the object shape is represented by the point cloud data, each point becomes a constituent point 203 of the object shape. When the shape data of the object shape is represented by the polygon mesh, each vertex of the mesh becomes the constituent point 203 of the object shape.
領域設定部１０は、１つの球２０２内に含まれる複数の構成点２０３の数が所定範囲内となるように、複数の球２０２を設定する。これにより、比較的平坦な形状で構成点２０３が密集していないところには、上述したように大きな半径の球２０２が設定される。一方、凹凸部、屈曲部、突出部のように比較的複雑な形状で構成点２０３が密集しているところには、上述したように小さな半径の球２０２が設定される。なお、この球２０２の具体的な設定方法は後述する。 The area setting unit 10 sets a plurality of spheres 202 so that the number of the plurality of constituent points 203 included in one sphere 202 is within a predetermined range. As a result, a sphere 202 having a large radius is set as described above where the constituent points 203 are not densely packed in a relatively flat shape. On the other hand, as described above, a sphere 202 having a small radius is set in a place where the constituent points 203 are densely arranged in a relatively complicated shape such as an uneven portion, a bent portion, and a protruding portion. The specific setting method of the sphere 202 will be described later.
変形写像算出部２０は、領域設定部１０により設定された複数の変形対象領域のそれぞれにおいて、変形対象領域内に含まれる物体形状の各構成点の移動元位置を移動先位置へと変形させるための変形写像を算出する。この変形写像の算出は、特許文献１に記載した手法に基づいて行う。 The deformation map calculation unit 20 deforms the movement source position of each constituent point of the object shape included in the deformation target area to the movement destination position in each of the plurality of deformation target areas set by the area setting unit 10. Calculate the deformed map of. The calculation of this modified map is performed based on the method described in Patent Document 1.
すなわち、変形写像算出部２０は、点群データまたはポリゴンメッシュにより表される物体形状の構成面を滑らかな曲面に変形するための変形写像を、ＲＢＦ（Radial Basis Function：放射基底関数）を用いて表現する。ＲＢＦは、「定点からの距離によって値が定まる関数」である。一般には、ｎ次元ユークリッド空間Ｒｎにおけるノルムを||・||と表すときに、以下の形で表されるｎ変数実数値関数Φ(ｘ)をＲＢＦと呼ぶ。
Φ(ｘ)＝φ（||ｘ−χ||）
ここで、φは１変数の関数である。また、χ∈Ｒｎはｎ次元空間における固定点で、Φ(ｘ)の中心点と呼ぶ。
That is, the deformation map calculation unit 20 uses RBF (Radial Basis Function) to perform a deformation map for transforming the constituent surface of the object shape represented by the point cloud data or the polygon mesh into a smooth curved surface. Express. RBF is a "function whose value is determined by the distance from a fixed point". Generally, when the norm in the n-dimensional Euclidean space R n is expressed as || · ||, the n-variable real-valued function Φ (x) expressed in the following form is called RBF.
Φ (x) = φ (|| x−χ ||)
Here, φ is a one-variable function. Further, χ ∈ R n is a fixed point in the n-dimensional space and is called the central point of Φ (x).
例えば、ｎ個の点χｉ（ｉ＝１，・・・，ｎ）について、それらが行き先の新しい点χ~ｉ（ｉ＝１，・・・，ｎ）に移動するように物体形状を変形させる場合、そのための変形写像Ψを、点χｉを中心点に持つＲＢＦ（Φ(ｘ−χｉ）＝φ(||ｘ−χｉ||)）の１次結合として、次の（式１）のように表す。ここで、係数ａｉ∈Ｒ３（ｉ＝１，・・・，ｎ）は未知ベクトルである。 For example, for n points χ i (i = 1, ..., N), the object shape is deformed so that they move to the new points χ ~ i (i = 1, ..., N) of the destination. In the case of making it, the modified mapping Ψ for that purpose is set as the linear combination of RBF (Φ (x−χ i ) = φ (|| x−χ i ||)) having the point χ i as the center point, and the following (Equation) It is expressed as 1). Here, the coefficient a i ∈ R 3 (i = 1, ..., N) is an unknown vector.
一方、領域設定部１０により設定された変形対象領域（球２０２）に含まれる各構成点２０３をＮ個の点ξj（ｊ＝１，・・・，Ｎ）で表し、これが目標とする行き先の新しい点ξ~j（ｊ＝１，・・・，Ｎ）に移動するものとして、移動後の点ξ~jで形成される物体形状の構成面が凹凸や波打ちのない滑らかな曲面となるような拘束条件を与える。ここで、Ｎ個の点ξjが特許請求の範囲の「空間上の指定された移動元位置」であり、行き先の新しい点ξ~jが「目標とする移動先位置」である。 On the other hand, each constituent point 203 included in the deformation target area (sphere 202) set by the area setting unit 10 is represented by N points ξ j (j = 1, ..., N), and this is the target destination. Assuming that the object moves to the new points ξ ~ j (j = 1, ···, N), the constituent surface of the object shape formed by the moved points ξ ~ j becomes a smooth curved surface without unevenness or waviness. Give such a restraint condition. Here, the N points ξ j are the “designated moving source positions in space” in the claims, and the new destination points ξ to j are the “target moving destination positions”.
本実施形態において与える拘束条件は２つある。１つは、移動元位置の点ξjを（式１）の変形写像式で写像した位置Ψ(ξj)と、点ξ~jで表される目標とする移動先位置との距離ができるだけ小さくなるようにするための位置近似に関する拘束条件である。もう１つは、移動先位置の点ξ~jにより形成される構成面の曲がり方の変化が少なくなるようにするための曲率変化率最小化に関する拘束条件である。 There are two restraint conditions given in this embodiment. One is that the distance between the position Ψ (ξ j ) obtained by mapping the point ξ j of the moving source position by the modified mapping equation of (Equation 1) and the target moving destination position represented by the points ξ to j can be as large as possible. It is a constraint condition for position approximation to make it smaller. The other is a constraint condition for minimizing the rate of change in curvature so that the change in the bending of the constituent surface formed by the points ξ to j at the destination position is small.
前者の位置近似に関する拘束条件は、次の（式２）に示す距離評価値Ｅ0によって表す。 The former constraint condition for position approximation is represented by the distance evaluation value E 0 shown in the following (Equation 2).
また、後者の曲率変化率最小化に関する拘束条件は、変形前の曲面Ｓ上の移動元位置における２つの独立な接ベクトルをｓu，ｓvとして、次の（式３）に示す曲率変化率評価値Ｅfairによって表す。接ベクトルをｓu，ｓvは、変形前曲面ｓ（ｕ，ｖ）上の点における互いに直交するｕ方向・ｖ方向の１階微分ベクトルである。 The latter constraint condition for minimizing the curvature change rate is the curvature change rate shown in the following (Equation 3), where two independent tangent vectors at the movement source position on the curved surface S before deformation are s u and s v. It is represented by the evaluation value E fair . The tangent vectors s u and s v are first-order differential vectors in the u and v directions orthogonal to each other at points on the pre-transformation curved surface s (u, v).
ここで、右辺のｓ~uuu，ｓ~vvv，ｓ~uuv，ｓ~uvvは、変形後曲面の移動先位置における３階微分ベクトルであり、それぞれ次の（式４）で表される。 Here, s ~ uuu , s ~ vvv , s ~ uuv , and s ~ uvv on the right side are third-order differential vectors at the destination position of the deformed curved surface, and are represented by the following (Equation 4), respectively.
上記（式４）において、ＤΨは変形写像Ψの１階微分写像、Ｄ2Ψは２階微分写像、Ｄ3Ψは３階微分写像である。このうち、１階微分写像ＤΨは、次の（式５）のように定義される。なお、ｖは任意のベクトルであり、添え字のαは３変数｛ｘ，ｙ，ｚ｝上を動く。 In the above (Equation 4), D Ψ is the first-order differential map of the modified map Ψ, D 2 Ψ is the second-order differential map, and D 3 Ψ is the third-order differential map. Of these, the first-order differential map DΨ is defined as follows (Equation 5). Note that v is an arbitrary vector, and the subscript α moves on three variables {x, y, z}.
ここで、変形前曲面の微分ベクトルと変形後曲面の微分ベクトルとの関係について説明する。変形前曲面をｓ(ｕ，ｖ)、これを変形写像Ψで変形した変形後曲面をｓ~(ｕ，ｖ)で表すと、次の（式６）に示す関係が成り立つ。
ｓ~(ｕ，ｖ)＝Ψ(ｓ(ｕ，ｖ)) ・・・（式６）
つまり、変形後曲面ｓ~を２変数ｕ，ｖのベクトル値の関数として見ると、これは変形写像Ψと変形前曲面ｓとの合成関数であると言える。そこで、合成関数の微分法を適用することで、変形後曲面の微分ベクトルを求めることができる。
Here, the relationship between the differential vector of the curved surface before deformation and the differential vector of the curved surface after deformation will be described. When the pre-deformation curved surface is represented by s (u, v) and the post-deformation curved surface deformed by the deformation mapping Ψ is represented by s ~ (u, v), the relationship shown in the following (Equation 6) holds.
s ~ (u, v) = Ψ (s (u, v)) ... (Equation 6)
That is, when the deformed curved surface s ~ is viewed as a function of the vector values of the two variables u and v, it can be said that this is a composite function of the deformed map Ψ and the pre-deformed curved surface s. Therefore, by applying the differential method of the composite function, the differential vector of the deformed curved surface can be obtained.
すなわち、変形写像Ψの１階微分写像を上述の（式５）のように定義し、２階微分写像を（式７）のように定義すると（ｖ，ｖ１，ｖ２は任意のベクトルであり、添え字のα，βは３変数ｘ，ｙ，ｚ上を動く）、変形後曲面ｓ~(ｕ，ｖ)＝Ψ(ｓ(ｕ，ｖ))の１階微分ベクトルは次の（式８）のように表され、２階微分ベクトルは次の（式９）のように表される。 That is, if the first-order differential map of the modified map Ψ is defined as in (Equation 5) above and the second-order differential map is defined as in (Equation 7), (v, v 1 , v 2 are arbitrary vectors. Yes, the subscripts α and β move on the three variables x, y, z), and the first derivative vector of the modified curved surface s ~ (u, v) = Ψ (s (u, v)) is as follows ( It is expressed as in Eq. 8), and the second derivative vector is expressed as in (Equation 9) below.
また、変形写像Ψの１階微分写像を上述の（式５）、２階微分写像を上述の（式７）のように定義し、さらに３階微分写像を次の（式１０）のように定義すると（ｖ，ｖ１，ｖ２，ｖ３は任意のベクトルであり、添え字のα，β，γは３変数ｘ，ｙ，ｚ上を動く）、変形後曲面ｓ~(ｕ，ｖ)＝Ψ(ｓ(ｕ，ｖ))の３階微分ベクトルは上述の（式４）のように表される。 Further, the first-order differential map of the modified map Ψ is defined as the above (Equation 5), the second-order differential map is defined as the above (Equation 7), and the third-order differential map is further defined as the following (Equation 10). By definition (v, v 1 , v 2 , v 3 are arbitrary vectors, and the subscripts α, β, γ move on the three variables x, y, z), the modified curved surface s ~ (u, v). The third-order differential vector of) = Ψ (s (u, v)) is expressed as in (Equation 4) above.
本実施形態では、次の（式１１）に示すように、距離評価値Ｅ0と曲率変化率評価値Ｅfairとを重みづけ加算した総合評価値Ｅtotalを定義し、この総合評価値Ｅtotalを最小化するという拘束条件を設定する。重みｗは、球の半径の６乗（球の断面である円の面積の３乗）に比例するように定める。これにより、大きい球ではより強く平滑化を行い、小さい球では弱く平滑化を行うこととなり、全体として整合性を保った平滑化結果形状を得ることができる。さらに、比例係数の大小により、全体的な平滑化の強さをユーザがコントロールすることができる。 In the present embodiment, as shown in the following equation (11), the distance evaluation value E 0 and the curvature change rate evaluation value E fair defines the comprehensive evaluation value E total obtained by adding weighted, the comprehensive evaluation value E total Set a constraint condition to minimize. The weight w is determined to be proportional to the sixth power of the radius of the sphere (the third power of the area of the circle which is the cross section of the sphere). As a result, the large sphere is smoothed more strongly, and the small sphere is weakly smoothed, so that a smoothed result shape that maintains consistency as a whole can be obtained. Further, the strength of the overall smoothing can be controlled by the user depending on the magnitude of the proportionality coefficient.
上記（式１）で表される変形写像Ψの中で、この（式１１）に示す評価値を最小化するものを求めることにより、未知ベクトルａi（ｉ＝１，・・・，ｎ）が求められ、目的の変形写像Ψが確定する。例えば、移動対象とする空間上にあるＮ個の拘束点ξjについて（式１）の連立１次方程式を解くことによって変形写像Ψが求まれば、その空間上の拘束点ではない点についても、それらがどこに移動するかを計算することができるようになる。すなわち、変形写像Ψが求まるということは、空間のどの点に対しても移動先が決まるということである。 The unknown vector a i (i = 1, ..., N) is obtained by finding the modified mapping Ψ represented by the above (Equation 1) that minimizes the evaluation value shown in this (Equation 11). Is obtained, and the desired modified map Ψ is determined. For example, if the deformation map Ψ is obtained by solving the simultaneous linear equations of (Equation 1) for N constraint points ξ j in the space to be moved, the points that are not the constraint points in the space are also obtained. , You will be able to calculate where they will move. That is, the fact that the deformed map Ψ can be obtained means that the destination is determined for any point in space.
図１に示す変形写像設定部２１は、上記（式１）に示したような、ＲＢＦの１次結合で表わした位置連続に関する項を含む変形写像式を設定する。すなわち、（式１）に対して、未知数ａi以外の値であるＲＢＦの中心点χi（ｉ＝１，・・・，ｎ）を設定することにより、変形写像式を設定する。ここで、ｎ個の中心点χiは、領域設定部１０により設定された変形対象領域の中から変形写像設定部２１が自動的に設定する。 The modified mapping setting unit 21 shown in FIG. 1 sets a modified mapping equation including a term relating to position continuity represented by a linear combination of RBFs as shown in the above (Equation 1). That is, the modified mapping equation is set by setting the center point χ i (i = 1, ..., N) of the RBF, which is a value other than the unknown number a i , with respect to (Equation 1). Here, the n center points χ i are automatically set by the deformation mapping setting unit 21 from the deformation target areas set by the area setting unit 10.
拘束条件設定部２２は、移動元位置の点ξjを（式１）の変形写像式で写像した位置の点Ψ(ξj)と目標とする移動先位置の点ξ~jとの距離を表した位置近似の距離評価値Ｅ0、および、変形結果形状の曲率変化率評価値Ｅfairとを含む拘束条件方程式（上述した（式１１））を設定する。すなわち、（式１１）に対して、距離評価値Ｅ0に含まれるξj，ξ~jと、曲率変化率評価値Ｅfairに含まれるｓ~uuu，ｓ~vvv，ｓ~uuv，ｓ~uvvと、重みｗとを設定することにより、拘束条件方程式を設定する。 The constraint condition setting unit 22 sets the distance between the point Ψ (ξ j ) at the position where the point ξ j at the moving source position is mapped by the modified mapping equation of (Equation 1) and the points ξ ~ j at the target moving destination position. A constraint condition equation (the above-mentioned (Equation 11)) including the distance evaluation value E 0 of the represented position approximation and the curvature change rate evaluation value E fair of the deformation result shape is set. That is, with respect to (Equation 11), ξ j , ξ ~ j included in the distance evaluation value E 0 and s ~ uuu , s ~ vvv , s ~ uuv , s ~ included in the curvature change rate evaluation value E fair. The constraint equation is set by setting uvv and the weight w.
変形写像確定部２３は、拘束条件設定部２２により設定された拘束条件方程式を解いて、変形写像設定部２１により設定された変形写像式に含まれる未知数ａiを求めることにより、位置近似および曲率変化率最小化を満たす変形写像Ψを確定させる。具体的には、変形写像確定部２３は、上述の（式１１）で示される総合評価値Ｅtotalを最小化するような（式１）の未知数ａiを求めることにより、変形写像Ψを確定させる。 The deformation mapping determination unit 23 solves the constraint condition equation set by the constraint condition setting unit 22 and obtains the unknown number a i included in the deformation mapping equation set by the deformation map setting unit 21 to perform position approximation and curvature. Establish a deformation map Ψ that satisfies the rate of change minimization. Specifically, the deformation mapping determination unit 23 determines the deformation mapping Ψ by obtaining the unknown number a i of (Equation 1) that minimizes the total evaluation value E total represented by the above (Equation 11). Let me.
形状変形部３０は、変形写像算出部２０により変形対象領域（球２０２）ごとに算出された変形写像Ψを用いて、球２０２内に含まれる物体形状を変形させる処理を実行する。すなわち、形状変形部３０は、球２０２内の各点に対して変形写像Ψを適用して移動先位置の点を求めることにより、物体形状を変形させる。これにより、球２０２内の形状が凹凸や波打ちのない滑らかな構成面となるような形状変形が実行される。 The shape deformation unit 30 executes a process of deforming the shape of the object contained in the sphere 202 by using the deformation map Ψ calculated for each deformation target area (sphere 202) by the deformation map calculation unit 20. That is, the shape deforming unit 30 deforms the object shape by applying the deformation mapping Ψ to each point in the sphere 202 to obtain the point at the movement destination position. As a result, shape deformation is executed so that the shape inside the sphere 202 becomes a smooth constituent surface without unevenness or waviness.
また、形状変形部３０は、変形対象領域がオーバーラップする重複領域内に含まれる形状部分の構成点については、各変形対象領域について算出された変形写像Ψによるそれぞれの移動先の重み付き平均により移動先位置を決定する。図３は、この重み付け平均の概要を説明するための図である。 Further, the shape deformation unit 30 uses the weighted average of each movement destination by the deformation mapping Ψ calculated for each deformation target area for the constituent points of the shape portion included in the overlapping areas where the deformation target areas overlap. Determine the destination position. FIG. 3 is a diagram for explaining an outline of this weighted average.
図３に示すように、変形対象領域としての２つの球ＢＬ1，ＢＬ2がオーバーラップしていて、そのオーバーラップ領域内に構成点Ｐがあるものとする。点Ｐは、一方の球ＢＬ1にも属し、他方の球ＢＬ2にも属する点である。変形写像算出部２０により、２つの球ＢＬ1，ＢＬ2のそれぞれについて変形写像Ψ1，Ψ2が算出されている。形状変形部３０は、点Ｐを移動元位置として、変形写像Ψ1，Ψ2により移動先位置Ｑ1，Ｑ2をそれぞれ算出し、この移動先位置Ｑ1，Ｑ2を重み付き平均化することにより、点Ｐの移動先位置を決定する。なお、重み付き平均計算の詳細については後述する。 As shown in FIG. 3, it is assumed that the two spheres BL 1 and BL 2 as the deformation target regions overlap and the constituent point P is in the overlapping region. The point P is a point that belongs to one sphere BL 1 and also belongs to the other sphere BL 2 . The deformation map calculation unit 20 calculates the deformation maps Ψ 1 and Ψ 2 for each of the two spheres BL 1 and BL 2 . Shape deformation unit 30, a movement source position the point P, deformation maps [psi 1, the destination position Q 1, Q 2 each calculated by [psi 2, to the weighted averages of the destination position Q 1, Q 2 This determines the destination position of the point P. The details of the weighted average calculation will be described later.
＜各機能ブロックの詳細構成＞
次に、図１に示した領域設定部１０、変形写像算出部２０および形状変形部３０の詳細な構成について説明する。
<Detailed configuration of each functional block>
Next, the detailed configuration of the area setting unit 10, the deformation map calculation unit 20, and the shape deformation unit 30 shown in FIG. 1 will be described.
＜領域設定部１０の詳細な構成例＞
まず、領域設定部１０の詳細な構成例について説明する。図４は、領域設定部１０の具体的な機能構成例を示すブロック図である。図４に示すように、本実施形態の領域設定部１０は、その具体的な機能構成として、球設定部１１、球分割部１２および隣接関係生成部１３を備えている。
<Detailed configuration example of the area setting unit 10>
First, a detailed configuration example of the area setting unit 10 will be described. FIG. 4 is a block diagram showing a specific functional configuration example of the area setting unit 10. As shown in FIG. 4, the area setting unit 10 of the present embodiment includes a sphere setting unit 11, a sphere division unit 12, and an adjacency relationship generation unit 13 as specific functional configurations thereof.
球設定部１１は、点群データまたはポリゴンメッシュにより表される物体形状の形状データに対して、１つのボックス内に含まれる複数の構成点の数が所定範囲内（例えば、１００±ｎ個程度の範囲内）となるまで分割を繰り返すことにより、複数の包含ボックスを設定し、それぞれの包含ボックスごとに、当該包含ボックスを内包する球を設定する。 In the sphere setting unit 11, the number of a plurality of constituent points included in one box is within a predetermined range (for example, about 100 ± n) with respect to the point cloud data or the shape data of the object shape represented by the polygon mesh. By repeating the division until it becomes (within the range of), a plurality of inclusion boxes are set, and a sphere containing the inclusion box is set for each inclusion box.
本実施形態では一例として、ＢＶＨ（Bounding Volume Hierarchy）を用いた２分木分割構造による複数の包含ボックスを設定し、ツリーのリーフノードに相当する包含ボックスごとに、これを内包する球を設定する。包含ボックスとは、形状データの一部分を表す点群またはポリゴンメッシュを包含する直方体である。包含ボックスを内包する球とは、直方体の中心点を中心とし、その点から最も遠い角までの長さを半径とする球のことである。 In the present embodiment, as an example, a plurality of inclusion boxes by a binary tree division structure using BVH (Bounding Volume Hierarchy) are set, and a sphere containing the inclusion boxes corresponding to leaf nodes of the tree is set. .. An inclusion box is a rectangular parallelepiped that includes a point cloud or polygon mesh that represents a part of shape data. A sphere containing an inclusion box is a sphere whose center is the center point of a rectangular parallelepiped and whose radius is the length from that point to the farthest angle.
図５は、球設定部１１による処理内容を説明するための模式図である。なお、説明を簡便にするために、図５では、立体の物体形状５０１を一方向から見た平面で表し、包含ボックスの直方体は長方形で表している。 FIG. 5 is a schematic diagram for explaining the processing contents by the sphere setting unit 11. For the sake of simplicity, in FIG. 5, the three-dimensional object shape 501 is represented by a plane viewed from one direction, and the rectangular parallelepiped of the inclusion box is represented by a rectangle.
図５に示すように、まず、２分木分割構造の１階層目に当たるルートノードでは、物体形状５０１の全体を覆う（例えば、物体形状５０１が内接する）ような大きな包含ボックスＢＸ1を設定する。次に、２階層目において包含ボックスＢＸ1を２つの包含ボックスＢＸ21，ＢＸ22に分割する。次いで、３階層目において包含ボックスＢＸ21を２つの包含ボックスＢＸ31，ＢＸ32に分割するとともに、包含ボックスＢＸ22を２つの包含ボックスＢＸ33，ＢＸ34に分割する。さらに、４階層目において包含ボックスＢＸ32を２つの包含ボックスＢＸ41，ＢＸ42に分割するとともに、包含ボックスＢＸ33を２つの包含ボックスＢＸ43，ＢＸ44に分割する。 As shown in FIG. 5, first, in the root node corresponding to the first layer of the binary tree division structure, a large inclusion box BX 1 is set so as to cover the entire object shape 501 (for example, the object shape 501 is inscribed). .. Next, in the second layer, the inclusion box BX 1 is divided into two inclusion boxes BX 21 and BX 22 . Next, in the third layer, the containing box BX 21 is divided into two containing boxes BX 31 and BX 32 , and the containing box BX 22 is divided into two containing boxes BX 33 and BX 34 . Further, in the fourth layer, the inclusion box BX 32 is divided into two inclusion boxes BX 41 and BX 42 , and the inclusion box BX 33 is divided into two inclusion boxes BX 43 and BX 44 .
このように、再帰的に分割処理を行うことで二分木構造にした結果、図５の例では、６つの包含ボックスＢＸ31，ＢＸ34，ＢＸ41，ＢＸ42，ＢＸ43，ＢＸ44がリーフノードとなる。これらのリーフノードに相当する包含ボックスＢＸ31，ＢＸ34，ＢＸ41，ＢＸ42，ＢＸ43，ＢＸ44は、何れもその中に含まれる複数の構成点の数が所定範囲内（例えば、１００±ｎ個程度の範囲内）となっている。 As a result of recursively dividing the tree into a binary tree structure in this way, in the example of FIG. 5, six inclusion boxes BX 31 , BX 34 , BX 41 , BX 42 , BX 43 , and BX 44 are leaf nodes. It becomes. In the inclusion boxes BX 31 , BX 34 , BX 41 , BX 42 , BX 43 , and BX 44 corresponding to these leaf nodes, the number of a plurality of constituent points contained therein is within a predetermined range (for example, 100 ±). Within the range of about n).
球設定部１１は、これら６つの包含ボックスＢＸ31，ＢＸ34，ＢＸ41，ＢＸ42，ＢＸ43，ＢＸ44に対して、これを内包する６つの球をそれぞれ設定する。この場合、３階層目の包含ボックスＢＸ31，ＢＸ34に対して設定される球は比較的大きくなり、４階層目の包含ボックスＢＸ41，ＢＸ42，ＢＸ43，ＢＸ44に対して設定される球は比較的小さくなる。すなわち、比較的平坦な形状のところには大きな半径の球が設定され、比較的複雑な形状のところには小さな半径の球が設定されることになる。 The sphere setting unit 11 sets six spheres containing the six inclusion boxes BX 31 , BX 34 , BX 41 , BX 42 , BX 43 , and BX 44 , respectively. In this case, the spheres set for the inclusion boxes BX 31 and BX 34 in the third layer are relatively large, and are set for the inclusion boxes BX 41 , BX 42 , BX 43 , and BX 44 in the fourth layer. The sphere is relatively small. That is, a sphere having a large radius is set in a relatively flat shape, and a sphere having a small radius is set in a relatively complicated shape.
なお、ここでは、ＢＶＨを用いた２分木分割構造によって複数の包含ボックスを設定する例について説明したが、本発明はこれに限定されない。例えば、ＢＶＨに代えて、８分木やｋｄ−ｔｒｅｅ等を用いてもよい。 Although an example in which a plurality of inclusion boxes are set by a binary tree division structure using BVH has been described here, the present invention is not limited to this. For example, instead of BVH, an ocree tree, kd-tree, or the like may be used.
球分割部１２は、球設定部１１により設定された球内に含まれる複数の構成点と最小２乗平面との距離誤差を算出し、当該誤差の算出値が第１の所定値より大きい球を更に分割する。誤差の算出に関しては、種々の方法を適用することが可能である。一例として、球分割部１２は、図６に示すように、球設定部１１により設定された球内に含まれる複数の構成点ｓ1〜ｓNから最小２乗平面６０１を生成し、当該最小２乗平面６０１と複数の構成点ｓ1〜ｓNとの距離ｄ1〜ｄNがそれぞれ第１の所定値より大きいか否かを判定する。そして、所定数以上の構成点について距離が第１の所定値より大きくなる場合は、その球は精度が不十分であると判断し、これを複数のより小さい球に分割する。 The sphere dividing unit 12 calculates a distance error between a plurality of constituent points included in the sphere set by the sphere setting unit 11 and the least squares plane, and the calculated value of the error is larger than the first predetermined value. Is further divided. Various methods can be applied to the calculation of the error. As an example, as shown in FIG. 6, the sphere dividing unit 12 generates a least squares plane 601 from a plurality of constituent points s 1 to s N included in the sphere set by the sphere setting unit 11, and the minimum squared plane 601 is generated. It is determined whether or not the distances d 1 to d N between the square plane 601 and the plurality of constituent points s 1 to s N are larger than the first predetermined value, respectively. Then, when the distance becomes larger than the first predetermined value for the predetermined number or more of the constituent points, it is determined that the accuracy of the sphere is insufficient, and this is divided into a plurality of smaller spheres.
本実施形態では、第１の所定値として、球の半径に対して一定割合（例えば、３０％）の値を用いる。また、本実施形態では、最小２乗平面６０１と構成点ｓ1〜ｓNとの距離が第１の所定値より大きい球を、４個の小さい球に分割する。分割した球についても同様の判定を行い、精度が不十分であれば更に分割する。なお、全ての球について精度が良くなるまで分割を繰り返してもよいが、処理効率を考慮して、上限の分割回数を定めてもよいし、固定回数（例えば、４回）だけ分割を行うようにしてもよい。 In the present embodiment, as the first predetermined value, a value at a constant ratio (for example, 30%) with respect to the radius of the sphere is used. Further, in the present embodiment, a sphere in which the distance between the least squares plane 601 and the constituent points s 1 to s N is larger than the first predetermined value is divided into four small spheres. The same judgment is made for the divided spheres, and if the accuracy is insufficient, the spheres are further divided. The division may be repeated until the accuracy is improved for all the spheres, but the upper limit of the number of divisions may be set in consideration of the processing efficiency, or the division may be performed only a fixed number of times (for example, 4 times). It may be.
なお、図６において、ｓ1〜ｓNは、１つの球内に含まれるＮ個の構成点を示している。形状変形部３０により変形が行われる前の物体形状は、その表面に凹凸を有しているため、Ｎ個の構成点ｓ1〜ｓNは波打った位置に存在している。球分割部１２は、これらＮ個の構成点ｓ1〜ｓNから最小２乗法により近似平面（最小２乗平面）６０１を生成する。そして、球分割部１２は、Ｎ個の構成点ｓ1〜ｓNと最小２乗平面６０１との距離ｄ1〜ｄNをそれぞれ求め、第１の所定値より大きくなるものが存在するか否かを判定する。 In FIG. 6, s 1 to s N indicate N constituent points contained in one sphere. Since the shape of the object before being deformed by the shape deforming portion 30 has irregularities on its surface, N constituent points s 1 to s N exist at wavy positions. The sphere dividing unit 12 generates an approximate plane (least squares plane) 601 from these N constituent points s 1 to s N by the method of least squares. Then, whether spherical division unit 12 obtains a distance d 1 to d N of the N control points s 1 ~s N and the least square plane 601 respectively, there is made larger than the first predetermined value Is determined.
また、球分割部１２は、物体形状の形状データがポリゴンデータまたは法線付き点群データの場合には、分割によって最終的に生成される球内に含まれる複数の構成点の法線ベクトルがほぼ同じ方向を向くように、球の分割を行う。すなわち、球分割部１２は、球内に含まれる複数の構成点の法線ベクトルの方向の相違度合を算出し、当該相違度合の算出値が第２の所定値より大きい場合には、その球を更により小さい球に分割する。 Further, in the sphere dividing unit 12, when the shape data of the object shape is polygon data or point cloud data with normals, the normal vectors of a plurality of constituent points included in the sphere finally generated by the division are obtained. Divide the sphere so that it faces in almost the same direction. That is, the sphere dividing unit 12 calculates the degree of difference in the direction of the normal vectors of the plurality of constituent points included in the sphere, and when the calculated value of the degree of difference is larger than the second predetermined value, the sphere. Is further divided into smaller spheres.
例えば、球分割部１２は、図６のように球内に含まれる複数の構成点ｓ1〜ｓNから最小２乗平面６０１を生成し、当該最小２乗平面６０１の法線ベクトルの方向と、複数の構成点ｓ1〜ｓNの法線ベクトルの方向との誤差が第２の所定値より大きいか否かを判定し、所定数以上の構成点について誤差が第２の所定値より大きくなる球を更に分割する。 For example, the sphere dividing unit 12 generates a least squares plane 601 from a plurality of constituent points s 1 to s N included in the sphere as shown in FIG. 6, and sets the direction of the normal vector of the least squares plane 601. , It is determined whether or not the error between the directions of the normal vectors of the plurality of constituent points s 1 to s N is larger than the second predetermined value, and the error is larger than the second predetermined value for the predetermined number or more of the constituent points. The sphere is further divided.
これにより、球分割部１２は、複数の構成点ｓ1〜ｓNから求められる最小２乗平面６０１の法線ベクトルの方向を、物体形状の表方向と一致させるように球の分割を行う。例えば、球分割部１２は、最小２乗平面６０１の法線ベクトルと球内の各構成点ｓ1〜ｓNの法線ベクトルとの内積が√３／２以上（角度の誤差が３０度以下）でない場合は、その球を更に分割する。このような分割を行うことにより、１つの球内に、法線ベクトルの方向が逆を向く構成点が含まれないようになる。 As a result, the sphere dividing unit 12 divides the sphere so that the direction of the normal vector of the least squares plane 601 obtained from the plurality of constituent points s 1 to s N matches the front direction of the object shape. For example, in the sphere dividing unit 12, the inner product of the normal vector of the least squares plane 601 and the normal vector of each constituent point s 1 to s N in the sphere is √3 / 2 or more (angle error is 30 degrees or less). ), The sphere is further divided. By performing such division, the constituent points in which the directions of the normal vectors are opposite to each other are not included in one sphere.
隣接関係生成部１３は、球設定部１１および球分割部１２によって生成された球どうしの隣接関係に関するデータを生成する。すなわち、隣接関係生成部１３は、各球と、その近傍に存在する別の球との間における隣接関係のデータを生成する。図７に示すように、球ＢＬ2が球ＢＬ1に隣接して存在するとは、この２つの球ＢＬ1，ＢＬ2の中心点Ｃ1，Ｃ2間の距離Ｄが、球ＢＬ1，ＢＬ2のそれぞれの半径Ｒ1，Ｒ2の和よりも小さいことをいう。 The adjacency relationship generation unit 13 generates data regarding the adjacency relationship between the spheres generated by the sphere setting unit 11 and the sphere division unit 12. That is, the adjacency relationship generation unit 13 generates data on the adjacency relationship between each sphere and another sphere existing in the vicinity thereof. As shown in FIG. 7, the fact that the sphere BL 2 exists adjacent to the sphere BL 1 means that the distance D between the center points C 1 and C 2 of the two spheres BL 1 and BL 2 is the spheres BL 1 and BL 2. It means that it is smaller than the sum of the radii R 1 and R 2 of 2 respectively.
ただし、物体形状の形状データがポリゴンデータまたは法線付き点群データ で構成される場合には、球ＢＬ2が球ＢＬ1に隣接して存在しても、ただちにこの２つの球ＢＬ1，ＢＬ2の間に隣接関係を構築するわけではない。すなわち、２つの球ＢＬ1，ＢＬ2の最小２乗平面の法線ベクトルの方向（表・裏）が一致する場合にのみ、隣接関係を構築する。 However, when the shape data of the object shape is composed of polygon data or normal line with point group data may be ball BL 2 are present adjacent to the ball BL 1, immediately the two spheres BL 1, BL It does not build an adjacency between the two . That is, the adjacency relationship is constructed only when the directions (front and back) of the normal vectors of the least squares planes of the two spheres BL 1 and BL 2 match.
２つの球ＢＬ1，ＢＬ2が隣接関係にあるとき、隣接関係生成部１３は、一方の球を他方の球の「隣接球集合」に入れる。すなわち、球ＢＬ2を他方の球ＢＬ1の「隣接球集合」に入れる。また、球ＢＬ1を他方の球ＢＬ2の「隣接球集合」に入れる。さらに、隣接関係生成部１３は、一方の球に所属する構成点から他方の球の中心までの距離が他方の球の半径よりも小さいとき、つまり、一方の球の構成点が球ＢＬ1，ＢＬ2のオーバーラップ領域に含まれるとき、その構成点を他方の球の「所属点集合」に入れる。例えば、図７のように球ＢＬ1，ＢＬ2のオーバーラップ領域に所属する球ＢＬ1の構成点ｓ1を、他方の球ＢＬ2の「所属点集合」に入れる。 When the two spheres BL 1 and BL 2 are in an adjacency relationship, the adjacency relationship generation unit 13 puts one sphere into the "adjacent sphere set" of the other sphere. That is, the sphere BL 2 is put into the "adjacent sphere set" of the other sphere BL 1 . Also, the sphere BL 1 is put into the "adjacent sphere set" of the other sphere BL 2 . Further, when the distance from the constituent point belonging to one sphere to the center of the other sphere is smaller than the radius of the other sphere, that is, the constituent point of one sphere is the sphere BL 1 , When it is included in the overlap region of BL 2 , its constituent points are put into the "affiliation point set" of the other sphere. For example, a configuration point s 1 sphere BL 1 belonging to the overlap region of the sphere BL 1, BL 2 as shown in FIG. 7, placed in "belonging point set" of the other balls BL 2.
＜変形写像算出部２０の詳細な構成例＞
次に、変形写像算出部２０の詳細な構成例について説明する。図８は、変形写像算出部２０の具体的な機能構成例を示すブロック図である。なお、図８において、図１に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。図８に示すように、変形写像算出部２０は、その具体的な機能構成として、図１に示した構成に加え、近似平面生成部２４、投影点算出部２５および中心点抽出部２６をさらに備えている。
<Detailed configuration example of the modified map calculation unit 20>
Next, a detailed configuration example of the modified map calculation unit 20 will be described. FIG. 8 is a block diagram showing a specific functional configuration example of the modified map calculation unit 20. Note that, in FIG. 8, those having the same reference numerals as those shown in FIG. 1 have the same functions, and therefore, duplicate description will be omitted here. As shown in FIG. 8, as a specific functional configuration thereof, the deformation mapping calculation unit 20 further includes an approximate plane generation unit 24, a projection point calculation unit 25, and a center point extraction unit 26 in addition to the configuration shown in FIG. I have.
近似平面生成部２４は、領域設定部１０により変形対象領域として設定された球に含まれる複数の構成点に対する近似平面を生成する。本実施形態において、近似平面の生成法は特に限定しないが、一例として、図６に示したように、複数の構成点に最小２乗法を適用して近似平面（最小２乗平面６０１）を生成することが可能である。なお、この最小２乗平面６０１は、球分割部１２が球を分割するか否かを判定する際に生成したものを用いてもよい。その場合、近似平面生成部２４は省略が可能である。 The approximate plane generation unit 24 generates approximate planes for a plurality of constituent points included in the sphere set as the deformation target region by the region setting unit 10. In the present embodiment, the method of generating the approximate plane is not particularly limited, but as an example, as shown in FIG. 6, the least squares method is applied to a plurality of constituent points to generate the approximate plane (minimum square plane 601). It is possible to do. As the least squares plane 601, the one generated when the sphere dividing portion 12 determines whether or not to divide the sphere may be used. In that case, the approximate plane generation unit 24 can be omitted.
投影点算出部２５は、複数の構成点をそれぞれ近似平面上に投影することにより、複数の投影点を算出する。例えば、投影点算出部２５は、構成点から近似平面に対して垂線を下し、その垂線と近似平面との交点を投影点として設定する。 The projection point calculation unit 25 calculates a plurality of projection points by projecting the plurality of constituent points on the approximate plane. For example, the projection point calculation unit 25 draws a perpendicular line from the constituent points with respect to the approximate plane, and sets the intersection of the perpendicular line and the approximate plane as a projection point.
図９は、近似平面生成部２４および投影点算出部２５の処理内容を説明するための図である。図９において、ｓ1〜ｓNは、１つの球内に含まれるＮ個の構成点を示している。近似平面生成部２４は、これらＮ個の構成点ｓ1〜ｓNから最小２乗法により近似平面６０１を生成する。そして、投影点算出部２５は、Ｎ個の構成点ｓ1〜ｓNから近似平面６０１に対してそれぞれ垂線を下ろし、その垂線と近似平面６０１との交点をＮ個の投影点ｐ1〜ｐNとして設定する。 FIG. 9 is a diagram for explaining the processing contents of the approximate plane generation unit 24 and the projection point calculation unit 25. In FIG. 9, s 1 to s N indicate N constituent points contained in one sphere. The approximate plane generation unit 24 generates an approximate plane 601 from these N constituent points s 1 to s N by the method of least squares. Then, the projection point calculation unit 25 draws a perpendicular line from each of the N constituent points s 1 to s N with respect to the approximate plane 601 and sets the intersection of the perpendicular line and the approximate plane 601 at N projection points p 1 to p. Set as N.
拘束条件設定部２２は、投影点算出部２５により算出されたＮ個の投影点ｐ1〜ｐNをそれぞれ移動元位置の点ξj（ｊ＝１，・・・，Ｎ）として指定する。また、拘束条件設定部２２は、領域設定部１０により設定された球内に含まれるＮ個の構成点ｓ1〜ｓNをそれぞれ、複数の投影点ｐ1〜ｐNに対する目標の移動先位置の点ξ~j（ｊ＝１，・・・，Ｎ）として指定して、位置近似および曲率変化率最小化に関する拘束条件方程式を設定する。 Constraint condition setting unit 22 specifies the N-number of the projection point p 1 ~p N calculated by the projection point calculating section 25 as the point of the source positions, respectively ξ j (j = 1, ··· , N). Also, constraint condition setting unit 22 each set of N control points contained within a sphere s 1 ~s N a by the area setting unit 10, the target destination position of for a plurality of projection points p 1 ~p N Specify as points ξ ~ j (j = 1, ..., N) of, and set the constraint equations for position approximation and curvature change rate minimization.
中心点抽出部２６は、近似平面生成部２４により生成された近似平面６０１内から複数のＲＢＦの中心点χi（ｉ＝１，・・・，ｎ）を抽出する。本実施形態において、中心点χiの抽出法は特に限定しないが、近似平面６０１内からほぼ均等に複数の中心点χiを抽出するのが好ましい。 The center point extraction unit 26 extracts the center points χ i (i = 1, ..., N) of a plurality of RBFs from the approximate plane 601 generated by the approximate plane generation unit 24. In the present embodiment, the extraction method of the center point χ i is not particularly limited, but it is preferable to extract a plurality of center points χ i substantially evenly from the approximate plane 601.
例えば、中心点抽出部２６は、近似平面生成部２４により生成された近似平面６０１を格子状に分割し、各格子点（格子の隅の各点）を１つずつ抽出する。上述の変形写像設定部２１は、中心点抽出部２６により抽出されたｎ個のＲＢＦの中心点χi（ｉ＝１，・・・，ｎ）を、（式１）に示す変形写像式における位置連続に関する項Φ(ｘ−χｉ）に設定する。 For example, the center point extraction unit 26 divides the approximate plane 601 generated by the approximate plane generation unit 24 into a grid pattern, and extracts each grid point (each point at the corner of the grid) one by one. The above-mentioned modified mapping setting unit 21 sets the center points χ i (i = 1, ..., N) of n RBFs extracted by the center point extracting unit 26 in the modified mapping equation shown in (Equation 1). Set to the term Φ (x-χ i ) related to position continuity.
＜形状変形部３０の詳細な構成例＞
次に、形状変形部３０の詳細な構成例について説明する。上述のように、形状変形部３０は、各球内に含まれる構成点を移動元位置の点として、各構成点に対して、変形写像算出部２０により個々の球ごとに算出された変形写像Ψを適用して移動先位置の点を求めることにより、物体形状を変形させる。このとき、形状変形部３０は、変形対象領域がオーバーラップする重複領域内に含まれる形状部分の構成点については、変形写像Ψによるそれぞれの移動先の重み付き平均により移動先位置を決定する。
<Detailed configuration example of the shape deforming portion 30>
Next, a detailed configuration example of the shape deforming portion 30 will be described. As described above, the shape deformation unit 30 uses the constituent points included in each sphere as points of the movement source position, and the deformed mapping calculated for each constituent point by the deformation mapping calculation unit 20 for each constituent point. The shape of the object is deformed by applying Ψ to find the point at the destination position. At this time, the shape deformation unit 30 determines the movement destination position of the constituent points of the shape portion included in the overlapping region where the deformation target regions overlap, by the weighted average of the movement destinations according to the deformation mapping Ψ.
例えば、図１０に示すように、球ＢＬに対してｎ個（図１０はｎ＝５の例）の他の球ＢＬi（ｉ＝１〜ｎ）が隣接している場合、球ＢＬに含まれる構成点ｓの移動先の点Ｑは、次の（式１２）により算出される。 For example, as shown in FIG. 10, when n other spheres BL i (i = 1 to n) adjacent to the sphere BL (FIG. 10 is an example of n = 5) are included in the sphere BL. The destination point Q of the constituent point s is calculated by the following (Equation 12).
上記（式１２）において、ｐは球ＢＬ内における構成点ｓの最小２乗平面への投影点、Ψ(ｐ)は当該投影点ｐを変形写像Ψにより写像した先の点を示す。また、ｐiは各球ＢＬi（ｉ＝１〜ｎ）内における構成点ｓiの最小２乗平面への投影点、Ψi(ｐi)は当該投影点ｐiを変形写像Ψiにより写像した先の点を示す。また、（式１２）に含まれる関数ｇ(x)は、次の条件を満たす重み関数である。
ｇ(0)＝０，ｇ(1)＝１，ｇ’(0)＝ｇ’(1)＝０
０≦ｇ(x)≦１（０≦x≦１）
ただし、ｇ’(x)は１階微分を示す。
In the above (Equation 12), p indicates a projection point of the constituent points s in the sphere BL on the least squares plane, and Ψ (p) indicates a point at which the projection point p is mapped by the modified mapping Ψ. Further, p i is the projection point of the constituent point s i on the minimum square plane in each sphere BL i (i = 1 to n), and Ψ i ( pi ) is the projection point p i by the deformation map Ψ i. Indicates the point to be mapped. Further, the function g (x) included in (Equation 12) is a weight function that satisfies the following conditions.
g (0) = 0, g (1) = 1, g'(0) = g'(1) = 0
0 ≤ g (x) ≤ 1 (0 ≤ x ≤ 1)
However, g'(x) indicates the first derivative.
本実施形態では、上記条件を満たす重み関数の一例として、次の（式１３）に示す関数ｇ(x)を用いる。そして、球ＢＬについてはｘ＝（ｒ−ｄ）／ｒ、球ＢＬに隣接する各球ＢＬiについてはｘ＝（ｒi−ｄi）／ｒiを用いる。ここで、ｒは球ＢＬの半径、ｒiは球ＢＬiの半径、ｄは構成点ｓと球ＢＬの中心点Ｃとの距離、ｄiは構成点ｓと球ＢＬiの中心点Ｃiとの距離である。図１０には、球ＢＬ2に関する半径ｒ2および距離ｄ2が示されている。 In this embodiment, the function g (x) shown in the following (Equation 13) is used as an example of the weighting function satisfying the above conditions. Then, the ball BL are x = (r-d) / r, for each sphere BL i adjacent to the ball BL x = using (r i -d i) / r i. Here, r the radius of the sphere BL, r i is the radius of the sphere BL i, d is the distance between the center point C of the constituting point s and the ball BL, d i is the center point C i of component points s and the ball BL i Is the distance to. FIG. 10 shows the radius r 2 and the distance d 2 with respect to the sphere BL 2 .
上記（式１３）に示す重み関数ｇ(x)は、図１１のように表される。これにより、重み関数ｇ(x)の値は、構成点ｓの位置が球ＢＬの中心点Ｃに近いほど大きくなり、中心点Ｃの位置と一致すると（ｄ＝０）、ｇ(x)＝ｇ(1)＝１となる。逆に、構成点ｓの位置が球ＢＬの中心点Ｃから遠いほど、重み関数ｇ(x)の値は小さくなり、球ＢＬの周面の位置と一致すると（ｄ＝ｒ）、ｇ(x) ＝ｇ(0)＝０となる。また、ｇ’(0)＝ｇ’(1)＝０であるから、球ＢＬと球ＢＬiとのオーバーラップ部分における形状の滑らかさが保証されている。 The weighting function g (x) shown in the above (Equation 13) is represented as shown in FIG. As a result, the value of the weighting function g (x) becomes larger as the position of the constituent point s is closer to the center point C of the sphere BL, and when it coincides with the position of the center point C (d = 0), g (x) = g (1) = 1. On the contrary, the farther the position of the constituent point s is from the center point C of the sphere BL, the smaller the value of the weight function g (x) becomes, and when it coincides with the position of the peripheral surface of the sphere BL (d = r), g (x). ) = G (0) = 0. Further, since g'(0) = g'(1) = 0, the smoothness of the shape at the overlapping portion between the sphere BL and the sphere BL i is guaranteed.
以上詳しく説明したように、本実施形態によれば、処理対象の物体形状が複数の互いにオーバーラップする変形対象領域（球）に分割され、それぞれの変形対象領域内において変形写像Ψによる物体形状の変形が行われることにより、滑らかな形状に平滑化される。また、変形対象領域どうしのオーバーラップ部分に関しては、各変形対象領域の変形写像Ψ，Ψi（ｉ＝１〜ｎ）により算出される移動先の重み付き平均により移動先位置が決定されるので、オーバーラップ部分で段差や折れが生じないようにすることができる。これにより、本実施形態によれば、ユーザが変形対象領域を指定しなくても、物体形状の広領域（例えば、全体）を滑らかな形状に変形することができる。 As described in detail above, according to the present embodiment, the object shape to be processed is divided into a plurality of deformation target regions (spheres) that overlap each other, and the object shape according to the deformation mapping Ψ is formed in each deformation target region. By being deformed, it is smoothed into a smooth shape. Further, regarding the overlapping portion between the deformation target areas, the movement destination position is determined by the weighted average of the movement destination calculated by the deformation mappings Ψ, Ψ i (i = 1 to n) of each deformation target area. , It is possible to prevent steps and breaks from occurring at the overlapping portion. Thereby, according to the present embodiment, a wide area (for example, the whole) of the object shape can be transformed into a smooth shape without the user specifying the deformation target area.
図１４は、図１３に示した物体形状の全体に対して、本実施形態の形状変形装置によりスムージング処理を実行した結果を示す図である。図１３に示す形状データは、フェイス数が871,306個、メッシュの頂点数が435,545個のポリゴンデータで構成されたものである。この形状データに対して本実施形態のスムージング処理を実行することにより、113,452個の球が設定され、球ごとに算出された変形写像Ψを用いた形状変形の結果、図１４に示す物体形状が得られた。図１４に示すように、物体の表面に存在していた凹凸が形状変形後には少なくなって、滑らかな曲面となっている。 FIG. 14 is a diagram showing the result of performing a smoothing process on the entire object shape shown in FIG. 13 by the shape deforming device of the present embodiment. The shape data shown in FIG. 13 is composed of polygon data having 871,306 faces and 435,545 mesh vertices. By executing the smoothing process of the present embodiment on this shape data, 113,452 spheres are set, and as a result of shape deformation using the deformation map Ψ calculated for each sphere, the object shape shown in FIG. 14 is obtained. Obtained. As shown in FIG. 14, the unevenness existing on the surface of the object is reduced after the shape is deformed, resulting in a smooth curved surface.
なお、物体形状の中でシャープなエッジ形状をしている部分では、分割して生成された球内の点群の分布が平面的ではなくなる。そのような球の各点群に対して変形写像Ψをそのまま適用すると、各点群の移動先の点群で形成される曲面も平面的でなくなって、滑らかな曲面にならない可能性がある。そこで、複数の構成点が平面的に分布していない球については、移動先の重み付け平均を求める際に、変形写像Ψによる移動先の位置に代えて、当該変形写像Ψを適用しない移動元の位置を用いるようにしてもよい。 In addition, in the portion of the object shape having a sharp edge shape, the distribution of the point cloud in the sphere generated by division is not flat. If the deformed map Ψ is applied to each point cloud of such a sphere as it is, the curved surface formed by the point cloud to which each point cloud is moved may not be flat and may not be a smooth curved surface. Therefore, for a sphere in which a plurality of constituent points are not distributed in a plane, when calculating the weighted average of the movement destination, instead of the position of the movement destination by the deformation map Ψ, the movement source to which the deformation map Ψ is not applied is applied. The position may be used.
図１２は、シャープなエッジ形状への対策を考慮した形状変形装置の機能構成例を示す図である。なお、この図１２において、図１に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。図１２に示す形状変形装置では、分散指標算出部４０を更に備えている。また、形状変形部３０に代えて形状変形部３０’を備えている。 FIG. 12 is a diagram showing a functional configuration example of a shape deforming device in consideration of measures for a sharp edge shape. Note that, in FIG. 12, those having the same reference numerals as those shown in FIG. 1 have the same functions, and therefore, duplicate description will be omitted here. The shape deforming device shown in FIG. 12 further includes a dispersion index calculation unit 40. Further, the shape deforming portion 30'is provided in place of the shape deforming portion 30.
分散指標算出部４０は、領域設定部１０により設定された変形対象領域（球）内に含まれる複数の構成点が非平面的に分散している度合いを表す指標である分散指標を算出する。例えば、分散指標算出部４０は、球内に含まれる複数の構成点から、共分散行列の固有値を算出し、最小固有値と２番目に小さい固有値との比率を分散指標として算出する。 The dispersion index calculation unit 40 calculates a dispersion index, which is an index indicating the degree to which a plurality of constituent points included in the deformation target region (sphere) set by the region setting unit 10 are non-planarly dispersed. For example, the variance index calculation unit 40 calculates the eigenvalues of the covariance matrix from a plurality of constituent points included in the sphere, and calculates the ratio between the minimum eigenvalue and the second smallest eigenvalue as the variance index.
例えば、共分散行列の固有値を小さい方から順に、σ1，σ2とする。ここで、球内に含まれる複数の構成点が平面的に分散している場合は、最小固有値σ1だけ“０”に近くなり、他の固有値σ2はσ1より大きな値となる。一方、球内に含まれる複数の構成点が平面的に分散していない場合は、最小固有値σ1と２番目に小さい固有値σ2とはほぼ同じ値となる。したがって、最小固有値σ1と２番目に小さい固有値σ2との比率λ＝σ1／σ2は、複数の構成点が非平面的に分散している度合を表す値として用いることができる。 For example, let the eigenvalues of the covariance matrix be σ 1 and σ 2 in ascending order. Here, when a plurality of constituent points included in the sphere are dispersed in a plane, only the minimum eigenvalue σ 1 is close to “0”, and the other eigenvalues σ 2 are larger than σ 1 . On the other hand, when the plurality of constituent points contained in the sphere are not dispersed in a plane, the minimum eigenvalue σ 1 and the second smallest eigenvalue σ 2 are almost the same value. Therefore, the ratio λ = σ 1 / σ 2 of the minimum eigenvalue σ 1 and the second smallest eigenvalue σ 2 can be used as a value indicating the degree to which a plurality of constituent points are non-planarly dispersed.
形状変形部３０’は、分散指標算出部４０により算出された分散指標の算出値（比率λの値）が第３の所定値より大きい変形対象領域内に含まれる構成点については、当該変形対象領域について算出された変形写像によるそれぞれの移動先に代えて、当該変形写像を行わない移動元の構成点を用いるようにする。すなわち、（式１２）において、Ψ(ｐ)の代わりに構成点ｓの位置を用い、Ψi(ｐi)の代わりに構成点ｓiの位置を用いるようにする。 The shape deformation unit 30'is a deformation target for a configuration point in which the calculation value (value of the ratio λ) of the dispersion index calculated by the dispersion index calculation unit 40 is included in the deformation target region larger than the third predetermined value. Instead of each movement destination by the deformation mapping calculated for the region, the constituent points of the movement source that does not perform the deformation mapping are used. That is, in (Equation 12), the position of the constituent point s is used instead of Ψ (p), and the position of the constituent point s i is used instead of Ψ i ( pi ).
一例として、形状変形部３０’は、ある球について分散指標算出部４０により算出された固有値σ1，σ2の比率λが０．２より大きい場合に（λ＞０．２）、当該球については移動元の構成点の位置を用いて重み付け平均を行うようにする。または、球ＢＬについて算出された比率λの値が０．０２＜λ≦０．２で、その球ＢＬに関するλの値が、 隣接する球ＢＬiに関するλiの値の平均値の２．５倍を超える場合に、移動元の構成点の位置を用いて重み付け平均を行うようにしてもよい。 As an example, when the ratio λ of the eigenvalues σ 1 and σ 2 calculated by the variance index calculation unit 40 for a certain sphere is larger than 0.2 (λ> 0.2), the shape deformation unit 30'is used for the sphere. Makes a weighted average using the position of the constituent point of the movement source. Alternatively, the value of the ratio λ calculated for the sphere BL is 0.02 <λ ≦ 0.2, and the value of λ for the sphere BL is 2.5, which is the average value of the values of λ i for the adjacent sphere BL i. If it exceeds twice, the weighted averaging may be performed using the position of the constituent point of the movement source.
図１２に示すように構成することにより、シャープなエッジ形状や形状が急変する箇所において、無理な形状変形をすることがなくなるので、形状の品質を低下させることを防止することができる。 With the configuration as shown in FIG. 12, it is possible to prevent the quality of the shape from being deteriorated because the shape is not unreasonably deformed at the place where the sharp edge shape or the shape suddenly changes.
その他、上記実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその要旨、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。 In addition, the above embodiments are merely examples of embodiment of the present invention, and the technical scope of the present invention should not be construed in a limited manner. That is, the present invention can be implemented in various forms without departing from its gist or its main features.
１０ 領域設定部
１１ 球設定部
１２ 球分割部
１３ 隣接関係生成部
２０ 変形写像算出部
２１ 変形写像設定部
２２ 拘束条件設定部
２３ 変形写像確定部
２４ 近似平面生成部
２５ 投影点算出部
２６ 中心点抽出部
３０，３０’ 形状変形部
４０ 分散指標算出部
10 Area setting unit 11 Sphere setting unit 12 Sphere division unit 13 Adjacent relationship generation unit 20 Deformation mapping calculation unit 21 Deformation mapping setting unit 22 Constraint condition setting unit 23 Deformation mapping determination unit 24 Approximate plane generation unit 25 Projection point calculation unit 26 Center point Extraction unit 30, 30'Shape deformation unit 40 Dispersion index calculation unit
Claims (12)
上記領域設定部により設定された上記複数の変形対象領域のそれぞれにおいて、当該変形対象領域内に含まれる物体形状の各構成点の移動元位置を移動先位置へと変形させるための変形写像を算出する変形写像算出部と、
上記変形写像算出部により上記変形対象領域ごとに算出された上記変形写像を用いて、上記変形対象領域内に含まれる物体形状を変形させる処理を実行する形状変形部とを備え、
上記形状変形部は、上記変形対象領域がオーバーラップする重複領域内に含まれる形状部分の構成点については、各変形対象領域について算出された上記変形写像によるそれぞれの移動先の重み付き平均により上記移動先位置を決定し、
上記変形写像算出部は、
放射基底関数の１次結合で表わした位置連続に関する項を含む変形写像式を設定する変形写像設定部と、
空間上の指定された移動元位置を上記変形写像式で写像した位置と目標とする移動先位置との距離を表した位置近似、および、上記移動先位置における曲率変化率最小化に関する拘束条件方程式を設定する拘束条件設定部と、
上記拘束条件設定部により設定された上記拘束条件方程式を解いて、上記変形写像設定部により設定された上記変形写像式に含まれる未知数を求めることにより、上記位置近似および上記曲率変化率最小化を満たす変形写像を確定させる変形写像確定部とを備えたことを特徴とする形状変形装置。 An area setting unit that sets a plurality of deformation target areas that overlap between adjacent areas with respect to shape data representing the object shape.
In each of the plurality of deformation target areas set by the area setting unit, a deformation map for transforming the movement source position of each constituent point of the object shape included in the deformation target area to the movement destination position is calculated. Deformation mapping calculation unit and
It is provided with a shape deforming unit that executes a process of deforming an object shape included in the deformation target area by using the deformation mapping calculated for each deformation target area by the deformation mapping calculation unit.
The shape deformation portion is described by weighted average of each movement destination by the deformation mapping calculated for each deformation target region for the constituent points of the shape portion included in the overlapping region where the deformation target regions overlap. Determine the destination position and
The modified mapping calculation unit
A modified mapping setting unit that sets a modified mapping expression including a term related to position continuity represented by a linear combination of radial basis functions, and a modified mapping setting unit.
Position approximation representing the distance between the position where the specified movement source position in space is mapped by the above-mentioned deformation mapping formula and the target movement destination position, and the constraint condition equation regarding the minimization of the curvature change rate at the above-mentioned movement destination position. Constraint condition setting unit to set
By solving the constraint condition equation set by the constraint condition setting unit and obtaining the unknown number included in the deformation mapping equation set by the deformation mapping setting unit, the position approximation and the curvature change rate can be minimized. A shape deforming device including a deformation mapping determination unit for determining a deformation mapping to be satisfied.
上記形状データに対して、１つのボックス内に含まれる複数の構成点の数が所定範囲内となるまで分割を繰り返すことにより、複数の包含ボックスを設定し、それぞれの包含ボックスごとに、当該包含ボックスを内包する球を設定する球設定部と、
上記球内に含まれる複数の構成点の最小２乗平面に対する距離誤差を算出し、当該誤差の算出値が第１の所定値より大きい球を更に分割する球分割部とを備え、
上記球設定部および上記球分割部の処理により設定される球を上記変形対象領域として設定することを特徴とする請求項１に記載の形状変形装置。 The above area setting section
A plurality of inclusion boxes are set by repeating division of the shape data until the number of a plurality of constituent points included in one box falls within a predetermined range, and the inclusion is performed for each inclusion box. A sphere setting unit that sets the sphere that contains the box,
A sphere dividing portion for calculating a distance error with respect to the least squares plane of a plurality of constituent points included in the sphere and further dividing a sphere whose calculated value of the error is larger than the first predetermined value is provided.
The shape deforming device according to claim 1, wherein the sphere set by the processing of the sphere setting unit and the sphere dividing unit is set as the deformation target region.
ｇ(0)＝０，ｇ(1)＝１，ｇ’(0)＝ｇ’(1)＝０，０≦ｇ(x)≦１（０≦x≦１）
を満たす関数ｇ(x)を用いて、上記重み付き平均を求めることを特徴とする請求項１に記載の形状変形装置。 The shape deformation part is
g (0) = 0, g (1) = 1, g'(0) = g'(1) = 0,0 ≤ g (x) ≤ 1 (0 ≤ x ≤ 1)
The shape deforming device according to claim 1, wherein the weighted average is obtained by using a function g (x) that satisfies.
上記形状変形部は、上記分散指標の算出値が第３の所定値より大きい変形対象領域内に含まれる構成点については、当該変形対象領域について算出された上記変形写像による移動先に代えて、当該変形写像を行わない移動元の構成点の位置を用いて上記重み付き平均を算出することを特徴とする請求項１に記載の形状変形装置。 A dispersion index calculation unit for calculating a dispersion index, which is an index indicating the degree of non-planar non-dispersion of a plurality of constituent points included in the deformation target region set by the region setting unit, is further provided.
For the constituent points included in the deformation target region in which the calculated value of the dispersion index is larger than the third predetermined value, the shape deformation portion replaces the movement destination by the deformation mapping calculated for the deformation target region. The shape deformation device according to claim 1, wherein the weighted average is calculated using the positions of the constituent points of the moving source that do not perform the deformation mapping.
上記形状変形部は、上記比率が上記第３の所定値より大きい変形対象領域内に含まれる構成点については、上記移動元の構成点を用いて上記重み付き平均を算出することを特徴とする請求項７に記載の形状変形装置。 The variance index calculation unit calculates the eigenvalues of the covariance matrix from a plurality of constituent points included in the transformation target region set by the region setting unit, and calculates the ratio between the minimum eigenvalue and the second smallest eigenvalue. Calculated as the above variance index
The shape deforming portion is characterized in that the weighted average is calculated by using the constituent points of the moving source for the constituent points included in the deformed target region whose ratio is larger than the third predetermined value. The shape deforming device according to claim 7.
上記領域設定部により設定された上記変形対象領域内に含まれる上記複数の構成点に対する近似平面を生成する近似平面生成部と、
上記複数の構成点をそれぞれ上記近似平面上に投影することにより複数の投影点を算出する投影点算出部とを更に備え、
上記拘束条件設定部は、上記投影点算出部により算出された上記複数の投影点をそれぞれ上記移動元位置として指定し、上記複数の構成点をそれぞれ上記複数の投影点に対する上記移動先位置として指定して、上記位置近似および上記曲率変化率最小化に関する拘束条件方程式を設定することを特徴とする請求項１に記載の形状変形装置。 The modified mapping calculation unit
An approximate plane generation unit that generates an approximate plane for the plurality of constituent points included in the deformation target area set by the area setting unit, and an approximate plane generation unit.
A projection point calculation unit for calculating a plurality of projection points by projecting the plurality of constituent points on the approximate plane is further provided.
The constraint condition setting unit designates the plurality of projection points calculated by the projection point calculation unit as the movement source positions, and designates the plurality of constituent points as the movement destination positions with respect to the plurality of projection points, respectively. The shape deforming device according to claim 1, wherein the constraint condition equations relating to the position approximation and the curvature change rate minimization are set.
上記変形写像設定部は、上記中心点抽出部により抽出された上記複数の中心点を用いて上記変形写像式を設定することを特徴とする請求項９に記載の形状変形装置。 A center point extraction unit for extracting a plurality of center points of the radial basis function from the approximate plane generated by the approximate plane generation unit is further provided.
The shape deformation device according to claim 9, wherein the deformation mapping setting unit sets the deformation mapping formula using the plurality of center points extracted by the center point extraction unit.
上記領域設定手段により設定された上記複数の変形対象領域のそれぞれにおいて、当該変形対象領域内に含まれる物体形状の各構成点の移動元位置を移動先位置へと変形させるための変形写像を算出する変形写像算出手段、および
上記変形写像算出手段により上記変形対象領域ごとに算出された上記変形写像を用いて、上記変形対象領域内に含まれる物体形状を変形させる処理を実行する形状変形手段
としてコンピュータを機能させ、
上記形状変形手段は、上記変形対象領域がオーバーラップする重複領域内に含まれる形状部分の構成点については、各変形対象領域について算出された上記変形写像によるそれぞれの移動先の重み付き平均により上記移動先位置を決定し、
上記変形写像算出手段は、
放射基底関数の１次結合で表わした位置連続に関する項を含む変形写像式を設定する変形写像設定手段、
空間上の指定された移動元位置を上記変形写像式で写像した位置と目標とする移動先位置との距離を表した位置近似、および、上記移動先位置における曲率変化率最小化に関する拘束条件方程式を設定する拘束条件設定手段、
上記拘束条件設定手段により設定された上記拘束条件方程式を解いて、上記変形写像設定手段により設定された上記変形写像式に含まれる未知数を求めることにより、上記位置近似および上記曲率変化率最小化を満たす変形写像を確定させる変形写像確定手段
とを含むことを特徴とする形状変形用プログラム。 Area setting means for setting a plurality of deformation target areas that overlap between adjacent areas with respect to shape data representing an object shape.
In each of the plurality of deformation target areas set by the area setting means, a deformation mapping for deforming the movement source position of each constituent point of the object shape included in the deformation target area to the movement destination position is calculated. As a shape deformation means for executing a process of deforming the shape of an object included in the deformation target area by using the deformation mapping calculation means and the deformation mapping calculated for each deformation target area by the deformation mapping calculation means. Make the computer work
The shape deformation means uses the weighted average of the movement destinations calculated for each deformation target area as the constituent points of the shape portions included in the overlapping regions where the deformation target areas overlap. Determine the destination position and
The above-mentioned deformation mapping calculation means
A modified mapping setting means for setting a modified mapping equation including a term relating to position continuity represented by a linear combination of radial basis functions,
Position approximation representing the distance between the position where the specified movement source position in space is mapped by the above-mentioned deformation mapping formula and the target movement destination position, and the constraint condition equation regarding the minimization of the curvature change rate at the above-mentioned movement destination position. Constraint condition setting means to set
By solving the constraint condition equation set by the constraint condition setting means and obtaining the unknown number included in the deformation map equation set by the deformation map setting means, the position approximation and the curvature change rate can be minimized. A shape deformation program including a deformation mapping determination means for determining a deformation mapping to be satisfied.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2016241037A JP6802702B2 (en) | 2016-12-13 | 2016-12-13 | Shape deformation device and shape deformation program |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2016241037A JP6802702B2 (en) | 2016-12-13 | 2016-12-13 | Shape deformation device and shape deformation program |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2018097567A JP2018097567A (en) | 2018-06-21 |
| JP6802702B2 true JP6802702B2 (en) | 2020-12-16 |
Family
ID=62633706
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2016241037A Active JP6802702B2 (en) | 2016-12-13 | 2016-12-13 | Shape deformation device and shape deformation program |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP6802702B2 (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP7585003B2 (en) * | 2020-11-18 | 2024-11-18 | Tdk株式会社 | Electromagnetic environment analysis system, electromagnetic environment analysis method, and program |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP6253053B2 (en) * | 2013-11-29 | 2017-12-27 | 富士通株式会社 | Data search device, data search device control method, and data search device control program |
| JP6426968B2 (en) * | 2014-10-08 | 2018-11-21 | キヤノン株式会社 | INFORMATION PROCESSING APPARATUS AND METHOD THEREOF |
| JP6495728B2 (en) * | 2015-04-27 | 2019-04-03 | 日本ユニシス株式会社 | Shape deformation apparatus and shape deformation program |
-
2016
- 2016-12-13 JP JP2016241037A patent/JP6802702B2/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| JP2018097567A (en) | 2018-06-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111581776B (en) | An isogeometric analysis method based on geometric reconstruction model | |
| RU2413996C2 (en) | Large mesh deformation using volumetric graph laplacian | |
| Zhang et al. | Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow | |
| US9972128B2 (en) | Methods and systems for generating polycubes and all-hexahedral meshes of an object | |
| Peternell | Developable surface fitting to point clouds | |
| US20160138914A1 (en) | System and method for analyzing data | |
| KR101023996B1 (en) | Surface construction method of fluid simulation based on particle method, and storage medium storing the program | |
| Yoshihara et al. | Topologically robust B-spline surface reconstruction from point clouds using level set methods and iterative geometric fitting algorithms | |
| Yang | Curve fitting and fairing using conic splines | |
| Bernardi et al. | Continuity properties of the inf-sup constant for the divergence | |
| CN117994424B (en) | A multi-scale characterization three-dimensional morphology construction method and system suitable for coarse-grained soil | |
| Zeng et al. | Efficient slicing procedure based on adaptive layer depth normal image | |
| KR101032397B1 (en) | 3D shape representation device and method using spherical coordinate system | |
| JP6802702B2 (en) | Shape deformation device and shape deformation program | |
| Heep et al. | An Adaptive Screen-Space Meshing Approach for Normal Integration | |
| JP6727932B2 (en) | Curved surface generator by point cloud surface fitting and curved surface generation program | |
| JP6449703B2 (en) | Shape deformation apparatus and shape deformation program | |
| JP6495728B2 (en) | Shape deformation apparatus and shape deformation program | |
| WO2021154273A1 (en) | Generating 3d printing points using an approximate mathematical expression of a rqb curve | |
| CN111145357A (en) | High-fidelity triangular mesh smoothing algorithm | |
| Batuhan Arisoy et al. | Free form surface skinning of 3d curve clouds for conceptual shape design | |
| Urick et al. | Reconstruction of trimmed NURBS surfaces for gap-free intersections | |
| JP6727931B2 (en) | Hole-covered curved surface generation device and hole-covered curved surface generation program | |
| JP6634317B2 (en) | Shape deformation device and shape deformation program | |
| CN121437776B (en) | Monorail track guiding-based road internal crack progressive extension modeling method and system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20191101 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20201112 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20201117 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20201127 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 6802702 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |