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

Thu Mar 1 19:49:48 PST 2018

On Wed, Feb 28, 2018 at 9:52 PM, Andreas Plesch <andreasplesch at gmail.com>
wrote:

> 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.
>
>
https://github.com/x3dom/x3dom/blob/master/src/nodes/Geometr
y3DExt/Extrusion.js#L334 is where the sidewalls are stitched together. i is
the current cross-section along the spine, and j is the current point of
the cross-section, and n the number of points in a cross-section.

Let's say the spine extends upwards vertically, and cross-section is a
circle with points ordered counterclockwise.

Going around the cross-section, skipping the first point, for each point
two triangles are generated. Let's start with the second triangle. The
first point of that triangle is the current point (say 5 o'clock on second
cross-section at Y = 5). The second point is the previous point on the
current cross-section (6 o'clock at Y = 5, going counterclockwise). The
third point is the previous point on the previous cross-section (6 o'clock
at Y = 4, one down). The diagonal splitting the current side wall quad is
therefore connecting the current point (5 o'clock at Y = 5) with the
previous point on the previous cross-section ( 6 o'clock at Y = 4 ).
Looking at the quad from the outside, the diagonal goes from the upper
right to the lower left of the quad. The first triangle has the same
diagonal as the second as it must.

Ok, let's compare this to http://www.web3d.org/documents/specifications/
19775-1/V3.3/Part01/components/geometry3D.html#Otherfields,
"
Each quadrilateral making up the sides of the extrusion are ordered from
the bottom cross-section (the one at the earlier spine point) to the top.
So, one quadrilateral has the points:

    spine[0](crossSection[0], crossSection[1])
    spine[1](crossSection[1], crossSection[0])

in that order.
"

"In that order" defines the winding order of the quad given the ordering of
the points in the cross-section. That order produces a counterclockwise
winding order for the quad given a counterclockwise cross-section ordering.
The x3dom procedure also produces counterclockwise winding orders for the
side wall triangles given counterclockwise cross-sections. The spec. does
not provide instructions how to split the quad. Adopting the instructions
for Elevationgrid means a diagonal from
spine[0]crossSection[0] to
spine[1]crossSection[1]

which corresponds to x3dom's behavior.

-Andreas

-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
>

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