2
\$\begingroup\$

I'm writing a program that takes a 2D planar polygon and extrudes it to a 3D mesh with a given height. I identify triangle edges that are borders of the polygon and now I'm trying to automatically compute the two triangles required for the extrusion of the border. However, I'm stuck at how to compute the correct winding and normals

My start situation is this: I have the two coordinates of the edge (marked in white) and the normal of the original triangle (marked in orange)

Start situation

Using this information I'm trying to compute two triangles which should result in:

Extruded

The 4 vertices are easy to compute (just the two vertices of the edge and two more at a different height). The normal should be perpendicular to the original normal but to do that I need a second reference point. It doesn't seem to be as simple as using the centroid of the triangle.

The triangle winding confuses me. I need a counter-clockwise winding and I guess I could determine which vertices to use based on the normal but how is not immediately apparent to me.

\$\endgroup\$
  • \$\begingroup\$ I don't completely understand the problem you're having, but supposing you already have your vertices in the correct order, the normal can be calculated as cross(v1 - v0, v2 - v0). You can even normalize it if necessary. This works even for oblique extrusions. \$\endgroup\$ – Panda Pajama Jul 2 '14 at 10:26
  • \$\begingroup\$ Thats the problem, to determine the correct order of the vertices I need the normal, and for the normal I need the vertices in the correct order ;). So I need to use extra information to steer this process. For example the direction which the edge lies in relation to the centroid of the triangle and the original triangle's normal. But I'm not sure how. \$\endgroup\$ – Roy T. Jul 2 '14 at 10:32
  • \$\begingroup\$ So you can't even assume the points in the original polygon are in counter-clockwise order? \$\endgroup\$ – Panda Pajama Jul 2 '14 at 10:33
  • \$\begingroup\$ Oh the cross product of the original triangles vertices? Yes they are in correct order. \$\endgroup\$ – Roy T. Jul 2 '14 at 10:35
2
\$\begingroup\$

I don't completely understand the problem you're having, but this is a sketch of an extrusion algorithm

Supposing polygon is an array of 3D points in counter-clockwise order (I guess they don't have to be convex, or even coplanar), and direction is a 3D vector determining the direction in which you want to extrude your polygon, this is what I came up with (in no particular language)

function extrude(polygon, direction)
    triangles = []
    -- Top cap
    for p = 0 to count(polygon) - 2 do
        p0 = polygon[0] + direction
        p1 = polygon[p + 1] + direction
        p2 = polygon[p + 2] + direction
        normal = normalize(cross(p1 - p0, p2 - p0))
        triangles.push(new triangle(p0, p1, p2, normal))
    end

    -- Bottom cap
    for p = 0 to count(polygon) - 2 do
        p0 = polygon[0]
        p1 = polygon[p + 2] -- pointing down now...
        p2 = polygon[p + 1]
        normal = normalize(cross(p1 - p0, p2 - p0))
        triangles.push(new triangle(p0, p1, p2, normal))
    end

    -- Sides
    for p = 0 to count(polygon) do
        p0 = polygon[p]
        p1 = polygon[(p + 1) mod count(polygon)]
        p2 = p0 + direction
        p3 = p1 + direction
        normal = normalize(cross(p1 - p0, p2 - p0))
        triangles.push(new triangle(p0, p1, p2, normal))
        triangles.push(new triangle(p0, p2, p3, normal))
    end

    return triangles
end

The normals created by this snippet point outwards for each face. You could also average them with the normal of the adjacent face to create a softer look for polygons with lots of faces...

Would something like this work for you?

\$\endgroup\$
  • \$\begingroup\$ Thanks, with these pointers I got it to work. I was thinking way too difficult somehow :). \$\endgroup\$ – Roy T. Jul 2 '14 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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