JP6890945B2

JP6890945B2 - Mesh voxels

Info

Publication number: JP6890945B2
Application number: JP2016200654A
Authority: JP
Inventors: リオール・ザール; ナタン・シャロン・カッツ; ベンジャミン・コーエン
Original assignee: Biosense Webster Israel Ltd
Current assignee: Biosense Webster Israel Ltd
Priority date: 2015-10-13
Filing date: 2016-10-12
Publication date: 2021-06-18
Anticipated expiration: 2036-10-12
Also published as: US9875578B2; IL248137B; MA41578A; US20170103570A1; EP3156975A1; EP3156975B1; CN107016731B; AU2016225803A1; ES2734123T3; JP2017076397A; CN107016731A; IL248137A0; CA2945022A1

Description

本発明は、概ね、画像生成に関し、具体的には、メッシュからの画像の効率的な生成に関する。 The present invention relates generally to image generation, specifically to efficient generation of images from meshes.

多くの分野において、タイミングよく画像を操作することができることは重要である。画像の解像度、サイズ、色数が増加するにつれ、操作は、よりコンピュータを駆使することが必要となる。外科手術中などの緊急を要する分野においては、ほぼリアルタイムで操作することが要求される場合があり、画像を提示するために使用されるコンピュータリソースに対する需要が更に大きくなっている。場合によっては、リアルタイムの挙動を維持するために、例えば、画像の解像度を低下させたり、画像の色数を減少させたりすることによって、画質が低下する場合がある。 In many fields, it is important to be able to manipulate images in a timely manner. As the resolution, size, and number of colors of an image increase, the operation requires more computer power. In urgent fields such as during surgery, near real-time operation may be required, further increasing the demand for computer resources used to present images. In some cases, in order to maintain real-time behavior, the image quality may be deteriorated by, for example, reducing the resolution of the image or reducing the number of colors of the image.

本発明の実施形態は、３次元（３Ｄ）レンダリングのための方法であって、該方法は、
表面の三角形メッシュを画定する一群の３Ｄ三角形を受け取ることであって、該群におけるそれぞれの３Ｄ三角形は、それぞれの３Ｄ座標を有する３つの３Ｄ頂点を有する、ことと、
それぞれの３Ｄ三角形を、該３Ｄ頂点にそれぞれ対応する３つの２次元（２Ｄ）頂点を有する、対応する２Ｄ三角形に変換することであって、それぞれの２Ｄ頂点は、それぞれの２Ｄ画素座標及び対応する３Ｄ頂点の３Ｄ座標に対応する画素属性の３つの値を有する、ことと、
それぞれの２Ｄ頂点の該画素属性の３つの値を補間可能な値として処理するグラフィックプロセッサへ、それぞれの２Ｄ三角形を渡すことと、
該グラフィックプロセッサにおいて、該２Ｄ三角形の該２Ｄ頂点の該画素属性間の補間によって、それぞれの２Ｄ三角形内の画素に対してそれぞれの補間された画素属性の３つの値を算出することと、
該表面の３Ｄ画像を、該グラフィックプロセッサによって算出された該補間された画素属性を該３Ｄ画像内のボクセル座標に変換することによって、レンダリングすることと、を含む、方法を提供する。 An embodiment of the present invention is a method for three-dimensional (3D) rendering, wherein the method is:
Receiving a group of 3D triangles defining a surface triangle mesh, with each 3D triangle in the group having three 3D vertices with their respective 3D coordinates.
Converting each 3D triangle into a corresponding 2D triangle, each having three two-dimensional (2D) vertices corresponding to the 3D vertice, each 2D vertice having its own 2D pixel coordinates and corresponding. Having three values of pixel attributes corresponding to the 3D coordinates of the 3D vertices,
Passing each 2D triangle to a graphics processor that processes the three values of the pixel attribute of each 2D vertex as interpolable values,
In the graphic processor, by interpolating between the pixel attributes of the 2D vertices of the 2D triangle, three values of each interpolated pixel attribute are calculated for the pixels in each 2D triangle.
Provided are methods including rendering a 3D image of the surface by converting the interpolated pixel attributes calculated by the graphics processor into voxel coordinates in the 3D image.

本方法は、典型的には、所与の２Ｄ三角形をグラフィックプロセッサへ渡した後、所与の２Ｄ三角形を所与の２Ｄ三角形内の画素で満たすことを含む。 The method typically involves passing a given 2D triangle to a graphics processor and then filling the given 2D triangle with pixels within a given 2D triangle.

開示された実施形態において、補間された画素属性は、それぞれの２Ｄ頂点の画素属性の３つの値の重み付けされた補間を含む。典型的には、重み付けされた補間は、所与の２Ｄ頂点の画素属性の３つの値に、所与の画素から所与の２Ｄ頂点までの距離に反比例する重みを適用することを含む。 In the disclosed embodiments, the interpolated pixel attributes include a weighted interpolation of the three values of the pixel attributes of each 2D vertex. Typically, weighted interpolation involves applying weights to the three values of the pixel attributes of a given 2D vertex that are inversely proportional to the distance from a given pixel to a given 2D vertex.

更なる開示された実施形態において、補間された画素属性をボクセル座標に変換することは、ボクセルからなる直方体内に三角形メッシュを包囲することと、補間された画素属性を含有するか、又は補間された画素属性に接触するボクセルを、表面のボクセルとして選択することと、からなる。 In a further disclosed embodiment, converting the interpolated pixel attributes to voxel coordinates involves enclosing a triangular mesh within a voxel square and containing or interpolating the interpolated pixel attributes. It consists of selecting voxels that come into contact with the pixel attributes as surface voxels.

なお更なる開示された実施形態において、表面は、心腔内に含まれている。 In a further disclosed embodiment, the surface is contained within the heart chamber.

代替的な実施形態において、それぞれの２Ｄ三角形は、１つの共通の２Ｄ三角形を含む。 In an alternative embodiment, each 2D triangle comprises one common 2D triangle.

更なる代替的な実施形態において、それぞれの２Ｄ三角形は、仮想画面を満たすように構成されている。 In a further alternative embodiment, each 2D triangle is configured to fill a virtual screen.

