Jump to content
  • Advertisement
Sign in to follow this  
Numsgil

Straight skeleton and offset polygon

This topic is 2348 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a 2D graphics engine using Shader Model 3 to draw the primitives (lines, circles, polygons, etc.)

I want to be able to draw polygons with an "interior" region of one color and an "exterior" region of another color. (Basically drawing a border around a polygon). So basically you could imagine drawing the polygon once, then shrinking it, and drawing it again in a different color. Basically what this Stack Overflow thread is talking about. In my case, however, I'd like the border thickness to be a constant thickness in pixels. So as you zoom in/out the thickness of the border will change. And ideally I don't want to perform any extra CPU-side computation to do this. Which means doing it in the pixel shader by testing if a given pixel is inside the border or the interior of the polygon.

I already have a triangulation algorithm that works using ear-clipping. I'm trying to figure out a way (or if there is a way) to get a pixel-in-the-interior-but-not-the-border test in the pixel shader using essentially only local information from the polygon's vertices (plus maybe neighbor information). Right now I'm basically doing a series of half-plane checks using the polygon edges on either side of the vertices. So I have a triangle with 3 vertices from the polygon, and I pass information on those 3 vertices' and their neighbors into the shader and construct the half planes from that. This seems to work for convex polygons, but for non-convex polygons I'm getting some artifacts that make me suspect that this idea is fundamentally flawed. (The intersection of half planes usually form convex regions anyway, so I'm pretty sure this idea just won't work).

There's a lot of ways to approach the problem from literature on the web, but it's not clear which ways might work best for this situation. Usually the goal for this problem is to get a new polygon with different vertices after the shrinking. I think (hope) it's possible to instead turn it in to an implicit test (so you test a point and get a yes/no for whether it's inside the shrunk region).

My current idea is to calculate the straight skeleton and triangulate that. The the shader becomes a much simpler test since each triangle would just need to check a single half plane. But that represents a lot of work...

So I'm curious if others have any ideas or have done something similar.

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!