Support approximation/triangulation of continuous faces

[hannobraun]

A continuous face is a face that connects to itself, instead of being bounded on all sides by edges. Currently, a continuous face can be created by sweeping a continuous curve. The only continuous curve supported right now is the circle, and you can sweep that into a cylinder. The side wall of the cylinder is the continuous face.

The approximation/triangulation code does not support continuous faces, which is why this is one of the last edge cases to still use the obsolete triangle representation (see #97).

Why it doesn't work

Currently, all approximation happens in 3D. If you ask a curve for an approximation, for example, it will return a list of 3D points. These 3D points are considered the canonical representation of these points. They are converted to 2D surface coordinates for the triangulation, then converted back to 3D (losslessly). This works well for bounded faces, but not for continuous ones.

Let's consider how the side wall of a cylinder is approximated. It starts with approximating the edges. While the side wall is not completely bound by edges, it still is bound by edges (circles) at the top and bottom. Here's how those are approximated:

The circle is approximated as a series of points, which are then connected to a series of line segments.

For triangulation, these circles are converted into cylinder surface coordinates.

In surface coordinates, the circles become straight lines at the top and bottom. A few things should be noted here:

• Remember, the circle is approximated as a connected series of line segments. I've drawn these small cross marks to indicate that these are not continuous lines.
• The leftmost and rightmost points of the circles connect back to each other (it's a circle, after all). I've drawn these dashed lines to indicate this, but of course, the actual connection is a straight line segment that overlaps with the other line segments that approximate the circle.
• The left and right sides of the face connect to each other. I've drawn these dashed vertical lines to indicate the connection.
• The leftmost points of the circles don't connect to where the face connects to each other. There's a gap there. That's because that leftmost point would be at 360°, which is the same 3D point as 0°. When converting that 3D point back to 2D, it will always end up as 0°.

So what happens if we feed this to the triangulation algorithm? First step, it finds triangles.

So far, so good. However, in this particular example, the face happens to be convex. It could just as well be concave, in which case the triangulation algorithm will create triangles outside of the face. It filters those out in step two, with the following steps:

1. Choose a point that is known to be outside of the face.
2. Draw a line from each triangle line segment to that point.
3. If that line crosses an odd number of edges, the line segment is inside the face. Otherwise it's outside.
4. Remove all triangles that have line segments outside of the face.

This works well enough for closed faces, that are completely bound by edges. It won't work for this continuous face. Since it's not bound by edges everywhere, drawing a line to the outside and counting the number of edge crossings will not work reliably. It will filter out some triangles, even though those are inside the face.

Here's how the result looks in 3D:

So how can this be fixed? I have a few ideas.

Possible solutions

Solution 1: Add virtual edges

We don't have edges that fully bound the face, but what if the approximation added "virtual" edges there? Then the face would be closed on all sides. The triangulation algorithm wouldn't have to know or care that the face connects to itself.

There's a problem though: Remember that drawing of the circles in surface coordinates above? The vertical dashed lines there are where these virtual edges would be added. But the circles only touch those virtual edges on one side! Even if we add virtual edges, there'd still be a gap.

This happens because, as I explained above, the approximation happens in 3D coordinates. And when converting those into 2D surface coordinates, the 3D point at 0° in circle coordinates will always be converted to 0°, never 360°. Which is why the circle connects back to itself, even in surface coordinates, instead of stretching in a straight line from left to right, perfectly bounding the surface at the top/bottom.

If approximation happened in the native coordinate system of the approximated object instead, in the case of the circle that would be the 1D curve coordinate system, then the circle approximation could return points in the range from 0° to 360° (inclusive). When converting that to 2D surface coordinates, we'd get those clean, straight lines, that would, together with the virtual edges, perfectly enclose the face.

To make that work while retaining the ability to always losslessly convert to 3D points, the canonical 3D point would have to be created alongside the native point representation. So those 0° and 360° points that the circle approximation returns, would internally both point to the same canonical point. Meaning they would never have to be converted to 3D using sine/cosine, which could result in slightly different 3D points being computed.

I like this solution, because it seems clean, and wouldn't require many extensions to the current conversion system.

Solution 2: Disallowing continuous faces

I'm aware some CAD kernels don't allow continuous faces. They require a face to have an edge where it otherwise would connect to itself, only allowing faces to stretch around 360°. Some even allow a face only to stretch 180°, meaning the cylinder side wall from our example here would have two edges.

I'm actually not sure if the 360° limitation would be of much help here, but the 180° limitation certainly would. And there are probably other good reasons for these limitations, so we might need to adopt them at some point anyways.

For now, I'm not a fan of this solution. While it would alleviate the need to upgrade the approximation code, it would push more complexity to code creating those faces (and possibly the user who uses that code to create faces), as these limitations would need to be enforced there.

---

I hope this was interesting to someone, because it was quite a bit of work to write 😄

But even it not, it was valuable. I initially thought that solution 1 would require much more complexity, to the point of being undesirable to implement. While writing, I realized how the challenges I saw could be overcome much more simply. Now it looks like this whole issue is not that big of a deal.