Vector Hidden Line Removal and Fractional Quantitative Invisibility

Walter Heger

Abstract: A vector hidden line removal algorithm based on Appel’s algorithm is presented. Notions based on fractional invisibility at singularities to deal with pathelogical problems are discussed. This object-precision algorithm is believed to be faster than other image-precision techniques for a practical software solution to CAD rendering.

Key Words and Phrases: Fast vector hidden line removal, object-precision algorithms, edge coherence, transitional and fractional quantitative invisibility, quadratic surface CAD modeling, computational comparisons, silhouette calculations.

Introduction

Hidden line removal (HLR) is the process of computing which edges are not obscured by the faces of parts for a particular view and the arrangement of parts in the projection of a model into a two-dimensional plane. HLR is used by a CAD package to display the non-hidden lines. It is assumed that information is readily available to describe a wireframe model as well as the 3-D topological information. Usually, the fastest algorithm is sought for displaying this information from an existing part representation. Given a hybrid Constructive Solid Geometry/Boundary Representation (H-CSG/Brep), like that used in modern CAD systems (as in Mäntylä [MÄN88]), the vector description of the model is available and therefore so are the rules and procedures in order to perform Vector Hidden Line Removal (VHL) which will work for quadric surfaces (for planes, cylinders, cones, torii, and spheres). These parts are easily manufactured and frequently occur in a CAD design of such a part. Moreover, the degrees of freedom are sufficient to represent most models and are not overwhelming in the number of constraints to be imposed. Moreover, for most models, the surface-surface intersections and silhouette calculations can be computed analytically which results in considerable savings in the number of computations over strictly numerical techniques.

Much of the initial work in the field of vector hidden line removal has been done by Appel [APP66] and [APP67]. Appel’s algorithm implements HLR by keeping a commutative count of the number of obscuring front-facing faces on all the projected curves. The algorithm is best illustrated for the case with non-interpenetrating faces of closed self-contained bodies (2-manifolds). The other cases are extensions of this case, which involve calculating the intersections of the interpenetrating faces and creating 1- and 2-manifolds out of the model. 1-manifolds are assumed to have all faces front-facing.

Other Hidden Edge Removal Algorithms

Appel’s algorithm is an edge/intersection algorithm. The other algorithms which can be classified as object-precision are: Weiss (point/surface test) and Galimberti/ Montenari (surface/surface test). The image-precision ones are Encarnacao (priority - edge intersection test), Warnock (surface/surface test), Encarnacao (scan grid - point/ surface test), and Watkins (sample span test). The most popular algorithms that I have to compete against are: z-buffering and face drawing algorithms like binary space partitioning. Z-buffering is a hidden surface removal algorithm and thus would be slower since all the interior points of faces are compared. Face drawing would be fast due to the fact that the hidden edges are overwritten (rather than their intersections computed), however computing the points in the interior of the face is time consuming. Analogous to hypothesis testing from the field of probability, CAD modeling uses floating point computations and to make a binary decision. Problems occur when this decision is wrong. Edelsbrunner [EDE88], [EDE90] uses his simplicity of solution approach to perturb the problem in coincidence cases. This works, but assumes that the solution is within object precision and is usually not seen in image precision.

Initializing the q. i. on a vertex

The q. i. could be initialized at a vertex by performing a ray trace to calculate the value. This is one of the more computationally expensive solutions. Given the closest vertex on the convex hull of the 2D projection, the q.i. is zero because no point can be outside the hull. The q. i. cannot be arbitrarily assumed to be zero at the vertex closest to the observer because there could be a half of a hemisphere that could hide the vertex and result in an incorrect q. i. All the faces are subdivided into subfaces such that all points in the interior of this subface are either front facing or back facing. Faces which are perpendicular to the view vector are assumed to be back-facing, by arbitrary convention. This also forces the silhouette loops to reside closer to the observer.

The Basic Algorithm

