Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite

I have a set of squares (pixels coming in from an image) that i want to triangulate.

Example problem

I narrowed my choices down to 2 possible routes: A, breaking the squares into lager rectangles, or B, generating a set of vertices and triangulating them. B is better, as it generates fewer vertices.

I'm dumb, and couldn't find a way to implement route A. But oddly enough, i found it simpler go with route B and generate the vertices. I'm checking neighbor pixels and using a simple lookup table to determine where to place a vertex. That is done and easy.

But with that collection of vertices, i'm stuck. It might contain holes, or be composed of multiple islands of polygons. So from there, i don't know where to go. Any ideas?

Also, if it makes any difference, i'm using these triangulated images to build up a voxel mesh, marching through the voxel data in 6 directions and looking at it in cross sections. At the end, i'll piece them all back together. It's kind of similar to the "trixels" used in Fez.

share|improve this question

1 Answer

up vote 0 down vote accepted

If you can generate a list of edges around the outside, counterclockwise, instead of a list of vertices (for holes, a list of edges clockwise around the hole), then you should be able to triangulate it using the answers from this question: http://stackoverflow.com/questions/406301/polygon-triangulation-with-holes

share|improve this answer
Interesting, thanks. I'm not sure if i can do that as easily, but we'll see :) – Logan Granberry Oct 25 '11 at 23:15
@LoganGranberry, one way to figure out the edges might be to think of each square as starting out with 4 edges running counterclockwise around it. Then combine squares, adding one square at a time to the combined shape, deleting any shared edges but keeping the rest in counterclockwise order, until all the squares are included. Then you should have a correct ordered list of edges. You'd likely also want to do a pass to combine collinear edges into one. – Nathan Reed Oct 25 '11 at 23:55
Hmm. I'm having trouble finding a way to do this so that the edges are added in order of appearance. I'm thinking about just adding the edges to a collection in non-sorted order, then going back and sorting them by looking at the ending vertex, and searching for an edge that has a corresponding starting vertex. But then i have the issue of corner where 2 edges share the same starting vertex. haha. I appreciate the help, this is the answer i was looking for i just need to solve this last bit. – Logan Granberry Oct 26 '11 at 1:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.