This issue attempts to explore some of the options for
- Improving tessellation/triangulation performance
- Support tessellation/triangulation in 3D
Current implementation in p5py
The existing implementation uses the triangle
python module to triangulate shapes before sending them to the GPU. The triangle
module is in turn a wrapper around the Triangle C library written by Jonathan Shewchuck that implements the Delaunay triangulation algorithm.
This site notes that the Triangle Library by Prof. Shewchuck has several deficiencies. In particular,
- It does not like duplicate vertices or duplicate edges. 'Duplicate' in this case is relative to numeric precision: For a building 10-100 meters in size, two vertices within 8cm of each other, defining a very short edge, can cause Triangle to crash.
- It does not like it when a hole (inner ring) in the polygon has a vertex in the same location as one in the outer ring (crash).
In fact, the problems mentioned above are rather minor. The biggest problem of all is probably the fact that triangle
does not support 3D points.
Current implementation in Processing and p5.js
Maybe we can reference the triangulation implementations in other branches of the processing language? Here's what I found:
For Processing (OpenGL backend), GLU was referenced through the JOGL binding, evidenced by source files PGraphicsOpenGL.java#L10985 and PJOGL.java#L605. Given that we don't have JOGL on Python and GLFW doesn't support GLU, we might have to look for other options.
For p5.js, tessellation support was achieved via libtess.js, which uses the GLU tessellation algorithm but rewritten in JavaScript (reference).
Exploring our options
OpenGL/GLU
From first glance, using OpenGL is as simple as using the following API:
gluTessBeginPolygon(tess, user_data);
gluTessBeginContour(tess);
gluTessVertex(tess, coords, vertex_data);
...
gluTessVertex(tess, coords_n, vertex_data);
gluTessEndContour(tess);
gluTessEndPolygon(tess);
(Code example adapted from songho.ca)
However, further searches indicated that this API is not part of OpenGL core, but part of GLU (OpenGL Utility Library). According to GLFW
GLU has been deprecated and should not be used in new code.
So GLFW isn't helpful here.
I asked the question of how to use GLU bindings on the vispy Gitter chat after not finding anything related to GLU on their documentation. I did get a response from vispy maintainers very quickly. Thank you! However, he confirmed that vispy does not currently support the tessellation API.
Short answer is no. Long answer: I'm not familiar with the gluTess API specifically, but I'm guessing this has to do with tessellation shaders, right? Currently VisPy does not have any support for tessellation shaders but I think there are PRs trying to add it. In the last year we added support for geometry shaders which really set up the interfaces for adding additional shaders like the tessellation shaders, but so far these have not been added.
---@djhoese
Given that our current dependencies don't have this functionality, another option is to introduce a new library called PyOpenGL, which offers a wrapper for GLU (in addition to a lot more OpenGL functionality). Since we already have vispy.gloo
for making OpenGL calls, we may want to discuss whether it's worth it to introduce another dependency with potentially the same capability as vispy
but only use it for tessellation.
Scipy
Scipy also has a function that performs the Delaunay triangulation algorithm. Instead of wrapping around Prof. Shewchuck's library, it wraps around Qhull. This supports both 2D and 3D. However, the Qhull website says the library only works with convex hulls, so non-convex objects (e.g. objects with holes created by begin_contour
) wouldn't work.
Moving Forward
Between scipy and PyOpenGL, I am leaning towards PyOpenGL because it uses the same underlying algorithm as the Processing Language and p5.js while also supporting non-convex shapes. The downside is that it's a rather large library that overlaps in features with vispy. If you have an opinion on this subject, leave a comment down below!
Roadmap
Here's my tentative plan to improve tessellation in p5py:
- [x] Build sample scenes for profiling
- [x] Profile performance of master branch as baseline
- [x] Fix obvious performance issues (if any)
- [x] Replace
triangle
with PyOpenGL, or another triangulation library
- [x] Profile again and compare to baseline
- [x] Implement parts of
begin_shape
and end_shape
that only requires trivial/no triangulation in 3D (i.e. POINTS
, LINES
, TRIANGLES
, TRIANGLE_FAN
, TRIANGLE_STRIP
, QUADS
, and QUAD_STRIP
).
- [x] Implement the complete version of
begin_shape
and end_shape
in 3D (i.e. TESS
in addition to the modes mentioned above).
- [x] (Stretch goal) Implement
begin_contour
and end_contour
in 3D.
- [x] Document API changes
enhancement GSoC2020