No Sharp Corners

Pancakes

I recently wrote an algorithm to make rounded rectangles for a grid with “holes”. The goal was to ensure that all the convex corners of the grid sections were rounded. I looked at existing implementations in softwares that I use daily, the most used are code editors. One of my favorite text editors Zed, renders text selections with beautifully rounded convex and concave corners.

I 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. The 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. Here are the directions: [⇐, ⇖, ⇑, ⇗, ⇒, ⇘, ⇓, ⇙] For 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. This 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. The final directions array: [⇐, ⇖, ⇑, ⇗, ⇒, ⇘, ⇓, ⇙, ⇐] Now I can implement a sliding window of width three on top of this array which can account for all the corners.

Who drew the short stick?

A corner that touches three empty cells is rounded. Vice-versa an empty cell that touches three filled cells, is rounded. As I'm only concerned with the external rounding, I ended up ignoring the empty cell case.

Let’s look at an example:

Evaluating the cell marked with `, xs are filled, and _s are empty.

By looking at the rectangle I can deduce that should have the left top corner rounded and nothing else.

Dry 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.

As 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.

Let’s look at a more complicated example:

For 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.

Expected Outcome:

Let's look at the cell marked with `, starting with the top left corner:

As the three relevant adjacent cells are out of bounds, I can mark the corner rounded.

Let’s look at the top right corner:

The first two adjacent cells are out-of-bounds and hence considered empty. The last one is actually empty, I can mark that corner rounded.

Let's look at the bottom right corner.

As the cells marked 1 and 3 are empty but cell 2 is not, this corner can’t be rounded.

Last corner:

As all the relevant cells are either empty or out of bounds, this corner can be marked as rounded similar to the right top corner.

Outcome:

In practice

Q: Can this use a compute shader to find the solution much faster?

I think so.