程序代写代做代考 algorithm c++ cache GPU data structure 01: Functions & Calculus

01: Functions & Calculus

03: Mesh Data Structures

Dr. Hamish Carr

COMP 5812M: Foundations of Modelling & Rendering
Data Structures
Based on identifying the requirements:
topological – mesh assumptions
algorithmic – what operations we will need
resource – how much memory / bandwidth
complexity – preprocessing / runtime cost
Throughout, we will assume IEEE floats (4B)

COMP 5812M: Foundations of Modelling & Rendering
Topological Requirements
Meshes are manifold (if possible)
If not, the boundary is clearly marked
Meshes are triangulations
Easily enforced – subdivide polygons
Sometimes generalise to quads
Almost never use larger mesh elements

COMP 5812M: Foundations of Modelling & Rendering
Algorithmic Requirements
Operations will include:
Rendering
GPU transfer
Iteration for mesh processing
Insertion / deletion / modification

COMP 5812M: Foundations of Modelling & Rendering
Operations
a. access to vertices, edges, faces
b. iteration over vertices, edges, faces (any order)
c. access to endpoints of edge
d. access to faces for each edge
e. oriented traversal of edges (walk around face)
f. oriented traversal of vertices (ditto) c,e
g. oriented traversal of edges (around vertex) d,e
h. oriented traversal of faces (ditto) d,g

COMP 5812M: Foundations of Modelling & Rendering
Example: Smooth Normals
We’ll use this as a running example
For each vertex
average the adjacent normals
to produce an approximate vertex normal
Strictly speaking, don’t need to iterate around
We just need to iterate over adjacent faces
Any order will do

COMP 5812M: Foundations of Modelling & Rendering
Resource Requirements
Memory footprint is the key issue
It also influences bandwidth
Memory transfer to GPU for rendering
Not all operations are on GPU
Ideal language these days is C++
Because it enforces the POD rule

COMP 5812M: Foundations of Modelling & Rendering
Runtime Polymorphism
OO languages have runtime polymorphism
decides which function to call at runtime
needs to store information on object class
typically done with trap table pointer
pointer to details of class in memory
object name, method base addresses, &c.

COMP 5812M: Foundations of Modelling & Rendering
Trap Table Penalty
This trap table pointer is on CPU
it’s totally useless on GPU
If you have a class representing a point
Point3 { float x, y, z; NULL *trapTablePtr;}
12B for your payload, 4B or 8B for the pointer
GPU bandwidth goes up by 33% or 67%
Unless you strip it out first (i.e. copy!)

COMP 5812M: Foundations of Modelling & Rendering
POD Loophole
If you have no runtime polymorphism
i.e. no virtual methods at all
you don’t need the trap table pointer
C++ guarantees not to create one
So you can copy your data straight to GPU
And arrays are even better!
One memory copy for the entire array

COMP 5812M: Foundations of Modelling & Rendering
Complexity Requirements
Algorithms should be O(n) if possible
Insertions / deletions should be O(1) cost
Iterations should also be O(1) cost
O(n lg n) should be reserved for preprocessing
O(lg n) is the maximum runtime lookup cost

COMP 5812M: Foundations of Modelling & Rendering
Mesh Data Structures
Face
Indexed Face
Winged-Edge
Half-Edge
Directed Edge

COMP 5812M: Foundations of Modelling & Rendering
Face Data Structure
Simplest approach:
Each face consists of 3 (xyz) points
Render uses glVertex() or equivalent
Most operations iterate over faces
Cannot (usually) enforce constraints
Attributes (normals, &c.) need to be repeated
Colloquially called triangle/polygon soup

COMP 5812M: Foundations of Modelling & Rendering
Face Operations
Reading / rendering is easy (but not fast)
Vertices stored 6x, prone to matching errors
Cannot iterate around vertices
Cannot (easily) swap faces across edge
Can iterate over vertices 6x, edges 2x
by iterating through faces
Can iterate over, around faces
No per vertex/edge storage

COMP 5812M: Foundations of Modelling & Rendering

Smooth Normals- Face
Hopelessly inefficient – O(v2)
Recomputes each normal six times

COMP 5812M: Foundations of Modelling & Rendering
(Old) Face Improvements
Display lists – save bandwidth, cache on GPU
Implicit vertex reuse
Line Strips & Loops
Triangle Fans & Strips
Quads, Quad Strips
Polygons

COMP 5812M: Foundations of Modelling & Rendering
Lines, Strips & Loops

