JP3340198B2 - Shape restoration device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a shape restoring apparatus for obtaining shape data for restoring a surface shape from three-dimensional surface coordinate values obtained by observing an object to be measured.

[0002]

2. Description of the Related Art In recent years, the need for three-dimensional CAD for supporting the design of industrial parts and the like, and the need for creating images using computer graphics have been rapidly increasing. In these techniques, it is necessary to input a geometrical shape, a surface attribute, and motion data of an object to be designed or displayed in computer graphics to a computer. (This process is called modeling, and the numerical data expressed inside the computer is called a model.) This part is currently performed by humans with much effort, and automation is strongly desired.

Recently, a system for automatically inputting a presented object shape using a range image device called a range finder has been proposed for application to three-dimensional CAD. Since the range finder can measure only the discrete surface three-dimensional coordinate values of the target object, to restore the shape, a surface must be generated by adding geometric phase information between the surface three-dimensional coordinate values. Must. The numerical data created in this way is called a shape model. Currently proposed methods perform geometrical ordering between surface three-dimensional coordinate values based on a measurement order to obtain a geometrical topological relationship. FIG. 22 schematically shows a conventional method using a range finder. The object to be measured 50 is placed on a turntable 52, and the orientation of the object 50 with respect to the range finder 49 can be arbitrarily changed by rotating the turntable 52. The range finder 49 is oriented in the direction of the rotation axis of the turntable 52, and has a fixed position. The measurement by the range finder 49 is performed only one scan in the vertical direction like the projected image 51 in a certain direction of the measured object 50. This measurement is performed 360 ° / Δθ times by rotating the turntable 52 by Δθ. The geometric phase information is added between the three-dimensional coordinate values of the surface measured in this way in the two-dimensional space in the vertical direction and the θ direction. Based on this information, the shape of the measured object 50 is determined. Restoration is easy. However, the range finder 49 is always oriented in the direction of the rotation axis of the turntable 52, and an object to be measured 50 itself becomes a shadow, and an occlusion region that cannot be measured from the range finder 49 occurs. For example, when the object to be measured is a doll, an area hidden by the arm is an occlusion area. At this time, it is possible to measure the three-dimensional coordinate value (non-occlusion area) of the surface of the arm and the occlusion area under the arm by rotating the doll on the turntable. However, there is a drawback that it is very difficult to use the data as shape restoration data. Therefore, the object that can be measured by this method is limited to a simple shape such that no occlusion region is generated by the measured object 50 itself. In addition, when the measurement in the upward and downward directions of the measured object 50 for which sufficient data cannot be obtained only by measuring from the lateral direction is performed by replacing the measured object 50,
It is a very difficult problem to determine the geometrical topological relationship between data in the horizontal, upward, and downward directions.

Further, in the field of scientific visualization, a marching cube method (hereinafter, referred to as an MC method) for visualizing volume data such as measurement data and calculation result data is known. M
The C method is a method of extracting an isosurface from volume data and approximating the isosurface with a group of triangular patches. For example, when a plurality of tomographic images of a human body are captured at predetermined intervals in the medical image field, isosurfaces are extracted according to pixel values between adjacent images. Here, if this method is used for the surface three-dimensional coordinate values on the target object obtained by the range finder, it is possible to obtain shape data that can be displayed even if the geometric phase relationship between the data is unknown. . But,
Since the positions of the vertices of the triangular patch are determined by interpolation when the isosurface is approximated by the triangular patch group, a triangular patch passing through the measured surface three-dimensional coordinate values is not always generated. . Therefore, the highly accurate surface three-dimensional coordinate values obtained from the range finder are not faithfully reflected in the restored shape data. This is because C is important for accuracy.
This is a serious problem for the AD field. Also in the computer graphics field, it is desirable that the shape of the target object be restored as faithfully as possible.

For the above reasons, it is considered that the conventionally proposed method is still insufficient for the purpose of automatically creating a shape model for three-dimensional CAD and computer graphics.

[0006]

As described above, when a range finder is used in a conventional shape restoration device, the object to be measured is limited to a simple shape.
When the MC method is used, high-precision surface shape data cannot be obtained, so that it is not enough to automatically create a shape model for a three-dimensional CAD or the like even if each method is used.

An object of the present invention is to limit the method of measuring surface three-dimensional coordinate values in a three-dimensional CAD or computer graphics, in which surface shape data can be restored with high accuracy even for a measured object having a complicated shape. It is possible to provide a shape recovery device without any.

[0008]