本発明の実施形態による、３次元（３Ｄ）レンダリングのための装置であって、装置は、
処理ユニットであって、
表面の三角形メッシュを画定する一群の３Ｄ三角形を受け取ることであって、該群におけるそれぞれの３Ｄ三角形は、それぞれの３Ｄ座標を有する３つの３Ｄ頂点を有することと、
それぞれの３Ｄ三角形を、該３Ｄ頂点にそれぞれ対応する３つの２次元（２Ｄ）頂点を有する、対応する２Ｄ三角形に変換することであって、それぞれの２Ｄ頂点は、それぞれの２Ｄ画素座標及び対応する３Ｄ頂点の３Ｄ座標に対応する及び画素属性の３つの値を有する、ことと、を行うように構成されている、処理ユニットと、
グラフィックプロセッサであって、
それぞれの２Ｄ三角形を受け取り、それぞれの２Ｄ頂点の該画素属性の３つの値を補間可能な値として処理することと、
該２Ｄ三角形の該２Ｄ頂点の該画素属性間の補間によって、それぞれの２Ｄ三角形内の画素に対してそれぞれの補間された画素属性の３つの値を算出することと、を行うように構成されている、グラフィックプロセッサと、を備え、
該処理ユニットは、該表面の３Ｄ画像を、該グラフィックプロセッサによって算出された該補間された画素属性を該３Ｄ画像内のボクセル座標に変換することによって、レンダリングするように構成されている、装置が更に提供される。 A device for three-dimensional (3D) rendering according to an embodiment of the present invention.
It ’s a processing unit,
Receiving a group of 3D triangles defining a surface triangle mesh, with each 3D triangle in the group having three 3D vertices with their respective 3D coordinates.
Converting each 3D triangle into a corresponding 2D triangle, each having three two-dimensional (2D) vertices corresponding to the 3D vertice, each 2D vertice having its own 2D pixel coordinates and corresponding. A processing unit that is configured to correspond to the 3D coordinates of a 3D vertex and to have three values of a pixel attribute.
It ’s a graphics processor
Receiving each 2D triangle and processing the three values of the pixel attribute of each 2D vertex as interpolable values.
It is configured to calculate the three values of each interpolated pixel attribute for the pixels in each 2D triangle by interpolating between the pixel attributes of the 2D vertices of the 2D triangle. It has a graphics processor and
The processing unit is configured to render a 3D image of the surface by converting the interpolated pixel attributes calculated by the graphics processor into voxel coordinates within the 3D image. Further provided.

本開示は、以下の本開示の実施形態の詳細な説明を図面と併せて読むことで、より完全な理解が得られるであろう。 A more complete understanding of the present disclosure will be obtained by reading the following detailed description of the embodiments of the present disclosure in conjunction with the drawings.

本発明の実施形態によるボクセル化装置の概略図である。It is the schematic of the voxelization apparatus by embodiment of this invention. 本発明の実施形態による、センサが表面に接触すると、センサによって登録される点の概略図である。FIG. 5 is a schematic view of points registered by the sensor when the sensor comes into contact with the surface according to the embodiment of the present invention. 本発明の実施形態による、画像を生成する処理ユニットによって行われる工程のフローチャートである。It is a flowchart of the process performed by the processing unit which generates an image according to embodiment of this invention. 本発明の実施形態による、フローチャートの工程のうち１つを示す図である。It is a figure which shows one of the steps of the flowchart by embodiment of this invention.

概要
画像の回転、移動、拡大及び／又は縮小などの表面画像の操作は、典型的には、コンピュータを駆使して行われる。更に、画像の解像度及び画像内の色数が増加するにしたがって、タイミングよく操作を行うために必要とされる演算能力の増大もまた必要とされる。従来技術のシステムでは、かかる演算能力を増大させるのではなく、画像の解像度を低下させ、色数を削減し、かつ／又は画像の操作にかかる時間を増加させる場合がある。 Overview Manipulation of surface images, such as rotating, moving, enlarging and / or reducing images, is typically performed using a computer. Further, as the resolution of the image and the number of colors in the image increase, it is also necessary to increase the computing power required for performing the operation in a timely manner. In a system of the prior art, instead of increasing such computing power, the resolution of the image may be reduced, the number of colors may be reduced, and / or the time required for manipulating the image may be increased.

本発明の実施形態は、高解像度を有する画像の迅速な操作に必要とされる演算能力を増大させることによって、異なる取り組みで行われている。増大したコンピュータの処理能力は、専用のグラフィックプロセッサの形態で提供されている。従来技術において既知であるように、グラフィックプロセッサは、大量のデータを処理するための汎用処理ユニットより効果的である高度並列構造（highly parallel structure）を有する。 Embodiments of the present invention have been made in different ways by increasing the computing power required for rapid manipulation of high resolution images. The increased computer processing power is provided in the form of a dedicated graphics processor. As is known in the art, graphics processors have a highly parallel structure that is more effective than general purpose processing units for processing large amounts of data.

本発明の実施形態において、汎用処理ユニットは、表面のメッシュを画定する一群の３次元（３Ｄ）三角形を受け取り、三角形のそれぞれは、それぞれの３Ｄ座標を有する３つの３Ｄ頂点を有する。処理ユニットは、それぞれの３Ｄ三角形を、３Ｄ頂点に対応する３つの２Ｄ頂点を有する対応する２次元（２Ｄ）三角形に変換する。典型的には、３Ｄ三角形が異なっても、２Ｄ三角形が１組の２Ｄ頂点を有する１つの共通の２Ｄ三角形であり得る。それぞれの２Ｄ頂点は、２Ｄ画素座標を有し、更に、それぞれの頂点には、対応する３Ｄ頂点の３Ｄ座標である画素属性の３つの値が割り当てられる。 In an embodiment of the invention, the general purpose processing unit receives a group of three-dimensional (3D) triangles defining a surface mesh, each of which has three 3D vertices with their respective 3D coordinates. The processing unit transforms each 3D triangle into a corresponding two-dimensional (2D) triangle with three 2D vertices corresponding to the 3D vertices. Typically, the 2D triangles can be one common 2D triangle with a set of 2D vertices, even if the 3D triangles are different. Each 2D vertex has 2D pixel coordinates, and each vertex is assigned three values of pixel attributes, which are the 3D coordinates of the corresponding 3D vertices.

