﻿using System.Collections.Generic; using Microsoft.Xna.Framework; namespace FRBForwardLighting { /// /// Class which takes a list of points representing a polygon and converts it into triangles that may /// then be rendered using XNA. Assumes all the points are in the x,y plane. The orientation of the /// vertices of output triangles (clockwise/counter-clockwise) will be the same as the input polygon. /// public class PolygonTessellation { #region Methods /// /// Takes the list of points forming a polygon in the x-y plane and generates a list of triangle /// vertices and indices suitable for drawing with XNA draw calls as a triangle list. The polygon /// cannot have holes in it (the holes will be ignored) nor can it handle correctly self-intersecting /// polygons. /// /// List of points making up the closed polygon. /// Array to be filled with vertices. /// Array to be filled with indices. public void TessellatePolygon(List polygon, out Vector3[] vertices, out short[] indices) { var tempIndices = new List(); var tempVertices = polygon; //create triangles from polygon MeshPoly(tempVertices, tempIndices); //transfer data into form needed by xna indices = tempIndices.ToArray(); vertices = tempVertices.ToArray(); } /// /// Determines the orientation of the polygon (clockwise or counter-clockwise). /// /// List of points (in order) making polygon. /// True if clockwise. private static bool IsClockwise(List vertexList) { //do the wrap-around case first double area = vertexList[vertexList.Count - 1].X * vertexList.Y - vertexList.X * vertexList[vertexList.Count - 1].Y; //compute the area (times 2) of the polygon for (int i = 0; i <= vertexList.Count - 2; i++) { area += vertexList[i].X * vertexList[i + 1].Y - vertexList[i + 1].X * vertexList[i].Y; } if (area >= 0) return false; return true; } /// /// Computes the determinant of 3 points. /// /// Index of point in vertex list. /// Index of point in vertex list. /// Index of point in vertex list. /// List of vertices. /// True if clockwise. private static bool Determinant(int p1, int p2, int p3, List vertexList) { double x1 = vertexList[p1].X; double y1 = vertexList[p1].Y; double x2 = vertexList[p2].X; double y2 = vertexList[p2].Y; double x3 = vertexList[p3].X; double y3 = vertexList[p3].Y; var determ = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1); if (determ >= 0) return false; return true; } /// /// Determines the square of the distance between 2 points. /// /// X coordinate of 1st point. /// Y coordinate of 1st point. /// X coordinate of 2nd point. /// Y coordinate of 2nd point. /// Square of distance between given points. private static double Distance2(double x1, double y1, double x2, double y2) { double xd = x1 - x2; double yd = y1 - y2; return xd * xd + yd * yd; } /// /// Determines if any points in the vertex list are within the given triangle. /// /// Index of 1st triangle point. /// Index of 2nd triangle point. /// Index of 3rd triangle point. /// Vertex list. /// Indices of vertices left to tessellate. /// True if polygon points are in clockwise order. /// True if no other point in vertex list is inside the given triangle. private static bool NoInteriorPoint(int p1, int p2, int p3, List vertexList, List verticesLeft, bool clockwisePoly) { for (var i = 0; i < verticesLeft.Count; i++) { var p = verticesLeft[i]; // don't bother checking against yourself if (p == p1 || p == p2 || p == p3) continue; if (Determinant(p2, p1, p, vertexList) != clockwisePoly && Determinant(p1, p3, p, vertexList) != clockwisePoly && Determinant(p3, p2, p, vertexList) != clockwisePoly) //point is inside triangle return false; } //no points inside triangle return true; } /// /// Divides a polygon into triangles. Doesn't work for polygons with holes or self-penetration. /// /// List of vertices in polygon. /// List to add vertex indices of created triangles to (needs to already be created). public static void MeshPoly(List vertexList, List indices) { var clockwisePoly = IsClockwise(vertexList); //make list of vertices indexes var verticesLeft = new List(); for (short i = 0; i < vertexList.Count; i++) { verticesLeft.Add(i); } //while more than 3 points left in list while (verticesLeft.Count > 3) { double minDist = 999999999; var minVert = 0; int prevPoint; int nextPoint; for (var curPoint = 0; curPoint < verticesLeft.Count; curPoint++) { //set adjacent points prevPoint = curPoint - 1; nextPoint = curPoint + 1; //wrap around the ends if (curPoint == 0) prevPoint = verticesLeft.Count - 1; else if (curPoint == verticesLeft.Count - 1) nextPoint = 0; //pick out the shortest distance that forms a good triangle and has same orientation as polygon and //has no other vertices inside it var dist = Distance2(vertexList[verticesLeft[prevPoint]].X, vertexList[verticesLeft[prevPoint]].Y, vertexList[verticesLeft[nextPoint]].X, vertexList[verticesLeft[nextPoint]].Y); if (Determinant(verticesLeft[prevPoint], verticesLeft[curPoint], verticesLeft[nextPoint], vertexList) == clockwisePoly && NoInteriorPoint(verticesLeft[prevPoint], verticesLeft[curPoint], verticesLeft[nextPoint], vertexList, verticesLeft, clockwisePoly) && dist < minDist) { minDist = dist; minVert = curPoint; } } prevPoint = minVert - 1; nextPoint = minVert + 1; //wrap around the ends if (minVert == 0) prevPoint = verticesLeft.Count - 1; else if (minVert == verticesLeft.Count - 1) nextPoint = 0; //add this triangle to list indices.Add(verticesLeft[prevPoint]); indices.Add(verticesLeft[minVert]); indices.Add(verticesLeft[nextPoint]); //remove triangle from the polygon verticesLeft.Remove(verticesLeft[minVert]); } //store the final triangle indices.Add(verticesLeft); indices.Add(verticesLeft); indices.Add(verticesLeft); } #endregion } }