当前位置:网站首页>Half edge mesh

Half edge mesh

2020-12-06 10:08:17 osc_ tj0is418

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 :
 Insert picture description here

Examples of adjacency matrices :
 Insert picture description here

Examples of half side structures :
 Insert picture description here

 Insert picture description here

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 :
 Insert picture description here

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 .

 Insert picture description here

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 :
 Insert picture description here

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

 Insert picture description here

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).

版权声明
本文为[osc_ tj0is418]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206100658060j.html