Graphical Algorithms: Sutherland-Hodgman Clipping Algorithm - what happens when two outer vertices intersect a clipping region?
The Sutherland-Hodgman algorithm for cropping polygons explains 4 rules:
- If both vertices are inside the clipping region, keep the second
- If the first vertex is inside and the second is outside - compute the intersection with the clipping region border and keep it
- If the first vertex is outside and the second is inside - calculate the intersection with the clipping region border and keep it, and also keep the second vertex
- If both vertices are outside - save nothing
With this explanation, what will it do when the line formed by the two vertices crosses the clipping region like in the picture below?
If I go through the steps of the algorithm, I will not have any vertices at all ... Is such a case not considered? Maybe I should pre-calculate all the intersection areas and use them too?
source to share
I finally found the answer myself - I will share it with anyone who loves to know ...
You can see a description of the correct algorithm here: https://www.youtube.com/watch?v=Euuw72Ymu0M
It is incorrect , described in a lot of tutorials , to have each vertex treated as inside / outside the clipping region and then apply the rules as described in the question above.
the correct algorithm is to iterate over all the edges of the clipping region . Rather than considering the vertex inside / outside the clipping region - the right thing to do is to consider the vertex as being on the inside / outside of the particular edge we are iterating on.This means that, for example, for the example image in the question - the left edge of the clipping region will treat the top-right corner of the blue rectangle as being inside - because although it is outside the clipping region, it is on the inside of the left edge. For example, the top left corner will be considered outside .
If the algorithm is executed in 2D, we have 4 edges of the clipping region. For example, we first apply the algorithm on the left edge - then we use its output to run the algorithm on the right edge, same for the top edge and bottom edge. The final answer will be the exit of the latter.
those. If we used Left-> Right-> Up-> Bottom, the end result is a list of vertices displayed as the bottom edge.
You can try to run this algorithm by following the rules described in the question for each edge - you will see that the final polygon will be accurately clipped.
source to share