[x3d-public] Mantis issue 1209: Tesselation of quadrilaterals and n-gons

Wed Feb 28 18:52:11 PST 2018

On Wed, Feb 28, 2018 at 4:52 PM, Leonard Daly <Leonard.Daly at realism.com>
wrote:

> Andreas,
>
> IndexedFaceSet nodes require that the polygon that defines each face (
> http://www.web3d.org/documents/specifications/19775-1/V3.3/
> Part01/components/geometry3D.html#IndexedFaceSet) have
>
>    1. at least three non-coincident vertices;
>    2. vertices that define a planar polygon;
>    3. vertices that define a non-self-intersecting polygon.
>
> Every face must be planar (to be spec-compliant); however, certain
> applications may choose to support non-planar faces. I believe that your
> discussion is what X3DOM does when it goes beyond the definition in the
> spec. I do not disagree about your final conclusion about winding order.
>

The discussion covered both non-planar and planar polygons as requested.
Quads for ElevationGrids will be non-planar in most cases. I believe this
to be reason why there are specific instructions on tessellation in this
case. I did not check but suspect that in most other cases rendering of
non-planar polygons was deemed out of scope, and as such may not need
further resolution.

For the ElevationGrid node there is a paragraph (about 5th, depending on
> how things are counted) that specifically addresses the case where the
> rendering algorithm requires tessellation (probably should be
> triangulation). ["quadrilaterals are split into triangles along the seam
> starting at the initial vertex of the quadrilateral and proceeding to the
> opposite vertex"]. Note that ElevationGrid does not require planar
> quadrilaterals.
>
> Extrusion is a much more complex shape and I don't have any special
> insights to it at this time.
>

Extrusions have non-planar polygons in their sides if there is a twist
along the extrusion. The only instructions are:
13.3.5.3: " Corresponding vertices of the first and second cross-sections
are then connected, forming a quadrilateral polygon between each pair of
vertices."

I could look up how x3dom triangulates the sides.

-Andreas

>
>
> Leonard Daly
>
>
>
> Hi Don,
>
> here is my interpretation of how x3dom deals with n>3-gons, in an
> IndexedFaceSet. Let's only deal with crease angles which do not require
> duplication of indices since normals at the vertices can be shared (for a
> smooth appearance).
>
> The tesselation/triangulation of the n-gons occurs by a simple conversion
> to triangle fans, with all triangles sharing the first point in the n-gon,
> in case of convex polygons as indicated by the convex field. In case of
> non-convex (concave) polygons, the more sophisticated earclipping method is
> used for the triangulation. In both cases, the original winding order of
> points around the polygons is preserved in the order of triangle indices.
> This is plain to see for the first, convex, case and is also true for
> concave case. However, the utilized earclipping library originally did not
> consider preservation of winding order and required a patch which was then
> merged.
>
> https://github.com/x3dom/x3dom/blob/master/src/nodes/Geometr
> y3D/IndexedFaceSet.js#L554 is the relevant entry for this first part.
>
> Then, if normals are not provided, they are calculated here:
>
> https://github.com/x3dom/x3dom/blob/master/src/Mesh.js#L141
>
> The three points of a triangle are labelled 0, t, 2 in this order. The
> vector pointing from t (the center point) to 0 is called a.  The vector
> pointing from 2 (the center point) to t is called b. (Hm, I would have
> pointed both vectors away from t).
>
> The normal of the triangle then is calculated as a cross b.
>
> This means that the normal is pointing to the front (back to the viewer),
> if the actual winding order is counterclockwise (as seen from the viewer).
> If the counterclockwise field is set to false, the normal is inverted.
> (This implementation may not be quite correct since the direction of the
> normal probably should not depend on the actual winding order of the given
> points, but only on the value of the field).
>
> Let's see what this all means for planar polygons. There is no problem
> since all generated triangles inherit the same winding order from the
> polygon, and are treated then the same.
> For non-planar, convex polygons, I think there is also no problem since
> the preservation of winding order means that all normals point
> consistently. For non-planar, concave polygons, the earclipping only works
> if for triangulation purposes points can be collapsed onto a 2d plane (say
> the x-z plane). But this is really an unrelated problem.
>
> As a result, I think it is important for implementations and may be for
> the spec. to deal with winding order. Winding order should be preserved
> when tesselating. For elevation grid this means that given a quad with
> points a, b, c, d in order around the the quad, the triangles should become
> a, b, c and a, c, d (and not a, c, d and a, d, c).
>
> -Andreas
>
> [I may have to reread relevant sections on the ccw field, particularly
> concerning the situation where actual order is reversed from indicated
> order.]
>
>
>
> On Wed, Feb 28, 2018 at 12:45 PM, Don Brutzman <brutzman at nps.edu> wrote:
>
>> Attached please find current Mantis issue searching for regular
>> tesselation of polygons with 4 or more vertices.
>>
>> For browser implementers: wondering how you handle polygons with greater
>> than 4 points (n-gons), so that all normals are pointing in the same
>> direction for planar polygons, or to the same side of the face for
>> nonplanar polygons.
>>
>> all the best, Don
>> --
>> Don Brutzman  Naval Postgraduate School, Code USW/Br
>> brutzman at nps.edu
>> Watkins 270,  MOVES Institute, Monterey CA 93943-5000 USA
>> +1.831.656.2149
>> X3D graphics, virtual worlds, navy robotics
>> http://faculty.nps.edu/brutzman
>>
>>
>
>
> --
> Andreas Plesch
> Waltham, MA 02453
>
>
> _______________________________________________
> x3d-public mailing listx3d-public at web3d.orghttp://web3d.org/mailman/listinfo/x3d-public_web3d.org
>
>
> --
> *Leonard Daly*
> 3D Systems & Cloud Consultant
> LA ACM SIGGRAPH Past Chair
> President, Daly Realism - *Creating the Future*
>

-- 
Andreas Plesch
Waltham, MA 02453
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://web3d.org/pipermail/x3d-public_web3d.org/attachments/20180228/a6d3c1ec/attachment.html>