home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / graphics / bsptree-faq < prev    next >
Encoding:
Internet Message Format  |  1995-09-27  |  56.8 KB

  1. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!newsfeed.internetmci.com!news.mathworks.com!news.kei.com!travelers.mail.cornell.edu!willow-farm.cit.cornell.edu!news.graphics.cornell.edu!uranus.graphics.cornell.edu!not-for-mail
  2. From: BSP-FAQ <bsp-faq@graphics.cornell.edu>
  3. Newsgroups: comp.graphics.algorithms,comp.answers,news.answers
  4. Subject: Binary Space Partitioning Trees FAQ
  5. Followup-To: comp.graphics.algorithms
  6. Date: 26 Sep 1995 11:28:16 -0400
  7. Organization: Cornell University Program of Computer Graphics
  8. Lines: 1365
  9. Sender: bwade@Graphics.Cornell.edu
  10. Approved: news-answers-request@MIT.EDU
  11. Message-ID: <44966g$dmo@uranus.graphics.cornell.edu>
  12. NNTP-Posting-Host: uranus.graphics.cornell.edu
  13. Summary: Frequently asked questions about Binary Space Partitioning trees.
  14. Xref: senator-bedfellow.mit.edu comp.graphics.algorithms:21402 comp.answers:14484 news.answers:53762
  15.  
  16. Archive-name: graphics/bsptree-faq
  17. Posting-Frequency: monthly
  18. URL: http://www.graphics.cornell.edu/bspfaq/
  19.  
  20.  
  21.                    BSP TREE FREQUENTLY ASKED QUESTIONS (FAQ)
  22.                                        
  23.    
  24.      _________________________________________________________________
  25.    
  26. Questions
  27.  
  28.    
  29.     1. About this document
  30.     2. Acknowledgements
  31.     3. How can you contribute?
  32.     4. About the pseudo C++ code
  33.     5. What is a BSP Tree?
  34.     6. How do you build a BSP Tree?
  35.     7. How do you partition a polygon with a plane?
  36.     8. How do you remove hidden surfaces with a BSP Tree?
  37.     9. How do you compute analytic visibility with a BSP Tree?
  38.    10. How do you accelerate ray tracing with a BSP Tree?
  39.    11. How do you perform boolean operations on polytopes with a BSP
  40.        Tree?
  41.    12. How do you perform collision detection with a BSP Tree?
  42.    13. How do you handle dynamic scenes with a BSP Tree?
  43.    14. How do you compute shadows with a BSP Tree?
  44.    15. How do you extract connectivity information from BSP Trees?
  45.    16. How are BSP Trees useful for robot motion planning?
  46.    17. How are BSP Trees used in DOOM?
  47.    18. How can you make a BSP Tree more robust?
  48.    19. How efficient is a BSP Tree?
  49.    20. How can you make a BSP Tree more efficient?
  50.    21. How can you avoid recursion?
  51.    22. What is the history of BSP Trees?
  52.    23. Where can you find sample code and related online resources?
  53.    24. References
  54.        
  55.    
  56.      _________________________________________________________________
  57.    
  58. Answers
  59.  
  60.     
  61.    About this document
  62.        
  63.        General
  64.        The purpose of this document is to provide answers to Frequently
  65.        Asked Questions about Binary Space Partitioning (BSP) Trees. This
  66.        document will be posted monthly to comp.graphics.algorithms. It is
  67.        also available via WWW at the URL:
  68.        
  69.         http://www.graphics.cornell.edu/bspfaq/
  70.    
  71.        
  72.        The most recent newsgroup posting of this document is available
  73.        via ftp at the URL:
  74.        
  75.         ftp://rtfm.mit.edu:/pub/usenet/news.answers/graphics/bsptree-faq
  76.    
  77.        
  78.        Requesting the FAQ by mail
  79.        You can request that the FAQ be mailed to you in plain text and
  80.        HTML formats by sending e-mail to bsp-faq@graphics.cornell.edu
  81.        with a subject line of "SEND BSP TREE [what]". The "[what]" should
  82.        be replaced with any combination of "TEXT" and "HTML".
  83.        Respectively, these will return to you a plain text version of the
  84.        FAQ, and an HTML formatted version of the FAQ viewable with Mosaic
  85.        or Netscape.
  86.        
  87.        Copyrights and distribution
  88.        This document is maintained by Bretton Wade, a graduate student at
  89.        the Cornell University Program of Computer Graphics.
  90.        
  91.        This document, and all its associated parts, are Copyright ©
  92.        1995, Bretton Wade. All rights reserved. Permisson to distribute
  93.        this collection, in part or full, via electronic means (emailed,
  94.        posted or archived) or printed copy are granted providing that no
  95.        charges are involved, reasonable attempt is made to use the most
  96.        current version, and all credits and copyright notices are
  97.        retained. If you make a link to the WWW page, please inform the
  98.        maintainer so he can construct reciprocal links.
  99.        
  100.        Requests for other distribution rights, including incorporation in
  101.        commercial products, such as books, magazine articles, CD-ROMs,
  102.        and binary applications should be made to
  103.        bsp-faq@graphics.cornell.edu.
  104.        
  105.        Warranty and disclaimer
  106.        This article is provided as is without any express or implied
  107.        warranties. While every effort has been taken to ensure the
  108.        accuracy of the information contained in this article, the
  109.        author/maintainer/contributors assume(s) no responsibility for
  110.        errors or omissions, or for damages resulting from the use of the
  111.        information contained herein.
  112.        
  113.        The contents of this article do not necessarily represent the
  114.        opinions of Cornell University or the Program of Computer
  115.        Graphics.
  116.        --
  117.        Last Update: 07/05/95 03:46:05
  118.        
  119.        
  120.    Acknowledgements
  121.        
  122.        About the contributors
  123.        This document would not have been possible without the selfless
  124.        contributions and efforts of many individuals. I would like to
  125.        take the opportunity to thank each one of them. Please be aware
  126.        that these people may not be amenable to recieving e-mail on a
  127.        random basis. If you have any special questions, please contact
  128.        Bretton Wade (bwade@graphics.cornell.edu or
  129.        bsp-faq@graphics.cornell.edu) before trying to contact anyone
  130.        else on this list.
  131.        
  132.        Contributors
  133.           + Bruce Naylor (naylor@research.att.com)
  134.           + Richard Lobb (richard@cs.auckland.ac.nz)
  135.           + Dani Lischinski (danix@cs.washington.edu)
  136.           + Chris Schoeneman (crs@lightscape.com)
  137.           + Philip Hubbard (pmh@graphics.cornell.edu)
  138.           + Jim Arvo (arvo@graphics.cornell.edu)
  139.           + Kevin Ryan (kryan@access.digex.net)
  140.           + Joseph Fiore (fiore@cs.buffalo.edu)
  141.           + Lukas Rosenthaler (rosenth@foto.chemie.unibas.ch)
  142.           + Anson Tsao (ansont@hookup.net)
  143.           + Robert Zawarski (zawarski@chaph.usc.edu)
  144.           + Ron Capelli (capelli@vnet.ibm.com)
  145.           + Eric A. Haines (erich@eye.com)
  146.           + Ian CR Mapleson (mapleson@cee.hw.ac.uk)
  147.           + Richard Dorman (richard@cs.wits.ac.za)
  148.           + Steve Larsen (larsen@sunset.cs.utah.edu)
  149.           + Timothy Miller (tsm@cs.brown.edu)
  150.           + Ben Trumbore (wbt@graphics.cornell.edu)
  151.           + Richard Matthias (richardm@cogs.susx.ac.uk)
  152.           + Ken Shoemake (shoemake@graphics.cis.upenn.edu)
  153.           + Seth Teller (seth@theory.lcs.mit.edu)
  154.           + Peter Shirley (shirley@graphics.cornell.edu)
  155.           + Michael Abrash (mikeab@idece2.idsoftware.com)
  156.           + Robert Schmidt (robert@idt.unit.no)
  157.    
  158.        
  159.        If I have neglected to mention your name, and you contributed,
  160.        please let me know immediately!
  161.        --
  162.        Last Update: 07/05/95 15:42:30
  163.        
  164.        
  165.    How can you contribute?
  166.        
  167.        Please send all new questions, corrections, suggestions, and
  168.        contributions to bsp-faq@graphics.cornell.edu.
  169.        --
  170.        Last Update: 03/29/95 14:12:10
  171.        
  172.        
  173.    About the pseudo C++ code
  174.        
  175.        Overview
  176.        The general efficiency of C++ makes it a well suited language for
  177.        programming computer graphics. Furthermore, the abstract nature of
  178.        the language allows it to be used effectively as a psuedo code for
  179.        demonstrative purposes. I will use C++ notation for all the
  180.        examples in this document.
  181.        
  182.        In order to provide effective examples, it is necessary to assume
  183.        that certain classes already exist, and can be used without
  184.        presenting excessive details of their operation. Basic classes
  185.        such as lists and arrays fall into this category.
  186.        
  187.        Other classes which will be very useful for examples need to be
  188.        presented here, but the definitions will be generic to allow for
  189.        freedom of interpretation. I assume points and vectors to each be
  190.        an array of 3 real numbers (X, Y, Z).
  191.        
  192.        Planes are represented as an array of 4 real numbers (A, B, C, D).
  193.        The vector (A, B, C) is the normal vector to the plane. Polygons
  194.        are structures composited from an array of points, which are the
  195.        vertices, and a plane.
  196.        
  197.        The overloaded operator for a dot product (inner product, scalar
  198.        product, etc.) of two vectors is the '|' symbol. This has two
  199.        advantages, the first of which is that it can't be confused with
  200.        the scalar multiplication operator. The second is that precedence
  201.        of C++ operators will usually require that dot product operations
  202.        be parenthesized, which is consistent with the linear algebra
  203.        notation for an inner product.
  204.        
  205.        The code for BSP trees presented here is intended to be
  206.        educational, and may or may not be very efficient. For the sake of
  207.        clarity, the BSP tree itself will not be defined as a class.
  208.        --
  209.        Last Update: 04/30/95 15:45:19
  210.        
  211.        
  212.    What is a BSP Tree?
  213.        
  214.        Overview A Binary Space Partitioning (BSP) tree represents a
  215.        recursive, hierarchical partitioning, or subdivision, of
  216.        n-dimensional space into convex subspaces. BSP tree construction
  217.        is a process which takes a subspace and partitions it by any
  218.        hyperplane that intersects the interior of that subspace. The
  219.        result is two new subspaces that can be further partitioned by
  220.        recursive application of the method.
  221.        
  222.        A "hyperplane" in n-dimensional space is an n-1 dimensional object
  223.        which can be used to divide the space into two half-spaces. For
  224.        example, in three dimensional space, the "hyperplane" is a plane.
  225.        In two dimensional space, a line is used.
  226.        
  227.        BSP trees are extremely versatile, because they are powerful
  228.        sorting and classification structures. They have uses ranging from
  229.        hidden surface removal and ray tracing hierarchies to solid
  230.        modeling and robot motion planning.
  231.        
  232.        Example
  233.        An easy way to think about BSP trees is to limit the discussion to
  234.        two dimensions. To simplify the situation, let's say that we will
  235.        use only lines parallel to the X or Y axis, and that we will
  236.        divide the space equally at each node. For example, given a square
  237.        somewhere in the XY plane, we select the first split, and thus the
  238.        root of the BSP Tree, to cut the square in half in the X
  239.        direction. At each slice, we will choose a line of the opposite
  240.        orientation from the last one, so the second slice will divide
  241.        each of the new pieces in the Y direction. This process will
  242.        continue recursively until we reach a stopping point, and looks
  243.        like this:
  244.        
  245. +-----------+      +-----+-----+      +-----+-----+
  246. |           |      |     |     |      |     |     |
  247. |           |      |     |     |      |  d  |     |
  248. |           |      |     |     |      |     |     |
  249. |     a     |  ->  |  b  X  c  |  ->  +--Y--+  f  |  -> ...
  250. |           |      |     |     |      |     |     |
  251. |           |      |     |     |      |  e  |     |
  252. |           |      |     |     |      |     |     |
  253. +-----------+      +-----+-----+      +-----+-----+
  254.    
  255.        
  256.        The resulting BSP tree looks like this at each step:
  257.       a                  X                  X           ...
  258.                        -/ \+              -/ \+
  259.                        /   \              /   \
  260.                       b     c            Y     f
  261.                                        -/ \+
  262.                                        /   \
  263.                                       e     d
  264.    
  265.        
  266.        Other space partitioning structures
  267.        BSP trees are closely related to Quadtrees and Octrees. Quadtrees
  268.        and Octrees are space partitioning trees which recursively divide
  269.        subspaces into four and eight new subspaces, respectively. A BSP
  270.        Tree can be used to simulate both of these structures.
  271.        --
  272.        Last Update: 05/16/95 01:18:59
  273.        
  274.        
  275.    How do you build a BSP Tree?
  276.        
  277.        Overview
  278.        Given a set of polygons in three dimensional space, we want to
  279.        build a BSP tree which contains all of the polygons. For now, we
  280.        will ignore the question of how the resulting tree is going to be
  281.        used.
  282.        
  283.        The algorithm to build a BSP tree is very simple:
  284.        
  285.          1. Select a partition plane.
  286.          2. Partition the set of polygons with the plane.
  287.          3. Recurse with each of the two new sets.
  288.    
  289.        
  290.        Choosing the partition plane
  291.        The choice of partition plane depends on how the tree will be
  292.        used, and what sort of efficiency criteria you have for the
  293.        construction. For some purposes, it is appropriate to choose the
  294.        partition plane from the input set of polygons. Other applications
  295.        may benefit more from axis aligned orthogonal partitions.
  296.        
  297.        In any case, you want to evaluate how your choice will affect the
  298.        results. It is desirable to have a balanced tree, where each leaf
  299.        contains roughly the same number of polygons. However, there is
  300.        some cost in achieving this. If a polygon happens to span the
  301.        partition plane, it will be split into two or more pieces. A poor
  302.        choice of the partition plane can result in many such splits, and
  303.        a marked increase in the number of polygons. Usually there will be
  304.        some trade off between a well balanced tree and a large number of
  305.        splits.
  306.        
  307.        Partitioning polygons
  308.        Partitioning a set of polygons with a plane is done by classifying
  309.        each member of the set with respect to the plane. If a polygon
  310.        lies entirely to one side or the other of the plane, then it is
  311.        not modified, and is added to the partition set for the side that
  312.        it is on. If a polygon spans the plane, it is split into two or
  313.        more pieces and the resulting parts are added to the sets
  314.        associated with either side as appropriate.
  315.        
  316.        When to stop
  317.        The decision to terminate tree construction is, again, a matter of
  318.        the specific application. Some methods terminate when the number
  319.        of polygons in a leaf node is below a maximum value. Other methods
  320.        continue until every polygon is placed in an internal node.
  321.        Another criteria is a maximum tree depth.
  322.        
  323.        Pseudo C++ code example
  324.        Here is an example of how you might code a BSP tree:
  325.        
  326. struct  BSP_tree
  327. {
  328.    plane     partition;
  329.    list      polygons;
  330.    BSP_tree  *front,
  331.              *back;
  332. };
  333.    This structure definition will be used for all subsequent example
  334.        code. It stores pointers to its children, the partitioning plane
  335.        for the node, and a list of polygons coincident with the partition
  336.        plane. For this example, there will always be at least one polygon
  337.        in the coincident list: the polygon used to determine the
  338.        partition plane. A constructor method for this structure should
  339.        initialize the child pointers to NULL.
  340.        
  341. void    Build_BSP_Tree (BSP_tree *tree, list polygons)
  342. {
  343.    polygon   *root = polygons.Get_From_List ();
  344.    tree->partition = root->Get_Plane ();
  345.    tree->polygons.Add_To_List (root);
  346.    list      front_list,
  347.              back_list;
  348.    polygon   *poly;
  349.    while ((poly = polygons.Get_From_List ()) != 0)
  350.    {
  351.       int   result = tree->partition.Classify_Polygon (poly);
  352.       switch (result)
  353.       {
  354.          case COINCIDENT:
  355.             tree->polygons.Add_To_List (poly);
  356.             break;
  357.          case IN_BACK_OF:
  358.             backlist.Add_To_List (poly);
  359.             break;
  360.          case IN_FRONT_OF:
  361.             frontlist.Add_To_List (poly);
  362.             break;
  363.          case SPANNING:
  364.             polygon   *front_piece, *back_piece;
  365.             Split_Polygon (poly, tree->partition, front_piece, back_piece);
  366.             backlist.Add_To_List (back_piece);
  367.             frontlist.Add_To_List (front_piece);
  368.             break;
  369.       }
  370.    }
  371.    if ( ! front_list.Is_Empty_List ())
  372.    {
  373.       tree->front = new BSP_tree;
  374.       Build_BSP_Tree (tree->front, front_list);
  375.    }
  376.    if ( ! back_list.Is_Empty_List ())
  377.    {
  378.       tree->back = new BSP_tree;
  379.       Build_BSP_Tree (tree->back, back_list);
  380.    }
  381. }
  382.    This routine recursively constructs a BSP tree using the above
  383.        definition. It takes the first polygon from the input list and
  384.        uses it to partition the remainder of the set. The routine then
  385.        calls itself recursively with each of the two partitions. This
  386.        implementation assumes that all of the input polygons are convex.
  387.        
  388.        One obvious improvement to this example is to choose the
  389.        partitioning plane more intelligently. This issue is addressed
  390.        separately in the section, "How can you make a BSP Tree more
  391.        efficient?".
  392.        --
  393.        Last Update: 05/08/95 13:10:25
  394.        
  395.        
  396.    How do you partition a polygon with a plane?
  397.        
  398.        Overview
  399.        Partitioning a polygon with a plane is a matter of determining
  400.        which side of the plane the polygon is on. This is referred to as
  401.        a front/back test, and is performed by testing each point in the
  402.        polygon against the plane. If all of the points lie to one side of
  403.        the plane, then the entire polygon is on that side and does not
  404.        need to be split. If some points lie on both sides of the plane,
  405.        then the polygon is split into two or more pieces.
  406.        
  407.        The basic algorithm is to loop across all the edges of the polygon
  408.        and find those for which one vertex is on each side of the
  409.        partition plane. The intersection points of these edges and the
  410.        plane are computed, and those points are used as new vertices for
  411.        the resulting pieces.
  412.        
  413.        Implementation notes
  414.        Classifying a point with respect to a plane is done by passing the
  415.        (x, y, z) values of the point into the plane equation, Ax + By +
  416.        Cz + D = 0. The result of this operation is the distance from the
  417.        plane to the point along the plane's normal vector. It will be
  418.        positive if the point is on the side of the plane pointed to by
  419.        the normal vector, negative otherwise. If the result is 0, the
  420.        point is on the plane.
  421.        
  422.        For those not familiar with the plane equation, The values A, B,
  423.        and C are the coordinate values of the normal vector. D can be
  424.        calculated by substituting a point known to be on the plane for x,
  425.        y, and z.
  426.        
  427.        Convex polygons are generally easier to deal with in BSP tree
  428.        construction than concave ones, because splitting them with a
  429.        plane always results in exactly two convex pieces. Furthermore,
  430.        the algorithm for splitting convex polygons is straightforward and
  431.        robust. Splitting of concave polygons, especially self
  432.        intersecting ones, is a significant problem in its own right.
  433.        
  434.        Pseudo C++ code example
  435.        Here is a very basic function to split a convex polygon with a
  436.        plane:
  437.        
  438. void Split_Polygon (polygon *poly, plane *part, polygon *&front, polygon *&back
  439. )
  440. {
  441.    int   count = poly->NumVertices (),
  442.          out_c = 0, in_c = 0;
  443.    point ptA, ptB,
  444.          outpts[MAXPTS],
  445.          inpts[MAXPTS];
  446.    real sideA, sideB;
  447.    ptA = poly->Vertex (count - 1);
  448.    sideA = part->Classify_Point (ptA);
  449.    for (short i = -1; ++i < count;)
  450.    {
  451.       ptB = poly->Vertex (i);
  452.       sideB = part->Classify_Point (ptB);
  453.       if (sideB > 0)
  454.       {
  455.          if (sideA < 0)
  456.          {
  457.             // compute the intersection point of the line
  458.             // from point A to point B with the partition
  459.             // plane. This is a simple ray-plane intersection.
  460.             vector v = ptB - ptA;
  461.             real   sect = - part->Classify_Point (ptA) / (part->Normal () | v);
  462.             outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
  463.          }
  464.          outpts[out_c++] = ptB;
  465.       }
  466.       else if (sideB < 0)
  467.       {
  468.          if (sideA > 0)
  469.          {
  470.             // compute the intersection point of the line
  471.             // from point A to point B with the partition
  472.             // plane. This is a simple ray-plane intersection.
  473.             vector v = ptB - ptA;
  474.             real   sect = - part->Classify_Point (ptA) / (part->Normal () | v);
  475.             outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
  476.          }
  477.          inpts[in_c++] = ptB;
  478.       }
  479.       else
  480.          outpts[out_c++] = inpts[in_c++] = ptB;
  481.       ptA = ptB;
  482.       sideA = sideB;
  483.    }
  484.    front = new polygon (outpts, out_c);
  485.    back = new polygon (inpts, in_c);
  486. }
  487.    A simple extension to this code that is good for BSP trees is to
  488.        combine its functionality with the routine to classify a polygon
  489.        with respect to a plane.
  490.        
  491.        Note that this code is not robust, since numerical stability may
  492.        cause errors in the classification of a point. The standard
  493.        solution is to make the plane "thick" by use of an epsilon value.
  494.        --
  495.        Last Update: 07/05/95 15:42:30
  496.        
  497.        
  498.    How do you remove hidden surfaces with a BSP Tree?
  499.        
  500.        Overview
  501.        Probably the most common application of BSP trees is hidden
  502.        surface removal in three dimensions. BSP trees provide an elegant,
  503.        efficient method for sorting polygons via a depth first tree walk.
  504.        This fact can be exploited in a back to front "painter's
  505.        algorithm" approach to the visible surface problem, or a front to
  506.        back scanline approach.
  507.        
  508.        BSP trees are well suited to interactive display of static (not
  509.        moving) geometry because the tree can be constructed as a
  510.        preprocess. Then the display from any arbitrary viewpoint can be
  511.        done in linear time. Adding dynamic (moving) objects to the scene
  512.        is discussed in another section of this document.
  513.        
  514.        Painter's algorithm
  515.        The idea behind the painter's algorithm is to draw polygons far
  516.        away from the eye first, followed by drawing those that are close
  517.        to the eye. Hidden surfaces will be written over in the image as
  518.        the surfaces that obscure them are drawn. One condition for a
  519.        successful painter's algorithm is that there be a single plane
  520.        which separates any two objects. This means that it might be
  521.        necessary to split polygons in certain configurations. For
  522.        example, this case can not be drawn correctly with a painter's
  523.        algorithm:
  524.        
  525.                           +------+
  526.                           |      |
  527.           +---------------|      |--+
  528.           |               |      |  |
  529.           |               |      |  |
  530.           |               |      |  |
  531.           |      +--------|      |--+
  532.           |      |        |      |
  533.        +--|      |--------+      |
  534.        |  |      |               |
  535.        |  |      |               |
  536.        |  |      |               |
  537.        +--|      |---------------+
  538.           |      |
  539.           +------+
  540.    One reason that BSP trees are so elegant for the painter's algorithm
  541.        is that the splitting of difficult polygons is an automatic part
  542.        of tree construction. Note that only one of these two polygons
  543.        needs to be split in order to resolve the problem.
  544.        
  545.        To draw the contents of the tree, perform a back to front tree
  546.        traversal. Begin at the root node and classify the eye point with
  547.        respect to its partition plane. Draw the subtree at the far child
  548.        from the eye, then draw the polygons in this node, then draw the
  549.        near subtree. Repeat this procedure recursively for each subtree.
  550.        
  551.        Scanline hidden surface removal
  552.        It is just as easy to traverse the BSP tree in front to back order
  553.        as it is for back to front. We can use this to our advantage in a
  554.        scanline method method by using a write mask which will prevent
  555.        pixels from being written more than once. This will represent
  556.        significant speedups if a complex lighting model is evaluated for
  557.        each pixel, because the painter's algorithm will blindly evaluate
  558.        the same pixel many times.
  559.        
  560.        The trick to making a scanline approach successful is to have an
  561.        efficient method for masking pixels. One way to do this is to
  562.        maintain a list of pixel spans which have not yet been written to
  563.        for each scan line. For each polygon scan converted, only pixels
  564.        in the available spans are written, and the spans are updated
  565.        accordingly.
  566.        
  567.        The scan line spans can be represented as binary trees, which are
  568.        just one dimensional BSP trees. This technique can be expanded to
  569.        a two dimensional screen coverage algorithm using a two
  570.        dimensional BSP tree to represent the masked regions. Any convex
  571.        partitioning scheme, such as a quadtree, can be used with similar
  572.        effect.
  573.        
  574.        Implementation notes
  575.        When building a BSP tree specifically for hidden surface removal,
  576.        the partition planes are usually chosen from the input polygon
  577.        set. However, any arbitrary plane can be used if there are no
  578.        intersecting or concave polygons, as in the example above.
  579.        
  580.        Pseudo C++ code example
  581.        Using the BSP_tree structure defined in the section, "How do you
  582.        build a BSP Tree?", here is a simple example of a back to front
  583.        tree traversal:
  584.        
  585. void    Draw_BSP_Tree (BSP_tree *tree, point eye)
  586. {
  587.    real   result = tree->partition.Classify_Point (eye);
  588.    if (result > 0)
  589.    {
  590.       Draw_BSP_Tree (tree->back, eye);
  591.       tree->polygons.Draw_Polygon_List ();
  592.       Draw_BSP_Tree (tree->front, eye);
  593.    }
  594.    else if (result < 0)
  595.    {
  596.       Draw_BSP_Tree (tree->front, eye);
  597.       tree->polygons.Draw_Polygon_List ();
  598.       Draw_BSP_Tree (tree->back, eye);
  599.    }
  600.    else // result is 0
  601.    {
  602.       // the eye point is on the partition plane...
  603.       Draw_BSP_Tree (tree->front, eye);
  604.       Draw_BSP_Tree (tree->back, eye);
  605.    }
  606. }
  607.    If the eye point is classified as being on the partition plane, the
  608.        drawing order is unclear. This is not a problem if the
  609.        Draw_Polygon_List routine is smart enough to not draw polygons
  610.        that are not within the viewing frustum. The coincident polygon
  611.        list does not need to be drawn in this case, because those
  612.        polygons will not be visible to the user.
  613.        
  614.        It is possible to substantially improve the quality of this
  615.        example by including the viewing direction vector in the
  616.        computation. You can determine that entire subtrees are behind the
  617.        viewer by comparing the view vector to the partition plane normal
  618.        vector. This test can also make a better decision about tree
  619.        drawing when the eye point lies on the partition plane. It is
  620.        worth noting that this improvement resembles the method for
  621.        tracing a ray through a BSP tree, which is discussed in another
  622.        section of this document.
  623.        
  624.        Front to back tree traversal is accomplished in exactly the same
  625.        manner, except that the recursive calls to Draw_BSP_Tree occur in
  626.        reverse order.
  627.        --
  628.        Last Update: 05/08/95 13:10:25
  629.        
  630.        
  631.    How do you compute analytic visibility with a BSP Tree?
  632.        
  633.        Overview
  634.        
  635.        --
  636.        Last Update: 05/20/95 22:56:51
  637.        
  638.        
  639.    How do you accelerate ray tracing with a BSP Tree?
  640.        
  641.        Overview
  642.        Ray tracing a BSP tree is very similar to hidden surface removal
  643.        with a BSP tree. The algorithm is a simple forward tree walk, with
  644.        a few additions that apply to ray casting.
  645.        
  646.        MORE TO COME
  647.        
  648.        
  649.        --
  650.        Last Update: 04/30/95 15:45:19
  651.        
  652.        
  653.    How do you perform boolean operations on polytopes with a BSP Tree?
  654.        
  655.        Overview
  656.        There are two major classes of solid modeling methods with BSP
  657.        trees. For both methods, it is useful to introduce the notion of
  658.        an in/out test.
  659.        
  660.        An in/out test is a different way of talking about the front/back
  661.        test we have been using to classify points with respect to planes.
  662.        The necessity for this shift in thought is evident when
  663.        considering polytopes instead of just polygons. A point can not be
  664.        merely in front or back of a polytope, but inside or outside.
  665.        Somewhat formally, a point is inside of a polytope if it is inside
  666.        of, or in back of, each hyperplane which composes the polytope,
  667.        otherwise it is outside.
  668.        
  669.        Incremental construction
  670.        Incremental construction of a BSP Tree is the process of inserting
  671.        convex polytopes into the tree one by one. Each polytope has to be
  672.        processed according to the operation desired.
  673.        
  674.        It is useful to examine the construction process in two
  675.        dimensions. Consider the following figure:
  676.        
  677.  
  678. A               B
  679.  +-------------+
  680.  |             |
  681.  |             |
  682.  |      E      |        F
  683.  |       +-----+-------+
  684.  |       |     |       |
  685.  |       |     |       |
  686.  |       |     |       |
  687.  +-------+-----+       |
  688. D        |      C      |
  689.          |             |
  690.          |             |
  691.          +-------------+
  692.         H               G
  693.    Two polygons, ABCD, and EFGH, are to be inserted into the tree. We
  694.        wish to find the union of these two polygons. Start by inserting
  695.        polygon ABCD into the tree, choosing the splitting hyperplanes to
  696.        be coincident with the edges. The tree looks like this after
  697.        insertion of ABCD:
  698.        
  699.  
  700.                 AB
  701.               -/  \+
  702.               /    \
  703.              /      *
  704.             BC
  705.           -/  \+
  706.           /    \
  707.          /      *
  708.         CD
  709.       -/  \+
  710.       /    \
  711.      /      *
  712.     DA
  713.   -/  \+
  714.   /    \
  715.  *      *
  716.    Now, polygon EFGH is inserted into the tree, one polygon at a time.
  717.        The result looks like this:
  718.  
  719. A               B
  720.  +-------------+
  721.  |             |
  722.  |             |
  723.  |      E      |J       F
  724.  |       +-----+-------+
  725.  |       |     |       |
  726.  |       |     |       |
  727.  |       |     |       |
  728.  +-------+-----+       |
  729. D        |L    :C      |
  730.          |     :       |
  731.          |     :       |
  732.          +-----+-------+
  733.         H      K        G
  734.  
  735.                         AB
  736.                       -/  \+
  737.                       /    \
  738.                      /      *
  739.                     BC
  740.                   -/  \+
  741.                   /    \
  742.                  /      \
  743.                 CD       \
  744.               -/  \+      \
  745.               /    \       \
  746.              /      \       \
  747.             DA       \       \
  748.           -/  \+      \       \
  749.           /    \       \       \
  750.          /      *       \       \
  751.         EJ              KH       \
  752.       -/  \+          -/  \+      \
  753.       /    \          /    \       \
  754.      /      *        /      *       \
  755.     LE              HL              JF
  756.   -/  \+          -/  \+          -/  \+
  757.   /    \          /    \          /    \
  758.  *      *        *      *        FG     *
  759.                                -/  \+
  760.                                /    \
  761.                               /      *
  762.                              GK
  763.                            -/  \+
  764.                            /    \
  765.                           *      *
  766.    Notice that when we insert EFGH, we split edges EF and HE along the
  767.        edges of ABCD. this has the effect of dividing these segments into
  768.        pieces which are inside ABCD, and outside ABCD. Segments EJ and LE
  769.        will not be part of the boundary of the union. We could have saved
  770.        our selves some work by not inserting them into the tree at all.
  771.        For a union operation, you can always throw away segments that
  772.        land in inside nodes. You must be careful about this though. What
  773.        I mean is that any segments which land in inside nodes of side the
  774.        pre-existing tree, not the tree as it is being constructed. EJ and
  775.        LE landed in an inside node of the tree for polygon ABCD, and so
  776.        can be discarded.
  777.        
  778.        Our tree now looks like this:
  779. 
  780. A               B
  781.  +-------------+
  782.  |             |
  783.  |             |
  784.  |             |J       F
  785.  |             +-------+
  786.  |             |       |
  787.  |             |       |
  788.  |             |       |
  789.  +-------+-----+       |
  790. D        |L    :C      |
  791.          |     :       |
  792.          |     :       |
  793.          +-----+-------+
  794.         H      K        G
  795.  
  796.                         AB
  797.                       -/  \+
  798.                       /    \
  799.                      /      *
  800.                     BC
  801.                   -/  \+
  802.                   /    \
  803.                  /      \
  804.                 CD       \
  805.               -/  \+      \
  806.               /    \       \
  807.              /      \       \
  808.             DA       \       \
  809.           -/  \+      \       \
  810.           /    \       \       \
  811.          *      *       \       \
  812.                         KH       \
  813.                       -/  \+      \
  814.                       /    \       \
  815.                      /      *       \
  816.                     HL              JF
  817.                   -/  \+          -/  \+
  818.                   /    \          /    \
  819.                  *      *        FG     *
  820.                                -/  \+
  821.                                /    \
  822.                               /      *
  823.                              GK
  824.                            -/  \+
  825.                            /    \
  826.                           *      *
  827.    Now, we would like some way to eliminate the segments JC and CL, so
  828.        that we will be left with the boundary segments of the union.
  829.        Examine the segment BC in the tree. What we would like to do is
  830.        split BC with the hyperplane JF. Conveniently, we can do this by
  831.        pushing the BC segment through the node for JF. The resulting
  832.        segments can be classified with the rest of the JF subtree. Notice
  833.        that the segment BJ lands in an out node, and that JC lands in an
  834.        in node. Remembering that we can discard interior nodes, we can
  835.        eliminate JC. The segment BJ replaces BC in the original tree.
  836.        This process is repeated for segment CD, yielding the segments CL
  837.        and LD. CL is discarded as landing in an interior node, and LD
  838.        replaces CD in the original tree. The result looks like this:
  839. 
  840. A               B
  841.  +-------------+
  842.  |             |
  843.  |             |
  844.  |             |J       F
  845.  |             +-------+
  846.  |                     |
  847.  |                     |
  848.  |        L            |
  849.  +-------+             |
  850. D        |             |
  851.          |             |
  852.          |             |
  853.          +-----+-------+
  854.         H      K        G
  855.  
  856.                         AB
  857.                       -/  \+
  858.                       /    \
  859.                      /      *
  860.                     BJ
  861.                   -/  \+
  862.                   /    \
  863.                  /      \
  864.                 LD       \
  865.               -/  \+      \
  866.               /    \       \
  867.              /      \       \
  868.             DA       \       \
  869.           -/  \+      \       \
  870.           /    \       \       \
  871.          *      *       \       \
  872.                         KH       \
  873.                       -/  \+      \
  874.                       /    \       \
  875.                      /      *       \
  876.                     HL              JF
  877.                   -/  \+          -/  \+
  878.                   /    \          /    \
  879.                  *      *        FG     *
  880.                                -/  \+
  881.                                /    \
  882.                               /      *
  883.                              GK
  884.                            -/  \+
  885.                            /    \
  886.                           *      *
  887.    As you can see, the result is the union of the polygons ABCD and EFGH.
  888.        
  889.        To perform other boolean operations, the process is similar. For
  890.        intersection, you discard segments which land in exterior nodes
  891.        instead of internal ones. The difference operation is special. It
  892.        requires that you invert the polytope before insertion. For simple
  893.        objects, this can be achieved by scaling with a factor of -1. The
  894.        insertion process is then cinducted as an intersection operation,
  895.        where segments landing in external nodes are discarded.
  896.        
  897.        Tree merging
  898.        
  899.        --
  900.        Last Update: 04/30/95 15:45:20
  901.        
  902.        
  903.    How do you perform collision detection with a BSP Tree?
  904.        
  905.        Overview
  906.        Detecting whether or not a point moving along a line intersects
  907.        some object in space is essentially a ray tracing problem.
  908.        Detecting whether or not two complex objects intersect is
  909.        something of a tree merging problem.
  910.        
  911.        Typically, motion is computed in a series of Euler steps. This
  912.        just means that the motion is computed at discrete time intervals
  913.        using some description of the speed of motion. For any given point
  914.        P moving from point A with a velocity V, it's location can be
  915.        computed at time T as P = A + (T * V).
  916.        
  917.        Consider the case where T = 1, and we are computing the motion in
  918.        one second steps. To find out if the point P has collided with any
  919.        part of the scene, we will first compute the endpoints of the
  920.        motion for this time step. P1 = A + V, and P2 = A + (2 * V). These
  921.        two endpoints will be classified with respect to the BSP tree. If
  922.        P1 is outside of all objects, and P2 is inside some object, then
  923.        an intersection has clearly occurred. However, if P2 is also
  924.        outside, we still have to check for a collision in between.
  925.        
  926.        Two approaches are possible. The first is commonly used in
  927.        applications like games, where speed is critical, and accuracy is
  928.        not. This approach is to recursively divide the motion segment in
  929.        half, and check the midpoint for containment by some object.
  930.        Typically, it is good enough to say that an intersection occurred,
  931.        and not be very accurate about where it occurred.
  932.        
  933.        The second approach, which is more accurate, but also more time
  934.        consuming, is to treat the motion segment as a ray, and intersect
  935.        the ray with the BSP Tree. This also has the advantage that the
  936.        motion resulting from the impact can be computed more accurately.
  937.        --
  938.        Last Update: 04/30/95 15:45:20
  939.        
  940.        
  941.    How do you handle dynamic scenes with a BSP Tree?
  942.        
  943.        Overview
  944.        So far the discussion of BSP tree structures has been limited to
  945.        handling objects that don't move. However, because the hidden
  946.        surface removal algorithm is so simple and efficient, it would be
  947.        nice if it could be used with dynamic scenes too. Faster animation
  948.        is the goal for many applications, most especially games.
  949.        
  950.        The BSP tree hidden surface removal algorithm can easily be
  951.        extended to allow for dynamic objects. For each frame, start with
  952.        a BSP tree containing all the static objects in the scene, and
  953.        reinsert the dynamic objects. While this is straightforward to
  954.        implement, it can involve substantial computation.
  955.        
  956.        If a dynamic object is separated from each static object by a
  957.        plane, the dynamic object can be represented as a single point
  958.        regardless of its complexity. This can dramatically reduce the
  959.        computation per frame because only one node per dynamic object is
  960.        inserted into the BSP tree. Compare that to one node for every
  961.        polygon in the object, and the reason for the savings is obvious.
  962.        During tree traversal, each point is expanded into the original
  963.        object.
  964.        
  965.        Implementation notes
  966.        Inserting a point into the BSP tree is very cheap, because there
  967.        is only one front/back test at each node. Points are never split,
  968.        which explains the requirement of separation by a plane. The
  969.        dynamic object will always be drawn completely in front of the
  970.        static objects behind it.
  971.        
  972.        A dynamic object inserted into the tree as a point can become a
  973.        child of either a static or dynamic node. If the parent is a
  974.        static node, perform a front/back test and insert the new node
  975.        appropriately. If it is a dynamic node, a different front/back
  976.        test is necessary, because a point doesn't partition three
  977.        dimesnional space. The correct front/back test is to simply
  978.        compare distances to the eye. Once computed, this distance can be
  979.        cached at the node until the frame is drawn.
  980.        
  981.        An alternative when inserting a dynamic node is to construct a
  982.        plane whose normal is the vector from the point to the eye. This
  983.        plane is used in front/back tests just like the partition plane in
  984.        a static node. The plane should be computed lazily and it is not
  985.        necessary to normalize the vector.
  986.        
  987.        Cleanup at the end of each frame is easy. A static node can never
  988.        be a child of a dynamic node, since all dynamic nodes are inserted
  989.        after the static tree is completed. This implies that all subtrees
  990.        of dynamic nodes can be removed at the same time as the dynamic
  991.        parent node.
  992.        
  993.        Advanced methods
  994.        Tree merging, "ghosts", real dynamic trees... MORE TO COME
  995.        --
  996.        Last Update: 04/29/95 03:14:22
  997.        
  998.        
  999.    How do you compute shadows with a BSP Tree?
  1000.        
  1001.        Overview
  1002.        
  1003.        --
  1004.        Last Update: 04/30/95 15:45:20
  1005.        
  1006.        
  1007.    How do you extract connectivity information from BSP Trees?
  1008.        
  1009.        Overview
  1010.        
  1011.        --
  1012.        Last Update: 04/30/95 15:45:20
  1013.        
  1014.        
  1015.    How are BSP Trees useful for robot motion planning?
  1016.        
  1017.        Overview
  1018.        
  1019.        --
  1020.        Last Update: 04/30/95 15:45:20
  1021.        
  1022.        
  1023.    How are BSP Trees used in DOOM?
  1024.        
  1025.        Overview
  1026.        Before you can understand how DOOM uses a BSP tree to accelerate
  1027.        its rendering process, you have to understand how the world is
  1028.        represented in DOOM. When someone creates a DOOM level in a level
  1029.        editor they draw linedefs in a 2d space. Yes, that's right, DOOM
  1030.        is only 2d. These linedefs (ignoring the special effects linedefs)
  1031.        must be arranged so that they form closed polygons. One linedef
  1032.        may be used to form the outline of two polygons (in which case it
  1033.        is known as a two-sided linedef) and one polygon may be contained
  1034.        within another, but no linedefs may cross. Each enclosed area of
  1035.        the world (i.e. polygon) is assigned a floor height, ceiling
  1036.        height, floor and ceiling textures, a lower texture and an upper
  1037.        texture. The lower texture is visible when a linedef is viewed
  1038.        from a direction where the floor is lower in the adjoining area.
  1039.        An equivalent thing is true for the upper texture. A set of these
  1040.        enclosed areas that all have the same attributes is known as a
  1041.        sector.
  1042.        
  1043.        When the level is saved by the editor some new information is
  1044.        created including the BSP tree for that level. Before the BSP tree
  1045.        can be created, all the sectors have to be split into convex
  1046.        polygons known as sub-sectors. If you had a sector that was a
  1047.        square area, then that would translate exactly into a sub-sector.
  1048.        Whereas if that sector was contained inside another larger square
  1049.        sector, the larger one would have to be split into four, four
  1050.        sided sub-sectors to make all the sub-sectors convex. When more
  1051.        complex sectors are split into sub-sectors the linedefs that bound
  1052.        that sector may need to be broken into smaller lengths. These
  1053.        linedef sections are called segs.
  1054.        
  1055.        Given a point on the 2d map, the renderer (which isn't discussed
  1056.        here) wants a list of all the segs that are visible from that
  1057.        viewpoint in closest first order. Because of the restrictions
  1058.        placed on the DOOM world, the renderer can easily tell when the
  1059.        screen has been filled so it can stop looking for segs at this
  1060.        time. This is quicker than rendering all the segs from back to
  1061.        front and using a method like painters algorithm.
  1062.        
  1063.        Each node in the BSP tree defines a partition line (this does not
  1064.        have be a linedef in the world but usually is) which is the
  1065.        equivalent to the partition plane of a 3d BSP tree. It then has
  1066.        left and right pointers which are either another node for further
  1067.        sub-division or a leaf, the leaf being a sub-sector in DOOM. The
  1068.        BSP tree in DOOM is effectively being used to sort whole
  1069.        sub-sectors rather than individual lines front to back. Each node
  1070.        also defines an orthogonal bounding box for each side of the
  1071.        partition. All segs on a particular side of the partition must be
  1072.        within that box. This speeds up the searching process by allowing
  1073.        whole branches of the tree to be discarded if that bounding box
  1074.        isn't visible. The test for visibility is simply if the bounding
  1075.        box lies wholly or partly within the cone defined by the left and
  1076.        right edges of the screen.
  1077.        
  1078.        During the display update process the BSP tree is searched
  1079.        starting from the node containing the sub-sector that the player
  1080.        is currently in. The search moves outwards through the tree
  1081.        (searching the other half of the current node before moving onto
  1082.        the other half of the parents node). When a partition test is
  1083.        performed the branch chosen is the one on the same side as the
  1084.        player. This facilitates the front to back searching. Each time a
  1085.        leaf is encountered the segs in that sub-sector are passed to the
  1086.        renderer. If the renderer has returned that the screen is filled
  1087.        then the process stops, otherwise it continues until the tree has
  1088.        been fully searched (in which case there is an error in the level
  1089.        design).
  1090.        
  1091.        In case you're thinking that it is inefficient to dump a whole
  1092.        sub-sectors worth of segs into the renderer at once, the segs in a
  1093.        sub-sector can be back-face culled very quickly. DOOM stores the
  1094.        angle of linedefs (of which segs are part). When the angle of the
  1095.        players view is calculated this allows segs to be culled in a
  1096.        single instruction! Angles are stored as a 16 bit number where 0
  1097.        is east an 65535 is 1/63336 south of east.
  1098.        --
  1099.        Last Update: 04/30/95 15:45:20
  1100.        
  1101.        
  1102.    How can you make a BSP Tree more robust?
  1103.        
  1104.        Overview
  1105.        
  1106.        --
  1107.        Last Update: 04/30/95 15:45:20
  1108.        
  1109.        
  1110.    How efficient is a BSP Tree?
  1111.        
  1112.        Space complexity
  1113.        For hidden surface removal and ray tracing accelleration, the
  1114.        upper bound is O(n ^ 2) for n polygons. The expected case is O(n)
  1115.        for most models. MORE LATER
  1116.        
  1117.        Time complexity
  1118.        For hidden surface removal and ray tracing accelleration, the
  1119.        upper bound is O(n ^ 2) for n polygons. The expected case is O(n)
  1120.        for most models. MORE LATER
  1121.        --
  1122.        Last Update: 04/30/95 15:45:20
  1123.        
  1124.        
  1125.    How can you make a BSP Tree more efficient?
  1126.        
  1127.        Bounding volumes
  1128.        Bounding spheres are simple to implement, take only a single plane
  1129.        comparison, using the center of the sphere.
  1130.        
  1131.        Optimal trees
  1132.        Construction of an optimal tree is an NP-complete problem. The
  1133.        problem is one of splitting versus tree balancing. These are
  1134.        mutually exclusive requirements. You should choose your strategy
  1135.        for building a good tree based on how you intend to use the tree.
  1136.        
  1137.        Minimizing splitting
  1138.        An obvious problem with BSP trees is that polygons get split
  1139.        during the construction phase, which results in a larger number of
  1140.        polygons. Larger numbers of polygons translate into larger storage
  1141.        requirements and longer tree traversal times. This is undesirable
  1142.        in all applications of BSP trees, so some scheme for minimizing
  1143.        splitting will improve tree performance.
  1144.        
  1145.        Bear in mind that minimization of splitting requires pre-existing
  1146.        knowledge about all of the polygons that will be inserted into the
  1147.        tree. This knowledge may not exist for interactive uses such as
  1148.        solid modelling.
  1149.        
  1150.        Tree balancing
  1151.        Tree balancing is important for uses which perform spatial
  1152.        classification of points, lines, and surfaces. This includes ray
  1153.        tracing and solid modelling. Tree balancing is important for these
  1154.        applications because the time complexity for classification is
  1155.        based on the depth of the tree. Unbalanced trees have deeper
  1156.        subtrees, and therefore have a worse worst case.
  1157.        
  1158.        For the hidden surface problem, balancing doesn't significantly
  1159.        affect runtime. This is because the expected time complexity for
  1160.        tree traversal is linear on the number of polygons in the tree,
  1161.        rather than the depth of the tree.
  1162.        
  1163.        Balancing vs. splitting
  1164.        If balancing is an important concern for your application, it will
  1165.        be necessary to trade off some balance for reduced splitting. If
  1166.        you are choosing your hyperplanes from the polygon candidates,
  1167.        then one way to optimize these two factors is to randomly select a
  1168.        small number of candidates. These new candidates are tested
  1169.        against the full list for splitting and balancing efficiency. A
  1170.        linear combination of the two efficiencies is used to rank the
  1171.        candidates, and the best one is chosen.
  1172.        
  1173.        Reference Counting
  1174.        Other Optimizations
  1175.        
  1176.        --
  1177.        Last Update: 05/16/95 01:16:38
  1178.        
  1179.        
  1180.    How can you avoid recursion?
  1181.        
  1182.        standard binary tree search/sort techniques apply.
  1183.        --
  1184.        Last Update: 03/02/95 23:40:07
  1185.        
  1186.        
  1187.    What is the history of BSP Trees?
  1188.        
  1189.        Overview
  1190.        
  1191.        --
  1192.        Last Update: 04/30/95 15:45:20
  1193.        
  1194.        
  1195.    Where can you find sample code and related online resources?
  1196.        
  1197.        BSP tree FAQ companion code
  1198.        The companion source code to this document is available via FTP
  1199.        at:
  1200.        
  1201.           + file://ftp.graphics.cornell.edu/pub/bsptree/
  1202.             
  1203.    or, you can also request that the source be mailed to you by sending
  1204.        e-mail to bsp-faq@graphics.cornell.edu with a subject line of
  1205.        "SEND BSP TREE SOURCE". This will return to you a UU encoded copy
  1206.        of the sample C++ source code.
  1207.        
  1208.        Other BSP tree resources
  1209.        Pat Fleckenstein and Rob Reay have put together a FAQ on 3D
  1210.        graphics, which includes a blurb on BSP Trees, and an ftp site
  1211.        with some sample code. They seem to have an unusual affinity for
  1212.        ftp sites, and therefore won't link the BSP tree FAQ from their
  1213.        document:
  1214.        
  1215.           + http://www.csh.rit.edu/~pat/misc/3dFaq.html
  1216.           + file://ftp.csh.rit.edu/pub/3dfaq/
  1217.    
  1218.        
  1219.        Dr. Dobbs Journal has an article in their July '95 issue about BSP
  1220.        trees, By Nathan Dwyer. It describes the construction of BSP trees
  1221.        for visible surface processing, how to split polygons with planes,
  1222.        and how to dump the tree to a file. There is C++ source code to
  1223.        accompany the article.
  1224.        
  1225.           + http://www.ddj.com/ddj/issues/j9507a.htm
  1226.           + http://www.ddj.com/ddj/issues/j9507b.htm
  1227.    
  1228.        
  1229.        Michael Abrash's columns in the '95 DDJ Sourcebooks are an
  1230.        excellent introduction to the concept of BSP trees, especially in
  1231.        two dimensions. The source code for these is available as part of
  1232.        a package.
  1233.        
  1234.           + ftp://ftp.mv.com/pub/ddj/1995/1995.cpp/asc.zip
  1235.    
  1236.        
  1237.        Ekkehard Beier has made available a generic 3D graphics kernel
  1238.        intended to assist development of graphics application interfaces.
  1239.        One of the classes in the library is a BSP tree, and full source
  1240.        is provided. The focus seems to be on ray tracing, with the code
  1241.        being based on Jim Arvo's Linear Time Voxel Walking article in the
  1242.        ray tracing news.
  1243.        
  1244.           +
  1245.             ftp://metallica.prakinf.tu-ilmenau.de/pub/PROJECTS/GENERIC/gen
  1246.             eric1.1.tar.gz
  1247.    
  1248.        
  1249.        Eddie Edwards wrote a commonly referenced text which describes 2D
  1250.        BSP trees in some detail for use in games like DOOM. It includes a
  1251.        bit of sample code, too.
  1252.        
  1253.           +
  1254.             file://x2ftp.oulu.fi/pub/msdos/programming/theory/bsp_tree.zip
  1255.    
  1256.        
  1257.        Mel Slater has made available his C source code for computing
  1258.        shadow volumes based on BSP trees:
  1259.        
  1260.           + http://www.dcs.qmw.ac.uk/~mel/BSP.html
  1261.    
  1262.        
  1263.        Graphics Gems
  1264.        The Graphics Gems archive at
  1265.        file://ftp.princeton.edu/pub/Graphics/GraphicsGems/ is an
  1266.        invaluable resource for all things graphical. In particular, there
  1267.        are some BSP tree references worth looking over.
  1268.        
  1269.        Peter Shirley and Kelvin Sung have C sample code for ray tracing
  1270.        with BSP trees in Graphics Gems III
  1271.        
  1272.        Norman Chin has provided a wonderful resource for BSP trees in
  1273.        Graphics Gems V. He provides C sample code for a wide variety of
  1274.        uses.
  1275.        
  1276.        More sources for sample BSP tree code
  1277.           +
  1278.             file://ftp.idsoftware.com/tonsmore/utils/level_edit/node_build
  1279.             ers/
  1280.           + file://ftp.cs.brown.edu/pub/sphigs.tar.Z
  1281.    
  1282.        
  1283.        General resources for computer graphics programming
  1284.        Algorithm, Incorporated, an Atlanta-based Scientific and
  1285.        Engineering Research and Development Company specializing in
  1286.        Computer Graphics Programming and Business Internet
  1287.        Communications, has lots of good pointers and useful offerings.
  1288.        
  1289.        If you are interested in game programming, check out the
  1290.        rec.games.programmer.faq:
  1291.        http://www.ee.ucl.ac.uk/~phart/FAQ/rgp_FAQ.html.
  1292.        --
  1293.        Last Update: 08/23/95 10:16:23
  1294.        
  1295.        
  1296.    References
  1297.        
  1298.        A partial listing of textual info on BSP trees.
  1299.        
  1300.     1. Abrash, M., BSP Trees, Dr. Dobbs Sourcebook, 20(14), 49-52,
  1301.        may/jun 1995.
  1302.        
  1303.     2. Dadoun, N., Kirkpatrick, D., and Walsh, J., The Geometry of Beam
  1304.        Tracing, Proceedings of the ACM Symposium on Computational
  1305.        Geometry, 55--61, jun 1985.
  1306.        
  1307.     3. Chin, N., and Feiner, S., Near Real-Time Shadow Generation Using
  1308.        BSP Trees, Computer Graphics (SIGGRAPH '89 Proceedings), 23(3),
  1309.        99--106, jul 1989.
  1310.        
  1311.     4. Chin, N., and Feiner, S., Fast object-precision shadow generation
  1312.        for area light sources using BSP trees, Computer Graphics (1992
  1313.        Symposium on Interactive 3D Graphics), 25(2), 21--30, mar 1992.
  1314.        
  1315.     5. Chrysanthou, Y., and Slater, M., Computing dynamic changes to BSP
  1316.        trees, Computer Graphics Forum (EUROGRAPHICS '92 Proceedings),
  1317.        11(3), 321--332, sep 1992.
  1318.        
  1319.     6. Naylor, B., Amanatides, J., and Thibault, W., Merging BSP Trees
  1320.        Yields Polyhedral Set Operations, Computer Graphics (SIGGRAPH '90
  1321.        Proceedings), 24(4), 115--124, aug 1990.
  1322.        
  1323.     7. Chin, N., and Feiner, S., Fast object-precision shadow generation
  1324.        for areal light sources using BSP trees, Computer Graphics (1992
  1325.        Symposium on Interactive 3D Graphics), 25(2), 21--30, mar 1992.
  1326.        
  1327.     8. Naylor, B., Interactive solid geometry via partitioning trees,
  1328.        Proceedings of Graphics Interface '92, 11--18, may 1992.
  1329.        
  1330.     9. Naylor, B., Partitioning tree image representation and generation
  1331.        from 3D geometric models, Proceedings of Graphics Interface '92,
  1332.        201--212, may 1992.
  1333.        
  1334.    10. Naylor, B., {SCULPT} An Interactive Solid Modeling Tool,
  1335.        Proceedings of Graphics Interface '90, 138--148, may 1990.
  1336.        
  1337.    11. Gordon, D., and Chen, S., Front-to-back display of BSP trees, IEEE
  1338.        Computer Graphics and Applications, 11(5), 79--85, sep 1991.
  1339.        
  1340.    12. Ihm, I., and Naylor, B., Piecewise linear approximations of
  1341.        digitized space curves with applications, Scientific Visualization
  1342.        of Physical Phenomena (Proceedings of CG International '91),
  1343.        545--569, 1991.
  1344.        
  1345.    13. Vanecek, G., Brep-index: a multidimensional space partitioning
  1346.        tree, Internat. J. Comput. Geom. Appl., 1(3), 243--261, 1991.
  1347.        
  1348.    14. Arvo, J., Linear Time Voxel Walking for Octrees, Ray Tracing News,
  1349.        feb 1988.
  1350.        
  1351.    15. Jansen, F., Data Structures for Ray Tracing, Data Structures for
  1352.        Raster Graphics, 57--73, 1986.
  1353.        
  1354.    16. MacDonald, J., and Booth, K., Heuristics for Ray Tracing Using
  1355.        Space Subdivision, Proceedings of Graphics Interface '89, 152--63,
  1356.        jun 1989.
  1357.        
  1358.    17. Naylor, B., and Thibault, W., Application of BSP Trees to Ray
  1359.        Tracing and CSG Evaluation, Tech. Rep. GIT-ICS 86/03, feb 1986.
  1360.        
  1361.    18. Sung, K., and Shirley, P., Ray Tracing with the BSP Tree, Graphics
  1362.        Gems III, 271--274, 1992.
  1363.        
  1364.    19. Fuchs, H., Kedem, Z., and Naylor, B., On Visible Surface
  1365.        Generation by A Priori Tree Structures, Conf. Proc. of SIGGRAPH
  1366.        '80, 14(3), 124--133, jul 1980.
  1367.        
  1368.    20. Paterson, M., and Yao, F., Efficient Binary Space Partitions for
  1369.        Hidden-Surface Removal and Solid Modeling, Discrete and
  1370.        Computational Geometry, 5(5), 485--503, 1990.
  1371.        
  1372.        
  1373.        --
  1374.        Last Update: 06/19/95 09:59:42
  1375.        
  1376.    
  1377.      _________________________________________________________________
  1378.    
  1379.    This document was last updated on
  1380.    Andrew Kunz (ank@graphics.cornell.edu)
  1381.