Unexpected steps in output of rasterize()

[catequalsgood]

Hi everyone,

I noticed that images generated by rasterize() do not always look exactly like I would expect them to look. I tried different settings but could never get rid of the issues entirely.
To demonstrate I used an X-shaped mesh (trimesh-test-cross.zip) and the code below.

import trimesh

mesh = trimesh.load('C:/trimesh-test-cross.stl', force='mesh')
slice = mesh.section(plane_origin=[0,0,0.5], plane_normal=[0,0,1])
slice_2D, to_3D = slice.to_planar(normal=[0,0,-1], check = True)

img = slice_2D.rasterize(pitch=[0.02, 0.02],
                         origin=[-2,-2],
                         resolution=[200,200],
                         fill=True, 
                         width=0)

img.save('C:/trimesh-bug-demo.png')

I scaled the image up by a factor of two to make it easier to see the steps I am talking about.

At first I thought it might just be the pixel grid and the edges of my mesh coinciding by chance. Looking at the image below (pixel grid on top of the edges) however shows that if one edge coincides with the corners of the pixels the other edge should not. The bottom right circle in the image above shows a step in both edges.

Using mesh.projected() changes the result but still shows some steps. The same goes for shifting the origin by half a pixel in one dimension.
The best workaround I have so far is rendering a much higher resolution and then scaling that image down without interpolation. Unfortunately my application requires high accuracy as well as high resolution so this approach might not work for long.

Is there anything else I have overlooked that might be worth a try?

(I am running trimesh 3.10.7 but noticed these issue even before the last update)

[mikedh]

Oh interesting, trimesh.path.raster.rasterize is just using Pillow.ImageDraw.polygon. It does seem like if it's exactly going through a corner the "filled-or-not-filled" logic would be arbitrary? Could you take multiple raster results with origin moved around inside a single pixel and then combine the images to get a more conservative fill rule?

[mikedh]

Out of curiosity I think I tracked down the actual drawing algorithm, it's buried here:

https://github.com/python-pillow/Pillow/blob/c58d2817bc891c26e6b8098b8909c0eb2e7ce61b/src/libImaging/Draw.c#L744-L814

[mikedh]

Also this may be slightly effected by how we convert to pixel coordinates, but adding a round only makes the effect symmetric (which is probably an improvement):

-    discrete = [((i - origin) / pitch).astype(np.int64)
+    discrete = [((i - origin) / pitch).round().astype(np.int64)
                 for i in path.discrete]

[catequalsgood]

After some more testing (sorry for the long delay) I think the behavior described in my initial post is completely explained by the use of Pillow.ImageDraw.polygon. The four corners at the center of the X are on pixel edges and therefore effectively all move half a pixel when converting to pixel coordinates. The edge drawn by Pillow is then not 45° anymore and we get a step somewhere along the drawn edge.
However, even after shifting the origin by one tenth of a pixel and making sure there are no vertices on pixel edges the result still seems wrong.

But this also just seems to be a result of conversion to pixel coordinates. There are still instances in which the starting point of a drawn edge is in a pixel to the left of the 45° slope and the endpoint in a pixel to the right of it (and vice versa), resulting in a step.

I do not think rounding is necessary here. According to the documentation of Pillow the origin of the coordinate system is in the top left corner of the pixel. The image you posted seems to be equivalent to shifting the origin by half a pixel.
For my use case I would prefer a conservative "any pixel containing part of the mesh is filled"-rule to the way rasterize() currently works but Pillow does not seem to offer any way to do that.
One workaround to get that conservative rule is to increase the mesh resolution so that any pixel containing a mesh edge also (likely) contains at least one vertex since pillow always fills corners of drawn polygons. This is obviously not really feasible for all meshes.

I think this issue can be closed. If anything this should probably be a feature request for Pillow.
Thanks for your help and your work on trimesh!

[mikedh]

No worries! Yeah I think this is on pillow, perhaps this issue. Microsoft also has a nice bit on pixel-fill rules that was kind of interesting.