>>07734 (OP)
Полезные ссылочки петухонерам и просто преемникам Джона Кармака:

https://www.rastergrid.com/blog/2010/10/gpu-based-dynamic-geometry-lod/ -- GPU based dynamic geometry LOD.
https://www.rastergrid.com/blog/2011/01/frei-chen-edge-detector/ -- алгоритм детектора краев.
https://www.rastergrid.com/blog/2010/11/texture-and-buffer-access-performance/ -- советы по производительному доступу к текстурам и буферам.
https://www.rastergrid.com/blog/2010/10/hierarchical-z-map-based-occlusion-culling/ -- Hierarchical-Z map based occlusion culling.

https://stackoverflow.com/questions/4995652/3d-occlusion-culling

https://visualizationlibrary.org/documentation/pag_guide_occlusion_culling.html -- OpenGL-Accelerated Occlusion Culling Tutorial.

https://developer.nvidia.com/gpugems/gpugems/part-v-performance-and-practicalities/chapter-29-efficient-occlusion-culling -- Efficient Occlusion Culling.
https://cpp-rendering.io/indirect-rendering/ -- Indirect Rendering : “A way to a million draw calls”.
https://gamedev.ru/code/articles/Cook-Torrance -- Быстрая реализация модели освещения Кука-Торренса. (Она очень хорошо подходит для создания различных стеклянных и металлических поверхностей).

https://interplayoflight.wordpress.com/2022/01/22/shader-tips-and-tricks/ -- Shader tips and tricks.
https://seblagarde.files.wordpress.com/2015/07/course_notes_moving_frostbite_to_pbr_v32.pdf -- Moving Frostbite to Physically Based Rendering 3.0.
https://interplayoflight.wordpress.com/2020/12/21/to-z-prepass-or-not-to-z-prepass/ -- To z-prepass or not to z-prepass.
https://interplayoflight.wordpress.com/2018/07/08/how-to-start-learn-graphics-programming/ -- How to start learning graphics programming?
https://interplayoflight.wordpress.com/2018/07/17/applying-for-a-graphics-programming-job/ -- Applying for a graphics programming job.
https://interplayoflight.wordpress.com/2020/02/17/ways-to-speedup-pixel-shader-execution/ -- Ways to speedup pixel shader execution.
https://google.github.io/filament/Filament.md.html -- Physically Based Rendering in Filament.
https://www.advances.realtimerendering.com/s2016/Siggraph2016_idTech6.pdf -- мастхэв про idTech 6 от преемника Джона Кармака -- Тьяги Соузы.

Не забудьте про "спасибо", смузихлёбы.

Анонче, это ваши инициалы на пикриле? Был бы я вашей маменькой, то меня переполняло бы от гордости

