On visible surface generation by a priori tree structures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

On visible surface generation by a priori tree structures

Full text

Pdf (639 KB)

Source

ACM SIGGRAPH Computer Graphics archive
Volume 14 , Issue 3 (July 1980) table of contents

Pages: 124 - 133

Year of Publication: 1980

ISSN:0097-8930

Also published in ...

Authors

Henry Fuchs	University of North Carolina at Chapel Hill
Zvi M. Kedem	The University of Texas at Dallas
Bruce F. Naylor	The University of Texas at Dallas

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 140, Citation Count: 141

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/965105.807481 What is a DOI?

Warning: The download time has expired please click on the item to try again.

ABSTRACT

This paper describes a new algorithm for solving the hidden surface (or line) problem, to more rapidly generate realistic images of 3-D scenes composed of polygons, and presents the development of theoretical foundations in the area as well as additional related algorithms. As in many applications the environment to be displayed consists of polygons many of whose relative geometric relations are static, we attempt to capitalize on this by preprocessing the environment's database so as to decrease the run-time computations required to generate a scene. This preprocessing is based on generating a “binary space partitioning” tree whose in order traversal of visibility priority at run-time will produce a linear order, dependent upon the viewing position, on (parts of) the polygons, which can then be used to easily solve the hidden surface problem. In the application where the entire environment is static with only the viewing-position changing, as is common in simulation, the results presented will be sufficient to solve completely the hidden surface problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Berman, G. and Fryer, K.D. Introduction to Combinatorics, (1972) Academic Press.
	2	Henry Fuchs , Brian W. Johnson, An expandable multiprocessor architecture for video graphics (Preliminary Report), Proceedings of the 6th annual symposium on Computer architecture, p.58-67, April 23-25, 1979 [doi>10.1145/800090.802893]
	3	Schumaker, R.A., Brand, P., Gilliland, M. and Sharp, W. "Study for Applying Computer-Generated Images to Visual Simulation," AFHRL-TR-69-14, U.S. Air Force Human Resources Laboratory (1969)
	4	Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]

