undefined | Better HN

0 pointsexDM699y ago0 comments

> I think it is much more elegant than the traditional point-in-poly ray-cast rasterization technique.

This is pretty similar to the point-in-poly raycasting (this is especially clear if you use the stencil buffer, but for some reason the author actively avoids that). You might also see some similarities with stencil shadow volumes (as seen in Doom 3).

There's two tricks used here: stencil-then-cover for the "bulk" of the shape and the Loop-Blinn method for doing quadratic Bezier curves in a triangle. You can find plenty of resources on both.

0 comments

drudru119y ago

Agreed, but my cg education (many moons ago), usually covered point in poly with a specific section of code to do ray intersection with segments. None that I can recall used the stencil trick, which is so much more clever and simple than solving line equations. I am just wondering... who came up with that first?

I looked for the original Warnock paper online, but it is behind the ACM paywall. That would at least tell me if they knew of that in the mid 80's.

I will check out the Doom 3 stuff. I had that on my reading list from a while back.

Thanks for your answer.

exDM69OP9y ago

You should understand that conceptually stencil-then-cover is the point-in-poly algorithm using line segment intersections. It's just that the GPU triangle rasterizer solves the line equations (or half plane equations) and accumulates the per-pixel result in the stencil buffer.

The Doom 3 shadow volume algorithm is just the same, extended into 3d and using a little bit of depth buffer and front/back face culling to make some edge cases work (self-shadowing, shadow volume caps).

If you want to go read the original paper (please share a link!), you can circumvent the paywall with sci-hub.io if you don't mind a little piracy.

j / k navigate · click thread line to collapse