The topological silhouettes of a model are those edges that bound front-facing and back-facing regions of faces. Additionally, for curvilinear surfaces, there exist view-silhouettes, which are dividing curves between front-facing and back-facing regions of a face. Silhouette curves on a surface are the collection of points such that the surface normal is perpendicular to the view vector at each of the points. Collectively, these edges are usually known as the silhouettes of a model with respect to a particular view vector. First the algorithm starts by projecting all of the edges into curves in a two-dimensional plane. These projected curves are classified as either back-facing, front-facing, or silhouettes corresponding to the edges which depend on the orientation of the bounding faces about the edges in the model. The curves are fragmented into multiple curves until the classification is unambiguous for each curve in its interior.

The quantitative invisibility (q. i.) of a point in the projection plane is the number of front-facing faces that obscure the given point. Given this, it can be seen that the quantitative invisibility is zero if there are no faces that obscure the point and increases by one for each convex body that obscures the point. Hence when traversing an edge segment, the visibility increments when going under a body and decrements when coming out from underneath. Thus, when given a linked list of edges and vertices, it is possible to proceed to the next edge by going from a vertex with a known q. i. to a vertex where the q. i. is unknown and only change the q. i. for each time that a silhouette is intersected in the projection plane. A projected edge curve is divided into two curve fragments for each of which the visibility count is constant. This makes use of the principle of edge coherence, which is the property that along sections of the edge, the q. i. is constant.

Thus, if the q. i. is determined at a vertex and is unique, this value is propagated along the edge to the surrounding vertices. For every time that an edge is traversed to the other vertex, the edge is marked to indicate that it has been processed. The vertex, along with its q. i., are pushed onto a vertex queue. Once all the edges about a vertex have been traversed, the vertex is marked as well. The vertex queue is then popped and the next vertex is processed. In this way, all the vertices and edges which are topologically connected can be processed. Vertices on faces which are not connected to other vertices can be reinitialized, or connected with temporary bridge edge (auxiliary) curves from a known vertex.

The projected curve of the currently processed traversal edge is intersected with all the silhouette edge projected curves in the projection plane. Depth checking is used in 3D in such a way that all intersections which occur where the silhouette is behind the traversal curve are discarded. These intersections are then ordered with respect to the traversal direction. Also, for more complicated surfaces, a traversal curve is intersected against itself for silhouette curves which, for example, may occur on spiral helii. To reduce the number of intersections to be performed, extend box overlap checking and tiling [the plane with a grid in which are stored all the extent boxes which contain the grid point] was used to discard unnecessary intersections. At each of the intersections, a transition vector is determined by taking the cross product of the traversal vector with the counter-clockwise direction of the silhouette curve (which is chosen with respect to the front facing face). Given that the view vector is defined from the intersection point in the direction of the observer, the q.i. transition is determined by taking the dot product of the transition vector with the view vector. This q.i. transition is added to the previous q.i. to obtain a new q.i. at a point beyond the intersection. See Fig. 1.

A new piece of insight gained recently is that the silhouette loops are closed for bodies having a connected skin. Although this makes intuitive sense, the validity of this could be questioned. Knowledge at a level of a graduate course in topology ([DUG66] and [MUN75]) is required in order to prove this rigorously. For free-formed bodies, one minor problem is the detection of all the silhouette islands [those silhouettes not intersecting other edges]. If the surface is tiled with a sufficiently fine (adaptive) tessellation, it should be possible to detect the silhouettes, but doing so is computationally expensive. An interesting problem is to find a fast way of detecting all silhouettes.

Delta q. i.