Published August 22, 1999 by Bretton Wade, posted by Myopic Rhino
Do you see issues with this article? Let us know.
(Editor's Note - this article requires additional formatting work and is incomplete)

BSP Tree Frequently Asked Questions (FAQ)

Questions

CHANGES
ABOUT THIS DOCUMENT
ACKNOWLEDGEMENTS
HOW CAN YOU CONTRIBUTE?
ABOUT THE PSEUDO C++ CODE
WHAT IS A BSP TREE?
HOW DO YOU BUILD A BSP TREE?
HOW DO YOU PARTITION A POLYGON WITH A PLANE?
HOW DO YOU REMOVE HIDDEN SURFACES WITH A BSP TREE?
HOW DO YOU COMPUTE ANALYTIC VISIBILITY WITH A BSP TREE?
HOW DO YOU ACCELERATE RAY TRACING WITH A BSP TREE?
HOW DO YOU PERFORM BOOLEAN OPERATIONS ON POLYTOPES WITH A BSP TREE?
HOW DO YOU PERFORM COLLISION DETECTION WITH A BSP TREE?
HOW DO YOU HANDLE DYNAMIC SCENES WITH A BSP TREE?
HOW DO YOU COMPUTE SHADOWS WITH A BSP TREE?
HOW DO YOU EXTRACT CONNECTIVITY INFORMATION FROM BSP TREES?
HOW ARE BSP TREES USEFUL FOR ROBOT MOTION PLANNING?
HOW ARE BSP TREES USED IN DOOM?
HOW CAN YOU MAKE A BSP TREE MORE ROBUST?
HOW EFFICIENT IS A BSP TREE?
HOW CAN YOU MAKE A BSP TREE MORE EFFICIENT?
HOW CAN YOU AVOID RECURSION?
WHAT IS THE HISTORY OF BSP TREES?
WHERE CAN YOU FIND SAMPLE CODE AND RELATED ONLINE RESOURCES?
REFERENCES

Answers

CHANGES Date Section Change 06/02/98
Online Resources Updated the pointer to A.T. Campbell's home page. 01/22/98
Online Resources Added a pointer to the Id Software source code and utilities (finally). 06/08/97
Building a tree Added definition of an autopartition. Efficiency Completely rewrote this section with a concise explanation of the complexity of HSR with an autopartition. Online Resources Updated link to Paton Lewis's BSP tree page, and added a link to Tom Hammersly's web page which describes his experience at implementing a BSP tree compiler and viewer. 06/01/97
Motion Planning Initial draft. Doom Removed text which is confusing and not quite informative enough. Still looking for a replacement. 04/29/97
Online Resources Updated the link to the Computational Gemoetry Pages. 04/25/97
What is... Corrected an error in the ascii-art version of the tree diagram. Building BSP Trees Corrected an error in the example code. 04/14/97
Boolean Ops Corrected an error: "... polygon EFGH is inserted ... one polygon at a time." was changed to "... is inserted ... one edge at a time." Thanks to Filip J. D. Uhlik for noticing this. 04/08/97
Online Resources Updated pointer to FTP site for the FAQ support files: ftp://ftp.sgi.com/other/bspfaq/. 04/02/97
Entire Document Moved document to reality.sgi.com. Changes were made to reflect the new host, but otherwise only a few minor HTML changes were made. 10/09/96
Acknowledgements Added a Michael Brundage to the acknowledgements. Online Resources Added a reference to GFX, a general graphics programming resource.
Added a reference to John Whitley's BSP tree tutorial page. 10/07/96
Definitions Added new definitions page to clarify some difficult terms. Ray Tracing Added a note about using the parent node of the ray origin as a hint for improving run-time performance. Efficiency Corrected a long standing error in the stated complexity of BSP trees for Hidden Surface Removal. 10/06/96
About Added new sub-sections describing the intended audience for the FAQ, and guidelines for obtaining assistance from the FAQ maintainer. Definition Began to re-word the overview of BSP trees in an attempt to make the definition clearer. 08/21/96
Online Resources Added a reference to Paton Lewis's Java based BSP tree demo applet. 08/07/96
Online Resources Added a reference to the Win95 BSP Tree Demo Application. 07/24/96
Online Resources Added reference to Michael Abrash's ftp site at Id. 07/11/96
Online Resources Added reference to Andrea Marchini and Stefano Tommesani's BSP tree compiler page. 05/01/96
General The FAQ articles may now be annotated using the forum mechanism. 04/28/96
Forum Experimental new discussion area for BSP trees. 04/24/96
General Added "Next" and "Previous" links on each page of the FAQ. 04/17/96
Whole FAQ The web search engines have been pointing a lot of people at the entire listing version of the FAQ, rather than at the indexed version. This has led to significantly increased load on our server, and slow response times. As a result, I have made it possible to view the whole document only by following the link from the index page. 04/12/96
Online Resources Update on A.T. Campbell's resources 04/08/96
Eliminating Recursion Initial Draft with code example 03/25/96
General White pages 03/22/96
Online Resources A.T. Campbell's home page
Update Mel Slater's location 03/21/96
Contribution Corrected e-mail address Online Resources Arcball FTP site
Paper by John Holmes, Jr. 02/19/96
Changes NEW Ray Tracing Draft implementation notes Analytic Visibility Draft contents Boolean Operations Spelling corrections
--
Last Update: 09/06/101 14:50:28

ABOUT THIS DOCUMENT General
The purpose of this document is to provide answers to Frequently Asked Questions about Binary Space Partitioning (BSP) Trees. The intended audience for this document has a working knowledge of computer graphics principles such as viewing transformations, clipping, and polygons. The intended audience also has knowledge of binary searching and sorting trees as covered in most computer algorithms textbooks.

A pointer to this document will be posted monthly to comp.graphics.algorithms and rec.games.programmer. It is available via WWW at the URL:

ftp://ftp.sgi.com/ot...faq/bspfaq.html The most recent newsgroup posting of this document is available via ftp at the following URL:

ftp://rtfm.mit.edu/p...ics/bsptree-faq Requesting the FAQ by mail
You can't. Sorry.

About the maintainer
This document was maintained by Bretton Wade, software engineer at Silicon Graphics, Incorporated, and graduate of the Cornell University Program of Computer Graphics. This resource is provided as a service to the computing community in the interest of disseminating useful information. Mr. Wade considers any personal exchange regarding BSP tree related technology to be confidential and not part of the business of Silicon Graphics, Incorporated. As of 2001-09-20, this FAQ does not appear to be maintained and the copy on ftp.sgi.com is the latest known copy.

Requesting assistance
The BSP tree FAQ maintainer receives a large number of requests for assistance. The maintainer makes every effort to respond to individual requests, but this is not always possible. There are several steps that you can take to insure a timely reply. First, be sure that any request for assistance is accompanied by a valid reply address. Second, try to limit your question to the topic of BSP trees. Third, if you are including source code, send only the portions necessary to illustrate your difficulty.

If you do not receive a reply within a reasonable amount of time, it most likely that your reply e-mail address is invalid. If you did not get an acknowledgement from the auto-responder, then you can be sure this is the case. Check your return address and try again.

Copyrights and distribution
This document, and all its associated parts, are Copyright (C) 1995-97, Bretton Wade. All rights reserved. Permisson to distribute this collection, in part or full, via electronic means (emailed, posted or archived) or printed copy are granted providing that no charges are involved, reasonable attempt is made to use the most current version, and all credits and copyright notices are retained. If you make a link to the WWW page, please inform the maintainer so he can construct reciprocal links.

Warranty and disclaimer
This article is provided as is without any express or implied warranties. While every effort has been taken to ensure the accuracy of the information contained in this article, the author/maintainer/contributors assume(s) no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein.

The contents of this article do not necessarily represent the opinions of Silicon Graphics, Incorporated.
--
Last Update: 09/20/101 11:02:10

ACKNOWLEDGEMENTS Web Space
Thank you to Silicon Graphics, Incorporated for kindly providing the web space for this document free of charge.

About the contributors
This document would not have been possible without the selfless contributions and efforts of many individuals. I would like to take the opportunity to thank each one of them. Please be aware that these people may not be amenable to recieving e-mail on a random basis.

Contributors
Bruce Naylor ([email="naylor%20@%20research.att.com"]mailto:naylor%20@%20research.att.com[/email])
Richard Lobb ([email="richard%20@%20cs.auckland.ac.nz"]mailto:richard%20@%20cs.auckland.ac.nz[/email])
Dani Lischinski ([email="danix%20@%20cs.washington.edu"]mailto:danix%20@%20cs.washington.edu[/email])
Chris Schoeneman ([email="crs%20@%20engr.sgi.com"]mailto:crs%20@%20engr.sgi.com[/email])
Philip Hubbard ([email="pmh%20@%20graphics.cornell.edu"]mailto:pmh%20@%20graphics.cornell.edu[/email])
Jim Arvo ([email="arvo%20@%20cs.caltech.edu"]mailto:arvo%20@%20cs.caltech.edu[/email])
Kevin Ryan ([email="kryan%20@%20access.digex.net"]mailto:kryan%20@%20access.digex.net[/email])
Joseph Fiore ([email="fiore%20@%20cs.buffalo.edu"]mailto:fiore%20@%20cs.buffalo.edu[/email])
Lukas Rosenthaler ([email="rosenth%20@%20foto.chemie.unibas.ch"]mailto:rosenth%20@%20foto.chemie.unibas.ch[/email])
Anson Tsao ([email="ansont%20@%20hookup.net"]mailto:ansont%20@%20hookup.net[/email])
Robert Zawarski ([email="zawarski%20@%20chaph.usc.edu"]mailto:zawarski%20@%20chaph.usc.edu[/email])
Ron Capelli ([email="capelli%20@%20vnet.ibm.com"]mailto:capelli%20@%20vnet.ibm.com[/email])
Eric A. Haines ([email="erich%20@%20eye.com"]mailto:erich%20@%20eye.com[/email])
Ian CR Mapleson ([email="mapleson%20@%20cee.hw.ac.uk"]mailto:mapleson%20@%20cee.hw.ac.uk[/email])
Richard Dorman ([email="richard%20@%20cs.wits.ac.za"]mailto:richard%20@%20cs.wits.ac.za[/email])
Steve Larsen ([email="larsen%20@%20sunset.cs.utah.edu"]mailto:larsen%20@%20sunset.cs.utah.edu[/email])
Timothy Miller ([email="tsm%20@%20cs.brown.edu"]mailto:tsm%20@%20cs.brown.edu[/email])
Ben Trumbore ([email="wbt%20@%20graphics.cornell.edu"]mailto:wbt%20@%20graphics.cornell.edu[/email])
Richard Matthias ([email="richardm%20@%20cogs.susx.ac.uk"]mailto:richardm%20@%20cogs.susx.ac.uk[/email])
Ken Shoemake ([email="shoemake%20@%20graphics.cis.upenn.edu"]mailto:shoemake%20@%20graphics.cis.upenn.edu[/email])
Seth Teller ([email="seth%20@%20theory.lcs.mit.edu"]mailto:seth%20@%20theory.lcs.mit.edu[/email])
Peter Shirley ([email="shirley%20@%20cs.utah.edu"]mailto:shirley%20@%20cs.utah.edu[/email])
Michael Abrash ([email="mikeab%20@%20idsoftware.com"]mailto:mikeab%20@%20idsoftware.com[/email])
Robert Schmidt ([email="robert%20@%20idt.unit.no"]mailto:robert%20@%20idt.unit.no[/email])
Samuel P. Uselton ([email="uselton%20@%20nas.nasa.gov"]mailto:uselton%20@%20nas.nasa.gov[/email])
Michael Brundage ([email="brundage%20@%20ipac.caltech.edu"]mailto:brundage%20@%20ipac.caltech.edu[/email])

If I have neglected to mention your name, and you contributed, please let me know immediately!
--
Last Update: 09/20/101 11:03:21

HOW CAN YOU CONTRIBUTE? As of 2001-09-20, this faq does not appear to be maintained.
--
Last Update: 09/20/101 11:03:55

ABOUT THE PSEUDO C++ CODE Overview
The general efficiency of C++ makes it a well suited language for programming computer graphics. Furthermore, the abstract nature of the language allows it to be used effectively as a psuedo code for demonstrative purposes. I will use C++ notation for all the examples in this document.

In order to provide effective examples, it is necessary to assume that certain classes already exist, and can be used without presenting excessive details of their operation. Basic classes such as lists and arrays fall into this category.

Other classes which will be very useful for examples need to be presented here, but the definitions will be generic to allow for freedom of interpretation. I assume points and vectors to each be an array of 3 real numbers (X, Y, Z).

Planes are represented as an array of 4 real numbers (A, B, C, D). The vector (A, B, C) is the normal vector to the plane. Polygons are structures composited from an array of points, which are the vertices, and a plane.

The overloaded operator for a dot product (inner product, scalar product, etc.) of two vectors is the '|' symbol. This has two advantages, the first of which is that it can't be confused with the scalar multiplication operator. The second is that precedence of C++ operators will usually require that dot product operations be parenthesized, which is consistent with the linear algebra notation for an inner product.

The code for BSP trees presented here is intended to be educational, and may or may not be very efficient. For the sake of clarity, the BSP tree itself will not be defined as a class.
--
Last Update: 09/06/101 14:50:29