JP4061013B2 - 3D shape generation method, storage medium storing program for executing the method, and 3D shape generation apparatus - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a three-dimensional shape generation method implemented in an information processing apparatus such as a dedicated three-dimensional shape processing apparatus or a personal computer, and more particularly to a triangular mesh generation method.
[0002]
[Prior art]
In recent years, with the spread of multimedia use on the Internet, 3D shape processing systems configured using a graphics display device and a computer have become widespread, and the stored 3D shape data is read and a 3D shape model is displayed. It is widely performed to generate a three-dimensional shape, to deform the generated three-dimensional shape, and to calculate a volume, a center of gravity, and the like of the three-dimensional shape.
Under such circumstances, a signed distance function is generated based on three-dimensional point cloud data or a distance image recently acquired using a three-dimensional measuring instrument or the like, and the marching cubes method (reference document [1]). For example, a method of automatically generating a three-dimensional shape model represented by a triangular mesh using the same phase plane generation method (see References [2] and [3]) has been proposed. The advantages of these methods are as follows.
A shape having a phase structure such as a through hole can also be generated.
Even if there is a missing point cloud, a surface that fills the hole can be generated.
Even if there is an error due to the nature of the three-dimensional measuring instrument or measurement conditions, it is less susceptible to the error.
Even when the measured distribution of sample points is non-uniform, sample points having a uniform distribution can be obtained by functioning.
However, this method has the following drawbacks.
The reproducibility of acute angle features is weak. Even artificial parts such as machine parts with sharp ridges are always reproduced as rounded shapes.
The reproducibility of thin and thin shapes is weak. Since the reproducibility depends on the position of the grid, it cannot be said that the shape can always be reproduced especially when the thickness or the thickness is less than the grid interval.
Supplementing on the reproducibility of the acute angle feature described above, in the marching cubes method, since the vertex position of the triangular mesh is limited on the lattice axis, the feature such as the acute angle ridge line cannot be sufficiently captured. Further, even with a lattice point connection method (see reference [4]) in which the vertex positions of the triangular mesh can be freely arranged in the voxel, the acute angle ridge line of the convex portion can be reproduced, but the acute angle ridge line of the concave portion cannot be reproduced. Regarding the reproducibility of thin shapes and thin shapes, the marching cubes method has a case where the shape can be reproduced (b) and a case where the shape cannot be reproduced (a) depending on the set position of the lattice as shown in FIG. In particular, the reproducibility of thin and narrow shapes below the lattice spacing is not guaranteed.
[0003]
[Problems to be solved by the invention]
As described above, in the prior art, when generating a triangular mesh from a distance image obtained by measuring with a three-dimensional measuring instrument or the like, the acute-angle ridgeline having an angular shape, particularly the acute-angle ridgeline corresponding to the concave portion is lost. There is a problem that thin and narrow shapes less than the lattice spacing are lost.
An object of the present invention is to solve such a problem of the prior art, and when generating a triangular mesh from a distance image obtained by measuring with a three-dimensional measuring instrument or the like, an acute ridgeline having an angular shape, particularly To provide a method for generating a three-dimensional shape capable of solving the problem that a sharp ridge line corresponding to a concave portion is lost, the problem that a thin shape and a thin shape less than a lattice interval are lost, and the problem that the shape changes depending on the lattice position. It is in.
[0004]
[Means for Solving the Problems]
  In order to solve the above-mentioned problem, in the invention according to claim 1, a three-dimensional shape is generated by generating a triangular mesh from a distance image.3D shape generatorIn the three-dimensional shape generation method,The distance image volume generation meansGenerating a volume model composed of individual voxels having one of the three attribute values of contour, internal, and external from the distance image;The basic mesh generation means acquires triangle generation information and rotation information from adjacent 8 voxel attribute values, rotates and converts 8 voxels using the acquired rotation information, and uses the rotation converted 8 voxels and triangle generation information.Generating a basic triangular mesh;Vertex fitting means detects at least two types of vertices among thin plate boundary vertices, non-manifold edge connecting vertices, non-manifold vertices, and general vertices as vertices of the basic triangular mesh, and the types of detected vertices Different vertex movement methods are selected according toGenerate triangle mesh by moving the vertex of basic triangle meshDoProcess,Move the thin plate boundary vertices by cutting the basic triangular meshes around the thin plate boundary vertices along the thin plate boundary ridges and moving the resulting multiple vertices until they are on the distance image mesh. Generating a new triangular surface in the gap of the basic triangular mesh generated by movement;TheExecuteIt is characterized by that.
  In the invention according to claim 2, the claim1In the described three-dimensional shape generation method,The vertex fitting means isA step of detecting a quadrangular surface composed of a set of two basic triangular meshes, a step of detecting a thin plate boundary ridge line from the combination of the detected quadrangular surfaces, and detecting the thin plate boundary vertices from the detected thin plate boundary ridge line And a process ofExecuteIt is characterized by that.
  In the invention according to claim 3, the claim1In the three-dimensional shape generation method described inThe vertex fitting means isA step of detecting a quadrangular surface comprising a set of two basic triangular meshes, a step of detecting a non-manifold ridge line from a combination of detected quadrangular surfaces, and a step of detecting the non-manifold ridge line connection vertex TheExecuteIt is characterized by that.
  In the invention according to claim 4, the claim1In the three-dimensional shape generation method described inThe vertex fitting means isSelect two general ridge lines that are orthogonal to each other across the non-manifold ridge line connection vertices, cut a plurality of basic triangular meshes around the non-manifold ridge line connection vertices along the two selected general ridge lines, and As a result, the non-manifold ridge line connected vertices are moved by moving the plurality of vertices generated on the distance image mesh, and a new triangle is added to the gap of the basic triangular mesh generated by the movement. Process for generating facesRunIt is characterized by that.