GL_LINES:
v0v1
v1v2
v2v3
v3v4
v4v5
v5v0
2 v/e
GL_LINE_STRIP:
v0v1
(v1)v2
(v2)v3
(v3)v4
(v4)v5
~ 1 v/e
GL_LINE_LOOP:
v0v1
(v1)v2
(v2)v3
(v3)v4
(v4)v5
(v5)(v0)
~ 1 v/e

COMP 5812M: Foundations of Modelling & Rendering
Triangle Fans/Strips

GL_TRIANGLE_FAN:
v0v1v2
(v0)(v2)v3
(v0)(v3)v4
(v0)(v4)v5
~ 1.16 v/e
(degree 6 vertex)

GL_TRIANGLE_STRIP:
v0v1v2
(v2)(v1)v3
(v2)(v3)v4
(v4)(v3)v5
~ 1 v/e
(for long strips)
alternate CW/CCW
NP-hard to find them
easier on regular grids

COMP 5812M: Foundations of Modelling & Rendering
Face Costs
Memory / bandwidth cost:
3 x 3 x 4B per face = 36B
f ~ 2v, so 72B per vertex
Every glVertex() call has overhead
so no advantage for batched operations
Horrendously inefficient operations
But easy and lowest common denominator

COMP 5812M: Foundations of Modelling & Rendering
Indexed Face Data Structure
Store a single array of vertices / attributes
Store their indices (or pointers) for each face
Pointers are no longer cheaper
Most PUs have 1-op array lookup
Render uses vertex arrays / VBOs
But operations aren’t so easy

COMP 5812M: Foundations of Modelling & Rendering
Vertex Arrays
Replace individual glVertex() calls
Pass entire arrays to library
Push loop through vertices into library call

COMP 5812M: Foundations of Modelling & Rendering
Vertex Buffer Objects
Same idea, but data transferred to VRAM
I.e. we cache the data & save the bandwidth
Which means memory management:
allocation: glGenBuffers, glDeleteBuffers
binding: glBindBuffer
transfer: glBufferData
And more is moving onto GPU with Vulkan

COMP 5812M: Foundations of Modelling & Rendering
Indexed Face Operations
Reading / rendering is easy & fast
Cannot iterate around vertices
But can iterate over them
Cannot (easily) swap faces across edge
Can iterate over, around faces
No per edge storage
Overall weakness – edge operations

COMP 5812M: Foundations of Modelling & Rendering

Smooth Normals – Indexed Face
Much better – O(v) computation
But it cannot iterate around vertices yet

COMP 5812M: Foundations of Modelling & Rendering
Reading Polygon Soup

COMP 5812M: Foundations of Modelling & Rendering
Writing Indexed Faces

COMP 5812M: Foundations of Modelling & Rendering
Indexed Face Costs
Memory / bandwidth cost:
3 x 4B per vertex= 12B
f ~ 2v, so 6 x 4B indices per vertex
Total: 36B / vertex
Efficient rendering
Default in practice: OBJ files / VBOs
But limited in its operations

COMP 5812M: Foundations of Modelling & Rendering
Improvements Needed
Mesh processing requires more operations
In particular, iterating in cyclic order
This allows us to preserve topology
e.g. testing 2-manifold conditions
can’t (easily) do this with indexed face
We will need to track vertices, faces, edges
Each will need index + attribute storage

COMP 5812M: Foundations of Modelling & Rendering
Face-Based Structures
Each vertex stores:
position 12B
1 face index (first) 4B 16B/vert
Each face stores:
3 vertex indices 12B
3 neighbours (face indices) 12B 24B/face
(2 faces / vertex) 48B /vert
Total: 64B / vert

COMP 5812M: Foundations of Modelling & Rendering
Smooth Normals – Face-Based
Iteration around vertices now possible
But lots of if statements
Starts failing with non-triangular faces

COMP 5812M: Foundations of Modelling & Rendering
Edge-Based Structures
These start explicitly representing edges
And using them to store cyclic edge loops
Each edge points to the next/previous edge
At each end, and for each face
Paradigm is the winged edge (Baumgart, 1972)

COMP 5812M: Foundations of Modelling & Rendering
Winged Edge

end[0]
end[1]
face[0]
face[1]
next[0]
prev[0]
prev[1]
next[1]

COMP 5812M: Foundations of Modelling & Rendering
Winged Edge Structures
Each vertex stores:
position 12B
1 edge index (first) 4B 16B/vertex
Each edge stores:
2 vertex indices 8B
2 face indices 8B
2 edge indices (next) 8B
2 edge indices (prev) 8B 32B/edge
(3 edges / vertex) 96B/vertex
Each face stores:
1 edge index (first) 4B
(2 faces / vertex) 8B /vert
Total: 120B / vert

