<div dir="auto"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Feb 28, 2018 at 9:52 PM, Andreas Plesch <span dir="ltr"><<a href="mailto:andreasplesch@gmail.com" target="_blank">andreasplesch@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">On Wed, Feb 28, 2018 at 4:52 PM, Leonard Daly <span dir="ltr"><<a href="mailto:Leonard.Daly@realism.com" target="_blank">Leonard.Daly@realism.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">
<div class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-cite-prefix">Andreas,<br>
<br>
IndexedFaceSet nodes require that the polygon that defines each
face
(<a class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-txt-link-freetext" href="http://www.web3d.org/documents/specifications/19775-1/V3.3/Part01/components/geometry3D.html#IndexedFaceSet" target="_blank">http://www.web3d.org/document<wbr>s/specifications/19775-1/V3.3/<wbr>Part01/components/geometry3D.h<wbr>tml#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></div></div></blockquote><div><br></div><div>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.<br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"><div class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-cite-prefix">
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></div></div></blockquote><div><br></div><div>Extrusions have non-planar polygons in their sides if there is a twist along the extrusion. The only instructions are:<br><a href="http://13.3.5.3" target="_blank">13.3.5.3</a>: " Corresponding vertices of the first and second cross-sections are then connected, forming a quadrilateral polygon between each pair of vertices." <br><br></div><div>I could look up how x3dom triangulates the sides.</div><div><br></div></div></div></div></blockquote><div><br></div><div><a href="https://github.com/x3dom/x3dom/blob/master/src/nodes/Geometry3DExt/Extrusion.js#L334" target="_blank">https://github.com/x3dom/x3dom<wbr>/blob/master/src/nodes/Geometr<wbr>y3DExt/Extrusion.js#L334</a> 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.<br></div><div><br></div><div>Let's say the spine extends upwards vertically, and cross-section is a circle with points ordered counterclockwise.</div><div><br></div><div>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.</div><div><br></div><div>Ok, let's compare this to <a href="http://www.web3d.org/documents/specifications/19775-1/V3.3/Part01/components/geometry3D.html#Otherfields" target="_blank">http://www.web3d.org/<wbr>documents/specifications/<wbr>19775-1/V3.3/Part01/<wbr>components/geometry3D.html#<wbr>Otherfields</a>, </div>"</div><div class="gmail_quote">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:<br><br>  spine[0](crossSection[0], crossSection[1])<br>  spine[1](crossSection[1], crossSection[0])<br><br>in that order.<div>"</div><div><br></div><div>"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 </div><div><span style="font-family:sans-serif">spine[0]crossSection[0] to </span><br></div><div><span style="font-family:sans-serif">spine[1]crossSection[1]</span><br></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">which corresponds to x3dom's behavior.</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><font face="sans-serif">-Andreas</font></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div>-Andreas</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"><div class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-cite-prefix">
<br>
<br>
<br>
Leonard Daly<br>
<br>
<br>
<br>
</div>
<blockquote type="cite">
<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" target="_blank">https://github.com/x3dom/x3dom<wbr>/blob/master/src/nodes/Geometr<wbr>y3D/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" target="_blank">https://github.com/x3dom/x3dom<wbr>/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">brutzman@nps.edu</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);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="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980HOEnZb"><font color="#888888"><br>
-- <br>
Don Brutzman Naval Postgraduate School, Code USW/Br Â
  <a href="mailto:brutzman@nps.edu" target="_blank">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">+1.831.656.2149</a><br>
X3D graphics, virtual worlds, navy robotics <a href="http://faculty.nps.edu/brutzman" rel="noreferrer" target="_blank">http://faculty.nps.edu/brutzma<wbr>n</a><br>
<br>
</font></span></blockquote>
</div>
<br>
<br clear="all"><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986HOEnZb"><font color="#888888">
<div><br>
</div>
-- <br>
<div class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980gmail_signature">
<div dir="ltr">
<div>Andreas Plesch<br>
Waltham, MA 02453</div>
</div>
</div>
</font></span></div><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986HOEnZb"><font color="#888888">
<br>
<fieldset class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
x3d-public mailing list
<a class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-txt-link-abbreviated" href="mailto:x3d-public@web3d.org" target="_blank">x3d-public@web3d.org</a>
<a class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-txt-link-freetext" href="http://web3d.org/mailman/listinfo/x3d-public_web3d.org" target="_blank">http://web3d.org/mailman/listi<wbr>nfo/x3d-public_web3d.org</a>
</pre>
</font></span></blockquote><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986HOEnZb"><font color="#888888">
<p><br><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-HOEnZb"><font color="#888888">
</font></span></p><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-HOEnZb"><font color="#888888">
<div class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980moz-signature">-- <br>
<font class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980tahoma,arial,helvetica m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980san m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986m_2892059108391546980serif" 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>
</font></span></font></span></div><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-HOEnZb"><font color="#888888">
</font></span></blockquote></div><span class="m_7778332564779914003gmail-m_-6268119804651753221gmail-HOEnZb"><font color="#888888"><br><br clear="all"><br>-- <br><div class="m_7778332564779914003gmail-m_-6268119804651753221gmail-m_-7281399266977686549m_-7566365854023806214m_5642900220519767986gmail_signature"><div dir="ltr"><div>Andreas Plesch<br>Waltham, MA 02453</div></div></div>
</font></span></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="m_7778332564779914003gmail-m_-6268119804651753221gmail_signature"><div dir="ltr"><div>Andreas Plesch<br>Waltham, MA 02453 by</div></div></div>
</div></div></div>