Polygon triangulation

I have a question related to triangulating <polygons> and <polylist> elements. In the spec for each of these elements it says “primitives that contain four or more vertices may be non-planar as well.” I thought that a polygon was considered planar by definition.

What polygon triangulation algorithms are built to handle non-planar polygons? The triangulation sample provided with the Collada dom uses a fanning algorithm, so it doesn’t handle holes, non-convex polygons, or non-planar polygons. I have to admit it’s a bit annoying that the spec specifically points out that a polygon can be concave, self-intersecting, and non-planar, and the sample code handles none of these cases.

I’m new to the problem of polygon triangulation so any help would be appreciated.

Hello,
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
There is a better algorith for doing polygon triangulation. We plan on implementing it into the conditioner sample code at some point in the near future. It is not an extremely high priority but it isn’t our lowest either.

-Andy

That algorithm will handle all the possible variants of polygons in a Collada model? i.e. concave, self-intersecting, non-planar, and polygons with holes?

I’m going to punt the problem for now by using the glu tessellator. We’ve had problems with the glu tessellator in the past so I’ll have to come back to this problem, but it’s fine for now. Thanks for the help.

Some notes about their implementation:[list=a][li]The code is free for non-commercial use only. Not that big a deal… just have to re-implement their ideas.[/:m:37z4vd8g][/li][li]The code works with 2d points, which means that their idea of a “polygon” is more in line with mine in that it’s planar by definition. So I guess you’d have to project the non-planar polygons onto a plane and then triangulate. Would it always be possible to find a good plane to project onto? I don’t know.[/:m:37z4vd8g][/li][]It claims that “the algorithm handles simple polygons with holes”, so I’m guessing it doesn’t handle self-intersecting polygons correctly.[/:m:37z4vd8g][/list]IMO it’d be better if each polygon were required to be planar and not have any self-intersections. I doubt that any Collada reader in existance handles Collada’s polygons correctly.

hmm polylist doesn’t say that it can be concave or self intersecting. But it doesn’t say that they can’t either.

Hmm maybe the algorith doesn’t do everything that COLLADA supports. I’m sorry I didn’t really look at it much. I was just handed the link and told “this would be better than the fanning” :slight_smile:

As for non-planar polygons. We are aware that that is an issue with COLLADA. You cannot triangulate a non-planar poly correctly without having extra information specifying the “crease” or something similar. I don’t know the technical terms I just know that there are more than one possible triangulation result and not all of them give the same visual output.

-Andy

That’s a good point. I sort of assumed <polylist> and <polygons> had the same restrictions (except for the holes), but maybe they don’t. Maybe the spec could be a little more clear in that regard.

You cannot triangulate a non-planar poly correctly without having extra information specifying the “crease” or something similar. I don’t know the technical terms I just know that there are more than one possible triangulation result and not all of them give the same visual output.
That’s what I suspected but I wasn’t 100% sure. Should I maybe submit a bug against the spec on this? Are there already plans to tighten the restrictions on polygon elements? Or instead are you going to add support for the extra information needed to correctly triangulate a non-planar polygon? (I hope it’s the former).

This is not a bug in the specification.

There are no restrictions in COLLADA regarding the polygons other than having a closed contour. They can be non-planar, simple or complex (self intersecting).
In addition <polygons> can have holes, <polylist> cannot.

Note that practically, most polygons with more than 4 vertices will not be planar, due to floating point accuracy. So often application define a tolerance value for deciding if a polygon is planar or not.

If is possible therefore to use COLLADA to store non-flat complex polygons with hole. I know that it is probably not very useful for most applications, that rather have triangles instead. Luckily, most (if not all) packages already have the export as triangle option, which in case of non flat polygons, should produce better results since the tool has more information to create the right tessellation.

When the tool does not create triangles, or when you want to do your own triangulation (for example because you want to directly generate triangle strips from the polygons) you have the right to restrict your input to simpler forms for polygons. It is rather easy to detect if a polygon is flat, simple, and have no holes, and reject it if it is not the case. It is probably the right thing to do anyway, since having any other form of polygon is most likely a bug in the data.

We will continuously improve the conditioning utilities (you can contribute too !) and will be able to handle more and more complex input. Maybe one day we will also add surfaces to COLLADA, and will also want to provide a triangulate algorithm for those…

Hmm, ok. It seems strange to me because in the face of non-planar polygons we really aren’t given enough information to tessellate and render the polygon. So I don’t see why it’s useful to allow them at all. But I’ll drop the issue since you seem pretty certain you want it this way.

I’ll have to add code to detect if a polygon is non-planar (allowing for roundoff errors and the like) and throw it out if it isn’t, since I can’t triangulate it for rendering. I’ll add that later because I have too much other stuff to do for now, and I doubt I’ll ever come across non-planar polygons in practice.