処理ユニットは、補間可能な値、すなわち、グラフィックプロセッサが補間を行うことができる値としてのそれぞれの２Ｄ頂点の画素属性の３つの値を処理する専用のグラフィックプロセッサにそれぞれの２Ｄ三角形を渡す。グラフィックプロセッサの一部の使用において、プロセッサに入力される補間可能な値は明度である。グラフィックプロセッサは、それぞれの２Ｄ三角形内の画素でそれぞれの２Ｄ三角形を満たすように構成されている。更に、グラフィックプロセッサは、それぞれの２Ｄ頂点の画素属性の３つの値を補間可能な値として処理することによって、満たした画素のそれぞれに対して補間された画素属性の３つの値を算出する。補間は、典型的には、２Ｄ頂点の３つの値の加重平均であり、重み付けは、２Ｄ頂点からの所与の満たした画素の距離に反比例するように構成されている。 The processing unit passes each 2D triangle to a dedicated graphics processor that processes three values of the pixel attributes of each 2D vertex as interpolable values, i.e., values that the graphics processor can interpolate. In some uses of the graphics processor, the interpolable value entered into the processor is lightness. The graphics processor is configured to fill each 2D triangle with pixels within each 2D triangle. Further, the graphic processor calculates the three values of the pixel attribute interpolated for each of the satisfied pixels by processing the three values of the pixel attribute of each 2D vertex as interpolable values. The interpolation is typically a weighted average of the three values of the 2D vertices, and the weighting is configured to be inversely proportional to the distance of a given filled pixel from the 2D vertices.

処理ユニットは、グラフィックプロセッサから補間された画素属性の３つの値を受け取り、対応する３Ｄ三角形内の３Ｄの点として３つの値を使用することができる。処理ユニットは、典型的には、まず、１セットのボクセル内にメッシュを包囲し、上述の処理を行った後、３Ｄの点を包囲又は３Ｄの点に接触するボクセルを選択する。その後、処理ユニットは、選択されたボクセルのボクセル座標を使用して、画面上にメッシュと関連付けられた表面の３Ｄ画像をレンダリングする。 The processing unit receives three values of the interpolated pixel attribute from the graphics processor and can use the three values as 3D points in the corresponding 3D triangle. The processing unit typically first surrounds the mesh within a set of voxels, performs the above-mentioned processing, and then selects a voxel that surrounds a 3D point or contacts a 3D point. The processing unit then renders a 3D image of the surface associated with the mesh on the screen using the voxel coordinates of the selected voxels.

画素属性の３つの値を補間可能な値として処理するように構成されている専用のグラフィックプロセッサを使用することによって、本発明の実施形態は、高度に並列な特性のグラフィックプロセッサを使用して、効率よく高解像度画像をリアルタイムに操作することができる。 By using a dedicated graphics processor configured to process the three values of the pixel attributes as interpolable values, embodiments of the present invention use a graphics processor with highly parallel characteristics. High-resolution images can be operated efficiently in real time.

システムの説明
以下の説明において、図面中の同様の要素は、同様の数字により識別され、同様の要素は、必要に応じて識別数字に文字を添えることにより区別される。 System Description In the following description, similar elements in the drawings are identified by similar numbers, and similar elements are distinguished by adding letters to the identification numbers as needed.

図１は、本発明の実施形態によるボクセル化装置２０の概略図である。以下に記載されるように、装置２０は、３次元（３Ｄ）の表面２２内に含まれるボクセルを決定するように構成されている。例として、装置は、侵襲性の医療処置において使用されることが想定され、処置が行われる表面２２は、ヒトの患者２８の心臓２６の心腔の表面２４を含むことが想定されている。処置は、医療専門家３０によって行われることが想定される。また、例として、処置は、表面２４のアブレーションを含むことが想定される。しかしながら、本発明の実施形態は、この特定の表面上の特定の処置だけに適用可能であるのではなく、任意の表面上の任意の処置を実質的に含み得ることが理解されよう。 FIG. 1 is a schematic view of a voxelizing device 20 according to an embodiment of the present invention. As described below, the device 20 is configured to determine the voxels contained within the three-dimensional (3D) surface 22. As an example, the device is envisioned to be used in an invasive medical procedure, the surface 22 on which the procedure is performed is envisioned to include the surface 24 of the heart chamber of the heart 26 of a human patient 28. The procedure is expected to be performed by medical professional 30. Also, by way of example, the treatment is expected to include ablation of the surface 24. However, it will be appreciated that embodiments of the present invention are not only applicable to specific treatments on this particular surface, but may include substantially any treatment on any surface.

装置２０は、装置の操作コンソール４８内に位置するシステム処理ユニット（ＰＵ）４６によって制御される。ＰＵ４６は、グラフィックプロセッサ（ＧＰ）５０及び追跡モジュール５２と通信しており、これらの機能は以下に記載される。ＰＵ４６はまた、典型的には、アブレーションモジュール及び灌流モジュールなどの処置に使用される他のモジュールと通信しているが、簡略化のために、かかるモジュールは、図１には図示されていない。コンソール４８は、専門家３０によって使用されるコントロール部５４を備えて、処理ユニットと通信している。 The device 20 is controlled by a system processing unit (PU) 46 located in the operation console 48 of the device. The PU 46 communicates with the graphics processor (GP) 50 and the tracking module 52, and these functions are described below. The PU 46 also typically communicates with other modules used in the procedure, such as the ablation module and the perfusion module, but for simplicity, such modules are not shown in FIG. .. The console 48 comprises a control unit 54 used by the expert 30 to communicate with the processing unit.