A singularity occurs when a traversed projected edge curve ends at a vertex that is under a curve which is a projected edge. A concept which can be referred to as delta q. i. is used when the vertex occurs underneath a silhouette. Delta q. i. (the change in visibility) is used to denote the middle ground between the condition of being obscured and being unobscured by a face underneath a silhouette. The reason for this formulation is that CAD parts are only accurate to within some tolerance (object-precision), hence a perturbation of the part by the tolerance could change the visibility. See Fig. 2 for an illustration. When a traversal edge reaches the end, the change in q.i. for the case in which the endpoint would have occurred slightly beyond the intersection is recorded in a variable, delta_qi. When a traversal edge is started, the change in q.i. is added to the delta_qi variable. For situations other that at the endpoint, the delta_qi is added to the regular q.i. and delta_qi =0;

Half q. i.

The case of an edge under or over a vertex must take into account the fact that both halves of the face meeting at the vertex on the edge contribute to a q.i. transition. Half q. i. is used when the traversal edge projected curve intersects the silhouette edges projected curve at the endpoint of the one edge projection while the other intersection is not at the endpoint. In this case, the q.i. transition is counted by signed half q.i.’s. See Fig. 3 for an illustration. Recently, I learned that Blinn [BLI88] was aware of this fact.

Quarter q. i.

There is also the vertex on vertex case. Quarter q. i. is used when both the traversal edge projected curve and the silhouette edge projected curve intersect at the endpoint. See Fig. 4 for an illustration. Unfortunately, as Blinn points out, this approach fails sometimes.

Most of my solutions come from thinking about the problem, seeing other software programs, having experience with writing a VHL program and dealing with issues as they occur, and discussions with other people. A good deal of these ideas about fractional invisibility comes from particle physics and fundamental mathematics (half planes, half q. i., quarter q. i. and delta q. i.).

Wedge testing

When the traversal curve is hidden by a face all sharing a common vertex, the curve must be compared against the face for a possible change in visibility. All the faces about the vertex are selected, and only those are considered that do not contain the traversal edge as their boundary and are front facing. The traversal edge is compared to see if it is in the interior of the wedge of face in the neighborhood of the vertex. See Fig. 5 for an illustration.

Rules for Special Cases

Appel does not treat the above singularity problems using fractional and delta q. i. Instead, Appel examines the traversal curves and intersection with silhouette curves at the vertex. At this point, he formulates rules as to the q. i. change at the intersection point and uses these rules to propagate the q. i. to the adjoining edges.

Similarly, the algorithm presented here uses this approach when dealing with curvilinear bodies. First, the q. i. is propagated along all the topological edges (including seam edges, which are introduced when joining two similar surfaces). The q. i. is propagated along view-silhouettes from topological edges by the use of rules based on the type of the edge and the direction of the traversal vector (with respect to the direction of the view vector). These rules were formulated based on quadratic surfaces. The only reservation is knowing if all possible cases were taken into consideration and if this would work for b-spline surfaces. The motivation for this formulation is based on the desire for speed rather than algorithmic consistency.

These rules are all based on looking at curvilinear problems and relating them to their planar counter-part. See Fig. 6 for an illustration. Care must be taken in choosing the planar counter-part, because the curvilinear problem has more degrees of freedom and might correspond to a multitude of planar problems.

Problems

Multiple intersections. and missed intersections cause problems to this algorithm because the q. i. is propagated to the adjoining edge. This problem is detected if the propagated q. i. when reached by two different traversal paths is not the same. There however is a way to resolve this problem. Either the most probable value could be taken, which would imply keeping track of the probability of a correct q. i. by looking at past q. i. transitions at problematic points, or the q. i. could be initialized. By the way, this is far less a problem if the curve-curve intersection algorithm is highly reliable.

Another consideration which comes up is whether to use a vertex queue or a vertex stack (as used by Bareau [BAR79]). The result of using a stack is that the network of vertices and edges is depth traversal, while the result of using a queue is breath traversal. A problem is that depth traversal often results in long chains of vertex -edge dependencies. Breath traversal produces short chains which tend to localize incorrect q.i. determinations.

Edges which are coincident with the view vector propagate the q.i. in the part but are usually not displayed since they degenerate into points.

Occluded Edges

