Practical Algorithms for 3D Computer Graphics, 2nd Edition

84 3. Data structures for 3D graphics

to exclude the current polygon j). If they have, then this is the polygon

adjacent to polygon j along the side between vertices i

1

and i

2

. This can be

done by checking all polygons adjacent to i

1

against all polygons adjacent

to i

2

and if they have a polygon in common it can only be polygon j or

another one with vertices i

1

and i

2

in common, which is the one adjacent

to polygon j.

Part 1: Build polygon adjacency list for each vertex

s e t i = 0 and repeat while i < Npolys {

s e t j = 0 and r e pe a t while j < 3 {

id = P oly(i).V

id

n = V ert(id).n

F

extend the list V ert(id).F

adj

to n + 1 spac es

V ert(id).F

Adj

(n) = i

V er