Tessellation

[Bruce Sherwood]

I'm in the process of developing an extrusion object for GlowScript VPython. Here's an early example:

http://www.glowscript.org/#/user/GlowScriptDemos/folder/Examples/program/Extrusions

Those extrusions have closed paths, because I didn't have a way to divide end caps into triangles ("tessellation") to be able to display them. Here is a demonstration of a tessellation algorithm that supports having a hole in the 2D surface to be extruded:

http://www.glowscript.org/#/user/Bruce_Sherwood/folder/My_Programs/program/Tessellate2

Notice the numbering of the vertices. As it says in the source code, the basic tessellation algorithm is described on p. 422 of "Interactive Computer Graphics" 7th edition, Edward Angel and Dave Shreiner, Pearson 2015. At each stage of the tessellation you look for the leftmost vertex and form a triangle from it and its nearest neighbors along the path. If you find another vertex inside the triangle, you draw a line from the leftmost point to that point which splits the contour into two, and you then process each of these contours separately. This could be done recursively, but I'm no good at recursion so I just manage a stack of contours to process.

I needed a way to check whether a triangle has another vertex inside it, and I found a fast incomprehensible algorithm at

http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle

which I tested and confirmed that it works (it counts the triangle vertexes as being "inside" so one has to exclude those points from the test).

To handle a hole, I used a technique I found somewhere on the web (I can't now find it again). Notice in the display that the vertex numbering goes 0 to 4 CCW along the outer contour, then goes to vertex 5 on the inner contour, then CW 5 to 11, where vertex 11 is at the same location as 5, then out to vertex 12, then CCW 12 back to 0. The clever idea is that this ordering scheme makes a polygon that has no hole and which can be treated by the technique Ed describes in his book. I haven't attempted to handle more than one hole.

I did run into some problems with there being duplicate vertex locations (4 and 12, 5 and 11), so I actually move them a little ways apart during the processing of the hole-less shape, then bring them back together at the end.

The book by Angel and Schreiner is globally the most widely used graduate-level computer science textbook on 3D computer graphics and this latest edition is the first to be based on WebGL instead of the older OpenGL. It used to be that at the start of every semester Ed was swamped by email from all over the world written by students who were having difficulty getting together all the tools needed to write OpenGL programs, but now all they need is a browser and he gets no email at all about installation problems. Ed is a friend and a colleague here in Santa Fe, and I learned about WebGL from him. He's running a Coursera MOOC on computer graphics that might be of interest to you:

https://www.coursera.org/course/webgl

[Bruce Sherwood]

I was able to eliminate the temporary displacement of the duplicate points when I realized that when testing whether a point is inside a potential triangle I need to make sure that both vertices are excluded from the test if either of them is one of the triangle vertices.