<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Andreas,<br>
<br>
IndexedFaceSet nodes require that the polygon that defines each
face
(<a class="moz-txt-link-freetext" href="http://www.web3d.org/documents/specifications/19775-1/V3.3/Part01/components/geometry3D.html#IndexedFaceSet">http://www.web3d.org/documents/specifications/19775-1/V3.3/Part01/components/geometry3D.html#IndexedFaceSet</a>)
have<br>
<ol start="1" type="a">
<li>at least three non-coincident vertices;</li>
<li>vertices that define a planar polygon;</li>
<li>vertices that define a non-self-intersecting polygon.</li>
</ol>
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.<br>
<br>
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.<br>
<br>
Extrusion is a much more complex shape and I don't have any
special insights to it at this time.<br>
<br>
<br>
<br>
Leonard Daly<br>
<br>
<br>
<br>
</div>
<blockquote type="cite"
cite="mid:CAKdk67sFapQsQyM=wu1+YGQB5MQLQgYzqr36wb_U6483m53-iw@mail.gmail.com">
<div dir="ltr">Hi Don,
<div><br>
</div>
<div>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). </div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div><a
href="https://github.com/x3dom/x3dom/blob/master/src/nodes/Geometry3D/IndexedFaceSet.js#L554"
moz-do-not-send="true">https://github.com/x3dom/x3dom/blob/master/src/nodes/Geometry3D/IndexedFaceSet.js#L554</a>
is the relevant entry for this first part.<br>
</div>
<div><br>
</div>
<div>Then, if normals are not provided, they are calculated
here:</div>
<div><br>
</div>
<div><a
href="https://github.com/x3dom/x3dom/blob/master/src/Mesh.js#L141"
moz-do-not-send="true">https://github.com/x3dom/x3dom/blob/master/src/Mesh.js#L141</a><br>
</div>
<div><br>
</div>
<div>The three points of a triangle are labelled 0, t, 2 in this
order.<span
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span> </span>The
vector pointing from t (the center point) to 0 is called a. <span
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span> </span>The
vector pointing from 2 (the center point) to t is called
b. (Hm, I would have pointed both vectors away from t).</span></span></div>
<div><br>
</div>
<div>The normal of the triangle then is calculated as a cross
b. </div>
<div><br>
</div>
<div>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). </div>
<div><br>
</div>
<div>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.</div>
<div>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.</div>
<div><br>
</div>
<div>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).</div>
<div><br>
</div>
<div>-Andreas</div>
<div><br>
</div>
<div>[I may have to reread relevant sections on the ccw field,
particularly concerning the situation where actual order is
reversed from indicated order.]</div>
<div><br>
</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Feb 28, 2018 at 12:45 PM, Don
Brutzman <span dir="ltr"><<a
href="mailto:brutzman@nps.edu" target="_blank"
moz-do-not-send="true">brutzman@nps.edu</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">Attached
please find current Mantis issue searching for regular
tesselation of polygons with 4 or more vertices.<br>
<br>
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.<br>
<br>
all the best, Don<span class="HOEnZb"><font color="#888888"><br>
-- <br>
Don Brutzman Naval Postgraduate School, Code USW/Br
<a href="mailto:brutzman@nps.edu" target="_blank"
moz-do-not-send="true">brutzman@nps.edu</a><br>
Watkins 270, MOVES Institute, Monterey CA 93943-5000
USA <a href="tel:%2B1.831.656.2149"
value="+18316562149" target="_blank"
moz-do-not-send="true">+1.831.656.2149</a><br>
X3D graphics, virtual worlds, navy robotics <a
href="http://faculty.nps.edu/brutzman"
rel="noreferrer" target="_blank"
moz-do-not-send="true">http://faculty.nps.edu/brutzma<wbr>n</a><br>
<br>
</font></span></blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<div class="gmail_signature" data-smartmail="gmail_signature">
<div dir="ltr">
<div>Andreas Plesch<br>
Waltham, MA 02453</div>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
x3d-public mailing list
<a class="moz-txt-link-abbreviated" href="mailto:x3d-public@web3d.org">x3d-public@web3d.org</a>
<a class="moz-txt-link-freetext" href="http://web3d.org/mailman/listinfo/x3d-public_web3d.org">http://web3d.org/mailman/listinfo/x3d-public_web3d.org</a>
</pre>
</blockquote>
<p><br>
</p>
<div class="moz-signature">-- <br>
<font class="tahoma,arial,helvetica san serif" color="#333366">
<font size="+1"><b>Leonard Daly</b></font><br>
3D Systems & Cloud Consultant<br>
LA ACM SIGGRAPH Past Chair<br>
President, Daly Realism - <i>Creating the Future</i>
</font></div>
</body>
</html>