home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / SBUFFER.TXT < prev    next >
Text File  |  1996-06-02  |  35KB  |  923 lines

  1. This was posted in rec.games.programmer by Paul Nettle 
  2.  
  3.  
  4. --------------------------------------------------------------------------
  5. S-BUFFER FAQ
  6.  
  7. Original Creation:
  8. Mar. 10, 1995
  9. Written By:
  10. Paul Nettle
  11. Version:
  12. 1.0.0
  13. --------------------------------------------------------------------------
  14.  
  15. A note from the author:
  16.  
  17. This may be a bit wordy at times, so I'll try to keep it light with
  18. some of my humor -- you may not call it humor, but at least *I* think
  19. it's funny. :)
  20.  
  21. Where did they come from?  s-Buffers were developed for my game
  22. engine.  Though, since I don't believe that FAQs should have anything
  23. to do with commercialization, I won't even mention the name of this
  24. product.  Let's keep FAQs for their purpose -- FACTS.
  25.  
  26. The technique described in the next few hundred lines of text bears a
  27. close resemblance to some scanline rendering methods of which I
  28. believe span-buffering is one of them.
  29.  
  30. Actually, I had no idea what span-buffering was until I spoke to a
  31. gentleman named Chris Babcock who read the original posts about
  32. s-buffering.  He explained to me what span-buffering was, and as it
  33. turns out, the two techniques are similar, but do have some major
  34. differences (mainly the Insertion routine and segment manager).
  35.  
  36. The major difference is that s-Buffers are more so meant for use in
  37. game engines.  Engines that are meant to produce a high frame rate.
  38.  
  39. When I posted a note to the rec.games.programmer newsgroup about the
  40. fact that I had discovered a technique that would perform z-Buffers
  41. in software faster than hardware could, the response was, quite
  42. literally, overwhelming.  Most of which was plagued with polite
  43. suspicion and skepticism.  This alone told me that, at least, in the
  44. gaming community, this technique was unfamiliar territory.  So, I
  45. propose to you, the game developer, a new technique, called
  46. s-Buffering.
  47.  
  48. The particular implementation of this technique and it's name are
  49. both my own original creation, sparked by my own, sometimes wry
  50. thoughts.  This FAQ and the techniques contained within are also all
  51. my own creation.  This isn't to say that there isn't somebody else
  52. out there that has once thought about these techniques or variations
  53. thereof.  I have no control over their thoughts (and wouldn't want to
  54. -- Ewwwwww!).  I am quite confident, however, that this technique is
  55. not popular, not documented, and not in wide use within games.
  56.  
  57. If you find the information contained within these words, diagrams,
  58. and psudo-codes useful to any degree, please contact me.  If you use
  59. this technique in a product (commercial or otherwise) that you would
  60. not have done so if it had not been for this FAQ, please just drop
  61. me a line and let me know.  It's nice to hear those things. Hearing
  62. good things about efforts like this can only spark more.
  63.  
  64. I would also encourage anybody and everybody to dig in.  Play with
  65. this new technique.  It's not perfect, and the "Insertion" routine
  66. can be it's own line of discussion -- inventing many new algorithms
  67. for insertion can very possibly improve the performance of this
  68. technique in quantum leaps.  I would expect that if this technique
  69. gains any popularity, you'll see new insertion algorithms popping up
  70. in the next Siggraph Proceedings.
  71.  
  72. I'll be the caretaker of this document.  Please make all corrections
  73. through me by contribution (internet e-mail preferred).
  74.  
  75. If you do have other useful information related to this FAQ, !PLEASE!
  76. contact me.  I may very well want to include it in future versions of
  77. this FAQ.  Lets keep the InfoBahn alive, let's contribute to it, and
  78. share ideas.  We've got a hell of a lot of brains out there to draw
  79. from.
  80.  
  81.                                        Striving for speeeeed,
  82.  
  83.                                               Paul Nettle
  84.                                               Hot Wax Software
  85.  
  86.  
  87.  
  88.   "And now for something completely different.  A man with six-hundred
  89.                 thirty-two-thousand four-hundred and forty-two big toes."
  90.  
  91. --------------------------------------------------------------------
  92. Q:  "How do I contact Paul?"
  93. --------------------------------------------------------------------
  94.  
  95. My vitals are:
  96. --------------
  97.  
  98. ADR:  7054 Foxthorn Dr.
  99.       Canton, MI  48187-3073
  100.  
  101. PH#:  (313) 981-6143 anytime
  102.  
  103. NET:  pnettle@umcc.umich.edu
  104. CIS:  72163,2442
  105.  
  106. Please, the name's "Paul", not "Mr. Nettle" :)  I hear "Mr. Nettle",
  107. and I turn around looking for an older man.
  108.  
  109. ----------------------------------------------------------------------
  110. Q:  "OK, so what the heck is this all about?!!"
  111. ----------------------------------------------------------------------
  112.  
  113. The movie "Weekend at Bernies" quotes this line:
  114.  
  115.     "He's got good form!"
  116.  
  117. I think that's one of my favorite quotes because, to me, it has a serious
  118. side other than it's humorous description of a corpse being dragged behind
  119. a moving boat by a rope, braining itself on buoys along the way.
  120.  
  121. "Good form" is "Elegance."
  122.  
  123. Webster defines "Elegant" as:
  124.  
  125.              "Marked by concision, incisiveness, and
  126.               ingenuity; cleverly apt and simple"
  127.  
  128. I couldn't have said it better, Noah.  Since elegance is a goal and
  129. not a destination, it's something that's to be strived for.  You
  130. can't reach pure elegance since there is always *something* that's
  131. more elegant (the human body, for example).
  132.  
  133. I hope you find s-Buffers to be "simply brilliant."  Not that I'm the
  134. brilliant one, mind you, I only discovered the technique.  The
  135. technique then just started to jump up and down, wave it's arms,
  136. blare sirens, and was later found to be screaming out it's advantages
  137. at me.  I'm just writing them down.
  138.  
  139. So, back to the question.  What's this all about?  Elegance,
  140. Simplicity and, of course, Speeeeeeeeeeeeeeeeeeeeeeed!
  141.  
  142. -------------------------------------------------------------------------
  143. Q:  "Why s-Buffers?"
  144. -------------------------------------------------------------------------
  145.  
  146. First, consider z-Buffers.  If you're not sure EXACTLY how they work,
  147. I'll explain briefly:
  148.  
  149.         A z-Buffer is a `second copy' of the screen-image.  It usually has the
  150.     same resolution.  This z-Buffer is initialized to the largest possible
  151.     value held by an UNSIGNED INT (for 16-bit INTs, that's 0xFFFF, and for
  152.     32-bit INTs that's 0xFFFFFFFF).
  153.  
  154.     During the drawing of polygons, the depth-value for each pixel
  155.     written has to be kept track of.  As you draw each pixel in a
  156.     polygon, you compare the depth-value of that pixel with the value in
  157.     the z-Buffer's corresponding pixel location.  If the z-Buffer value is
  158.     larger (farther away from the camera), then the pixel is plotted, and
  159.     the z-Buffer is updated with the new pixel's depth.  If the z-Buffer
  160.     value is lower (closer to the camera), then the pixel is not drawn
  161.     since it is hidden behind the existing pixel.
  162.  
  163. This is a very simple approach, and, depending on implementation, can
  164. offer pixel-perfect output.  However it is very slow and cumbersome.
  165.  
  166. Your code's inner-most loop (the code that's doing the drawing of the
  167. pixels) -- the same code you've hand-assembled for speed is being
  168. used to waste clock cycles as if they're as rich a commodity as
  169. Madonna CDs.  Even if that mean-ol-nasty z-Buffer says the pixel is
  170. hidden, you still need to track your deltas.  You still have to keep
  171. moving through your shades, texture maps, bump maps, colors, etc. 
  172.  
  173. So, you've had to add depth-tracking as well as a slow check to
  174. another buffer (possibly outside of your CPU's cache), and a
  175. conditional update to that buffer.  Whew...what a waste.  Such a
  176. waste in fact, that I plan to tell you how s-Buffers are not only
  177. FAST, but FASTER than z-Buffering in HARDWARE.  Keep reading, it's
  178. all in here.
  179.  
  180. Is there a more elegant solution?  I believe I have found one. I call
  181. it, simply, "s-Buffering."
  182.  
  183. -------------------------------------------------------------------------
  184. Q:  "What are s-Buffers?"
  185. -------------------------------------------------------------------------
  186.  
  187. `S-Buffers' or `segmented-Buffers' are the segmented representation
  188. of a z-Buffer.  They have three key elements:
  189.  
  190. 1.  An array of linked-lists (for this example)
  191. 2.  An insertion routine for inserting segments into the s-buffer
  192. 3.  A segment manager
  193.  
  194. These key Elements are outlined in the next few questions.  To
  195. continue with the answer to this question, you'll need to read the
  196. next three Qs.
  197.  
  198. -------------------------------------------------------------------------
  199. Q:  "What is...KEY ELEMENT #1:  The s-Buffer itself"
  200. -------------------------------------------------------------------------
  201.  
  202. For the sake of simplicity, I'll just use a linked list, later, this
  203. can be expanded upon.  It's the concept I'm trying to get across
  204. here.
  205.  
  206. Lets consider our trusty friend, the z-Buffer.  Pull out a single
  207. scanline from the z-Buffer and set it's representation on the kitchen
  208. table (watch out, don't set it in the little puddle of spaghetti
  209. sauce).
  210.  
  211. You now have a single plane.  Across the front is the x-direction
  212. through a scanline.  As you run your finger from the front to the
  213. back you're moving it along the depth axis (z-axis).  Now go wipe
  214. that spaghetti off your finger.
  215.  
  216.                                     Kitchen-table representation
  217.     x     z-Buffer                (Dots represent the depth of a pixel)
  218.  +-------------------+                 _______________________  
  219. y|-------------------|                /   (far away)         / n
  220.  |-------------------|               /                      / o
  221.  |-------------------|              /       ..             / i
  222.  |-------------------|             /       .  .           / t
  223.  |---------------------\          / ...  ..    .         / c
  224.  |-------------------| |         / .   ..               / e
  225.  |-------------------| |        /..            .       / r
  226.  |-------------------| |       /                      / i
  227.  |-------------------| |      /                . ..../ d
  228.  |-------------------| |     /    (close)       .   / /
  229.  +-------------------+ \--->/______________________/ Z
  230.                              (front -- x-direction)
  231.  
  232. When you look at the entire z-buffer, you're looking at a stack of
  233. these planes (that's not true at all, but I want you to think of it
  234. that way for now).  So, lets just consider the kitchen-table
  235. representation.
  236.  
  237. For each scanline in the z-Buffer, what you have is a list of depth
  238. values for each pixel.  Even though you may only have a single
  239. polygon on the screen, and the depth values in the z-Buffer that the
  240. polygon occupies are all the same (it's orientation is perpendicular
  241. to the z-axis), you still have to check each pixel, right?  Not any
  242. more.
  243.  
  244. From now on, I don't want you to think in terms of pixels.  I want
  245. you to think in terms of the segments that make up that polygon.  In
  246. our case, we'll stick with horizontal segments (though orientation
  247. isn't important).
  248.  
  249. When you scan convert a polygon, you break it up into horizontal
  250. SEGMENTS:
  251.  
  252.               /\
  253.              /--\
  254.             /----\
  255.                      /------\
  256.           /--------\
  257.          /----------\
  258.          ------------\
  259.               --------\
  260.                    ----\
  261.  
  262. This is the key to s-Buffers.  Now you have a list of segments. 
  263. Rather that calling any low-level drawing routines to draw these
  264. segments, just simply call the s-buffer "insertion" routine.
  265.  
  266. No, this isn't going to be easy.  The "insertion" routine can be a
  267. beast all by itself.  But, there is a simple `starter' algorithm that
  268. I've included here.
  269.  
  270. When you're all done scan-converting your polygons and adding your
  271. segments to the s-Buffer, what do you have?
  272.  
  273. You have the ENTIRE screen in a well-formatted, nicely laid out
  274. fashion.  All the data is in one place, too.  The screen is laid
  275. out top-to-bottom and each scanline is left-to-right.  Can you think
  276. of any possible optimizations to take advantage of here?  I sure can.
  277.  
  278. Now it's time to call your 'modified' low-level drawing routine.  But
  279. first, a glance in the past.  In a lot of applications, the low-level
  280. drawing routine might look something like this:
  281.  
  282. void LowLevelDrawer( int x1, int x2, int y, int shade1, int shade1, int Color)
  283. {
  284.    [lots of setup code, clipping, etc.]
  285.    .
  286.    .
  287.    .
  288.    [draw the scanline]
  289.    .
  290.    .
  291.    .
  292.    [any exit code]
  293.      .
  294.    .
  295.    .
  296.    [return]
  297. }
  298.  
  299. This is for a single horizontal line of a polygon.  This routine will
  300. be getting called for each of the scanlines in a polygon, for every
  301. polygon.  Hmmm...I wonder how many times that startup code is gunna
  302. get run through...
  303.  
  304. See all them parameters (I count 6)?  That's just for a single piece
  305. of a single polygon for a simple gouraud shader.  What about a
  306. bump-mapper and texture-mapper?  Your stack will hate you for that,
  307. you're driving it nuts!  Push, Pop, Push, Pop, Push, Pop....
  308.  
  309. Here's a peek at your NEW and IMPROVED s-Buffer drawing routine.  It
  310. draws the ENTIRE screen:
  311.  
  312. void LowLevelDrawer( SBUFFER *Sbuf )
  313. {
  314.    while( !Done )
  315.    {
  316.       [do a little setup for this scanline]
  317.       .
  318.       .
  319.       .
  320.       [draw all segments for a single scanline (optimized code goes here)]
  321.       .
  322.       .
  323.       .
  324.       [next scanline]
  325.    }
  326.    [any exit code]
  327.    .
  328.    .
  329.    .
  330.    [return]
  331. }
  332.  
  333. When you leave here, you have a new screen, drawn to completion, ready
  334. for display.
  335.  
  336. One thing to note is that as you're drawing, if you watch it in slow-
  337. motion, you'll see that you're drawing each scanline from
  338. left-to-right, top-down.  Nice and clean.  I'll address this cool
  339. feature later...
  340.  
  341. -------------------------------------------------------------------------
  342. Q:  "What is...KEY ELEMENT #2:  The insertion routine"
  343. -------------------------------------------------------------------------
  344.  
  345. Due to the nature of it's possible complexity, the Insertion routine
  346. is the most important key element of the s-Buffer algorithm.  As
  347. such, it's also the most confusing routine to write.
  348.  
  349. Like some compression routines, any version of the de-compression
  350. routine can de-compress the data stored in compressed form.  However,
  351. each version of the compressing code is different.  Better
  352. compression can be obtained by better analysis.  The format of the
  353. output is still the same, but substantial gains can be made by better
  354. analysis in the compressing code.  I believe that the Insertion
  355. routine can also have this trait.  A better analysis on the part of
  356. the Insertion routine can simplify the job of the low-level drawing
  357. routines.
  358.  
  359. My point is that there is ALWAYS room for improvements to be made to
  360. any insertion routine.  The closer to perfect elegance, the better.
  361.  
  362. Take my rudimentary psudo-code for example.  The code relies on
  363. splitting segments that may not need splitting simply to keep the
  364. algorithm simple for explanation's sake.  It does the job, but it is
  365. wasteful.
  366.  
  367. Granted, the segments won't overlap (that would defeat the purpose of
  368. s-Buffering all together).  But on many occasions, a segment may be
  369. split into two segments side-by-side, causing the low-level drawing
  370. routines more effort, and wasting memory by using up more segments
  371. than are necessary.  And ultimately more time is spent in the drawing
  372. phase.
  373.  
  374. Please note that the following code may not be satisfactory for real
  375. use, but will certainly improve the performance of your application
  376. regardless.
  377.  
  378. You'll need these defined before we can start...
  379.  
  380.    Cur = Start of the existing segment list
  381.      New = Segment to be added to the list
  382.  
  383. First, the possible cases used in the psudo-code.  In the following
  384. cases, I use characters to represent pixels of the New segment being
  385. added (`n') and the current segment in the list being compared against
  386. (`c').  So in the following example:
  387.  
  388.          cccccccc
  389.             nnnnn
  390.  
  391. The Cur's right-half is overlapping with the entire New segment, and
  392. an intersection must be tested for.  These examples only represent
  393. where the start x coordinates and ending X coordinates fall, they in
  394. no way represent the depth values.
  395.  
  396. -----------------------------------------------------------
  397. Possible cases:
  398. -----------------------------------------------------------
  399.  
  400.             Case 1:
  401.          -> cccccc
  402.          ->        nnnnnn
  403.  
  404.       Case 2:
  405.          ->          cccccccc
  406.          -> nnnnnnnn
  407.  
  408.       Case 3a:
  409.          ->         ccccccccc
  410.          -> nnnnnnnnn
  411.  
  412.       Case 3b:
  413.          ->        cccccccccc
  414.          -> nnnnnnnnnn
  415.  
  416.       Case 3c:
  417.          ->         ccccccccc
  418.          -> nnnnnnnnnnnnnnnnn
  419.  
  420.       Case 3d:
  421.          ->    ccccccccccc
  422.          -> nnnnnnnnnnnnnnnnn
  423.  
  424.       Case 3e:
  425.          ->       c
  426.          -> nnnnnnnnnnnnn
  427.  
  428.       Case 3f:
  429.          ->             c
  430.          -> nnnnnnnnnnnnn
  431.  
  432.       Case 4a:
  433.          -> ccccccccccccc
  434.          ->   nnnnnnnn
  435.  
  436.       Case 4b:
  437.          -> ccccccccccccc
  438.                  ->   nnnnnnnnnnn
  439.  
  440.       Case 4c:
  441.          -> ccccccccccccc
  442.          ->             n
  443.  
  444.       Case 4d:
  445.          -> ccccccccccc
  446.          ->   nnnnnnnnnnn
  447.  
  448.       Case 4e:
  449.          -> ccccccc
  450.          ->       nnnnnnn
  451.  
  452.       Case 5:
  453.          -> cccccccccccccc
  454.          -> n
  455.  
  456.       Case 6:
  457.                  -> cccccccccccccc
  458.          -> nnnnnnn
  459.  
  460.       Case 7:
  461.          -> c
  462.          -> nnnnnnnnnnnnn
  463.  
  464.       Case 8:
  465.          -> ccccccc
  466.          -> nnnnnnnnnnnnnn
  467.  
  468.       Case 9:
  469.          ->       c
  470.          ->       n
  471.  
  472.       Case 10:
  473.          -> cccccccccccccc
  474.          -> nnnnnnnnnnnnnn
  475.  
  476. -----------------------------------------------------------
  477. Psudo-code for a rudimentary insertion routine begins here
  478. -----------------------------------------------------------
  479.  
  480.    if (New is entirely off-screen)
  481.       return;
  482.  
  483.    // Make sure segment is sorted left-right
  484.  
  485.    if (the list is empty)
  486.    {
  487.       just add it
  488.    }
  489.  
  490.    while(we still have entries in the list)
  491.    {
  492.       // Case 1
  493.       if (New.x1 > Cur.x2)
  494.       {
  495.                  // Next Cur
  496.          // Continue Checking
  497.       }
  498.       // Simply off-screen? (do this check again 'cause New is changin')
  499.       else if (New.x1 >= ScreenResX || New.x2 < 0)
  500.       {
  501.          // Return
  502.       }
  503.       // Case 2
  504.       else if (New.x2 < Cur.x1)
  505.       {
  506.          // Add New before Cur;
  507.          // Return
  508.       }
  509.       // Case 3
  510.       else if (New.x1 < Cur.x1)
  511.       {
  512.          // Split New at Cur's left-most point
  513.          // Add New's left-half before Cur
  514.                  // Replace New with it's right half
  515.          // Continue checking
  516.       }
  517.       // Case 4
  518.       else if (Cur.x1 < New.x1)
  519.       {
  520.          // Split Cur at New's left-most point
  521.          // Add Cur's right-half after Cur
  522.          // Next Cur
  523.          // Continue checking
  524.       }
  525.       // Cases 5 & 6
  526.       else if (Cur.x2 > New.x2)
  527.       {
  528.          // Case 5
  529.          if (New.x1 == New.x2)
  530.          {
  531.             // If New's starting Z is behind Cur's starting Z, just return
  532.             // Split Cur at New's right-most point + 1
  533.                         // Replace Cur with it's right half
  534.             // Add New before Cur
  535.             // Return
  536.          }
  537.          else
  538.          // Case 6
  539.          {
  540.             // Split Cur at New's right-most point + 1
  541.             // Replace Cur with it's right half
  542.             // Call IntersectSplit for New and Cur's left-half
  543.             // Return
  544.          }
  545.          
  546.       }
  547.       // Cases 7 & 8
  548.       else if (Cur.x2 < New.x2 )
  549.       {
  550.          // Case 7
  551.          if (Cur.x1 == Cur.x2)
  552.                  {
  553.             // Split New at Cur's right-most point + 1
  554.             // If Cur is behind New's left-half, replace Cur with New's left-half
  555.             // Continue checking using New's right half
  556.          }
  557.          // Case 8
  558.          else
  559.          {
  560.             // Split New at Cur's right-most point + 1
  561.             // Remove Cur from the list
  562.             // Call IntersectSplit for Cur and New's left-half
  563.             // Continue checking using New's right-half
  564.          }
  565.       }
  566.       // Cases 9 & 10
  567.       else
  568.       {
  569.          // Case 9
  570.          if (Cur.x1 == Cur.x2)
  571.                  {
  572.             // If Cur is behind New, replace Cur with New
  573.             // Return
  574.          }
  575.          // Case 10
  576.          else
  577.          {
  578.             // Remove Cur from the list
  579.             // Call IntersectSplit for Cur and New
  580.             // Return
  581.          }
  582.       }
  583.    }
  584.  
  585.    // Just add it to the end
  586.    // Return
  587.  
  588. -----------------------------------------------------------
  589. Psudo-code for a rudimentary insertion routine ends here
  590. -----------------------------------------------------------
  591.  
  592. This routine makes use of a few linked-list management routines and a
  593. routine I called IntersectSplit().
  594.  
  595. IntersectSplit() simply finds the intersection of two lines that
  596. start at the same x coordinate, end at the same x coordinate and
  597. returns the order in which the two segments appear from left->right,
  598. unless one segment is totally behind the other, in which case it
  599. simply returns the single segment.
  600.  
  601. Note that your splitting code must be very accurate.  Not making an
  602. accurate splitting routine or an accurate IntersectSplit() routine
  603. may cause artifacting in the foreground polygons caused by polygons
  604. hidden behind them.
  605.  
  606. Besides, if your intersection and splitting routines are accurate,
  607. then you can expect more accurate results than a 16-bit z-Buffer.
  608.  
  609. For more information on inserting segments into the list, see the Q
  610. titled: "What are some ways to improve the Insertion routine?"
  611.  
  612. -------------------------------------------------------------------------
  613. Q:  "What is...KEY ELEMENT #3:  The segment manager"
  614. -------------------------------------------------------------------------
  615.  
  616. The segment manager is simply a reservoir of pre-allocated segment
  617. structures.  These segment structures hold the actual segments that
  618. are linked together in the s-Buffer's linked lists.
  619.  
  620. If you were to malloc() and free() segments as you needed them, you
  621. run the risk of fragmenting memory, and running out of larger chunks
  622. of memory for other parts of your application.  Not to mention the
  623. extra overhead of the malloc() and free() routines.
  624.  
  625. To solve this problem, a segment manager is needed.  It keeps a
  626. reservoir of segments, and gives you free segments as you ask for
  627. them.  This may be done in any number of ways.  It's also very fast.
  628.  
  629. A simple data example would be an array of SEG pointers that is
  630. "grown" as needed, in blocks of...say...512 segments at a time. 
  631. When you run out of available segments, you simply allocate another
  632. block, and give one up.
  633.  
  634. Here's some psudo-code for the GetSegment() routine:
  635.  
  636. SEG *GetSegment( void )
  637. {
  638.    if (there are no available segments)
  639.    {
  640.       GrowReservoir()
  641.    }
  642.     
  643.    Find an available segment
  644.    Decrease the number of available segments in the reservoir
  645.    Return the segment pointer
  646. }
  647.  
  648. The segment manager might consist of these routines:
  649.  
  650.     InitSManager()
  651.  
  652.                 Allocates the default base number of segments for the reservoir
  653.         probably by calling GrowReservoir()
  654.  
  655.     UninitSManager()
  656.  
  657.         Frees all memory in use
  658.  
  659.     ResetSManager()
  660.  
  661.         Marks all segments in reservoir as "available"
  662.  
  663.     GetSegment()
  664.  
  665.         Find an available segment (call GrowReservoir() if none are
  666.         available), mark it as used, and return it's pointer.
  667.  
  668.     CopySegment()
  669.  
  670.         A simple memcpy() will do
  671.  
  672.         GrowReservoir()
  673.  
  674.                 realloc() the reservoir's array of segments in increments of
  675.                 some pre-determined number.  Use a #define for this number
  676.                 for fine-tuning memory usage.
  677.  
  678. -------------------------------------------------------------------------
  679. Q:  "What are some ways to improve the Insertion routine?"
  680. -------------------------------------------------------------------------
  681.  
  682. Now, it's your turn.  Let's have some optimizations.  I'd love to see
  683. any code/psudo-code submissions to the FAQ!  Here are some things to
  684. consider:
  685.  
  686.   1.  Using a Binary-searchable tree instead of a linked list
  687.  
  688.   2.  Checking entire New segments for fully behind or in-front
  689.       before adding or quitting.
  690.  
  691.   3.  [this section not complete]
  692.  
  693. -------------------------------------------------------------------------
  694. Q:  "What about accuracy?"
  695. -------------------------------------------------------------------------
  696.  
  697. Considering the accuracy of splitting two 2D line segments, the
  698. accuracy is perfectly pixel accurate where as a 16-bit z-Buffer is
  699. only partially accurate for a 32-bit world coordinate system.
  700.  
  701. -------------------------------------------------------------------------
  702. Q:  "What kind of performance can I expect?"
  703. -------------------------------------------------------------------------
  704.  
  705. I can't say, at this time, exactly what sort of performance
  706. improvements to expect over z-Buffer.  It all depends on the
  707. application, the code used for the segment manager, and especially the
  708. insertion routine.  When I have some numbers, I'll include them here.
  709.  
  710. However, let me explain why I believe you can expect better results
  711. out of s-Buffering than z-Buffering in hardware.  No this dude ain't
  712. nuts, that's right, software that's faster than hardware.  Keep on
  713. readin'. :)
  714.  
  715. When you're rendering to the s-Buffer, if you're clever about it in
  716. your insertion routine, you can eliminate many segments before they
  717. get into the s-Buffer, so you've just eliminated a segment that your
  718. code would have spent VERY valuable time drawing.  Consider this
  719. example:
  720.  
  721.  
  722.                                         +----------+    +----------+
  723.                     |4444444444|    |2222222222|
  724.                     |4444444444|    |2222222222|
  725.                  +------------------|2222222222|--+
  726.                  |111111111111111111|2222222222|11|
  727.                  |111111111111111111|2222222222|11|
  728.                  |111111111111111111|2222222222|11|
  729.                  |111111111111111111|2222222222|11|
  730.                  |111111111111111111|2222222222|11|
  731.                  +------------------|2222222222|--+
  732.                     |4444444444|    |2222222222|
  733.                     |4444444444|    |2222222222|
  734.                     |4444444444|    |2222222222|
  735.                     |4444444444|    |2222222222|
  736.                  +--|4444444444|------------------+
  737.                  |33|4444444444|333333333333333333|
  738.                  |33|4444444444|333333333333333333|
  739.                  |33|4444444444|333333333333333333|
  740.                  |33|4444444444|333333333333333333|
  741.                                  |33|4444444444|333333333333333333|
  742.                  +--|4444444444|------------------+
  743.                     |4444444444|    |2222222222|
  744.                     |4444444444|    |2222222222|
  745.                     +----------+    +----------+
  746.  
  747.      [You wouldn't believe how long it took to draw that!]
  748.  
  749.  
  750. In the above example, the polygons are numbered.  Notice, I even used
  751. the age-old problem of recursively overlapping polygons.  s-Buffers
  752. handle it intuitively.
  753.  
  754. There are (roughly) 300 pixels in the above example.  200 of which
  755. overlap.  Using z-Buffering in hardware, you will have to draw 500
  756. pixels, keep in mind that you'll also have to track the z-coords for
  757. each pixel for use with the z-buffer hardware.  But we'll ignore that
  758. fact for now.
  759.  
  760. So you draw blast out 500 pixels.  This is your lowest-level code.
  761. This is your fastest stuff.
  762.  
  763. You've just rendered a full-screen of polygons, and 40% of it was for
  764. nothing.  Jeesh! 40%!  What a waste!
  765.  
  766. Consider s-Buffers.  They immediately find that where you have an
  767. overlap in the example, there is no extra drawing to be done. Granted
  768. this takes a little time (not much, mind you).  But the savings is
  769. 40% of screen-space coverage!  You're simply NOT drawing those
  770. pixels!
  771.  
  772. There are other advantages, too.
  773.  
  774. s-Buffers allow you to cut your drawing to the significant pixels
  775. ONLY. You draw 300 pixels (without tracking the z-coord along the
  776. way).
  777.  
  778. Unless the hardware is drawing the stuff for you (which s-Buffers
  779. should be nicely adaptable to -- if the hardware supports scanline
  780. drawing of textures, shades, etc. rather than entire polygons) then
  781. you're still doing the drawing.  The z-Buffer hardware is only helping
  782. you out with your low-level code.  It's only doing something for
  783. you.  It's not reducing the number of pixels you draw, it's just
  784. doing some work for you.
  785.  
  786. s-Buffers not only reduce your workload by reducing the amount of
  787. screen space coverage you're drawing to, but it does the z-Buffering
  788. for you.  Just like hardware does.  Granted there is overhead for
  789. inserting segments, but nothing compared to the rendering of them to
  790. the screen only to find that they're not viewed.
  791.  
  792. So, in this example, you see about a 5/3 speed improvement.  It gets
  793. much better as you have more hidden polygons.  But, with z-Buffering,
  794. your performance just plummets with more hidden polys. It's an
  795. inverse non-linear scale to your disadvantage.
  796.  
  797. -------------------------------------------------------------------------
  798. Q:  "Yeah, so like, what about memory?"
  799. -------------------------------------------------------------------------
  800.  
  801. Since you've written a segment manager (which is, by definition -- a
  802. memory manager) you've got control.  You decide how much memory to
  803. allocate at any one point in time.  The smarter your segment manager
  804. is the better off you'll be.
  805.  
  806. But there is still the issue of how much memory to store the required
  807. segments in the list.
  808.  
  809. For simple gouraud shading, here's what I would expect a segment
  810. structure to look like:
  811.  
  812. typedef struct segment
  813. {
  814.  
  815.      short  start_x, end_x;       // starting and ending Xs
  816.      short  start_z, end_z;       // starting and ending Zs
  817.      char   start_s, end_s;       // starting and ending shade values
  818.  
  819. } SEG;
  820.  
  821. I count 14 bytes per segment structure.  This means that if your
  822. average segment is 7 pixels or more (consider this in YOUR
  823. application), then you've saved memory over a 16-bit z-Buffer.
  824.  
  825. This does NOT include any in-efficiencies in your segment manager or
  826. insertion routine (see the insertion routine questions for details).
  827.  
  828. You may not be doing simple grayscale gouraud shading.  You might
  829. have colors, too.  Add a byte (or whatever your app requires) for
  830. color.
  831.  
  832. Then there's the texture mapping information.  This adds to the size,
  833. too -- possibly almost doubling the amount of memory required.  But
  834. in some games (especially Wolfenstien-style games), you can still
  835. find a tremendous memory advantage over z-Buffers since the segments
  836. will most likely be so long.
  837.  
  838. These are things to consider when using s-Buffers.  If you find that
  839. the s-Buffers will use more memory than z-Buffers, you've got a
  840. decision to make:  Speed or Memory?
  841.  
  842. -------------------------------------------------------------------------
  843. Q:  "What are some more possible advantages of s-Buffers?"
  844. -------------------------------------------------------------------------
  845.  
  846. As you render the s-Buffer, you'll be rendering the screen top-down,
  847. and each scanline from left to right.  I can't think of any obvious
  848. advantages this offers other than the fact that it makes your
  849. low-level drawing routine a tightly optimized muscle machine.
  850.  
  851. If you have any cool ideas to make use of this unique feature, please
  852. lemme have 'em!
  853.  
  854. It would be an easy task to add information to your s-buffer lists
  855. that allows you to determine which scanlines have changed since the
  856. previous render so that your screen updates only contain updates to
  857. the scanlines that have changed.  This will reduce the amount of time
  858. you spend updating the slow RAM on your video card (for PCs).
  859.  
  860. For more, see the next two sections on Masking and Transparencies.
  861.  
  862. -------------------------------------------------------------------------
  863. Q:  "What about masking?"
  864. -------------------------------------------------------------------------
  865.  
  866. Many games have dash-board masks or the like.  s-Buffers offer a
  867. clean way to handle this.
  868.  
  869. You can add a flag to your segment structures that can make it a
  870. masking segment.
  871.  
  872. This way, you can build a masking s-Buffer, use it as your starting
  873. point when you render, and insert segments into it, not letting them
  874. interfere with the masking segments.  This will remove the need to
  875. perform pixel-by-pixel masking as the image is drawn to the screen.
  876.  
  877. This will also prevent your low-level drawing routines from having to
  878. render pixels behind the mask.
  879.  
  880. -------------------------------------------------------------------------
  881. Q:  "What about transparencies?"
  882. -------------------------------------------------------------------------
  883.  
  884. By extending the masking idea a bit further, you can flag certain
  885. segments as transparent.  As you insert segments, any non-transparent
  886. segments that fall behind the transparent ones won't remove the
  887. transparent segments.  Any non-transparent segments that end up
  888. in-front of the transparent ones will clip the transparent segments.
  889.  
  890. This brings up the problem that some segments now overlap with
  891. transparent segments, making the Insertion routine that much more
  892. complex.
  893.  
  894. Note that transparencies modify the image behind them.  If these
  895. transparent segments are kept in order of left-right (following their
  896. non-transparent neighbors in back-front order) within the linked-list
  897. for a scanline, as the low-level drawing routine draws the
  898. transparent segments, the non-transparent ones will already have been
  899. drawn, and the transparency modifications will fall into place
  900. nicely.
  901.  
  902. -------------------------------------------------------------------------
  903. Q:  "What are the disadvantages?"
  904. -------------------------------------------------------------------------
  905.  
  906. If s-Buffers are used to store many small segments, of if you use an
  907. in-efficient Insertion routine, you might find that the memory
  908. requirements will be quite high.  I would expect that this would only
  909. be a concern in a small percentage of the applications out there.
  910.  
  911. There can be much difficulty in writing insertion routine.
  912.  
  913.  
  914. s-Buffers won't work with some implementations of curved surfaces as
  915. a z-Buffer will.
  916.  
  917.  
  918.       
  919.  
  920. Last Updated: 29th March 1995 
  921.  
  922. Paul Hart (phart@eleceng.ucl.ac.uk) 
  923.