According to the present invention, a data input section for inputting three-dimensional coordinate values of the surface shape of an object to be measured, and all three-dimensional coordinate values input from the data input section are completely converted. Cell generation unit for generating voxel data obtained by dividing the space covered by the cell into a grid, and one range data for each voxel data generated by the cell generation unit using the corresponding three-dimensional coordinate value. A data storage unit, a cell pattern recognition unit for obtaining a topological relationship in accordance with each range data for a predetermined number of three-dimensionally adjacent voxel data, and a topological relationship obtained by the cell pattern recognition unit A triangular patch is created for each of the predetermined number of voxel data according to It is characterized in that it has and a patch generator for the switch was removed shape data.

[0009]

In the present invention, the surface shape is reconstructed from the surface three-dimensional coordinate values obtained by observing the object to be measured, and the surface shape is obtained by dividing the surface three-dimensional coordinate values into a grid-like space. The respective voxel data are associated with each other. The surface three-dimensional coordinate value associated with each voxel data obtains one range data, and the topological relationship between a predetermined number of spatially adjacent voxel data is obtained from each range data, thereby forming a triangular patch. Determine the shape data. That is, in the present invention, the order of the measurement method when inputting the surface three-dimensional coordinate values is not necessary, and the geometric phase relationship is known even if the geometric phase relationship between the surface three-dimensional coordinate values is unknown. The shape can be easily restored by associating the surface three-dimensional coordinate values with the voxel data. Furthermore, by changing the size of the voxel data, desired shape data can be created from high-resolution shape data that faithfully reflects the surface three-dimensional coordinate values of the measurement result to low-resolution shape data with a small amount of data.

[0010]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a diagram showing a schematic configuration of an apparatus according to an embodiment of the present invention, FIG. 2 is a diagram for explaining processing contents of an embodiment of the present invention, and FIG. 3 is a processing flowchart of the embodiment of the present invention.

In FIG. 1 and FIG. 3, a data input section 1 inputs range data obtained by observing an object to be measured (step 101). The cell generation unit 2 creates voxel data obtained by equally dividing a space that completely covers the range data input by the data input unit 1 by the voxel division method (step 102). The data storage unit 3 associates the range data input by the data input unit 1 with the voxel data generated by the cell generation unit 2,
The average of the coordinate values of a plurality of range data associated with the voxel data is obtained, and the range data having that value is newly set as one range data corresponding to the voxel data (steps 103 and 104). Cell pattern recognition unit 4
Finds a relationship determined by whether or not each voxel data is associated with range data for eight adjacent voxel data (step 105). The patch generator 5 generates a triangular patch based on the topological relationship between the eight adjacent voxel data obtained by the cell pattern recognizer 4 (step 106). The shape data 6 is a triangular patch group as a result of performing the processing of the patch generation unit 5 on all voxel data (step 1).
07).

In FIG. 2, reference numeral 7 denotes observation range data obtained by observing a measurement object, and 8 denotes voxel data obtained by equally dividing a space which completely covers the observation range data 7 by a voxel division method. , 9 are triangular patch data obtained as a processing result. By creating the voxel data 8 from the observation range data 7, the observation range data 7 can have a geometric phase relationship, and the triangular patch data 9 that can be displayed by CG can be created by simple processing. .

Hereinafter, each component of FIG. 19 will be described in detail. The data input unit 1 converts observation range data 14 obtained by observing from a plurality of directions with the range finder 10, 11, 12 so that there is no unobserved part on the surface of the measured object 13 as shown in FIG. Is entered.

FIG. 5 schematically shows the processing performed in the cell generator 2. The cell generation unit 2 refers to all the coordinate values of the observation range data 15 input by the data input unit 1, and determines the minimum value (x min, y min, z) in each of the x-axis direction, the y-axis direction, and the z-axis direction. min), maximum value (x max,
y max, z max). Then, P0 (x min, y min, z min), P1 (x min, y min, z ma
x) P2 (x min, y max, z min), P3 (x min, y max, z ma
x) P4 (x max, y min, z min), P5 (x max, y min, z ma
x) P6 (x max, y max, z min), P7 (x max, y max, z ma
The voxel division method is applied to the space with the eight points of x) as vertices. When the user designates the number of divisions as l, m, and n in the x-axis direction, the y-axis direction, and the z-axis direction, V
(0,0,0), v (0,0,1),. . . , V (l−
1, m−1, n−1) of 1 × m × n voxel data are generated.