An occluded edge occurs when the projection curve of one edge overlaps another in a non-zero length intersection curve. These edges can be calculated in the course of a hidden line removal algorithm, even though neither is necessarily a silhouette. Doing so is computationally expensive, because all of the edges have to be compared with each other, rather than just the silhouettes. The computations involved are so similar that they can thus be handled in the same algorithm. The curve-curve intersection algorithm, in addition to providing the points of intersection of two curves, also provides an indication of whether the curves are coincident. Furthermore, the depth check algorithm will indicate which edge is under which at the points of intersection. This information is used to fragment the curves and set the curve underneath (and hence the corresponding edge) as occluded. The visibility is known from the coincidence information of the intersector subroutine and the obscured edge is known from the depth check.

Computational Comparison

Object precision algorithms are thought to be slower than image precision algorithms. However, run time all depends on the information available at the onset. In CAD applications, most of the information needed to perform the visibility change calculations is readily available for immediate use. Thus the algorithm is not being applied to (raw) unpreprocessed data. Moreover, a modern CAD system (one having a H-CSG/Brep) includes the topology (as opposed to an older system which is based largely on geometric information). Hence, it can easily be calculated if the traversal curve is going under or coming out from under a silhouette.

The complexity of a image precision algorithm is O(p*e) while the complexity of a VHL/Appel’s algorithm is O(e*e), where e is the number of edges and p is the number of pixels. For Appel’s algorithm, edges are only intersected against silhouette edges. On the average, half of the faces are front facing and half are back facing, so that one half of the edges are silhouette edges (bound a back and front face). Thus for simpler scenes, vector based algorithms are less expensive computationally. This is one motivation for using a vector based algorithm.

However, it should be noted as remarked by Rogers, [ROG85], that if one applies all the techniques to reduce the number of unnecessary expensive operations (bounding spheres, bounding boxes, recursive subdivision) to an algorithm, the computations for Robert’s object-precision algorithm, [ROB63], have been empirically shown to be almost linear. Franklin [FRA80], claims similar results, as well as his remark that software solutions is the way the industry is heading. Rogers claims that image precision algorithms have been studied for much longer and that tends to be the reason why they are preferred, in spite of evidence since 1980 that they are not overwhelmingly superior. Moreover, object precision algorithms result in the objects themselves for further rendering, as opposed to processed data (colored pixels).

Hidden Surface Removal

The VHL algorithm can be extended to a hidden surface removal (HSR) algorithm by looking at the intersection of the silhouettes with each face of the part. Each face is described by a counter-clock-wise linked list (loop) of edges. The HSR algorithm makes use of the edge intersection to provide visibility information for each face, and each face is shaded appropriately.

Conclusion

An algorithm for the determination of hidden lines in a three dimensional model is presented. This algorithm concentrates on determining the visibility transitions at singularities by treating each edge at the singularity separately. Once the singularity is passed by, the algorithm propagates the visibility transition as most other object-precision algorithms. One motivation for dealing with the problem in this way is that the algorithm propagates the q.i. from a vertex along an edge to another vertex, rather than from a vertex along an edge to a vertex to an edge as described by Appel. This leads to at least a mathematical elegance in the solution of the HLR problem. Computationally, the algorithm has some advantages in that redundant processing is eliminated.

References:

[APP66] Appel, A., "The Notion of Quantitative Invisibility and the Machine Rendering of Solids," IBM research report RC 1618, 5/20/66.

[APP67] Appel, A., "The Notion of Quantitative Invisibility and the Machine Rendering of Solids," Proceedings ACM National Conference, Thompson Books, Washington, DC, 1967, pp. 387-393. Also in [FREE80], pp. 214-220.

[BAR79] Bareau, H., "Convenient Representation Method for Spatial Finite Element Structures," Computers and Structures, Vol. 10, Pergame Press, Great Britain, 1979, pp. 815-819.

[BLI88] Blinn, J., "Fractional Invisibility," IEEE Computer Graphics and Applications, Nov. 1988, pp. 77-84

