Hello, and welcome to this tutorial :)

This thread will (initially) be dedicated to the development of a general-purpose oop object for describing 2D polygons, and performing various tests with them. It will serve as the basis for a more generalized 3D class.
The code will be written for the ObjAsm oopasm environment, but don't be put off - you may still learn something :)

If you are reading this as I write it, you may want to periodically check for modified posts...

To begin with, let's assume that we want to handle pairs of NON CONVEX 2d polygons, and that they are 'sane' (don't self-intersect), and finally, that they always have the same 'winding order' (they are perfectly coplanar - their surface normals point in the same direction .. will help us later in 3D).
We can handle CONVEX polygons later... I choose the more difficult case first :)

So, let's define our Polygon object as an ObjAsm class.
What do we need it to contain as a bare minimum?
We could either describe our polygon as a set of edges, or as a set of points, both being circular lists.
While each has its advantages, we should choose one, and I choose to keep a list of points.
So: we need to keep a list of the 2d points (coordinates) which make up the polygon.
In fact, we COULD assume that they exist in an array somewhere else, and just remember their Vertex Index instead :) But to start with, we'll just shove numbers into a list.

And for the purposes of this tutorial, let's implement the list of points by inheriting from ObjAsm's DwordCollection class. This allows us to keep an unsorted list of 32-bit integers, and we can choose to allow or disallow duplicates.
DwordCollections will also Grow automatically, if we underestimated the storage space requirements.
Inheriting from an existing class means that our Polygon object will inherit all the data, and all the code methods, which are defined by the ancestor class, and any ancestors it might have. But we're only typically only interested in the immediate ancestor class, in this case, DwordCollection. We'll have to call its Init method from our code.

The object would look something like this:


Object POLYGON, PolygonID, DwordCollection
   ;Nothing going on here yet
ObjectEnd


Now to build a Polygon, we simply create an instance (New), initialize it (New Polygon, Init, pOwner, 3, 3, INFINITE), then construct its geometry (add our 2D points via calls to the Insert method).
In this example, I'll be storing the 2D coordinates as pairs of REAL4 floating point values.



mov pMyFirstPolygon, $New(POLYGON, Init, NULL, 3, 3, INFINITE)
OCall pMyFirstPolygon::POLYGON.Insert, 20.0       ;X coordinate
OCall pMyFirstPolygon::POLYGON.Insert, 15.27     ;Y coordinate


Remember that the Polygon represents a Circular Buffer of 2D points forming a CLOSED POLYGON... this implies that the first point is also the last point - don't put it in there twice.
We should observe the same Winding Order - soon we'll see how to enforce that.

<stuff about 'which side of a line is this point test' here, as it lead into>
<stuff about determining and enforcing winding order goes here>

Now that we've constructed our first Polygon, we better make another one, since we need at least two for intersection testing :P


<example polygons jpg to go here>
Let's discuss the possible outcomes of an intersection test between two coplanar 2D polygons.
We can note that there are basically three possible cases:

1 - The polygons do not intersect. They are separated by some space (or are 'just touching' - special case!)
2 - One polygon is entirely inside another.
3 - The polygons overlap in some fashion.

We can't simply check 'if a point of one Polygon is inside the other' - this won't cover case 1 or 3.
And we can't simply check 'if any Edge of one Polygon intersects any Edge of the other' - this won't cover case 2.
The easiest case to check for, and perhaps the fastest (?) is the first case.
For this, we can use 'SAT' (Separating Axis Theorem).
Basically, if we can find any Edge of either Polygon which cleanly separates the two Polygons (a separating axis), then we have case 1: polygons are not intersecting (but may be touching).
If we can't find a Separating Axis, then we must have some kind of intersection (cases 2 and 3), and can move on to another more expensive (?) test - ie, checking for Case 2 (Poly in Poly).

<here belongs injected content>
Posted on 2010-02-22 01:00:28 by Homer
I actually have a great new algorithm to lay out here, which is my own creation.
Not enough interest, I'll keep it to myself.
This thread will evolve with due interest.
Anyone who actually really was interested in this, be patient, or complain loudly.
Posted on 2010-03-01 04:13:14 by Homer