1
\$\begingroup\$

Following a very helpful post on another forum I've found a simple algorithm that takes an array of 2D vectors and creates a triangle strip. I've modified the source code for my purposes. I haven't tested it yet, but it should do the trick.

public static void PolyLineToTriangleStrip(Vector2[] pts, bool closed, float thickness, List<Vector2> vertices, List<int> indices)
    {
        var numPts = pts.Length;
        vertices.Clear();
        indices.Clear();
        for (int i = 0; i < numPts; ++i) {
            int a = ((i - 1) < 0) ? 0 : (i - 1);
            int b = i;
            int c = ((i + 1) >= numPts) ? numPts - 1 : (i + 1);
            int d = ((i + 2) >= numPts) ? numPts - 1 : (i + 2);
            var p0 = pts[a];
            var p1 = pts[b];
            var p2 = pts[c];
            var p3 = pts[d];

            if (p1 == p2)
                continue;

            // 1) define the line between the two points
            var line = (p2 - p1).normalized;

            // 2) find the normal vector of this line
            var normal = new Vector2(-line.y, line.x).normalized;

            // 3) find the tangent vector at both the end points:
            //      -if there are no segments before or after this one, use the line itself
            //      -otherwise, add the two normalized lines and average them by normalizing again
            var tangent1 = (p0 == p1) ? line : ((p1 - p0).normalized + line).normalized;
            var tangent2 = (p2 == p3) ? line : ((p3 - p2).normalized + line).normalized;

            // 4) find the miter line, which is the normal of the tangent
            var miter1 = new Vector2(-tangent1.y, tangent1.x);
            var miter2 = new Vector2(-tangent2.y, tangent2.x);

            // find length of miter by projecting the miter onto the normal,
            // take the length of the projection, invert it and multiply it by the thickness:
            //      length = thickness * ( 1 / |normal|.|miter| )
            float length1 = thickness / Vector2.Dot(normal, miter1);
            float length2 = thickness / Vector2.Dot(normal, miter2);

            if (i == 0 && !closed) {
                vertices.Add(p1 - length1 * miter1);
                vertices.Add(p1 + length1 * miter1);
            }

            vertices.Add(p2 - length2 * miter2);
            vertices.Add(p2 + length2 * miter2);

            if (closed && i == numPts-1) {
                indices.Add(i * 2);
                indices.Add(i * 2 + 1);
                indices.Add(0);
                indices.Add(i * 2);
                indices.Add(0);
                indices.Add(1);
            } else {
                indices.Add(i * 2);
                indices.Add(i * 2 + 1);
                indices.Add(i * 2 + 2);
                indices.Add(i * 2);
                indices.Add(i * 2 + 2);
                indices.Add(i * 2 + 3);
            }
        }
    }

Feeding it a sequence of vectors would produce something a bit like this:

enter image description here

However, I want to complicate matters by introducing another problem - 3 way joints (or rather n-way).

It must be possible to do this by building on the algorithm, but I'm not sure how I would modify the above algorithm to draw an n-way miter joint with perfect angle distribution like so:

enter image description here

enter image description here

enter image description here

The highlighted lines represent the source lines that would be fattened up by the algorithm.

I calculated and drew these in blender, unfortunately I'm at a bit of a loss to do it programmatically.

Obviously this cannot be achieved with simple line sequences, but that's beside the problem. All that' needed is a central point and n-ammount of points that represent the ends of outcropping lines, and then an algorithm to calculate the outer edges of the required shape.

\$\endgroup\$
1
\$\begingroup\$

You will need to operate on a graph data structure, rather than a list / array. So the flow of the algorithm will no longer be as linear as you are used to.

I'm assuming you're really only speaking in term of 2D planar problem, not the same structure built / jointed in 3D, as the latter would enhance the complexity by a considerable margin.

Iterate each node in your graph, each of which should contain a list of those edges connecting it to neighbouring nodes. Every time you have a conflux of lines meeting at this node (whether 2, 3, 4, 5 or whatever number) you need to get the angle between each pair of adjacent lines (meaning you'll need to have some way of knowing which lines are adjacent, by the way - I'd suggest first ordering them in a list by increasing angle). Then insert a new point (line) at an angle halfway between them. Your 2nd T-junction example above is useful in showing this: The left hand side has to split an angle of 180 degrees between the lines - the line going out is thus at 90 degrees to both of them. Again on the right hand side of the same drawing, the same principle applies, here splitting 90 degree corners into 45 degree angles, above and below the lateral line.

So, you can create those new separating lines / points, but you also need to know how long they need to be in order to keep the "band" thickness the same throughout. The diagonal lines in your 2nd diagram are longer than the matching lines at the end of structure, because they are the hypotenuse of a triangle whose one side is not marked in your diagram, but which runs from the tip of those diagonal 45 deg lines, directly inward and perpendicular to the "spine" until it touches the spine, and is parallel to that line which caps the arm. So in each case you need to use that half-width of each "band" to calculate the hypotenuse length. Indeed, that should be a parameter your specify as a setting before startup, or as a draggable slider "thickness" which reconfigures the mesh each time you drag it.

Obviously, once you've created all the necessary points in this way, you can create the actual lines by retriangulating those accordingly. I tend to triangulate meshes in a second pass after constructing the vertices. This may mean you need to store some intermediate data to know what you're doing once you get to the triangulation pass.

This should give you enough to work from.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.