Week 2 recap - Aseprite's pixel perfect

Monday, 10 June 2024 | Ken Lo

Hi, it's week 2 and my last scheduled week for research. I spent this week looking over more of Krita's code base and pixel-perfect algorithm. There was a large focus on looking at examples of how pixel-perfect is achieved (specifically in Aseprite). Down below are important code snippets from Aseprite's pixel-perfect implementation and some explanation.

static void pixelPerfectLine(int x, int y, PPData* data) {  gfx::Point newPoint(x, y);  if (data->pts.empty() || data->pts[data->pts.size()-1] != newPoint) {    data->pts.push_back(newPoint);  }}

Aseprite uses this static function as a callback to ensure that each new point in a line is unique and does not overlap with a previous point. It checks if "newPoint" is already the last point in the points array data->pts, and if it isn't it adds newPoint to the array. This lays the foundation for the tracking (as mentioned in the last blog) of points (last drawn pixel, current pixel, and waiting pixel).

 void joinPoints(ToolLoop* loop, const Points& points) OVERRIDE {    if (points.size() == 0)      return;    else if (m_pts.empty() && points.size() == 1) {      m_pts = points;    }    else {      PPData data(m_pts, loop);      for (size_t c=0; c+1<points.size(); ++c) {        int x1 = points[c].x;        int y1 = points[c].y;        int x2 = points[c+1].x;        int y2 = points[c+1].y;        algo_line(x1, y1, x2, y2, (void*)&data, (AlgoPixel)&IntertwineAsPixelPerfect::pixelPerfectLine);      }    }

Here it checks for an empty input (exits) and then it checks for the case where there are only one point and 'm_pts', the internal points list, is empty, in which case points are assigned to 'm_pts'. Then it creates a PPData structure to hold references to 'm_pts' and 'loop'. The loop below basically iterates through consecutive pairs and then draws lines between each pair of points with a function pointer to pixelPerfectLine.

for (size_t c = 0; c < m_pts.size(); ++c) {  if (c > 0 && c + 1 < m_pts.size()    && (m_pts[c - 1].x == m_pts[c].x || m_pts[c - 1].y == m_pts[c].y)    && (m_pts[c + 1].x == m_pts[c].x || m_pts[c + 1].y == m_pts[c].y)    && m_pts[c - 1].x != m_pts[c + 1].x    && m_pts[c - 1].y != m_pts[c + 1].y) {    ++c;  }  doPointshapePoint(m_pts[c].x, m_pts[c].y, loop);}

Here's where the algorithm implements pixel-perfect. This loop iterates over all points in 'm_pts' and ignores certain points. There is a conditional check designed to skip over points that would visually form a corner in an L-like shape. While the current point is not the first or the last point in the vector, m_pts[c - 1].x == m_pts[c].x || m_pts[c - 1].y == m_pts[c].y checks if the previous point shares either the same x or y coordinate with the current point, and subsequently m_pts[c+1].x == m_pts[c].x || m_pts[c+1].y == m_pts[c].y checks if the next point shares either the same x or y coordinate with the current point. Then the rest of the code makes sure that the previous and next points do not share the x and y coordinates. Assuming all of the conditions are met c is incremented, basically skipping over the next point in the iteration. In practice, this code should detect a change in direction between the previous and next points (i.e, they do not lie on the same straight line but instead make a bend) and that the current point lies between two points that are aligned either vertically or horizontally but not diagonally.

Assuming Krita's drawing system isn't drastically different from how Aseprite's is implemented, we can assume a similar implementation where we track this list of points, along with pair adjacency and directions of points.