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

[Leonard Daly]

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.

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.



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/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 
> <mailto: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 <mailto:brutzman at nps.edu>
>     Watkins 270,  MOVES Institute, Monterey CA 93943-5000 USA
>     +1.831.656.2149 <tel:%2B1.831.656.2149>
>     X3D graphics, virtual worlds, navy robotics
>     http://faculty.nps.edu/brutzman <http://faculty.nps.edu/brutzman>
>
>
>
>
> -- 
> Andreas Plesch
> Waltham, MA 02453
>
>
> _______________________________________________
> x3d-public mailing list
> x3d-public at web3d.org
> http://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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://web3d.org/pipermail/x3d-public_web3d.org/attachments/20180228/f09645f2/attachment-0001.html>