3
$\begingroup$

I'm trying to find an algorithm for finding all faces in a wireframe mesh. Wireframe means only the vertices and edges are given as input. There is no restriction on the number of edges a resulting face can have and the face can be convex or concave.

Simple Example

In a wireframe of a square-based Pyramid there are 5 faces - the base is a square and the sides are triangles.

The algorithm should produce 5 sets of edges (since there are 5 faces). One set of edges would contain the 4 edges that make up the square base and then 4 sets of 3 edges for each side of the pyramid.

square-based Pyramid

Bonus

It would be a bonus if the algorithm can create an edge winding resulting in all faces pointing inwards or outwards.

$\endgroup$
  • 4
    $\begingroup$ What are your thoughts on the question? Have you tried to figure it out yourself? Have you tried looking at online resources? $\endgroup$ – Yuval Filmus Aug 30 '16 at 21:18
  • $\begingroup$ If you have vertices and edges - connect them. Adjacent edges will constitute face. After reading them output in one winding. If it does not matter which one and you have connected mesh without encoded holes any starr will do, just keeping in mind that normals of adjacent faces cannot flip. Where is the catch? What went wrong? $\endgroup$ – Evil Aug 30 '16 at 22:18
  • 3
    $\begingroup$ This problem reduces to finding all chordless cycles in a planar graph. Have a look at: stackoverflow.com/questions/838076/… $\endgroup$ – Mario Cervera Aug 30 '16 at 22:44
3
$\begingroup$

After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work.

This problem reduces to finding all chordless cycles in a planar graph.

This was one of my first thoughts early on, but this doesn't work when you consider the following:

      5-------f-------6
     /               /|
    /               / |
   e               g  |
  /               /   h
 /               /    |
1-------a-------2     7
|               |    /
|               |   /
d               b  i
|               | /
|               |/
4-------c-------3

Given three sides, the answers should be: 1 2 3 4 1, 1 5 6 2 1, and 2 6 7 3 2. Unfortunately, 1 4 3 7 6 5 1 is considered chordless and is not a correct answer.

If you have vertices and edges - connect them. Adjacent edges will constitute a face.

Unfortunately, without weighting or accounting for spatial information you'll end up running into the edge cases described below.

Edge Cases

The highlighted "face" in the following two examples should not be in the solution. These highlighted faces are referred to as "internal faces" (yes, even the highlighted face on the right is considered an internal face in graphics terminology).

enter image description here

Then there are other issues like objects with distinct subgraphs, holes, and ambiguous face loops.

enter image description here

The Solution

While researching I found the paper: A new algorithm for finding faces in wireframes by Peter A. C. Varley and Pedro P. Company (full text here). The algorithm attempts to solve the problem for both 2D and 3D input. The solution is non-trivial: the setup alone is polynomial time.

Basic Description

Start by creating a set of directed edges from all edges of the graph (so the initial set is of size 2e were e is the number of edges). These sets of directed edges are stored as the vertices that comprise them and are referred to by the paper as "strings". Each string must be given a priority according to the geometry around it (e.g. there will be a different priority assigned depending upon if it touches a triangle or quadrilateral).

You then exhaustively attempt to merge the strings by finding ones that start were another one ends. You do this by picking the highest priority strings first.

When merging strings you remove the original strings from the set and add the merged version back in. When the merge is preformed a new priority must be calculated using the existing priorities and spatial information about the strings themselves (the spatial calculation differs depending upon if your running the algorithm against 2D or 3D input).

Strings are removed from the set if their first and last vertex match (that means a loop was found). You continue repeating the algorithm until the set is empty.

Complete Algorithm

Here is the complete algorithm copied directly from the paper. Hopefully the description I gave above helps a bit. The paper is very well written and its a good read for anyone interested in the topic.

Some steps in the algorithm come down to guesswork and assumptions about the input. For example, step #3 says to "choose a trihedral vertex", but if there is no trihedral vertices (e.g. octahedron or icosahedron) then the paper suggests breaking the symmetry by assuming that an arbitrary triangular loop of edges is a face.

(Top level of algorithm)
Create initial master string list, two entries per edge
Assign priorities to all strings in the list
Choose a trihedral vertex, and concatenate two strings at this vertex
While there are strings remaining in the master list
Examine the master list for the presence of forced concatenations
    If there are forced concatenations, perform them
    Otherwise, examine the master list for the presence of voluntary mergers
    If there are voluntary mergers, perform them
    Otherwise, examine hypotheses (see subroutine below)
(Subroutine: Examine Hypotheses)
Take a working copy of the master string list
Repeat
Take the highest-priority string S in the working string list
Find the string T which has the best mating value with S
Concatenate S and T, and reduce the priority of the resulting string
Repeat
Examine the working string list for the presence of a forced concatenation
If there is a forced concatenation, perform it
    If the forced concatenation created a new face, update the master list accordingly and exit this subroutine
If there is no forced concatenation
    If there is a voluntary merger available, create the face, update the master list accordingly and exit this subroutine
    Otherwise exit this inner loop

Other Solutions

According to the paper, the current face-finding algorithms generally fall into four categories: exhaustive search approaches, pseudo-random approaches, shortest-path approaches, and heavily mathematical approaches. It does a good job citing other possible solutions along with their advantages and disadvantages.

Keep in mind that this algorithm acknowledges that it still produces incorrect output for certain input. However, this is still an improvement over the previous best solution which fails for even more input.

$\endgroup$
  • 1
    $\begingroup$ Nice analysis. Note that, if we only consider "external faces", the reduction to finding chordless cycles should work. When reducing one problem to another, sometimes the original input cannot be used as is (that is, it requires some kind of pre-processing). Then, we can solve the probem using the modified input, and, finally, post-process the result to obtain a solution to the original problem. In your wireframe mesh problem, the original 3D object must be "unfolded". This way we obtain a 2D object (represented as a planar graph) with some vertices of the original object duplicated. $\endgroup$ – Mario Cervera Sep 1 '16 at 7:55

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.