2

I need to generate a triangulated mesh between two or more 3d contour lines. The contour lines are simply an array of points and are always closed.

Example contour lines

I've tried using the Poly2Tri library to do a delaunay triangulation, but this doesn't work so great because it only works in 2d, and while I can get it to work in 3d, it doesn't deal with with contour lines that stack vertically (ie: have the same coordinates when the 3rd dimension is discarded)

Does anyone know what sort of algorithm is best to use and ideally an existing library I can use from a c# application?

Hamish
  • 579
  • 5
  • 20
  • You could do it with an R script (see https://www.r-project.org/about.html) and control execution of the script from a C# app (see https://stackoverflow.com/questions/4485943/executing-r-script-programmatically). I wouldn't do it that way myself but if you want a reason to learn R... – cymorg Apr 23 '19 at 23:57
  • Does your data structure allows you to work with strips, bounded by two neighboring contour lines? If yes, you can triangulate your surface strip by strip. Also please see `https://en.wikipedia.org/wiki/Triangle_strip` – HEKTO Apr 25 '19 at 18:44
  • 1
    @HEKTO, I can work with tri-strips sure, but that doesn't define the algorithm to generate the indices required for generating a sensible tessellation. – Hamish Apr 26 '19 at 02:41
  • What exactly do you call "indices" here? – HEKTO Apr 26 '19 at 03:26
  • 1
    @HEKTO I'm not sure how to answer. I'm referring to triangle indices for the resulting mesh. I need to construct a mesh given these contour lines as input. The question is, what algorithm to use to define the mesh. A mesh is a collection of positions and a collection of indices to define the triangles. Given I already have the positions from the contour lines, the only thing the algorithm needs to output is the collection of indices. – Hamish Apr 28 '19 at 23:44
  • It looks like you call "indices" the data structure, storing information about triangles. When designing such a structure you have to decide which operations on this structure you want to be most efficient – HEKTO Apr 29 '19 at 02:30
  • As for the algorithm - if you have two "concentric" polylines, then you'll be able to construct triangles between them one by one traversing these polylines. On each step you'll have two choices - make sure you construct triangles maximizing their minimal angle (or minimizing the maximal one). It's simple heuristic algorithm, but it'll work... You don't need Delaunay – HEKTO Apr 29 '19 at 02:36

1 Answers1

1

You can keep using the 2D Delaunay algorithm, but do it between two neighboring layers (z1, z2) each time. (z1 < z2)

Assume contour lines are sampled and stored as a set of (x,y,z) in counter-clockwise order on z-plane. You need to construct a set of boundary/hole points for triangulation:

  • detect or compute overlapping line segments (x1, y1, z1)(x2, y2, z1), and (x1, y1, z2)(x2, y2, z2)
  • move (x1, y1, z1) inwards by a small offset, along the direction of average normal of two neighboring line segments. Similarly, move (x2, y2, z1) inwards; move (x1, y1, z2)(x2,y2,z2) outwards. Now the two (or more) contour lines are separated, and you get two (or more) boundary/hole point set.
  • apply Delaunay trangulation within the area defined by boundary and holes (i.e. generate random points, drop points outside boundary or inside holes, construct triangle). I assume Poly2Tri will handle the cases where a triangle partially cover a hole. Once you have all triangles in (x,y) plane, restore the offset and compute z by interpolating original data.

Do triangulation again for (z2, z3) layer, so on and so forth. Note that the hole/boundary points at z2 remains the same, but if overlapping happens, instead of moving inwards, it's now moving outwards. At the end, combine all triangles into one mesh.

dchneric
  • 121
  • 5
  • Thanks @dchneric, I had considered offsetting overlapping points, I guess I was hoping for a more tailored algorithm. But it might be me best bet. I'll give it a shot, thanks for the input. – Hamish Apr 28 '19 at 23:45
  • @Hamish Adding offset is just one way of flattening extended contour map to 2D space to apply triangulation. You can try other mapping methods too. Direct triangulation in 3D is also possible, as long as you have a set of sampled points, and your data structure can answer the question "do these 3 points form a valid triangle on the surface?" Then you can incrementally construct triangles by selecting unclosed points that are nearest to your existing mesh, and adding the first valid one to it. – dchneric Apr 29 '19 at 18:48