# Filling in a shape from vertices

What I'm trying to do is set a bunch of points to create a shape and then fill everything in within those points. It needs to be done in 3D becasue this is being used as a way to generate a texture for another shader I'm working on so the other shader knows what to highlight and what to not highlight.

Right now what I have a camera setup and I have it drawing a simple square with line lists. Eventually this will be extended upon to be more than just a simple square.

What is the best way to go about filling this shape in with a color, keeping in mind that it won't be a square later on.

Sounds like you are asking for a convex hull, this is sortof like "gift wrapping" all your vertices. (Otherwise, if the shape can be concave you cannot imply it by the vertices alone)

Wikipedia has a good list of techniques here: http://en.wikipedia.org/wiki/Convex_hull_algorithms

And google code even has an implementation (I haven't tested this): http://code.google.com/p/stanhull/

• This method would rule out any concave shapes as an option. I like to think of it as wrapping a rubber band around a bunch of nails. – OriginalDaemon Oct 11 '13 at 10:06
• @OriginalDaemon Non-trivial concave shapes are ruled out just based on the OPs input dataset, hence: "if the shape can be concave you cannot imply it by the vertices alone" – MickLH Oct 11 '13 at 14:11
• I can see why my comment wasn't actually needed in this case, my bad. – OriginalDaemon Oct 14 '13 at 9:55
• I take the comments "within those points" and "square with line lists" to imply that the current dataset may well be a set of points lying strictly on the shape edge, as opposed to a point cloud, thus concave shapes can be defined with it. – OriginalDaemon Oct 14 '13 at 9:57

Triangulation

If the shape is defined by a series of vertices/points which are listed linearly to create a outline/membrane then what you want is polygon triangulation.

By breaking the shape down into a list of triangles it will be possible to render like any other mesh in XNA (or opengl/directX). If you don't already know how to do this there are a plethora of triangle rendering tutorials out there for xna or pretty much any other system.

Note: If the system generating the shape can guarantee that it is monotonic (convex) then you will probably be able to get away with rendering it as a triangle fan where the center (first point) is simply the average of all points making up the shape membrane.