Surface patch techniques for computational geometry

• US 9,262,859 B2
• Filed: 08/17/2014
• Issued: 02/16/2016
• Est. Priority Date: 07/23/1998
• Status: Expired due to Fees

• Current Assignee: Cad-Sense LLC
• Original Assignee: Freedesign, Inc.
• Inventors: Rockwood, Alyn P.
• Primary Examiner(s): Liu, Zhengxi
• Application Number:
  US14/461,439
• Publication Number:
  US 20140354639A1
• Time in Patent Office: 548 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06F 30/10 Geometric CAD
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 17/30 Polynomial surface description

Abstract

A method and system for computer aided design (CAD) is disclosed for designing geometric objects, wherein interpolation and/or blending between such objects is performed while deformation data is being input. Thus, a designer obtains immediate feedback to input modifications without separately entering a command (s) for performing such deformations. A novel N-sided surface generation technique is also disclosed herein to efficiently and accurately convert surfaces of high polynomial degree into a collection of lower degree surfaces. E.g., the N-sided surface generation technique disclosed herein subdivides parameter space objects (e.g., polygons) of seven or more sides into a collection of subpolygons, wherein each subpolygon has a reduced number of sides. More particularly, each subpolygon has 3 or 4 sides. The present disclosure is particularly useful for designing the shape of surfaces. Thus, the present disclosure is applicable to various design domains such as the design of, e.g., bottles, vehicles, and watercraft. Additionally, the present disclosure provides for efficient animation via repeatedly modifying surfaces of an animated object such as a representation of a face.

Claims

1. A computer-implemented method for deforming a computer displayed three dimensional surface during a continuous input by a user for such deformation, comprising performing the following by computer equipment:

displaying, on a computer display, at least one three dimensional geometric surface, which is represented by first data providing a parameterization of the at least one geometric surface, wherein the at least one geometric surface has an at least two dimensional area as a pre-image in the parameterization;

accessing respective data representing one or more additional geometric objects used in determining shape modified instances of the at least one geometric surface, each of the one or more additional geometric objects;

(i) having a corresponding portion that is coincident with the at least one geometric surface, and (ii) being continuously differentiable;

for at least one point of a plurality of user identified points, each of the user identified points included in the corresponding portion coincident with, the at least one geometric surface, receiving a user input for selecting the at least one point, or associated information associated with the at least one point, the associated information providing geometric information characteristic of one of the additional geometric objects having the at least one point;

iteratively performing A1 through A4 following so that the user perceives a substantially real time deformation of the at least one geometric surface during a continuous series of user inputs to the computer equipment, wherein each of the user inputs is for entering a corresponding change to one of;

a location for the at least one point, or the associated information therefor;

(A1) receiving a next one of the user inputs by the computer equipment;

(A2) deriving, using the next one of the user inputs received, data representing a modified version of the one additional geometric object,

wherein for another point, for the one additional geometric object, the another point being also one of the plurality of user identified points such that the another point is not selected by the user for contributing to the substantially real time deformation, and the another point has second associated data providing a second geometric information characteristic of the one additional geometric object at the another point,

then at least one of;

(1) the another point, and

(2) the second geometric information characteristic remains unchanged and also corresponds with the modified version;

(A3) subsequently, determining data representing one of the shape modified instances of the at least one geometric surface, using data representing a modified collection of the one or more additional geometric objects, wherein the modified version of the one additional geometric object is provided in the modified collection; and

(A4) displaying the one shape modified instance of the at least one geometric surface on a computer display.

2. The method of claim 1, wherein the geometric information characteristic includes a corresponding related extent for the at least one point, wherein one or more of:

i) the corresponding related extent has a parametric direction substantially identical to a parametric tangency direction of the at least one geometric surface at the at least one point according to the parameterization of the at least one geometric surface, and ii) a length of the corresponding related extent for the at least one point is representative of how closely a contour of the at least one geometric surface follows the parametric tangency direction as the contour extends away from the at least one point.

3. The method of claim 1, further including:

adding an additional boundary to the at least one geometric surface, or to a specified one of the shape modified instances, the additional boundary being responsive to a corresponding user input for selecting points therefor;

subsequently, generating a further geometric object for the additional boundary; and

subsequently, iteratively performing the A1 through A4 using the further geometric object as one of the additional geometric objects.

4. The method of claim 3, wherein the adding the additional boundary includes:

