Wednesday, September 7, 2011

Adventures with Triangulation

Oooh, blogger has a new interfa.... err getting distracted again.

So, as i mentioned i am currently working on The Collapse, or rather, i am kind of redesigning it. I was brainstorming with Lateman this weekend and he had a nice idea for a graphical design concept. But more on that in another post.

To be able to achieve what we had in mind i had to redesign the leveleditor from scratch. No more boxes, cubes, and spheres.
One technical hurdle was getting convex triangulation with holes to work. I was scrolling through a couple of papers earlier today, and i got a good glimpse of... well i wont be shitting you, i didn't get most of it. I currently don't care much about how it is solved technically, considering that it is quite a complex topic, so i further ventured through the internet looking for resources. Eventually i found this.

I am using the C# version by Erwin Perik, ironically the High performance version by Salvatore Previti, well the sample anyways, was pretty slow. We're talking about ~1 second for around 150vertices slow. Kind of curious since they both are derived from the same base code.

So what am i gonna do with it? I am feeding it a series of vectors in order to receive a generated surface i can texture.

Simply simple
So far so good. The problem is though, i dont have randomly scattered vertices like shown above.
What i am looking for is, after all, a concave polygon with holes. So when feeding it with proper data, it was more looking like this:

Oh, why you be so convex :(

Just then i was remembering a rule to determine if a point is within an arbitrary shape or not, which is: draw a line from a point you chose to a point anywhere within the shape, and make an intersectiontest with every bordering line segment. Is the amount of intersections even, the point is inside the shape. Is it odd, it lies outside.
So what i can do now is simply define an anchor point within the shape, calculate the center of each triangle, and do intersection tests with the border segments, check the amount of intersections and voila:

Concave, with holes, not all that complex after all

So i guess this is kind of cheating, but it works, and quite fast too. I worried that it might take a week to get it working correctly, but thanks to the internets it just took a couple of hours \o/

If you have questions, let me know below