Thanks,
Steve

  &lt;mesh&gt;
    &lt;source id="pCylinderShape1-positions" name="position"&gt;
      &lt;float_array id="pCylinderShape1-positions-array" count="78"&gt;0.707107 -6 -0.707107 0 -6 -1 -0.707107 -6 -0.707107 -1 -6 0 -0.707107 -6 0.707107 0 -6 1 0.707107 -6 0.707107 1 -6 0 0.707107 0 -0.707107 0 0 -1 -0.707107 0 -0.707107 -1 0 0 -0.707107 0 0.707107 0 0 1 0.707107 0 0.707107 1 0 0 0.707107 6 -0.707107 0 6 -1 -0.707107 6 -0.707107 -1 6 0 -0.707107 6 0.707107 0 6 1 0.707107 6 0.707107 1 6 0 0 -6 0 0 6 0&lt;/float_array&gt;
      &lt;technique_common&gt;
        &lt;accessor source="#pCylinderShape1-positions-array" count="26" stride="3"&gt;
          &lt;param name="X" type="float"/&gt;
          &lt;param name="Y" type="float"/&gt;
          &lt;param name="Z" type="float"/&gt;
        &lt;/accessor&gt;
      &lt;/technique_common&gt;
    &lt;/source&gt;
    &lt;source id="pCylinderShape1-normals" name="normal"&gt;
      &lt;float_array id="pCylinderShape1-normals-array" count="198"&gt;0.382683 0 -0.92388 0.382683 0 -0.92388 0.382683 0 -0.92388 0.382683 0 -0.92388 -0.382683 0 -0.92388 -0.382683 0 -0.92388 -0.382683 0 -0.92388 -0.382683 0 -0.92388 -0.92388 0 -0.382683 -0.92388 0 -0.382683 -0.92388 0 -0.382683 -0.92388 0 -0.382683 -0.92388 0 0.382683 -0.92388 0 0.382683 -0.92388 0 0.382683 -0.92388 0 0.382683 -0.382683 0 0.92388 -0.382683 0 0.92388 -0.382683 0 0.92388 -0.382683 0 0.92388 0.382683 0 0.92388 0.382683 0 0.92388 0.382683 0 0.92388 0.382683 0 0.92388 0.923879 0 0.382683 0.923879 0 0.382683 0.923879 0 0.382683 0.923879 0 0.382683 0.923879 0 -0.382684 0.923879 0 -0.382684 0.923879 0 -0.382684 0.923879 0 -0.382684 0.382683 0 -0.92388 0.382683 0 -0.92388 -0.382683 0 -0.92388 -0.382683 0 -0.92388 -0.92388 0 -0.382683 -0.92388 0 -0.382683 -0.92388 0 0.382683 -0.92388 0 0.382683 -0.382683 0 0.92388 -0.382683 0 0.92388 0.382683 0 0.92388 0.382683 0 0.92388 0.923879 0 0.382683 0.923879 0 0.382683 0.923879 0 -0.382684 0.923879 0 -0.382684 0 -1 0 0 -1 0 0 -1 0 0 -1 0.000000 0 -1 0 0 -1 -0.000000 0 -1 0 0 -1 0 0 -1 0 0 1 0 0 1 0 0 1 0 0 1 0.000000 0 1 0 0 1 -0.000000 0 1 0 0 1 0 0 1 0&lt;/float_array&gt;
      &lt;technique_common&gt;
        &lt;accessor source="#pCylinderShape1-normals-array" count="66" stride="3"&gt;
          &lt;param name="X" type="float"/&gt;
          &lt;param name="Y" type="float"/&gt;
          &lt;param name="Z" type="float"/&gt;
        &lt;/accessor&gt;
      &lt;/technique_common&gt;
    &lt;/source&gt;
    &lt;vertices id="pCylinderShape1-vertices"&gt;
      &lt;input semantic="POSITION" source="#pCylinderShape1-positions"/&gt;
    &lt;/vertices&gt;
    &lt;polylist material="initialShadingGroup" count="32"&gt;
      &lt;input semantic="VERTEX" source="#pCylinderShape1-vertices" offset="0"/&gt;
      &lt;input semantic="NORMAL" source="#pCylinderShape1-normals" offset="1"/&gt;
      &lt;vcount&gt;4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3&lt;/vcount&gt;

0 0 1 1 9 2 8 3 1 4 2 5 10 6 9 7 2 8 3 9 11 10 10 11 3 12 4 13 12 14 11 15 4 16 5 17 13 18 12 19 5 20 6 21 14 22 13 23 6 24 7 25 15 26 14 27 7 28 0 29 8 30 15 31 8 3 9 2 17 32 16 33 9 7 10 6 18 34 17 35 10 11 11 10 19 36 18 37 11 15 12 14 20 38 19 39 12 19 13 18 21 40 20 41 13 23 14 22 22 42 21 43 14 27 15 26 23 44 22 45 15 31 8 30 16 46 23 47 1 48 0 49 24 50 2 51 1 48 24 50 3 52 2 51 24 50 4 53 3 52 24 50 5 54 4 53 24 50 6 55 5 54 24 50 7 56 6 55 24 50 0 49 7 56 24 50 16 57 17 58 25 59 17 58 18 60 25 59 18 60 19 61 25 59 19 61 20 62 25 59 20 62 21 63 25 59 21 63 22 64 25 59 22 64 23 65 25 59 23 65 16 57 25 59</p>
</polylist>
</mesh>

Hello, whats wrong with this mesh ? I’m unable to convert properly the poly with 4 vertices. I’ve tryed using the triangulate(…) method from Crt and same problem. ColViewer seem to read it correctly…

It is a stupid cylinder exported from maya.

I’m not sure but it seem to be non CCW sometimes…

There is no convention about CCW/CCW for poly in collada ?

Nevermind, the bug was in my weight’s assignation. All works fine now.