The Half-Edge Data Structure Computational Geometry, WS 2007/08 Lecture 3, Part III Prof. Dr. Thomas Ottmann Khaireel A. Mohamed Algorithmen & Datenstrukturen,

The Half-Edge Data Structure

Computational Geometry, WS 2007/08Lecture 3, Part III

Prof. Dr. Thomas OttmannKhaireel A. Mohamed

Algorithmen & Datenstrukturen, Institut für InformatikFakultät für Angewandte WissenschaftenAlbert-Ludwigs-Universität Freiburg

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 2

Overview

• Planar subdivision representation• Adjacency relationships and queries• Boundary representation structure• Baumgart’s winged-edge data structure• Doubly-connected-edge-list (DCEL)• Overlaying planar subdivisions• Analyses


Representing a Polygon Mesh

• We require a convenient and efficient way to represent a planar subdivision.

• Components in the planar subdivision:– A list of vertices

– A list of edges

– A list of faces storing pointers for its vertices

• Must preserve adjacency relationships between components.


Possible Adjacency Queries

Point anywhere on the polygon mesh and ask:• Which faces use this vertex?• Which edges use this vertex?• Which faces border this edge?• Which edges border this face?• Which faces are adjacent to this face?

Our deliberations: Constrained to manifold surfaces only.


Planar Subdivision

Euler’s Formula:

v – e + f = 2


Boundary Representation Structures

• To represent such queries efficiently, we use the boundary representation (B-rep) structure.

• B-rep explicitly models the edges, vertices, and faces of the planar subdivision PLUS additional adjacency information stored inside.

• Two most common examples of B-rep:– Baumgart’s winged-edge data structure

– Doubly-connect-edge-list (DCEL)


Baumgart’s Winged-Edge DS

• The Edge DS is augmented with pointers to:– the two vertices it touches (v1, v2),

– the two faces it borders (f1, f2), and

– pointers to four of the edges which emanate from each end point (e_v1[4], e_v2[4]).

• We can determine which faces or vertices border a given edge in constant time.

• Other types of queries can require more expensive processing.

e

v1

v2

f2

f1

e_v1[4]

e_v2[4]


The Doubly-Connected-Edge-List (DCEL)

• DCEL is a directed half-edge B-rep data structure.

• Allows all adjacency queries in constant time (per piece of information gathered). That is, for example;– When querying all edges adjacent to a vertex, the operation will be

linear in the number of edges adjacent to the vertex, but constant time per edge.

• The DCEL is excellent in representing manifold surfaces:– Every edge is bordered by exactly two faces.

– Cross junctions and internal polygons are not allowed.


DCEL Component – Half-edge

• The half-edges in the DCEL that border a face, form a circular linked-list around its perimeter (anti-clockwise); i.e. each half-edge in the loop stores a pointer to the face it borders (incident).

• Each half-edge is directed and can be described in a Java class as follows:

H_Edge

f eNext

ePrev

vOrig eTwin

class H_Edge { Vertex vOrig; H_Edge eTwin; Face f;

H_Edge eNext; H_Edge ePrev;}


DCEL Component - Vertex

• A vertex in the DCEL stores:– its actual location of the point on the plane, and

– a pointer to exactly ONE of the H_Edge, which uses this vertex as its origin.

• There may be several H_Edge which origins start at the same vertex. We need only one, and it does not matter which one.

Vertex

hEdge

p=(x,y)

class Vertex { Point2D p; H_Edge hEdge;}


• A face component stores – a reference to any one of the half-edges it borders (the face’s outer-

most boundary), and– a set of references to half-edges of unique holes inside the face.

• For the unbounded face, the eOuterComp reference is NULL.

DCEL Component – Face

class Face { H_Edge eOuterComp; List<H_Edge> eInnerComps;}

Face eOuterComp

eInnerComps[0]


DCEL Example: Planar Subdivision

Vertexv1

v2

v3

v4

v5

v6

v7

v8

v9