CITED BY 141

	Boris Aronov , Alan R. Davis , Tamal K. Dey , Sudebkumar P. Pal , D. Chithra Prasad, Visibility with reflection, Proceedings of the eleventh annual symposium on Computational geometry, p.316-325, June 05-07, 1995, Vancouver, British Columbia, Canada
	Subodh Kumar , Dinesh Manocha , William Garrett , Ming Lin, Back-face computation of polygon clusters, Proceedings of the thirteenth annual symposium on Computational geometry, p.487-488, June 04-06, 1997, Nice, France
	Cregg K. Cowan , Peter D. Kovesi, Automatic Sensor Placement from Vision Task Requirements, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.3, p.407-416, May 1988
	Tom Duff, Interval arithmetic recursive subdivision for implicit functions and constructive solid geometry, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.131-138, July 1992
	Ned Greene, Hierarchical polygon tiling with coverage masks, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.65-74, August 1996
	Pankaj K. Agarwal , Leonidas J. Guibas , T. M. Murali , Jeffrey Scott Vitter, Cylindrical static and kinetic binary space partitions, Proceedings of the thirteenth annual symposium on Computational geometry, p.39-48, June 04-06, 1997, Nice, France
	Csaba D. Tóth, Binary space partitions for line segments with a limited number of directions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.465-471, January 06-08, 2002, San Francisco, California
	Norman Chin , Steven Feiner, Fast object-precision shadow generation for area light sources using BSP trees, Proceedings of the 1992 symposium on Interactive 3D graphics, p.21-30, June 1992, Cambridge, Massachusetts, United States
	Andrei State , Mark A. Livingston , William F. Garrett , Gentaro Hirota , Mary C. Whitton , Etta D. Pisano , Henry Fuchs, Technologies for augmented reality systems: realizing ultrasound-guided needle biopsies, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.439-446, August 1996
	Mark de Berg , Joao Comba , Leonidas J. Guibas, A segment-tree based kinetic BSP, Proceedings of the seventeenth annual symposium on Computational geometry, p.134-140, June 2001, Medford, Massachusetts, United States
	Christian A. Duncan , Michael T. Goodrich , Stephen Kobourov, Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.300-309, January 17-19, 1999, Baltimore, Maryland, United States
	Michael Lee , Hanan Samet, Navigating through triangle meshes implemented as linear quadtrees, ACM Transactions on Graphics (TOG), v.19 n.2, p.79-121, April 2000
	John Snyder , Jed Lengyel, Visibility sorting and compositing without splitting for image layer decompositions, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.219-230, July 1998
	Dirk Bartz , Dirk Staneker , Wolfgang Straßer , Brian Cripe , Tom Gaskins , Kristann Orton , Michael Carter , Andreas Johannsen , Jeff Trom, Jupiter: a toolkit for interactive large model visualization, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
	Orion Sky Lawlor , Laxmikant V. Kalée, A voxel-based parallel collision detection algorithm, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	George Vaněček, Jr., BRep-Index: a multidimensional space partitioning tree, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.35-44, June 05-07, 1991, Austin, Texas, United States
	Han-Ming Chen , Wen-Teng Wang, The feudal priority algorithm on hidden-surface removal, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.55-64, August 1996
	Pankaj K. Agarwal , Jeff Erickson , Leonidas J. Guibas, Kinetic binary space partitions for intersecting segments and disjoint triangles, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.107-116, January 25-27, 1998, San Francisco, California, United States
	Chris Goad, Special purpose automatic programming for hidden surface elimination, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.167-178, July 1982
	Mel Slater , Yiorgos Chrysanthou, View volume culling using a probabilistic caching scheme, Proceedings of the ACM symposium on Virtual reality software and technology, p.71-77, September 1997, Lausanne, Switzerland
	Henry Fuchs , Gregory D. Abram , Eric D. Grant, Near real-time shaded display of rigid objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.65-72, July 1983
	Hansong Zhang , Dinesh Manocha , Tom Hudson , Kenneth E. Hoff, III, Visibility culling using hierarchical occlusion maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.77-88, August 1997
	Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
	Bernard Chazelle , David P. Dobkin , Nadia Shouraboura , Ayellet Tal, Strategies for polyhedral surface decomposition: an experimental study, Proceedings of the eleventh annual symposium on Computational geometry, p.297-305, June 05-07, 1995, Vancouver, British Columbia, Canada
	Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.61-70, July 1991
	Csaba D. T'oth, A note on binary plane partitions, Proceedings of the seventeenth annual symposium on Computational geometry, p.151-156, June 2001, Medford, Massachusetts, United States
	Jiandong Liang , Mark Green, Interaction techniques for a highly interactive 3D geometric modeling system, Proceedings on the second ACM symposium on Solid modeling and applications, p.475-476, May 19-21, 1993, Montreal, Quebec, Canada
	Samuel Boivin , André Gagalowicz, Advanced computer vision and graphics collaboration techniques for image-based rendering, Imaging and vision systems: theory, assessment and applications, Nova Science Publishers, Inc., Commack, NY, 2001
	Blaine Bell , Steven Feiner , Tobias Höllerer, View management for virtual and augmented reality, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida
	Ketan Mulmuley, Hidden surface removal with respect to a moving view point, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.512-522, May 05-08, 1991, New Orleans, Louisiana, United States
	Feng Xie , Michael Shantz, Adaptive hierarchical visibility in a tiled architecture, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.75-84, August 08-09, 1999, Los Angeles, California, United States
	Kim L. Shelley , Donald P. Greenberg, Path specification and path coherence, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.157-166, July 1982
	Bruce F. Naylor, Interactive playing with large synthetic environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.107-ff., April 09-12, 1995, Monterey, California, United States
	Mark de Berg , Mark Overmars , Otfried Schwarzkopf, Computing and verifying depth orders, Proceedings of the eighth annual symposium on Computational geometry, p.138-145, June 10-12, 1992, Berlin, Germany
	Seth Teller , Pat Hanrahan, Global visibility algorithms for illumination computations, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.239-246, September 1993
	Paul S. Heckbert , Pat Hanrahan, Beam tracing polygonal objects, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.119-127, July 1984
	T. M. Murali , Thomas A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proceedings of the 1997 symposium on Interactive 3D graphics, p.155-ff., April 27-30, 1997, Providence, Rhode Island, United States
	M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany
	Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998
	Cláudio Silva , Joseph S. B. Mitchell , Arie E. Kaufman, Fast rendering of irregular grids, Proceedings of the 1996 symposium on Volume visualization, p.15-ff., October 28-29, 1996, San Francisco, California, United States
	Thomas Funkhouser , Ingrid Carlbom , Gary Elko , Gopal Pingali , Mohan Sondhi , Jim West, A beam tracing approach to acoustic modeling for interactive virtual environments, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.21-32, July 1998
	Marshall Bern , David Dobkin , David Eppstein , Robert Grossman, Visibility with a moving point of view, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.107-117, January 22-24, 1990, San Francisco, California, United States
	Oded Sudarsky , Craig Gotsman, Dynamic Scene Occlusion Culling, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.13-29, January 1999
	Pei-Wen Liu , Lih-Shyang Chen , Su-Chou Chen , Jong-Ping Chen , Fang-Yi Lin , Shy-Shang Hwang, Distributed Computing: New Power for Scientific Visualization, IEEE Computer Graphics and Applications, v.16 n.3, p.42-51, May 1996
	Jonathan Shade , Dani Lischinski , David H. Salesin , Tony DeRose , John Snyder, Hierarchical image caching for accelerated walkthroughs of complex environments, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.75-82, August 1996
	Yiorgos Chrysanthou , Mel Slater, Shadow volume BSP trees for computation of shadows in dynamic scenes, Proceedings of the 1995 symposium on Interactive 3D graphics, p.45-50, April 09-12, 1995, Monterey, California, United States
	Bruce Naylor , John Amanatides , William Thibault, Merging BSP trees yields polyhedral set operations, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.115-124, Aug. 1990
	Georges Winkenbach , David H. Salesin, Computer-generated pen-and-ink illustration, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.91-100, July 1994
	M. R. Stytz , G. Frieder , O. Frieder, Three-dimensional medical imaging: algorithms and computer systems, ACM Computing Surveys (CSUR), v.23 n.4, p.421-499, Dec. 1991
	Franco P. Preparata , Jeffrey S. Vitter , Mariette Yvinec, Computation of the axial view of a set of isothetic parallelepipeds, ACM Transactions on Graphics (TOG), v.9 n.3, p.278-300, July 1990
	B. N. Khoromskij , J. M. Melenk, An efficient direct solver for the boundary concentrated FEM in 2D, Computing, v.69 n.2, p.91-117, October 2002
	Pankaj K. Agarwal , T. M. Murali , Jeffrey Scott Vitter, Practical techniques for constructing binary space partitions for orthogonal rectangles, Proceedings of the thirteenth annual symposium on Computational geometry, p.382-384, June 04-06, 1997, Nice, France
	Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.100-106, January 22-24, 1990, San Francisco, California, United States
	H. Hubschman , S. W. Zucker, Frame-to-frame coherence and the hidden surface computation: constraints for a convex world, ACM Transactions on Graphics (TOG), v.1 n.2, p.129-162, April 1982
	Harold Hubschman , Steven W. Zucker, Frame-to-frame coherence and the hidden surface computation: Constraints for a convex world, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.45-54, August 1981
	Sanjeev Khanna , S. Muthukrishnan , Mike Paterson, On approximating rectangle tiling and packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 25-27, 1998, San Francisco, California, United States
	Cláudio T. Silva , Joseph S. B. Mitchell , Peter L. Williams, An exact interactive time visibility ordering algorithm for polyhedral cell complexes, Proceedings of the 1998 IEEE symposium on Volume visualization, p.87-94, October 19-20, 1998, Research Triangle Park, North Carolina, United States
	T. Hudson , D. Manocha , J. Cohen , M. Lin , K. Hoff , H. Zhang, Accelerated occlusion culling using shadow frusta, Proceedings of the thirteenth annual symposium on Computational geometry, p.1-10, June 04-06, 1997, Nice, France
	H. Edelsbrunner, An acyclicity theorem for cell complexes in d dimensions, Proceedings of the fifth annual symposium on Computational geometry, p.145-151, June 05-07, 1989, Saarbruchen, West Germany
	A. T. Campbell, III , Donald S. Fussell, Adaptive mesh generation for global diffuse illumination, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.155-164, Aug. 1990
	Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.99-106, July 1989
	Jefferson Han , Brian Smith, CU-SeeMe VR immersive desktop teleconferencing, Proceedings of the fourth ACM international conference on Multimedia, p.199-207, November 18-22, 1996, Boston, Massachusetts, United States
	Jiří Bittner, Efficient construction of visibility maps using approximate occlusion sweep, Proceedings of the 18th spring conference on Computer graphics, April 24-27, 2002, Budmerice, Slovakia
	Eugene Zhang , Greg Turk, Visibility-guided simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
	Wu-chang Feng , Francis Chang , Wu-chi Feng , Jonathan Walpole, Provisioning on-line games: a traffic analysis of a busy counter-strike server, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France
	John Hershberger , Subhash Suri, Binary space partitions for 3D subdivisions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Masato Ogata , Shigeru Muraki , Xuezhen Liu , Kwan-Liu Ma, The design and evaluation of a pipelined image compositing device for massively parallel volume rendering, Proceedings of the 2003 Eurographics/IEEE TVCG Workshop on Volume graphics, July 07-08, 2003, Tokyo, Japan
	Daniel Vlasic , Hanspeter Pfister , Sergey Molinov , Radek Grzeszczuk , Wojciech Matusik, Opacity light fields: interactive rendering of surface light fields with view-dependent opacity, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California
	Samuel M. Goldwasser, A generalized object display processor architecture, ACM SIGARCH Computer Architecture News, v.12 n.3, p.38-47, June 1984
	Türker Yilmaz , Uğur Güdükbay , Varol Akman, Modeling and visualization of complex geometric environments, Geometric modeling: techniques, applications, systems and tools, Kluwer Academic Publishers, Norwell, MA, 2004
	Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003
	Madhav K. Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental Algorithms for Collision Detection Between Polygonal Models, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.51-64, January 1997
	Jean-Eudes Marvie , Kadi Bouatouch, A VRML97-X3D extension for massive scenery management in virtual worlds, Proceedings of the ninth international conference on 3D Web technology, April 05-08, 2004, Monterey, California
	Kalpathi R. Subramanian , Bruce F. Naylor, Converting Discrete Images to Partitioning Trees, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.273-288, July 1997
	M. R. Stytz , G. Frieder , O. Frieder, Three-dimensional medical imaging: algorithms and computer systems, ACM Computing Surveys (CSUR), v.23 n.4, p.421-499, Dec. 1991
	Peter L. Williams, Visibility-ordering meshed polyhedra, ACM Transactions on Graphics (TOG), v.11 n.2, p.103-126, April 1992
	Seth J. Teller, Computing the antipenumbra of an area light source, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.139-148, July 1992
	Per H. Christensen , Dani Lischinski , Eric J. Stollnitz , David H. Salesin, Clustering for glossy global illumination, ACM Transactions on Graphics (TOG), v.16 n.1, p.3-33, Jan. 1997
	Madhav Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental algorithms for collision detection between solid models, Proceedings of the third ACM symposium on Solid modeling and applications, p.293-304, May 17-19, 1995, Salt Lake City, Utah, United States
	Xiaolin Wu, Color quantization by dynamic programming and principal analysis, ACM Transactions on Graphics (TOG), v.11 n.4, p.348-372, Oct. 1992
	Georges Winkenbach , David H. Salesin, Rendering parametric surfaces in pen and ink, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.469-476, August 1996
	Tom Duff, Compositing 3-D rendered images, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.41-44, Jul. 1985
	William F. Garrett , Henry Fuchs , Mary C. Whitton , Andrei State, Real-time incremental visualization of dynamic ultrasound volumes using parallel BSP trees, Proceedings of the 7th conference on Visualization '96, p.235-ff., October 28-29, 1996, San Francisco, California, United States
	D. S. Andrews , J. Soenyink, Geometry in GIS is not combinatorial: segment intersection for polygon overlay, Proceedings of the eleventh annual symposium on Computational geometry, p.424-425, June 05-07, 1995, Vancouver, British Columbia, Canada
	William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
	Jeff Erickson, Local polyhedra and geometric graphs, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Tim Purcell, Parallel ray tracing on a chip, Practical parallel rendering, A. K. Peters, Ltd., Natick, MA, 2002
	Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan, Slice and dice: a simple, improved approximate tiling recipe, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.455-464, January 06-08, 2002, San Francisco, California
	Hanan Samet , Robert E. Webber, Hierarchical Data Structures and Algorithms for Computer Graphics, IEEE Computer Graphics and Applications, v.8 n.4, p.59-65, 67-75, July 1988
	K. R. Subramanian , Bruce Naylor, Representing medical images with partitioning trees, Proceedings of the 3rd conference on Visualization '92, October 19-23, 1992, Boston, Massachusetts
	O. Günther , J. Bilmes, Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.342-356, September 1991
	J. Andreas Baerentzen , Henrik Aanaes, Signed Distance Computation Using the Angle Weighted Pseudonormal, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.243-253, May 2005
	Claudio T. Silva , Joseph S. B. Mitchell, The Lazy Sweep Ray Casting Algorithm for Rendering Irregular Grids, IEEE Transactions on Visualization and Computer Graphics, v.3 n.2, p.142-157, April 1997
	Chi-Wing Fu , Tien-Tsin Wong , Wai-Shun Tong , Chi-Keung Tang , Andrew J. Hanson, Binary-Space-Partitioned Images for Resolving Image-Based Visibility, IEEE Transactions on Visualization and Computer Graphics, v.10 n.1, p.58-71, January 2004
	Dan Gordon , Shuhong Chen, Front-to-Back Display of BSP Trees, IEEE Computer Graphics and Applications, v.11 n.5, p.79-85, September 1991
	Didier Badouel , Kadi Bouatouch , Thierry Priol, Distributing Data and Control for Ray Tracing in Parallel, IEEE Computer Graphics and Applications, v.14 n.4, p.69-77, July 1994
	K. Bowyer , M. Sallam , D. Eggert , J. Stewman, Computing the Generalized Aspect Graph for Objects with Moving Parts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.6, p.605-610, June 1993
	Hanan Samet, Object-based and image-based object representations, ACM Computing Surveys (CSUR), v.36 n.2, p.159-217, June 2004
	Chris Joslin , Nadia Magnenat-Thalmann, Significant facet retrieval for real-time 3D sound rendering in complex virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, October 01-03, 2003, Osaka, Japan
	James T. Klosowski , Cláudio T. Silva, Efficient Conservative Visibility Culling Using the Prioritized-Layered Projection Algorithm, IEEE Transactions on Visualization and Computer Graphics, v.7 n.4, p.365-379, October 2001
	Wenting Zheng , Hanqiu Sun , Hujun Bao , Qunsheng Peng, Rendering of virtual environments based on polygonal & point-based models, Proceedings of the ACM symposium on Virtual reality software and technology, November 11-13, 2002, Hong Kong, China
	Sunil Arya, Binary space partitions for axis-paralles line segments: size-height tradeoffs, Information Processing Letters, v.84 n.4, p.201-206, 30 November 2002
	Steven P. Callahan , Milan Ikits , Joao L. D. Comba , Claudio T. Silva, Hardware-Assisted Visibility Sorting for Unstructured Volume Rendering, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.285-295, May 2005
	Jeff Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications, v.31 n.1-2, p.101-125, May 2005
	Wu-chang Feng , Francis Chang , Wu-chi Feng , Jonathan Walpole, A traffic characterization of popular on-line games, IEEE/ACM Transactions on Networking (TON), v.13 n.3, p.488-500, June 2005
	Naga K. Govindaraju , Michael Henson , Ming C. Lin , Dinesh Manocha, Interactive visibility ordering and transparency computations among geometric primitives in complex environments, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia
	Antti Nurminen, m-LOMA - a mobile 3D city map, Proceedings of the eleventh international conference on 3D web technology, April 18-21, 2006, Columbia, Maryland
	Diego Nehab , Joshua Barczak , Pedro V. Sander, Triangle order optimization for graphics hardware computation culling, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California
	Jianbing Huang , Michael B. Carter, Interactive Transparency Rendering for Large CAD Models, IEEE Transactions on Visualization and Computer Graphics, v.11 n.5, p.584-595, September 2005
	John Hershberger , Subhash Suri , Csaba D. Toth, Binary space partitions of orthogonal subdivisions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Boris Aronov , Vladlen Koltun , Micha Sharir, Cutting triangular cycles of lines in space, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Mark de Berg , Micha Streppel, Approximate range searching using binary space partitions, Computational Geometry: Theory and Applications, v.33 n.3, p.139-151, February 2006
	Eyal Ackerman , Gill Barequet , Ron Y. Pinter , Dan Romik, The number of guillotine partitions in d dimensions, Information Processing Letters, v.98 n.4, p.162-167, 31 May 2006
	Dani Lischinski , Filippo Tampieri , Donald P. Greenberg, Discontinuity Meshing for Accurate Radiosity, IEEE Computer Graphics and Applications, v.12 n.6, p.25-39, November 1992
	Sanjoy Dasgupta , Yoav Freund, Random projection trees and low dimensional manifolds, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Roland T. Chin , Charles R. Dyer, Model-based recognition in robot vision, ACM Computing Surveys (CSUR), v.18 n.1, p.67-108, March 1986
	A. Paoluzzi , F. Bernardini , C. Cattani , V. Ferrucci, Dimension-independent modeling with simplicial complexes, ACM Transactions on Graphics (TOG), v.12 n.1, p.56-102, Jan. 1993
	Bruce H. McCormick , Brad Busse , Purna Doddapaneni , Zeki Melek , John Keyser, Compression, segmentation, and modeling of filamentary volumetric data, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	J. Anderson , J. Baltes, An agent-based approach to introductory robotics using robotic soccer, International Journal of Robotics and Automation, v.21 n.2, p.141-152, April 2006
	Peter Shirley, Data structures for graphics, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Heiko Friedrich , Johannes Günther , Andreas Dietrich , Michael Scherbaum , Hans-Peter Seidel , Philipp Slusallek, Exploring the use of ray tracing for future games, Proceedings of the 2006 ACM SIGGRAPH symposium on Videogames, p.41-50, July 30-31, 2006, Boston, Massachusetts
	Shinichi Fukushige , Hiromasa Suzuki, Voronoi diagram depth sorting for polygon visibility ordering, Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia, November 29-December 02, 2006, Kuala Lumpur, Malaysia
	Todd Keeler , John Fedorkiw , Sherif Ghali, The spherical visibility map, Computer-Aided Design, v.39 n.1, p.17-26, January, 2007
	Sven Woop , Gerd Marmitt , Philipp Slusallek, B-KD trees for hardware accelerated ray tracing of dynamic scenes, Proceedings of the 21st ACM SIGGRAPH/Eurographics symposium on Graphics hardware, September 03-04, 2006, Vienna, Austria
	Norm Dadoun , David G. Kirkpatrick , John P. Walsh, The geometry of beam tracing, Proceedings of the first annual symposium on Computational geometry, p.55-61, June 05-07, 1985, Baltimore, Maryland, United States
	Oliver Günther , Eugene Wong, A Dual Space Representation for Geometric Data, Proceedings of the 13th International Conference on Very Large Data Bases, p.501-506, September 01-04, 1987
	Nelson Max , Pat Hanrahan , Roger Crawfis, Area and volume coherence for efficient visualization of 3D scalar functions, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.27-33, Nov. 1990
	J. S. Pantazopoulos , S. G. Tzafestas, An Efficient Algorithm for Ray Tracing, Journal of Intelligent and Robotic Systems, v.28 n.1-2, p.171-180, June 2000
	Kiriakos N. Kutulakos , Steven M. Seitz, A Theory of Shape by Space Carving, International Journal of Computer Vision, v.38 n.3, p.199-218, July-August 2000
	Hanan Samet, A sorting approach to indexing spatial data, ACM SIGGRAPH 2008 classes, August 11-15, 2008, Los Angeles, California
	Voicu Popescu , Elisha Sacks , Chunhui Mei, Sample-Based Cameras for Feed Forward Reflection Rendering, IEEE Transactions on Visualization and Computer Graphics, v.12 n.6, p.1590-1600, November 2006
	Stefano Boschi , Miriam Di lanni , Pilu Crescenzi , Gianluca Rossi , Paola Vocca, MOMOSE: a mobility model simulation environment for mobile wireless ad-hoc networks, Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops, March 03-07, 2008, Marseille, France
	Simon Heinzle , Gaël Guennebaud , Mario Botsch , Markus Gross, A hardware processing unit for point sets, Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, June 20-21, 2008, Sarajevo, Bosnia and Herzegovina
	Simon Perkins , David Jacka , James Gain , Patrick Marais, A spatial awareness framework for enhancing game agent behaviour, Proceedings of the 2008 ACM SIGGRAPH symposium on Video games, August 09-10, 2008, Los Angeles, California
	Christian Rubino , John Power, Level design optimization guidelines for game artists using the epic games: Unreal editor and unreal engine 2, Computers in Entertainment (CIE), v.6 n.4, December 2008
	Mikola Lysenko , Roshan D'Souza , Ching-Kuan Shene, Improved Binary Space Partition merging, Computer-Aided Design, v.40 n.12, p.1113-1120, December, 2008
	Abel J. P. Gomes , José F. M. Morgado , Edgar S. Pereira, A BSP-based algorithm for dimensionally nonhomogeneous planar implicit curves with topological guarantees, ACM Transactions on Graphics (TOG), v.28 n.2, p.1-24, April 2009
	Csaba D. Tóth, Binary plane partitions for disjoint line segments, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Jeff Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications, v.31 n.1-2, p.101-125, May 2005
	Carlos J. Ogayar , Rafael J. Segura , Francisco R. Feito, Technical section: Point in solid strategies, Computers and Graphics, v.29 n.4, p.616-624, August, 2005
	Mark de Berg , Micha Streppel, Approximate range searching using binary space partitions, Computational Geometry: Theory and Applications, v.33 n.3, p.139-151, February 2006