receiving input, of the corresponding user input by the computer equipment for identifying a point, q, for the at least one geometric surface or the specified one shape modified instance; and

subsequently, generating the additional boundary, wherein a boundary of the at least one geometric surface is modified to connectedly extend between the point q and another user identified point for the at least one geometric surface such that the additional boundary is interpolated from the at least one geometric surface or the specified one shape modified instance so that a tolerance between the at least one geometric surface or the specified one shape modified instance and the additional boundary is below a predetermined maximum tolerance.

5. The method of claim 1, wherein the next one of the user inputs moves the at least one point along a boundary curve, C, containing the at least one point, and further including changing the one shape modified instance of the at least one geometric surface as a result of the next one of the user inputs.

6. The method of claim 1, wherein the next one of the user inputs is generated from the user dragging a graphical representation of the at least one point.

7. The method of claim 1, wherein the geometric information characteristic includes a corresponding related extent, E, for the one additional geometric object, and further including maintaining a predetermined constraint for the corresponding related extent E, wherein the constraint includes one of:

(a) constraining the extent E to a predetermined range of directions;

(b) constraining the extent E to a predetermined range of magnitudes; and

(c) constraining the extent E to a predetermined range of curvatures.

8. The method of claim 1, wherein the geometric information characteristic includes data for a corresponding related extent, E, for the one additional geometric object, and further including maintaining a predetermined constraint for the corresponding related extent E, wherein the constraint includes one of:

(a) constraining the extent E to lie in a plane with another related extent for some other point of the corresponding portion for at least one of the additional geometric objects; and

(b) constraining the extent E to transform identically with another related extent for some other point of the corresponding portion for at least one of the additional geometric objects.

9. The method of claim 1, wherein the another point is user designated.

10. The method of claim 1, further including, prior to the receiving the user input, receiving a designation by the user for designating the another point.

11. The method of claim 1, wherein the determining the data representing the one shape modified instance includes combining a plurality of terms for determining points of the one shape modified instance, wherein for each pre-image point in a plurality of points distributed throughout the at least two dimensional area, and for each surface (S_i) of the modified collection, conditions (I) and (II) following hold:

(I) there are one or more corresponding terms, T, of the plurality of the terms, each term, T, dependent on the pre-image point and the surface S_i; and

(II) each of the corresponding terms T is determined by computing a multiplicative product of;

(a) a corresponding term weighting, and (b) data representing a particular point of the surface S_i, wherein the particular point has the pre-image point, upon which the corresponding term T is dependent, as a pre-image;

wherein for each term, T′

, of a plurality of the terms that are dependent on the surface S_i being the modified version of the one additional geometric object, the corresponding term weighting (W), used in determining the term T′

, is determined by the computer equipment computing a value determined using a distance-like measurement between;

(i) the pre-image point for the term T′

, and (ii) a pre-image of the corresponding portion for the at least one geometric surface and the one additional geometric object.

12. The method of claim 11, wherein each of the one or more additional geometric objects has a pre-image parameterization space, and further including obtaining, for each term weighting (Wtg) used in determining the terms for determining points of the one shape modified instance, a corresponding value of a blending function, wherein the corresponding value is used for determining the corresponding term weighting Wtg.

13. The method of claim 11, wherein the corresponding term weighting, W, vary monotonically with a corresponding distance-like measurements, each of the corresponding distance-like measurements, DM, being indicative of a spacing between:

(i) for a particular one of the term weightings W for which the distance-like measurement DM is used for computing the value for determining the particular term weighting W, the pre-image point upon which a particular one of the terms T′

depends, the particular term T′

determined using the particular term weighting W, and

(ii) a pre-image of the corresponding portion for the at least one geometric surface and the one additional geometric object.

14. The method of claim 11, wherein the distance-like measurement is determined by a distance-like function.

15. The method of claim 1, wherein the corresponding portion is a connected boundary of the at least one geometric surface, the connected boundary including a plurality of boundary points.

16. The method of claim 1, wherein the one additional geometric object is a ruled surface.

17. The method of claim 1, wherein the geometric information characteristic includes an extent of at least a portion of the one additional geometric object.

18. The method of claim 1, wherein the geometric information characteristic includes a shape of at least a portion of the one additional geometric object.

19. The method of claim 1, wherein the corresponding portion of the one additional geometric object includes a connected portion that connects the at least one point to the another point.

20. The method of claim 1, wherein the corresponding portion of the one additional geometric object includes a curve between the at least one point to the another point.