Half Edges and Ray Tracing

Computer Graphics and Imaging

UC Berkeley CS 184/284A

Discussion 07

Worksheet 6 link!

https://tinyurl.com/quarteredge

Have you guys seen subdivision memes

https://youtu.be/ipvwpJusp2Y?si=17m_ZbZzMa2FXM1e

Week 7 Announcements

Disc 6 Review!

Review Discussion

1. Cubic Hermite Interpolation

• What does it do? When it is useful?
• What are two information needed?
• How do we compute it?

2. Catmull-Rom Interpolation

• How do we get the slope in Catmull-Rom?
• What are C0, C1, C2 continuity?

3. de Casteljau’s algorithm

• How do we find Bezier curve of given control points =>
• What is the degree of polynomial resulted from de Casteljau algorithm on n control points?

Half-Edges

Half-Edge Background

Preferred way to represent 3D shapes: Meshes

Many ways to represent meshes:

• List of triangles
• List of points + indexed triangle
• Triangle neighbor

​

Downsides: hard to edit, store redundant data, hard to navigate

8

The Half-Edge Data Structure

​

struct Halfedge {

Halfedge *twin,

Halfedge *next;

Vertex *vertex;

Edge *edge;

Face *face;

}

​

struct Vertex {

Point pt;

Halfedge *halfedge;

}

​

struct Edge {

Halfedge *halfedge;

}

​

struct Face {

Halfedge *halfedge;

}

Key idea: two half edges act as “glue” between mesh elements

Each vertex, edge, and face points to one of its half edges

vertex

The Half-Edge Data Structure

​

struct Halfedge {

Halfedge *twin,

Halfedge *next;

Vertex *vertex;

Edge *edge;

Face *face;

}

​

struct Vertex {

Point pt;

Halfedge *halfedge;

}

​

struct Edge {

Halfedge *halfedge;

}

​

struct Face {

Halfedge *halfedge;

}

​

Key idea: two half edges act as “glue” between mesh elements

Each vertex, edge, and face points to one of its half edges

vertex

The Half-Edge Data Structure

​

struct Halfedge {

Halfedge *twin,

Halfedge *next;

Vertex *vertex;

Edge *edge;

Face *face;

}

​

struct Vertex {

Point pt;

Halfedge *halfedge;

}

​

struct Edge {

Halfedge *halfedge;

}

​

struct Face {

Halfedge *halfedge;

}

Key idea: two half edges act as “glue” between mesh elements

Each vertex, edge, and face points to one of its half edges

vertex

The Half-Edge Data Structure

​

struct Halfedge {

Halfedge *twin,

Halfedge *next;

Vertex *vertex;

Edge *edge;

Face *face;

}

​

struct Vertex {

Point pt;

Halfedge *halfedge;

}

​

struct Edge {

Halfedge *halfedge;

}

​

struct Face {

Halfedge *halfedge;

}

​

Key idea: two half edges act as “glue” between mesh elements

Each vertex, edge, and face points to one of its half edges

vertex

The Half-Edge Data Structure & Mesh Traversal

Halfedge *h = f->halfedge;

do {

process(h->vertex);

h = h->next;

} while (h != f->halfedge);

​

Use twin and next pointers to move around the mesh

You can process vertex, edge, and/or face pointers

Example 1: Process all vertices of a face

​

Mesh Traversal

• Use twin and next pointers to move around the mesh.

Mesh Traversal

• Use twin and next pointers to move around the mesh.
• h->next() to access the halfedge ahead of h.

​

twin

Mesh Traversal

• Use twin and next pointers to move around the mesh.
• h->next() to access the halfedge ahead of h, going counterclockwise.
• h->twin() to access the halfedge that shares an edge with h.

Note: We denote e.g. a pointer to an Edge by EdgeIter. So the following initialization is valid, given EdgeIter e:

​

HalfedgeIter h = e→halfedge();

​

​

std::vector<EdgeIter> getOppositeEdges(VertexIter v)

