Creating good geometries

Jul 2, 2007 at 6:45 PM
Hi,

I'm working on a tool for attaching vertices and physical properties to images (I know a tool like this exists already, but this one is more specific to my 2D library). I noticed that the geometries I defined in this tool were having some collision detection/handling problems that I had not seen before, and discovered that this is because for example a RectangleGeometry has 16 vertices, where my tool would create just four to represent a rectangle (at the moment rectangles are just created as polygons). I was particularly fascinated by this because there's always 16, regardless of the size of the rectangle. I was hoping someone could explain to me the principle behind this, and how I can use it to create good geometries in my tool (hopefully automatically, based on a simpler geometry input by the user).

Thanks,
Max
Coordinator
Jul 3, 2007 at 4:46 PM
I think I explain it in this document: http://www.codeplex.com/FarseerPhysics/Project/FileDownload.aspx?DownloadId=3231

Ideally, the you want a fairly even spread of vertices around the perimeter of you polys. This is because each vert of poly A is tested against the grid of Poly B (and vice versa). The rectangles in the current engine simply divide each edge into quarters (or thirds???) This was just something I did as a temporary quick fix.

I have an idea for an algorithm to compute a better set of verts. The algo will take a "shortest edge length" as a parameter, then it will simply cycle thru all edges and divide them in half repeatably until all edges are less or equal the "shortest edge length" parameter. So the rectangle would start with 4 edges and on the first pass over the edges each would be split half creating 8 total edges. If the edges still were to large, another pass would split them all again... and so on. For polys with different length edges, multiple passes would still be made, but only edges that are greater than the "shortest edge length" parameter would be further split.

This is only in my head right now, I'll try implementing it soon for the new engine.
Jul 3, 2007 at 6:39 PM
Thanks, that makes sense, I just wanted to make sure that the goal was to reduce edge length, it was the constant number of vertices in the rectangle that threw me off. I think I will do something like this: take a max edge length parameter but instead of dividing in halves, divide each edge into the minimum number of equal-sized pieces that can satisfy the parameter. So if you have an edge of length 100 and the user wants maximum length 22, you'll get five edges out instead of eight. That way you're using the minimum number of vertices to do what the user wants.
Coordinator
Jul 5, 2007 at 11:38 AM
Sounds like a good idea... better than my idea.