1.这个裁剪算法可用于当3d光栅化完毕需要将图形渲染到屏幕上方时所作的裁剪 也可以是类似Box2d在多边形碰撞深度计算的时候所作的运算

Polygon SutherlandHodgman( const Polygon startingPolygon, Plane[] clippingPlanes )
{
  Polygon output = startingPolygon
  for each Plane clippingPlane in clippingPlanes
    input = output
    output.Clear( )
    Vec2 startingPoint = input.Last( )
    for each Vec2 endPoint in input
      if startingPoint and endPoint in front of clippingPlane
        out.push( endPoint )
      else if startingPoint in front and endPoint behind clippingPlane
        out.push( Intersection( clippingPlane, startingPoint, endPoint ) )
      else if startingPoint and endPoint behind clippingPlane
        out.push( Intersection( clippingPlane, startingPoint, endPoint ) )
        out.push( endPoint )
      endPoint = startingPoint
  return output
}

其本质就是遍历需要被裁减的多边形的所有的边 每边与裁剪多边形的所有边进行位置判断

// InFront = plane.Distance( point ) > 0.0f
// Behind  = plane.Distance( point ) < 0.0f

Vec2 p1, p2;
ClipPlane plane;

case p1 InFront and p2 InFront
  push p2
case p1 InFront and p2 Behind
  push intersection
case p1 Behind and p2 InFront
  push intersection
  push p2

上方代码的含义基本为下图

1.当边的方向进入裁剪区域 添加P与P1

2.当边的方向是背离裁剪区域 只添加P

3.倘若全部都在背离方向上 不添加点

4.整个边都在内部 只添加P1

这里P是p0->p1与裁剪边的交接点 (一元二次的直线方程可以计算出)

下方为一个裁剪的案例

详情见