Function to re-orient mesh faces


#1

Tried to find Julia implementation of re-orienting faces of a mesh. Does an implementation exist?

Geometries from external sources not necessary have their faces oriented consistently (even if possible). If visualized in GLVisualize.jl, coloring vertices of faces not oriented consistently does not come out nicely.

Example Julia code using GLVisualize with a screenshot linked with non-consistent mesh https://i.stack.imgur.com/N9lS1.png .

using GLVisualize, GeometryTypes, GLWindow, GLAbstraction, Colors

vertices = [
 0.0  0.0 0.0
10.0  0.0 0.0
10.0 20.0 0.0
 0.0 20.0 0.0
 0.0  0.0 5.0
10.0  0.0 5.0
10.0 20.0 5.0
 0.0 20.0 5.0
]

faces = [
7 6 5 # 5 6 7 for consistent orientation
5 7 8
1 4 3 
1 3 2
1 2 6
1 6 5
2 3 7
2 7 6
3 4 8
3 8 7
4 1 5
4 5 8
]

v = [ Point{3,Float32}( vertices[i,1:3] ) for i=1:size(vertices,1) ]
f = [ Face{3,UInt32}( faces[i,3:-1:1] ) for i=1:size(faces,1) ]

mesh =  GLNormalAttributeMesh(
            vertices=v, faces=f,
            attributes=RGBA{Float32}[RGBA{Float32}( 0.0, 1.0, 0.0, 1.0 )], attribute_id=zeros( length( v ) )
        )

window = glscreen()
_view( visualize( mesh ), window )

I could write a slow brute-force algorithm, which would be slow. Better to ask first.

A recent article suggests the algorithm can be O(N), see https://arxiv.org/pdf/1512.02137.pdf

Note: one should be careful not to look at source implementation of mesh re-orientation in software with non-compatible licenses.

Note2: copied the topic from https://stackoverflow.com/questions/46759661/function-to-re-orient-faces-in-julia based on the suggestion there.


#2

There is an open-source implementation this algorithm (using a stack) in my BESS library: http://hogwarts.ucsd.edu/~pkrysl/software/BESS.tar.gz


#4

Thanks Petr for link.

I’ll have a look. Based on a very quick browse, is it in bess.c function start_manifold_s ?


#5

I would start with smesh_orient() in the file smesh.c. The description of the algorithm is in our paper [http://onlinelibrary.wiley.com/doi/10.1002/nme.94/abstract]. The relevant algorithm is this


mf = mesh face, me = mesh edge


#6

To compare with the arxiv paper: