Method for designing curved shapes for use by a computer

• US 5,636,338 A
• Filed: 01/29/1993
• Issued: 06/03/1997
• Est. Priority Date: 01/29/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Moreton, Henry P.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/010,800
• Time in Patent Office: 1,586 Days
• Field of Search: 395/119, 395/120, 395/127, 395/133, 395/138, 395/139, 395/140, 395/141, 395/142, 395/143, 395/150, 395/151
• US Class Current: 345/442
• CPC Class Codes: G06T 17/30 Polynomial surface description

Abstract

Methods for forming computer models of curves, networks, or surfaces from user defined specifications of the shape to be modeled. Each specification includes a set of geometric constraints, such as positions, tangents curvatures, and torsions, and may also include discontinuity specifications. In the preferred embodiment, curves are computed so as to locally minimize a scale invariant functional of the geometry of the curve, such as a magnitude of variation in curvature of the curve (MVC) or a magnitude of curvature of the curve (MEC), while satisfying a user defined specification. An improvement on the MVC functional is to add a magnitude of variation in torsion of the curve. An improvement on the MEC functional is to add a magnitude of torsion of the curve. Networks of curves are produced using similar techniques of computing a local minimum of a functional of the geometry of the curves comprising the network, such as a magnitude of variation in curvature of the curves (MVN) or a magnitude of curvature of the curves (MEN), while satisfying a user defined specification. An improvement on these methods is to make the MVN and MEN functionals scale invariant. Another improvement is to make the MVN and MEN functionals torsion dependent. Surfaces are produced using a technique of computing a locally minimized functional of a magnitude of variation in curvature of the surface (MVS), while satisfying a set of surface constraints. An improvement on this method is to make the MVS functional scale invariant.

Claims

1. A method for producing a representation of a curve for display by a computer system, comprising:

specifying a desired shaped of the curve utilizing a set of geometric constraints;

specifying a scale invariant functional of the desired shape that is locally minimized and operative to measure a magnitude of variation in a curvature of the desired shape;

producing a representation of the curve based on the functional and the set of geometric constraints; and

displaying the representation of the curve via an output device to create a visual or physical embodiment of the curve.

2. The method as recited in claim 1, wherein the functional is further operative to measure variations in a torsion of the desired shape.

3. The method as recited in claim 2, wherein the functional is a sum of an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape and an arc length integral of a square of an arc length derivative of the torsion of the desired shape.

4. The method as recited in claim 3, wherein said functional is made scale invariant by multiplying the sum by a cube of an arc length of the desired shape.

5. The method as recited in claim 1 wherein the set of geometric constraints includes at least one point that the desired shape of the curve must interpolate.

6. The method as recited in claim 1 wherein the set of geometric constraints includes at least one tangent that the desired shape of the curve must interpolate.

7. The method as recited in claim 1 wherein the set of geometric constraints includes at least one curvature that the desired shape of the curve must interpolate.

8. The method as recited in claim 1, wherein the set of geometric constraints includes at least one torsion that the desired shape of the curve must interpolate.

9. The method as recited in claim 1 wherein the set of geometric constraints includes at least one G² discontinuity specification for the desired shape of the curve.

10. The method as recited in claim 1, wherein the set of geometric constraints includes at least one G¹ discontinuity specification for the desired shape of the curve.

11. The method as recited in claim 1, wherein the magnitude of variation is an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape.

12. The method as recited in claim 1, wherein the functional is made scale invariant by multiplying the magnitude of variation by a cube of an arc length of the desired shape.

13. The method as recited in claim 1, wherein the functional is made scale invariant by multiplying the magnitude of curvature by an arc length of the desired shape.

14. A method for producing a representation of a curve for display by a computer system, comprising:

specifying a desired shape of the curve utilizing a set of geometric constraints;

specifying a functional of the desired shape that is locally minimized, operative to measure a magnitude of variation in a curvature of the desired shape, and operative to measure a magnitude of variation in a torsion of the desired shape;

producing a representation of the curve based on the specified functional and the specified set of geometric constraints; and

displaying the representation of the curve via an output device to create a visual or physical embodiment of the curve.

15. The method as recited in claim 14, wherein the functional is a sum of an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape and an arc length integral of a square of an arc length derivative of the torsion of the desired shape.

16. The method as recited in claim 14, wherein the set of geometric constraints includes at least one point that the desired shape of the curve must interpolate.

17. The method as recited in claim 14, wherein the set of geometric constraints includes at least one tangent that the desired shape of the curve must interpolate.

