Computational geometry using control geometry having at least two dimensions

• US 7,755,623 B2
• Filed: 10/16/2008
• Issued: 07/13/2010
• Est. Priority Date: 07/23/1998
• Status: Expired due to Fees

• Current Assignee: Cad-Sense LLC
• Original Assignee: Freedesign, Inc.
• Inventors: Lee, John, Hagen, Lance, Hagen, Scott A., Rockwood, Alyn P.
• Primary Examiner(s): Nguyen; Kimbinh T
• Application Number:
  US12/253,165
• Publication Number:
  US 20090033658A1
• Time in Patent Office: 635 Days
• Field of Search: 345/419, 345/420, 345/441, 345/442, 345/586, 345/473, 345/474, 382/131, 715/964
• US Class Current: 345/420
• CPC Class Codes: G06T 17/30 Polynomial surface description
• CPC Class Codes: Y10S 715/964 CAD or CAM, e.g. interactive design tools

Abstract

A method and system for computer aided design (CAD) is disclosed for designing geometric objects. The present invention interpolates and/or blends between such geometric objects sufficiently fast so that real time deformation of such objects occurs while deformation data is being input. Thus, a user designing with the present invention obtains immediate feedback to input modifications without separately entering a command for performing such deformations. The present invention utilizes novel computational techniques for blending between geometric objects, wherein weighted sums of points on the geometric objects are used in deriving a new blended geometric object. The present invention is particularly useful for designing the shape of surfaces. Thus, the present invention is applicable to various design domains such as the design of, e.g., bottles, vehicles, and watercraft. Additionally, the present invention provides for efficient animation via repeatedly modifying surfaces of an animated object such as a representation of a face.

Claims

1. A method for modifying data representing a geometric object, comprising:

displaying, by a computational machine, a first geometric object having a parameterization, wherein the first geometric object has a dimension greater than or equal to two in an object space coordinate system, and wherein the first geometric object has an at least a two dimensional area as a pre-image in a parametric space for the parameterization;

wherein for each of the one or more additional geometric objects, respective data therefor is effective for defining a curve where the additional geometric object meets the first geometric object in the object space coordinate system;

wherein, for least one of the one or more curves, corresponding marker data is available, the corresponding marker data representing one or more marker points on the at least one curve such that for each of the one or more marker points, there is at least one corresponding marker related extent of one of the additional geometric objects that is used in defining the at least one curve;

receiving, by the computational machine, and for the at least one curve, a selection by a user of at least one of the marker points, or the at least one corresponding marker related extent, for the at least one marker point;

iteratively performing, by the computational machine, the following steps (A1) through (A4) so that the user is presented with a substantially real time deformation of the first geometric object during a continuous time series of user inputs, wherein each of the user inputs is indicative of a corresponding change to one of;

a location for the at least one marker point, or a geometric property of the at least one corresponding marker related extent for the at least one marker point;

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

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

wherein the modified version is dependent upon the at least one marker point after the change, and, for the ibe additional geometric object, when;

(i) another of the marker points of the at least one curve, and

(ii) the corresponding marker related extent in the one additional geometric object, and for the another marker point, are each not selected by the user for contributing to the real time deformation than at least one of the another marker points, and the corresponding extent for the another marker point remains unchanged and is also included in the modified version;

(A3) subsequently, determining data representing a modified instance of the first geometric object, using data representing a modified collection of the one or more additional geometric objects, wherein the modified version MV of the one additional geometric object is provided in the modified collection, and data for the modified version is used in determining the modified instance,

wherein for each pre-image point of a plurality of points of the two dimensional area pre-image, a corresponding substep of combining terms is performed, wherein for each object of the modified collection, one of the terms is determined by computing a product of a weighting, and data representing a particular point of the object, wherein the particular point has the pre-image point as a pre-image, and

wherein for each of the pre-image points, the weightings, used in determining the terms for the corresponding substep of combining, satisfy a predetermined constraint; and

(A4) displaying the modified instance of the first geometric object to a user.

