@TechReport{EVL-1998-675, author = "Andr{\'e} Hinkenjann and Heinrich M{\"u}ller", title = "Determining Visibility between Extended Objects", number = "675/1998", type = "Research Report", institution = "University of Dortmund", address = "Universit{\"a}t Dortmund, 44221 Dortmund, Germany", month = aug, year = "1998", who = "Havran Vlastimil: VIS-0090", } @TechReport{EVL-1996-10, author = "Andr{\'e} Hinkenjann and Heinrich M{\"u}ller", title = "Hierarchical Blocker Trees for Global Visibility Calculation", number = "621/1996", type = "Research Report", institution = "University of Dortmund", month = aug, year = "1996", abstract = "We present a technique to determine visibility within geometric scenes, as required for more advanced rendering approaches in computer graphics. Visibility types considered are completely visible, completely blocked and partially blocked. In a preprocessing step, the given scene is recursively subdivided into a hierarchy of subscenes. For each resulting subscene, a so called blocker tree is calculated which holds information about the visibility type of viewing lines passing through a bounding box enclosing the scene. The resulting hierarchical blocker tree is used to answer queries for the visibility between two subscenes. This approach is implemented in flatland based on quadtrees, and analyzed experimentally.", postscript-url = "ftp://euklid.informatik.uni-dortmund.de/pub/reports/ls7/rr-6 21.ps.gz", evlib-url = "http://infovis.zib.de:8000/Dienst/UI/2.0/Describe/evl.computat ionalgeometry%2FEVL-1996-10", evlib-revision = "1st", evlib-postscript-md5 = "2abfecb868f469b0af855c1167f7dd14", who = "Havran Vlastimil: VIS-0089", } @inproceedings{addpp-vr-95, author = "Boris Aronov and Alan R. Davis and Tamal K. Dey and Sudebkumar P. Pal and D. Chithra Prasad", title = "Visibility with Reflection", booktitle = "Proc. 11th Annu. ACM Sympos. Comput. Geom.", year = 1995, pages = "316--325", keywords = "mirrors", cites = "addpp-vmr-95, ak-frtrc-87, bo-arcgi-79, dpp-agpvr-95, ea-lacvp-81, fkn-vsgpt-80, ghlst-ltavs-87, g-bp-86, hv-splsp-49, k-ealdp-89, kw-onupp-91, l-vsp-83, ll-ccagp-86, lpsssstwy-clcsp-88, o-agta-87, rty-ccrt-94, s-rrag-92, s-mlppr-87, s-sldps-90, ZZZ", update = "98.03 bibrelex, 95.09 mitchell", who = "Havran Vlastimil: VIS-0088", } @Article{Sharir:1992:SOS, author = "Micha Sharir and Mark H. Overmars", title = "A Simple Output-Sensitive Algorithm for Hidden Surface Removal", journal = "ACM Transactions on Graphics", volume = "11", number = "1", pages = "1--11", month = jan, year = "1992", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Fri Jan 5 07:58:42 MST 1996", url = "http://www.acm.org/pubs/toc/Abstracts/0730-0301/112141.html", abstract = "We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If $k$ is the combinatorial complexity of the output visibility map, the method runs in time $O(n\sqrt{k} \log n)$. The method is extended to work for other classes of objects as well, sometimes with even improved time bounds. For example, we obtain an algorithm that performs hidden surface removal for n (nonintersecting) balls in time $O(n^{3/2}\log n+k)$", acknowledgement = ack-nhfb, keywords = "algorithms; hidden surface removal; theory", subject = "{\bf I.3.7}: Computing Methodologies, COMPUTER GRAPHICS, Three-Dimensional Graphics and Realism, Hidden line/surface removal. {\bf F.2.2}: Theory of Computation, ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and Problems, Geometrical problems and computations. {\bf I.3.5}: Computing Methodologies, COMPUTER GRAPHICS, Computational Geometry and Object Modeling, Geometric algorithms, languages, and systems.", who = "Havran Vlastimil: VIS-0087", } @InProceedings{Westermann:1997:VVO, author = "R{\"{u}}diger Westermann and Thomas Ertl", title = "The {VSBUFFER}: Visibility Ordering of Unstructured Volume Primitives by Polygon Drawing", booktitle = "IEEE Visualization \'97", editor = "Roni Yagel and Hans Hagen", year = "1997", organization = "IEEE", month = nov, pages = "35--42", who = "Havran Vlastimil: VIS-0086", } @InProceedings{COZ-gi98, title = "Visibility Streaming for Network-based Walkthroughs", author = "Daniel Cohen-Or and Eyal Zadicario", booktitle = "Graphics Interface", year = "1998", month = jun, pages = "1--7", who = "Havran Vlastimil: VIS-0085", } @InProceedings{Soler:1996:AEB, author = "Cyril Soler and Fran{\c{c}}ois Sillion", title = "Accurate Error Bounds for Multi-Resolution Visibility", booktitle = "Eurographics Rendering Workshop 1996", editor = "Xavier Pueyo and Peter Schr{\"{o}}der", year = "1996", organization = "Eurographics", publisher = "Springer Wein", address = "New York City, NY", month = jun, pages = "133--142", note = "ISBN 3-211-82883-4", keywords = "error bounds, hierarchical radiosity, multi-resolution visibility, error-driven refinement, visibility correlation", annote = "We propose a general error-driven algorithm to compute form factors in complex scenes equipped with a suitable cluster hierarchy. This opens the way for the efficient approximation of form factors in a controlled manner, with guaranteed error bounds at every stage of the calculation. In particular we discuss the issues of bounding the error in the form factor approximation using average cluster transmittance, combining subcluster calculations with proper treatment of visibility correlation, and the calculation and storage of the necessary information in the hierarchy. We present results from a 2D implementation, that demonstrate the validity of the approach; the form factor approximations are efficiently bounded by the user-supplied threshold.", who = "Havran Vlastimil: VIS-0084", } @Article{Pueyo:1996:OAT, author = "Xavier Pueyo and Frederic P{\'e}rez and Toni Sellar{\`e}s and Josep Suy", title = "An object-oriented approach for teaching visibility computation algorithms", journal = "Computers and Graphics", volume = "20", number = "4", pages = "605--610", month = jul # "--" # aug, year = "1996", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Wed Feb 5 07:22:58 MST 1997", acknowledgement = ack-nhfb, affiliation = "Universitat de Girona", affiliationaddress = "Spain", classification = "721.1; 723; 723.5; 921.4", journalabr = "Comput Graphics (Pergamon)", keywords = "Abstraction; Algorithms; Computational complexity; Computational geometry; Computer graphics; Object recognition; Ray casting; Scan line; Visibility computation algorithms; Visualization", who = "Havran Vlastimil: VIS-0083", } @InProceedings{james-cgf-98, author = "A. James and A.M. Day", title = "The Priority Face Determination Tree for Hidden Surface Removal", pages = "55-71", booktitle = "Computer Graphics Forum", volume = "17", number = "1", year = "1998", month = "march", who = "Havran Vlastimil: VIS-0082", } @inproceedings{james-eguk-98, author = "A. James and A.M. Day", title = "Conflict Neutralization on Binary Space Partitioning (extended abstract)", booktitle = "Eurographics UK Proceedings", year = 1998, month = "march", volume = 16, pages = "225 - 229", who = "Havran Vlastimil: VIS-0081", } @inproceedings{james-eguk-97, author = "A. James and A.M. Day", title = "The Priority Face Determination Tree", booktitle = "Eurographics UK Proceedings", year = 1997, month = "march", volume = 15, pages = "21 - 46", who = "Havran Vlastimil: VIS-0080", } @inproceedings{cohen-egc-98, author = "D. Cohen-Or and G. Fibich and D. Halperin and E. Zadicario", title = "Conservative Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes", booktitle = "EUROGRAPHICS'98", year = "1998", who = "Havran Vlastimil: VIS-0079", } @InCollection{deb93, author = "M. De Berg", title = "Ray shooting, Depth Orders and Hidden Surface Removal", year = "1993", booktitle = "Lecture Notes in Computer Science", volume = "703", publisher = "Springer Verlag, New York", topic = "visibility", who = "Havran Vlastimil: VIS-0078", } @InProceedings{Funkhouser98, author = "Thomas Funkhouser and Ingrid Carlbom and Gary Elko and Gopal Pingali and Mohan Sondhi and Jim West", title = "A Beam Tracing Approach to Acoustic Modeling for Interactive Virtual Environments", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '98)", pages = "21--32", month = jul, year = "1998", who = "Havran Vlastimil: VIS-0077", } @PhdThesis{Teller92phd, author = "Seth J. Teller", title = "Visibility Computations in Densely Occluded Polyhedral Environments", school = "CS Division, UC Berkeley", month = oct, year = "1992", note = "Tech. Report UCB/CSD-92-708", keywords = "computational geometry, architectural walkthrough", who = "Havran Vlastimil: VIS-0076", } @InProceedings{Aliaga:1997:AWU, author = "Daniel G. Aliaga and Anselmo A. Lastra", title = "Architectural Walkthroughs Using Portal Textures", booktitle = "IEEE Visualization \'97", editor = "Roni Yagel and Hans Hagen", year = "1997", organization = "IEEE", month = nov, pages = "355--362", who = "Havran Vlastimil: VIS-0075", } @InProceedings{Stewart93-OSACS, author = "A. James Stewart and Sherif Ghali", month = aug, year = "1993", title = "An {Output} {Sensitive} {Algorithm} for the {Computation} of {Shadow} {Boundaries}", booktitle = "Canadian Conference on Computational Geometry", pages = "291--296", who = "Havran Vlastimil: VIS-0074", } @InProceedings{Kumar:1996:HBF, author = "Subodh Kumar and Dinesh Manocha and William Garrett and Ming Lin", title = "Hierarchical Back-Face Computation", booktitle = "Eurographics Rendering Workshop 1996", editor = "Xavier Pueyo and Peter Schr{\"{o}}der", year = "1996", organization = "Eurographics", publisher = "Springer Wein", address = "New York City, NY", month = jun, pages = "235--244", note = "ISBN 3-211-82883-4", annote = "We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a pre-processing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine if it is in front of or behind a cluster. Due to coherence, the algorithm's performance is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull almost half the polygons. The algorithm accounts for 5 - 10% of the total CPU time per frame on an SGI Indigo2 Extreme. The overall frame rate is improved by 40 - 75% as compared to the standard back-face culilng implemented in hardware.", who = "Havran Vlastimil: VIS-0073", } @InProceedings{Zhang97a, author = "Hansong Zhang and Kenneth E. Hoff III", month = "???", year = "1997", title = "Accelerated Walkthrough of Large Spline Models", booktitle = "Symposium on Interactive 3D Graphics, 1997", who = "Havran Vlastimil: VIS-0072", } @Article{Orti:1996:RDS, author = "Rachel Orti and Stephane Riviere and Fredo Durand and Claude Puech", title = "Radiosity for Dynamic Scenes in Flatland with the Visibility Complex", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "15", number = "3", pages = "C237--C248", month = sep, year = "1996", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Tue Mar 17 15:44:38 MST 1998", acknowledgement = ack-nhfb, affiliation = "iMAGIS\slash GRAVIR - IMAG", affiliationaddress = "Grenoble, Fr", affiliationaddress = "Fr", classification = "723.2; 723.5; 741.1; 741.2; 921.4; C4260 (Computational geometry); C6130B (Graphics techniques)", conference = "Proceedings of the 1996 17th Annual Conference and Exhibition of the European Association for Computer Graphics, EUROGRAPHICS'96", conflocation = "Poitiers, France; 26-30 Aug. 1996", conftitle = "European Association for Computer Graphics 17th Annual Conference and Exhibition. EUROGRAPHICS '96", corpsource = "IMAG, Grenoble, France", journalabr = "Comput Graphics Forum", keywords = "Algorithms; Architectural simulation; Calculations; Computational geometry; Computer graphics; Computer simulation; Data structures; Discontinuity mesh; Form factor; Global illumination; Image synthesis; Lighting; Lighting design; Radiosity; Static environment; Three dimensional; Two dimensional; Visibility; Visibility complex; Visualization", keywords = "2D method; algorithm; Algorithms; Architectural simulation; brightness; Calculations; computational geometry; Computational geometry; computational geometry; computer graphics; Computer graphics; Computer simulation; data structure; Data structures; discontinuity mesh; Discontinuity mesh; discontinuity mesh; dynamic environments; dynamic scenes; factors; flatland; form; Form factor; global; Global illumination; illumination; Image synthesis; image synthesis; Lighting; lighting; Lighting design; polygonal scenes; Radiosity; radiosity method; Static environment; static scenes; Three dimensional; Two dimensional; visibility; Visibility; visibility; Visibility complex; visibility complex; Visualization", meetingaddress = "Poitiers, Fr", meetingdate = "Aug 26--30 1996", meetingdate2 = "08/26--30/96", sponsor = "CNRS; ERCIM; BARCO; EDF; SUN; et al", sponsororg = "CNRS; BARCO; Electr. France; et al", treatment = "T Theoretical or Mathematical", who = "Havran Vlastimil: VIS-0071", } @InProceedings{Kumar97, author = "Subodh Kumar and Dinesh Manocha and Kenneth E. Hoff III and Hansong Zhang", month = "???", year = "1997", title = "Accelerated Walkthrough of Large Spline Models", booktitle = "Symposium on Interactive 3D Graphics, 1997", who = "Havran Vlastimil: VIS-0070", } @InProceedings{Orti96-UVCRC, author = "Rachel Orti and Stephane Riviere and Fredo Durand and Claude Puech", month = may, year = "1996", title = "Using the {Visibility} {Complex} for {Radiosity} {Computation}", booktitle = "Lecture Notes in Computer Science (Applied Computational Geometry: Towards Geometric Engineering)", volume = "1148", pages = "177--190", publisher = "Springer-Verlag", address = "Berlin, Germany", who = "Havran Vlastimil: VIS-0069", } @Article{EVL-1996-194, author = "R. Yagel and W. Ray", title = "Visibility Computation for Efficient Walkthrough Complex Environments", journal = "PRESENCE", volume = "5", number = "1", pages = "1--16", year = "1996", language = "en", abstract = "In many virtual reality applications as well as general computer graphics we need to consider large numbers of objects in order to render one image. In many cases rendering can be preceded by a culling phase which employs simple mechanisms to reject most of the objects. As a result, only a very small portion of the model has to go through the time consuming process of hidden object removal. We report on such a culling mechanism that is based on regular space subdivision into cells followed by cell classification into interior, exterior, and wall cells. A special cell-to-cell visibility algorithm is then activated between every two non-exterior cells. Only the objects in the potentially visible set of cells are actually submitted to the hidden object removal algorithm. We report on the implementation of the algorithm and its performance for walkthrough of various environments.", postscript-url = "http://www.cis.ohio-state.edu/volviz/Papers/1995/presence.ps.gz", evlib-url = "http://visinfo.zib.de:80/Dienst/UI/2.0/Describe/evl.volumerendering%2FEVL-1996-194", postscript-url-md5 = "614ddffe140b1fb6e4b238c7923097aa", evlib-revision = "1st", who = "Havran Vlastimil: VIS-0068", } @TechReport{Krishnan:TR94063:1994, author = "S. Krishnan and D. Manocha", number = "TR94-063", title = "Global Visibility and Hidden Surface Algorithms for Free Form Surfaces", institution = "University of North Carolina, Chapel Hill, NC 27599-3175", year = 1994, month = nov, documentURL = "ftp://ftp.cs.unc.edu/pub/users/manocha/papers/visibility/visib.ps.Z", who = "Havran Vlastimil: VIS-0067", } @Misc{Hoff98, author = "Kenneth E. Hoff III", title = "Faster 3D Game Graphics by Not Drawing What Is Not Seen", documentURL = "http://www.acm.org/crossroads/xrds3-4/faster3d.html", who = "Havran Vlastimil: VIS-0066", } @InProceedings{Luebke:1995:PMS, author = "David Luebke and Chris Georges", title = "Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets", editor = "Pat Hanrahan and Jim Winget", pages = "105--106", booktitle = "1995 Symposium on Interactive {3D} Graphics", year = "1995", organization = "ACM SIGGRAPH", month = apr, who = "Havran Vlastimil: VIS-0065", } @Misc{Holmes96, author = "John Holmes", title = "Binary Space Partitioning (BSP) Trees", documentURL = "http://www.cis.ufl.edu/~jch/is-final.ps", who = "Havran Vlastimil: VIS-0064", } @Misc{BSPFAQ, author = "et al", title = "BSP Tree Frequently Asked Questions (FAQ)", documentURL = "http://reality.sgi.com/bspfaq/", who = "Havran Vlastimil: VIS-0063", } @Misc{Campbel96, author = "A.T. Campbell, III", title = "BSP Trees: An Introduction and an Implementation", year = 1996, month = mar, pages = "8", who = "Havran Vlastimil: VIS-0062", } @InProceedings{Martinka95a, author = "Josef Martinka and Ludovit Niepel and Andrej Ferko", title = "Sweeping Algorithm for Scene Visibility Graph", pages = "11--16", booktitle = "Summer school in computer graphics in Bratislava (SCCG95)", year = "1995", month = jun, keywords = "ray tracing", who = "Havran Vlastimil: VIS-0061", } @InProceedings{Sojka92, author = "E. Sojka", title = "Potencial viditelnosti a jeho vypocet", booktitle = "Winter School of Computer Graphics 1992", year = "1992", month = "feb", pages = "36--46", note = "held at University of West Bohemia, Plzen, Czech Republic, February 1992", who = "Havran Vlastimil: VIS-0060", } @InProceedings{Fuchs80a, author = "Fuchs, H. and Kedem, Z. M. and Naylor, B. F.", title = "On Visible Surface Generation by a Priori Tree Structures", pages = "124--133", booktitle = "Computer Graphics (SIGGRAPH '80 Proceedings)", volume = "14", number = "3", year = "1980", month = jul, keywords = "graphical data/base/structures, Algorithmic Aspects hidden line/surface removal, surface generation, Three-Dimensional Graphics realism, Applications of Computer Graphics electrical engineering power engineering, Painter's Algorithm", who = "Havran Vlastimil: VIS-0059", } @TechReport{Cazals:3204:1997, author = "F. Cazals and M. Sbert", number = "RR-3204", title = "Some integral geometry tools to estimate the complexity of 3D scenes", institution = "The French National Institue for Research in Computer Science and Control (INRIA)", year = 1997, month = jul, documentURL = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-3204.ps.gz", keywords = "Average case analysis, Stochastic geometry, Computer Graphics", who = "Havran Vlastimil: VIS-0058", } @inproceedings{pv-cvgpt-95, author = "M. Pocchiola and G. Vegter", title = "Computing the Visibility Graph via Pseudo-Triangulations", booktitle = "Proc. 11th Annu. ACM Sympos. Comput. Geom.", year = 1995, pages = "248--257", keywords = "topological sweep, visibility complex", cites = "ce-oails-92, eg-tsa-89, gt-ltasc-85, gm-osacv-91, hmrt-sjslt-86, ow-nmcvg-88, pv-vc-93, s-ec-86, w-cvgnl-85, ZZZ", update = "98.03 bibrelex, 96.05 pocchiola, 95.09 mitchell", who = "Havran Vlastimil: VIS-0057", } @inproceedings{pv-vc-93, author = "M. Pocchiola and G. Vegter", title = "The visibility complex", booktitle = "Proc. 9th Annu. ACM Sympos. Comput. Geom.", year = 1993, pages = "328--337", precedes = "pv-vc-96", cites = "cg-vippg-89, gm-osacv-91, hm-oacvp-91, p-gfr-90, v-vddsv-90, v-dmvg-91, w-cvgnl-85, ZZZ", update = "98.03 bibrelex, 97.03 devillers, 93.09 jones", who = "Havran Vlastimil: VIS-0056", } @TechReport{Mount:TR9771, author = "David M. Mount and Fan-Tao Pu", number = "UMIACS-TR-96-71", title = "Stabbing Orthogonal Objects in 3-Space", institution = "University of Maryland Institute for Advanced Computer Studies~Dept. of Computer Science, Univ. of Maryland", year = 1996, month = oct, documentURL = "ftp://ftp.cs.umd.edu/pub/papers/papers/3701/3701.ps.Z", keywords = "Lines in 3-space, Plucker coordinates, approximation algorithms, orthogonal polygons, computer graphics", who = "Havran Vlastimil: VIS-0055", } @TechReport{Miller:CS9615, author = "Timothy Miller", title = "Hidden-Surfaces: Combining BSP Trees with Graph-Based Algorithms", institution = "Department of Computer Graphics, Brown University", number = "CS-96-15", month = apr, year = 1996, documentURL = "http://www.cs.brown.edu/publications/techreports/reports/CS-96-15.html", who = "Havran Vlastimil: VIS-0054", } @inproceedings{chrysanthou:1996:five, author = "Yiorgos Chrysanthou", title = "A Fast and Accurate Shadow Algorithm for Dynamic Scenes", booktitle = "A symposium of the Framework for Immersive Virtual Environments Working Group", year = "1996", month = oct, pages = "??--??", address = "Geneva, Switzerland", who = "Havran Vlastimil: VIS-0053", } @inproceedings{sadagic:1996:five, author = "Amela Sadagic", title = "Fast Approximate Quantitative Visibility for Complex Scenes", booktitle = "A symposium of the Framework for Immersive Virtual Environments Working Group", year = "1996", month = oct, pages = "??--??", address = "Geneva, Switzerland", who = "Havran Vlastimil: VIS-0052", } @inproceedings{chrysanthou:cgi:98, author = "Chrysanthou, Y. and Cohen-Or, D. and Lischinski, D.", title = "Fast Approximate Quantitative Visibility for Complex Scenes", booktitle = "Proceedings of Computer Graphics International '98 (CGI'98)", year = "1998", month = jun, pages = "23--31", address = "Hannover, Germany", publisher = "IEEE, NY", who = "Havran Vlastimil: VIS-0051", } @inproceedings{barelber:cgi:98, author = "Bar-Lev, A. and Elber, G.", title = "Visibility as an Intrinsic Property of Geometric Models", booktitle = "Proceedings of Computer Graphics International '98 (CGI'98)", year = "1998", month = jun, pages = "198--206", address = "Hannover, Germany", publisher = "IEEE, NY", who = "Havran Vlastimil: VIS-0050", } @inproceedings{hinkenjann:cgi:98, author = "Hinkenjann, A. and Muller, H.", title = "Determining Visibility between Extended Objects", booktitle = "Proceedings of Computer Graphics International '98 (CGI'98)", year = "1998", month = jun, pages = "23--31", address = "Hannover, Germany", publisher = "IEEE, NY", who = "Havran Vlastimil: VIS-0049", } @inproceedings{iones:cgi:98, author = "Iones, A. and Zhukov, S. and Krupkin, A.", title = "On Optimality of OBBs for Visibility Tests for Frustrum Culling, Ray Shooting and Collision Detection", booktitle = "Proceedings of Computer Graphics International '98 (CGI'98)", year = "1998", month = jun, pages = "256--263", address = "Hannover, Germany", publisher = "IEEE, NY", who = "Havran Vlastimil: VIS-0048", } @inproceedings{bb12590, AUTHOR = "Shimshoni, I. and Ponce, J.", TITLE = "Finite Resolution Aspect Graphs of Polyhedral Objects", BOOKTITLE = "WQV93", YEAR = "1993", PAGES = "140-150", who = "Havran Vlastimil: VIS-0046", } @inproceedings{devai-star-97, author = "F. D\`{e}vai", title = "On the Computational Requirements of Virtual Reality Systems", booktitle = "State of Art, Eurographics'97", year = 1997, who = "Havran Vlastimil: VIS-0045", } @article{bb12595, AUTHOR = "Eggert, D.W. and Bowyer, K.W. and Dyer, C.R. and Christensen, H.I. and Goldgof, D.B.", TITLE = "The Scale Space Aspect Graph", JOURNAL = "PAMI", VOLUME = "15", YEAR = "1993", NUMBER = "11", MONTH = "November", PAGES = "1114-1130", who = "Havran Vlastimil: VIS-0044", } @inproceedings{r-tsvcp-95, author = "St\'{e}phane Rivi\`{e}re", title = "Topologically Sweeping the Visibility Complex of Polygonal Scenes", booktitle = "Proc. 11th Annu. ACM Sympos. Comput. Geom.", year = 1995, pages = "C36--C37", keywords = "visibility graph optimal algorithm, experimental", cites = "eg-tsa-86, gm-osacv-87, ow-nmcvg-88, pv-savgc-93, pv-vc-93, pv-cvgpt-95, r-ectac-93, ZZZ", update = "98.03 bibrelex, 95.09 mitchell", who = "Havran Vlastimil: VIS-0043", } @inproceedings{r-wvcav-97, author = "St\'ephane Rivi\`ere", title = "Walking in the Visibility Complex with Applications to Visibility Polygons and Dynamic Visibility", booktitle = "Proc. 9th Canad. Conf. Comput. Geom.", year = 1997, pages = "147--152", update = "97.11 jones", who = "Havran Vlastimil: VIS-0042", } @inproceedings{r-dvpsv-97, author = "S. Rivi{\`e}re", title = "Dynamic visibility in polygonal scenes with the visibility complex", booktitle = "Proc. 13th Annu. ACM Sympos. Comput. Geom.", year = 1997, pages = "421--423", who = "Havran Vlastimil: VIS-0041", } @Article{Slater:1992a, author = "M. Slater", title = "A Comparison of Three Shadow Volume Algorithms", journal = "The Visual Computer", volume = "9", number = "1", pages = "25--38", year = "1992", who = "Havran Vlastimil: VIS-0040", } @inproceedings{slater97a, author = "M. Slater and Y. Chrysanthou", title = "View Volume Culling Using a Probabilistic Caching Scheme", booktitle = "ACM Virtual Reality Software and Technology VRST'97", year = 1997, month = sep, address = "Lausanne, Switzerland", pages = "??-??", who = "Havran Vlastimil: VIS-0039", } @TechReport{Coorg96a, author = "Coorg, Satyan and Teller, Seth", title = "A Spatially and Temporally Coherent Object Space Visibility Algorithm", institution = "Department of Computer Graphics, MIT", number = "TM-546", month = feb, year = 1996, documentURL = "http://graphics.lcs.mit.edu/~satyan/pubs/mit-lcs-tm-546.ps.Z", who = "Havran Vlastimil: VIS-0038", } @inproceedings{blais98a, author = "M. Blais and P. Poulin", title = "Sampling Visibility in Three-Space", booktitle = "Proc. of the 1998 Western Computer Graphics Symposium", year = 1998, month = apr, pages = "45--52", who = "Havran Vlastimil: VIS-0037", } @Article{Sudarsky:1996:OVA, author = "Oded Sudarsky and Craig Gotsman", title = "Output-Sensitive Visibility Algorithms for Dynamic Scenes with Applications to Virtual Reality", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "15", number = "3", pages = "C249--C258", month = sep, year = "1996", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Tue Mar 17 15:44:38 MST 1998", acknowledgement = ack-nhfb, affiliation = "Technion - Israel Inst of Technology", affiliationaddress = "Haifa, Isr", affiliationaddress = "Isr", classification = "722.4; 723.1; 723.2; 723.5; 741.2; 921.4; C6120 (File organisation); C6130B (Graphics techniques); C6150N (Distributed systems software)", conference = "Proceedings of the 1996 17th Annual Conference and Exhibition of the European Association for Computer Graphics, EUROGRAPHICS'96", conflocation = "Poitiers, France; 26-30 Aug. 1996", conftitle = "European Association for Computer Graphics 17th Annual Conference and Exhibition. EUROGRAPHICS '96", corpsource = "Dept. of Comput. Sci., Israel Inst. of Technol., Haifa, Israel", journalabr = "Comput Graphics Forum", keywords = "Algorithms; Client server design; Computational geometry; Computer graphics; Computer simulation; Data structures; Distributed computer systems; Distributed multi user virtual environment; Dynamic scenes; Output sensitive visibility algorithm; Temporal bounding volumes; Virtual reality; Visibility", keywords = "Algorithms; auxiliary data structure; Client server design; client-server systems; communications; Computational geometry; Computer graphics; Computer simulation; current position; Data structures; Distributed computer systems; Distributed multi user virtual environment; distributed virtual; dynamic object; dynamic objects; dynamic scenes; Dynamic scenes; environments; hidden feature removal; model; multiple; Output sensitive visibility algorithm; output-sensitive visibility algorithms; overhead; runtime; scene; spatial data; structures; temporal bounding volumes; Temporal bounding volumes; temporal bounding volumes; updated spatial data structure; virtual reality; Virtual reality; Visibility; visibility; visible graphic primitives", meetingaddress = "Poitiers, Fr", meetingdate = "Aug 26--30 1996", meetingdate2 = "08/26--30/96", sponsor = "CNRS; ERCIM; BARCO; EDF; SUN; et al", sponsororg = "CNRS; BARCO; Electr. France; et al", treatment = "T Theoretical or Mathematical", who = "Havran Vlastimil: VIS-0036", } @inproceedings{hmclhz-aocus-97, author = "T. Hudson and D. Manocha and J. Cohen and M. Lin and K. Hoff and H. Zhang", title = "Accelerated Occlusion Culling Using Shadow Frustra", booktitle = "Proc. 13th Annu. ACM Sympos. Comput. Geom.", year = 1997, pages = "1--10", update = "97.07 efrat", who = "Havran Vlastimil: VIS-0035", } @InProceedings{Durand:1996:VCN, author = "Fr{\'{e}}do Durand and George Drettakis and Claude Puech", title = "The {3D} Visibility Complex: {A} New Approach to the Problems of Accurate Visibility", booktitle = "Proceedings of Eurographics Rendering Workshop '96", year = "1996", publisher = "Springer", month = jun, pages = "245--256", keywords = "visibility, visibility complex, spatial coherence, discontinuity meshing, form factor", annote = "Visibility computations are central in any computer graphics application. The most common way to reduce this expense is the use of approximate approaches using spatial subdivision. More recently analytic approaches efficently encoding visibility have appeared for 2D (the visibility complex) and for certain limited cases in 3D (aspect graph, discontinuity meshes). In this paper we propose a new way of describing and studying the visibility of 3D space by a dual space of the 3D lines, such that all the visibility events are described. A new data-structure is defined, called the 3D visibility complex, which encapsulates all visibility events. This structure is global and complete since it encodes all visibility relations in 3D, and is spatially coherent allowing efficient visibility queries such as view extraction, aspect graph, discontinuity mesh, or form factor computation. A construction algorithm and suitable data structures are sketched.", who = "Havran Vlastimil: VIS-0034", } @InProceedings{Teller:1991:VPI, author = "Seth J. Teller and Carlo H. S{\'e}quin", title = "Visibility preprocessing for interactive walkthroughs", pages = "61--69", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '91)", year = "1991", keywords = "architectural simulation, linear programming, superset visibility", who = "Havran Vlastimil: VIS-0033", } @InProceedings{EVL-1997-163, author = "Hansong Zhang and Dinesh Manocha and Thomas Hudson and Kenneth E. {Hoff III}", title = "Visibility Culling Using Hierarchical Occlusion Maps", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '97)", pages = "77--88", year = "1997", keywords = "visibility culling, interactive display, image pyramid, occlusion culling, hierarchical data structures", language = "en", abstract = "We present hierarchical occlusion maps (HOM) for visibility culling on complex models with high depth complexity. The culling algorithm uses an object space bounding volume hierarchy and a hierarchy of image space occlusion maps. Occlusion maps represent the aggregate of projections of the occluders onto the image plane. For each frame, the algorithm selects a small set of objects from the model as occluders and renders them to form an initial occlusion map, from which a hierarchy of occlusion maps is built. The occlusion maps are used to cull away a portion of the model not visible from the current viewpoint. The algorithm is applicable to all models and makes no assumptions about the size, shape, or type of occluders. It supports approximate culling in which small holes in or among occluders can be ignored. The algorithm has been implemented on current graphics systems and has been applied to large models composed of hundreds of thousands of polygons. In practice, it achieves significant speedup in interactive walkthroughs of models with high depth complexity.", evlib-url = "http://visinfo.zib.de:80/Dienst/UI/2.0/Describe/evl.computergraphics%2FEVL-1997-163", evlib-revision = "1st", who = "Havran Vlastimil: VIS-0032", } @InProceedings{Kumar:1996:HVC, author = "Subodh Kumar and Dinesh Manocha", title = "Hierarcical Visibility Culling for Spline Models", booktitle = "Graphics Interface '96", editor = "Wayne A. Davis and Richard Bartels", year = "1996", organization = "Canadian Information Processing Society", publisher = "Canadian Human-Computer Communications Society", month = may, pages = "142--150", note = "ISBN 0-9695338-5-3", keywords = "NURBS rendering, visibility, backpatch, CAGD, ONE-tree", annote = "We present hierarchical algorithms for visibilit culling of spline models. This includes back-patch culling, a generalization of back-face culling for polygons to splines. These algorithms are extended to trimmed surfaces as well. We propose different spatial approximations for enclosing the normals of spline surface and compare them for efficiency and effectiveness on different graphics systems. We extend the culling algorithms using hierarchical techniques to collection of surface patches and combine them with view-frustum culling to formulate a ONE (Object-Normal Exclusion)-tree for a given model. The algorithm traverses the ONE-tree at run time and culls away portions of the model not visible from the current viewpoint. These algorithms have been implemented and applied to a number of large models. In practice, we are able to speed-up the overall spline rendering algorithms by about 20 - 30% based on back-patch culling only and by more than 50% using ONE-trees.", who = "Havran Vlastimil: VIS-0031", } @InProceedings{SOJKA:1995:FMG, author = "Eduard SOJKA", title = "Fields, Maps and Graphs of Properties of a Scene", booktitle = "Compugraphics '95", pages = "234--245", year = "1995", month = dec, editor = "Harold P. Santo", note = "ISBN 972-8342-00-4", who = "Havran Vlastimil: VIS-0030", } @InProceedings{Sojka:1994:GPV, author = "Eduard Sojka", title = "Graf potencialu viditelnosti", booktitle = "Winter School of Computer Graphics 1994", year = "1994", month = jan, note = "held at University of West Bohemia, Plzen, Czech Republic, 19-20 January 1994", keywords = "graf potencialu viditelnosti, graf aspektu, viditelnost.", pages = "168--173", annote = "Clanek podava novy pohled na teorii potencialu viditelnosti. Tento pohled predpoklada, ze na mnozine obrazu dane sceny lze zavest relaci ekvivalence. Tato relace pak indukuje rozklad mnoziny obrazu, ktera je nekonecna, na konecny pocet trid. Take prostor obklopujici scenu je dekomponovan na tridy. Ze vsech bodu jedne tridy vnima pozorovatel ekvivalentni obrazy. Graf potencialu viditelnosti zachycuje informaci o techto tridach a vztazich mezi nimi. Predkladana teorie umoznuje zasadit publikovane pristupy do jednotneho ramce. Pouziti teorie je ilustrovano na nekolika prikladech. Graf potencialu viditelnosti muze byt puzit jako alternativni nebo doplnkovy model sceny a muze byt uzitecny pri reseni ruznych problemu jako je napriklad problem viditelnosti, problem navigace ve scene a problem rozpoznani trojrozmernych objektu.", who = "Havran Vlastimil: VIS-0029", } @InProceedings{Sojka:1995:AGT, author = "E. Sojka", title = "Aspect Graphs of Three Dimensional Scenes", booktitle = "Winter School of Computer Graphics 1995", year = "1995", month = feb, pages = "289--299", note = "held at University of West Bohemia, Plzen, Czech Republic, 14-18 February 1995", who = "Havran Vlastimil: VIS-0028", } @Article{Mulmuley:1989:EAH, author = "Ketan Mulmuley", editor = "Jeffrey Lane", title = "An Efficient Algorithm for Hidden Surface Removal", journal = "Computer Graphics", volume = "23", number = "3", pages = "379--388", month = jul, year = "1989", bibsource = "Graphics/imager/imager.89.bib", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", who = "Havran Vlastimil: VIS-0027", } @InProceedings{Sillion:1995:FBC, author = "Fran\c{c}ois Sillion and George Drettakis", title = "Feature-based Control of Visibility Error: {A} Multi-Resolution Clustering Algorithm for Global Illumination", pages = "145--152", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '95)", year = "1995", publisher = "ACM SIGGRAPH/Addison Wesley", month = aug, who = "Havran Vlastimil: VIS-0026", } @InProceedings{Drettakis:1997:IUG, author = "George Drettakis and Fran{\c{c}}ois Sillion", title = "Interactive Update of Global Illumination Using {A} Line-Space Hierarchy", booktitle = "SIGGRAPH 97 Conference Proceedings", editor = "Turner Whitted", series = "Annual Conference Series", year = "1997", organization = "ACM SIGGRAPH", publisher = "Addison Wesley", month = aug, pages = "57--64", note = "ISBN 0-89791-896-7", keywords = "global illumination, dynamic environments, hierarchical radiosity, form-factors, interactivity, frame rate control", annote = "Interactively manipulating the geometry of complex, globally illuminated scenes has to date proven an elusive goal. Previous attempts have failed to provide interactive updates of global illumination and have not been able to offer well-adapted algorithms controlling the frame rate. The need for such interactive updates of global illumination is becoming increasingly important as the field of application of radiosity algorithms widens. To address this need, we present a novel algorithm which provides interactive update rates of global illumination for complex scenes with moving objects. In the context of clustering for hierarchical radiosity, we introduce the idea of an implicit line-space hierarchy. This hierarchy is realized by augmenting the links between hierarchical elements (clusters or surfaces) with shafts, representing the set of lines passing through the two linked elements. We show how line-space traversal allows rapid identification of modified links, and simultaneous cleanup of subdivision no longer required after a geometry move. The traversal of line-space also limits the amount of work required to update and solve the new hierarchical system after a move, by identifying the modified paths in the scene hierarchy. The implementation of our new algorithm allows interactive updates of illumination after object motion for scenes containing several thousand polygons, including global illumination effects. Finally, the line-space hierarchy traversal provides a natural control mechanism allowing the regulation of the tradeoff between image quality and frame rate.", who = "Havran Vlastimil: VIS-0025", } @TechReport{deBerg96traverse, author = "Mark de Berg and Marc van Kreveld and Rene van Oostrum and Mark Overmars", title = "Simple traversal of a subdivision without extra storage", institution = "CS Dept, Utrecht U.", year = "1996", note = "UU-CS-1996-17 URL: http:/www.cs.ruu.nl/docs/research/publication/TechList2.", keywords = "contour map, computational geometry, interval tree, cartography", annote = "traversing a planar subdivision without mark bits", who = "Havran Vlastimil: VIS-0024", } @InProceedings{chrysanthou92a, author = "Y. Chrysanthou and M. Slater", title = "Computing dynamic changes to BSP trees", pages = "321--332", booktitle = "Computer Graphics Forum (EUROGRAPHICS '92 Proceedings)", volume = "11", number = "3", year = "1992", month = sep, editor = "A. Kilgour and L. Kjelldahl", conference = "held in Cambridge, UK; 7-11 September 1992", keywords = "binary space partition trees, svbsp, shadows", who = "Havran Vlastimil: VIS-0023", } @InProceedings{navazo87a, author = "Isabel Navazo and Josep Fontdecaba and Pere Brunet", title = "Extended octtrees, between {CSG} trees and boundary representations", pages = "239--247", booktitle = "Eurographics '87", year = "1987", month = aug, editor = "G. Marechal", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Amsterdam, The Netherlands; 24 -- 28 August 1987", keywords = "octree", who = "Havran Vlastimil: VIS-0022", } @InProceedings{Torres:1990:OBS, author = "Enric Torres", title = "Optimization of the Binary Space Partition Algorithm ({BSP}) for the Visualization of Dynamic Scenes", pages = "507--518", booktitle = "Eurographics '90", year = "1990", month = sep, editor = "C. E. Vandoni and D. A. Duce", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Montreux, Switzerland; 3 -- 7 September 1990", keywords = "", annote = "", who = "Havran Vlastimil: VIS-0021", } @InProceedings{Chin:1989:NRT, author = "Norman Chin and Steven Feiner", title = "Near Real-Time Shadow Generation Using {BSP} Trees", pages = "99--106", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '89)", year = "1989", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "shadows, shadow volumes, BSP, binary space partitioning", annote = "", who = "Havran Vlastimil: VIS-0020", } @Article{Morer:1995:OPL, author = "P. Morer and A. M. Garcia-Alonso and J. Flaquer", title = "Optimization of a Priority List Algorithm for {3-D} Rendering of Buildings", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "14", number = "4", pages = "217--227", month = oct, year = "1995", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Fri Sep 13 06:22:32 MDT 1996", acknowledgement = ack-nhfb, classification = "C7440 (Civil and mechanical engineering computing); C6130B (Graphics techniques); C1180 (Optimisation techniques)", keywords = "Priority list algorithm; 3D rendering; 3-D rendering; Buildings; Architectural scenes; Parallel surfaces; Instantiation; Visualization algorithms; Hidden surface removal problem; Implementation policies; Binary space partition algorithm; Memory space; Optimization TECHNIQUES", pubcountry = "UK", thesaurus = "Architectural CAD; Data visualisation; Engineering graphics; Hidden feature removal; Optimisation; Rendering [computer graphics]", who = "Havran Vlastimil: VIS-0019", } @Article{Gordon:1991:FDB, author = "Dan Gordon and Shuhong Chen", title = "Front-to-back display of {BSP} trees", journal = "IEEE Computer Graphics and Applications", volume = "11", number = "5", pages = "79--85", month = sep, year = "1991", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "Texas A\&M Univ, USA", annote = "For each scanline, keeps a list of unlit segments. By displaying front-to-back instead of the traditional back-to-front, save on the unnecessary display/shading of hidden polygons. The savings are negligible for small polygons but increase with the size of the polygons. Using hardware polygon rendering (instead of the scanline algorithm) would not make this technique as interesting.", classification = "723; 921", journalabr = "IEEE Comput Graphics Appl", keywords = "Back-to-Front Display; Binary Space Partitioning Trees; bsp, dynamic screen data structure; Computer Graphics; Data Structures; Front-to-Back Display; Image Processing; Interpolation Shading", who = "Havran Vlastimil: VIS-0018", } @InProceedings{Chen:1996:FPA, author = "{Han-Ming} Chen and {Wen-Teng} Wang", title = "The Feudal Priority Algorithm on Hidden-Surface Removal", editor = "Holly Rushmeier", series = "Annual Conference Series", pages = "55--64", booktitle = "SIGGRAPH 96 Conference Proceedings", year = "1996", organization = "ACM SIGGRAPH", publisher = "Addison Wesley", month = aug, note = "held in New Orleans, Louisiana, 04-09 August 1996", annote = "Development of a real-time shaded rendering approach for a frequently changing viewpoint or view vector is very important in the simulation of 3-D objects in Computer-Aided Design. A new approach is proposed in this paper to meet this demand in a very efficient manner. A pre-processing phase, in which a feudal priority tree is established for all polygons of an object, and a post-processing phase, in which a rendering priority list is searched for from the feudal priority tree for a new viewpoint or view vector, are included in our approach. The most time-consuming work is finished in the pre-processing phase which only has to be executed once for an object, and the relatively simple task is left to the post-processing phase, which is repeated when the viewpoint or view vector is changed. For the pre-processing phase, a static version and a dynamic version are proposed in this paper. The one-way priority relations of all polygons are computed in the former part of the dynamic pre-processing in a more efficient way than that in the static pre-processing, but the latter part of the dynamic pre-processing is still based on the static pre-processing. A new concept of ``absolute priority'' is introduced to systematically reduce the polygons in which a separating plane is to be searched for so the probability of finding the separating plane is much increased. This is the basis to implement another important concept of ``separating before splitting'' by which the polygon splittings are much reduced. Hence the efficiency in the pre-processing and the post-processing phases is highly increased.", who = "Havran Vlastimil: VIS-0017", } @Article{Loscos:1997:IHS, author = "Celine Loscos and George Drettakis", title = "Interactive High-Quality Soft Shadows in Scenes with Moving Objects", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "16", number = "3", pages = "C219--C230", month = sep # " 4--8", year = "1997", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Tue Mar 17 15:44:38 MST 1998", acknowledgement = ack-nhfb, affiliation = "INRIA", affiliationaddress = "Grenoble, Fr", classification = "723.2; 723.5; 741.2", journalabr = "Comput Graphics Forum", keywords = "Algorithms; Backprojection structures; Computational geometry; Discontinuity mesh; Dynamic scenes; Image quality; Interactive computer graphics; Lighting; Soft shadows; Three dimensional computer graphics; Visibility", who = "Havran Vlastimil: VIS-0016", } @InProceedings{Teller:1992:CAA, author = "Seth J. Teller", title = "Computing the antipenumbra of an area light source", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '92)", pages = "139--148", month = jul, year = "1992", conference = "held in Chicago, Illinois; 26--31 July 1992", keywords = "radiosity, aspect graph, discontinuity meshing, stabbing lines, plucker coordinates", who = "Havran Vlastimil: VIS-0015", } @Article{Naylor:1990:MBT, author = "Bruce Naylor and John Amanatides and William Thibault", editor = "Forest Baskett", title = "Merging {BSP} Trees Yields Polyhedral Set Operations", journal = "Computer Graphics", volume = "24", number = "4", pages = "115--124", month = aug, year = "1990", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", conference = "held in Dallas, Texas; 6--10 August 1990", who = "Havran Vlastimil: VIS-0014", } @InProceedings{Chrysanthou:1997:IUS, author = "Yiorgos Chrysanthou and Mel Slater", title = "Incremental Updates to Scenes Illuminated by Area Light Sources", booktitle = "Proceedings of Eurographics Workshop on Rendering", year = "1997", publisher = "Springer Verlag", month = jun, pages = "103--114", annote = "An object space algorithm for computing shadows in dynamic scenes illuminated by area light sources is presented. A mesh with the shadow boundaries as well as other discontinuities in the illumination function, is built in a pre-processing stage and updated on-line after any interaction resulting in a change in the scene geometry. The mesh on each polygon is a 2D BSP tree stored in a winged edge data structure. To accelerate the mesh construction a number of new ideas are employed: sorting of the polygons in respect to the area source, the shadow overlap cube, BSP tree merging of the shadows. In addition a method for dynamically changing the BSP representation of the mesh and quickly identifying the vertices requiring intensity computations was developed. Preliminary experimental results indicate the strength and the potential of this method.", who = "Havran Vlastimil: VIS-0013", } @InProceedings{Daubert:1997:HLS, author = "Katja Daubert and Hartmut Schirmacher and Fran{\c{c}}ois X. Sillion and George Drettakis", title = "Hierarchical Lighting Simulation for Outdoor Scenes", booktitle = "Eurographics Rendering Workshop 1997", editor = "Julie Dorsey and Philipp Slusallek", year = "1997", organization = "Eurographics", publisher = "Springer Wein", address = "New York City, NY", month = jun, pages = "229--238", note = "ISBN 3-211-83001-4", annote = "Lighting algorithms for outdoor scenes suffer from the sheer geometric and lighting complexity of such environments. In this paper we introduce an efficient, hierarchical solution to the problem of outdoor illumination. Data structures and sampling algorithms are presented, permitting the integration of complex and natural objects in a hierarchical radiosity simulation system. This new approach allows the hierarchical simulation of radiant energy exchanges in outdoor scenes for the first time, including terrain and botanical models as well as sunlight and skylight. This is accomplished by providing the necessary tools to treat terrain meshes as a hierarchy of light-exchanging objects, as well as an efficient hierarchical representation for the sky dome. In addition, refinement criteria are adapted to the particular characteristics of natural lighting. Results of our implementation are presented including naturally-lit images of terrain-maps, trees and buildings.", who = "Havran Vlastimil: VIS-0012", } @InProceedings{Drettakis:1996:AVM, author = "George Drettakis and Fran{\c{c}}ois Sillion", title = "Accurate Visibility and Meshing Calculations for Hierarchical Radiosity", booktitle = "Eurographics Rendering Workshop 1996", editor = "Xavier Pueyo and Peter Schr{\"{o}}der", year = "1996", organization = "Eurographics", publisher = "Springer Wein", address = "New York City, NY", month = jun, pages = "269--278", note = "ISBN 3-211-82883-4", annote = "Precise quality control for hierarchical lighting simulations is still a hard problem, due in part to the difficulty of analysing the source of error and to the close interactions between different components of the algorithm. In this paper we attempt to address this issue by examining two of the most central components of these algorithms: visibility computation and the mesh. We first present an investigation tool in the form of a new hierarchical algorithm: this algorithmic extension encapsulates exact visibility information with respect to the light source in the form of the backprojection data structure, and allows the use of discontinuity meshes in the solution hierarchy. This tool permits us to study separately the effects of visibility and meshing error on image quality, computational expense as well as solution convergence. Initial experimental results are presented by comparing standard quadtree-based hierarchical radiosity with point-sampling visibility to the approaches incorporating backprojections, discontinuity meshes or both.", who = "Havran Vlastimil: VIS-0011", } @Article{bib:naylor90, author = "B. Naylor", title = "Binary Space Partitioning Trees as an Alternative Representation of Polytopes", journal = "Computer--Aided Design", year = "1990", pages = "250--252", who = "Havran Vlastimil: VIS-0010", } @InProceedings{Naylor:1992:PTI, author = "Bruce F. Naylor", title = "Partitioning tree image representation and generation from 3{D} geometric models", pages = "201--212", booktitle = "Proceedings of Graphics Interface '92", year = "1992", month = may, conference = "held in Vancouver, B.C.; 11-15 May 1992", keywords = "bsp trees", who = "Havran Vlastimil: VIS-0009", } @InProceedings{Naylor:1993:CGP, author = "Bruce Naylor", title = "Constructing good partition trees", booktitle = "Proceedings of Graphics Interface '93", year = "1993", pages = "181--191", organization = "Canadian Information Processing Society", address = "Toronto, Ontario, Canada", month = may, who = "Havran Vlastimil: VIS-0008", } @InProceedings{Naylor:1992:ISG, author = "Bruce F. Naylor", title = "Interactive solid geometry via partitioning trees", pages = "11--18", booktitle = "Proceedings of Graphics Interface '92", year = "1992", month = may, conference = "held in Vancouver, B.C.; 11-15 May 1992", keywords = "bsp trees", who = "Havran Vlastimil: VIS-0007", } @InProceedings{Durand:1997:VSP, author = "Fr{\'{e}}do Durand and George Drettakis and Claude Puech", title = "The Visibility Skeleton: {A} Powerful and Efficient Multi-Purpose Global Visibility Tool", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '97)", year = "1997", pages = "89--100", keywords = "Visibility, Global Visibility, Extremal Stabbing Lines, Aspect Graph, Global Illumination, Form Factor Calculation, Discontinuity Meshing, View Calculation", annote = "Many problems in computer graphics and computer vision require accurate global visibility information. Previous approaches have typically been complicated to implement and numerically unstable, and often too expensive in storage or computation. The Visibility Skeleton is a new powerful utility which can efficiently and accurately answer visibility queries for the entire scene. The Visibility Skeleton is a multi-purpose tool, which can solve numerous different problems. A simple construction algorithm is presented which only requires the use of well known computer graphics algorithmic components such as ray-casting and line/plane intersections. We provide an exhaustive catalogue of visual events which completely encode all possible visibility changes of a polygonal scene into a graph structure. The nodes of the graph are extremal stabbing lines, and the arcs are critical line swaths. Our implementation demonstrates the construction of the Visibility Skeleton for scenes of over a thousand polygons. We also show its use to compute exact visible boundaries of a vertex with respect to any polygon in the scene, the computation of global or on-the-fly discontinuity meshes by considering any scene polygon as a source, as well as the extraction of the exact blocker list between any polygon pair. The algorithm is shown to be manageable for the scenes tested, both in storage and in computation time. To address the potential complexity problems for large scenes, on-demand or lazy contruction is presented, its implementation showing encouraging first results.", who = "Havran Vlastimil: VIS-0006", } @InProceedings{Drettakis94-FSAAL, author = "George Drettakis and Eugene Fiume", year = "1994", title = "A {Fast} {Shadow} {Algorithm} for {Area} {Light} {Sources} {Using} {Backprojection}", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '94)", pages = "223--230", keywords = "shadows, umbra, penumbra, discontinuity meshing, global illumination, backprojection", comments = "available via the World Wide Web at: http://safran.imag.fr/Membres/George.Drettakis/pub.html", who = "Havran Vlastimil: VIS-0005", } @InProceedings{Plantinga:1993:CVP, author = "Harry Plantinga", title = "Conservative visibility preprocessing for efficient walkthroughs of 3{D} scenes", booktitle = "Proceedings of Graphics Interface '93", year = "1993", pages = "166--173", organization = "Canadian Information Processing Society", address = "Toronto, Ontario, Canada", month = may, who = "Havran Vlastimil: VIS-0003", } @InProceedings{Teller:1993:GVA, author = "Seth Teller and Pat Hanrahan", booktitle = "Computer Graphics Proceedings, Annual Conference Series, 1993", title = "Global Visibility Algorithms for Illumination Computations", pages = "239--246", year = "1993", keywords = "hidden surface removal, visibility space, radiosity, global illumination, algorithmic triage", annote = "The most expensive geometric operation in image synthesis is visibility determination. Classically this is solved with hidden surface removal algorithms that render only the parts of the scene visible from a point. Global illumination calculations, however, may require information between any two points in the scene. This paper describes global visibility algorithms that preprocess polygon databases in order to accelerate visibility determination during illumination calculations. These algorithms are sensitive to the output complexity in visibility space; that is, how many pairs of objects are mutually visible. Furthermore, the algorithms are incremental so that they work well with progressive refinement and hierarchical methods of image synthesis. The algorithms are conservative, but exact; that is, when they return visibility predicates they can be proved true. However sometimes they do not return either totally visible or totally invisible, but partially visible, even though in the same situation a better algorithm might return the exact answer. In this paper we describe the algorithms and their implementation, and show that, in a scene with low average visual complexity, they can dramatically accelerate conventional radiosity programs.", who = "Havran Vlastimil: VIS-0002", } @InProceedings{Stewart:1994:FCSb, author = "A. James Stewart and Sherif Ghali", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '94)", title = "Fast Computation of Shadow Boundaries Using Spatial Coherence and Backprojections", pages = "231--238", year = "1994", who = "Havran Vlastimil: VIS-0001", } @Article{Cohen-Or:1995:VDZ, author = "D. Cohen-Or and A. Shaked", title = "Visibility and Dead-Zones in Digital Terrain Maps", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "14", number = "3", pages = "C/171--C/180", month = sep, year = "1995", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Fri Jul 18 14:10:02 1997", acknowledgement = ack-nhfb, classification = "A9110D (Cartography); A9365 (Data and information; acquisition, processing, storage and dissemination in geophysics); C4240C (Computational complexity); C4260 (Computational geometry); C6130B (Graphics techniques); C7340 (Geophysics computing); C7840 (Geography and cartography computing)", conflocation = "Maastricht, Netherlands; 18 Aug.-1 Sept. 1995", conftitle = "EUROGRAPHICS '95", corpsource = "Sch. of Math. Sci., Tel Aviv Univ., Israel", keywords = "cartography; computational; computational complexity; Computational geometry; Dead-zones; dead-zones; detection; digital; Digital elevation map; digital terrain maps; Digital terrain maps; digital terrain maps; Discrete cross-sections; discrete cross-sections; discrete lines of sight; Discrete lines of sight; discrete lines of sight; elevation map; geographic information systems; Geographic information systems; geographic information systems; geometry; hidden area detection; Hidden area detection; hidden area detection; hidden feature; multiplication; Multiplication; multiplication; Polygonal surface representation; polygonal surface representation; removal; Surface perimeter; surface perimeter; terrain modelling; Terrain modelling; terrain modelling; Testing operations; testing operations; topographic surface; Topographic surface; topographic surface; Unit-sized terrain elements; unit-sized terrain elements; viewpoint; Viewpoint; viewpoint; Visibility; visibility; visible area; Visible area detection", thesaurus = "Cartography; Computational complexity; Computational geometry; Geographic information systems; Hidden feature removal; Visibility", treatment = "P Practical", who = "Havran Vlastimil: VIS-0091", }