Computational geometry using control geometry having at least two dimensions

• US 7,417,635 B2
• Filed: 03/01/2007
• Issued: 08/26/2008
• Est. Priority Date: 07/23/1998
• Status: Expired due to Fees

• Current Assignee: Cad-Sense LLC
• Original Assignee: Freedesign, Inc.
• Inventors: Hagen, Lance, Hagen, Scott A., Rockwood, Alyn P., Lee, John N.
• Primary Examiner(s): Nguyen; Kimbinh T
• Application Number:
  US11/681,077
• Publication Number:
  US 20070152999A1
• Time in Patent Office: 544 Days
• Field of Search: 345/419, 345/420, 345/441, 345/442
• US Class Current: 345/419
• 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 determining a blended geometric object, comprising:

providing, for each of a plurality of parameterized geometric objects S_i, i=1, . . . , N, N≧

2, a mapping f_si from a parametric space, PS, to a common geometric space GS containing the S_i wherein (A1) and (A2) hold;

(A1) at least one of the plurality of parameterized geometric objects, S_i0, has a dimension greater than or equal to 2;

(A2) for each S_i there is a portion P_i of S_i wherein f_Si is continuous at points of f_Si<sup>−

1</sup>(P_i);

computing, a function S at each of a plurality of points q in PS, for obtaining a corresponding point S(q) in GS, wherein (B1) and (B2) hold;

(B1) S(q) is dependent upon

$f_{S_{i_0}}^{-1}$

and at least one f_Sj(q) for j∫

i₀, and wherein S(f_S0<sup>−

1</sup>(P_i0))⊂

P_i0, S(f_Sj<sup>−

1</sup>(P_j))⊂

P_j,

(B2) S is a continuous at

$f_{S_{i_0}}^{-1}<br><br>\left(P_{i_o}\right)<br><br><br><br>\mathrm{and}<br><br><br><br>f_{S_j}^{-1}<br><br>\left(S_j\right);<br><br>$

and f_Sj<sup>−

1</sup>(S_j);

displaying a representation of said corresponding points S(q) as a representation of a geometric object that blends between Sio and Sj.

2. The method as claimed in claim 1, wherein:

(a) each said mapping f_si is a parametric mapping for parameterizing the S_i;

(b) each said S_i is a surface;

(c) each said P_i is a curve for one of the S_i;

(d) said points, S(q), are contained within a surface defined by said function S, wherein said curves P_i are included in a perimeter of said surface.

3. The method as claimed in claim 2, wherein each of said P_i is interpolated through a plurality of points.

4. The method as claimed in claim 1, wherein points of said parametric space PS are represented as a tuple of a predefined number of coordinates, wherein each coordinate has a predetermined range.

5. The method as claimed in claim 1, wherein said computing step includes determining S(q) as a function of at least a weighted sum of

$f_{S_{i_0}}\; <li></li>\left(q\right)$

and f_sj(q).

6. The method as claimed in claim 5, wherein said step of computing includes determining, for at least some of said points S(q), one or more corresponding weights of said weighted sum, wherein each weight, w, scales a point of one of said geometric objects Si.

7. A method for determining a blended geometric object, G, comprising:

providing, for each of a plurality of parameterized geometric objects S_i, i=1, . . . , N, N≧

2, a mapping f_si from a parametric space, PS, to a common geometric space GS containing the S_i wherein (A1) and (A2) hold;

(A1) at least one of the plurality of parameterized geometric objects, S_io, includes a surface or a geometric object of a higher dimension than that of a surface;

(A2) for each S_i there is a portion P_i of S_i wherein f_si is continuous at points of f_si<sup>−

1</sup>(P_i);

computing, a function S at each of a plurality of points q in PS, for obtaining a corresponding point S(q) in GS, wherein (B1) and (B2) hold;

(B1) S(q) is dependent upon

$f_{S_{i_0}}<br><br>\left(q\right)$

 

and at least one f_sj(q) for j≠

i₀, and wherein

$S<br><br>\left(f_{S_{i_0}}^{-1}<br><br>\left(P_{i_0}\right)\right)\subseteq <br><br>P_{i_0},$

 

S(f_sj<sup>−

1</sup>(P_j))⊂

P_j; and

(B2) S is continuous at

$f_{S_{i_0}}^{-1}<br><br>\left(P_{i_0}\right)<br><br><br><br>\mathrm{and}<br><br><br><br>f_{S_f}^{-1}<br><br>\left(S_j\right);<br><br>$

displaying, on a computer display device, a representation of said corresponding points S(q) as a representation of the geometric object G that blends between S_i0 and S_j;

displaying, on the computer display device with G, a representation, R, related to a shape of G, wherein the representation R is indicative of;

(i) a tangent, T, of G that is also a tangent of S_io at a common point, m₀, of G and P_i0, and (ii) how closely a contour of G follows the tangent T as the contour extends away from the common point m₀;

receiving a user input for modifying G, the input including one or more of the following (C1) through (C3);

(C1) a different geometric location for m₀ in GS;