FIG. 6 schematically shows the processing performed in the data storage unit 3. The processing performed on the i-th, j-th, and k-th voxel data V (i, j, k) in the x-axis direction, the y-axis direction, and the z-axis direction of the voxel data generated by the cell generator 2 will be described below. (Where 0 ≦ i ≦ l−1, 0 ≦ j ≦ m−1,
0 ≦ k ≦ n−1). FIG. 6A shows the voxel data V
(I, j, k) and the observation range data 20 input at the data input unit 1 existing inside and around the voxel data V (i, j, k). Data storage unit 3
Is the voxel data V (i, j,
When the observation range data 20 exists inside k), the internal range data 21 is associated with the voxel data V (i, j, k) as shown in FIG. 6B. If no internal range data 21 exists inside the voxel data V (i, j, k), the correspondence of the internal range data 21 to the voxel data V (i, j, k) is as follows. Not done. As shown in FIG. 6B, a plurality of internal range data 21 is added to the voxel data V (i, j, k).
Are associated with each other, an average of coordinate values is obtained between the plurality of internal range data 21, and one average range data 22 having the obtained average coordinate values is converted into a voxel as shown in FIG. It is associated with the data V (i, j, k). The processing shown in FIG. 6 is performed by the voxel data V (0, 0,
0), V (0, 0, 1),. . . , V (l-1, m-
1, n-1). Here, if the average range data 22 is associated with the voxel data, the attribute value of the voxel data is set to 1, and if not, the attribute value of the voxel data is set to 0.

Next, the processing performed by the cell pattern recognition section 4 will be described. FIG. 7 logically shows eight adjacent voxel data for which a relationship between voxel data is determined. Voxel data V shown in FIG.
0,. . . , V7, V0 (p, q, r) = V (p, q, r) V1 (p, q, r) = V (p, q, r + 1) V2 (p, q, r) = V (p , Q + 1, r) V3 (p, q, r) = V (p, q + 1, r + 1) V4 (p, q, r) = V (p + 1, q, r) V5 (p, q, r) = V ( p + 1, q, r + 1) V6 (p, q, r) = V (p + 1, q + 1, r) V7 (p, q, r) = V (p + 1, q + 1, r + 1) (where 0 ≦ p ≦ l) -2, 0 ≦ q ≦ m−2, 0
≤r≤n-2). The voxel data V0,. . . ,
V7 is represented by a voxel data group VG (p, q, r). Each voxel data in the voxel data group VG (p, q, r) has already been processed in the data storage unit 3. Voxel data group VG (p, q, r)
In FIG. 9, there are 23 patterns (a) to (w) that can be generated depending on the attribute value of each voxel data. However, patterns that match when the attribute values of eight adjacent voxel data are rotated around the x, y, and z axes by an integral multiple of 90 degrees are grouped into one pattern as being treated as the same. Voxel data group VG
In order to obtain the (p, q, r) pattern, the pattern is collated with the 23 patterns shown in FIG. When performing the collation, the rotation processing is performed on the attribute value of each voxel data of the voxel data group VG (p, q, r), and then the processing is performed later.
The collated pattern in FIG. 9 is converted to a voxel data group VG.
The matching pattern is (p, q, r). Such processing is performed for each of p, q, and r. . . 1-2,
0. . . m-2, 0. . . This is performed for the voxel data group VG (p, q, r) with n-2. Thereafter, the following processing is performed between the voxel data groups VG. Here, the following data is defined for the voxel data group VG (p, q, r).

VSa = (V0, V1, V2, V3) VSb = (V4, V5, V6, V7) VSc = (V0, V1, V4, V5) VSd = (V2, V3, V6, V7) VSe = ( V0, V2, V4, V6) VSf = (V1, V3, V5, V7) This means that each face of the logical hexahedron 26 shown in FIG. . . , VSf. As shown in FIG. 8, there are six patterns (a) to (f) that can be generated by the attribute value of each voxel data in the voxel data group VS. The voxel data group VSa,. . . , VSf are compared with the six patterns in FIG. 8, and the matched patterns are extracted as voxel data groups VSa,. . . , VSf. Such processing is performed for all voxel data groups VG (p, q,
r). Therefore, the voxel data group VG and the associated voxel data group VS are generated by the processing of the cell pattern recognizing unit 4, and each holds the collation pattern data.

Next, the processing performed by the patch generator 5 will be described. FIG. 10 schematically shows a triangular patch 37 generated corresponding to each pattern shown in FIG. As shown in FIG. 10A, the vertices of the logical hexahedron 36 in FIGS. . . , VP7. Below, the generated triangular patches T are shown for each pattern.

(A)... Not generated. (B) ... not generated. (C) ... not generated.