18. The method as recited in claim 14, wherein the set of geometric constraints includes at least one curvature that the desired shape of the curve must interpolate.

19. The method as recited in claim 14, wherein the set of geometric constraints includes at least one torsion that the desired shape of the curve must interpolate.

20. The method as recited in claim 14, wherein the set of geometric constraints includes at least one G² discontinuity specification for the desired shape of the curve.

21. The method as recited in claim 14, wherein the set of geometric constraints includes at least one G¹ discontinuity specification for the desired shape of the curve.

22. The method as recited in claim 14, wherein the magnitude of variation is an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape.

23. A method for producing a representation of a curve for use by a computer system, comprising:

specifying a desired shape of the curve utilizing a set of geometric constraints;

specifying a scale invariant functional of the desired shape that is locally minimized and operative to measure a magnitude of curvature of the desired shape;

producing a representation of the curve based on the functional and the set of geometric constraints; and

displaying the representation via an output device to create a visual or physical embodiment of the curve.

24. The method as recited in claim 23, wherein the functional is further operative to measure a torsion of the desired shape.

25. The method as recited in claim 24, wherein the functional is a sum of an arc length integral of a square of the magnitude of curvature of the desired shape and an arc length integral of a square of the torsion of the desired shape.

26. The method as recited in claim 25, wherein the functional is made scale invariant by multiplying the sum by a cube of an arc length of the desired shape.

27. The method as recited in claim 23, wherein the set of geometric constraints includes at least one point that the desired shape of the curve must interpolate.

28. The method as recited in claim 23, wherein the set of geometric constraints includes at least one tangent that the desired shape of the curve must interpolate.

29. The method as recited in claim 23, wherein the set of geometric constraints includes at least one curvature that the desired shape of the curve must interpolate.

30. The method as recited in claim 23, wherein the set of geometric constraints includes at least one torsion that the desired shape of the curve must interpolate.

31. The method as recited in claim 23, wherein the set of geometric constraints includes at least one G¹ discontinuity specification for the desired shape of the curve.

32. The method as recited in claim 23, wherein the set of geometric constraints includes at least one G² discontinuity specification for the desired shape of the curve.

33. The method as recited in claim 23, wherein the functional is an arc length integral of a square of the magnitude of curvature of the desired shape.

34. A method for producing a representation of a curve for display by a computer system, comprising:

specifying a desired shape of the curve utilizing a set of geometric constraints;

specifying a functional of the desired shape that is locally minimized, operative to measure a magnitude of curvature of the desired shape, and operative to measure a torsion of the desired shape;

producing a representation of the curve based on the functional and the set of geometric constraints; and

displaying the representation of the curve via an output device to create a visual or physical embodiment of the curve.

35. The method as recited in claim 34, wherein the functional is a sum of an arc length integral of a square of the magnitude of curvature of the desired shape and an arc length integral of a square of the torsion of the desired shape.

36. The method as recited in claim 34, wherein the set of geometric constraints includes at least one point that the desired shape of the curve must interpolate.

37. The method as recited in claim 34, wherein the set of geometric constraints includes at least one tangent that the desired shape of the curve must interpolate.

38. The method as recited in claim 34, wherein the set of geometric constraints includes at least one curvature that the desired shape of the curve must interpolate.

39. The method as recited in claim 34, wherein the set of geometric constraints includes at least one torsion that the desired shape of the curve must interpolate.

40. The method as recited in claim 34, wherein the set of geometric constraints includes at least one G¹ discontinuity specification for the desired shape of the curve.

41. The method as recited in claim 34, wherein the set of geometric constraints includes at least one G² discontinuity specification for the desired shape of the curve.

42. The method as recited in claim 34, wherein the functional is an arc length integral of a square of the magnitude of curvature of the desired shape.

43. A method for producing a representation of a network of curves for display by a computer system, comprising:

specifying a desired shape of the network of curves utilizing a set of geometric constraints;

specifying a scale invariant functional of the desired shape that is locally minimized and operative to measure a magnitude of variation in a curvature of the desired shape;

producing a representation of the network of curves based on the functional and the set of geometric constraints; and

displaying the representation of the network of curves via an output device to create a visual or physical embodiment of the network of curves.

44. The method as recited in claim 43, wherein the functional is an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape.

45. The method as recited in claim 43, wherein the functional is further operative to measure variations in a torsion of the desired shape.

46. The method as recited in claim 45, wherein the functional is a sum of an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape and an arc length integral of a square of an arc length derivative of the torsion of the desired shape.

47. The method as recited in claim 46, wherein the functional is made scale invariant by multiplying the functional by a cube of an arc length of the desired shape.