[0005]
  In the invention according to claim 5,Claim1In the three-dimensional shape generation method described inThe vertex fitting means isDetects a quadrangular surface consisting of a set of two basic triangular meshesAnd the processDetecting non-manifold vertices from combinations of detected quadrangular surfacesRunIt is characterized by that.
  In the invention according to claim 6,Claim1In the described three-dimensional shape generation method,The vertex fitting means isA plurality of pairs of ridge lines with two ridge lines orthogonal to each other across the non-manifold vertices are selected, and a plurality of ridge lines around the non-manifold vertices are selected along each ridge line of the selected plurality of ridge lines. The non-manifold vertices are moved by separating the basic triangular mesh, and moving the non-manifold vertices by moving a plurality of vertices generated as a result on the distance image mesh, and the basic triangular mesh generated by the movement is moved. The process of creating a new triangular surface in the clearanceExecuteIt is characterized by that.
  In the invention according to claim 7,Claim1In the three-dimensional shape generation method described inThe vertex fitting means isA step of detecting a quadrangular surface comprising a set of two basic triangular meshes, a step of selecting a surface configuration pattern from the combination of detected quadrangular surfaces, and a new vertex and ridge for each selected surface configuration pattern GeneratingRunThe general vertex is moved by moving the newly generated vertex until it falls on the distance image mesh.
  In the invention according to claim 8,Claim1To claims7One of1 itemIn the three-dimensional shape generation method described inThe vertex fitting means isThe average normal vector of the basic triangular mesh adjacent to the vertex is calculated, the diagonal vector is obtained from the obtained average normal vector, and the vertex is moved by moving along the diagonal vector until it intersects the distance image mesh. Move until it is on the distance image meshExecute the processIt is characterized by that.
  In the invention according to claim 9,A computer-readable storage medium storing a program for causing a computer to execute the process according to any one of claims 1 to 8.
  In the invention according to claim 10,In a 3D shape generation device that generates a 3D shape by generating a triangular mesh from a distance image, a volume model consisting of individual voxels with one of the three attribute values of contour, inside, and outside is generated from the distance image. DoDistance image volume generation meansWhen,Triangle generation information and rotation information are acquired from adjacent 8 voxel attribute values, 8 voxels are rotated and converted using the acquired rotation information, and the 8 voxels and triangle generation information that have been converted to rotation are used.Generate a basic triangular meshBasic mesh generation meansWhen,As the vertices of the basic triangular mesh, at least two types of vertices are detected among thin plate boundary vertices, non-manifold ridge line connection vertices, non-manifold vertices, and general vertices, and differ according to the detected vertex type. Select the vertex movement methodMeans for generating a triangular mesh by moving the vertices of the basic triangular mesh;Move the thin plate boundary vertices by cutting the basic triangular meshes around the thin plate boundary vertices along the thin plate boundary ridges and moving the resulting multiple vertices until they are on the distance image mesh. Vertex fitting means comprising: means for newly generating a triangular surface in the gap of the basic triangular mesh generated by movement;It is provided with.
  In the invention according to claim 11,ClaimTo 10In the described three-dimensional shape generation apparatus,The vertex fitting means includesMeans for detecting a quadrangular surface comprising a set of two basic triangular meshes, means for detecting a thin plate boundary ridge line from the combination of detected quadrangular surfaces, and detecting the thin plate boundary vertices from the detected thin plate boundary ridge line And means for carrying out the above.
  In the invention according to claim 12,ClaimTo 10In the described three-dimensional shape generation apparatus,
  The vertex fitting means includes theMeans for detecting a quadrilateral surface comprising a set of two basic triangular meshes, means for detecting a non-manifold ridge line from the combination of detected quadrilateral surfaces, and means for detecting the non-manifold ridge line connection vertex , Provided.
  In the invention according to claim 13,ClaimTo 10In the described three-dimensional shape generation apparatus,The vertex fitting means includesSelect two general ridge lines that are orthogonal to each other across the non-manifold ridge line connection vertices, cut a plurality of basic triangular meshes around the non-manifold ridge line connection vertices along the two selected general ridge lines, and As a result, the non-manifold ridge line connected vertices are moved by moving the plurality of vertices generated on the distance image mesh, and a new triangle is added to the gap of the basic triangular mesh generated by the movement. A means for generating a surface is provided.
  In the invention according to claim 14,Claim10In the three-dimensional shape generation apparatus described inThe vertex fitting means includesThe present invention is characterized by comprising means for detecting a quadrangular surface comprising a set of two basic triangular meshes and means for detecting a non-manifold vertex from a combination of the detected quadrangular surfaces.
  In the invention according to claim 15,Claim10In the three-dimensional shape generation apparatus described inThe vertex fitting means includesA plurality of pairs of ridge lines with two ridge lines orthogonal to each other across the non-manifold vertices are selected, and a plurality of ridge lines around the non-manifold vertices are selected along each ridge line of the selected plurality of ridge lines. The non-manifold vertices are moved by separating the basic triangular mesh, and moving the non-manifold vertices by moving a plurality of vertices generated as a result on the distance image mesh, and the basic triangular mesh generated by the movement is moved. A means for newly generating a triangular surface in the clearance is provided.
  In the invention according to claim 16,Claim10In the three-dimensional shape generation apparatus described in
  The vertex fitting means includesMeans for detecting a quadrangular surface consisting of a set of two basic triangular meshes, means for selecting a surface configuration pattern from the combination of detected quadrangular surfaces, and new vertices and ridge lines for each selected surface configuration pattern And generating the vertices by moving the newly generated vertices until they are on the distance image mesh.
  In the invention according to claim 17,Claim10To claims16One of1 itemIn the three-dimensional shape generation apparatus described inThe vertex fitting means includesBy calculating the average normal vector of the basic triangular mesh adjacent to the vertex, obtaining the diagonal vector from the obtained average normal vector, and moving the vertex along the diagonal vector until it intersects the distance image mesh, the vertex Is moved until it falls on the distance image mesh.
