“Polygonization of non-manifold implicit surfaces” by Bloomenthal and Ferguson

A method is presented to broaden implicit surface modeling. The implicit surfaces usually employed in computer graphics are two dimensional manifolds because they are defined by real-valued functions that impose a binary regionalization of space (i.e., an inside and an outside). When tiled, these surfaces yield edges of degree two. The new method allows the definition of implicit surfaces with boundaries (i.e., edges of degree one) and intersections (i.e., edges of degree three or more). These non-manifold implicit surfaces are defined by a multiple regionalization of space. The definition includes a list of those pairs of regions whose separating surface is of interest. Also presented is an implementation that converts a non manifold implicit surface definition into a collection of polygons. Although following conventional implicit surface polygonization, there are significant differences that are described in detail. Several example surfaces are defined and polygonized.

1. E. Allgower and K. Georg, Numerical Continuation Methods, an Introduction, Springer-Verlag, 1990.
2. Bajaj, Surface Fitting with Implicit Algebraic Surface Patches, in Topics in Surface Modeling, H. Hagen. ed., SIAM Publications, 1992.
3. J. Bloomenthal, Polygonization of Implicit Surfaces, Computer Aided Geometric Design, Nov. 1988.
4. J. Bloomenthal and K. Ferguson, Polygonization of Non-Manifold Surfaces, Research Rep. 94-541-10, Dept. of Computer Science, The University of Calgary, June 1994.
5. G. Farin, Curves and Surfaces for Computer Aided Geometric Design, a Practical Guide, Academic Press, New York 1988.
6. Koide, A. Doi, and K. Kajioka, Polyhedral Approximation Approach to Molecular Orbital Graphics, Journal of Molecular Graphics 4, 1986.
7. M. Mäntylä, An Introduction to Solid Modeling, Computer Science Press, Md., 1988.
8. J. Miller, Sculptured Surfaces in Solid Models: Issues and Alternative Approaches, IEEE Computer Graphics and Applications, Dec. 1986.
9. D. Moore and J. Warren, Mesh Displacement: An Improved Contouring Method for Trivariate Data, Rice University Technical Rep. TR91-166, Sept. 1991.
10. M.E. Mortensen, Geometric Modeling. Wiley and Sons, New York, 1985.
11. M. Muuss and L. Butler, Combinatorial Solid Geometry, B-Reps, and n-Manifold Geometry, in Computer Graphics
12. Techniques: Theory and Practice, D. Rogers and R. Earnshaw, eds., Springer Verlag, New York, 1990.
13. P. Ning and J. Bloomenthal, An Evaluation of Implicit Surface Tilers, IEEE Computer Graphics and Applications, Nov. 1993.
14. Paoluzzi, F. Bernardini, C. Cattani, and V. Ferrucci, Dimension-Independent Modeling with Simplicial Complexes, ACM Trans. on Graphics 12, Jan. 1993.
15. Rockwood and J.C. Owen, Blending Surfaces in Solid Modeling, Proc. of SIAM Conf. on Geometric Modeling and Robotics, G. Farin, ed., Albany New York, 1985.
16. J. Rossignac and M. O’Connor, SGC: a Dimension-Independent Model for Pointsets with Internal Structures and Incomplete Boundaries, Geometric Modeling for Product Engineering, Elsevier Science, 1990.
17. J. Rossignac and A. Requicha, Constructive Non-Regularized Geometry, in Beyond Solid Modeling, special ed. of Computer Aided Design, 1991.
18. K. Weiler, Topological Structures for Geometric Modeling, Ph.D. dissertation, Dept. of Computer and Systems Engineering, Rensselaer Polytechnic Institute, Aug. 1986.
19. G. Wyvill, C. McPheeters, and B. Wyvill, Data Structure for Soft Objects. Visual Computer 2, 4, Aug. 1986.