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

[Andreas Plesch]

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/Geometry3D/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/brutzma
> n
>
>


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