典型的には、処置を行う前に、表面２２は、マッピングされ、マッピングは、専門家３０によって行われることが想定される。マッピングを行うために、プローブ６０は、その遠位端に位置センサ６２を有するように構成されてもよく、位置センサは、ＰＵ４６と通信し、センサからのシグナルにより、処理ユニットは、センサの位置を判定することができる。センサ６２は、当該技術分野において既知の位置を判定するための任意の方法を使用してもよい。例えば、センサ６２は、１つ又は２つ以上のコイルを備えてもよく、ＰＵ４６は、患者２８の外部の磁気トランスミッタ６４がコイル内でシグナルを生成する磁気追跡方法を使用してもよい。処理ユニットは、追跡モジュール５２などの追跡モジュールを使用して、磁気トランスミッタによって規定される３次元（３Ｄ）基準座標系６６内の位置座標へシグナルを変換することができる。図１において、３Ｄ基準座標系は、１組の直交するｘｙｚ軸によって示される。ＢｉｏｓｅｎｓｅＷｅｂｓｔｅｒ（ＤｉａｍｏｎｄＢａｒ，ＣＡ）により生産されるＣａｒｔｏ（登録商標）システムは、このような追跡方法を使用している。 Typically, prior to the procedure, the surface 22 is mapped and it is envisioned that the mapping will be done by expert 30. To perform the mapping, the probe 60 may be configured to have a position sensor 62 at its distal end, the position sensor communicating with the PU 46, and a signal from the sensor causing the processing unit to use the sensor. The position can be determined. The sensor 62 may use any method for determining a position known in the art. For example, the sensor 62 may include one or more coils, and the PU 46 may use a magnetic tracking method in which a magnetic transmitter 64 external to the patient 28 produces a signal within the coils. The processing unit can use a tracking module, such as the tracking module 52, to transform the signal into position coordinates within the three-dimensional (3D) frame of reference 66 defined by the magnetic transmitter. In FIG. 1, the 3D frame of reference is represented by a set of orthogonal xyz axes. The Carto® system produced by Biosense Webster (Diamond Bar, CA) uses such a tracking method.

マッピングを行うために、専門家は、患者の内腔内へプローブ６０を挿入することができ、プローブの遠位端は、患者の心腔２４に入り、センサ６２は、複数の点で心腔の表面２２に接触する。マッピングから、ＰＵ４６は、表面２２の画像７０を生成することができ、処理ユニットは、典型的には、専門家３０に対して、画面７４上に表面２２の画像７０を提示する。処置中、専門家３０は、コントロール部５４を使用して、例えば、画像の回転、倍率の変更、視野方向の変更、及び／又は画像の一部のみを示すことによって、画像７０を操作することができる。画像７０の生成は、以下に記載される。 To perform the mapping, the expert can insert the probe 60 into the lumen of the patient, the distal end of the probe enters the patient's heart chamber 24, and the sensor 62 is the heart chamber at multiple points. Contact the surface 22 of the. From the mapping, the PU 46 can generate an image 70 of the surface 22, and the processing unit typically presents the image 70 of the surface 22 on the screen 74 to the expert 30. During the procedure, expert 30 uses the control unit 54 to manipulate the image 70, for example by rotating the image, changing the magnification, changing the viewing direction, and / or showing only part of the image. Can be done. The generation of image 70 is described below.

ＰＵ４６、ＧＰ５０、及びモジュール５２用のソフトウェアは、例えば、電子形態で、ネットワークを介して、ダウンロードすることができる。あるいは又はこれに加えて、ソフトウェアは、光学的、磁気的、又は電子的記憶媒体など、一時的でない有形の媒体上に提供され得る。 The software for PU 46, GP 50, and module 52 can be downloaded, for example, in electronic form over the network. Alternatively or additionally, the software may be provided on a non-temporary tangible medium, such as an optical, magnetic, or electronic storage medium.

図２は、本発明の実施形態による、センサ６２が表面２２に接触した際、センサ６２によって登録される点１００の概略図である。典型的には、上で言及されたマッピング中、ＰＵ４６は、まず、トランスミッタ６４によって規定される３Ｄ基準座標系において測定されたとおり、点１００の３Ｄ座標を記憶する。その後、処理ユニットは、ボールピボッティングアルゴリズムなどの当該技術分野において既知の任意の方法を使用して、本明細書において３Ｄ頂点１００とも称される点１００の３Ｄ座標を線分１０２によって接続して、総称的に三角形１０４と称される、１組の接続された３Ｄ三角形１０４Ａ、１０４Ｂ、１０４Ｃを生成する。３Ｄ三角形１０４は、表面の三角形メッシュ１０６を形成する。図３のフローチャートを参照して以下で記載されるように、ＰＵ４６は、ＧＰ５０を使用して、メッシュ１０６を画像７０にレンダリングする。 FIG. 2 is a schematic view of a point 100 registered by the sensor 62 when the sensor 62 comes into contact with the surface 22 according to the embodiment of the present invention. Typically, during the mapping mentioned above, the PU 46 first stores the 3D coordinates of point 100 as measured in the 3D reference coordinate system defined by the transmitter 64. The processing unit then uses a line segment 102 to connect the 3D coordinates of the point 100, also referred to herein as the 3D vertex 100, using any method known in the art, such as a ball pivoting algorithm. Thus, a set of connected 3D triangles 104A, 104B, 104C, collectively referred to as the triangle 104, is generated. The 3D triangle 104 forms a surface triangle mesh 106. The PU 46 uses the GP 50 to render the mesh 106 into the image 70, as described below with reference to the flowchart of FIG.

図３は、本発明の実施形態による、画像７０を生成するために、ＰＵ４６によって行われる工程のフローチャートであり、図４は、本発明の実施形態による、フローチャートの工程のうち１つを示す図である。図１及び図２を参照して上述されるように、最初の工程１５０において、処理ユニットは、本明細書において、表面２２のメッシュ１０６を含むように想定される３Ｄ三角形のメッシュを生成する。メッシュの生成は、メッシュの３Ｄ頂点１００の順序付けられた３つの値としての３Ｄ座標を決定することと、その後、頂点を接続する線分１０２の均衡を判定して、基準座標系６６内に３Ｄ三角形１０４を形成することと、を含む。 FIG. 3 is a flowchart of the steps performed by the PU 46 to generate the image 70 according to the embodiment of the present invention, and FIG. 4 shows one of the steps of the flowchart according to the embodiment of the present invention. It is a figure. As described above with reference to FIGS. 1 and 2, in the first step 150, the processing unit produces a mesh of 3D triangles, which is assumed herein to include the mesh 106 of the surface 22. The mesh is generated by determining the 3D coordinates of the 3D vertices 100 of the mesh as three ordered values, and then determining the balance of the line segments 102 connecting the vertices, and 3D within the reference coordinate system 66. Includes forming the triangle 104.

