Graphics Reference
In-Depth Information
In the version of
k
-means used in this algorithm, the clusters begin with
k
randomly chosen “seed” triangles. Each cluster is represented by a centroid and
a cluster normal; initially these are the centroid and face normal for the start-
ing triangle. The clusters are “grown” by a breadth-first search (based on triangle
adjacency) from the seed triangles, which are assigned a distance of zero from
the cluster center. A triangle
f
adjacent to a triangle
g
of cluster
C
is assigned a
distance equal to that of
g
plus 1
, where
n
f
and
n
C
are the face normal
and average cluster normal, respectively, and
−
n
f
·
n
C
+
is a small constant that ensures that
triangles topologically close to the seed are preferred over those that are far away.
Once distances from each face to all cluster centroids have been thus computed,
each face is assigned to the cluster of the nearest centroid. In the second step,
the cluster centroid and the average cluster normal
n
C
are recomputed, and the
iteration is restarted. Because of the dot-product term in the incremental distance
function, triangles closely aligned with the cluster normal tend to fall into the clus-
ter, while those tilted away do not; this results in cluster boundaries tending to be
aligned with sharp creases in the mesh. Note that a triangle may be adjacent to a
cluster
C
along two of its edges (or all three); in this case, we add the incremental
distance to the
lowest
of the already-computed distances of the neighbors.
25.6.2.2 Sorting
Once we have computed the clusters, we compute a value
I
(
c
1
,
c
2
)
that says how
much cluster
c
1
obscures cluster
c
2
, from enough viewpoints that our computation
is a good estimate of the average occlusion, and we use this to build a graph whose
nodes are labeled by the clusters. The value
I
is computed in
pixels:
It's meant to
represent the number of possible overdraws that result from drawing
c
2
before
c
1
,
on average. If
I
(
c
1
,
c
2
)
I
(
c
2
,
c
1
)
, we should draw
c
1
before
c
2
,soweplacea
directed edge from
c
1
to
c
2
in the graph, with edge weight
I
(
c
1
,
c
2
)
>
−
I
(
c
2
,
c
1
)
,
which is always positive.
If the resultant graph admits a topological sort (which ignores the weights),
we'll use it. If not, we want a sort order that minimizes the weights of all “viola-
tions” (i.e., cases where
c
2
comes before
c
1
in the sort order, even though there's
an edge from
c
1
to
c
2
). Unfortunately, this problem is NP-complete [Kar72], but a
simple greedy heuristic works well. It's based on an algorithm for topological sort
in which we choose as a starting node any vertex with only outgoing edges, and
as an ending node any vertex with only incoming edges; we then remove these
vertices and their associated edges from the graph and find a topological sort for
the remainder.
In an unsortable graph, the approach above fails when every node is part of
some cycle (i.e., has both incoming and outgoing edges). In this situation, we
remove the node at which the weight sum for incoming edges is most different
from the weight sum for outgoing edges, placing it on the “winning” side of the
ordering (i.e., making it the next cluster to be drawn), and then continue with the
normal topological sort.
Finally, within each cluster, we sort the triangles in a way to optimize mesh
locality (i.e., to avoid vertex-cache misses), using some triangle-stripping algo-
rithm like that of Hoppe [Hop99].
The results are impressive, generating up to 40% savings on overdraw for a
model with 150,000 triangles. Of course, it's possible to construct exotic meshes
for which almost no planar patch clusters exist; the algorithm will perform badly