2. The method of claim 1, wherein the extent for the at least one marker is such that:

(i) the extent has a parametric direction substantially identical to a parametric tangency direction of the first geometric object at the at least one marker point according to the parameterization of the first geometric object, and

(ii) a length of the extent for the at least one marker is representative of how closely a contour of the first geometric object follows the tangency direction as the contour extends away from the marker point.

3. The method of claim 1, wherein

step A3 includes a step of determining a corresponding data D_S for computing points of the modified instance of the first geometric object from points of the parametric space, wherein for each of the additional geometric objects, S_i, and a corresponding one of the curves B_i, each point N of the modified instance is computed via D_Sfrom a parametric space point that is in a pre-image of the one of the curves B_i.

4. The method of claim 1, wherein the first geometric object is a surface, and each of the additional geometric objects is a surface, and at least one of the curves is a boundary of the first geometric object.

5. The method of claim 1, wherein each of the curves has a corresponding pre-image in the parametric space, and there are at least five of the corresponding curve pre-images.

6. The method of claim 1 further including:

adding an additional curve to the first geometric object or one of the instances of the first geometric object by the user selecting points;

subsequently, generating a further one of the additional geometric objects having the additional curve therein; and

subsequently, iteratively performing the steps A1 through A4 with the additional geometric objects including the further additional geometric object.

7. The method of claim 6, wherein the step of adding the an additional curve includes:

receiving a user input (UI) identifying a point of the first geometric object or the one instance; and

subsequently, automatically generating the additional curve as a boundary, and as part of a collection of one or more automatically generated boundaries, wherein the collection of boundaries connectedly extend between the point identified by the user input UI, and another user identified point terminating the collection of boundaries such that the boundaries of the collection are interpolated from the first geometric object or the one instance so that a tolerance between the first geometric object or the one instance and the collection of boundaries is below a predetermined maximum tolerance.

8. The method of claim 1, further including a step of determining the weightings of the terms for one of the geometric objects OBJ of the modified collection by performing a step of obtaining an evaluation of a blending function, wherein the evaluation determines a collection of the weightings having a weighting for each point of a plurality of points distributed throughout the two dimensional area pre-image, wherein the weightings of the collection vary monotonically with a Euclidean distance between the plurality of points and the pre-image of the additional geometric object.

9. The method of claim 1, wherein the predetermined constraint is independent of the pre-image point.

10. The method of claim 1, wherein the step of combining includes determining a weighted sum, wherein for each of the weighted sums determined, a summation of the weights therefor is effectively a same constant value.

11. The method of claim 1, wherein one or more of the user inputs changes the tangency direction of the at least one corresponding marker related extent.

12. The method of claim 1, wherein one or more of the user inputs changes the length of the at least one corresponding marker related extent for the at least one marker point.

13. The method of claim 1, wherein a pre-image of each of the curves in the parameter space is different.

14. The method of claim 1, wherein one or more of the user inputs moves the at least one marker point along the at least one curve, and further including a step of changing the at least one curve as a result of the one or more user inputs.

15. The method of claim 1, wherein one or more of the user inputs is generated from the user dragging a graphical representation of the at least one marker point.

16. The method of claim 1, wherein for each of the curves, and each point, pt, of a plurality of points determined on the curve, a further step of determining pt as a sum of weighted vectors, wherein:

(a) each weighting is determined as an evaluation of one of a quintic polynomial, a Bezier function, a sine squared function, or a cosine squared function,

(b) the weightings provide a partition of unity, and

(c) for each of the vectors, the vector is a dependent upon data resulting from a sum of;

(i) a marker point, m_i, for the curve, and (ii) a tangent vector of the curve at the marker point m_i scaled by a linear function of values in the pre-image.

17. The method of claim 1, further including a step of determining another curve for the additional geometric object, the another curve being different from the at least one curve having the at least one marker point, wherein each point, pt, of a plurality of points of the another curve is dependent upon data resulting from a sum of weighted vectors, wherein:

(a) each weighting for the weighted sum is determined as an evaluation of one of;