包囲する工程１５１において、３Ｄメッシュは、ボクセルから構成される３Ｄ体積内に包囲される。必ずではないが、典型的には、包囲している体積の縁部は、基準座標系６６のｘｙｚ軸に平行であるように選択される。ボクセルの数及び大きさは、専門家３０によって選択されてもよい。ボクセルは、典型的には、立体であり、典型的には、サイズが等しい。典型的な３Ｄ体積は、１２８×１２８×１２８ボクセル又は５１２×５１２×５１２ボクセルを含んでもよいが、本発明の実施形態は、これらの特定の値に限定されず、３Ｄ体積に対して他の都合のよいボクセルの形状が専門家３０によって選択され得る。 In the encircling step 151, the 3D mesh is enclosed in a 3D volume composed of voxels. Typically, but not always, the edges of the surrounding volume are chosen to be parallel to the xyz axis of the frame of reference 66. The number and size of voxels may be selected by expert 30. Voxels are typically three-dimensional and typically of equal size. A typical 3D volume may include 128 x 128 x 128 voxels or 512 x 512 x 512 voxels, but embodiments of the invention are not limited to these particular values and are other to the 3D volume. A convenient voxel shape can be selected by expert 30.

三角形の選択工程１５２において、処理ユニットは、３Ｄ三角形を選択し、ここで、３Ｄ三角形が三角形１０４Ａであると想定すると、３つの値（ｘ_Ａ１，ｙ_Ａ１，ｚ_Ａ１），（ｘ_Ａ２，ｙ_Ａ２，ｚ_Ａ２），（ｘ_Ａ３，ｙ_Ａ３，ｚ_Ａ３）と想定される、三角形の３Ｄ頂点の３Ｄ座標を登録する。 In the triangle selection step 152, the processing unit selects a 3D triangle, and assuming that the 3D triangle is a triangle 104A, three values (x _A1 , y _A1 , z _A1 ), (x _A2 , y). Register the 3D coordinates of the 3D vertices of the triangle, which are assumed to be _A2 , z _A2 ), (x _A3 , y _A3 , z _A3).

変換工程１５４において、ＧＰ５０へのデータ入力に備えて、選択された３Ｄ三角形は、２Ｄ三角形に変換される。選択された三角形の３Ｄ頂点の３Ｄ座標のそれぞれは、２次元（２Ｄ）頂点のそれぞれの２Ｄ座標と１対１の対応で配置される。２Ｄ頂点のそれぞれは、２Ｄ画素座標及び対応する３Ｄ頂点の画素属性の３つの値を有する。 In conversion step 154, the selected 3D triangle is converted to a 2D triangle in preparation for data entry into GP 50. Each of the 3D coordinates of the 3D vertices of the selected triangle is arranged in a one-to-one correspondence with the respective 2D coordinates of the two-dimensional (2D) vertices. Each of the 2D vertices has three values: 2D pixel coordinates and the corresponding pixel attributes of the 3D vertices.

図４及び以下の表Ｉは、工程１５４において形成される対応を示す。 FIG. 4 and Table I below show the correspondence formed in step 154.

図４は、基準座標系６６に描かれる３つの３Ｄ頂点を有する３Ｄ三角形１０４Ａを示す。３Ｄ三角形１０４Ａに対応する２Ｄ三角形１８０は、２Ｄの基準座標系１８４を有する２Ｄ画面１８２上に描かれている。三角形１８０、画面１８２、及び基準座標系１８４は、工程１５４において生成された対応関係が画面上の任意の実際の点の場所に関係せず、画面１８２が仮想画面であることを示すために、破線で描かれている。このように、２Ｄ三角形１８２の実際の図は存在しないので、三角形１８２は、破線で描かれている。 FIG. 4 shows a 3D triangle 104A with three 3D vertices drawn in the reference coordinate system 66. The 2D triangle 180 corresponding to the 3D triangle 104A is drawn on a 2D screen 182 having a 2D reference frame of reference 184. The triangle 180, the screen 182, and the frame of reference 184 are used to indicate that the screen 182 is a virtual screen, regardless of the location of any actual point on the screen for the correspondence generated in step 154. It is drawn with a broken line. Thus, since there is no actual figure of the 2D triangle 182, the triangle 182 is drawn with a broken line.

以下で更に記載されるように、工程１５４は、工程１５２において選択された様々な３Ｄ三角形に対して繰り返される。しかしながら、３Ｄ三角形は、異なってもいいが、３Ｄ三角形が変換される２Ｄ三角形は、同一でもよく、この場合、全ての３Ｄ三角形に対して１つの共通の２Ｄ三角形が存在する。いくつかの実施形態において、共通の２Ｄ三角形の２Ｄ頂点は、２Ｄ三角形が画面１８２を満たすように選択される。この場合、基準座標系１８４における画面１８２は、コーナ（１，１）、（１，−１）、（−１，−１）、及び（−１，１）を有すると想定され、表ＩＩは、対応関係に適合している。 As further described below, step 154 is repeated for the various 3D triangles selected in step 152. However, the 3D triangles may be different, but the 2D triangles to which the 3D triangles are converted may be the same, in which case there is one common 2D triangle for all 3D triangles. In some embodiments, the 2D vertices of a common 2D triangle are selected so that the 2D triangle fills screen 182. In this case, screen 182 in the reference coordinate system 184 is assumed to have corners (1,1), (1, -1), (-1, -1), and (-1,1), and Table II shows , Conforms to the correspondence.

ＧＰへの入力及びＧＰの満たす工程１５６において、ＰＵ４６は、２Ｄ頂点及び２Ｄ三角形の関連する画素の３つの値をＧＰ５０へ渡す。ＧＰ５０は、３つの２Ｄ頂点を受け取ると、２Ｄ画素で三角形１８２を満たすように構成され、それぞれの２Ｄ画素は、それぞれの２Ｄ画面座標（ｘ_ｐ，ｙ_ｐ），ｐ＝１，２，３，・・・を有する。 In step 156 of inputting to the GP and filling the GP, the PU 46 passes three values of the 2D vertices and the related pixels of the 2D triangle to the GP 50. When the GP 50 receives three 2D vertices, the 2D pixels are configured to fill the triangle 182, and each 2D pixel has its own 2D screen coordinates (x _p , y _p ), p = 1, 2, 3 , ...

