Algorithm for offsetting edges of 3D triangle mesh

Question

I have a 3D triangle mesh, and I'm looking for an algorithm to offset all the ~~un-bordered edges~~ border edges of the mesh inwards, along the surface of the triangle mesh.

I've looked at Clipper as mentioned in An algorithm for inflating/deflating (offsetting, buffering) polygons, but it doesn't really handle 3D nor can it preserve the triangle mesh, and I'm not sure that re-triangulating the resulting borders to match the original input mesh is any easier of a problem to solve.

Any suggestions as to how I might accomplish this?

The problem seems to be somewhat ill-defined; although the picture gives some rough idea, what exactly is a non-bordered edge? — Codor, Sep 04 '15 at 18:32
I think by "un-bordered edge" you must mean an edge on the border, as in your figure? I.e., an edge that is shared by just one, rather than two triangles? I would handle it in an ad hoc manner, computing the new offset edge coordinates. I don't think you will find code for this specific task. — Joseph O'Rourke, Sep 04 '15 at 19:05
Sorry about that, Joseph is correct. Where this gets more complicated is that in some cases new triangles need to be created (happens in the picture), and in others, triangles need to removed. Sometimes, even triangles that aren't along the edge will be affected, for example if they are bordered by triangles that are on the edge but that are smaller than the offset distance. — Jeff, Sep 04 '15 at 19:36
hmm I would 1. convert your mesh to set of planar faces (just the border polylines `your bold black lines` not the full triangulation) 2. then shrink/trim/shift/cut the right polylines according to your task `which is not described well enough` 3. and after that triangulate back to mesh. This way you work in 2D space where your algorithms you linked should work. if your mesh has curved faces/sides this will not work (unless you change the face selection method from planar to boundary) — Spektre, Sep 05 '15 at 06:15
@Spektre for any mesh with coplanar triangles, there could be a similar mesh where none of the triangles are coplanar, at which point I'm back to where I started. Combining coplanar triangles might help solve particular cases, but I don't think it gets me closer to a solution that works for all of them. — Jeff, Sep 05 '15 at 17:05
i might have an answer... but your question is extremely unclear. 1. why does your "new" green trapezoid have 4 green triangles, when your original trapezoid only had two triangles? 2. why is the bottom bar of your "blue x thingy" paralell with one axis, but the "feet" are at a different angle? sorry to sound harsh. — don bright, Nov 20 '15 at 05:28
@donbright Sorry for the late response: 1. Perhaps the original two triangles are not quite coplanar. For the result to be correct, each result triangle must be contained within a single of the original triangles. The 4 triangles could be combined into 2 if everything is coplanar, but that is just unnecessary complexity since we'd still need to handle the similar case where they aren't coplanar. 2. My preference would be offset the triangle edges a set distance along the XZ plane (if Y is up), rather than a set distance along the plane of the triangle. Does that help clear things up at all? — Jeff, Mar 02 '16 at 03:33

bebbo · Answer 1 · 2021-04-01T09:15:29.930

Based on the assumption that a border edge is shared by only one triangle:

You need

a map edge -> triangle : e2t
a multi map point -> triangle : p2t
a set to track already modified points: pts

then this will do it

for all triangles do:
    for each edge do:
        normalize edge: e.p1 < e.p2
        if the egde is in e2t: put edge/dummy into e2t
        else: put the edge/triangle into e2t

    for each point do:
        put point/triangle into p2t

prune all edge/dummy from e2t

while e2t is not empty:
    remove first edge/triangle from e2t -> e,t
    calculate replacement points for t: e.p1,e.p2 -> q1,q2
        unless the point is in pts
    use p2t to update all triangles with e.p1->q1 and all with e.p2->q2:
        update e2t if the modified edge is in there
    add each modified point to pts

to caclulate the replacement points you have to find the sharing triangles not in the same plane -> this defines the direction do move the point.

it looks like this then:

Algorithm for offsetting edges of 3D triangle mesh

1 Answers1