a quintic polynomial, a Bezier function, a sine squared function or a cosine squared function,

(b) the weightings of the weighted sum are a partition of unity, and

(c) for each of the vectors, the vector is determined using the sum of (i) and (ii) following;

(i) a marker point, m_i, for the at least one curve having the at least one marker point, and

(ii) a tangent vector of the at least one curve, having the at least one marker point, at the marker point m_i scaled by a linear function of values in the pre-image.

18. The method of claim 1, wherein the respective data for each of the additional geometric objects is defined by geometric characteristics of exactly two of the marker points on the curve for the additional geometric object.

19. The method of claim 18, wherein the exactly two marker points on the curve for the additional geometric object are endpoints thereof.

20. The method of claim 1, further including, during the iteratively performing step, a step of maintaining a predetermined constraint for the at least one corresponding marker related extent, P, for the at least one marker point, wherein the constraint includes one of:

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

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

(c) constraining the extent P to lie in a plane with another corresponding marker related extent for another of the marker points included in the additional geometric object;

(d) constraining the extent P to a predetermined range of curvatures; and

(e) constraining the extent P to transform identically with another corresponding marker related extent for another of the marker points included in the additional geometric object.

21. The method of claim 1, further including a step of determining the additional geometric object as a blend of two other surfaces.

22. The method of claim 1, wherein the additional geometric object includes two of the additional geometric objects, and the at least one marker point is provided on each of the two additional geometric objects, wherein each iteration of substep A2 derives a modified version of each of the two additional geometric objects.

23. The method of claim 1, wherein step A3 includes a step of determining corresponding data D_S for computing points of the modified instance of the first geometric object from points of the parametric space, wherein for at least one object in the modified collection, and a corresponding curve B₁ for both the at least one object and the modified instance, each point P of the modified instance that is computed from a point p, in the parametric space, that is also in the pre-image of the curve B_i, as computed via data D_si, the point P is included in the curve B_i.

24. The method of claim 1, wherein the corresponding change includes a change in the location for the at least one marker point.

25. The method of claim 1, wherein the corresponding change includes a change in the corresponding marker related extent for the at least one marker point.

26. A system for modifying data representing a geometric object, comprising:

a user interface of a computational machine, for displaying a first geometric object having a parameterization, wherein the first geometric object has a dimension greater than or equal to two in an object space coordinate system, and wherein the first geometric object has an at least a two dimensional area as a pre-image in a parametric space for the parameterization;

wherein for each of one or more additional geometric objects, respective data therefor is effective for providing a boundary where the additional geometric object meets the first geometric object in the object space coordinate system;

wherein, for at least one of the one or more boundaries of the above identified boundaries, corresponding marker data is accessible by the computational machine, the corresponding marker data representing at least two marker points on the at least one boundary such that for each of the at least two marker points, there is at least one corresponding marker related extent of the additional geometric object that is used in providing the at least one boundary;

wherein the user interface receives a selection by a user of at least one of the marker points or the at least one corresponding marker related extent for the at least one marker point;

wherein the computational machine iteratively performs the following steps (A1) through (A4) so that the user is presented with a substantially real time deformation of the first geometric object during a continuous time series of user inputs to the user interface, wherein each of the user inputs provides a corresponding change to one of;

a location for the at least one marker point, or a geometric property of the at least one corresponding marker related extent for the at least one marker point;

(A1) receiving a next one of the user inputs at the user interface;

(A2) deriving, using the next one of the user inputs received, data representing a modified version of at least one of the additional geometric objects, wherein the at least one additional geometric object includes the at least one marker point as one of the marker points therefor,

wherein the modified version includes the at least one marker point after the change, and, for the at least one additional geometric object, when;

(i) another of the marker points of the at least one additional geometric object, and

(ii) the corresponding marker related extent of the at least one additional geometric object, and for the another marker points, are each not selected by the user for a contributing to the real time deformation, then at least one of the another marker point, and the corresponding marker related extent for the another marker point remains unchanged and is also included in the modified version;