[DUG66] Dugundji, J., Topology, Allyn and Bacon, Inc., 1966.

[EDE88] Edelsbrunner, H. and Mücke, E. P., "Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms", "Proc. 4th Annu. ACM Sympos. Comput. Geom.," 1988, pp. 118-133.

[EDE90] Edelsbrunner, H. and Mücke, E. P., "Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms," "ACM Trans. Graph.." vol. 9, 1990, pp.66-104.

[ELB80] Elber, G., and Cohen, E., "Hidden Curve Removal for Free Form Surfaces," Computer Graphics, Vol. 24, No. 4, August 1980.

[FOY90] Foley and Van Dam , Computer Graphics, Principles and Practice, 2nd ed., Addison Wesley Publishing Company. 1990.

[FRA78] Franklin, W. R., Combinatorics Of Hidden Surface Algorithms, Technical Report TR-12-78, Center Res. Comput., Harvard Univ., Cambridge, MA.

[FRA80] Franklin, W. R., "A Linear Time Exact Hidden Surface Algorithm," Proc. SIGGRAPH '80, Comput. Graph., Vol. 14, No. 3, 1980 , pp. 117-123

[FRA81] Franklin, W. R., "An Exact Hidden Sphere Algorithm That Operates In Linear Time," Comput. Graph. Image Process., Vol. 15, 1981, pp. 364-379.

[FRA90] Franklin, W. R., and Kankanhalli, M., "Parallel Object-Space Hidden Surface Removal," Proceedings of SIGGRAPH ‘90, Comput. Graph., Vol. 24, Aug. 1990, pp. 87-94.

[FREE80] Freeman, H. ed., Tutorial and Selected Readings in Interactive Computer Graphics, IEEE Comp. Soc. Press, Silver Spring, MD, 1980.

[GAL69] Galimberti, R., and Montanari, U., "An Algorithm for Hidden Line Elimination," CACM 1211, Vol. 4, April 1969, pp. 206-208.

[HOR82] Hornung. C., "An Approach to a Calculation-Minimized Hidden Line Algorithm," Computer and Graphics, Vol. 6, No 3, 1982, pp. 121-126.

[LOU70] Loutrel, P., "A Solution to the Hidden Line Problem for Computer Drawn Polyhedra," IEEE Transactions on Computers, Vol. C-19, No. 3, March 1970, pp. 205-213.

[RAN87] Rankin, J., "A Geometric Hidden -Line Processing Algorithm," Computers and Graphics, Vol. 11, No. 1, 1987, pp. 11-19.

[ROB63] Roberts, L. G., Machine Perception of Three-Dimensional Solids, MIT Lincoln Laboratory, TR 315, May 1963

[ROG85] Rogers, D. F. Procedural Elements for Computer Graphics, McGraw-Hill Book Co., 1985

[SUT74] Sutherland, I.., Sproull, R. and Schumacker, R., "A Characterization of Ten Hidden Surface Algorithms," Computer Surveys, Vol. 6, No. 1, Mar. 1974, pp. 1-55.

[MAS89] Masuda, H., Shimada, K., Numao., Kawabe, S. "A Mathematical Theory and Applications Of Non-Manifold Geometric Modeling," Advanced Geometric Modeling For Engineering Applications, ed. Krause, F. L., and Jansen, H., 1989, pp. 78-94.

[MÄN88] Mäntylä, M., An Introduction to Solid Modeling, Computer Science Press, 1988.

[MUN75] Munkres, J. R., Topology, A First Course, Prentice-Hall, Inc. 1975.

[NEW79] Newman, W. M. and Sproull, Principles of Interactive Computer Graphics, 2nd ed., McGraw-Hill. 1979.

see pics
bmc.doc
delta_qi.doc
cylplnin.doc
ex_l.doc
quart_qi.doc
ver_face.doc
Fig. 1 qi_rule.doc
half_qi.doc