# Algorithm for constructing doubly connected edge list in 3d

This post explains how to construct double connected edge list in 2d. One of the steps in the algorithm is to sort the halfedges around a vertex in clockwise order. However this will not work in 3d. We can project the halfedge coordinates onto 2d viewplane and sort them that way (if the construction is user interactive). However this would make the construction dependent on the user view.

What sort of algorithm would we use for 3d case of double connected edge list?

• It depends, if you want to represent a mesh you can look into "open mesh" implementation so you can find what you need to do to define face and vertices. If you want a general DCEL more than defining your self manually each point, half edge and face there's no much you can do. CGAL has a dcel representation of planar map, which as far I'm aware it's quite a general object you can represent with DCEL (so maybe they have specialized API for these object representation in terms of DCEL) – user8469759 Sep 10 '20 at 3:37
• – D.W. Jan 14 at 20:48
• All you really need is a reference vector for each face. So if you know which side is outside. Then you can do this. Also following from this if you know the front side of one well formed, nonmanifold and continious mesh, then you can figure out all of them. So a camera view can be a starting point.... – joojaa Feb 9 at 18:01

## 1 Answer

The problem statement in the linked post says that only the vertices and edges are input to the algorithm, but I don't think it's possible to do this unambiguously in 3D without additional input about the faces of the mesh. In the 2D case, since the input is specified to be a planar graph, the faces are unambiguous: any region in the plane contained within an edge loop, and empty of edges in its interior, is a face. However, in 3D, you don't know which edge loops should be faces and which shouldn't.

Consider a cube, represented as just vertices and edges: you would want the "usual" 6 sides of the cube to be treated as faces, but you wouldn't want the algorithm to create additional faces that stretch across the diagonal of the cube, internally. But there is no way for the algorithm to know that. Moreover, the vertex/edge mesh might not even be possible to assign faces to in a sensible way; it might have non-planar faces, might be non-orientable (e.g. Möbius strip) or non-manifold.

Typically in 3D applications we would have the mesh faces already defined, and we can assume it to be a manifold, orientable mesh. With the face data as input to the algorithm, such as by lists of edges or vertices in counterclockwise order around each face, then it becomes straightforward (if tedious) to figure out the half-edge relationships.