(A3) subsequently, determining data representing a modified instance of the first geometric object, using data representing a modified collection of the one or more additional geometric objects, wherein the modified version of the at least one additional geometric object is provided in the modified collection, and data for the modified version is used in determining the modified instance,

wherein for each pre-image point of a plurality of points of the two dimensional area pre-image, a corresponding substep of combining terms is performed, wherein for each object, of the modified collection, one of the terms is determined by computing a multiplicative product of a weighting, and data representing a particular point of the object,

wherein for each of the objects of the modified collection, the particular point has the pre-image point as a pre-image, and

wherein for each of the pre-image points, the weightings, used in determining the terms for the corresponding substep of combining, satisfy a predetermined constraint; and

(A4) displaying to a user the modified instance of the first geometric object.

27. The system of claim 26, wherein one or more of a shape, a position and an orientation of said at least one additional geometric object is indicative of a first value for a geometric characteristic of said first geometric object at the at least one marker point, and the modified version of said at least one additional geometric object is indicative of a second value of the geometric characteristic for said modified instance of the first geometric object.

28. The system of claim 27, wherein the geometric characteristic includes one of a tangency, a curvature, a higher order continuity condition, and a differentiability condition at the at least one marker point.

29. A method for modifying data representing a geometric object by first displaying a first geometric object having a parameterization, wherein the first geometric object has a dimension greater than or equal to two in an object space coordinate system, and wherein the first geometric object has an at least a two dimensional area as a pre-image in a parametric space for the parameterization;

wherein a computational machine has respective data representing one or more additional geometric objects available,

wherein for each of the one or more additional geometric objects, the respective data therefor is effective for determining a boundary where the additional geometric object meets the first geometric object;

wherein, for each of one or more of the above identified boundaries, marker data representing at least two marker points on the boundary is defined such that for each of the marker points, there is at least one corresponding marker related extent of one of the additional geometric objects, wherein the corresponding marker related extent is used in determining a corresponding portion of the first geometric object, comprising;

for at least one of the marker points, a step of receiving a selection by a user of the at least one of the marker point or a geometric property of the at least one corresponding marker related extent, for the at least one marker point;

iteratively performing, by the computational machine, the following sequence of steps (A1) through (A4) so that the user perceives a substantially real time deformation of the first geometric object during a continuous time series of user inputs, wherein each of the user inputs is for entering a corresponding change to one of;

a location for the at least one marker point, or the at least one corresponding marker related extent for the at least one marker point;

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

(A2) deriving, using the next one of the user inputs received, data representing a modified version of at least one of the additional geometric objects having the at least one marker point as one of the marker points therefor,

wherein the modified version of the at least one additional geometric object includes the corresponding change, and, for the at least one additional geometric object, when each of (i) and (ii) following are not selected by the user for contributing to the real time deformation, then at leasr one other of the marker points for the at least one additional geometric object, and the corresponding marker related extent for the at least one other of the marker points remains unchanged and is also included in the modified version;

(i) the at least one other of the marker points therefor, and

(ii) the corresponding marker related extent of the at least one additional geometric object, and also for the other of the marker points;

(A3) subsequently, determining data representing a modified instance of the first geometric object, using data representing a modified collection of the one or more additional geometric objects, wherein the modified version MV of the at least one additional geometric object is provided in the modified collection, and data for the modified version MV is used in determining the modified instance;

wherein for each pre-image point of a plurality of points of the two dimensional area pre-image, a corresponding substep of combining terms is performed, wherein for each object OBJ, of the modified collection, one of the terms is determined by computing a multiplicative product of a weighting, and data representing a particular point of the object OBJ,

wherein for each of the objects OBJ of the modified collection, the particular point has the pre-image point as a pre-image, and

wherein for each of the pre-image points, the weightings used in determining the terms for the corresponding substep of combining are such that these weightings satisfy a predetermined constraint; and

(A4) displaying the modified instance to the user.

30. A system for modifying data representing a geometric object, comprising:

