Central to any sampling-based renderer is the point in polygon test or, in the case of Reyes, point in micropolygon. In layman’s terms: put a sticky note on the wall, throw a dart at it, and then determine if the dart hit the note.
First of all, an important message for other RenderMan developers: micropolygons may be concave. If you don’t believe me, just think of what a displacement shader can do to micropolygons. They can be twisted and shredded six ways from Sunday. We don’t even need a displacement shader. Suppose we wanted to create an approximation of the Star Trek logo. The following RIB file uses a large shading rate to make a bilinear patch out of a single micropolygon:
Format 400 400 -1
Display "trek.tif" "file" "rgb"
Projection "perspective" "fov" [45]
WorldBegin
Surface "constant"
Translate 0 0 2.5
ShadingInterpolation "smooth"
ShadingRate 320000
Patch "bilinear"
"P" [0 1 0 .6 -.9 0 -.6 -1 0 .15.-.25 0]
"Cs" [1 1 1 0 0 1 0 0 1 0 0 1]
WorldEndWe expect to see something like this:
Besides RenderDotC, I have seven other RenderMan-compliant renderers installed on my development system. You know how many of them rendered a concave micropolygon? One. Just one out of seven. I’m not going to name names but one of them produced this:
It’s easy to see what’s going on here. The micropolygon was assumed to be convex and only points that passed the “inside” test for all four edges were rendered. It’s not much harder to write a function that handles concave micropolygons. Wikipedia’s article on point in polygon offers two suggestions: ray casting or winding number. The Wikipedia article mentions a problem with the ray casting algorithm when a ray passes exactly through a polygon vertex. For two different solutions to that problem, see the article “Fractional Invisibility” in Jim Blinn’s Corner: A Trip Down the Graphics Pipeline and Eric Haines’ section of An Introduction to Ray Tracing.
My original goal of rewriting my point in micropolygon test was to optimize it for the 21st century. You see my old one was “branchy” (i.e. full of if-else statements) which worked fine in the 1990’s but was running out of steam. I came up with a tight solution but soon realized that there was another boundary condition: How do you handle a sample that falls on the border between two micropolygons? My old sampler counted it as a hit on both micropolygons and let the resolver weed out the duplicate later. We can do better than that.
I arbitrarily decided that a sample on the border belongs to the micropolygon on the right. This is consistent with the concept of the half open interval [0, 1). A scanline through a polygon includes all points starting with the left edge up to (but not including) the right edge.
If the edge is horizontal then the sample belongs to the lower micropolygon (in RenderMan’s raster coordinates, +y is down). My new sampler handles all of these special cases and still runs about 25% faster than the old one.