Vero - Wikipedia - User contributions [en]

Binary space partitioning

2025-10-10T18:04:09Z

2A00:23C5:FE1C:3701:11C:3C25:E9B9:C886: caps

{{Short description|Method for recursively subdividing a space into two subsets using hyperplanes}}
{{More citations needed
|date=May 2016}}
[[File:Binary space partition.png|thumb|300x300px|The process of making a BSP tree]]
In [[computer science]], '''binary space partitioning''' ('''BSP''') is a method for [[space partitioning]] which [[recursively]] subdivides a [[Euclidean space]] into two [[convex set]]s by using [[hyperplane]]s as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a [[Tree (data structure)|tree data structure]] known as a '''BSP tree'''.

Binary space partitioning was developed in the context of [[3D computer graphics]] in 1969.<ref name="schumacker69">{{Cite report |url=https://books.google.com/books?id=0mtk5MdXJhEC |title=Study for Applying Computer-Generated Images to Visual Simulation |last1=Schumacker |first1=R.A. |last2=Brand |first2=B. |date=1969 |publisher=U.S. Air Force Human Resources Laboratory |id=AFHRL-TR-69-14 |last3=Gilliland |first3=M.G. |last4=Sharp |first4=W.H.}}</ref><ref name="fuchs80" /> The structure of a BSP tree is useful in [[rendering (computer graphics)|rendering]] because it can efficiently give spatial information about the objects in a scene, such as objects being ordered from front-to-back with respect to a viewer at a given location. Other applications of BSP include: performing [[geometrical]] operations with [[shape]]s ([[constructive solid geometry]]) in [[Computer-aided design|CAD]],<ref name="thibault87">
{{cite conference
| last1 = Thibault | first1 = William C.
| last2 = Naylor | first2 = Bruce F.
|title=Set operations on polyhedra using binary space partitioning trees
|book-title=SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques
| year=1987
|pages=153–162
| publisher=ACM
| doi=10.1145/37402.37421}}</ref> [[collision detection]] in [[robotics]] and 3D video games, [[ray tracing (graphics)|ray tracing]], virtual landscape simulation,<ref>{{Cite journal |last1=Etherington |first1=Thomas R. |last2=Morgan |first2=Fraser J. |last3=O’Sullivan |first3=David |date=2022 |title=Binary space partitioning generates hierarchical and rectilinear neutral landscape models suitable for human-dominated landscapes |journal=Landscape Ecology |language=en |volume=37 |issue=7 |pages=1761–1769 |doi=10.1007/s10980-022-01452-6 |doi-access=free|bibcode=2022LaEco..37.1761E }}</ref> and other applications that involve the handling of complex spatial scenes.

=={{Anchor|Timeline}}History==

*1969 Schumacker et al.<ref name="schumacker69" /> published a report that described how carefully positioned planes in a virtual environment could be used to accelerate polygon ordering. The technique made use of depth coherence, which states that a polygon on the far side of the plane cannot, in any way, obstruct a closer polygon. This was used in flight simulators made by GE as well as Evans and Sutherland. However, the creation of the polygonal data organization was performed manually by the scene designer.
*1980 [[Henry Fuchs|Fuchs]] et al.<ref name="fuchs80" /> extended Schumacker's idea to the representation of 3D objects in a virtual environment by using planes that lie coincident with polygons to recursively partition the 3D space. This provided a fully automated and algorithmic generation of a hierarchical polygonal data structure known as a Binary Space Partitioning Tree (BSP Tree). The process took place as an off-line preprocessing step that was performed once per environment/object. At run-time, the view-dependent visibility ordering was generated by traversing the tree.
*1981 Naylor's Ph.D. thesis<ref>{{cite thesis |last=Naylor |first=Bruce |date=May 1981 |title=A Priori Based Techniques for Determining Visibility Priority for 3-D Scenes |url=https://www.proquest.com/openview/94daf3b8677f8ca4567915515efeefac/1?pq-origsite=gscholar&cbl=18750&diss=y |degree=Ph.D. |location=University of Texas at Dallas |access-date=June 5, 2025}}</ref> provided a full development of both BSP trees and a graph-theoretic approach using strongly connected components for pre-computing visibility, as well as the connection between the two methods. BSP trees as a dimension-independent spatial search structure were emphasized, with applications to visible surface determination. The thesis also included the first empirical data demonstrating that the size of the tree and the number of new polygons were reasonable (using a model of the Space Shuttle).
*1983 [[Henry Fuchs|Fuchs]] et al.<ref>{{Cite book |last1=Fuchs |first1=Henry |last2=Abram |first2=Gregory D. |last3=Grant |first3=Eric D. |title=Proceedings of the 10th annual conference on Computer graphics and interactive techniques |chapter=Near real-time shaded display of rigid objects |date=1983 |language=en |publisher=ACM |pages=65–72 |doi=10.1145/800059.801134 |isbn=978-0-89791-109-2}}</ref> described a micro-code implementation of the BSP tree algorithm on an Ikonas frame buffer system. This was the first demonstration of real-time visible surface determination using BSP trees.
*1987 Thibault and Naylor<ref name="thibault87" /> described how arbitrary polyhedra may be represented using a BSP tree as opposed to the traditional b-rep ([[boundary representation]]). This provided a solid representation vs. a surface based-representation. Set operations on polyhedra were described using a tool, enabling [[constructive solid geometry]] (CSG) in real-time. This was the forerunner of BSP level design using "[[brush (video games)|brushes]]", introduced in the Quake editor and picked up in the Unreal Editor.
*1990 Naylor, Amanatides, and Thibault<ref>{{cite journal |last1=Naylor |first1=Bruce |last2=Amanatides |first2=John |last3=Thibault |first3=William |date=August 1990 |title=Merging BSP Trees Yields Polyhedral Set Operations |url=https://dl.acm.org/doi/pdf/10.1145/97880.97892 |doi=10.1145/97880.97892 |citeseerx=10.1.1.69.292|journal=ACM SIGGRAPH Computer Graphics |volume=24 |issue=4 |publisher=Association of Computing Machinery |pages=115–124 |access-date=June 5, 2025}}</ref> provided an algorithm for merging two BSP trees to form a new BSP tree from the two original trees. This provides many benefits including combining moving objects represented by BSP trees with a static environment (also represented by a BSP tree), very efficient CSG operations on polyhedra, exact collisions detection in O(log n * log n), and proper ordering of transparent surfaces contained in two interpenetrating objects (has been used for an x-ray vision effect).
*1991 [[Seth J. Teller|Teller]] and Séquin<ref>{{cite journal |last1=Teller |first1=Seth J. |last2=Séquin |first2=Carlo H. |date=July 1, 1991 |title=Visibility preprocessing for interactive walkthroughs |url=https://dl.acm.org/doi/abs/10.1145/127719.122725 |journal=ACM SIGGRAPH Computer Graphics |volume=25 |issue=4 |publisher=Association of Computing Machinery |pages=61–70 |access-date=June 5, 2025}}</ref> proposed the offline generation of potentially visible sets to accelerate visible surface determination in orthogonal 2D environments.
*1991 Gordon and Chen<ref>{{cite journal |first1=S. |last1=Chen |first2=D. |last2=Gordon |title=Front-to-Back Display of BSP Trees |journal=IEEE Computer Graphics and Applications |volume=11 |issue=5 |pages=79–85 |date=October 1991 |doi=10.1109/38.90569 |s2cid=19056967 |url=https://www.researchgate.net/publication/3208236_Front-to-back_display_of_BSP_trees}}</ref> described an efficient method of performing front-to-back rendering from a BSP tree, rather than the traditional back-to-front approach. They utilized a special data structure to record, efficiently, parts of the screen that have been drawn, and those yet to be rendered. This algorithm, together with the description of BSP trees in the standard computer graphics textbook of the day (''[[Computer Graphics: Principles and Practice]]'') was used by [[John D. Carmack|John Carmack]] in the making of [[Doom (1993 video game)|''Doom'' (video game)]].
*1992 [[Seth J. Teller|Teller]]'s Ph.D. thesis<ref>{{cite thesis |last=Teller |first=Seth |date=1992 |title=Visibility computations in densely occluded polyhedral environments |url=https://www.proquest.com/openview/80322259984cf6c676a345676ab1d74a/1?pq-origsite=gscholar&cbl=18750&diss=y |degree=Ph.D. |location=University of California at Berkeley |access-date=June 5, 2025}}</ref> described the efficient generation of potentially visible sets as a pre-processing step to accelerate real-time visible surface determination in arbitrary 3D polygonal environments. This was used in ''[[Quake (video game)|Quake]]'' and contributed significantly to that game's performance.
*1993 Naylor<ref>{{cite journal |last1=Naylor |first1=Bruce |date=1993 |title=Constructing good partitioning trees |url=https://www.researchgate.net/profile/Bruce-Naylor/publication/2492209_Constructing_Good_Partitioning_Trees/links/55cc86be08aea2d9bdce442d/Constructing-Good-Partitioning-Trees.pdf |journal=Graphics Interface |publisher=Canadian Information Processing Society |pages=181–191 |access-date=June 5, 2025}}</ref> answered the question of what characterizes a good BSP tree. He used expected case models (rather than worst-case analysis) to mathematically measure the expected cost of searching a tree and used this measure to build good BSP trees. Intuitively, the tree represents an object in a multi-resolution fashion (more exactly, as a tree of approximations). Parallels with Huffman codes and probabilistic [[binary search]] trees are drawn.
*1993 Hayder Radha's Ph.D. thesis<ref>{{cite thesis |last=Radha |first=Hayder |date=1993 |title=Efficient image representation using binary space partitioning trees |url=https://www.proquest.com/openview/a80bc19b1374b928afa8844a8ed05ef4/1?pq-origsite=gscholar&cbl=18750&diss=y |degree=Ph.D. |publisher=Columbia University |access-date=June 5, 2025}}</ref> described (natural) image representation methods using BSP trees. This includes the development of an optimal BSP-tree construction framework for any arbitrary input image. This framework is based on a new image transform, known as the Least-Square-Error (LSE) Partitioning Line (LPE) transform. H. Radha's thesis also developed an optimal rate-distortion (RD) [[image compression]] framework and image manipulation approaches using BSP trees.

==Overview==
[[File:2D Binary Index.svg|thumb|An example of a recursive binary space partitioning [[quadtree]] for a 2D index]]

Binary space partitioning is a generic process of [[recursion|recursively]] dividing a scene into two using [[hyperplanes]]<ref>{{cite web |last=Naylor |first=Bruce |date=January 2005 |title=A Tutorial on Binary Space Partitioning Trees |url=https://www.researchgate.net/publication/238348725_A_Tutorial_on_Binary_Space_Partitioning_Trees |website=ResearchGate |access-date=July 1, 2025}}</ref> until the partitioning satisfies one or more requirements. It can be seen as a generalization of other spatial tree structures such as [[K-d tree|''k''-d trees]] and [[quadtree]]s, one where hyperplanes that partition the space may have any orientation, rather than being aligned with the coordinate axes as they are in ''k''-d trees or quadtrees. When used in computer graphics to render scenes composed of planar [[Polygon mesh|polygons]], the partitioning planes are frequently chosen to coincide with the planes defined by polygons in the scene.

The specific choice of partitioning plane and criterion for terminating the partitioning process varies depending on the purpose of the BSP tree. For example, in computer graphics rendering, the scene is divided until each node of the BSP tree contains only polygons that can be rendered in arbitrary order. When [[back-face culling]] is used, each node, therefore, contains a convex set of polygons, whereas when rendering double-sided polygons, each node of the BSP tree contains only polygons in a single plane. In collision detection or ray tracing, a scene may be divided up into [[Geometric primitive|primitives]] on which collision or ray intersection tests are straightforward.

Binary space partitioning arose from computer graphics needing to rapidly draw three-dimensional scenes composed of polygons. A simple way to draw such scenes is the [[painter's algorithm]], which produces polygons in order of distance from the viewer, back to front, painting over the background and previous polygons with each closer object. This approach has two disadvantages: the time required to sort polygons in back-to-front order, and the possibility of errors in overlapping polygons. Fuchs and co-authors<ref name="fuchs80"/> showed that constructing a BSP tree solved both of these problems by providing a rapid method of sorting polygons with respect to a given viewpoint (linear in the number of polygons in the scene) and by subdividing overlapping polygons to avoid errors that can occur with the painter's algorithm. A disadvantage of binary space partitioning is that generating a BSP tree can be time-consuming. Typically, it is therefore performed once on static geometry, as a pre-calculation step, prior to rendering or other real-time operations on a scene. The expense of constructing a BSP tree makes it difficult and inefficient to directly implement moving objects into a tree.

==Generation==
The canonical use of a BSP tree is for rendering polygons (that are double-sided, that is, without [[back-face culling]]) with the painter's algorithm. Each polygon is designated with a front side and a backside which could be chosen arbitrarily and only affects the structure of the tree but not the required result.<ref name="fuchs80" /> Such a tree is constructed from an unsorted list of all the polygons in a scene. The recursive algorithm for construction of a BSP tree from that list of polygons is:<ref name="fuchs80">
{{cite conference
| last1 = Fuchs | first1 = Henry
| last2 = Kedem | first2 = Zvi. M
| last3 = Naylor | first3 = Bruce F.
|title=On Visible Surface Generation by A Priori Tree Structures
|book-title=SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques
| year=1980
|pages=124–133
| publisher=ACM
| doi=10.1145/965105.807481| url=http://www.cs.unc.edu/~fuchs/publications/VisSurfaceGeneration80.pdf}}</ref>
# Choose a polygon ''P'' from the list.
# Make a node ''N'' in the BSP tree, and add ''P'' to the list of polygons at that node.
# For each other polygon in the list:
## If that polygon is wholly in front of the plane containing ''P'', move that polygon to the list of nodes in front of ''P''.
## If that polygon is wholly behind the plane containing ''P'', move that polygon to the list of nodes behind ''P''.
## If that polygon is intersected by the plane containing ''P'', split it into two polygons and move them to the respective lists of polygons behind and in front of ''P''.
## If that polygon lies in the plane containing ''P'', add it to the list of polygons at node ''N''.
# Apply this algorithm to the list of polygons in front of ''P''.
# Apply this algorithm to the list of polygons behind ''P''.

The following diagram illustrates the use of this algorithm in converting a list of lines or polygons into a BSP tree. At each of the eight steps (i.-viii.), the algorithm above is applied to a list of lines, and one new node is added to the tree.

{|
|- valign="top"
|
| Start with a list of lines, (or in 3D, polygons) making up the scene. In the tree diagrams, lists are denoted by rounded rectangles and nodes in the BSP tree by circles. In the spatial diagram of the lines, the direction chosen to be the 'front' of a line is denoted by an arrow.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 1.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''i.'''
|Following the steps of the algorithm above,
# We choose a line, A, from the list and,...
# ...add it to a node.
# We split the remaining lines in the list into those in front of A (i.e. B2, C2, D2), and those behind (B1, C1, D1).
# We first process the lines in front of A (in steps ii–v),...
# ...followed by those behind (in steps vi–vii).
| style="text-align:right;" | [[File:Example of BSP tree construction - step 2.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''ii.''' || We now apply the algorithm to the list of lines in front of A (containing B2, C2, D2). We choose a line, B2, add it to a node and split the rest of the list into those lines that are in front of B2 (D2), and those that are behind it (C2, D3). || style="text-align:right;" | [[File:Example of BSP tree construction - step 3.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''iii.'''
| Choose a line, D2, from the list of lines in front of B2 and A. It is the only line in the list, so after adding it to a node, nothing further needs to be done.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 4.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''iv.'''
| We are done with the lines in front of B2, so consider the lines behind B2 (C2 and D3). Choose one of these (C2), add it to a node, and put the other line in the list (D3) into the list of lines in front of C2.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 5.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''v.'''
| Now look at the list of lines in front of C2. There is only one line (D3), so add this to a node and continue.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 6.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''vi.''' || We have now added all of the lines in front of A to the BSP tree, so we now start on the list of lines behind A. Choosing a line (B1) from this list, we add B1 to a node and split the remainder of the list into lines in front of B1 (i.e. D1), and lines behind B1 (i.e. C1). || [[File:Example of BSP tree construction - step 7.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''vii.''' || Processing first the list of lines in front of B1, D1 is the only line in this list, so add this to a node and continue. || style="text-align:right;" | [[File:Example of BSP tree construction - step 8.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''viii.''' || Looking next at the list of lines behind B1, the only line in this list is C1, so add this to a node, and the BSP tree is complete. || style="text-align:right;" | [[File:Example of BSP tree construction - step 9.svg|class=skin-invert]]
|}

The final number of polygons or lines in a tree is often larger (sometimes much larger<ref name="fuchs80" />) than the original list, since lines or polygons that cross the partitioning plane must be split into two. It is desirable to minimize this increase, but also to maintain reasonable [[Binary tree#Types of binary trees|balance]] in the final tree. The choice of which polygon or line is used as a partitioning plane (in step 1 of the algorithm) is therefore important in creating an efficient BSP tree.

==Traversal==
A BSP tree is [[Tree traversal|traversed]] in a linear time, in an order determined by the particular function of the tree. Again using the example of rendering double-sided polygons using the painter's algorithm, to draw a polygon ''P'' correctly requires that all polygons behind the plane ''P'' lies in must be drawn first, then polygon ''P'', then finally the polygons in front of ''P''. If this drawing order is satisfied for all polygons in a scene, then the entire scene renders in the correct order. This procedure can be implemented by recursively traversing a BSP tree using the following algorithm.<ref name="fuchs80" /> From a given viewing location ''V'', to render a BSP tree,
# If the current node is a leaf node, render the polygons at the current node.
# Otherwise, if the viewing location ''V'' is in front of the current node:
## Render the child BSP tree containing polygons behind the current node
## Render the polygons at the current node
## Render the child BSP tree containing polygons in front of the current node
# Otherwise, if the viewing location ''V'' is behind the current node:
## Render the child BSP tree containing polygons in front of the current node
## Render the polygons at the current node
## Render the child BSP tree containing polygons behind the current node
# Otherwise, the viewing location ''V'' must be exactly on the plane associated with the current node. Then:
## Render the child BSP tree containing polygons in front of the current node
## Render the child BSP tree containing polygons behind the current node

[[File:Example of BSP tree traversal.svg|center]]
Applying this algorithm recursively to the BSP tree generated above results in the following steps:
* The algorithm is first applied to the root node of the tree, node ''A''. ''V'' is in front of node ''A'', so we apply the algorithm first to the child BSP tree containing polygons behind ''A''
** This tree has root node ''B1''. ''V'' is behind ''B1'' so first, we apply the algorithm to the child BSP tree containing polygons in front of ''B1'':
*** This tree is just the leaf node ''D1'', so the polygon ''D1'' is rendered.
** We then render the polygon ''B1''.
** We then apply the algorithm to the child BSP tree containing polygons behind ''B1'':
*** This tree is just the leaf node ''C1'', so the polygon ''C1'' is rendered.
* We then draw the polygons of ''A''
* We then apply the algorithm to the child BSP tree containing polygons in front of ''A''
** This tree has root node ''B2''. ''V'' is behind ''B2'' so first, we apply the algorithm to the child BSP tree containing polygons in front of ''B2'':
*** This tree is just the leaf node ''D2'', so the polygon ''D2'' is rendered.
** We then render the polygon ''B2''.
** We then apply the algorithm to the child BSP tree containing polygons behind ''B2'':
*** This tree has root node ''C2''. ''V'' is in front of ''C2'' so first, we would apply the algorithm to the child BSP tree containing polygons behind ''C2''. There is no such tree, however, so we continue.
*** We render the polygon ''C2''.
*** We apply the algorithm to the child BSP tree containing polygons in front of ''C2''
**** This tree is just the leaf node ''D3'', so the polygon ''D3'' is rendered.

The tree is traversed in linear time and renders the polygons in a far-to-near ordering (''D1'', ''B1'', ''C1'', ''A'', ''D2'', ''B2'', ''C2'', ''D3'') suitable for the painter's algorithm.

== Application ==
BSP trees are often used by 3D [[video game]]s, particularly [[first-person shooter]]s and those with indoor environments. [[Game engine]]s using BSP trees include the [[Doom engine|Doom (id Tech 1)]], [[Quake engine|Quake (id Tech 2 variant)]], [[GoldSrc]] and [[Source (game engine)|Source]] engines. In them, BSP trees containing the static geometry of a scene are often used together with a [[Z-buffer]], to correctly merge movable objects such as doors and characters onto the background scene. While binary space partitioning provides a convenient way to store and retrieve spatial information about polygons in a scene, it does not solve the problem of [[Hidden surface determination|visible surface determination]].
BSP trees have also been applied to image compression.<ref>{{cite journal | doi=10.1109/83.544569 | title=Image compression using binary space partitioning trees | date=1996 | last1=Radha | first1=H. | last2=Vetterli | first2=M. | last3=Leonardi | first3=R. | journal=IEEE Transactions on Image Processing | volume=5 | issue=12 | pages=1610–1624 | pmid=18290079 | bibcode=1996ITIP....5.1610R | url=https://infoscience.epfl.ch/record/33877/files/RadhaVL96.pdf }}</ref>

==See also==
* [[Chazelle polyhedron]]
* [[k-d tree]]
* [[Octree]]
* [[Quadtree]]
* [[Hierarchical clustering]], an alternative way to divide [[3D model]] data for efficient rendering.
*[[Guillotine cutting]]

==References==
{{Reflist}}

==Additional references==
{{refbegin}}
*{{cite journal |first=B. |last=Naylor |title=Constructing Good Partitioning Trees |date=May 1993 |journal=Graphics Interface |url=https://www.researchgate.net/publication/2492209 |citeseerx=10.1.1.16.4432}}{{dead link|date=January 2025|bot=medic}}{{cbignore|bot=medic}}
*{{cite journal |first1=H. |last1=Radha |first2=R. |last2=Leoonardi |first3=M. |last3=Vetterli |first4=B. |last4=Naylor |title=Binary space partitioning tree representation of images |journal=Journal of Visual Communications and Image Processing |volume=2 |issue=3 |pages=201–221 |date=1991 |doi=10.1016/1047-3203(91)90023-9 |url=http://infoscience.epfl.ch/record/33911 |doi-access=free}}
*{{cite thesis |first=H.M.S. |last=Radha |title=Efficient Image Representation using Binary Space Partitioning Trees |date=1993 |type=PhD |publisher=Columbia University |oclc=30775044}}
*{{cite journal |first=H.M.S. |last=Radha |title=Efficient image representation using binary space partitioning trees |journal=Signal Processing |volume=35 |issue=2 |pages=174–181 |date=1994 |doi=10.1016/0165-1684(94)90047-7|bibcode=1994SigPr..35..174R }}
*{{cite journal |first1=H. |last1=Radha |first2=M. |last2=Vetterli |first3=R. |last3=Leoonardi |title=Image compression using binary space partitioning trees |journal=IEEE Transactions on Image Processing |volume=5 |issue=12 |pages=1610–24 |date=December 1996 |doi=10.1109/83.544569 |url=http://infoscience.epfl.ch/record/33877 |pmid=18290079 |bibcode=1996ITIP....5.1610R}}https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract
*{{cite CiteSeerX |first=A.S. |last=Winter |title=An investigation into real-time 3d polygon rendering using bsp trees |date=April 1999 |citeseerx=10.1.1.11.9725}}
*{{cite book |first1=M. |last1=de Berg |author-link=Mark de Berg |first2=M. |last2=van Kreveld |author2-link=Marc van Kreveld |first3=M. |last3=Overmars |author3-link=Mark Overmars |first4=O. |last4=Schwarzkopf |author4-link=Otfried Schwarzkopf |year=2000 |title=Computational Geometry |publisher=[[Springer-Verlag]] |edition=2nd |isbn=978-3-540-65620-3 |url-access=registration |url=https://archive.org/details/computationalgeo00berg |chapter=§12: Binary Space Partitions |pages=251–265}} Describes a randomized Painter's Algorithm..
*{{cite book |first=Christer |last=Ericson |chapter=8. BSP Tree Hierarchies |chapter-url=https://books.google.com/books?id=WGpL6Sk9qNAC&pg=PA350 |title=Real-Time collision detection |publisher=Morgan Kaufmann |date=2005 |isbn=1-55860-732-3 |pages=349–382 |series=Morgan Kaufmann Series in Interactive 3-D Technology}}
{{refend}}

==External links==
*{{cite web |url=https://www.researchgate.net/publication/238348725 |first=B.F. |last=Naylor |title=A Tutorial on Binary Space Partitioning Trees |date=2005 }}
*[http://www.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html BSP trees presentation]
*[https://web.archive.org/web/20110719195212/http://www.cc.gatech.edu/classes/AY2004/cs4451a_fall/bsp.pdf Another BSP trees presentation]
*[http://symbolcraft.com/graphics/bsp/ A Java applet that demonstrates the process of tree generation]
*[http://archive.gamedev.net/archive/reference/programming/features/bsptree/bsp.pdf A Master Thesis about BSP generating]
*[https://web.archive.org/web/20111115163809/http://www.devmaster.net/articles/bsp-trees BSP Trees: Theory and Implementation]
*[http://www.euclideanspace.com/threed/solidmodel/spatialdecomposition/bsp/index.htm BSP in 3D space]
*[https://www.google.com/books/edition/Graphics_Gems_V_Macintosh_Version/ekGjBQAAQBAJ?hl=en&gbpv=1&dq=graphics%20gems%20v&pg=PA121&printsec=frontcover Graphics Gems V: A Walk through BSP Trees]

{{Authority control}}

[[Category:Binary trees]]
[[Category:Geometric data structures]]
[[Category:3D computer graphics]]
[[Category:Articles with example C code]]

J. H. Hexter

2025-10-10T17:04:22Z

2A00:23C5:FE1C:3701:11C:3C25:E9B9:C886: hyphen

{{Short description|American historian (1910–1996)}}
{{More citations needed|date=December 2023}}
{{infobox person
| name= J. H. Hexter
| birth_name= Jack H. Hexter
| birth_date= {{birth date|1910|5|25}}
| birth_place= [[Memphis, Tennessee]], U.S.
| death_date= {{death date and age|1996|12|8|1910|5|25}}
| death_place= [[St. Louis]], [[Missouri]], U.S.
| education= [[University of Cincinnati]] ([[Bachelor of Arts|BA]])<br>[[Harvard University]] ([[Master of Arts|MA]], [[Doctor of Philosophy|PhD]])
| occupation= Historian
| employer= [[Queens College, City University of New York|Queens College]]<br>[[Washington University in St. Louis]]<br>[[Yale University]]
| spouse= {{marriage|Ruth Mullin|1942}}
| children= 4
}}
'''Jack H. Hexter''' (May 25, 1910 – December 8, 1996) was an American historian, a specialist in [[Tudor period|Tudor]] and seventeenth-century [[British history]], and well known for his comments on [[historiography]]. Hexter was a member of both the [[American Academy of Arts and Sciences]] and the [[American Philosophical Society]].<ref>{{Cite web |title=Jack H. Hexter |url=https://www.amacad.org/person/jack-h-hexter |access-date=2022-05-17 |website=American Academy of Arts & Sciences |language=en}}</ref><ref>{{Cite web |title=APS Member History |url=https://search.amphilsoc.org/memhist/search?creator=Jack+H.+Hexter&title=&subject=&subdiv=&mem=&year=&year-max=&dead=&keyword=&smode=advanced |access-date=2022-05-17 |website=search.amphilsoc.org}}</ref>

==Early career==
Jack Hexter was born in [[Memphis, Tennessee]], and was awarded a BA by the [[University of Cincinnati]] in 1931.<ref name=Guggenheim>{{cite web |title=J. H. Hexter – John Simon Guggenheim Memorial Foundation… |url=https://www.gf.org/fellows/j-h-hexter/ |website=www.gf.org}}</ref><ref name=Davis1997>{{cite web |last1=Davis |first1=R. W. |title=J.H. Hexter (1910–96) – AHA |url=https://www.historians.org/perspectives-article/j-h-hexter-1910-96-march-1997/ |website=www.historians.org |access-date=24 November 2024 |date=1 March 1997}}</ref> He received his MA (1933) and PhD (1937) from [[Harvard University]].<ref name=Davis1997/> His research interests encompassed both political and intellectual history, as witnessed by his first two books, one a history of the parliamentary conflict leading up to the Civil War, and the other a nuanced textual interpretation of [[Thomas More|Thomas More's]] [[Utopia (More book)|''Utopia'']].<ref name=Davis1997/>

==Scholarship and historiography==
Hexter coined the term [[tunnel history]].<ref name=Breen1972>{{cite journal |last1=Breen |first1=T. H. |title=English Origins and New World Development: The Case of the Covenanted Militia in Seventeenth-Century Massachusetts |journal=Past & Present |date=1972 |issue=57 |pages=74–96 |url=https://www.jstor.org/stable/650417 |issn=0031-2746|url-access=subscription}}</ref><ref>Ostrowski, Donald (ed.), [https://academic.oup.com/cornell-scholarship-online/book/40415/chapter-abstract/347401072?redirectedFrom=fulltext 'Introduction'], Who Wrote That? Authorship Controversies from Moses to Sholokhov (Ithaca, NY, 2020; online edn, Cornell Scholarship Online, 21 Jan. 2021), https://doi.org/10.7591/cornell/9781501749704.003.0001, accessed 24 Nov. 2024.</ref>

Hexter's scholarly reputation probably owes as much to his historiographical critiques as to his body of research. He is noted for his distinction between [[lumpers and splitters|"splitters" and "lumpers"]] of historical material, and his 1975 attack on [[Christopher Hill (historian)|Christopher Hill]] (as a "lumper" of selectively read sources).<ref name="Palmer1979">{{cite journal |last1=Palmer |first1=William G. |title=The Burden of Proof: J.H. Hexter and Christopher Hill |journal=Journal of British Studies |date=1979 |volume=19 |issue=1 |pages=122–129 |url=https://www.jstor.org/stable/175685 |issn=0021-9371|url-access=subscription}}</ref> More to Hexter's fancy was the "splitter" who saw his responsibility to the full range of particulars and the ambiguity of historical sources. "Lumping" was the tendency that, according to Hexter, threatened to bind historians to overreaching generalizations, of which he suggested [[Marxism]] was the most typical and intellectually pernicious. Nonetheless, his essay appeared to argue that both tendencies (analysis and synthesis) were intellectually necessary.

==Storm over the gentry==
{{see also|Storm over the gentry}}
This attack continued from a position he had earlier assumed, in his response in the late 1950s to a debate between [[Lawrence Stone]] and [[Hugh Trevor-Roper]]. Stone, along with [[R.H. Tawney]], explained the origins of the [[English Civil War]] by positing that an increasingly well-off and ambitious [[gentry]] had, over the course of many years, destabilized the English state in which power had traditionally been divided between the aristocracy and the king. Trevor-Roper inverted this theory, arguing that in fact the Civil War was caused in part by court gentry who had fallen on bad times.

Hexter's contribution, puckishly titled "The Storm over the Gentry" and originally published in a popular magazine, contends that both theses are undermined by their authors' social determinism which causes them to overlook the ordinary business of the House of Commons. Hexter maintained that the overlooked group, the rural magnates, the wealthier of the country gentry, wielded the most influence in the House of Commons and had brought no real interest in revolution. To the contrary, their experience was in practical management and governance, and for the most part they did not act out of simple self-interest. The Civil War needs, therefore, to be seen as the story of how such solid, service-minded and economically comfortable men were persuaded to resist the King, and not as any particular group's economically motivated power grab.

His ultimate self-definition was overtly, unabashedly, and often polemically [[whiggish]]. For Hexter, the English Civil War was to be seen as the defence of traditional English liberties against an aggressive Crown. This position contrasted in the 1970s with the [[Historical revisionism|revisionist]] views of [[Conrad Russell]] and others who disputed both the uniqueness of the English Civil War and its connection with ideas of liberty. However, inasmuch as the revisionists were also explicitly anti-Marxist, their stance owed a great deal to Hexter's critiques. Russell in particular echoed Hexter's emphasis on continuity in English political values, Hexter's distinction between the Civil War and the subsequent Revolution, and Hexter's belief that contingencies better explained the coming of the War, while rejecting Hexter's view that Parliament was acting out of a clear-cut sense of constitutional obligation and embracing instead the view that religious conflicts and practical problems in the composite monarchy were more decisive.

Hexter in 1978 wrote a bitter historiographical review in which he attacked younger scholars for reducing the analysis of the Civil War to an essentially amoral struggle for power (socio-economic for the Marxists; religious, political and fiscal for the revisionists), which he argued was too dismissive of the intrinsic moral strength of Parliament's position. He thus declared his preference for the 19th-century narrative by [[Samuel Rawson Gardiner]] over the new interpretation, and, true to form, even adopted an exaggerated Whig-style argument: that one should recognize and accept the principles of the Parliamentary rebels because these ideas about freedom were the very foundation for our modern sense of political liberty.

==Hexter on Braudel==
Another famous Hexterian intervention in [[historiography]] is his article "[[Fernand Braudel]] and the Monde Braudellien", which can be seen as a more appreciative, temperate, and intellectually sophisticated antecedent to Hexter's attack on Hill. Here, Hexter dissected Braudel's vast "geohistory", ''[[Fernand Braudel#La Méditerranée|La Mediteranée]]'', marvelling at the organization of the [[Annales School]] but pointing out the ironic tensions between the Annales' rigorous, collaborative, scientific institutional ethos and its leader's passionate, highly personal, often factually inaccurate or poorly sourced book (for which much of the intellectual labor was carried out from memory while Braudel was in a [[prisoner-of-war camp]]). The article also reveals Hexter's satirical touch, as, in its first section, Hexter mimics the quantitative bent of the Annales scholars, representing their output in a series of graphs and tables.

==Academic positions==
His most prominent academic positions were at [[Queens College, City University of New York|Queens College of the City University of New York]] from 1938 until 1957, [[Washington University in St. Louis]] from 1957 until 1964, and at [[Yale University]] from 1964 to 1978, becoming Charles Stillé Professor. The Yale Center for Parliamentary History was founded in 1966 under his directorship. He then returned to [[Washington University in St. Louis|Washington University]], where he founded the [[Center for the History of Freedom]], and was named John M. Olin Professor Emeritus of the History of Freedom at Washington University, retiring in 1990. In this stead, he served as the founder and editor of the [[Stanford University Press]] ''Making of Modern Freedom'' series of books.

==Family==
Hexter married Ruth Mullin in 1942; they had four children. He died of congestive heart failure in [[St. Louis, Missouri]] after suffering heart ailments for much of his adult life.<ref name="Saxon1996">{{cite news |last1=Saxon |first1=Wolfgang |title=J. Hexter, 86, Who Began History of Freedom |url=https://www.nytimes.com/1996/12/16/arts/j-hexter-86-who-began-history-of-freedom.html |access-date=24 November 2024 |work=New York Times |date=16 December 1996 |page=13}}</ref>

==Works==
*''The Reign of King Pym'' (1941)<ref>{{cite journal|doi=10.1111/1750-0206.12544 |title=King Pym and his 'Happy, Scrappy Jester' |date=2021 |last1=Roberts |first1=Stephen K. |journal=Parliamentary History |volume=40 |pages=81–92 |s2cid=234078302 }}</ref> {{LCCN|a41004164}}
*''More's Utopia: The Biography of an Idea'' (1952) {{cite book|title=1976 edition|isbn=0837189470}}
*''Storm Over the Gentry: The Tawney-Trevor-Roper Controversy'' (1958)
*''Reappraisals in History: New Views on History and Society in Early Modern Europe'' (1961)
*''Utopia, Thomas More'' (1965) edited with [[Edward Surtz]], vol. 4 of the Yale Complete Edition of [[Thomas More]]
*''The Judaeo-Christian Tradition'' (1966)
*''The Traditions of the Western World'' (1967)
** {{cite book|url=https://books.google.com/books?id=2PsAIYb-6RoC | title=The Traditions of the Western World (Abridged) | isbn=9780819111807 | date=1980 | publisher=University Press of America }}
*''Europe Since 1500'' (1971) with [[Richard Pipes|R. Pipes]] and [[Anthony Molho|A. Molho]] {{isbn|0060428147}} {{LCCN|72147642}}
*''The History Primer'' (1971)
*''Doing History'' (1971) {{isbn|0253318203}} {{LCCN|70165049}}
*''The Vision of Politics on the Eve of the Reformation: More, Machiavelli, and Seyssel'' (1973)
*''On Historians: Reappraisals of the Masters of Modern History'' (1979) {{isbn|0674634268}} {{LCCN|78016635}}<ref name=Kirschner1980>{{cite journal |last1=Kirschner |first1=Julius |title=Review of On Historians |journal=Ethics |date=1980 |volume=90 |issue=4 |pages=596–602 |url=https://www.jstor.org/stable/2380458 |issn=0014-1704|url-access=subscription}}</ref>
*''The Monarchy of France, [[Claude De Seyssel]]'' (1981) translator with Michael Sherman, editor Donald R. Kelley
*''The Traditions of the Western World: Antiquity through the Early Modern period'' (vol. 1) (1982)
*''Parliament and Liberty from the Reign of Elizabeth to the English Civil War'' (1992) editor

==References==
{{Reflist}}

==Further reading==
*[[William Herbert Dray|Dray, W. H.]] ''J. H. Hexter, Neo-Whiggism and Early Stuart Historiography'' pages 133-149 from ''History and Theory'', Volume 26, 1987.
*Malament, Barbara (editor). [https://books.google.com/books?id=YsPnAAAAIAAJ ''After the Reformation: Essays in Honour of J.H. Hester''], Manchester: Manchester University Press, 1980.{{isbn|0-7190-0805-0}}

{{Authority control}}

{{DEFAULTSORT:Hexter, J. H.}}
[[Category:20th-century American historians]]
[[Category:American historiographers]]
[[Category:Queens College, City University of New York faculty]]
[[Category:Washington University in St. Louis faculty]]
[[Category:Yale University faculty]]
[[Category:Harvard University alumni]]
[[Category:University of Cincinnati alumni]]
[[Category:American male non-fiction writers]]
[[Category:20th-century American male writers]]
[[Category:Members of the American Philosophical Society]]
[[Category:Fellows of the American Academy of Arts and Sciences]]
[[Category:People from Memphis, Tennessee]]
[[Category:1910 births]]
[[Category:1996 deaths]]