Out-of-core build of a topological data structure from polygon soup

ABSTRACT

Many solid modeling applications require information not only about the geometry of an object but also about its topology. Most interchange formats do not provide this information, which the application must then derive as it builds its own topological data structure from unordered, “polygon soup” input. For very large data sets, the topological data structure itself can be bigger than core memory, so that a naive algorithm for building it that doesn't take virtual memory access patterns into account can become prohibitively slow due to thrashing. In this paper, we describe a new out-of-core algorithm that can build a topological data structure efficiently from very large data sets, improving performance by two orders of magnitude over a naive approach.

REFERENCES

• 1: 3D Systems, Inc. Stereolithography Interface Specification. Company literature, 1988.
• 2: C. L. Bajaj , V. Pascucci , D. Thompson , X. Y. Zhang, Parallel accelerated isocontouring for out-of-core visualization, Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics, p.97-104, October 25-26, 1999, San Francisco, California, United States [doi>10.1145/328712.319342]
• 3: B. G. Baumgart. A Polyhedron Representation for Computer Vision. In Proceedings of the National Computer Conference, pages 589-596, 1975.
• 4: Joseph J. Beaman , Harris L. Marcus , David L. Bourell , Joel W. Barlow , Richard H. Crawford , Kevin P. McAlea, Solid Freeform Fabrication: A New Direction in Manufacturing, Kluwer Academic Publishers, Norwell, MA, 1997
• 5: Yi-Jen Chiang , Cláudio T. Silva , William J. Schroeder, Interactive out-of-core isosurface extraction, Proceedings of the conference on Visualization '98, p.167-174, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 6: Yi-Jen Chiang , Cláudio T. Silva, I/O optimal isosurface extraction (extended abstract), Proceedings of the 8th conference on Visualization '97, p.293-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 7: Michael Cox , David Ellsworth, Application-controlled demand paging for out-of-core visualization, Proceedings of the 8th conference on Visualization '97, p.235-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 8: Douglass Davis , William Ribarsky , Nickolas Faust , T. Y. Jiang, Intent, perception, and out-of-core visualization applied to terrain, Proceedings of the conference on Visualization '98, p.455-458, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 9: Thomas A. Funkhouser , Carlo H. Séquin, Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.247-254, September 1993 [doi>10.1145/166117.166149]
• 10: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 11: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 12: E. Gursoz, Y. Choi, and E Prinz. Vertex-based Representation of Non-Manifold Boundaries. In Geometric Modeling for Product Engineering, pages 107-130. North-Holland, Amsterdam, 1990.
• 13: M. Kitsuregawa , M. Nakayama , M. Takagi, The effect of bucket size tuning in the dynamic hybrid GRACE hash join method, Proceedings of the 15th international conference on Very large data bases, p.257-266, July 1989, Amsterdam, The Netherlands
• 14: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 15: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 16: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 17: Sara McMains , Carlo Séquin, A coherent sweep plane slicer for layered manufacturing, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.285-295, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304042]
• 18: Matt Pharr , Craig Kolb , Reid Gershbein , Pat Hanrahan, Rendering complex scenes with memory-coherent ray tracing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.101-108, August 1997 [doi>10.1145/258734.258791]
• 19: StephenJ. Rock and Michael J. Wozny. GeneratingTopological Information from a "Bucket of Facets". Proceedings Solid Freeform Fabrication Symposium, pages 251-259, 1992.
• 20: C.H. Srquin and J. Smith. Parameterized procedural synthesis of artistic geometry, lnternationalJournalofShapeModeling, 5(1):81-99, June 1999.
• 21: Spatial Technology, Inc, Boulder, CO. ACIS Save File Format Manual, 1996.
• 22: Peter Sulatycke , Kanad Ghose, A Fast Multithreaded Out-of-Core Visualization Technique, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.569-575, April 12-16, 1999
• 23: Seth Teller , Celeste Fowler , Thomas Funkhouser , Pat Hanrahan, Partitioning and ordering large radiosity computations, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.443-450, July 1994 [doi>10.1145/192161.192279]
• 24: Shyh-Kuang Ueng , Christopher Sikorski , Kwan-Liu Ma, Out-of-Core Streamline Visualization on Large Unstructured Meshes, IEEE Transactions on Visualization and Computer Graphics, v.3 n.4, p.370-380, October 1997 [doi>10.1109/2945.646239]
• 25: H. Voelcker. Modeling in the Design Process. In Design and Analysis of Integrated Manufacturing Systems, pages 167- 199. National Academy Press, Washington, DC, 1988.
• 26: Kevin Weiler. The Radial Edge Structure: A Topological Representation for Non-Manifold Geometric Boundary Modeling. In Geometric Modeling for CAD Applications, pages 3-36. North-Holland, Amsterdam, 1988.
• 27: Janet L. Wiener , Jeffrey F. Naughton, OODB Bulk Loading Revisited: The Partitioned-List Approach, Proceedings of the 21th International Conference on Very Large Data Bases, p.30-41, September 11-15, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Measurement, Performance, Theory