Three-dimensional geometry processing system

Claim 1

An apparatus for generating, from surface data and curve data, an intersection point between a surface and a curve, for use in a three-dimensional geometry processing system, the apparatus comprising: a) checking means for checking whether or not there is an intersection between convex hulls by obtaining: 1) a convex hull of the surface at a given control point, and 2) a convex hull of the curve at a given control point; b) generating means including: 1) means for generating a rough intersection point which is an intersection point between: i) a polygonal face of a polyhedron obtained from the surface data, and ii) a segment of a polyline obtained from the curve data; and 2) means for generating an initial parameter with respect to an initial point on the surface located at the rough intersection point and an initial parameter with respect to an initial point on the curve located at the rough intersection point; and c) adjusting means for generating an intersection point between the surface and the curve, by updating respective parameters of the surface and the curve, starting from the initial parameters with respect to the initial points, and ending at secondary parameters with respect to secondary points on the surface and the curve, wherein: 1) the secondary points are nearer to the intersection point between the surface and the curve than the initial points; and 2) the adjusting means includes means for performing steps A), B), C) and D), in order to update the respective parameters of the surface and the curve: A) generating a tangent plane of the surface at the initial point on the surface and a tangent line of the curve at the initial point on the curve, based on the initial parameters; B) generating a secondary rough intersection point which is an intersection point between the tangent plane and the tangent line; C) generating the secondary parameters with respect to the secondary point on the surface nearest the secondary rough intersection point and with respect to the secondary point on the curve nearest the secondary rough intersection point; and D) repeating the steps A), B) and C) until respective changes from the initial parameters to the secondary parameters are detected to meet a convergence criterion.

Claim 2

An apparatus for generating, from surface data and curve data, an intersection point between a surface and a curve, for use in a three-dimensional geometry processing system, the apparatus comprising: a) checking means for checking whether or not there is an intersection between convex hulls by obtaining: 1) a convex hull of the surface at a given control point, and 2) a convex hull of the curve at a given control point; b) generating means including: 1) means for generating a rough intersection point which is an intersection point between: i) a polygonal face of a polyhedron obtained from the surface data, and ii) a segment of a polyline obtained from the curve data; and 2) means for generating an initial parameter with respect to an initial point on the surface located at the rough intersection point and an initial parameter with respect to an initial point on the curve located at the rough intersection point; and c) adjusting means for generating an intersection point between the surface and the curve, by updating respective parameters of the surface and the curve, starting from the initial parameters with respect to the initial points, and ending at secondary parameters with respect to secondary points on the surface and the curve, wherein: 1) the secondary points are nearer to the intersection point between the surface and the curve than the initial points; and 2) the adjusting means includes means for performing steps A), B), C) and D), in order to update the respective parameters of the surface and the curve: A) generating a tangent plane of the surface at the initial point on the surface and a tangent line of the curve at the initial point on the curve, based on the initial parameters; B) generating a secondary rough intersection point which is an intersection point between the tangent plane and the tangent line; C) generating the secondary parameters with respect to the secondary point on the surface nearest the secondary rough intersection point and with respect to the secondary point on the curve nearest the secondary rough intersection point; and D) repeating the steps A), B) and C) until respective changes from the initial parameters to the secondary parameters are detected to meet a convergence criterion.

Claim 3

An apparatus for generating, from surface data and point data, parameters of a surface at a point, for use in a three-dimensional geometry processing system, the apparatus comprising: a) input means for inputting the surface data and the point data; b) rough parameter generating means including: 1) means for generating a polygonal face of a polyhedron on the surface near the point, based on the surface data and the point data; and 2) means for generating rough parameters with respect to an endpoint of the polygonal face, and rough parameters with respect to a first projective point based on the rough parameters of the endpoint, by obtaining the first projective point by projecting the point onto the polygonal face; and c) parameter adjusting means including: 1) means for generating a tangent plane of the surface at the first projective point, based on the rough parameters generated by the rough parameter generating means; and 2) means for generating parameters of the surface at the point by repeatedly updating the rough parameters of the surface, starting from the rough parameters with respect to the first projective point, and continuing to rough parameters with respect to a second projective point which is obtained by projecting the point onto a subsequently generated polygonal face, until respective changes in the rough parameters of the surface from the first projective point to the second projective point meet a convergence criterion.

Claim 4

An apparatus for generating, from surface data and point data, parameters of a surface at a point, for use in a three-dimensional geometry processing system, the apparatus comprising: a) input means for inputting the surface data and the point data; b) rough parameter generating means including: 1) means for generating a polygonal face of a polyhedron on the surface near the point, based on the surface data and the point data; and 2) means for generating rough parameters with respect to an endpoint of the polygonal face, and rough parameters with respect to a first projective point based on the rough parameters of the endpoint, by obtaining the first projective point by projecting the point onto the polygonal face; and c) parameter adjusting means including: 1) means for generating a tangent plane of the surface at the first projective point, based on the rough parameters generated by the rough parameter generating means; and 2) means for generating parameters of the surface at the point by repeatedly updating the rough parameters of the surface, starting from the rough parameters with respect to the first projective point, and continuing to rough parameters with respect to a second projective point which is obtained by projecting the point onto a subsequently generated polygonal face, until respective changes in the rough parameters of the surface from the first projective point to the second projective point meet a convergence criterion.