RE: [Algorithms] Silhouettes in dual space

[Ville M. <wi...@hy...>]

We're nowadays using a somewhat different algorithm for computing the
silhouette edges (exactly, not "conservatively", as described in the
Umbra manual).

The basic idea is that we can perform conservative silhouette extractio=
n
for _volumes_ in object-space. The results for a volume are cached and
when we have an exact camera position, we can refine the results to get
the corresponding exact silhouette.

The algorithm is conceptually simpler than the dual-space algorithms an=
d
works as follows:

[setup] Organize your model into a winged-edge structure (if there are =
edges
that
are shared by more than two polygons, just "duplicate" the edge -> this
will give correct results later). After this process each edge has eith=
er
one or two polygons connected to it.

Calculate plane equations for the polygons and store them.

[extraction] The silhouette extraction works in two steps. The first st=
ep
either locates a valid bounding volume (sphere,box) in object-space tha=
t the
camera intersects, or creates a new one. The bounding volumes are organ=
ized
hierarchically.

[extracting conservative silhouettes]. A conservative silhouette for an
arbitrary bounding volume can be extracted by classifying all polygons =
of
a model as follows:

front-facing: bounding volume is completely in front of the polygon
back-facing: bounding volume is completely behind the polygon
straddling: bounding volume is both in front and behind the polygon

Performing such a classification is trivial for spheres (one dot produc=
t
and two comparisons) or AABBs. Slightly modified standard view frustum
culling
routines work nicely.

After this, we can classify all edges of the model as follows:

if edge has only one neighbor and that is back-facing:  discard edge
if edge has only one neighbor and that is front-facing: classify edge a=
s
"silhouette"
if edge has only one neighbor and that is straddling:   classify edge a=
s
"straddling"

if edge has two neighbors and both are front-facing: discard edge
if edge has two neighbors and both are back-facing: discard edge
if edge has two neighbors, one is front-facing and one is back-facing:
classify as "silhouette"
else
classify edge as "straddling"

Now put all "silhouette" edges into one array and all "straddling" edge=
s
into another and
store them along with the bounding volume.

[refining silhouettes] Take all "silhouette" edges associated with the
bounding volume. These are
guaranteed to be silhouette edges for the camera position. Then process=
 all
"straddling" edges and perform
camera in object-space vs.  plane test (dot product) for the triangles
connected to them ->

if edge has only one neighbor and it is front-facing: add edge to
"silhouette"
if edge has only one neighbor and it is back-facing: discard edge
if edge has two neighbors and both are front-facing: discard edge
if edge has two neighbors and both are back-facing: discard edge
if edge has two neighbors and one is front-facing, the other back-facin=
g:
add edge to "silhouette"

* * *

Note that all of the classification cases above can be done with bit
arithmetics and using XORs,
so the actual implementation is simpler than what it looks above.

* * *

The complexity analysis of the algorithm is rather difficult. Clearly, =
each
caching operation is O(N)
(although by organizing the volumes hierarchically, one needs only to
process the 'straddling' edges
of the parent volume). The complexity of the final extraction is relate=
d to
the "quality" of the bounding
volume (its size/distance in object-space and the local curvature of th=
e
model). In a larger world,
the camera moves relatively slowly in the object-space of each far-away
model and thus the bounding
volumes last longer.

The cache structure we use allows multiple camera positions per model (=
nice
when using model instancing
or rendering reflections etc.) and all cached volumes are put into a gl=
obal
cache; thus we can bound
the memory consumption of the whole silhouette extraction system. Simpl=
e LRU
policy is used to kick out
volumes from the cache.

There are some heuristics involved in choosing the BV sizes and decidin=
g
when to partition a bounding
volume (to reduce processing during subsequent frames). We currently
partition while #straddling > #C*silhouette
(C is a small constant). This guarantees that the per-frame extraction
complexity is O(actual silhouette).

* * *

Note that the same algorithm (although simplified) can be used for
hierarchical back-face culling (even though
it's not a great win on modern 3D cards, it can be useful for culling o=
ut
entire objects).

cheers,
-wili

Ville Miettinen
http://surrender3d.com/umbra


-----Original Message-----
=46rom: gda...@li...
[mailto:gda...@li...]On Behalf Of
Pierre Terdiman
Sent: Friday, January 05, 2001 10:32
To: gda...@li...
Subject: [Algorithms] Silhouettes in dual space


Read this :
http://citeseer.nj.nec.com/283677.html

Summary: to compute silhouette edges quickly, dualize the problem:
- faces become points
- viewpoint becomes a viewplane
- edges become edges

Then find the edges intersecting the viewplane.

Now, optimize from O(n) to O(log n) by using an appropriate spatial dat=
a
structure.
Then use temporal coherence to further speed this up.

I've done it without temporal coherence, it works. But I have some
questions:
1) I don't feel like implementing a BAR tree (BAR =3D Balanced Aspect R=
atio).
Where can I find an implementation of this? (not sure it even exists on=
 the
net)
2) What kind of spatial database can answer a "double wegde query"? Wha=
t is
a "double wedge" ?
3) How could one translate those structures into homogeneous space in o=
rder
to get rid of the "point at infinity" problem ? Is it even possible? (I
can't visualize an octree in homogeneous space)
4) What would be the advantages of the dual space for *other* common CG
problems? For example, since two triangles become two points, would it =
be
possible to resolve, say the triangle-triangle intersection problem in =
dual
space .... ?
5) Is this method faster than Hoppe's one in silhouette clipping?
6) This is a perspective-correct method, i.e. it works well for toon
rendering, silhouette clipping and occlusion culling (=E0 la Umbra). Bu=
t it
does not work to compute shadow volumes for ex. Is there a fast method =
like
this to compute shadow volumes?


Pierre Terdiman      *   Home: p.t...@wa...
Coder in the dark    *   Zappy's Lair:  www.codercorner.com



_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list