v10

v11

p(1,1)

(10,0)

(9,5)

(2,7)

(5,8)

(8,9)

(5,11)

(7,13)

(1,13)

(11,12)

(6,15)

hEdgee1_3

e2_3

e3_4

e4_9

e5_9

e6_7

e7_8

e8_6

e9_11

0 1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

v1

v2

v3

v4

v5v6

v7

v8v9v10

v11

f1

f3

f2

f4



Half-Edgee1_3

e3_1

e2_3

e3_2

e10_3

e11_10

e9_11

e4_9

e3_4

e4_3

e9_4

e5_9

e3_5

e5_3

e9_5

e11_9

vOrigv1

eTwine3_1

ff1

eNexte3_4

ePreve3_1

0 1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

v1

v2

v3

v4

v5v6

v7

v8v9v10

v11

f1

f3

f2

f4



Half-Edgee10_11

e3_10

e6_7

e8_6

e7_8

e8_7

e7_6

e6_8

vOrigv10

eTwine11_10

ff3

eNexte11_9

ePreve3_10

Facef1

f2

f3

f4

eOuterCompNULL

eInnerCompse1_3

0 1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

v1

v2

v3

v4

v5v6

v7

v8v9v10

v11

f1

f3

f2

f4


Adjacency Queries

• Given a half-edge e, we can perform queries in constant time.

• Example:Vertex v1 = e . vOrig;Vertex v2 = e . eTwin . vOrig;Face f1 = e . f;Face f2 = e . eTwin . f;

ef1 v2

v1 f2


Iterated Adjacency Queries

• Iterating over the half-edges adjacent to a given face f.

H_Edge hEdge = f . eOuterComp;do { // Do something with edge. hEdge = hEdge . eNext;} while (


Iterated Adjacency Queries

• Iterating over the half-edges on a given vertex v.

H_Edge hEdge = v . hEdge;do { // Do something with edge. hEdge = hEdge . eTwin . eNext;} while (


Splitting an Edge

• Given a half-edge e and a point p on e, we can split e into two sub-edges e1 and e2 in constant time.

ep

p

e.eTwine.vOrig

e.vOrig e1

e2 e2.eTwin

e1.eTwin


Splitting and Re-directing Edges

• Given a half-edge e and a vertex v of degree deg(v) on e, we can split and redirect the sub-edges of the DCEL at v in time O(1 + deg(v)).

e

e1

e2

e.vOrig

v

vInsertion of new edges into the flow:» Iterate edges at v.» Exercise (in next tutorial).


Face Records

Determining the boundary-type:• Is a complete edge-loop (boundary-cycle) an outer-boundary, or the

boundary of a hole in the face?– Select the face f that we are interested in.

– Identify the lowest of the left-most vertex v of any edge-loop.

– Consider the two half-edges passing through v, and compute their angle .

– If is smaller than 180°, then the edge-loop is an outer-boundary.

f


Overlaying Two Planar SubdivisionsPlane sweep!

• Event-points (maintained in balanced binary search tree): – Vertices of S1 and S2

– All intersections between edges in S1 and S2

• Status-structure (per event):– Neighbouring edges sorted in increasing x-order.


Handling Intersections

• Additional handling of ‘intersection’ event points:– Split and re-direct edges.

– Check new nearest-neighbours for intersections.

• Recall (from Lecture 3b): 2

13

7

7 3

12 8

U(P)

C(P)

C(P)

3

8

4

5

7

1

3

2

1

• PL


Analysis

For a total of n vertices in both S1 and S2:• Sorting of n vertices: In time• Runtime per ‘intersection’-vertex: In time• Operation per ‘intersection’-vertex: In time • Total ‘intersection’-vertices: k

• Total runtime:

Documents

The Half-Edge Data Structure Computational Geometry, WS 2007/08 Lecture 3, Part III Prof. Dr. Thomas Ottmann Khaireel A. Mohamed Algorithmen & Datenstrukturen,