Rasterization Bastardization
I have a couple lazyweb questions, this time concerning some topics in computer graphics. For, uh, my own edification:
- Rasterizing a circle (a disc). Say we want to take a circle, represented by a point (x, y) and a radius r, and produce a grayscale bitmap of this circle. This circle has some real, idealized size, on the order of millimeters (though, some of them a lot smaller), and our synthetic camera will have a specific length per pixel that it’s capturing, approximately; call the length per pixel l. My solution was to consider each pixel a l by l square, located where the pixel would be, and then I first see if it intersects the circle at all (pretty easy to compute), and if it’s completely inside, set the pixel to full white. If it’s fully outside the circle, set the pixel to full black. Otherwise, compute the area of intersection between the rectangle and the circle (which, actually seems to be really computationally expensive), and divide that by the area of the pixel. Set the pixel to full white times the quotient, so the pixel will be some percent of white, depending on how much the pixel overlaps the circle.
This is pretty slow, if we’re working with large circles compared to pixels; for small circles, around the size of a few pixels to a few dozen pixels, I just find the bounding box of the circle, expand that to encompass whole pixels, and do the same rasterization per pixel, but just in that box. Is there any way to generally speed this up? Is there a fast way to get the intersection of a circle and a square?
(I want this to be camera-accurate, not an approximation, of which there are a lot of ways to do that. I’d like to be as camera-accurate as possible, but don’t like how slow it is now.)
- Computing projective transforms. Now, I also have a projective transform that I’m applying to images, and this is how I’m doing it:
- First, compute how large a new image we will need to contain the entire transformed image, which will just be the bounding box of the polygon
P = { T(-w/2, -h/2), T(w/2, -h/2), T(w/2, h/2), T(-w/2, h/2) }, whereTapplies the transform. The width and height of this bounding box is the new image width and height, and the minimum corner of this bounding box will be an offset we’ll use to map pixels into our new image. - Now, for each pixel in the source image, compute the projected pixel, which will be another polygon:
P = { T(x, y), T(x+1, y), T(x+1, y+1), T(x, y+1) }. We’ll look at the bounding box of this polygon, expanded to encompass whole pixels, and then for each of these pixels, we compute its intersection with the projected pixel from the source image (this — computing the area of intersection of two polygons — turns out to be pretty hairy too). The value of the pixel in the new image is then this area of overlap times full white. - Finally, we add in this value to the pixel in the new image — addition because that pixel in the new image might overlap multiple pixels in the source image, so we have to account for that; all pixels start out as black.
This works surprisingly well, except for (1) it’s insanely slow, and (2) it seems like rotations along the X or Y axis are hugely exaggerated. For example, this is a square that should be rotated along X and Y by only 0.001 radians:
It gets much worse as the angles increase, so any rotation at all borks the entire image. Rotation in Z looks perfect. My suspicion is that the issue is Z: we’re essentially right on the image plane when we begin, and edges that move “toward” us come way too close, and likewise edges that move “away” from us go way too far.
Are there any optimizations here? One example would be computing the intersection of two quadrilaterals, or maybe better, a quadrilateral and a square, but I haven’t figured out how to do that yet. Also, any clue as to why a rotation in X or Y is so exaggerated?
- First, compute how large a new image we will need to contain the entire transformed image, which will just be the bounding box of the polygon
- Transformations at raster time. One speedup (and improvement in image quality) was to do the transformation at raster time, so when I’m doing the simple rasterization I described above, of features like circles, can I apply the projective transform then?
One thing I think might do this, but haven’t gotten working yet, is to first rasterize a feature in the shape plane, and then transform that rasterization to the image plane. All we need in this case is a sufficient resolution rasterized in the shape plane, and transforming that little rasterization (which might span a single pixel in the image plane) into a rasterization for the final image.
Are there any other solutions for this? I assume you could do this by transforming the shape being rasterized by the transform, but the geometry here seems like it would get a whole lot more complicated; just measuring the overlap of a rectangle and a circle, or two polygons, is difficult enough already.
Loading...