更に、ＧＰは、補間可能な値として、２Ｄ頂点に関連するそれぞれの画素の３つの値の属性を処理するように構成されている。補間可能な値の処理に関して、それぞれの補間された２Ｄ画素（ｘ_ｐ，ｙ_ｐ）に対して、ＧＰは、三角形１８２の２Ｄ頂点の３つの画素の３つの値の加重平均として画素に関連する画素の３つの値［ｘ_ｗｐ，ｙ_ｗｐ，ｚ_ｗｐ］を算出し、重み付けは、補間された画素の頂点までの近接性により判定される。 Further, the GP is configured to process the attributes of the three values of each pixel associated with the 2D vertices as interpolable values. In relation to the processing of the interpolation possible values, each interpolated 2D pixel (x _{p, y} _p) with respect to, GP is associated with the pixel as a weighted average of the three values of the three pixels of the 2D vertices of the triangle 182 Three values of the pixel [x _wp , y _wp , z _wp ] are calculated, and the weighting is determined by the proximity to the apex of the interpolated pixel.

［ｘ_ｗｐ，ｙ_ｗｐ，ｚ_ｗｐ］に対する式は、等式（１）：

［式中、ｗ_１，ｗ_２，ｗ_３は、２Ｄ画素（ｘ_ｐ，ｙ_ｐ）から２Ｄ頂点（ｘ_ｓ１，ｙ_ｓ１），（ｘ_ｓ２，ｙ_ｓ２），（ｘ_ｓ３，ｙ_ｓ３）までの距離ｄ_１，ｄ_２，ｄ_３に反比例する正規化された重み付け係数である］によって与えられる。 The equation for [x _ww , y _ww , z _ww ] is the equation (1) :.

[In the formula, w ₁ , w ₂ , w ₃ are from 2D pixels (x _p , y _p ) to 2D vertices (x _s1 , y _s1 ), (x _s2 , y _s2 ), (x _s3 , y _s3 ). It is a normalized weighting factor that is inversely proportional to the distances d ₁ , d ₂ , and d _3.].

例えば，ｄ_１＝ｄ_２＝ｄ_３の場合、ｗ_１＝ｗ_２＝ｗ_３＝１／３。第２の例として、ｄ_１＝ｄ_２＝２ｄ_３の場合、ｗ_１＝ｗ_２＝１／４、かつｗ_３＝１／２。 For example, in the case of d ₁ = d ₂ = d ₃ , w ₁ = w ₂ = w ₃ = 1/3. As a second example, in the case of d ₁ = d ₂ = 2d ₃ , w ₁ = w ₂ = 1/4 and w ₃ = 1/2.

工程１５６において、処理ユニットは、等式（１）により、２Ｄ三角形１８２を満たす２Ｄ画素（ｘ_ｐ，ｙ_ｐ）のそれぞれに対して、それぞれの３つの値［ｘ_ｗｐ，ｙ_ｗｐ，ｚ_ｗｐ］の値を求める。 In step 156, the processing unit, according to equation (1), _{for each of the 2D pixels (x p} , y _p ) satisfying the 2D triangle 182, each of its three values [x _wp , y _wp , z _wp ]. Find the value of.

関連付ける工程１５８において、工程１５６において満たされた画素のそれぞれの３つの値［ｘ_ｗｐ，ｙ_ｗｐ，ｚ_ｗｐ］は、三角形１０４Ａに関連付けられ、三角形に対して３つの値のセット｛Ｓ｝を形成し、処理ユニットは、３つの値のセットを記憶する。等式（１）から、それぞれの３つの値のセット｛Ｓ｝は、三角形１０４Ａ内の３Ｄの点に等しいことが明らかとなるだろう。 In the associating step 158, each of the three values [x _wp , y _wp , z _wp ] of the pixels filled in step 156 is associated with the triangle 104A, forming a set of three values {S} for the triangle. However, the processing unit stores a set of three values. From equation (1), it will be clear that each set of three values {S} is equal to a 3D point within triangle 104A.

決定する工程１６０において、処理ユニットは、３つの値のセット、すなわち、所与の３Ｄ三角形１０４内の１組の３Ｄの点がメッシュ１０６内のすべての３Ｄ三角形に対して記憶されているか否かを確認する。３Ｄ三角形１０４がかかるセットを有さずに存在する場合、フローチャートは、工程１５２へ戻る。３Ｄの点のそれぞれの組がメッシュ１０６内の全ての三角形１０４に対して記憶されている場合、フローチャートは、ボクセル化工程１６２へ続く。 In step 160 of determining, whether the processing unit stores a set of three values, i.e., a set of 3D points in a given 3D triangle 104, for all 3D triangles in mesh 106. To confirm. If the 3D triangle 104 does not have such a set, the flowchart returns to step 152. If each set of 3D points is stored for all triangles 104 in the mesh 106, the flowchart continues to voxelization step 162.

工程１５１において形成された３Ｄ体積のボクセル毎のボクセル化工程１６２において、ＰＵ４６は、工程１５８において記憶された３つの値のうち少なくとも１つがボクセル内に含有されているか、又はボクセルに接触しているか否かを確認する。かかるボクセルは、表面２２内に含まれるボクセルであると想定されるとして、「強調される」か、又は「選択される」。３Ｄ体積内のすべての他のボクセル、すなわち、工程１５８において記憶された３つの値を包囲しないか、又は３つの値に接触しないボクセルは、表面２２に含まれないと想定される。 Voxelization for each voxel of 3D volume formed in step 151 In step 162, the PU 46 contains at least one of the three values stored in step 158 in the voxel or is in contact with the voxel. Check if it is. Such voxels are "emphasized" or "selected" as being assumed to be voxels contained within the surface 22. It is assumed that all other voxels in the 3D volume, i.e. voxels that do not enclose or contact the three values stored in step 158, are not included in the surface 22.

ＰＵ４６は、選択されたボクセルのボクセル座標を使用して、画面７４上に表面２２の画像７０をレンダリングする。 The PU 46 renders the image 70 of the surface 22 on the screen 74 using the voxel coordinates of the selected voxels.

上述の実施形態は、例として引用したものであり、本発明は、本明細書の上記で具体的に図示及び記載した内容に限定されるものではないということが理解されるであろう。むしろ、本発明の範囲には、本明細書の上記で説明した様々な特徴の組み合わせ及び部分的な組み合わせ、並びに、上記の説明を読むことで当業者には想到されるであろう、従来技術には開示されていないそれらの変形例及び変更例が含まれるものである。 It will be appreciated that the above embodiments are cited as examples and that the present invention is not limited to what is specifically illustrated and described above herein. Rather, the scope of the present invention will be conceived by those skilled in the art by reading the combinations and partial combinations of various features described above herein, as well as the description above. Includes those modifications and modifications not disclosed in.

〔実施の態様〕
（１）３次元（３Ｄ）レンダリングのための方法であって、
表面の三角形メッシュを画定する一群の３Ｄ三角形を受け取ることであって、該群におけるそれぞれの３Ｄ三角形は、それぞれの３Ｄ座標を有する３つの３Ｄ頂点を有する、ことと、
それぞれの３Ｄ三角形を、該３Ｄ頂点にそれぞれ対応する３つの２次元（２Ｄ）頂点を有する、対応する２Ｄ三角形に変換することであって、それぞれの２Ｄ頂点は、それぞれの２Ｄ画素座標及び対応する３Ｄ頂点の３Ｄ座標に対応する画素属性の３つの値（triplet）を有する、ことと、
それぞれの２Ｄ頂点の該画素属性の３つの値を補間可能な値として処理するグラフィックプロセッサへ、それぞれの２Ｄ三角形を渡すことと、
該グラフィックプロセッサにおいて、該２Ｄ三角形の該２Ｄ頂点の該画素属性間の補間によって、それぞれの２Ｄ三角形内の画素に対してそれぞれの補間された画素属性の３つの値を算出することと、
該表面の３Ｄ画像を、該グラフィックプロセッサによって算出された該補間された画素属性を該３Ｄ画像内のボクセル座標に変換することによって、レンダリングすることと、を含む、方法。
（２）所与の２Ｄ三角形を前記グラフィックプロセッサへ渡した後、該所与の２Ｄ三角形を該所与の２Ｄ三角形内の画素で満たすことを含む、実施態様１に記載の方法。
（３）前記補間された画素属性は、それぞれの２Ｄ頂点の前記画素属性の３つの値の重み付けされた補間を含む、実施態様１に記載の方法。
（４）前記重み付けされた補間は、所与の２Ｄ頂点の前記画素属性の３つの値に、所与の画素から該所与の２Ｄ頂点までの距離に反比例する重みを適用することを含む、実施態様３に記載の方法。
（５）前記補間された画素属性をボクセル座標に変換することは、ボクセルからなる直方体内に前記三角形メッシュを包囲することと、前記補間された画素属性を含有するか、又は前記補間された画素属性に接触するボクセルを、前記表面のボクセルとして選択することと、を含む、実施態様１に記載の方法。 [Implementation mode]
(1) A method for three-dimensional (3D) rendering,
Receiving a group of 3D triangles defining a surface triangle mesh, with each 3D triangle in the group having three 3D vertices with their respective 3D coordinates.
Converting each 3D triangle into a corresponding 2D triangle, each having three two-dimensional (2D) vertices corresponding to the 3D vertice, each 2D vertice having its own 2D pixel coordinates and corresponding. Having three values (triplets) of pixel attributes corresponding to the 3D coordinates of the 3D vertices,
Passing each 2D triangle to a graphics processor that processes the three values of the pixel attribute of each 2D vertex as interpolable values,
In the graphic processor, by interpolating between the pixel attributes of the 2D vertices of the 2D triangle, three values of each interpolated pixel attribute are calculated for the pixels in each 2D triangle.
A method comprising rendering a 3D image of the surface by converting the interpolated pixel attributes calculated by the graphics processor into voxel coordinates within the 3D image.
(2) The method of embodiment 1, comprising passing a given 2D triangle to the graphics processor and then filling the given 2D triangle with pixels within the given 2D triangle.
(3) The method of embodiment 1, wherein the interpolated pixel attributes include weighted interpolation of the three values of the pixel attributes of each 2D vertex.
(4) The weighted interpolation comprises applying weights inversely proportional to the distance from a given pixel to the given 2D vertex to the three values of the pixel attribute of a given 2D vertex. The method according to the third embodiment.
(5) Converting the interpolated pixel attribute to voxel coordinates includes surrounding the triangular mesh in a rectangular body composed of voxels and containing the interpolated pixel attribute or the interpolated pixel. The method of embodiment 1, wherein the voxels that come into contact with the attributes are selected as the voxels on the surface.

（６）前記表面は、心腔内に含まれる、実施態様１に記載の方法。
（７）それぞれの２Ｄ三角形は、１つの共通の２Ｄ三角形を含む、実施態様１に記載の方法。
（８）それぞれの２Ｄ三角形は、仮想画面を満たすように構成されている、実施態様１に記載の方法。
（９）３次元（３Ｄ）レンダリングのための装置であって、
処理ユニットであって、
表面の三角形メッシュを画定する一群の３Ｄ三角形を受け取ることであって、該群におけるそれぞれの３Ｄ三角形は、それぞれの３Ｄ座標を有する３つの３Ｄ頂点を有する、ことと、
それぞれの３Ｄ三角形を、該３Ｄ頂点にそれぞれ対応する３つの２次元（２Ｄ）頂点を有する、対応する２Ｄ三角形に変換することであって、それぞれの２Ｄ頂点は、それぞれの２Ｄ画素座標及び対応する３Ｄ頂点の３Ｄ座標に対応する画素属性の３つの値を有する、ことと、を行うように構成されている、処理ユニットと、
グラフィックプロセッサであって、
それぞれの２Ｄ三角形を受け取り、それぞれの２Ｄ頂点の該画素属性の３つの値を補間可能な値として処理することと、
該２Ｄ三角形の該２Ｄ頂点の該画素属性間の補間によって、それぞれの２Ｄ三角形内の画素に対してそれぞれの補間された画素属性の３つの値を算出することと、を行うように構成されている、グラフィックプロセッサと、を備え、
該処理ユニットは、該表面の３Ｄ画像を、該グラフィックプロセッサによって算出された該補間された画素属性を該３Ｄ画像内のボクセル座標に変換することによって、レンダリングするように構成されている、装置。
（１０）前記グラフィックプロセッサは、前記画素で所与の２Ｄ三角形を満たすように構成されている、実施態様９に記載の装置。 (6) The method according to embodiment 1, wherein the surface is contained in a heart chamber.
(7) The method of embodiment 1, wherein each 2D triangle comprises one common 2D triangle.
(8) The method according to embodiment 1, wherein each 2D triangle is configured to fill a virtual screen.
(9) A device for three-dimensional (3D) rendering.
It ’s a processing unit,
Receiving a group of 3D triangles defining a surface triangle mesh, with each 3D triangle in the group having three 3D vertices with their respective 3D coordinates.
Converting each 3D triangle into a corresponding 2D triangle, each having three two-dimensional (2D) vertices corresponding to the 3D vertice, each 2D vertice having its own 2D pixel coordinates and corresponding. A processing unit that has three values of pixel attributes corresponding to the 3D coordinates of a 3D vertex and is configured to do so.
It ’s a graphics processor
Receiving each 2D triangle and processing the three values of the pixel attribute of each 2D vertex as interpolable values.
It is configured to calculate the three values of each interpolated pixel attribute for the pixels in each 2D triangle by interpolating between the pixel attributes of the 2D vertices of the 2D triangle. It has a graphics processor and
The processing unit is configured to render a 3D image of the surface by converting the interpolated pixel attributes calculated by the graphics processor into voxel coordinates in the 3D image.
(10) The apparatus according to embodiment 9, wherein the graphic processor is configured to fill a given 2D triangle with the pixels.

