Curve clipping

1. Curve clipping

2. The bounding rectangle for a curved object can be used first to test for overlap with a rectangular clip window (we can use polygon clipping) X MAX , Y MAX X MIN , Y MAX X MAX , Y MIN X MIN , Y MIN Object

3. Case 1 If the bounding rectangle for the object is completely inside the window, we save the object. Clipping window Bounding rectangle

4. Case 2 If the rectangle is determined to be completely outside the window, we discard the object Object

5. Case 3 If the two regions overlap, we will need to solve the simultaneous line-curve equations to obtain the clipping intersection points.

6. finding intersection points by solving the curve and boundary equations simultaneously sometimes takes a long time. We have to consider special curves as circles and ellipses before solving the equations simultaneously.

7. Circle clipping Xc+R X LEFT -If X C + R < X LEFT Then the circle is discarded . -No need for bounding triangle x c Clipping window

8. Circle clipping cont.. If X C - R > X right Then the circle is discarded X right Xc -R X C R

9. Circle clipping cont.. Y top Yc -R If Y C - R >Y top Then the circle is discarded Clipping window

10. Circle clipping cont.. Y bottom Yc + R If Y C +R <Y bottom Then the circle is discarded

11. Circle clipping cont.. If all the four previous conditions are false then the circle is saved

12. Circle clipping cont.. Intersection conditions: With right edge: Xc+R> Xright With left edge: Xc-R< Xleft With top edge : Yc+R>Ytop With bottom edge: Yc -R<Ybottom

13. Circle clipping cont.. Getting intersection points : Example : The intersection with the right edge α Start (angle=0) First intersection angle= α Second intersection α X right X c 1- Simply Cos α = X right -X c /R 2- Get α 3- y=R sin α 4- the segment from angle 0 to angle α is discarded 5- the segment from angle α to angle 360- α is considered 6- the segment from angle 360- α to angle 360 is considered

14. Other techniques Clip individual point : for point plotted curves , may consume time if number of points is great. Curves approximated to poly lines: clip individual line segments , if segment is not small enough no accurate result , if it is small more than enough , it will be time consuming for linear segments

15. A Spline Curve : Any Composite curve formed with polynomial sections satisfying specified continuity conditions at the boundary of the pieces. Spline curve : definition

16. Specifying Splines

17. Example : Third order spline In order to assure C1 continuity  at two extremities, our functions must be of at least degree 3

18. 18 Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005 Convex Hull Property Bezier curves lie in the convex hull of their control points Hence, even though we do not interpolate all the data, we cannot be too far away p p 1 p 2 p 3 convex hull Bezier curve

19. B é zier Clipping Problem Given polynomial p with degree n Find all roots within an interval Algorithm B é zier representation Intersect the convex hull with t -axis Obtain a new interval

20. B é zier Clipping

21. B é zier Clipping

22. B é zier Clipping

23. B é zier Clipping

24. B é zier Clipping

25. The Approximated Roots A sequence of intervals that bound the root of p If the width of interval is smaller than the given tolerance, return the root (interval).

26. Convergence Rates A sequence of intervals that converge to the root: How fast does the sequence converge?

27. 2. Quadratic Clipping

28. Quadratic Clipping Idea Use quadratic bounds Motivation To improve the convergence rate

29. Quadratic Bounds Upper bound Lower bound

30. Quadratic Bounds But, how to compute the quadratic bounds efficiently?

31. Quadratic Bounds Approximated quadratic bounds Upper bound Lower bound Best quadratic approximant

32. Quadratic Clipping The same type of algorithm as B é zier clipping Convex hull  Quadratic bounds Find the best quadratic approximant q of p in L 2 norm Compute error bound of p and q Construct quadratic functions: upper bound M , lower bound m Compute roots of M and m

33. Quadratic Clipping

34. Quadratic Clipping

35. Quadratic Clipping

36. Quadratic Clipping

37. Quadratic Clipping

38. Quadratic Clipping

39. Quadratic Clipping