[0006]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 31 is a hardware configuration block diagram of a three-dimensional shape processing apparatus showing an embodiment of the present invention. As shown in the figure, the three-dimensional shape processing apparatus of this embodiment temporarily stores a CPU 1 for controlling the entire apparatus according to a program or performing three-dimensional shape processing including processing according to the present invention, and programs and data. Memory 2, external storage device 3 that stores various data such as programs and 3D shape data, mouse, keyboard, etc. to specify 3D shape model and shape elements constituting it, An input device 4 that performs input for generation and shape deformation, a display device 5 that includes a graphics display and displays a three-dimensional shape model, and the like are provided.
In the 3D shape processing system of the present invention using such hardware and program, in the 3D shape generation method for generating a triangular mesh from a distance image, any one of the three attribute values of contour, inside, and outside is selected. A volume model consisting of individual voxels with a distance image is generated from a distance image, a basic triangular mesh is generated using a combination of the attribute values of adjacent voxels, and a manifold vertex is detected from the generated basic triangular mesh Then, the fitting process is performed. The distance image is an image obtained by perspective projection or parallel projection with the photographing position as the viewpoint, and each pixel constituting the distance image (minimum unit constituting an image portion distinguished from the background) Has distance information from the shooting position as an attribute value. Further, the fitting process is a process for bringing the shape close to the actual shape.
[0007]
In the following, preparation and prerequisites are shown prior to the operation flow shown in FIG.
(1) A pointer to information for generating a triangle based on a triangle surface generation pattern as shown in FIG. 2 and rotation information (described later) are stored in advance in a triangle generation lookup table. The look-up table is accessed by using as an address a combination of attribute values of eight adjacent voxels as shown in FIG. In the example of FIG. 3, in the lookup table, the address of 1 byte is “01011111” (V0 shown in FIG. 3 corresponds to bit 0, so the bit string is opposite to that in FIG. 3). To access. A voxel is an individual rectangular parallelepiped generated by subdividing the bounding box (bounding box) of the three-dimensional shape model in the x, y, and z directions, and each voxel has the three-dimensional shape. Information indicating one of the internal voxel, the contour voxel, and the external voxel is provided as an attribute value depending on whether the model is inside, at the contour position, or outside. 2 and 3, eight voxels are indicated by white circles or black circles indicating the respective center points (see FIG. 4). White circles are external voxels and black circles are internal or contour voxels. A rectangular parallelepiped formed by connecting eight center points is called a cube. Adjacent cubes are 8 voxels extracted by overlapping, for example, 4 voxels in any direction. In FIG. 2, there is no triangular surface generation pattern connected to the center point (external point) of the external voxel because the external point is outside the triangular surface forming the contour.
(2) In the lookup table used in the present invention, triangle generation information (surface generation information) as shown in FIG. 5 which is information indicating a place where a surface is generated is stored in advance (a pointer is stored). You can leave it). In FIG. 5, the triangle generation information is shown in 6 bits in association with 6 planes (F0 to F5), but in actuality, for example, it is expressed using 1 byte.
(3) The distance image used in the present invention is the distance information (indicating the distance from the shooting position) in the depth direction (direction from the shooting position to the subject), camera position, camera shooting direction, viewing angle, etc. for each pixel. Has shooting information. That is, it is assumed that each pixel can be easily converted into a coordinate value in a three-dimensional space using perspective transformation.
(4) In the volume model used in the present invention, the size in each direction (the number of voxels in each direction) Nx, Ny, Nz (all positive integers) is determined in advance. However, if necessary, the user can specify the size before use. If the size is increased, a triangular mesh with finer resolution can be obtained. However, a working memory space having a size proportional to Nx, × Ny, × Nz is required.
[0008]
The outline of the operation of this embodiment will be described below according to the operation flow shown in FIG.
First, a volume model composed of voxels having any one of three attribute values of outline, inside, and outside is generated from distance image data acquired using a three-dimensional measuring device (distance image volume generation step) (S1). .
Subsequently, while sequentially shifting the position of the voxel in the volume model, the combination value of the attribute values of the adjacent 8 voxels is acquired, and the basic triangle mesh is generated using the triangle generation information stored at the address of the value. (Basic mesh generation step) (S2).
Then, a corresponding surface configuration pattern is extracted from the basic triangular mesh, the vertex of the basic triangular mesh is moved using the surface configuration pattern, and fitting processing is performed to deform the basic triangular mesh according to the vertex movement (vertex) Fitting step) (S3).
Next, the distance image volume generation step (S1) will be described with reference to the operation flowchart shown in FIG.
First, a distance image mesh having the pixels of the distance image as vertices is generated (S11). Adjacent information is obtained when the pixels of the distance image are regularly arranged. Therefore, a distance image mesh is generated by generating a triangle having three adjacent pixels as vertices. If each pixel of the distance image is irregularly arranged, a distance image mesh is generated by using Delaunay triangulation (reference document [5]) for the coordinate value of each pixel of the distance image. If there are a plurality of distance image data taken from different directions, a distance image mesh is generated for each distance image data.
Subsequently, a bounding box is generated from the distance image mesh, and the bounding box is subdivided into a structure including a plurality of voxels. For the time being, an initial volume model is generated in which all the voxels are internal voxels (internal Voxel generation step) (initial volume generation) (S12).
Then, a contour voxel is detected from the volume model (described later), and attribute information indicating that it is a contour voxel is set in the voxel (contour voxel generation step) (S13).
Further, an external voxel is detected from the volume model (described later), and attribute information indicating that the voxel is an external voxel is set (external voxel generation step) (S14).
[0009]
Next, the internal voxel generation step (S12) will be described with reference to the operation flowchart shown in FIG.
First, a bounding box (bounding box) including all vertex coordinates of the distance image mesh is obtained (S121). The bounding box calculates the maximum value Xmin, Ymin, Zmin and the minimum value Xmax, Ymax, Zmax for each element X, Y, Z of the three-dimensional coordinates (X, Y, Z) of each vertex coordinate, It is obtained as a rectangular parallelepiped with the eight coordinates B1 to B8 combined with the minimum values as follows.
B1: (Xmin, Ymin, Zmin), B2: (Xmax, Ymin, Zmin), B3: (Xmin, Ymax, Zmin), B4: (Xmax, Ymax, Zmin), B5: (Xmin, Ymin, Zmax), B6: (Xmax, Ymin, Zmax), B7: (Xmin, Ymax, Zmax), B8: (Xmax, Ymax, Zmax)
Subsequently, the bounding box is enlarged by adding or subtracting a constant δ to each vertex of the bounding box as shown below (S122). δ is a small positive number so that each pixel is distributed on the surface of the bounding box and does not cause a subtle boundary judgment problem.
B1: (Xmin−δ, Ymin−δ, Zmin−δ), B2: (Xmax + δ, Ymin−δ, Zmin−δ), B3: (Xmin−δ, Ymax + δ, Zmin−δ), B4: (Xmax + δ, Ymax + δ, Zmin−δ), B5: (Xmin−δ, Ymin−δ, Zmax + δ), B6: (Xmax + δ, Ymin−δ, Zmax + δ), B7: (Xmin −δ, Ymax + δ, Zmax + δ), B8: (Xmax + δ, Ymax + δ, Zmax + δ)
Then, a volume model composed of voxels generated by dividing the bounding box by a predetermined size (number) Nx, Ny, Nz with the vertex B1 of the bounding box as the origin of the volume model is created (S123). .
Furthermore, all the initial attribute values of the voxels are set to internal voxels (S124).
[0010]
Next, the outline voxel generation step (S13) will be described with reference to the operation flowchart shown in FIG.
First, a contour voxel attribute is set to a voxel including the three-dimensional coordinates (X, Y, Z) of each vertex of the distance image mesh (S131). The voxel containing the coordinates (X, Y, Z) of each vertex is detected using the following equation (1), and the contour voxel attribute is set to the detected voxel.
(Xi, Yi, Zi) = ((X−Xmin) / Nx, (Y−Ymin) / Ny, (Z−Zmin) / Nz) (1)
Here, (Xi, Yi, Zi) is the address (number) of the voxel, and the decimal part of each element is rounded down and rounded to an integer.
Next, for each triangle of the distance image mesh, search for a maximum of three voxels containing the vertices by equation (1), and the voxel address defined as follows, corresponding to the bounding box containing the three voxels: A voxel space existing in the range of (X, Y, Z) is obtained (S132).
min (X1, X2, X3) ≦ X ≦ max (X1, X2, X3),
min (Y1, Y2, Y3) ≦ Y ≦ max (Y1, Y2, Y3),
min (Z1, Z2, Z3) ≤Z≤max (Z1, Z2, Z3).
Here, (X1, Y1, Z1), (X2, Y2, Z2), and (X3, Y3, Z3) are assumed to be three voxel addresses including triangle vertices.
Further, intersection check with each triangle of the distance image mesh is performed for each voxel included in each voxel space as described above, and the intersecting voxel is set as a contour voxel (S133). Note that, in order to save calculation cost, the intersection check is not performed for those that have already been determined as contour voxels in step S131.
[0011]
Next, the external voxel generation step (S14) will be described according to the operation flow chart shown in FIG.
First, a plurality of pyramid-shaped viewpoint volume spaces (prism-shaped volume spaces in the case of parallel projection) composed of spaces from the distance image capturing position to each triangular surface of the distance image mesh are created (S141).
Subsequently, an intersection check between each viewpoint volume space and the volume model is performed, and an external voxel attribute is set for the intersected voxel (S142). In order to save the calculation cost, those already determined as external voxels and those determined as contour voxels in step S131 and step S133 are left without being subjected to the intersection check.
Thus, a voxel that is neither a contour voxel nor an external voxel becomes the final internal voxel, and if there is a voxel outside the contour voxel that does not intersect the viewpoint volume space, that voxel is also included in the internal voxel. turn into. For this reason, the distance images are taken from all directions, and all the outside of the subject intersects the viewpoint volume space.
[0012]
Next, the basic mesh generation step (S2) will be described with reference to the operation flowchart shown in FIG.
First, rotation information and triangle generation information are acquired from an address formed by a combination of attribute values of adjacent 8 voxels in the lookup table (S21). Or the pointer memorize | stored in the lookup table may be acquired, and you may acquire them from the pointing destination. The triangle generation information is collected as shown in FIG. 2 by combining the rotation transformations according to the rotation information into one. As shown in Fig. 11, the rotation information is defined as (Rx, Ry, Rz), where the number of rotations is 90 ° around X, Y, and Z axes. It is. FIG. 11 shows an example in which the rotation of 90 degrees around the X axis is performed once. In FIG. 11, white and black circles shown below the cube have the same meaning as in FIG.
Subsequently, eight voxels (cube) are rotationally converted by the rotation information (Rx, Ry, Rz) (S22). An area storing an address of 8 voxels is prepared at the addressing destination, and rotation conversion is performed. For example, in the example shown in FIG. 11, in the lookup table, the rotation information (1,0,0) and (a) diagrams are associated with the address information “11111100” of the combination shown in FIG. The address “11001111” is stored, and the address “11001111” is obtained to obtain the triangle generation pattern of FIG. (A), rotate it 90 degrees around the X axis, and (b) the triangle of FIG. Get the generation pattern.
Further, a basic triangular mesh is generated using the rotationally converted 8 voxels and the triangular generation information (S23). The coordinates of the center point of the contour voxel are acquired, and a triangle having the center point as the vertex of the triangular mesh is created. For example, in the example of FIG. 11, four basic triangular meshes are created. Each thick line of the basic triangular mesh shown in FIG. 2 or FIG. 11 is a ridge line of the three-dimensional shape model.
Thus, when the basic triangular mesh is obtained for the entire volume model of interest, the vertex fitting (S3) shown in FIG. 1 shows the vertices of the basic triangular mesh as shown in FIG. To move the surface of the basic triangular mesh closer to the actual contour surface. The outline of the vertex fitting method for the basic triangular mesh in the vertex fitting step S3 shown in FIG. 1 will be described below based on the operation flow shown in FIG. As will be described later, this embodiment is characterized in that vertices are moved by different movement methods depending on the types of vertices of the basic triangular mesh. Thereby, even in the case of a thin plate whose actual three-dimensional shape is less than the size of, for example, one voxel, a three-dimensional shape close to the actual one can be generated.
[0013]
As shown in FIG. 13, first, thin plate boundary vertices are detected from the target volume model (S31). Then, the thin plate boundary vertex is moved in a direction close to an actual three-dimensional shape (S32). In addition, a thin plate refers to a case in which a quadrangular surface consisting of a set of two basic triangular meshes is back-to-back and in close contact with each other, and the actual three-dimensional shape has a thickness less than 1 voxel. To tell. An example of a thin plate is shown in FIG. In FIG. 15, the black circle is the thin plate boundary vertex. The thin plate boundary will be described later.
Next, the non-manifold ridge line connection vertex is detected (S33), and the non-manifold ridge line connection vertex is moved by a method different from the case of the thin plate boundary vertex (S34).
Subsequently, the non-manifold vertex is detected (S35), the non-manifold vertex is moved (S36), and the general vertex is further moved (S37).
[0014]
Next, the thin plate boundary vertex detection method shown in step S31 of FIG. 13 will be described according to the operation flow shown in FIG.
First, a quadrangular surface composed of a set of two basic triangular meshes adjacent to each vertex is detected, and a quadrangular surface arrangement flag which is the arrangement information of the quadrangular surface is acquired (S311). As shown in FIG. 16, since there are 24 types of quadrangular surfaces around each vertex, the arrangement information of the quadrangular surfaces is represented by a 24-bit quadrangular surface arrangement flag. R0 to R23 are sequentially set from the least significant bit to the most significant bit of the quadrangular surface arrangement flag. If Ri is 1, the i-th square surface exists, and if Ri is 0, the i-th square surface does not exist. Such a quadrangular surface arrangement flag is created when the basic triangular mesh is generated in step S2 shown in FIG.
Subsequently, the arrangement information of the thin plate, that is, the presence or absence of the thin plate is obtained from the combination of the presence or absence of the quadrangular surface (S312). As shown in FIG. 17, since there are 12 kinds of thin plates around each vertex, the thin plate arrangement information is represented by a 12-bit thin plate arrangement flag. L0 to L11 in order from the least significant bit to the most significant bit of the thin plate placement flag. If Li is 1, the i-th thin plate exists, and if Li is 0, the i-th thin plate does not exist. Each bit of such a thin plate arrangement flag is calculated using the logical product (&) of the bits of the quadrangular surface arrangement flag as follows. That is, if the quadrangular surface is on both sides, it is 1.
L0 = R0 & R5, L1 = R1 & R4, L2 = R2 & R7, L3 = R3 & R6,
L4 = R8 & R13, L5 = R9 & R12, L6 = R10 & R15, L7 = R11 & R14,
L8 = R17 & R20, L9 = R16 & R21, L10 = R19 & R22, L11 = R18 & R23
[0015]
Next, the presence / absence of a surface is obtained (S313). Using the same arrangement information as in the case of the thin plate shown in FIG. 17, it is represented by a 12-bit surface presence flag. Similarly to the thin plate arrangement flag, N0 to N11 are sequentially set from the least significant bit to the most significant bit. If Ni is 1, there is a surface at the i th location, and if Ni is 0, there is no surface at the i th location. Each bit of such a surface presence flag is calculated using the logical sum (|) of the bits of the quadrangular surface arrangement flag as follows. That is, if there is a quadrangular surface on at least one of both sides of the back-to-back, it is 1.
N0 = R0 | R5, N1 = R1 | R4, N2 = R2 | R7, N3 = R3 | R6,
N4 = R8 | R13, N5 = R9 | R12, N6 = R10 | R15, N7 = R11 | R14,
N8 = R17 | R20, N9 = R16 | R21, N10 = R19 | R22, N11 = R18 | R23
Further, a thin plate boundary ridge line is obtained by combining thin plates (S314). The thin plate boundary ridge line is a ridge line forming a thin plate boundary, that is, a ridge line shared only by two quadrangular surfaces forming a thin plate. Since there are a maximum of six ridge lines around the vertex, the arrangement information of the thin plate boundary ridge lines is represented by a 6-bit ridge line arrangement flag as shown in FIG. BE0 to BE5 in order from the least significant bit to the most significant bit of the flag. If BEi is 1, there is a ridgeline at that location, and if BEi is 0, there is no ridgeline at that location. Each bit of the ridge line placement flag of the thin plate boundary ridge line is calculated using the logical product (&), logical sum (|), negation (!) Of the thin plate placement flag and the surface presence flag as follows. If even one thin plate boundary ridge exists around the vertex, the vertex is determined to be a thin plate boundary vertex.
BE0 = (L0 & (! N1 &! N4 &! N6)) | (L1 & (! N0 &! N4 &! N6))
| (L4 & (! N0 &! N1 &! N6)) | (L6 & (! N0 &! N1 &! N4)),
BE1 = (L0 & (! N2 &! N8 &! N10)) | (L2 & (! N0 &! N8 &! N10))
| (L8 & (! N0 &! N2 &! N10)) | (L10 & (! N0 &! N2 &! N8)),
BE2 = (L0 & (! N1 &! N4 &! N6)) | (L1 & (! N0 &! N4 &! N6))
| (L4 & (! N0 &! N1 &! N6)) | (L6 & (! N0 &! N1 &! N4)),
BE3 = (L0 & (! N1 &! N4 &! N6)) | (L1 & (! N0 &! N4 &! N6))
| (L4 & (! N0 &! N1 &! N6)) | (L6 & (! N0 &! N1 &! N4)),
BE4 = (L0 & (! N1 &! N4 &! N6)) | (L1 & (! N0 &! N4 &! N6))
| (L4 & (! N0 &! N1 &! N6)) | (L6 & (! N0 &! N1 &! N4)),
BE5 = (L0 & (! N1 &! N4 &! N6)) | (L1 & (! N0 &! N4 &! N6))
| (L4 & (! N0 &! N1 &! N6)) | (L6 & (! N0 &! N1 &! N4))
[0016]
Next, according to the operation flow shown in FIG. 19, the thin plate boundary vertex moving method shown in step S32 of FIG. 13 will be described.
First, the basic triangular mesh around the thin plate boundary vertex is cut (cut) along the thin plate boundary ridge line (S321). As shown in FIGS. 21 (a) and 21 (b), the thin plate boundary vertex and the thin plate boundary ridge line are duplicated in phase and separated as separate elements.
Subsequently, the plurality of vertices generated by the separation are moved in the direction indicated by the arrow in FIG. 21A (details of this direction will be described later) until they are placed on the distance image mesh (S322). Then, a new triangular surface is generated in the gap of the basic triangular mesh generated by such vertex movement (S323). That is, first, a triangle with four sides of the copied thin plate boundary ridge line (four triangles surrounded by the thick line in FIG. 21 (c)) is generated, and there are three thin plate boundary ridge lines as shown in the figure. In many cases, the gap in the polygonal area still remains, so filling the polygonal area by dividing it into multiple triangles (two triangles surrounded by bold lines in Fig. 21 (d)) is there.
Thus, the surface of the basic triangular mesh is closer to the actual surface. The vertex position before the vertex movement was approximated to the center position of the voxel, but the vertex position after the movement is a point on the distance image mesh where the three vertices are the actual positions, so it is very close to the actual position. . In addition, increasing the number of faces and complementing between the basic triangular meshes also brings the effect of bringing them closer to the actual faces.
Next, according to the operation flow shown in FIG. 20, the non-manifold ridge line connection vertex detection shown in step S33 of FIG. 13 will be described.
First, a quadrangular surface composed of a set of two basic triangular meshes is detected, and a quadrangular surface arrangement flag, which is arrangement information of the quadrangular surface, is acquired (S331). Then, a non-manifold ridge line is detected from the combination of the quadrangular surfaces (S332). Note that the non-manifold ridge line is a ridge line shared by three or more faces, and except for those that become the same by rotation transformation, the combination of quadrangular faces including the non-manifold ridge line is shown in FIG. ) and (b). Prepare a table storing the quadrilateral plane placement flag for each vertex, search for such a table, and include the non-manifold ridgeline as shown in FIGS. 22 (a) and (b) for each vertex. If at least one non-manifold ridge line is detected, the vertex is set as a non-manifold ridge line connection vertex.
[0017]
Next, the non-manifold ridge line connection vertex moving method shown in step S34 of FIG. 13 will be described according to the operation flow shown in FIG.
First, two general ridge lines (thick lines in FIGS. 24A and 24D) orthogonal to each other across the non-manifold ridge line connection vertex are selected (S341). Then, the basic triangular mesh around the vertex is cut (cut) along the two general ridge lines (S342).
Subsequently, the plurality of vertices generated by this separation are moved in the direction of the arrow (details will be described later) until they lie on the distance image mesh (see FIGS. 24 (a), (b), (d), and (e). (S343). Then, a new triangular surface is generated in the gap of the basic triangular mesh generated by the movement of the vertex (a triangle surrounded by a thick line in FIGS. 24C and 24F) (S344).
Thus, the surface of the basic triangular mesh is closer to the actual surface. In addition, increasing the number of faces and complementing between the basic triangular meshes also brings the effect of bringing them closer to the actual faces.
Next, according to the operation flow shown in FIG. 25, the non-manifold vertex detection method shown in step S35 of FIG. 13 will be described. A non-manifold vertex is a vertex when only a vertex is shared by a plurality of faces.
First, a quadrangular surface composed of a set of two basic triangular meshes is detected, and a quadrangular surface arrangement flag is acquired (S351). Then, a non-manifold vertex is detected from the combination of the quadrangular surfaces (S352). Excluding those that become the same due to the rotation transformation, the combination of the quadrangular faces including the non-manifold vertices is one shown in FIG. 22 (c), so a table storing the quadrangular face arrangement flag for each vertex. Is prepared, and such a table is searched, and for each vertex, the presence or absence of a combination of quadrangular surfaces as shown in FIG. If there is such a combination, the vertex is set as a non-manifold vertex.
[0018]
Next, according to the operation flow shown in FIG. 26, the non-manifold vertex moving method shown in step S36 of FIG. 13 will be described.
First, three pairs of ridge lines (thick lines in FIG. 27 (a)) having two ridge lines orthogonal to each other across the non-manifold vertex are selected (two pairs may be used) (S361). Then, a plurality of basic triangular meshes around the non-manifold vertices are cut (cut) along the ridge lines of the three sets of ridge lines (S362).
Subsequently, the plurality of vertices generated by the separation are moved until they fall on the distance image mesh (see FIG. 27B) (S363). Then, a new triangular surface (triangle surrounded by a thick line in FIG. 27C) is generated in the gap of the basic triangular mesh generated by such vertex movement (S364).
Thus, the surface of the basic triangular mesh is closer to the actual surface. In addition, increasing the number of faces and complementing between the basic triangular meshes also brings the effect of bringing them closer to the actual faces.
Next, according to the operation flow shown in FIG. 28, the general vertex moving method shown in step S37 of FIG. 13 will be described.
First, for each vertex, a quadrangular surface composed of a set of two basic triangular meshes is detected, and a quadrangular surface arrangement flag, which is arrangement information of the quadrangular surface, is acquired (S371). Then, general vertices other than the various vertices described so far (such as vertices connecting edge lines shared by two faces) are extracted, and a surface configuration pattern is selected from a combination of quadrangular faces around the general vertices ( S372). Except for the ones that become the same due to the rotation transformation, there are 10 such combinations of quadrangular surfaces as shown in FIG. 12. Therefore, a table storing a quadrangular surface arrangement flag for each vertex is prepared. Such a table is searched to obtain a matching surface composition pattern as shown in FIG. 12 for each vertex.
Subsequently, a plurality of basic triangular meshes around the vertex are separated (cut), and a vertex and a ridge line are newly generated (duplicated) for each surface configuration pattern (S373). Since there may be a plurality of surface configuration patterns extracted in step S372 for one vertex, in that case, the vertex and the ridgeline connected to each other are duplicated in a topological manner.
Further, the original vertex and the newly generated vertex are moved until they fall on the distance image mesh (S374).
Thus, the surface of the basic triangular mesh is closer to the actual surface.
[0019]
Next, according to the operation flow shown in FIG. 29, the moving direction at the time of moving each vertex will be described.
First, the average normal vector of the basic triangular mesh around the vertex is calculated (S41). Then, a diagonal vector whose direction is closest to the opposite direction of the average normal vector is obtained (S42). Note that the diagonal vector is a value obtained by connecting the vertex to the vertex of the voxel at the diagonal position in the adjacent 8 voxels including the vertex (see FIG. 30 (a)), and any ridge line connected to the vertex. A connection between the midpoint and the midpoint of the diagonal ridgeline (see Fig. 30 (b)), and a midpoint of one of the faces including the vertex and the midpoint of the opposite face ( FIG. 30 (c)).
Subsequently, an intersection where the obtained diagonal vector intersects the distance image mesh is obtained, and the various vertices shown in each operation flow are moved to the intersection (S43).
At that time, if the intersection with the distance image mesh cannot be obtained, the diagonal vector whose direction is next to the opposite direction of the average normal vector is selected to obtain the intersection, and none of the diagonal vectors has an intersection. In this case, the vertex movement destination is a point on the distance image mesh that is the closest to the starting point of the diagonal vector. In the above, the original vertex is simply moved in the opposite direction of the average normal vector and the point on the distance image mesh is not the movement destination. This is because there is a high possibility that the vertex is shifted from the surface of the actual thin plate and not on the distance image mesh.
The three-dimensional shape generation method of the present invention has been described above. However, a program for executing the three-dimensional shape generation method as described above is stored in, for example, a removable storage medium, and the storage medium has been described so far. By attaching to an information processing apparatus such as a personal computer that could not generate the three-dimensional shape according to the information processing apparatus, the information processing apparatus can also generate the three-dimensional shape according to the present invention.
References
[1] William E. Lorensen and Harvey E. Cline: "Marching Cubes: A High Resolution 3D Surface Construction Algorithm", SIGGRAPH'87 Proceedings, pp.163-169, Jul 1987.
[2] Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald and Werner Stuetzle: "Surface reconstruction from unorganized points", SIGGRAPH '92 Proceedings, pp.71-78, Jul 1992.
[3] Brian Curless and Marc Levoy: "A Volumetric Method for Building Complex Models from Range Images", SIGGRAPH '96 Proceedings, pp.303-312, Aug 1996.
[4] Matsuoka, Ueda, Hayano: “Automatic reconstruction of solid model from point cloud data using grid connection method and local operation”, IPSJ Journal, vol.40, No.5, 1999.
[5] Jean-Daniel Boissonnat: "Geometric structures for three-dimentional shape representation", ACM Transactions on Graphics, Vol.3, No.4, Oct 1984, pp.266-286.
[0020]
【The invention's effect】
  As explained above,According to the present invention described in claims 1 and 10,When generating a triangular mesh from a distance image obtained by measuring with a three-dimensional measuring instrument or the like, there is a problem that the sharp ridgeline of the angular shape, particularly the acute ridgeline of the concave portion is lost, and a thin shape less than the lattice spacing The problem that the thin shape is lost, the problem that the shape changes depending on the lattice position, and the like can be solved.In addition, the basic triangular mesh can be brought closer to the actual contour surface more appropriately.
  Moreover, according to invention of Claim 2, 11,The detection of the thin plate boundary vertex can be easily realized.
[0021]
  According to the inventions of claims 3 and 12,Non-manifold ridge line connection vertices can be easily detected.
  According to the inventions of claims 4 and 13,Even if it is a three-dimensional shape with non-manifold ridge line connection vertices, the basic triangular mesh can be appropriately brought close to the actual contour surface. The problem that the shape is lost, the problem that the thin and narrow shapes less than the lattice interval are lost, the problem that the shape changes depending on the position of the lattice, and the like can be solved.
  According to the inventions of claims 5 and 14,Non-manifold vertices can be easily detected.
  According to the inventions of claims 6 and 15,Even in a three-dimensional shape having non-manifold vertices, the basic triangular mesh can be appropriately brought close to the actual contour surface, and therefore the sharp ridgeline of the angular shape, particularly the sharp ridgeline of the concave portion is lost. Problems such as loss of thin and thin shapes that are less than or equal to the lattice spacing, and changes in shape depending on the lattice position can be solved.
[0022]
  Moreover, according to the invention of Claims 7 and 16,Even if it is a three-dimensional shape in which general vertices are mixed among various vertices, the basic triangular mesh can be appropriately brought close to the actual contour surface. Therefore, the sharp edge of the angular shape, particularly the acute angle of the concave portion The problem that the ridgeline is lost, the problem that the thin and narrow shapes less than the grid interval are lost, the problem that the shape changes depending on the grid position, and the like can be solved.
  Moreover, according to the invention of Claims 8 and 17,For example, in the case of a thin plate or the like, it is possible to avoid a situation in which the vertex as the center of the voxel is shifted from the surface of the actual thin plate and does not fall on the distance image mesh when moving the vertex.
  Also,According to the invention described in claim 9, the present inventionBy attaching a storage medium to an information processing apparatus such as a personal computer, the information processing apparatusAny one of claims 1 to 8The effects of the described invention can be realized.
[Brief description of the drawings]
FIG. 1 is an operation flow diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 2 is an explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 3 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 4 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 5 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 6 is another operation flow diagram of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 7 is another operation flow diagram of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 8 is another operation flow diagram of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 9 is another operation flow diagram of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 10 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 11 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 12 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 13 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 14 is another operation flow diagram of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 15 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 16 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 17 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 18 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 19 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 20 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 21 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 22 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 23 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 24 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 25 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 26 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 27 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 28 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 29 is another operation flowchart of the three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 30 is another explanatory diagram of a three-dimensional shape generation method showing an embodiment of the present invention.
FIG. 31 is a block diagram showing the hardware configuration of a three-dimensional shape processing apparatus according to an embodiment of the present invention.
FIG. 32 is an explanatory diagram of a three-dimensional shape generation method showing an example of a conventional technique.
[Explanation of symbols]
1 CPU
2 memory
3 External storage device
4 input devices
5 display devices

Claims (17)

In a 3D shape generation method of a 3D shape generation apparatus that generates a 3D shape by generating a triangular mesh from a distance image,
Distance image volume generation means, and generating a volume model of individual voxels with either of the three attribute values of the contour, internal and external from the distance image,
The basic mesh generation means acquires triangle generation information and rotation information from adjacent 8 voxel attribute values, rotates and converts 8 voxels based on the acquired rotation information, and uses the 8 voxels and triangle generation information that have been converted to rotation. Generating a triangular mesh;
Vertex fitting means detects at least two types of vertices among thin plate boundary vertices, non-manifold ridge line connection vertices, non-manifold vertices, and general vertices as vertices of the basic triangular mesh, and the types of detected vertices A different vertex moving method is selected according to the step, the vertex of the basic triangular mesh is moved to generate a triangular mesh, and a plurality of basic triangular meshes around the thin plate boundary vertex are moved along the thin plate boundary ridge line. The thin plate boundary vertices are moved by separating and moving the resulting plurality of vertices until they lie on the distance image mesh, and a new triangular surface is added to the gap of the basic triangular mesh generated by this movement. Generating
The three-dimensional shape generation method characterized by performing . The three-dimensional shape generation method according to claim 1 , wherein the vertex fitting means detects a quadrangular surface composed of a set of two basic triangular meshes, and a thin plate boundary ridge line from a combination of the detected quadrangular surfaces. step and three-dimensional shape generation method characterized by performing the step of detecting the thin boundary vertices from the detected sheet boundary edge, a detected. 2. The method of generating a three-dimensional shape according to claim 1 , wherein the vertex fitting means detects a quadrangular surface comprising a set of two basic triangular meshes, and a non-manifold from a combination of the detected quadrangular surfaces. 3-dimensional shape generation method, characterized by performing the steps of detecting a ridge, and detecting the non-manifold edge line connecting the vertices, the. 2. The three-dimensional shape generation method according to claim 1 , wherein the vertex fitting means selects two general ridge lines orthogonal to each other across the non-manifold ridge line connection vertices, along the two selected general ridge lines. The non-manifold ridge line connection vertex is moved by cutting a plurality of basic triangular meshes around the non-manifold ridge line connection vertex and moving the resulting plurality of vertices until they are on the distance image mesh. A method for generating a three-dimensional shape characterized by executing a step of newly generating a triangular surface in a gap of the basic triangular mesh generated by this movement. 2. The method of generating a three-dimensional shape according to claim 1 , wherein the vertex fitting means detects a quadrangular surface comprising a set of two basic triangular meshes, and a non-manifold from a combination of the detected quadrangular surfaces. A method for generating a three-dimensional shape, comprising performing a step of detecting a vertex. 2. The three-dimensional shape generation method according to claim 1 , wherein the vertex fitting means selects a plurality of pairs of ridge lines including one pair of two ridge lines orthogonal to each other across the non-manifold vertices. By cutting a plurality of basic triangular meshes around the non-manifold vertices along each set of ridge lines, and moving the resulting plurality of vertices until they lie on the distance image mesh move the manifold vertices, three-dimensional shape generation method characterized by performing the step of generating a new triangle surface in the gap of the base triangle mesh generated by the movement. 2. The method of generating a three-dimensional shape according to claim 1 , wherein the vertex fitting means detects a quadrangular surface composed of a set of two basic triangular meshes, and a surface configuration pattern from a combination of the detected quadrangular surfaces. And a step of newly generating vertices and edge lines for each selected surface configuration pattern, and moving the newly generated vertices until they fall on the distance image mesh, A method for generating a three-dimensional shape, characterized by moving a vertex. In 3-D shape generation method according to any one of claims 1 to 7, the average normals the apex fitting means calculates the average normal vectors of the basic triangular meshes adjacent to the vertex, Motoma' was A three-dimensional process comprising: obtaining a diagonal vector from the vector, and moving the vertex along the diagonal vector until the vertex crosses the distance image mesh by crossing the distance image mesh. Shape generation method.   A computer-readable storage medium storing a program for causing a computer to execute the process according to any one of claims 1 to 8. In a three-dimensional shape generation apparatus that generates a three-dimensional shape by generating a triangular mesh from a distance image,
A distance image volume generation means for generating a volume model composed of individual voxels having any one of three attribute values of contour, inside, and outside from a distance image ;
Triangle generation information and rotation information are acquired from adjacent 8 voxel attribute values, 8 voxels are rotationally converted by the acquired rotation information, and a basic triangular mesh is generated using the 8 voxels and triangle generation information that have been rotationally converted. Basic mesh generation means ;
As the vertices of the basic triangular mesh, at least two types of vertices are detected among thin plate boundary vertices, non-manifold ridge line connection vertices, non-manifold vertices, and general vertices, and differ according to the detected vertex type. A method of moving the vertices of the basic triangular mesh to generate a triangular mesh, and separating a plurality of basic triangular meshes around the thin plate boundary vertex along the thin plate boundary ridge line, Means for moving the thin plate boundary vertices by moving a plurality of vertices generated on the distance image mesh and generating a new triangular surface in the gap of the basic triangular mesh generated by the movement And vertex fitting means comprising:
A three-dimensional shape generation apparatus comprising: The three-dimensional shape generation apparatus according to claim 10 ,
The vertex fitting means includes means for detecting a quadrangular surface comprising a set of two basic triangular meshes, means for detecting a thin plate boundary ridge line from a combination of detected quadrangular surfaces, and a detected thin plate boundary ridge line. Means for detecting the thin plate boundary vertices. The three-dimensional shape generation apparatus according to claim 10 ,
The vertex fitting means includes means for detecting a quadrangular surface comprising a set of the two basic triangular meshes, means for detecting a non-manifold ridge line from the combination of detected quadrilateral surfaces, and the non-manifold ridge line. And a means for detecting a connection vertex. The three-dimensional shape generation apparatus according to claim 10 ,
The vertex fitting means selects two general ridge lines orthogonal to each other across the non-manifold ridge line connection vertex, and a plurality of basic 3 around the non-manifold ridge line connection vertex along the selected two general ridge lines. The non-manifold ridge line connection vertex is moved by cutting the polygonal mesh and moving the resulting plurality of vertices until they lie on the distance image mesh, and the basic triangular mesh generated by this movement is moved. A three-dimensional shape generating apparatus comprising means for newly generating a triangular surface in the clearance. The three-dimensional shape generation apparatus according to claim 10 ,
The vertex fitting means includes means for detecting a quadrangular surface composed of a set of two basic triangular meshes, and means for detecting a non-manifold vertex from a combination of the detected quadrangular surfaces. 3D shape generator. The three-dimensional shape generation apparatus according to claim 10 ,
The vertex fitting means selects a plurality of pairs of ridge lines including two ridge lines orthogonal to each other across the non-manifold vertices, and the non-various along the ridge lines of each set of the selected plurality of ridge lines. The non-manifold vertices are moved by separating the plurality of basic triangular meshes around the body vertices and moving the resulting plurality of vertices until they are on the distance image mesh. A three-dimensional shape generating apparatus comprising means for newly generating a triangular surface in the gap of the basic triangular mesh. The three-dimensional shape generation apparatus according to claim 10 ,
The vertex fitting means includes
Means for detecting a quadrangular surface consisting of a set of two basic triangular meshes, means for selecting a surface configuration pattern from the combination of detected quadrangular surfaces, and new vertices and ridge lines for each selected surface configuration pattern A three-dimensional shape generating apparatus, wherein the general vertex is moved by moving the newly generated vertex on the distance image mesh. In the three-dimensional shape generation apparatus according to any one of claims 10 to 16, wherein the apex fitting means calculates the average normal vectors of the basic triangular meshes adjacent to the vertex, Motoma' average normal A three-dimensional shape generation apparatus, wherein a diagonal vector is obtained from a vector, and the vertex is moved along the diagonal vector until the vertex crosses the distance image mesh by crossing the distance image mesh.

Images