(D) No generation. (E) ... not generated. (F)... T (VP1, VP4, VP5), T (VP1,
VP5, VP4) (g)... T (VP0, VP4, VP7), T (VP0,
VP7, VP4) (h)... T (VP2, VP4, VP7), T (VP2,
(VP7, VP4) (i)... T (VP0, VP1, VP5), T (VP0,
VP5, VP1), T (VP0, VP4, VP5), T
(VP0, VP5, VP4) (j)... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP5, VP3), T
(VP1, VP3, VP5) (k)... T (VP0, VP2, VP5), T (VP0,
VP5, VP2), T (VP2, VP5, VP7), T
(VP2, VP7, VP5) (1)... T (VP0, VP7, VP1), T (VP0,
VP1, VP5), T (VP0, VP5, VP7), T
(VP1, VP7, VP5) (m)... T (VP1, VP5, VP4), T (VP1,
VP2, VP5), T (VP1, VP4, VP2), T
(VP2, VP4, VP5) (n)... T (VP0, VP3, VP5), T (VP0,
VP6, VP3), T (VP0, VP5, VP6), T
(VP3, VP6, VP5) (o) ... T (VP1, VP4, VP3), T (VP1,
VP3, VP5), T (VP1, VP5, VP4), T
(VP3, VP4, VP5) (p) ... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP5, VP4), T
(VP0, VP4, VP3), T (VP1, VP3, V
P (5), T (VP3, VP4, VP5) (q)... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP6, VP3), T
(VP0, VP5, VP6), T (VP1, VP3, V
P5), T (VP3, VP6, VP5) (r)... T (VP1, VP2, VP3), T (VP1,
VP5, VP2), T (VP1, VP3, VP5), T
(VP2, VP5, VP6), T (VP2, VP6, V
P (3), T (VP3, VP6, VP5) (s) ... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP7, VP3), T
(VP0, VP5, VP4), T (VP0, VP4, V
P7), T (VP1, VP3, VP5), T (VP3,
VP7, VP5), T (VP4, VP5, VP7) (t)... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP6, VP3), T
(VP0, VP5, VP6), T (VP1, VP3, V
P5), T (VP3, VP7, VP5), T (VP3,
VP6, VP7), T (VP5, VP7, VP6) (u)... T (VP0, VP3, VP1), T (VP0,
VP1, VP4), T (VP0, VP6, VP3), T
(VP0, VP4, VP6), T (VP1, VP3, V
P7), T (VP1, VP7, VP4), T (VP3,
VP6, VP7), T (VP4, VP7, VP6) (v) ... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP2, VP3), T
(VP0, VP4, VP2), T (VP0, VP5, V
P4), T (VP1, VP3, VP5), T (VP2,
VP7, VP3), T (VP2, VP4, VP7), T
(VP3, VP7, VP5), T (VP4, VP5, V
P7) (w)... T (VP0, VP3, VP1), T (VP0,
VP1, VP5), T (VP0, VP2, VP3), T
(VP0, VP4, VP2), T (VP0, VP5, V
P4), T (VP1, VP3, VP5), T (VP2,
VP7, VP3), T (VP2, VP6, VP7), T
(VP2, VP4, VP6), T (VP3, VP7, V
P5), T (VP4, VP5, VP7), T (VP4,
VP7, VP6) For example, the triangular patches (VP0, VP1, VP2)
This represents a triangular patch having vertices P0, VP1, and VP2. The order of VP0, VP1, and VP2 indicates the direction of the triangular patch.

