An encoding engine encodes a video sequence to provide optimal quality for a given bitrate. The encoding engine cuts the video sequence into a collection of shot sequences. Each shot sequence includes video frames captured from a particular capture point. The encoding engine resamples each shot sequence across a range of different resolutions, encodes each resampled sequence with a range of quality parameters, and then upsamples each encoded sequence to the original resolution of the video sequence. For each upsampled sequence, the encoding engine computes a quality metric and generates a data point that includes the quality metric and the resample resolution. The encoding engine collects all such data points and then computes the convex hull of the resultant data set. Based on all convex hulls across all shot sequences, the encoding engine determines an optimal collection of shot sequences for a range of bitrates.