COMP 5812M: Foundations of Modelling & Rendering
Smooth Normals – Winged Edge
This is cleaner, and handles arbitrary meshes
Face can store vertex IDs as well (+24B/v)
Still need if statements to track things

COMP 5812M: Foundations of Modelling & Rendering
Half-Edge Structures
Break winged-edges into a pair of half-edges
Mantyla 1988, Kettner 1999
Each half edge has:
vertex, face, next, prev
ID of paired half-edge
But store them in pairs
Use XOR on bit 0 to flip between them
Same cost as winged-edge, simpler code

COMP 5812M: Foundations of Modelling & Rendering
Smooth Normals – Half Edge
This is nice, but still memory-inefficient
We need to reduce the per edge costs

COMP 5812M: Foundations of Modelling & Rendering
Directed Edge Structures
Campagna 1998
Stores the directed-edges per triangle
I.e. in groups of three
Assumes arithmetic cheap, memory not
Uses modular arithmetic (%3) instead of XOR
And uses it for implicit storage of topology

COMP 5812M: Foundations of Modelling & Rendering
Conversion
Each directed edge d is no. i on face f:
d = 3f + i f = h/3 i = h%3
d is directed face index
f is face index
i is 0, 1, or 2 in CCW order
next = 3f + (i + 1) % 3
prev = 3f + (i + 2) % 3

COMP 5812M: Foundations of Modelling & Rendering
Smooth Normals – Directed Edge
Right, let’s look at the cost

COMP 5812M: Foundations of Modelling & Rendering
Directed Edge Structures
Each vertex stores:
position 12B
1 edge index (first) 4B 16B/vertex
Each directed edge stores:
1 vertex index 4B
1 paired directed edge index 4B 8B/directed edge
(6 directed edges / vertex) 48B / vertex
Each face stores:
nothing
Total: 64B/ vertex

COMP 5812M: Foundations of Modelling & Rendering
Implementation
We will do this C-style, not OO
so we get that efficiency as well
the vertices are stored in a vertex array
and the faces have vertex indices in an array
since directed edges are stored per face
their vertex indices are also the face’s list

COMP 5812M: Foundations of Modelling & Rendering
Code (Finally)
After all that mess, it’s surprisingly simple
But it’s not perfect

COMP 5812M: Foundations of Modelling & Rendering
Directed Edge Comments
A boundary edge does not have a pair
So store a negative index
Similar structure for quads is easy to construct
but we can’t mix the two
Libraries exist (OpenMesh, CGAL, &c.)
But most people roll their own
Because their attributes vary

COMP 5812M: Foundations of Modelling & Rendering

Page 1/7/Users/scshca/Desktop/mesh_structures.cpp
Saved: 30/01/2018 11:33:34 Printed for: Hamish Carr

// FACE DATA STRUCTURE1
for (each face f)2
{ // loop through faces3
// start with a zero vector4
normal = zero5
for (each vertex v on face f)6
{ // loop through vertices on face7
// loop through all faces (including this one)8
for (each face f1)9
{ // loop through faces again10
for (each vertex v1 on face f1)11
{ // loop through vertices on faces12
// if it’s the same vertex (look out for roundoff errors!)13
if (v1 == v)14
{ // vertex match15
compute normal n_f1 for face f116
normal += n_f117
} // vertex match18
} // loop through vertices on faces19
} // loop through faces again20
// note: we don’t need to keep the degree or divide through21
// because we’re going to normalise anyway! 22
normalise(normal)23
} // loop through faces24

25
26
27
28
29
30
31
32
33
34

Page 1/7/Users/scshca/Desktop/mesh_structures.cppSaved: 30/01/2018 11:33:34 Printed for: Hamish Carr// FACE DATA STRUCTURE
1
for (each face f)
2
{ // loop through faces
3
// start with a zero vector
4
normal = zero
5
for (each vertex v on face f)
6
{ // loop through vertices on face
7
// loop through all faces (including this one)
8
for (each face f1)
9
{ // loop through faces again
10
for (each vertex v1 on face f1)
11
{ // loop through vertices on faces
12
// if it’s the same vertex (look out for roundoff errors!)
13
if (v1 == v)
14
{ // vertex match
15
compute normal n_f1 for face f1
16
normal += n_f1
17
} // vertex match
18
} // loop through vertices on faces
19
} // loop through faces again
20
// note: we don’t need to keep the degree or divide through
21
// because we’re going to normalise anyway!
22
normalise(normal)
23
} // loop through faces
24
25
26
27
28
29
30
31
32
33
34