As described above, the triangular patch 37 is generated only when the number of the voxel data 35 having the attribute value 1 in the logical hexahedron 36 is three or more. The triangular patch 37 is generated such that a triangular patch 37 is formed in the logical hexahedron 36 so as to form a closed polyhedron between voxel data 35 having attribute values of 1 as much as possible. Each vertex of the generated triangular patch 37 is stored in the cell pattern recognition unit 4.
Is used, the average range data of each voxel data of the voxel data group VG associated with. Thus, the triangular patch 37 is generated according to the collation pattern of the voxel data group VG generated by the cell pattern recognition unit 4. However, the generated closed polyhedra are oxidized k
When the patches are adjacent with the boundary as a boundary, the triangular patch at the boundary is hidden by other triangular patches. FIG. 11 shows an example of such a state. FIG. 11 shows a case where the patterns of two adjacent voxel data groups VG are (j) and (l), which are bordered by the concealed triangular patch 43. Hereinafter, a process of deleting such a triangular patch will be described. The hidden triangular patches described above occur because of the voxel data group V adjacent to each other.
G patterns are (j), (l), (m), (o), (p), (q), (r), (s), (t), (u),
Only in any of (v) and (w). Each of the patterns of the voxel data group VG adjacent to each other is within the above 12 patterns, and the pattern of the voxel data group VS existing on the adjacent surface of the voxel data group VG adjacent to each other is shown in FIG. In the case of (e) or (f) of FIG. 8, the triangular patch generated only in the voxel data group VS is deleted. Voxel data group VG
The pattern of the voxel data group VS attached to is already recognized by the cell pattern recognizing unit 4 and it is easy to determine whether the collation pattern data is the pattern (e) or (f) in FIG. By performing the processing as described above, the triangular patches completely hidden by the other triangular patches are removed from the triangular patches generated from all the voxel data groups VG. Further, as shown in FIG. 12, when the respective patterns of the voxel data groups VG adjacent to each other are as shown in (f) and (f), two overlapping triangular patches 48 are generated by each voxel data group VG. Therefore, extra data increases. Such a situation occurs when the adjacent voxel data group VG
Also occurs when the respective patterns are (i) and (i). To generate extra triangular patches like this,
A process is performed to delete a triangular patch generated by one voxel data group. As described above, the patch generation unit 5 generates a triangular patch for restoring the surface shape of the measured object based on the patterns of the voxel data groups VG and VS recognized by the cell pattern recognition unit 4.

The shape data 6 is triangular patch data for restoring the surface shape of the measured object generated by the processing of the patch generator 5. Here, another example of the unnecessary triangular patch deletion processing of the triangular patch generation unit 5 will be described.

Due to the nature of the present invention for generating a closed polyhedron in a logical hexahedron, the patch generator 5 generates a plurality of triangular patches 71 to 74 adjacent to a side 70 of a triangular patch as shown in FIG. For example, a thick surface (a surface 54 that reflects the surface on the measured object 53 and a non-surface 55 that is a redundant inner surface) is generated on the surface of the measured object. Therefore, a process of deleting a redundant triangular patch is added to the patch generator 5. Patches are connected so that the directions between adjacent patches are synchronized, and inappropriate patches are deleted. Here, the meaning of the synchronization between the directions will be described with reference to FIG. Triangular patch tr [p], tr
[q] shares a line [s] consisting of vrtx [a] and vrtx [c]. At this time, tr [p] and tr [q] are said to be adjacent. Also,
tr [[p] and ts [q] are oriented (vrtx [a] → vrtx [b] →
vrtx [c]) and (vrtx [a] → vrtx [c] → vrtx [d]). The fact that the directions between the patches are synchronized means that the directions of the adjacent patches are opposite to each other on the shared side. In the case of FIG. 15, the side to be shared
In line [s], the directions of tr [p] and ts [q] are (vrtx
[c] → vrtx [a]) and (vrtx [a] → vrtx [c]), which are opposite to each other, so that the directions of tr [p] and tr [q] are synchronized. The direction of the patch is represented by the order of the vertices constituting the patch, that is, since it determines the direction of the normal vector of the patch, the direction of the normal vector between the patches is aligned. Further, a plurality of patches may be adjacent to one patch. In the reconstructed shape, at most one triangular patch should be connected to each side of each triangular patch, so if two or more are adjacent, one appropriate patch is connected,
Or, if there is no appropriate patch, do not connect. FIG. 16A shows a case where two patches tr [q] and tr [r] are adjacent to tr [p], and tr [q] and tr [r].
Is aligned with tr [p]. So, tr
One of the patches [q] and tr [r] is connected to tr [p]. FIG. 16B is a one-dimensional view of FIG. 16A. If the angles formed by tr [p] and tr [q], tr [r] are θq and θr, respectively, then tr [r] when θq> θr
Is concatenated with tr [p].

FIG. 17 shows a flowchart of a process for generating the final data. In the processing procedure, first, one initial patch that is considered to be correct is determined as a connection source patch (step 201). The initial patch is a triangular patch tr [p] that maximizes the following function f. Where tr [p]
Are defined as v ₀ , v ₁ , and v ₂ .

[0025]

(Equation 1) The function f takes a large value for a triangular patch in which the coordinate values of the three vertices are as close to 0 as possible in the x and y axis directions and as large as possible in the z axis direction. This is because patches located as close as possible to the rangefinder and at the origin on the xy plane, that is, in the area near the center of gravity of the measured object are less likely to be affected by occlusion during observation, and are reliable patches in reconstructing the shape. (However, the integrated coordinate system is set so as to apply to the above idea). When there is a patch adjacent to the source patch obtained by using the function f and having the same direction as the source patch, an appropriate patch is connected to the source patch as described above (step 2).
02-205). If there is no synchronizing patch,
Patches are not linked. This connection process is performed on all three sides of the connection source patch (step 206). When the above processing is completed for the three sides of the connection source patch, a patch that is connected and has a side that has not been subjected to the connection processing is set as a connection source patch (step 207). Then, a connection process is performed on the unconnected side of the connection source patch. Such processing is recursively repeated until there is no patch having a side that is connected and has not been connected. Therefore, a patch that is not finally linked to any patch is deleted as inappropriate.

