Polygon clipping#

The Sutherland-Hodgman algorithm is used to clip polygons to the edges of the visible region. Given an input list of vertices that define a polygon (e.g., a row of the face array), the Sutherland-Hodgman algorithm loops through each vertex of the polygon and if the current vertex is inside the visible region then we check whether the previous vertex is also inside. If it is the line joining the two points is entirely inside and we add both endpoints to an output list defining the clipped polygon and move onto the next vertex in the input list. If the previous vertex is not inside the visible region we clip the line using the Cyrus-Beck algorithm and add the clipped point and the current endpoint to the output list. If the current point is not inside the visible region but the previous one is, we clip the line to the edge and add the clipped point to the output list. Once all vertices in the input list have been considered the output list contains the information for the clipped polygon.

Algorithm 2 (Sutherland-Hodgman algorithm)

Inputs An \(inputlist\) containing the vertices of a polygon and a visible region.

Outputs An \(outputlist\) containing the vertices of the clipped polygon.

\(outputlist \gets inputlist\)
For each edge of the visible region
- \(inputlist \gets outputlist\)
- \(outputlist \gets \emptyset\)
- \(previous \gets inputlist(end)\)
- For \(i = 1, \ldots, \operatorname{length}(inputlist)\)
  - \(current \gets inputlist(i)\)
  - If \(current\) is in front of the edge
    - If \(previous\) is behind the edge
      - Add intersection point to \(outputlist\)
    - Add \(current\) to \(outputlist\)
  - Else if \(previous\) is in front of the edge
    - Add intersection point to \(outputlist\)
  - \(previous \gets current\)
Return \(outputlist\)

Example 34

Use the Sutherland-Hodgman algorithm to clip the polygon defined by the vertices \(\mathbf{v}_1\) to \(\mathbf{v}_4\) to the visible region shown below.

../_images/sutherland_hodgman_example_1.svg

MATLAB code#

The MATLAB function clipped_space(V, F) defined below clips the screen space defined by the vertex and face matrices V and F using the Sutherland-Hodgman algorithm.

function [Vclip, Fclip] = clipped_space(V, F)

% Define cube region points and normal vectors
P = [ -1, -1,  1,  1, -1,  1 ; 
      -1, -1,  1,  1, -1,  1 ; 
       1,  1, -1, -1,  1, -1 ];
n = [  0,  0, -1,  0,  1,  0 ;  
       1,  0,  0,  0,  0, -1 ; 
       0, -1,  0,  1,  0,  0 ];

% Loop through the polygons in F
Vclip = V;   
Fclip = [];
for poly = 1 : size(F, 1)

    % Loop through the edges of the clipping cube
    output = F(poly, :);
    for edge = 1 : size(P,2)
        input = output;
        output = [];
        prev = input(end);

        for i = 1 : length(input)
            curr = input(i);
            dcurr = dot(Vclip(1:3,curr) - P(:,edge), n(:,edge));
            dprev = dot(Vclip(1:3,prev) - P(:,edge), n(:,edge));

            % Check if polygon edge crosses clipping cube edge
            if dcurr > 0 
                % Current point is inside
                if dprev < 0
                     % Previous point is outside so add intersection to output list
                    t = dprev / (dprev - dcurr);
                    int = [Vclip(1:3,prev) + t * (Vclip(1:3,curr) - Vclip(1:3,prev)) ; 1];
                    Vclip = [Vclip, int];
                    output = [output, size(Vclip, 2)];
                end

                % Add current point to output list
                output = [output, curr];

            elseif dprev > 0
                % Current point is outside so add intersection to output list
                t = dprev / (dprev - dcurr);
                int = [Vclip(1:3,prev) + t * (Vclip(1:3,curr) - Vclip(1:3,prev)) ; 1];
                Vclip = [Vclip, int];
                output = [output, size(Vclip, 2)];
            end

            % Update previous
            prev = curr;
        end
    end

    % If outputlist is non-empty add to Fclipped
    if ~isempty(output)
        if isempty(Fclip)
            Fclip = output;
            continue
        end

        diff = length(output) - size(Fclip,2);
        if diff > 0
            % Pad out Fclip
            Fclip = [Fclip, repmat(Fclip(:,end), 1, diff)];
        elseif diff < 0
            % Pad out outputlist
            output = [output, repmat(output(end), 1, -diff)];
        end

        % Add outputlist to Fclipped
        Fclip = [Fclip ; output];
    end
end

end

The affect of applying the Sutherland-Hodgman algorithm to the screen space from Example 32 is shown in Fig. 75. Note that all of the objects have been clipped to the edges of the unit cube that defines the visible region. A view looking down the \(z\)-axis is shown in Fig. 76.

../_images/clipped_space_example_2.png — Fig. 75 Plot of the clipped screen space viewed from the side.#

../_images/clipped_space_example_3.png — Fig. 76 Plot of the clipped screen space viewed looking down the \(z\)-axis.#

Computer Graphics Lecture Notes

Polygon clipping

Contents

Polygon clipping#

MATLAB code#