{
  "path": "/posts/no-sharp-corners",
  "site": "at://did:plc:pans3xjam4khj7y54dx7gtfg/site.standard.publication/3mdqevmg6w32c",
  "$type": "site.standard.document",
  "title": "No Sharp Corners",
  "description": "An algorithm for rounding convex corners and making grids look posh AF.",
  "publishedAt": "2024-08-25T18:58:05.000Z",
  "textContent": "<a href=\"/pancakes\" target=\"_blank\" rel=\"noopener noreferrer\">Pancakes</a>\n\nI recently wrote an algorithm to make rounded rectangles for a grid with “holes”.\nThe goal was to ensure that all the convex corners of the grid sections were rounded.\nI looked at existing implementations in softwares that I use daily, the most used are code editors.\nOne of my favorite text editors Zed, renders text selections with beautifully rounded convex and concave corners.\n\nI couldn’t find a way to add external rounded corners without adding extra blocks at the beginning and end of each row, so decided to focus on internal corners, which led me to a somewhat elegant solution.\nThe algorithm requires that I evaluate for each cell it’s neighboring cells, starting with the one to its left, and going clockwise at 45 degree increments.\nHere are the directions: [⇐, ⇖, ⇑, ⇗, ⇒, ⇘, ⇓, ⇙]\nFor each corner I had to evaluate the three adjacent cells that it touches. Evaluating each corner cell clockwise staring from left-top makes it awkward as the last corner (left-bottom) requires that I look at the first direction (left) again.\nThis would require array index shenanigans and I wanted to avoid that for the sake of obsession. However, if I duplicate the first direction at the end, it simplifies the code.\nThe final directions array: [⇐, ⇖, ⇑, ⇗, ⇒, ⇘, ⇓, ⇙, ⇐]\nNow I can implement a sliding window of width three on top of this array which can account for all the corners.\n\nWho drew the short stick?\n\nA corner that touches three empty cells is rounded.\nVice-versa an empty cell that touches three filled cells, is rounded.\nAs I'm only concerned with the external rounding, I ended up ignoring the empty cell case.\n\nLet’s look at an example:\n\nEvaluating the cell marked with `, xs are filled, and _s are empty.\n\nBy looking at the rectangle I can deduce that  should have the left top corner rounded and nothing else.\n\nDry running the algorithm for the top left corner, I start by checking the cell to the left, then the one to the left and above, and then finally the one above.\n\nAs I was evaluating a filled cell, and all the neighboring cells for the left top corner are empty, I can mark the corner as rounded.\n\nLet’s look at a more complicated example:\n\nFor ths particular case, all the corners except the corner that’s common between the large and the small rectangle should be rounded. The clockwise sweeping algorithm is a generalized solution and works fine for this case.\n\nExpected Outcome:\n\nLet's look at the cell marked with `, starting with the top left corner:\n\nAs the three relevant adjacent cells are out of bounds, I can mark the corner rounded.\n\nLet’s look at the top right corner:\n\nThe first two adjacent cells are out-of-bounds and hence considered empty.\nThe last one is actually empty, I can mark that corner rounded.\n\nLet's look at the bottom right corner.\n\nAs the cells marked 1 and 3 are empty but cell 2 is not, this corner can’t be rounded.\n\nLast corner:\n\nAs all the relevant cells are either empty or out of bounds, this corner can be marked as rounded similar to the right top corner.\n\nOutcome:\n\nIn practice\n\nQ: Can this use a compute shader to find the solution much faster?\n\nI think so.",
  "canonicalUrl": "https://afloat.boats/posts/no-sharp-corners"
}