If the obtained range data covers the entire surface of the object to be measured, a closed triangular patch group for reconstructing the surface shape can be generated by performing the above processing. However, if the range data obtained does not cover the entire surface due to insufficient observation, a correct group of triangular patches cannot be obtained. FIG. 18 shows a state of a series of processing in two dimensions. FIG. 18 (a)
Shows the surface 56 of the measured object by a line segment.
FIGS. 18 (b) and 18 (c) show the measured object shown in FIG. 18 (a) from a plurality of directions and generate patches. The solid line indicates the surface patch 57, and the dashed line indicates the non-surface patch 58. When observation is performed so that an unobserved area does not occur, a triangular patch group generated by the matching pattern of the voxel data VG is as shown in FIG. Since the surface patch 57 and the non-surface patch 58 are separated, the shape of the object can be reconstructed as shown in FIG. FIG. 18C shows a group of triangular patches generated based on the collation pattern of the voxel data VG when an unobserved region occurs above the measured object. At this time, the surface patch 57 and the non-surface patch 58
Are adjacent to each other, the non-surface patch cannot be deleted even if the patch connection processing is performed, and the finally generated final triangular patch 59 includes a patch group other than the object surface as shown in FIG. It will be.

Therefore, in order to avoid the connection of a group of patches other than the object surface, the ridgeline between the adjacent surface patch and the non-surface patch is set as the surface patch boundary line, so that the connection does not extend to the non-surface patch. The designation of the surface patch boundary is achieved by displaying a group of triangular patches generated by the collation pattern of the voxel data VG, and specifying the sides of the triangle patch considered to be the surface patch boundary on the display screen. Since the surface patch boundary indicates the boundary between the unobserved area and the observed area, it must be a closed line segment. If an open segment is insufficiently specified, an adjacent surface patch and a non-surface patch for which a surface patch boundary is not specified are generated, and the surface patch and the non-surface patch are connected. Therefore, it is determined whether the surface patch boundary line is a closed figure by tracing the specified boundary line, and displaying to the operator whether the work is completed,
Or notify by voice. The surface patch boundary line specified in this way is tuned to the side where the connected source patch is located at the surface patch boundary line during the synchronism check with the adjacent patch in the final data generation process. No patch connection is performed assuming that there is no patch to be performed.
FIG. 19 shows a case where an unobserved region 60 occurs when a cube is observed. When an unobserved area 60 is formed on the upper surface as shown in FIG. 19A when the cube is observed,
A surface patch boundary 61 indicated by a bold line in FIG. 19B is designated as a boundary between the surface patch 62 and the non-surface patch group 63. When the above-described connection processing is performed on the triangular patch group specified in this way, a triangular patch group consisting only of surface patches is generated as shown in FIG.
As described above, even when an unobserved region occurs, the shape of the measured object can be restored.

The present invention is not limited to the embodiment described above. For example, regarding the processing of the data storage unit 3, in the above description, the voxel data V (i, j,
The coordinate values obtained by simply averaging the coordinate values of the plurality of internal range data associated with k) are associated with the voxel data V (i, j, k) as the average range data. The weighted average value can be associated with the voxel data V (i, j, k) as average range data. Hereinafter, the method will be described. The observation range data input to the data input unit 1 is represented by r0, r1,. . .
Then, the distance between the observation position of the range finder and the range data when each observation range data is observed is defined as the observation distances d0, d1,. . . And The observation range data holding such an observation distance is input to the data input unit 1. At this time, the voxel data V (i, j, k) is stored in the data storage unit 3 as the internal range data ra, rb, rc.
Is assumed to be correlated. Also, the internal range data r
The three-dimensional coordinate values of a, rb, and rc are respectively pa, pb,
pc, and the observation distances are da, db, and dc, respectively. Weight value of each internal range data is wt
(A), wt (b), and wt (c), which are defined as follows.

[0029]