(C2) a modified version of the tangent T at m₀; and

(C3) data indicating a change in how closely a contour of G is to follow the modified version of the tangent T if available, and the tangent T otherwise;

deriving, using the user input, data indicative of points of a modified version of G, wherein;

(D1) there is at most an insubstantial difference between m₀ and a corresponding location of the modified version of G;

(D2) the modified version of the tangent T, if available, and the tangent T otherwise, is tangent to the modified version of G at the corresponding location; and

(D3) the modified version of G has a contour extending away from the corresponding location that is indicative of any change according to (C3);

wherein said step of deriving includes determining a weighted sum dependent upon at least one of the parameterized geometric objects S_i, and the user input; and

displaying the modified version of G on the computer display device.

8. The method of claim 7, further including a step of determining, using the user input, a modified version of S_i0, wherein:

(E1) there is at most an insubstantial difference, in GS, between m₀ and a location, m, in the modified version of S_io;

(E2) the modified version of the tangent T, if available, and the tangent T otherwise is tangent to the modified version of S_io at m; and

(E3) there is a path in the modified version of S_io, representing any change according to (C3).

9. The method of claim 8, wherein the path extends from m to a point on a boundary of S_io, wherein the boundary point is determined by a step of blending between representations of two geometric objects, each of the representations of the geometric objects determined from a corresponding tangency condition to the boundary at one of first and second points of the boundary, wherein in traversing the boundary from the first point to the second point, the location m is encountered during the traversal.

10. The method of claim 9, wherein the location m resides on another boundary of S_io, having no common points with the boundary.

11. The method of claim 10, wherein the another boundary is at most insignificantly different from P_i0.

12. The method of claim 11, wherein P_i0 is a curve, and is a boundary for both S_io and G.

13. The method of claim 12, wherein each of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2 satisfies all antecedent limitations of S_i0 by S_i replacing S_i0.

14. The method of claim 7, wherein the blended geometric object G includes a surface, and each of the parameterized geometric objects S_i includes a surface, and each of portion P_i of S_i is a curve.

15. The method of claim 7, wherein each of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2 has a boundary with G, and each of the boundaries has a corresponding pre-image in the parametric space PS, and there are at least five of the corresponding boundary pre-images.

16. The method of claim 7 further including the steps of:

adding a boundary to the blended geometric object G or the modified version thereof by the user selecting points for the boundary;

subsequently, generating a further one of the parameterized geometric objects, S_N+1, having the boundary;

displaying, with the modified version of G, a representation, R_N+1, related to a shape of the modified version of G, wherein the representation R_N+1 is indicative of;

(i) a tangent, T_N+1, of the modified version of G that is also a tangent of S_N+1 at a common point, m_N+1, of the modified version of G and the boundary, and (ii) how closely a contour, C, of the modified version of G follows the tangent T_N+1 as the contour C extends away from the common point m_N+1;

receiving a second user input for modifying the modified version of G, the second input including one or more of the following (F1) through (F3);

(F1) a different geometric location for m_N+1 in GS;

(F2) a modified version of the tangent T_N+1 at m_N+1; and

(F3) data indicating a change in how closely a contour of the modified version of G is to follow the modified version of the tangent T_N+1 if available, and the tangent T_N+1 otherwise;

deriving, using the second user input, data indicative of a further modified version of G, wherein;

(G1) there is at most an insubstantial difference between m_N+1 and a corresponding location, m′

_N+1, in the further modified version of G;

(G2) the modified version of the tangent T_N+1, if available, and the tangent T_N+1 otherwise, is tangent to the further modified version of G at the corresponding location m′

_N+1; and

(G3) the further modified version of G has a contour extending away from the corresponding location m′

_N+1 that is indicative of any change according to (F3); and

displaying the further modified version of G.

17. The method of claim 16, wherein the step of adding an additional boundary includes:

receiving a user input identifying a point, n, of the modified version of G; and

subsequently, generating the boundary as part of a collection of one or more generated boundaries, wherein the collection of boundaries connectedly extend between the user identified point n, and another user identified point terminating the collection of boundaries such that the boundaries of the collection are interpolated from the modified version of G so that there is a maximum tolerance between the modified version of G and the collection of boundaries.

18. The method of claim 7, wherein the deriving step includes determining the data indicative of the modified blended geometric object G, wherein for each point, p, of a plurality of points distributed throughout the parametric space PS, a substep of summing is performed wherein a plurality of terms are summed together, one term for each of the plurality of parameterized geometric objects S_i, i=1, . . . , N, N≧

2, wherein each term is determined as a multiplicative product of a weighting, and a particular point of S_i, wherein each of the particular points has p as a pre-image in PS;

wherein a summation of the weightings for the pre-image point p is a predetermined value independent of p.

19. The method of claim 18, further including determining the weightings of the terms for one of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2 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 parametric space PS, wherein the weightings of the collection vary monotonically with a Euclidean distance between;

(i) the points of the plurality points, and (ii) a pre-image in PS of the one parameterized geometric object.

