Contour triangulation system and method

A method of reconstructing a surface shape of an object from a plurality of contour lines, comprising:

• obtaining a plurality of contour lines by scanning an object to obtain scan data and segmenting the scan data;
• assigning points, by a computer, to each of the plurality of contour lines obtained from the segmented scan data of the object, 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 by the computer, 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.

A method of reconstructing a surface shape of an object from a plurality of contour lines, comprising:

• obtaining a plurality of contour lines by scanning an object to obtain scan data and segmenting the scan data;
• assigning points, by a computer, to each of the plurality of contour lines obtained from the segmented scan data of the object, 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 by the computer, 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.

A computer readable memory having stored thereon program code executable on a computer that when executed by the computer cause the computer to perform a method comprising:

• assigning points to each of a plurality of contour lines obtained from segmented scan data of an object, 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.

A computer readable having stored thereon program code executable on a computer that when executed by the computer cause the computer to perform a method comprising:

• assigning points to each of a plurality of contour lines obtained from segmented scan data of an object, 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.

A computer readable memory having stored thereon program code executable on a computer that when executed by the computer cause the computer to perform a method comprising:

• assigning points to each of a plurality of contour lines obtained from segmented scan data of an object, 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 t) 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.

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.