Mark Sachs (ksleet) wrote,
Mark Sachs

  • Mood:
  • Music:

Look on my works, ye Mighty, and purchase a souvenir!

Today on Neon Galaxy: polygon clipping!!! Isn't that exciting?

Basically, for a long time I've been meaning to rework the polygon clipping routine in my engine. The essential problem is as follows: It's very difficult to do the math for concave polygons -- this means such things as evaluating whether or not a point or circle is inside the polygon, does the polygon intersect other objects, even just drawing the stupid things -- all this stuff is much harder. It's much easier to do all those things with convex polygons. Unfortunately, a convex polygon isn't going to be a very interesting maze, so effectively I've got to create a game environment that looks like a giant concave polygon and under the hood breaks it down into convex polygons.

This is fairly tricky, and the homebrewed algorithm I was using before wasn't really cutting the mustard. The mechanism was clever: it involved following the border of one polygon until it intersected the other, then following the second until it rejoined the first, and using that information to define the output polygons. This could therefore clip two convex polygons against each other, so when placed against each other in the world they'd make up the desired concave polygon (imagine, say, sticking a straw into a block of Jell-O; you can divide this concave shape into two convex ones, the block and the piece of straw sticking out of it). However, it couldn't handle the situation where one of the polygons would need to be divided into two new ones (imagine pushing the straw all the way through the Jell-O and out the other side -- now you'd need three convex polygons to represent the result.)

Two convex polygons, versus three convex polygons.

I'd been putting off dealing with this problem because math is hard and even just clipping two polygons like this is sufficient for creating some very complex geometry, as long as you've got a solid understanding of what polygons you're sending into the system. Needing to carefully shape the input data really cramped my style, though. This weekend I finally broke down and rethought the whole thing. I realized that all I really had to do was let my algorithm continue on after the first time it returned to the initial polygon. It simply had to proceed on around the border, and if it crossed the second polygon again, generate another output polygon, and so forth as many times as necessary. Once I figured this out, the actual implementation was easy. The most complicated part in the end turned out to be dealing with the concept that I might get back an arbitrary number of polygons after clipping instead of just two. I am going to need to rethink some of the maze construction code because of this, but still:

In this example, placing several irregular, overlapping polygons in a row creates a more naturalistic cave structure, and clipping them against each other generates a set of convex polygons suitable for gameplay use.
Tags: neon galaxy
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.