20. The method of claim 18, wherein the predetermined value is one.

21. The method of claim 7, wherein there are at least three of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2, and each of the two S_i different from S_i0 satisfies all antecedent limitations of S_i0 when each of the two S_i is substituted for S_i0.

22. The method of claim 7, wherein the user input changes a direction of the tangent T.

23. The method of claim 7, wherein the user input changes the length of the tangent T.

24. The method of claim 7, wherein each of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2 includes a boundary, B_i, that is also a boundary of the blended geometric object G, wherein the boundaries B_i i=1, . . . , N, N≧

2 form a closed curve surrounding G, and the user input moves the least one point, m₀, along the closed curve, and further including a step of automatically extending at least one of the boundaries as a result of the user input.

25. The method of claim 7, wherein each displayed point, q, of the blended geometric object G is determined by computing a weighted sum of points, one from each of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2, having a same pre-image point as a pre-image of q in the parametric space PS, wherein for each of the weighted sums, a sum of all the weights for the weighted sum is a value insignificantly different from one.

26. The method of claim 7, wherein the user input is generated from the user dragging a graphical representation of the marker point m₀.

27. The method of claim 24, wherein for each of the boundaries B_i, and each point, pt, of a plurality of points determined on the boundary, 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 are a partition of unity, and

(c) for each of the vectors, the vector is the sum of;

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

28. The method of claim 24, wherein for each of the boundaries B_i, a further step of determining each point, pt, of a plurality of points of the corresponding portion, CP, for the boundary B_i 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 are a partition of unity, and

(c) for each of the vectors, the vector is the sum of;

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

29. The method as claimed in claim 28, wherein the corresponding portion CP is a boundary for the parameterized geometric object S_i, having B_i as a boundary.

30. The method of claim 7, wherein at least one of the parameterized geometric objects S_i is defined by geometric characteristics of exactly two points on a boundary for the parameterized geometric object S_i.

31. The method of claim 30, wherein the exactly two points are endpoints of the boundary.

32. The method of claim 7, further including a step of displaying on a computer monitor one of the parameterized geometric objects S_i as a separate graphical entity from the blended geometric object G.

33. The method of claim 7, further including, during the deriving step, a step of maintaining a predetermined constraint for a path across one of the parameterized geometric objects, wherein the constraint includes one of:

(a) constraining the path to a predetermined range of directions;

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

(c) constraining the path to a predetermined to lie in a plane with another path provided on the at least one additional geometric object representation;

(a) constraining the path to a predetermined range of curvatures; and

(b) constraining the path to transform identically with another path provided on the at least one additional geometric object representation.

34. The method of claim 7, wherein at least one of the parameterized geometric objects S_i is a ruled surface.

35. The method of claim 7, further including determining at least one of the parameterized geometric objects S_i as a blend of two other surfaces.

36. The method of claim 7, wherein the at least one parameterized geometric object, includes, with S_io, another of the plurality of parameterized geometric objects, and the point m₀ is provided on each of S_io and the another parameterized geometric object, and the method further including determining a modified version of each of S_io and the another parameterized geometric object using the user input.

37. The method of claim 7, wherein the at least one parameterized geometric object, S_io, is graphically selected from a display of the computer display device.

38. The method of claim 7, wherein each of the plurality of parameterized geometric objects S_i, i=1, . . . , N, N≧

2 has four sides.

39. The method of claim 7, further including iteratively performing the steps of:

(i) receiving, (ii) deriving, and (iii) displaying successive modified versions of G, wherein instances of the receiving step overlaps with instances of the step of displaying successive modified versions of G, so that the user perceives a substantially real time deformation of G during a continuous time series of the user inputs for modifying G.

40. The method of claim 39, including, between instances of the receiving step, and instances of the step of displaying successive modified versions of G, a further step of obtaining a corresponding modified version of at least the parameterized geometric object S_io having one or more of the changes of (C1) through (C3), wherein for at least one point m₁ of S_io not selected by the user, no tangent, T₁, of G that is also a tangent of S_io at the point, m₁, of P_i0 is changed.

41. The method of claim 40, wherein each of the parameterized geometric objects, S_i, includes data D_si for determining points of S_i in the common geometric space GS from points of the parametric space PS, and the step of obtaining includes a step of determining a different version of the data

$D_{S_{i_0}}$

for the corresponding modified version of S_i0; and

determining a corresponding data D_s for computing points of the modified version of G, wherein for each S_i and a corresponding boundary B_i thereof that is also a boundary of G, each point n of S, computed via D_s from a parametric space point that is in the pre-image of the boundary B_i as computed via data D_si, is included in the boundary B_i.

42. The method of claim 7, wherein the step of determining a weighted sum includes, for each point (p) of a plurality of points distributed throughout the parametric space PS, a substep of summing, wherein a plurality of terms are summed together, one term for each object of the parameterized geometric objects S_i, i=1, . . . , N, N≧

2, wherein each term is determined as a multiplicative product of a weighting, and a particular point of the object, wherein the particular point has p as a pre-image.