Graphics Reference
In-Depth Information
Input:
A faceted surface
S
Output:
A list of pseudofacets F that constitute the section of
(A pseudofacet is a list of vertices that define a facet that may be listed
in a random order)
S
by the x-y plane
{ Global variables }
integer list array
indexed by the faces of
S
Exs;
edge list
E;
edge
e, e';
real
z0, z1;
vertex
v0, v1;
pseudofacet
fc;
begin
for each
face f in
Sdo
initialize Exs[f] to the empty list;
Initialize E to empty;
for each
edge e in
Sdo
begin
z0 := z-coordinate of first vertex v0 of e;
z1 := z-coordinate of second vertex v1 of e;
if
0 Œ [z0,z1]
then
case
type of intersection
of
z0 = 0, z1 π 0 :
for each
edge e' incident to v0
do
begin
Add e' to E;
for each
face f incident to e'
do
Add e' to Exs[f];
end
;
z1 = 0, z0 π 0 :
for each
edge e' incident to v1
do
begin
Add e' to E;
for each
face f incident to e'
do
Add e' to Exs[f];
end
;
z0 = z1 = 0 : { horizontal edge case }
for each
face f incident to e
do
for each
nonhorizontal edge e' of f adjacent to e
do
begin
Add e' to E; Add e' to Exs[f];
end
;
0 Œ (z0,z1) :
begin
{ the typical generic case }
Add e to E;
for each
face f incident to e
do
Add e to Exs[f];
end
end
;
Initialize F to empty;
if
Empty (E)
then
Exit;
Algorithm 13.4.3.1.
A faceted surface sectioning algorithm.