(Equation 2) However, da>db> dc. Therefore, the smaller the observation distance is, the higher the reliability of the observation range data is. The smaller the observation distance is, the larger the weight is assigned to the internal range data. Average range data 3
The dimensional coordinate value pe is

[0030]

(Equation 3) Given by Therefore, in the data processing unit 3,
A method of obtaining the three-dimensional coordinate value of the average range data by weighting each observation range data is also included in the present invention.

Further, in the above-described embodiment, the correspondence to the voxel data is performed simply based on whether or not the observed range data exists inside the voxel data V (i, j, k). It is not limited to this method. Another method is described below. It is assumed that range data from a certain direction is observed so that the geometric phase relationship between the point sequences becomes known. For example, as shown in FIG. 20, adjacent points on the measured object are geometrically observed such that i = 0, 1, 2,..., J = 0, 1, 2,.
At this time, the geometric phase relationship between the point sequences in the range data in a certain observation direction θ is known, and a triangular patch can be generated as shown in FIG. That is, (i, j)
Th, (i + 1, j) th, (i + 1, j + 1) th,
A triangular patch is generated from the (i, j + 1) -th observed four adjacent point sequences. Data in which a triangular patch is generated from the range data observed in each direction as described above is input to the data input unit 1. The processing in the data storage unit 3 based on the data input as described above is as follows. The correspondence to the voxel data is determined by examining the spatial intersection between the triangular patch generated above and the voxel data, and a certain triangular patch is converted to the voxel data V (i, j, k).
And voxel data V (i,
j, k) is associated with the triangular patch. The associated voxel data V (i, j, k) is associated with the center of gravity of the eight vertices of the hexahedron of the voxel data V (i, j, k) as average range data. By associating the voxel data with the triangular patches in this manner, even when the range data is lower than the resolution of the voxel, shape data without holes can be generated, and the convenience is further improved.

[0032]

According to the present invention, the three-dimensional coordinate value obtained by observing the object to be measured is associated with each voxel data whose geometrical phase relationship is known, whereby the shape of the surface of the object to be measured is obtained. Can create data. Therefore, it is possible to remove the restriction on the measurement order of the three-dimensional coordinate values, which is conventionally required, and to obtain surface shape data with high accuracy even for an object having a complicated shape. Furthermore, by arbitrarily changing the size of the voxel data, it is possible to create shape data with desired accuracy from high-resolution shape data that faithfully reflects the observed three-dimensional coordinate values to low-resolution shape data with a small amount of data.

[Brief description of the drawings]

FIG. 1 is a schematic configuration diagram of an embodiment of the present invention.

FIG. 2 is a view for explaining processing contents of an embodiment of the present invention.

FIG. 3 is a processing flowchart according to the embodiment of the present invention.

FIG. 4 is a view for explaining processing contents of a data input unit according to the embodiment of the present invention.

FIG. 5 is a view for explaining processing contents of a cell generation unit according to the embodiment of the present invention.

FIG. 6 is a view for explaining processing contents of a data storage unit according to the embodiment of the present invention.

FIG. 7 is a view for explaining eight adjacent voxel data.

FIG. 8 is a diagram showing a pattern based on attribute values of each voxel data of an adjacent voxel data group VS.

FIG. 9 is a view showing a pattern based on attribute values of each voxel data of an adjacent voxel data group VG.

FIG. 10 is a view showing triangular patches generated corresponding to each pattern of FIG. 9;

FIG. 11 is a diagram illustrating a state in which a triangular patch hidden by another triangular patch occurs.

FIG. 12 is a diagram illustrating a state in which an overlapping triangular patch occurs.

FIG. 13 is a diagram showing a situation where a plurality of triangular patches are adjacent to each other.

FIG. 14 is a diagram showing a generation example of a thick surface.

FIG. 15 is a diagram showing tunability with respect to the orientation between triangular patches.

FIG. 16 is a view for explaining a connection process between triangular patches.

FIG. 17 is a flowchart of a connection process for a triangular patch.

FIG. 18 is a diagram illustrating patch generation when an unobserved region occurs.

FIG. 19 is a diagram showing an example of patch generation when a connection process is performed when an unobserved region occurs.

FIG. 20 is a diagram showing three-dimensional coordinate values measured geometrically.

FIG. 21 is a diagram illustrating a state where a triangular patch is generated from the three-dimensional coordinate values of FIG. 20;