（１１）前記補間された画素属性は、それぞれの２Ｄ頂点の前記画素属性の３つの値の重み付けされた補間を含む、実施態様９に記載の装置。
（１２）前記重み付けされた補間は、所与の２Ｄ頂点の前記画素属性の３つの値に、所与の画素から該所与の２Ｄ頂点までの距離に反比例する、重みを適用することを含む、実施態様１１に記載の装置。
（１３）前記処理ユニットは、ボクセルからなる直方体内に前記三角形メッシュを包囲するように、かつ前記補間された画素属性を含有するか、又は前記補間された画素属性に接触するボクセルを、前記表面のボクセルとして選択するように構成されている、実施態様９に記載の装置。
（１４）前記表面は、心腔内に含まれている、実施態様９に記載の装置。
（１５）それぞれの２Ｄ三角形は、１つの共通の２Ｄ三角形を含む、実施態様９に記載の装置。 (11) The apparatus according to embodiment 9, wherein the interpolated pixel attribute includes weighted interpolation of three values of the pixel attribute of each 2D vertex.
(12) The weighted interpolation involves applying weights to the three values of the pixel attribute of a given 2D vertex, which are inversely proportional to the distance from a given pixel to the given 2D vertex. , The apparatus according to the eleventh embodiment.
(13) The processing unit places the voxels in a rectangular parallelepiped composed of voxels so as to surround the triangular mesh and contains the interpolated pixel attributes or contacts the interpolated pixel attributes on the surface. 9. The apparatus according to embodiment 9, which is configured to be selected as a voxel of.
(14) The device according to embodiment 9, wherein the surface is contained in a heart chamber.
(15) The device of embodiment 9, wherein each 2D triangle comprises one common 2D triangle.

（１６）それぞれの２Ｄ三角形は、仮想画面を満たすように構成されている、実施態様９に記載の装置。 (16) The device according to embodiment 9, wherein each 2D triangle is configured to fill a virtual screen.

Claims

A method for 3D rendering,
Receiving a group of 3D triangles defining a surface triangle mesh, with each 3D triangle in the group having three 3D vertices with their respective 3D coordinates.
Converting each 3D triangle into a corresponding 2D triangle, each having three two-dimensional (2D) vertices corresponding to the 3D vertice, each 2D vertice having its own 2D pixel coordinates and corresponding. have a three values of pixels attributes corresponding to the 3D coordinates of the 3D vertices, 2D vertices of the 2D pixel coordinates are the same in each 2D triangle, and that,
Passing each 2D triangle to a graphics processor that processes the three values of the pixel attribute of each 2D vertex as interpolable values,
In the graphic processor, by interpolating between the pixel attributes of the 2D vertices of the 2D triangle, three values of each interpolated pixel attribute are calculated for the pixels in each 2D triangle.
A method comprising rendering a 3D image of the surface by converting the interpolated pixel attributes calculated by the graphics processor into voxel coordinates within the 3D image.

The method of claim 1, comprising passing a given 2D triangle to the graphics processor and then filling the given 2D triangle with pixels within the given 2D triangle.

The method of claim 1, wherein the interpolated pixel attributes include weighted interpolation of the three values of the pixel attributes of each 2D vertex.

3. The weighted interpolation comprises applying weights inversely proportional to the distance from a given pixel to the given 2D vertex to the three values of the pixel attribute of a given 2D vertex. The method described in.

Converting the interpolated pixel attribute to voxel coordinates encloses the triangular mesh in a voxel rectangular body and includes the interpolated pixel attribute or contacts the interpolated pixel attribute. The method according to claim 1, wherein the voxels to be used are selected as the voxels on the surface.

The method of claim 1, wherein the surface is contained within a heart chamber.

A device for 3D rendering
It ’s a processing unit,
Receiving a group of 3D triangles defining a surface triangle mesh, with each 3D triangle in the group having three 3D vertices with their respective 3D coordinates.
Converting each 3D triangle into a corresponding 2D triangle, each having three two-dimensional (2D) vertices corresponding to the 3D vertice, each 2D vertice having its own 2D pixel coordinates and corresponding. have a three values of pixels attributes corresponding to the 3D coordinates of the 3D vertices, 2D vertices of the 2D pixel coordinates is configured to perform, and be the same in each 2D triangle, a processing unit,
It ’s a graphics processor
Receiving each 2D triangle and processing the three values of the pixel attribute of each 2D vertex as interpolable values.
It is configured to calculate the three values of each interpolated pixel attribute for the pixels in each 2D triangle by interpolating between the pixel attributes of the 2D vertices of the 2D triangle. It has a graphics processor and
The processing unit is configured to render a 3D image of the surface by converting the interpolated pixel attributes calculated by the graphics processor into voxel coordinates in the 3D image.

The device of claim 7 , wherein the graphics processor is configured to fill a given 2D triangle with the pixels.

The apparatus according to claim 7 , wherein the interpolated pixel attribute includes weighted interpolation of three values of the pixel attribute of each 2D vertex.

The weighted interpolation comprises applying weights to the three values of the pixel attributes of a given 2D vertex, which are inversely proportional to the distance from a given pixel to the given 2D vertex. 9. The apparatus according to 9.

The processing unit uses a voxel as a voxel on the surface so as to surround the triangular mesh in a rectangular parallelepiped composed of voxels and contains the interpolated pixel attribute or contacts the interpolated pixel attribute. The device according to claim 7 , which is configured to be selected.

The device of claim 7 , wherein the surface is contained within a heart chamber.