CODEWITHSUNDEEP
algorithm3dcomputational-geometry
innochenti
innochenti

Reputation: 1103

inverse task of tessellation

As input I have a set of triangles that form concave mesh with holes. Each triangle consist of three vertices: (vi,vj,vk),... No adjacency information is provided. Algorithm have to "union" the set of triangles with the same normal into polygon. So output is (pi,pj,pk,...,ps),...

For example(see picture below), let say we have mesh that consist of triangles

(v0,v1,v4), (v1,v3,v4), (v1,v2,v3)

(v2,v6,v4), (v6,v5,v4).

As output we have:

(p0,p1,p4)

(p1,p2,p3,p4)

enter image description here

I'm looking for efficient algorithm that solves problem described above. Any suggestion, tips or articles is appreciated.

Upvotes: 3

Views: 1150

Answers (2)

MoonKnight
MoonKnight

Reputation: 23833

Look at adaptive mesh coarsening algorithms. These are typically used in advanced software for Computational Fluid Dynamics (Ansys CFX, CD-Adapco Star CCM+ etc.) / Structural Dynamics (Anasys et al.). Where automatic refinement and coarsening of a given mesh is advantageous.

Some free papers to look at on this subject, that will give you a strong starting point are:

  1. https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/coarsening.pdf

  2. http://tetra.mech.ubc.ca/ANSLab/publications/coarsen.pdf

  3. http://www.cs.cmu.edu/~glmiller/Publications/MiTaTe98.pdf (This is fairly mathematical)

Additional Google searches in the area of adaptive mesh refinement algorithms will reveal similar papers on the subject.

Edit. A basic and well established method for the adaptive mesh coarsing is the Edge Collapse Method which involves reducing an edge to a single vertex and thereby removing two elements. Li X., Shephard M.S., Beall M.W. “3-D anisotropic mesh adaptation by mesh modifications.” Computer Methods in Applied Mechanics and Engineering, 2004. has a great coarsening algorithm which is defined in pseudo-code as

for all edge in short edge list do
    for all vertex that bounds the current edge do
        if vertex is not yet tagger then
            append vertex to dynamic list
            tag vertex to be in dynamic list
        end if
    end for
end for
while vertices not tagged processed in dynamic list do
    get an unprocessed vertex Vi from the list
    get Ej , the shortest mesh edge in transformed space connected to Vi
    if the transformed length Ej is greater than Llow then
        remove Vi from the dynamic list
    else
        evaluate edge collapse operation of collapsing Ej with Vi removed
        if the edge collapse would create an edge longer than Lmax then
            evaluate relocated vertex Vi
        else if the edge collapse would lead to 
            at/inverted elements then
            evaluate the swaps(s)/collapse compound operation
        end if
        if any local mesh modication is determined then
            tag neighbouring vertices of Vi in the dynamic list as unprocessed
            apply the local mesh modication
            remove Vi from the dynamic list if it is collapse
        else
            tag Vi as processed
        end if
    end if
end while

This is taken from an impressive Masters thesis I have used in the past. It can be found here

I hope this helps.

Upvotes: 1

SmacL
SmacL

Reputation: 22922

Off the top of my head;

  • Triangulate each polygon, to get a set of triangles.
  • For all triangles in all polygons, assign a group number based on the normal
  • For every triangle T = (va,vb,vc) created the adjacency information E = (ab,bc,ca) where ab is a link / index to the triangle adjacent to T at edge a,b.
  • Trace the outline of each new polygon by searching for any edge where the two neighbouring triangles are not part of the same group, following to the next edge with the same relationship, and repeating until you get back to the first edge.

Note you will also have to contend with a NULL edge type at the edge of your TIN hull, but this is straightforward.

The slowest bit here is developing the adjacency information which can be done in O(n log n) by many good TIN creation algorithms.

Upvotes: 2

Related Questions