FIG. 22 is a diagram showing a conventional shape restoration method.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 ... Data input part 2 ... Cell generation part 3 ... Data storage part 4 ... Cell pattern recognition part 5 ... Patch generation part 6 ... Shape data 7, 14, 15, 20 ... Observation range data 8, 18, 19, 23, 24 , 25 ... Voxel data 9 ... Triangle patch data 10, 11, 12, 49 ... Range finder 13, 50, 53 ... Object to be measured 16 ... Observation register data inclusion space 17 ... Observation range data inclusion space Vertex 21 ... Internal range data 22 ... average range data 26, 33, 36, 40, 41, 46, 47 ... logical hexahedron 28, 31, 34, 38, 44 ... voxel data with attribute value 0 29, 32, 35, 39, 45 ... attribute value 1 Voxel data 30 ... logical square 37, 42 ... triangle patch 43 ... concealed triangle patch 48 ... overlapping triangle patch

────────────────────────────────────────────────── ─── Continuation of the front page (56) References Masayuki Nakajima, Volume Rendering, IEICE Technical Report, Japan, The Institute of Electronics, Information and Communication Engineers, December 20, 1991, Vol. 91, No. 400, p. 1-8 (58) Field surveyed (Int. Cl. ⁷ , DB name) G06T 1/00 315 G06T 15/00 200

Claims (8)

(57) [Claims] 1. A data input unit for inputting three-dimensional coordinate values of a surface shape of an object to be measured, and a space that completely covers all three-dimensional coordinate values input from the data input unit is divided into a grid. A cell generator for creating the created voxel data,
For each voxel data created by the cell generator, a data storage unit for obtaining one range data using the corresponding three-dimensional coordinate value, and for each of a predetermined number of three-dimensionally adjacent voxel data, respectively. A triangular patch for each of the predetermined number of voxel data in accordance with the topological relationship obtained by the cell pattern recognition unit; And a patch generation unit for removing unnecessary triangular patches located on adjacent surfaces of the predetermined number of voxel data and using the patch data as shape data. 2. A cell generation unit calculates a maximum value and a minimum value in each of an X-axis direction, a Y-axis direction, and a Z-axis direction from an input three-dimensional coordinate value. 2. The shape restoring device according to claim 1, wherein the voxel data is created by dividing a predetermined number in each of the axial direction, the Y-axis direction, and the Z-axis direction. 3. The data accumulating section, when one voxel data includes one three-dimensional coordinate value, sets the voxel data as corresponding range data. When the voxel data includes a plurality of three-dimensional coordinate values, the average coordinate value is used. 2. The shape restoration apparatus according to claim 1, wherein when the voxel data does not include three-dimensional coordinate values, there is no corresponding range data. 4. The data storage unit sets the attribute value of the voxel data to 1 when the range data is associated with the voxel data, and sets the attribute value of the voxel data when the range data is not associated with the voxel data. 4. The shape restoration device according to claim 3, wherein the attribute value is set to 0. 5. The shape reconstructing apparatus according to claim 4, wherein the cell pattern recognition unit performs pattern matching for each logical hexahedron composed of eight adjacent voxel data in accordance with a combination of attribute values of the respective voxel data. 6. The patch generation unit according to claim 1, wherein, when the number of voxel data having the attribute value of 1 is 3 or more in the logical hexahedron, the patch generation unit forms a polyhedron closed between the voxel data having the attribute value of 1. 6. The shape restoring apparatus according to claim 5, wherein a triangular patch having a vertex of the range data of the voxel data is generated. 7. A patch generation unit that deletes the triangular patch if the triangular patch is bounded by another triangular patch between the logical hexahedrons and the triangular patch is hidden by another triangular patch in the logical hexahedron, or 7. The shape restoration device according to claim 6, wherein one of the triangular patches is deleted when each triangular patch is adjacent to each other as an overlapping boundary between the target hexahedrons. 8. A data input unit for inputting three-dimensional coordinate values of the surface shape of the object to be measured, and a space that completely covers all three-dimensional coordinate values input from the data input unit is divided into a grid. A cell generator for creating the created voxel data,
For each voxel data created by the cell generator, a data storage unit for obtaining one range data using the corresponding three-dimensional coordinate value, and for each of a predetermined number of three-dimensionally adjacent voxel data, respectively. A cell pattern recognizing unit for obtaining a topological relationship according to the range data, and forming a triangular patch for each of the predetermined number of voxel data according to the topological relationship obtained by the cell pattern recognizing unit; One side is shared with each side of a predetermined triangular patch in the group, and the triangular patches whose directions are synchronized are connected one by one, and the same connecting process is repeated for the unconnected side of the connected triangular patch. By doing
A patch generation unit for removing a triangular patch whose edges are not connected to each other.