[dpvc: X geomview display]

[mbp]

[I'm forwarding this to "software" for the log.  --Mark]

From: dpvc
Subject: X geomview display
To: techstaff
Date: Tue, 15 Feb 94 11:08:21 CST
X-Mailer: ELM [version 2.3 PL11]

During the last Geomview meeting, I mentioned that I thought the X
version should be able to handle self-intersection.  I should also
point out that the current display algorithm can fail even when there
is NO self-intersection.

A trivial example of this has four rectangular faces in the following
arrangement:


         ___     ___
        |   |   |   |
      +-|   |---------+
      | |   |         |
      +-|   |---------+
        |   |   |   |
      +---------|   |-+
      |         |   | |
      +---------|   |-+
        |___|   |___|


Here, the faces are interleaved, so there is NO order in which they
can be drawn so that they overlap correctly.  Of course, this is
rather contrived, but a version of this using only three interleaved
pieces appears in the vertex-minimal piecewise-linear version of the
trefoil curve (with 6 vertices).  Such arrangements also appear in
some of the polyhedral models that I have developed.

A less-contrived situation begins with the following collection of
lines


                        /
                       /
                      / ---- C
                     /
             A ---- /
                   /
                  /
                B


and builds a rectangle over each that sticks out of the page (if these
lines lie in the xy-plane, take their cross product with the unit
interval in the z direction).

If we look at this configuration from a viewpoint at the bottom of the
page (that is, from the negative y-axis), the correct order for
drawing the faces would be ABC since B overlaps A and C overlaps B
when viewed from that direction.

But if the faces are sorted front to back, they will not be in the
correct order.  For example, if we sort by closest point on each face,
then the order is BAC, whereas if we sort by farthest point, the
order is BCA, and if we sort by the average distance of the vertices
(i.e, the vector sum of the vertices divided by the number of
vertices) the order is CBA.  The current X version draws this as CBA,
so I assume Daeron is doing something like the latter.  The current
PS snapshot module ends up with BCA.

An OFF file containing this configuration is /u/dpvc/geomview/sort.off
in case you want to play with it.  The interleaved rectangles above
are in /u/dpvc/geomview/overlap.off

I do not know of a front-to-back algorithm that handles this
configuration correctly, and I think you will agree that such a set of
faces is not unreasonable.  In fact, in my work with polyhedral models
with very few vertices, such configurations are quite common (with few
vertices, it is easy to get long, thing faces like B that pass between
other faces).

Front-to-back sorting works well when there are lots of small faces,
but it does not do well for the kinds of objects that I use, which may
have only 10 or 12 vertices, but 20 or more faces.  Since the faces
share vertices so often, sorting by closest or farthest vertex usually
doesn't distinguish between the faces very well, and the averaging
process simply doesn't capture the overlapping information (as in the
CBA case above).

An example of a real-life situation where this occurs is the Csaszar
embedding of the vertex-minimal torus (see the geomview file
/u/dpvc/Research/Surfaces/Torus/gv/t7.gv).  This is an embedding of
the torus with 7 vertices and 14 faces.  If you display it in X
geomview and rotate the object, faces will "pop" from the back to the
front periodically.  I can show you the physical model if you want to
see what it _should_ look like (or view it on an SGI).  Note that this
is an embedding, so there is no self-intersection to confuse the issue.

In my experience, the front-to-back algorithm is insufficient to
render non-convex polyhedra with few vertices (the subject of my own
research).  The solution I used when I wrote a graphics program to
help my research at Brown was a binary-subdivision algorithm:  look for
a plane that divides the faces into two groups, one on each side of
the plane with no faces intersecting the plane (for example, the plane
containing the face B in the example above), and then do the same in
each of the two group separately, and so on.  Usually you locate the
dividing plane by looking at the planes spanned by the faces
themselves, so the data structure is a tree with faces as the nodes
and the sub-trees of a node are all the faces on one side or the other
of the face at that node.  When you go to draw the object, check which
side of the plane the viewpoint is on and draw the opposite group
first, then the face within the dividing plane, then the group on the
same side as the viewpoint.

If no plane divides the faces into groups (as in the overlapping
example above), then you must subdivide faces until such a plane can
be found.  This will take care of self-intersection as a by-product of
getting a correct tree-structure, and it will solve both the problem
configurations given here.  Furthermore, it can help make the display
faster, since the tree structure is independent of the viewing
direction:  once the tree is created, it can be used to correctly
render the object from any rotation (the front-to-back algorithm
requires re-sorting the object each time it is moved or rotated).  The
tree-structure is correct for both orthogonal and stereographic
projections.


You may want to create a binary tree for each geomview object as it is
loaded and then use this to display the object no matter where it is
moved or rotated.  If there are multiple objects, however, they may not
intersect or overlap correctly unless a binary-subdivision is created
for all the faces of all the objects as a whole.  Such a division
would have to be recreated each time something rotates or moves, which
is probably impractical.  You may want a button or something that
forces such a common subdivision at the user's request.


For my own use, X geomview will be unusable unless these issues are
addressed.  I look forward to an improved display algorithm within
geomview.