How do I fill a grid based shape with tris

I have a shape defined by an array of 2D points (clockwise around the shape) and a height value. The points conform to a grid layout with whole numbers, however there can be negative space in the shape. A simple example generated could be like the various blocks from Tetris.

I need to create surfaces and tris to fill the top side of the shape (the face that looks like a Tetris block) but I don't know how to break down the edge definition points into rectangles so I can cre开发者_StackOverflowate surfaces to cover it.

I'm sure this has been asked before but I don't know how to phrase it to find what I need.

---

The term you're looking for is "polygon triangulation". The Wikipedia article explains a couple of algorithms.

---

As mentioned above you want to research triangulation. A great method for beginners is called 'Ear Clipping'. Below is a link to a wonderful PDF that explains in detail the steps you need to take to implement it.

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

---

If you're working in C++, you might use the CGAL library to do this: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Mesh_2/Chapter_main.html