48. The method as recited in claim 43, wherein the functional is made scale invariant by multiplying the functional by a cube of an arc length of the desired shape.

49. The method as recited in claim 43, wherein the set of geometric constraints includes at least one point that the desired shape of the network of curves must interpolate.

50. The method as recited in claim 43, wherein the set of geometric constraints includes at least one tangent plane that the desired shape of the network of curves must interpolate.

51. The method as recited in claim 43, wherein the set of geometric constraints includes at least one direction of principle curvature of the desired shape that the desired shape of the network of curves must interpolate.

52. The method as recited in claim 43, wherein the set of geometric constraints includes at least one maximum principle curvature of the desired shape that the desired shape of the network of curves must interpolate.

53. The method as recited in claim 43, wherein the set of geometric constraints includes at least one minimum principle curvature of the desired shape that the desired shape of the network of curves must interpolate.

54. The method as recited in claim 43, wherein the set of geometric constraints includes at least one tangent direction that the desired shape of the network of curves must interpolate.

55. The method as recited in claim 43, wherein the set of geometric constraints includes at least one pair of curves that meet with G¹ continuity at a node of the network of curves.

56. The method as recited in claim 43, wherein the set of geometric constraints includes at least one pair of curves that meet with G² continuity at a node of the network of curves.

57. A method for producing a representation of a network of curves for display by a computer system, comprising:

specifying a desired shape of the network of curves utilizing a set of geometric constraints;

specifying a functional of the desired shape that is locally minimized, operative to measure a magnitude of variation in a curvature of the desired shape, and operative to measure variations in a torsion of the desired shape;

producing a representation of the network of curves based on the functional and the set of geometric constraints; and

displaying the representation of the network of curves via an output device to create a visual or physical embodiment of the network of curves.

58. The method as recited in claim 57, wherein the functional is a sum of an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape and an arc length integral of a square of an arc length derivative of the torsion of the desired shape.

59. The method as recited in claim 57, wherein the set of geometric constraints includes at least one point that the desired shape of the network of curves must interpolate.

60. The method as recited in claim 57, wherein the set of geometric constraints includes at least one tangent plane that the desired shape of the network of curves must interpolate.

61. The method as recited in claim 57, wherein the set of geometric constraints includes at least one direction of principle curvature of the desired shape that the desired shape of the network of curves must interpolate.

62. The method as recited in claim 57, wherein the set of geometric constraints includes at least one maximum principle curvature of the desired shape that the desired shape of the network of curves must interpolate.

63. The method as recited in claim 57, wherein the set of geometric constraints includes at least one minimum principle curvature of the desired shape that the desired shape of the network of curves must interpolate.

64. The method as recited in claim 57, wherein the set of geometric constraints includes at least one tangent direction that the desired shape of the network of curves must interpolate.

65. The method as recited in claim 57, wherein the set of geometric constraints includes at least one pair of curves that meet with G¹ continuity at a node of the network of curves.

66. The method as recited in claim 57, wherein the set of geometric constraints includes at least one pair of curves that meet with G² continuity at a node of the network of curves.

67. A method for producing a representation of a network of curves for display by a computer system, comprising:

specifying a desired shape of the network of curves utilizing a set of geometric constraints;

specifying a functional of the desired shape that is locally minimized, operative to measure a magnitude of curvature of the desired shape, and operative to measure a torsion of the desired shape;

producing a representation of the network of curves based on the functional and the set of geometric constraints; and

displaying the representation of the network of curves via an output device to create a visual or physical embodiment of the network of curves.

68. The method as recited in claim 67, wherein the functional is a sum of an arc length integral of a square of a magnitude of the curvature of the desired shape and an arc length integral of a square of the torsion of the desired shape.

69. The method as recited in claim 67, wherein the set of geometric constraints includes at least one point that the desired shape of the network of curves must interpolate.

70. The method as recited in claim 67, wherein the set of geometric constraints includes at least one tangent plane that the desired shape of the network of curves must interpolate.

71. The method as recited in claim 67, wherein the set of geometric constraints includes at least one direction of principle curvature that the desired shape of the network of curves must interpolate.

72. The method as recited in claim 67, wherein the set of geometric constraints includes at least one maximum principle curvature that the desired shape of the network of curves must interpolate.

73. The method as recited in claim 67, wherein the set of geometric constraints includes at least one minimum principle curvature that the desired shape of the network of curves must interpolate.

74. The method as recited in claim 67, wherein the set of geometric constraints includes at least one pair of curves that meet with G¹ continuity at a node of the network of curves.

