Brushstroke envelopes

• US 6,067,094 A
• Filed: 04/07/1998
• Issued: 05/23/2000
• Est. Priority Date: 04/07/1998
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Schuster, Michael D.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US09/057,011
• Time in Patent Office: 777 Days
• Field of Search: 345/441, 345/442, 345/150, 345/153
• US Class Current: 345/441
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77

Abstract

An envelope enclosing brush instances corresponding to transformations of a brush at points along a trajectory is generated. Points on the brush instances that are furthest from the trajectory are identified, and the identified points are connected based on the trajectory and the relative orientations of the brush instances.

Claims

1. A computer-implemented method for generating an envelope enclosing brush instances corresponding to transformations of a brush at points along a trajectory, the method comprising:

identifying points on the brush instances that are furthest from the trajectory; and

connecting the identified points based on the trajectory and relative orientations of candidate envelope segments formed by sequentially connecting the identified points.

2. The method of claim 1, wherein the identified points comprise a sequence of ordered points, and wherein connecting the identified points comprises:

sequentially connecting points in the sequence if two consecutive points in the sequence comprise the same point.

3. The method of claim 1, wherein the identified points comprise a sequence of ordered points, and wherein connecting the identified points comprises:

sequentially connecting points in the sequence if the line segments do not have similar relative orientations; and

otherwise, sequentially connecting points in the sequence and at least one point on the brush instances.

4. The method of claim 1, wherein transformations comprise affine transformations.

5. The method of claim 1, wherein the brush comprises a sequence of connected line segments forming a convex polygon.

6. The method of claim 1, further comprising:

identifying breakpoints in the sequence as points on candidate envelope segments which do not have similar relative orientations; and

prior to the connecting step, eliminating breakpoints that are within less than a threshold distance of a candidate envelope segment.

7. The method of claim 1, further comprising:

determining slopes of line segments formed by connecting the identified points.

19. The method of claim 3, wherein sequentially connecting points in the sequence and at least one point on the brush instances comprises:

sequentially connecting points in the sequence and points on the brush instances that are between points in the sequence.

20. The method of claim 3, wherein candidate envelope segments do not have similar relative orientations if an angle between vectors formed by consecutive points in the sequence is not less than about zero degrees.

21. The method of claim 20, wherein the angle between the vectors is measured as the product of the sign of the cross product of the vectors, and the arccosine of the quotient of the dot product of the vectors and the product of the magnitudes of the vectors.

8. A computer-implemented method for generating an envelope of a brush at points along a trajectory, the method comprising:

applying a transformation having at least two parameters which vary independently of each other to the brush at the points along the trajectory to develop brush instances;

identifying points on the brush instances that are furthest from the trajectory; and

connecting the identified points based on the trajectory and relative orientations of candidate envelope segments formed by sequentially connecting the identified points.

9. The method of claim 8, wherein a parameter of the transformation comprises a horizontal scale.

10. The method of claim 8, wherein a parameter of the transformation comprises a vertical scale.

11. The method of claim 8, wherein a parameter of the transformation comprises a horizontal offset.

12. The method of claim 8, wherein a parameter of the transformation comprises a vertical offset.

13. The method of claim 8, wherein a parameter of the transformation comprises a horizontal rotation.

14. The method of claim 8, wherein a parameter of the transformation comprises a vertical rotation.

15. The method of claim 8, wherein candidate envelope segments comprise line segments.

16. The method of claim 8, wherein identifying points comprises:

identifying left-hand points that are furthest to the left of the trajectory and identifying right-hand points that are furthest to the right of the trajectory; and

connecting the identified points comprises;

connecting the left-hand points and connecting the right-hand points.

17. The method of claim 8, wherein the trajectory comprises a contiguous sequence of line segments and identifying points on the brush instances that are furthest from the trajectory comprises:

