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/

  • \$\begingroup\$ 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. \$\endgroup\$ – OriginalDaemon Oct 11 '13 at 10:06
  • \$\begingroup\$ @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" \$\endgroup\$ – MickLH Oct 11 '13 at 14:11
  • \$\begingroup\$ I can see why my comment wasn't actually needed in this case, my bad. \$\endgroup\$ – OriginalDaemon Oct 14 '13 at 9:55
  • \$\begingroup\$ 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. \$\endgroup\$ – OriginalDaemon Oct 14 '13 at 9:57


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.