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 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: {

prevEage: e, nextEage: e, vertex: v, face: 0}
e: {

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

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

prevEage: e, nextEage: e, vertex: v, face: 0}
e: {

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

prevEage: e, nextEage: e, vertex: v, face: 0}
e: {

prevEage: e, nextEage: e, vertex: v, face: 0}
e: {

prevEage: -1, nextEage: -1, vertex: v, face: -1}

Explain the first :

e This side :
The starting vertex is : v
The last side is : e
The next side is : e

The sides that make up the face are only e,e,e,e. So the other sides are idle (-1).

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