I need help for this question. Hidden surface removal.Hidden surface removal is

Question

I need help for this question. Hidden surface removal.Hidden surface removal is a problem in computer graphics that scarcely needs an introduction: when Woody is standing in front of Buzz you should be able to see Woody but not Buzz; when Buzz is standing in front of Woody, . . . well, you get the idea. The magic of hidden surface removal is that you can often compute things faster than your intuition suggests. Here’s a clean geometric example to illustrate a basic speed-up that can be achieved. You are given n non-vertical lines in the plane, labeled L1, ..., Ln, with the i th line specified by the equation y = aix + bi . We will make the assumption that no three of the lines all meet at a single point. We say line Li is uppermost at a given x-coordinate x0 if its y-coordinate at x0 is greater than the y-coordinates of all the other lines at x0 : aix0 + bi > ajx0 + bj for all j 6= i. We say line Li is visible if there is some x-coordinate at which it is uppermost—intuitively, some portion of it can be seen if you look down from “y = .” Give an algorithm that takes n lines as input, and in O(n log n) time returns all the visible ones and where they intersect. Figure 5.10 of the text gives an example

Explanation / Answer

1.
Start by sorting the edges in order of increasing slope. Notice that the first and last lines in this order will always be visible.
2.
If two lines are both visible, the region in which the line of smaller slope is uppermost lies to the left of the region in which the line of larger slope is uppermost.
3.
When you combine two sub-solutions, consider each intersection point and consider which sub-solution has the uppermost line at this point.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.