Does a 3D Half-Edge Data Structure Exist?

• Ole Lindberg
In summary, the individual is seeking a data structure for an unstructured quadrilateral mesh and asks if a three-dimensional half-edge or "half-face" data structure exists. They also ask for recommendations on data structures for an unstructured mesh of polygons, tetrahedrals, and quadrilaterals. A referenced article suggests a binary tree representation as the most efficient option.
Ole Lindberg
Hello Everyone

I'm currently working on a unstructured quadrilateral mesh for a discontinuous galerkin free surface flow model. I use the half-edge data structure in the two dimensional code. Does something like a half-edge or "half-face" three dimensional data structure exist.

Otherwise which data structure do you prefer for an unstructured mesh of polygons tetrahedrals and quadrilaterals.

Greetings

Ole Lindberg, Denmark

While I don't know much about your application, I found a reference on the web that suggested a binary tree representation as the most efficient and have attached the reference for you:

http://onlinelibrary.wiley.com/doi/...10)49:10<1327::AID-NME996>3.0.CO;2-L/abstract

there's a link to a PDF following the abstract that describes the details and is an excerpt from the book they are selling.

So it looks like the tree is useful as you continue to fracture the surface into smaller and smaller pieces they can be added to the existing node from which they came.

1. What is a half-edge data structure in 3D?

A half-edge data structure is a way of representing 3D mesh data in computer graphics. It stores information about the vertices, edges, and faces of a mesh, making it easier to manipulate and perform operations on the mesh.

2. How does a half-edge data structure differ from other data structures?

A half-edge data structure is unique in that it stores information about both the edges and the faces of a mesh. This makes it more efficient for certain operations, such as finding neighboring faces or edges.

3. What are the benefits of using a half-edge data structure?

One of the main benefits of a half-edge data structure is its ability to efficiently perform operations on a 3D mesh, such as finding neighboring faces or edges. It also allows for easy manipulation of the mesh, such as adding or removing vertices, edges, or faces.

4. Are there any limitations to using a half-edge data structure?

One limitation of a half-edge data structure is that it can be more complex to implement compared to other data structures. It also may not be the most efficient for certain operations, such as finding the closest point on a mesh.

5. How is a half-edge data structure used in real-world applications?

Half-edge data structures are commonly used in computer graphics and 3D modeling software. They are also used in simulations and scientific visualization to represent complex 3D geometries. Additionally, they are used in virtual reality and augmented reality applications to render 3D environments in real-time.

• Topology and Analysis
Replies
9
Views
2K
• Programming and Computer Science
Replies
8
Views
2K
Replies
13
Views
2K
• Programming and Computer Science
Replies
1
Views
2K
• General Math
Replies
7
Views
2K
• Sci-Fi Writing and World Building
Replies
2
Views
3K
• Beyond the Standard Models
Replies
6
Views
4K
• Sci-Fi Writing and World Building
Replies
1
Views
3K
• Beyond the Standard Models
Replies
2
Views
3K
• Beyond the Standard Models
Replies
25
Views
5K