identifying, for line segments in the trajectory, brush instances containing the line segments and pairs of points on the identified brush instances that are furthest from the sections of the line segments that are within the identified brush instances.

18. The method of claim 17, further comprising:

for each pair of points, connecting the pair of points to form a connecting line segment;

identifying a new pair of points on the identified brush instances that are furthest from the connecting line segment;

if either of the new pairs of points is different from the pair of points, connecting the new pair of points to form a connecting line segment and identifying a second new pair of points.

22. A computer program tangibly stored on a computer-readable medium and operable to cause a computer to generate an envelope enclosing brush instances corresponding to transformations of a brush at points along a trajectory, comprising instructions to:

identify points on the brush instances that are furthest from the trajectory; and

connect the identified points based on the trajectory and relative orientations of candidate envelope segments formed by sequentially connecting the identified points.

23. The computer program of claim 22, wherein the identified points comprise a sequence of ordered points, and wherein instructions to connect the identified points comprise:

instructions to sequentially connect points in the sequence if two consecutive points in the sequence comprise the same point.

24. The computer program of claim 22, wherein the identified points comprise a sequence of ordered points, and wherein instructions to connect the identified points comprises:

instructions to sequentially connect points in the sequence if the brush instances do not have similar relative orientations; and

instructions to sequentially connecting points in the sequence and at least one point on the brush instances if the brush instances have similar relative orientations.

25. The computer program of claim 22, wherein transformations comprise affine transformations.

26. The computer program of claim 22, wherein the brush comprises a sequence of connected line segments forming a convex polygon.

27. The computer program of claim 22, further comprising instructions to:

identify breakpoints in the sequence as points on candidate envelope segments which do not have similar relative orientations; and

eliminate breakpoints that are within less than a threshold distance of a candidate envelope segment.

28. The computer program of claim 22, further comprising instructions to:

determine slopes of line segments formed by connecting the identified points.

29. A computer program tangibly stored on a computer-readable medium and operable to cause a computer to generate an envelope of a brush at points along a trajectory, comprising instructions to:

apply a transformation having at least two parameters which vary independently of each other to the brush at the points along the trajectory to develop brush instances;

identify points on the brush instances that are furthest from the trajectory; and

connect the identified points based on the trajectory and the relative orientations of the brush instances.

30. The computer program of claim 29, wherein candidate envelope segments comprise line segments.

31. The computer program of claim 29, wherein instructions to identify points comprises instructions to:

identify left-hand points that are furthest to the left of the trajectory and to identify right-hand points that are furthest to the right of the trajectory; and

instructions to;

connect the left-hand points and connect the right-hand points.

32. The computer program of claim 29, wherein the trajectory comprises a contiguous sequence of line segments and instructions to identify points on the brush instances that are furthest from the trajectory comprise instructions to:

identify, for line segments in the trajectory, brush instances containing the line segments and pairs of points on the identified brush instances that are furthest from the endpoints of the line segments.

33. The computer program of claim 32, wherein instructions to sequentially connect points in the sequence and at least one point on the brush instances comprise instructions to:

sequentially connect points in the sequence and points on the brush instances that are between points in the sequence.

34. The computer program of claim 32, wherein candidate envelope segments do not have similar relative orientations if an angle between vectors formed by consecutive points in the sequence is not less than zero degrees.

35. The computer program of claim 34, wherein the angle between the vectors is measured as the product of the sign of the cross product of the vectors, and the arccosine of the quotient of the dot product of the vectors and the product of the magnitudes of the vectors.

36. A system, comprising:

a computer having a computer-readable memory;

an input device for developing input signals to the computer representing a trajectory traced by a user;

a computer program residing in the computer-readable memory for generating an envelope enclosing brush instances corresponding to transformations of a brush at points along the trajectory, comprising instructions to identify points on the brush instances that are furthest from the trajectory, and to connect the identified points based on the trajectory and the relative orientations of the brush instances; and

an output device for displaying a representation of the envelope.