Home Overview FAQ Documentation Download Mailing List Geomview For Windows? Support Users Development Bug Reporting Contributing Contact Us Sponsors

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [dpvc: X geomview display]
[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 XMailer: ELM [version 2.3 PL11] During the last Geomview meeting, I mentioned that I thought the X version should be able to handle selfintersection. I should also point out that the current display algorithm can fail even when there is NO selfintersection. 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 vertexminimal piecewiselinear version of the trefoil curve (with 6 vertices). Such arrangements also appear in some of the polyhedral models that I have developed. A lesscontrived 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 xyplane, 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 yaxis), 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 fronttoback 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). Fronttoback 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 reallife situation where this occurs is the Csaszar embedding of the vertexminimal 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 selfintersection to confuse the issue. In my experience, the fronttoback algorithm is insufficient to render nonconvex 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 binarysubdivision 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 subtrees 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 selfintersection as a byproduct of getting a correct treestructure, 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 fronttoback algorithm requires resorting the object each time it is moved or rotated). The treestructure 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 binarysubdivision 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.


Home  Overview  FAQ  Documentation  Support  Download  Mailing List Windows?  Development  Bug Reporting  Contributing  Contact Us  Sponsors 

site hosted by 