Contour triangulation system and method
First Claim
1. A method of reconstructing a surface shape of an object from a plurality of contour lines, comprising:
- obtaining the plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a first triangulation scheme with respect to respective points on two adjacently-positioned contour lines, to determine a first surface shape for a portion of the object corresponding to the two adjacently-positioned contour lines;
checking the first surface shape to determine if the first surface shape is in error;
if the first surface shape is not in error, outputting the first surface shape for the portion of the object as determined by the first triangulation scheme, as a reconstructed surface shape for the portion of the object; and
if the first surface shape is in error, performing a second triangulation scheme with respect to the respective points on the two adjacently-positioned contour lines, to determine a second surface shape for the portion of the object corresponding to the two adjacently-positioned contour lines; and
outputting the second surface shape for the portion of the object as determined by the second triangulation scheme, as a reconstructed surface shape for the portion of the object.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for reconstructing a surface shape of an object having contour lines, includes assigning points to each contour line. A first triangulation scheme is performed with respect to respective points on two adjacently-positioned contour lines, to determine a first surface shape for a portion of the object corresponding to the two contour lines. The first surface shape is checked to determine if the first surface shape is in error. If the first surface shape is not in error, the first surface shape is outputted for the portion of the object as determined by the first triangulation scheme, as a reconstructed surface shape for that portion of the object. If the first surface shape is in error, a second triangulation scheme is performed with respect to the respective points on the two contour lines, to determine a second surface shape for that portion of the object, and the second surface shape is outputted for that portion of the object as determined by the second triangulation scheme, as a reconstructed surface shape.
-
Citations
51 Claims
-
1. A method of reconstructing a surface shape of an object from a plurality of contour lines, comprising:
-
obtaining the plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a first triangulation scheme with respect to respective points on two adjacently-positioned contour lines, to determine a first surface shape for a portion of the object corresponding to the two adjacently-positioned contour lines;
checking the first surface shape to determine if the first surface shape is in error;
if the first surface shape is not in error, outputting the first surface shape for the portion of the object as determined by the first triangulation scheme, as a reconstructed surface shape for the portion of the object; and
if the first surface shape is in error, performing a second triangulation scheme with respect to the respective points on the two adjacently-positioned contour lines, to determine a second surface shape for the portion of the object corresponding to the two adjacently-positioned contour lines; and
outputting the second surface shape for the portion of the object as determined by the second triangulation scheme, as a reconstructed surface shape for the portion of the object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method of reconstructing a surface shape of an object from a plurality of contour lines, comprising:
-
obtaining the plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a shortest distance triangulation scheme with respect to respective points on two adjacently-positioned contour lines that correspond to first and second contour lines, to determine a first surface shape for a portion of the object corresponding to the first and second contour lines, wherein the shortest distance triangulation scheme comprises;
a) for each point on the first contour line, determining a point on the second contour line that is closest to the point on the first contour line;
b) setting a first triangle leg as a line that connects the point on the second contour line that is closest to the point on the first contour line;
c) comparing a first distance from the point on the second contour line to an adjacent point on the first contour line that is adjacent the point on the first contour line, to a second distance from an adjacent point on the second contour line to the point on the first contour line;
d) based on the comparing step, setting a second triangle leg as a line that connects the shorter one of the first and second distances, and setting a third triangle leg as a line that connects either the point and the adjacent point on the first contour line, or the point and the adjacent point on the second contour line; and
e) repeating steps a) through d) by moving to a next point in either a clockwise direction or a counterclockwise direction on either the first contour line or the second contour line, until all points on the first and second contour lines have been connected to another point on the other of the first and second contour lines. - View Dependent Claims (13, 14, 15, 16)
-
-
17. A method of reconstructing a surface shape of an object from a plurality of contour lines, comprising:
-
obtaining the plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a closest orientation triangulation scheme with respect to respective points on two adjacently-positioned contour lines that correspond to first and second contour lines, to determine a first surface shape for a portion of the object corresponding to the first and second contour lines, wherein the closest orientation triangulation scheme comprises;
a) for each point on the first contour line, determining an orientation of a centroid vector of the point on the first contour line to each contour point on the second contour line;
b) determining a closest orientation of the centroid vector of the point on the first contour line to a centroid vector of a point on the second contour line;
c) repeating steps a) and b) until a closest orientation for all points on the first contour line have been determined;
d) setting a first triangle leg as a line that connects the point on the second contour line that has the closest orientation to the point on the first contour line;
e) comparing a first orientation from the point on the second contour line to an adjacent point on the first contour line that is adjacent the point on the first contour line, to a second orientation from an adjacent point on the second contour line to the point on the first contour line;
f) based on the comparing step, setting a second triangle leg as a line that connects the closest orientation of the first and second orientations, and setting a third triangle leg as a line that connects either the point and the adjacent point on the first contour line, or the point and the adjacent point on the second contour line; and
g) repeating steps d) through f) by moving to a next point in either a clockwise direction or a counterclockwise direction on either the first contour line or the second contour line, until all points on the first and second contour lines have been connected to another point on the other of the first and second contour lines. - View Dependent Claims (18, 19, 20, 21, 22)
-
-
23. A computer program product executable on a computer and configured to compute a surface shape of an object, the computer program product, when executed on the computer, performing the steps of:
-
obtaining a plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a first triangulation scheme with respect to respective points on two adjacently-positioned contour lines, to determine a first surface shape for a portion of the object corresponding to the two adjacently-positioned contour lines;
checking the first surface shape to determine if the first surface shape is in error;
if the first surface shape is not in error, outputting the first surface shape for the portion of the object as determined by the first triangulation scheme, as a reconstructed surface shape for the portion of the object; and
if the first surface shape is in error, performing a second triangulation scheme with respect to the respective points on the two adjacently-positioned contour lines, to determine a second surface shape for the portion of the object corresponding to the two adjacently-positioned contour lines; and
outputting the second surface shape for the portion of the object as determined by the second triangulation scheme, as a reconstructed surface shape for the portion of the object. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
34. A computer program product executable on a computer and configured to compute a surface shape of an object, the computer program product, when executed on the computer;
- performing the steps of;
obtaining a plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a shortest distance triangulation scheme with respect to respective points on two adjacently-positioned contour lines that correspond to first and second contour lines, to determine a first surface shape for a portion of the object corresponding to the first and second contour lines, wherein the shortest distance triangulation scheme comprises;
a) for each point on the first contour line, determining a point on the second contour line that is closest to the point on the first contour line;
b) setting a first triangle leg as a line that connects the point on the second contour line that is closest to the point on the first contour line;
c) comparing a first distance from the point on the second contour line to an adjacent point on the first contour line that is adjacent the point on the first contour line, to a second distance from an adjacent point on the second contour line to the point on the first contour line;
d) based on the comparing step, setting a second triangle leg as a line that connects the shorter one of the first and second distances, and setting a third triangle leg as a line that connects either the point and the adjacent point on the first contour line, or the point and the adjacent point on the second contour line; and
e) repeating steps a) through d) by moving to a next point in either a clockwise direction or a counterclockwise direction on either the first contour line or the second contour line, until all points on the first and second contour lines have been connected to another point on the other of the first and second contour lines. - View Dependent Claims (35, 36, 37, 38)
- performing the steps of;
-
39. A computer program product executable on a computer and configured to compute a surface shape of an object, the computer program product, when executed on the computer, performing the steps of:
-
obtaining a plurality of contour lines by scanning the object to obtain scan data and segmenting the scan data;
assigning points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
performing a closest orientation triangulation scheme with respect to respective points on two adjacently-positioned contour lines that correspond to first and second contour lines, to determine a first surface shape for a portion of the object corresponding to the first and second contour lines, wherein the closest orientation triangulation scheme comprises;
a) for each point on the first contour line, determining an orientation of a centroid vector of the point on the first contour line to each contour point on the second contour line;
b) determining a closest orientation of the centroid vector of the point on the first contour line to a centroid vector of a point on the second contour line;
c) repeating steps a) and b) until a closest orientation for all points on the first contour line have been determined;
d) setting a first triangle leg as a line that connects the point on the second contour line that has the closest orientation to the point on the first contour line;
e) comparing a first orientation from the point on the second contour line to an adjacent point on the first contour line that is adjacent the point on the first contour line, to a second orientation from an adjacent point on the second contour line to the point on the first contour line;
f) based on the comparing step, setting a second triangle leg as a line that connects the closest orientation of the first and second orientations, and setting a third triangle leg as a line that connects either the point and the adjacent point on the first contour line, or the point and the adjacent point on the second contour line; and
g) repeating steps d) through f) by moving to a next point in either a clockwise direction or a counterclockwise direction on either the first contour line or the second contour line, until all points on the first and second contour lines have been connected to another point on the other of the first and second contour lines. - View Dependent Claims (40, 41, 42, 43, 44)
-
-
45. An apparatus for reconstructing a surface shape of an object from a plurality of contour lines, comprising:
-
a scanner unit configured to obtain the plurality of contour lines by scanning the object to obtain scan data and to segment the scan data;
an assigning unit configured to assign points to each of the plurality of contour lines obtained from the segmented scan data, wherein each of the contour lines is closed and non-intersecting with respect to others of the contour lines;
a first triangulation computation unit configured to perform a first triangulation scheme with respect to respective points on two adjacently-positioned contour lines, to determine a first surface shape for a portion of the object corresponding to the two adjacently-positioned contour lines;
a checking unit configured to check the first surface shape to determine if the first surface shape is in error;
a second triangulation computation unit configured to perform a second triangulation scheme with respect to the respective points on the two adjacently-positioned contour lines, to determine a second surface shape for the portion of the object corresponding to the two adjacently-positioned contour lines; and
an output and display unit configured to output and display either the first surface shape as output by the first triangulation computation unit or the second surface shape as output by the second triangulation computation unit, as a reconstructed surface shape for the portion of the object. - View Dependent Claims (46, 47, 48, 49, 50, 51)
-
Specification