a user interface provided by performing computer instructions by a computational machine, for displaying a first geometric object having a parameterization, wherein the first geometric object has a dimension greater than or equal to two, and wherein the first geometric object has an at least a two dimensional area as a pre-image in a parametric space for the parameterization;

wherein for each of one or more additional geometric objects, respective data therefor is effective for defining a boundary with the first geometric object in an object space coordinate system;

wherein, for at least one of one or more of the above identified boundaries, corresponding marker data is accessible by the computational machine, the corresponding marker data representing one or more marker points on the at least one boundary such that for each of the one or more marker points, there is at least one corresponding marker related extent of one of the additional geometric objects that is used in defining the at least one boundary;

wherein for the at least one boundary, the user interface receives a selection by a user of at least one of the marker points or the at least one corresponding marker related extent for the at least one marker point;

wherein the computational machine iteratively performs the following sequence of steps (A1) through (A4) so that the user is presented with a substantially real time deformation of the first geometric object during a continuous time series of user inputs to the user interface, wherein each of the user inputs is indicative of a corresponding change to one of;

a location for the at least one marker point, or the at least one corresponding marker related extent for the at least one marker point;

(A1) receiving a next one of the user inputs at the user interface;

(A2) deriving, using the next one of the user inputs received, data representing a modified version, MV, of the additional geometric object for defining the at least one boundary,

wherein the modified version MV is dependent upon the at least one marker point after the corresponding change, and, for the additional geometric object, when each of (i) and (ii) following are not selected by the user for contributing to the real time deformation, then at least one other of the marker points, and the corresponding marker related extent for the at least one other of the marker points remains unchanged and is also included in the modified version;

(i) the at least one other of the marker points of the at least one boundary, and

(ii) the corresponding marker related extent in the additional geometric object, and for the one other of the marker points;

(A3) subsequently, determining data representing a modified instance of the first geometric object, using data representing a modified collection of the one or more additional geometric objects, wherein the modified version MV of the additional geometric object is provided in the modified collection,

wherein for each pre-image point of a plurality of points of the two dimensional area pre-image, a corresponding substep of combining terms is performed, wherein for each object, OBJ, of the modified collection, one of the terms is determined by computing a multiplicative product of a weighting, and data representing a particular point of the object OBJ,

wherein for each of the objects OBJ of the modified collection, the particular point has the pre-image point as a pre-image, and

wherein for each of the pre-image points, the weightings used in determining the terms for the corresponding substep of combining, are such that these weightings satisfy a predetermined constraint; and

(A4) displaying the modified instance of the first geometric object according to the modified data representing the first geometric object.

31. A method for modifying a representation of a geometric object, wherein there is a display, by a computational machine, of a first geometric object representation having a dimension greater than or equal to two in an object space coordinate system, and wherein the computational machine has access to one or more additional geometric object representations, wherein at least one geometric characteristic of each of said additional geometric object representations is indicative of a shape of said first geometric object representation at at least one point thereof, and wherein one or more of said additional geometric object representations have a dimension greater than or equal to 1 in the object space coordinate system, comprising:

iteratively performing, by the computational machine, in response to an input by a user of a substantially continuous time series of change requests for changing said first geometric object representation, the following sequence of steps (A1) and (A2);

(A1) changing data indicative of a change in the object space coordinate system of one of a shape, an orientation and a position of at least one of said additional geometric object representations in response to a corresponding prior portion of the substantially continuous time series of change requests;

(A2) graphically displaying a geometrically modified version of said first geometric object representation having modifications indicative of the data resulting from the changing step of (A1), wherein the data resulting from the changing step of (A1), is indicative of a geometric characteristic of the geometrically modified version at at least one point thereof;

wherein for successive activations of the sequence of steps (A1) and (A2), each activation of the sequence;

(a) computes a weighted sum of points, P, for obtaining each of a plurality of points, q, of a corresponding instance of the geometrically modified version resulting from the activation, wherein said points P are obtained using the data changed in step (A1) of the activation, and (b) displays a corresponding instance of the geometrically modified version in real time as the user inputs a next portion of the substantially continuous time series, wherein the next portion becomes a subsequent instance of the prior portion used in a subsequent one of the successive activations.

