Warnock's Algorithm

• A divide and conquer algorithm

  Warnock(PolyList PL, ViewPort VP)
  If ( PL simple in VP) then
      Draw PL in VP
  else
      Split VP vertically and horizontally into VP1,VP2,VP3,VP4
      Warnock(PL in VP1, VP1)
      Warnock(PL in VP2, VP2)
      Warnock(PL in VP3, VP3)
      Warnock(PL in VP4, VP4)
  end

• What does ``simple'' mean?
  • No more than one polygon in viewport

    Scan convert polygon clipped to viewport

  • Viewport only 1 pixel in size

    Shade pixel based on closest polygon in the pixel

• Runtime:
  • p: number of pixels
  • n: number of polygons