# Half edge mesh

2020-12-06 10:08:17

### Half grid structure (Half edge mesh)

#### 1、 Representation of grids

In computer graphics , There are three data structures for representing surface grids , It's a list of faces ( List of faces)、 Adjacency matrix (Adjacency matrix)、 half-edge structure (Half-edge).

For example, the plane column shows :

Examples of half side structures :

#### 2、 Grid Classification

Manifold grid (manifold mesh)
Non manifold mesh (non-manifold mesh)

If each edge of the mesh is shared by at most two patches , So this grid is a manifold network , Otherwise, it's called a non manifold network .

Examples of non manifold networks :

#### 3、 Half grid structure (Halfedge)

Half grid structure

Half data structure & Mesh subdivision and simplification

doubly connected edge list Or call it half-edge data structure.
The biggest feature is half , Each side is divided into two halves , Each half is a directed side , In the opposite direction . If an edge is shared by two patches , Then each patch can have its own half . If an edge is occupied by only one patch （ Boundary edge ）, Then the patch has only one half of the edge , The other half is idle . Each half stores only its starting point pointer , Half side data structure only supports manifold network . The edges face each face in a counter clockwise direction .

#### 4、 Examples of grid half structure

Take a square for example , This is c4d Derived square of .obj file :

``````# WaveFront *.obj file (generated by CINEMA 4D)

v -50 -50 0
v 50 -50 0
v -50 50 -0
v 50 50 -0
# 4 vertices

vn 0 0 1
# 1 normal

vt 0 0 0
vt 0 1 0
vt 1 1 0
vt 1 0 0
# 4 texture coordinates

f 2/4/1 4/3/1 3/2/1 1/1/1

``````

Extract vertex and face information :

v: It means a vertex , [i] Index representation , v[0] On behalf of the apex 0 individual . The representation of a side is similar to , use e.

``````{

"verts":[
{

"x":-50,
"y":-50,
"z":0
},
{

"x":50,
"y":-50,
"z":0
},
{

"x":-50,
"y":50,
"z":0
},
{

"x":50,
"y":50,
"z":0
}
],
"faces":[
[1,3,2,0]
]
}
``````

This square is made of 4 Four vertices and four deformations .

#### The relationship between a vertex and an edge

A total of 8 side , The index is 0~7. Anti-clockwise , The relationship between edge topologies :

``````e[0]: {

prevEage: e[6], nextEage: e[3], vertex: v[3], face: 0}
e[1]: {

prevEage: -1, nextEage: -1, vertex: v[1], face: -1}
e[2]: {

prevEage: -1, nextEage: -1, vertex: v[3], face: -1}
e[3]: {

prevEage: e[0], nextEage: e[5], vertex: v[2], face: 0}
e[4]: {

prevEage: -1, nextEage: -1, vertex: v[2], face: -1}
e[5]: {

prevEage: e[3], nextEage: e[6], vertex: v[0], face: 0}
e[6]: {

prevEage: e[5], nextEage: e[0], vertex: v[1], face: 0}
e[7]: {

prevEage: -1, nextEage: -1, vertex: v[0], face: -1}
``````

Explain the first :

``````e[0] This side :
The starting vertex is : v[3]
The last side is : e[6]
The next side is : e[3]
``````

The sides that make up the face are only e[0],e[3],e[5],e[6]. So the other sides are idle (-1).

https://chowdera.com/2020/12/20201206100658060j.html