32. The method of claim 31, wherein for each of the successive activations, the geometric characteristic of the modified version includes a tangency of a corresponding resulting instance of the at least one additional geometric object representation with the corresponding instance of the geometrically modified version at a corresponding instance of the at least one point of the modified version.

33. The method of claim 31, wherein for each of the successive activations, the geometric characteristic of the modified version includes a curvature of a corresponding resulting instance of the at least one additional geometric object representation providing a curvature of the corresponding instance of the geometrically modified version at a corresponding instance of the at least one point of the modified version.

34. The method of claim 31, wherein for each of the successive activations, the geometric characteristic of the modified version includes curvature continuity or other higher order continuity condition of a corresponding resulting instance of the at least one additional geometric object representation providing a continuity condition of the corresponding instance of the geometrically modified version at a corresponding instance of the at least one point of the modified version.

35. The method of claim 31, wherein for each of the successive activations, the geometric characteristic of the modified version includes a differentiability condition of a corresponding resulting instance of the at least one additional geometric object representation providing a differentiability condition of the corresponding instance of the geometrically modified version at a corresponding instance of the at least one point of the modified version.

36. The method of claim 35, wherein the differentiability condition includes continuous differentiability.

37. The method of claim 31, wherein said weighted sum includes weights wherein each weight is obtained using a corresponding blending function, each said blending function having a range of predetermined numerical extent along a line, and each said blending function being dependent upon a parametric pre-image of a corresponding one of the points q for determining the weight to which the blending function corresponds.

38. A method for modifying a representation of a geometric object, comprising:

providing, to a computer aided design computational machine, two or more particular geometric object representations, wherein one or more of a shape, an orientation and a position of said particular geometric object representations are used in determining a shape of a first geometric object representation relative to a coordinate system, wherein said first geometric object representation has a dimension greater than or equal to two in the coordinate system, and wherein one or more of said particular geometric object representations have a dimension greater than or equal to 1 in the coordinate system;

first displaying, by the computational machine, a first display of said first geometric object to a user;

iteratively performing, by the computational machine, a sequence of steps, the sequence including steps of receiving and second displaying following;

receiving data indicative of a geometric change to one of a shape, a position, and an orientation of at least one of said one or more particular geometric object representations thereby obtaining a changed one or more of said particular geometric object representations;

second displaying, to the user, a second display of a geometric object representation, GR, wherein the geometric object representation GR for said second display is determined using said changed one or more of the particular geometric object representations, and wherein a shape difference between said first geometric object representation and the geometric object representation GR for said second display is determined using, from the data, a value for said one of the orientation and shape changed in said step of receiving;

wherein the geometric object representation GR for the second display includes a representation whose display includes a point, P_i, derived using said changed particular geometric object representations, wherein said point P_i is not representative of a point of said changed particular geometric objects; and

wherein each iteration of said receiving step includes inputting, by the user, a next portion of a substantially continuous time series of change requests used for changing said particular geometric object representations;

wherein said iteratively performed steps of receiving and second displaying are interleaved so that the user perceives a substantially real time deformation of said first geometric object representation during said continuous time series of change requests.

39. The method of claim 38, wherein there is at least one point, P, of a parametric space being a pre-image for the first geometric object representation and the geometric object representation GR:

(i) said first display of said first geometric object representation at P, and

(ii) said second display of the geometric object representation GR at P are different.

40. The method of claim 38, wherein said particular geometric object representations include one of a parametric surface and a plurality of points obtained from said parametric surface.

41. The method of claim 38, wherein there is no manual entry after said step of receiving resulting in a performance of an immediately subsequent performance of said step of second displaying.

42. The method of claim 38, wherein the coordinate system is for an object space having a display of each said first geometric object representation, and said geometric object representation GR provided therein.

43. The method of claim 38, further including a step of determining three dimensional coordinates of points of said geometric object representation GR for said second display.