{

std::vector<EdgeIter> edges;

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

do {

edges.push_back(h->next()->edge());

h = h->next()->next()->twin();

} while (h != start_h);

return edges;

}

std::vector<EdgeIter> getOppositeEdges(VertexIter v)

{

std::vector<EdgeIter> edges;

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

do {

edges.push_back(h->next()->edge());

h = h->next()->next()->twin();

} while (h != start_h);

return edges;

}

std::vector<EdgeIter> getOppositeEdges(VertexIter v)

{

std::vector<EdgeIter> edges;

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

do {

edges.push_back(h->next()->edge());

h = h->next()->next()->twin();

} while (h != start_h);

return edges;

}

std::vector<EdgeIter> getOppositeEdges(VertexIter v)

{

std::vector<EdgeIter> edges;

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

do {

edges.push_back(h->next()->edge());

h = h->next()->next()->twin();

} while (h != start_h);

return edges;

}

std::vector<EdgeIter> getOppositeEdges(VertexIter v)

{

std::vector<EdgeIter> edges;

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

do {

edges.push_back(h->next()->edge());

h = h->next()->next()->twin();

} while (h != start_h);

return edges;

}

std::vector<EdgeIter> getOppositeEdges(VertexIter v)

{

std::vector<EdgeIter> edges;

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

do {

edges.push_back(h->next()->edge());

h = h->next()->next()->twin();

} while (h != start_h);

return edges;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

void diffuse(VertexIter v, float k)

{

Vector3D L(0, 0, 0);

HalfedgeIter h = v->halfedge();

HalfedgeIter start_h = h;

int n = 0;

do {

VertexIter v_j = h->next()->vertex();

Vector3D dir = v_j->position() - v->position();

L = L + dir;

n++;

h = h->twin()->next()

} while (h != start_h);

v->position() = v->position() + k * L / n;

}

Local Operations

Local Operations - Edge Flip

34

Triangles (a, b, c), (b, d, c) become (a, d, c), (a, b, d):

• Long list of pointer reassignments
• However, no elements need to be created or destroyed

flip

Local Operations - Edge Flip

35

Triangles (a, b, c), (b, d, c) become (a, d, c), (a, b, d):

• Long list of pointer reassignments
• However, no elements need to be created or destroyed

flip

Local Operations - Edge Split

36

Insert midpoint m of edge (c, b), connect to get four triangles:

• This time, you have to add elements
• Again, there are a lot of pointer reassignments you’ll have to make!

split

Local Operations - Edge Split

37

Insert midpoint m of edge (c, b), connect to get four triangles:

• This time, you have to add elements
• Again, there are a lot of pointer reassignments you’ll have to make!

split

m

Local Operations - Edge Collapse

38

Replace edge (c, d) with a single vertex m:

• This time, you have to delete elements
• Again, there are a lot of pointer reassignments you’ll have to make!

collapse

a

b

c

d

a

b

c

d

Local Operations - Edge Collapse

39

Replace edge (c, d) with a single vertex m:

• This time, you have to delete elements
• Again, there are a lot of pointer reassignments you’ll have to make!

collapse

a

b

c

d

a

b

c

d

c

d

Local Operations - Edge Collapse

40

Replace edge (c, d) with a single vertex m:

• This time, you have to delete elements
• Again, there are a lot of pointer reassignments you’ll have to make!

collapse

a

b

c

d

a

b

d

m

41

a

b

c

d

42

a

b

c

d

43

a

b

m

Local Operations

flip

split

m

a

b

c

d

b

c

d

c

d

collapse

d

m

e₀

e₀

any of e₀, e₁₀, e₁₁

e₀

any of e₀, e₁₀, e₁₁

any of e₀, e₉, e₁₂, e₁₆

e₀

f₄, e₃->next() = e₁₂

any of e₀, e₁₀, e₁₁

any of e₀, e₉, e₁₂, e₁₆

e₀

V₀

any of e₀, e₁₀, e₁₁

any of e₀, e₉, e₁₂, e₁₆

f₄, e₃->next() = e₁₂

e₀

V₀

any of e₀, e₁₀, e₁₁

any of e₀, e₉, e₁₂, e₁₆

either of e₆, e₁₀

f₄, e₃->next() = e₁₂

e₀

any of e₀, e₁₀, e₁₁

any of e₀, e₉, e₁₂, e₁₆

V₀

either of e₆, e₁₀

e₁₃->next() = e₃

f₄->halfedge() = any of e₃, e₁₂, e₁₃

e₀->face() = f₃

e₀->next() = e₁₀

V₃->halfedge() = either of e₃, e₁₄

f₄, e₃->next() = e₁₂

Subdivision

Subdivision Motivation

• It’s expensive to create smooth meshes by hand.
• Instead…
1. Start with control cage — a coarse mesh.
2. Smooth algorithmically.

​

55

Subdivision Motivation

• It’s expensive to create smooth meshes by hand.
• Instead…
1. Start with control cage — a coarse mesh.
2. Smooth algorithmically.
• Techniques:
• Loop subdivision → triangular meshes.
• Catmull-Rom subdivision → quad meshes.

56

Loop Subdivision

1. Split each triangle face into four → new triangles, new vertices!

57

Loop Subdivision

1. Split each triangle face into four → new triangles, new vertices!
2. Update old and new vertex positions as weighted sum.

1/8

3/8

3/8

1/8

New vertices

Old vertices

u

u

u

u

u

u

1 - n*u

n: vertex degree

u: 3/16 if n = 3, 3/(8n) otherwise

Loop Subdivision

59

Example: degree 6

1/16

1/16

1/16

1/16

1/16

1/16

10/16

Loop Subdivision Example

Loop Subdivision Example

61

Worksheet Question 2

A

B

C

D

E

F

G

This result depends on the order that edges are processed in! ��Do you see why?

This result depends on the order that edges are processed in! ��Do you see why?

For any new edge that connects new vertex to old vertex…

This result depends on the order that edges are processed in! ��Do you see why?

For any new edge that connects new vertex to old vertex…

​

Edge flip!

This result depends on the order that edges are processed in! ��Do you see why?

For any new edge that connects new vertex to old vertex…

​

Edge flip!

This completes the face splitting procedure.

<= hint

https://geogebra.org/classic/dkcv5cs8

The position of a new vertex unchanged if and only if the midpoint of the opposite vertices A and C lies at the exact same location as the midpoint of edge BD (i.e., when $A, B, C, D$ form a parallelogram)

​

Proof:

​

Set V_new = midpoint of BD

Hint:

Loop Subdivision

• Split each triangle face into four → new triangles, new vertices!
• Update old and new vertex positions as weighted sum.

1/8

3/8

3/8

1/8

New vertices

Old vertices

u

u

u

u

u

u

1 - n*u

n: vertex degree

u: 3/16 if n = 3, 3/(8n) otherwise

Hint:

Since n = 5,

weight u = 3/8n = 3/40

​

So v’_old = (1 - 5 * (3/40)) * (4, 2, 0) + (3/40) * (25, 15, 0)

=

Solution:

towards the centroid (average position) of its 1-ring neighboring vertices

Slide link!

https://tinyurl.com/4ns3tdab

D7 Attendance!

https://tinyurl.com/4p3xcpsx

Attendance Code:

• Loop subdivision was developed at Pixar!
• https://graphics.pixar.com/library/SEC/supplemental.pdf

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

​

​

Procedure:

1. Add vertex in each face
2. Add midpoint to each edge
3. Connect all new vertices
4. Adjust vertex positions to weighted average

86

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

1. Add face point:

For each face, add a face point and set its position to be the average of all original points in the same face.

​

87

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

2. Add edge point:

For each edge, add an edge point and set its position to be the average of 2 neighboring face points (AF) and the midpoint of the edge (ME).

​

88

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

3. Move original vertices:

For each original vertex (P), take the average (F) of all n neighboring face points, and the average (R) of all n midpoints on neighboring edges (Note: edge midpoint is not the same as edge point! )

Move each vertex to

​

89

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

​

4. Form new edges and faces:

Connect each new face point to the new edge points of all original edges defining the original face

​

90

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

​

4. Form new edges and faces:

Connect each new vertex point to the new edge points of all original edges incident on the original vertex

​

91

Catmull-Clark Subdivision

Designed for meshes with variable polygons (triangles/quadrilaterals/pentagons)

​

4. Form new edges and faces:

Define new faces as enclosed by the new edges.

​

92

Catmull-Clark Subdivision Example

93

Ray Tracing Basics

Ray Equation

r(t) = o + td

• Where o is the position of the origin.
• d is the direction of the ray.
• t is time, and is ≥ 0.

Ray Tracing

Ray Tracing

Bonus Question!

How would you check if an intersection is inside a triangle?

Bonus Question!

How would you check if an intersection is inside a triangle?

Try placing the ray in this diagram to get intuition

Try placing the ray in this diagram to get intuition

Ray Triangle Intersection

Last week: Ray-Plane Intersection

Ray Triangle Intersection

But meshes are made of triangles, so we need ray-triangle intersection!

116

Last week:

Ray Triangle Intersection

Ray Triangle Intersection Derivation

118

Acceleration Structures

Acceleration Structures Motivation

• Meshes can be made of hundreds of thousands of triangles.
• We sample at least one ray per pixel. (Imagine a 4K = 3840x2160 TV.)
• Calculating intersections can quickly get expensive!

127

Sneak Peek

In the next assignment, you will be able to render images like these!

128

Idea: Bounding Volume Hierarchy

Internal nodes:

1. Bounding box.
2. Reference to children.

129

Idea: Bounding Volume Hierarchy

Internal nodes:

1. Bounding box.
2. Reference to children.

130

Leaf nodes:

1. Bounding box.
2. List of primitives in the box.

Worksheet Question 2

132

133

split this side

134

split this side

135

There are 2 valid splits!

136

We’ll just consider this one.

137

138

• It’s fine if these bounding boxes intersect!
• Key idea: we have partitioned objects into disjoint sets.

139

140

141

142

143

Using a Bounding Volume Hierarchy

144

Using a Bounding Volume Hierarchy

145

Using a Bounding Volume Hierarchy

146

Using a Bounding Volume Hierarchy

147

Using a Bounding Volume Hierarchy

148

Using a Bounding Volume Hierarchy

149

Using a Bounding Volume Hierarchy

150

Using a Bounding Volume Hierarchy

151

Using a Bounding Volume Hierarchy

152

Using a Bounding Volume Hierarchy

153

Using a Bounding Volume Hierarchy

154

Using a Bounding Volume Hierarchy

155

Using a Bounding Volume Hierarchy

156

https://www.geogebra.org/3d/umn78ybr

2.2. Using a Bounding Volume Hierarchy

158

Hint: Axis-aligned ray-plane intersection equation

2.2. Using a Bounding Volume Hierarchy

159

2.2. Using a Bounding Volume Hierarchy

160

2.2. Using a Bounding Volume Hierarchy

161

Radiometry & Photometry

Radiometry

Flux (Power) is measured in Watts.

Radiometry

Flux (Power) is measured in Watts.

Radiant intensity is flux per solid angle.

Radiometry

Flux (Power) is measured in Watts.

Radiant intensity is flux per solid angle.

Radiance is flux per area per solid angle.

​

AKA brightness!

Radiometry

Flux (Power) is measured in Watts.

Radiant intensity is flux per solid angle.

Irradiance is flux per area.

Radiance is flux per area per solid angle.

​

AKA brightness!

Radiant flux is energy received per time. Watts.

Radiant (luminous) flux is energy received per time. Watts (lumens).

Photometry mirrors radiometry but adjusts for human vision.

Radiant (luminous) intensity is flux per solid angle. W/sr (candela).

Radiant (luminous) flux is energy received per time. Watts (lumens).

Photometry mirrors radiometry but adjusts for human vision.

Radiant (luminous) intensity is flux per solid angle. W/sr (candela).

Radiant (luminous) flux is energy received per time. Watts (lumens).

Radiance is flux per area per solid angle. W/(sr m²) (nit).

Photometry mirrors radiometry but adjusts for human vision.

Radiant (luminous) intensity is flux per solid angle. W/sr (candela).

Irradiance is flux per area.

W/m² (lux).

Radiant (luminous) flux is energy received per time. Watts (lumens).

Radiance is flux per area per solid angle. W/(sr m²) (nit).

Photometry mirrors radiometry but adjusts for human vision.

Radiant (luminous) intensity is flux per solid angle. W/sr (candela).

Irradiance is flux per area.

W/m² (lux).

Radiant (luminous) flux is energy received per time. Watts (lumens).

n

l

θ

Lambert’s cosine law

Radiance is flux per area per solid angle. W/(sr m²) (nit).

Photometry mirrors radiometry but adjusts for human vision.

3.1. Radiometry Definitions and Relations

173

3.1. Radiometry Definitions and Relations

174

3.1. Radiometry Definitions and Relations

3.1. Radiometry Definitions and Relations

177

Solid Angle

178

Solid Angle

179

Solid Angle

180

Approximate dA as a rectangle!

Solid Angle

181

How do we approximate?

Solid Angle

182

How do we approximate?

Solid Angle

183

How do we approximate?

θ

dθ

r

r dθ

Solid Angle

184

How do we approximate?

Solid Angle

185

How do we approximate?

Solid Angle

186

How do we approximate?

φ

dφ

r sin θ

r sin θ dφ

Solid Angle

187

Worksheet Question 4.1

4 Shedding Some Light

189

4 Shedding Some Light

190

3.2. Solid Angle

191

Approximate this value

as a rectangle.

​

Recall the arclength of a circle: L = r · 𝜃

What’s the radius of this circle?

What’s the radius of this circle?

3.2. Solid Angle

192

193

194

195

Lambert’s Cosine Law

197

Definition: The radiance (luminance) is the power emitted by a surface, per unit solid angle, per unit projected area.

199

Light Emitted By A Surface

“Surface Radiance”

Units Summary

Units Summary

Units Summary

203

A scales as R², so E(x) decreases as R increases.

Units Summary

Units Summary

Worksheet Question 4.2

4.2 Irradiance Calculation

207

4.2 Irradiance Calculation

208

Irradiance is power/area:

cos(Ө)

4.2 Irradiance Calculation

209

Irradiance is power/area:

What do we know?

​

cos(Ө)

4.2 Irradiance Calculation

210

Irradiance is power/area:

What do we know?

Φ = 100 W

​

What do we not know?

​

cos(Ө)

4.2 Irradiance Calculation

211

Irradiance is power/area:

What do we know?

Φ = 100 W

​

What do we not know?

r, Ө

cos(Ө)

4.2 Irradiance Calculation

212

Irradiance is power/area:

Use the Pythagorean Theorem

r = (6² + 8²)^½ = 10

This is r !

cos(Ө)

4.2 Irradiance Calculation

213

=

Irradiance is power/area:

Cosine angle between surface normal and the light position is given by the dot product of normalized vectors:

cos(Ө) = (6, 0, 8)/10 · (1, 1, 1)/√3

cos(Ө)

normal

Ө

4.2 Irradiance Calculation

214

=

Irradiance is power/area:

E =

W/m²

=

W/m²

215

1

Light Source

Surface 1:

Irradiance = E

Solid Angle = w

Surface 2:

Irradiance = E / r²

Solid Angle = w / r²

r

How does radiance change with distance?

​

Hint:�

1. The light source emits uniform flux.��2. With irradiance E and solid angle w at surface 1, what are these values at the surface 2?

216

1

Light Source

Surface 1:

Irradiance = E

Solid Angle = w

Surface 2:

Irradiance = E / r²

Solid Angle = w / r²

r

Since L = dE / dw (cos θ = 1 here), the radiance at the two surfaces is the same.

​

Radiance does not change with distance.

217