Jump to content
  • Advertisement
Sign in to follow this  

Straight skeleton and offset polygon

This topic is 2776 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
Sign in to follow this  

  • Advertisement

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!