75. The method as recited in claim 67, wherein the set of geometric constraints includes at least one tangent direction that the desired shape of the network of curves must interpolate.

76. A method for producing a representation of a network of curves for display by a computer system, comprising:

specifying a desired shape of the network of curves utilizing a set of geometric constraints;

specifying a scale invariant functional of the desired shape that is locally minimized and operative to measure a magnitude of curvature of the desired shape;

producing a representation of the network of curves based on the functional and the set of geometric constraints; and

displaying the representation of the network of curves via an output device to create a visual or physical embodiment of the network of curves.

77. The method as recited in claim 76, wherein the functional is an arc length integral of a square of a magnitude of an arc length derivative of the curvature of the desired shape.

78. The method as recited in claim 76, wherein the functional is further operative to measure variations in a torsion of the desired shape.

79. The method as recited in claim 78, wherein the functional is a sum of an arc length integral of a square of a magnitude of the curvature of the desired shape and an arc length integral of a square of the torsion of the desired shape.

80. The method as recited in claim 79, wherein the functional is made scale invariant by multiplying the functional by a cube of an arc length of the desired shape.

81. The method as recited in claim 76, wherein the functional is made scale invariant by multiplying the functional by a cube of an arc length of the desired shape.

82. The method as recited in claim 76, wherein the set of geometric constraints includes at least one point that the desired shape of the network of curves must interpolate.

83. The method as recited in claim 76, wherein the set of geometric constraints includes at least one tangent plane that the desired shape of the network of curves must interpolate.

84. The method as recited in claim 76, wherein the set of geometric constraints includes at least one direction of principle curvature that the desired shape of the network of curves must interpolate.

85. The method as recited in claim 76, wherein the set of geometric constraints includes at least one maximum principle curvature that the desired shape of the network of curves must interpolate.

86. The method as recited in claim 76, wherein the set of geometric constraints includes at least one minimum principle curvature that the desired shape of the network of curves must interpolate.

87. The method as recited in claim 76, wherein the set of geometric constraints includes at least one pair of curves that meet with G¹ continuity at a node of the network of curves.

88. The method as recited in claim 76, wherein the set of geometric constraints includes at least one tangent direction that the desired shape of the network of curves must interpolate.

89. A method for producing a representation of a curved surface for display by a computer system, comprising:

specifying a desired shape of the curved surface utilizing a set of geometric constraints;

specifying a functional of the desired shape that is locally minimized and operative to measure a magnitude of variation in a curvature of the desired shape;

producing a representation of the curved surface based on the functional and the set of geometric constraints; and

displaying the representation of the curved surface via an output device to create a visual or physical embodiment of the curved surface.

90. The method as recited in claim 89, wherein the functional is an area integral of a sum of a square of an arc length derivative of a maximum principle curvature of the desired shape taken in a maximum principle direction of the desired shape and a square of an arc length derivative of a minimum principle curvature of the desired shape taken in a minimum principle direction of the desired shape.

91. The method as recited in claim 89, wherein the functional is made scale invariant by multiplying the functional by an area of the desired shape.

92. The method as recited in claim 89, wherein the set of geometric constraints includes at least one point that the desired shape of the curved surface must interpolate.

93. The method as recited in claim 89, wherein the set of geometric constraints includes at least one tangent plane that the desired shape of the curved surface must interpolate.

94. The method as recited in claim 89, wherein the set of geometric constraints includes at least one direction of principle curvature of the desired shape that the desired shape of the curved surface must interpolate.

95. The method as recited in claim 89, wherein the set of geometric constraints includes at least one maximum principle curvature of the desired shape that the desired shape of the curved surface must interpolate.

96. The method as recited in claim 89, wherein the set of geometric constraints includes at least one minimum principle curvature of the desired shape that the desired shape of the curved surface must interpolate.

97. The method as recited in claim 89, wherein the set of geometric constraints includes at least one continuous curve of tangent plane specification that the desired shape of the curved surface must interpolate.

98. The method as recited in claim 97, wherein the continuous curve of tangent plane specification further specifies a continuous surface normal curvature in a direction perpendicular to the curve of tangent plane specification that the desired shape of the curved surface must interpolate.

99. The method as recited in claim 89, wherein the set of geometric constraints includes at least one curve of G² discontinuity specification for the desired shape of the curved surface.

100. The method as recited in claims 89, wherein the set of geometric constraints includes at least one curve G¹ discontinuity specification for the desired shape of the curved surface.

101. The method as recited in claim 89, wherein the functional is made scale invariant by multiplying the functional by an area of the desired shape.