home *** CD-ROM | disk | FTP | other *** search
/ Groovy Bytes: Behind the Moon / groovybytes.iso / GROOVY / MISC / TEXTE / DEMO081.ZIP / DN_2OF2.081 < prev    next >
Encoding:
Text File  |  1995-01-29  |  26.1 KB  |  626 lines

  1. DemoNews.081.continued.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.part.2.of.2
  2.  
  3.  
  4.  
  5.              SECTIONS          ARTICLES
  6.  
  7.              ----------------  -----------------------------------
  8.  
  9.              Code              Assembly Part 3 (It ain't no party)
  10.  
  11.                                BSP Trees
  12.  
  13.              Back Issues       How to Get 'em, Descriptions
  14.  
  15.              Closing Comments  Quote for the Week, etc.
  16.  
  17.  
  18.  
  19. .,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,
  20.  
  21.  
  22.  
  23.  
  24.  
  25. _____Assembly Part 3 by Jason Nunn
  26.  
  27.  
  28.  
  29.      \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
  30.  
  31.      \\\\\\\\[ "Implementation Techniques" - Assembly Part III
  32.  
  33.      \\\\\\\[[  By Jason Nunn
  34.  
  35.      \\\\\[[[[
  36.  
  37.      \\[[[[[[[
  38.  
  39.      ____________________________________________________________________
  40.  
  41.  
  42.  
  43.  In this issue I will be discussing the basic nuts and bolts on how to
  44.  
  45.  implement an assembly program geared towards a demo. This article is
  46.  
  47.  intended for the C or Pascal programmer who hasn't quite got the confidence
  48.  
  49.  to use a full blown assembly compiler. In the first part, you may remember
  50.  
  51.  me telling you of a friend that has reached a turning point in his coding
  52.  
  53.  development, yet he still won't "take the plunge" because he doesn't have
  54.  
  55.  access to all the nice perks of 3GL's, like sine, cosine, and random
  56.  
  57.  functions and larger precision variables than the chip itself. This issue
  58.  
  59.  will hopefully provide that incentive.
  60.  
  61.  
  62.  
  63.  But...., before we do that, I would like to first finish off last article's
  64.  
  65.  talk on optimization. I forgot to include the fast string functions. I'm
  66.  
  67.  not going to waffle on too much about this now, as this article is
  68.  
  69.  dedicated to "assembly techniques". All I will do here is show my results,
  70.  
  71.  and give out some tips.
  72.  
  73.  
  74.  
  75.  Same things apply on this run - my machine is a 486-33 ISA, operating in
  76.  
  77.  P-mode, and the lower the number, the faster a given instruction is.
  78.  
  79.  
  80.  
  81.          STOSB   [209729]                MOV     [EDI],AL   [134226]
  82.  
  83.                                          INC     EDI
  84.  
  85.  
  86.  
  87.          STOSD   [306805]                MOV     [EDI],EAX  [244208]
  88.  
  89.                                          INC     EDI
  90.  
  91.  
  92.  
  93.          LODSB   [209729]                MOV     AL,[ESI]   [134226]
  94.  
  95.                                          INC     ESI
  96.  
  97.  
  98.  
  99.          STOSD   [306805]                MOV     EAX,[ESI]  [244208]
  100.  
  101.                                          INC     ESI
  102.  
  103.  
  104.  
  105.          MOVSB   [228550]                MOV     AL,[ESI]   [142124]
  106.  
  107.                                          MOV     [EDI],AL
  108.  
  109.                                          INC     ESI
  110.  
  111.                                          INC     EDI
  112.  
  113.  
  114.  
  115.          MOVSD   [384379]                MOV     EAX,[ESI]  [324112]
  116.  
  117.                                          MOV     [EDI],EAX
  118.  
  119.                                          INC     ESI
  120.  
  121.                                          INC     EDI
  122.  
  123.  
  124.  
  125.  Of course, REP operations are faster than their equivalent by about half.
  126.  
  127.  In general, it is better to use MOV's and INC's to perform one off
  128.  
  129.  operations. So if you're coding with these instructions, chances are that
  130.  
  131.  you can get a bit more speed out of your code.
  132.  
  133.  
  134.  
  135.  Ok, now on with the main talk. Generally, I won't be going into great depth
  136.  
  137.  as there are plenty of tutorials and manuals on the net that explain the
  138.  
  139.  rank basics of assembly. My role here will be to highlight and familiarize
  140.  
  141.  extrordinary things about coding methods of assembly.
  142.  
  143.  
  144.  
  145.  If you've never coded in assembly, then it may pay you to write your
  146.  
  147.  equivalent program in a 3GL first and before converting it over. I guess it
  148.  
  149.  depends on the person. I prefer to implement idea's in straight assembler.
  150.  
  151.  I'm comfortable with the language enough to mumble it in my sleep and their
  152.  
  153.  are no barriers or contingencies like there are in 3GL code. You can also
  154.  
  155.  run into serious problems when converting to your target language, but I'm
  156.  
  157.  sure that there are as many negative points about doing this as they are
  158.  
  159.  positive points.
  160.  
  161.  
  162.  
  163.  How to crunch huge numbers
  164.  
  165.  --------------------------
  166.  
  167.  
  168.  
  169.  One of the first questions a new demo coder may ask is how he/she could
  170.  
  171.  add, multiply or subtract a number that is larger than the precision of the
  172.  
  173.  chip. Well, this really doesn't apply now, as the standard is 32 bits. This
  174.  
  175.  is ample for nearly all calculations, but for those of you that may want to
  176.  
  177.  perform a 64 bit ADD calculation, this is how you do it:
  178.  
  179.  
  180.  
  181.          ADD     EAX,ECX
  182.  
  183.          ADC     EDX,0
  184.  
  185.  
  186.  
  187.  In this example, we don't have a 64 bit register, therefore we must make
  188.  
  189.  two data sources, whether they be registers or memory references to act as
  190.  
  191.  one large register. In our case, EDX and EAX act as one. EAX contains the
  192.  
  193.  least significant data and the EDX contains the most significant data of
  194.  
  195.  our 64 bit number. ECX contains the number we are adding to this 64 bit
  196.  
  197.  concatenated register. The basic idea behind this is that we first add ECX
  198.  
  199.  to EAX. If the number in the EAX register "clocks" then the CPU's carry
  200.  
  201.  flag will be set.
  202.  
  203.  
  204.  
  205.  The next instruction - ADC (for those of you that don't know) is a funny
  206.  
  207.  sort of ADD instruction that performs two add instructions. It will first
  208.  
  209.  add the source register to the destination register, and then add 1 to the
  210.  
  211.  source register if the carry is set. Hence the name "ADD ON CARRY". In our
  212.  
  213.  example, if the carry flag is set, we will only add in the carry flag as
  214.  
  215.  the source value is zero. Therefore, if the least significant component of
  216.  
  217.  our 64 bit variable (EAX) clocks, the it will carry over to the EDX
  218.  
  219.  component.
  220.  
  221.  
  222.  
  223.  Although the above example only adds a 32 number to the 64 bit number. If
  224.  
  225.  you wanted to add a 64 bit number to a 64 number then you would adopt the
  226.  
  227.  following:
  228.  
  229.  
  230.  
  231.          ADD     EAX,ECX
  232.  
  233.          ADC     EDX,0
  234.  
  235.          ADD     EDX,EBX
  236.  
  237.  
  238.  
  239.  Where EDX:EAX is the destination 64 register, and EBX:ECX is the source
  240.  
  241.  register.
  242.  
  243.  
  244.  
  245.  To add larger precision's, we simply chain!. Here we are adding a 32 bit
  246.  
  247.  number that resides in EAX to a 128 bit number which is stored in
  248.  
  249.  EDX,EBX,ECX and ESI.
  250.  
  251.  
  252.  
  253.          ADD     EDX,EAX
  254.  
  255.          ADC     EBX,0
  256.  
  257.          ADC     ECX,0
  258.  
  259.          ADC     ESI,0
  260.  
  261.  
  262.  
  263.  To subtract, the same principle applies, accept we use SUB and SBB
  264.  
  265.  instructions:
  266.  
  267.  
  268.  
  269.          (a)                                     (b)
  270.  
  271.          SUB     EAX,ECX                         SUB     EAX,ECX
  272.  
  273.          SBB     EDX,0                           SBB     EDX
  274.  
  275.                                                  SUB     EDX,EBX
  276.  
  277.  
  278.  
  279.  With the 486's math coprocessor, the large multiplication and division is
  280.  
  281.  more viable than our old conventional way of calculating large numbers;
  282.  
  283.  which as you will see and very slow. Pretty soon, I will be exclusively
  284.  
  285.  using coprocessor calculations in my demos, as they are extremely popular
  286.  
  287.  now. Hence rendering the following code (for me) obsolete. However, for
  288.  
  289.  names sake, I'll discuss the old way of doing things...
  290.  
  291.  
  292.  
  293.  For multiplying a 64 bit variable to a 32 bit variable you can use this
  294.  
  295.  algorithm:
  296.  
  297.  
  298.  
  299.          MOV     EAX,ESI
  300.  
  301.          MUL     EBX
  302.  
  303.          PUSH    EAX EDX
  304.  
  305.          MOV     EAX,ESI
  306.  
  307.          MUL     ECX
  308.  
  309.          POP     ECX EBX
  310.  
  311.          ADD     ECX,EAX
  312.  
  313.  
  314.  
  315.  As a formula, the code is equivalent to this: ECX:EBX = ECX:EBX*ESI.
  316.  
  317.  
  318.  
  319.  Note that you can chain this one also by taking the EDX value from the
  320.  
  321.  second MUL and multiplying it by the next significant register of the
  322.  
  323.  source and adding that answer into the respective register of the
  324.  
  325.  destination.
  326.  
  327.  
  328.  
  329.  Dividing is a little bit more complex. How complex?...this complex:
  330.  
  331.  
  332.  
  333.          PROC LONG_DIV
  334.  
  335.            OR            EBP,EBX
  336.  
  337.            JZ            @@jump_0599
  338.  
  339.            PUSH          EBP
  340.  
  341.            MOV           EBP,ECX
  342.  
  343.            OR            EBX,EBX
  344.  
  345.            PUSHF
  346.  
  347.            JNS           @@jump_0548
  348.  
  349.            NOT           ECX
  350.  
  351.            NOT           EBX
  352.  
  353.            ADD           ECX,01
  354.  
  355.            ADC           EBX,00
  356.  
  357.          @@jump_0548:
  358.  
  359.            OR            EDX,EDX
  360.  
  361.            PUSHF
  362.  
  363.            JNS           @@jump_0557
  364.  
  365.            NOT           EAX
  366.  
  367.            NOT           EDX
  368.  
  369.            ADD           EAX,01
  370.  
  371.            ADC           EDX,00
  372.  
  373.          @@jump_0557:
  374.  
  375.            MOV           ESI,ECX
  376.  
  377.            MOV           EDI,EBX
  378.  
  379.            XOR           ECX,ECX
  380.  
  381.            XOR           EBX,EBX
  382.  
  383.            MOV           EBP,0021h
  384.  
  385.          @@jump_0562:
  386.  
  387.            RCL           ECX,1
  388.  
  389.            RCL           EBX,1
  390.  
  391.            SUB           ECX,ESI
  392.  
  393.            SBB           EBX,EDI
  394.  
  395.            JNB           @@jump_0570
  396.  
  397.            ADD           ECX,ESI
  398.  
  399.            ADC           EBX,EDI
  400.  
  401.          @@jump_0570:
  402.  
  403.            CMC
  404.  
  405.            RCL           EAX,1
  406.  
  407.            RCL           EDX,1
  408.  
  409.            DEC           EBP
  410.  
  411.            JNZ           @@jump_0562
  412.  
  413.            POPF
  414.  
  415.            JNS           @@jump_058A
  416.  
  417.            NOT           ECX
  418.  
  419.            NOT           EBX
  420.  
  421.            ADD           ECX,01
  422.  
  423.            ADC           EBX,00
  424.  
  425.            POPF
  426.  
  427.            JNS           @@jump_058D
  428.  
  429.            JMP           @@jump_0597
  430.  
  431.          @@jump_058A:
  432.  
  433.            POPF
  434.  
  435.            JNS           @@jump_0597
  436.  
  437.          @@jump_058D:
  438.  
  439.            NOT           EAX
  440.  
  441.            NOT           EDX
  442.  
  443.            ADD           EAX,0001
  444.  
  445.            ADC           EDX,00
  446.  
  447.          @@jump_0597:
  448.  
  449.            POP           EBP
  450.  
  451.          @@jump_0599:
  452.  
  453.            RET
  454.  
  455.          ENDP
  456.  
  457.  
  458.  
  459.  This formula divides EDX:EAX by EBX:ECX. Just in case anybody recognizes
  460.  
  461.  this thing, I've reversed it from a certain popular commercial package (not
  462.  
  463.  giving any names) hehe :). I havn't used it since my real mode days
  464.  
  465.  (which, for the record is about 2 years ago when coding TC669), and it's
  466.  
  467.  basically optimized for that. I've made no attempt to optimize it for
  468.  
  469.  P-mode, as I most likely will never use it ever again.
  470.  
  471.  
  472.  
  473.  How to implement a Decimal point (or rather - a hexadecimal point :)
  474.  
  475.  --------------------------------------------------------------------
  476.  
  477.  
  478.  
  479.  Now that we have discussed the ways in which we can do a whole range of
  480.  
  481.  calculations, your next question is how to implement floating/none discrete
  482.  
  483.  calculations. For that, we must take a register/memory unit and divide it
  484.  
  485.  into two parts. The number and a mantissa. For the sake of efficiency, you
  486.  
  487.  would typically contain this in a single register, namely a 32 bit
  488.  
  489.  register. I usually use this type of construct (represented in binary):
  490.  
  491.  
  492.  
  493.           /------------32 bits------------\
  494.  
  495.           NNNNNNNNNNNNNNNN.MMMMMMMMMMMMMMMM
  496.  
  497.  
  498.  
  499.  Here you have a 16 bit actual number, with a 16 bit mantissa. As you can
  500.  
  501.  see the actual number is of a higher order than normal. If to wanted to
  502.  
  503.  extract the number from this variable, you can simply perform a SHR 16.
  504.  
  505.  This will arrive you at the "NNN...." component of the number. Here is an
  506.  
  507.  example of 1 and a half:
  508.  
  509.  
  510.  
  511.          0000000000000001 1000000000000000b
  512.  
  513.  
  514.  
  515.  If we wanted the discrete part of the number (ie the "1" part), then just
  516.  
  517.  perform a SHR 16, which arrives us at: 0000000000000001. As you can see,
  518.  
  519.  there is no real difference between discrete and non-discrete variables. To
  520.  
  521.  the machine, it's all the same thing. The difference is the way you
  522.  
  523.  interpret the product. Calculations are still no different to normal
  524.  
  525.  numbers. If we wanted to add a "half" to this number then it's as simple
  526.  
  527.  that this:
  528.  
  529.  
  530.  
  531.     MOV     EAX,00000000000000010000000000000000b   ; this is a decimal "1"
  532.  
  533.  
  534.  
  535.     ADD     EAX,00000000000000001000000000000000b   ;this is a decimal "0.5"
  536.  
  537.  
  538.  
  539.  So, as you can see, it's not very hard. For multiplication, you're going to
  540.  
  541.  have to include a SHRD instruction, as the number will now be in EDX and
  542.  
  543.  the mantissa in EAX, hence the precision is now larger. This will return
  544.  
  545.  the number back to the EAX 32 bit precision that it should be. Here is an
  546.  
  547.  example:
  548.  
  549.  
  550.  
  551.          MUL             ECX
  552.  
  553.          SHRD            EDX,EAX,16
  554.  
  555.  
  556.  
  557.  Here, we multiply EAX by ECX, which arrives at EDX:EAX. Then we just step
  558.  
  559.  down this answer to arrive at the result, witch will now be contained in
  560.  
  561.  EAX. With division, it's the opposite:
  562.  
  563.  
  564.  
  565.          MOV             EDX,0
  566.  
  567.          SHLD            EDX,EAX,16
  568.  
  569.          DIV             ECX
  570.  
  571.  
  572.  
  573.  Here we are dividing EAX by ECX. Note the preparation just before the
  574.  
  575.  divide.
  576.  
  577.  
  578.  
  579.  Signed Data
  580.  
  581.  -----------
  582.  
  583.  
  584.  
  585.  As of now, we have only discussed unsigned data. Generally speaking, these
  586.  
  587.  calculations are very simular, but there are some major differences.
  588.  
  589.  
  590.  
  591.  Contained in a given 32 register, unsigned numbers go from 0 to FFFFFFFFh,
  592.  
  593.  where as 32 signed data range from 80000000h which is the lowest number and
  594.  
  595.  7FFFFFFFh begin the highest number. When using signed data, there are only
  596.  
  597.  a couple of extra things you must know. Signed data has its own
  598.  
  599.  multiplication and division instructions (ie IMUL and IDIV), and its own
  600.  
  601.  set of conditional jump instructions.
  602.  
  603.  
  604.  
  605.    JL (jump if less than) and JLE (jump if less than or equal to)
  606.  
  607.        are a signed equivalent to
  608.  
  609.    JB (jump if below)     and JBE (jump if below or equal to).
  610.  
  611.  
  612.  
  613.    JG (jump if greater)   and JGE (jump if greater than or equal to)
  614.  
  615.        are the signed equivalent to
  616.  
  617.    JA (jump if above)     and JAE (jump if above or equal to).
  618.  
  619.  
  620.  
  621.  To change our unsigned divider from this....
  622.  
  623.          MOV             EDX,0
  624.  
  625.          SHLD            EDX,EAX,16
  626.  
  627.          DIV             ECX
  628.  
  629.  
  630.  
  631.  ...To a signed divider, simply substitute the MOV EDX,0 with a CDQ. The CDQ
  632.  
  633.  extends a signed number in EAX into EDX. Example given:
  634.  
  635.  
  636.  
  637.          CDQ
  638.  
  639.          SHLD            EDX,EAX,16
  640.  
  641.          IDIV            ECX
  642.  
  643.  
  644.  
  645.  Implementing Complex mathematical relationships
  646.  
  647.  -----------------------------------------------
  648.  
  649.  
  650.  
  651.  At one time or another, a coder is going to have to use some sort of
  652.  
  653.  complex mathematical function like triangle ratios, logarithmic factors and
  654.  
  655.  random numbers to implement various things. To create a function that maps
  656.  
  657.  a relationship in real time is basically impossible in efficiently terms.
  658.  
  659.  The only way you can do this is to store relationships in the form of
  660.  
  661.  tables. This may not be apparent to users of compilers like turbo C etc but
  662.  
  663.  electronic calculators, compliers, maths coprocessors, spreadsheets all use
  664.  
  665.  this method of mapping these relationships. it a very fast a convenient way
  666.  
  667.  of doing things.
  668.  
  669.  
  670.  
  671.  The first common function is the random function. A random signal can be
  672.  
  673.  achieved using the following algorithm. The product of this function is a
  674.  
  675.  random number stored in the EAX register.
  676.  
  677.  
  678.  
  679.          ;input: NIL; output: EAX
  680.  
  681.          proc random
  682.  
  683.            mov  ebx,[random_seed1]
  684.  
  685.            lea  ebx,[ebx*4]
  686.  
  687.            mov  eax,[ebx+@@rantable]
  688.  
  689.            mov  ebx,[random_seed2]
  690.  
  691.            lea  ebx,[ebx*4]
  692.  
  693.            add  eax,[ebx+@@rantable]
  694.  
  695.            mov  [ebx+@@rantable],eax
  696.  
  697.            inc  [byte random_seed1]
  698.  
  699.            and  [byte random_seed1],01111b
  700.  
  701.            dec  [byte random_seed2]
  702.  
  703.            and  [byte random_seed2],01111b
  704.  
  705.            ret
  706.  
  707.          random_seed1
  708.  
  709.            dd    2
  710.  
  711.          random_seed2
  712.  
  713.            dd    13
  714.  
  715.          @@rantable:
  716.  
  717.            dd 0fd8fce7ah,02d7ad7b7h,0f48a8f3ab,04a3b8f8bh
  718.  
  719.            dd 0f2dec542h,0a847fab7h,0f4da81aab,04a348f86h
  720.  
  721.            dd 024547edah,03b535a43h,0b35a535ab,0aa333483h
  722.  
  723.            dd 0fd2f4e7ah,0c525a5b7h,016d3b4a4b,0643b4fd3h
  724.  
  725.          endp
  726.  
  727.  
  728.  
  729.  If you expand the table to 256 entries then you could eliminate two
  730.  
  731.  instructions, but there again, it's not worth doing. This random function
  732.  
  733.  will give you a very random signal :). There is only one problem with this
  734.  
  735.  algorithm, and that is, the randomness will always follow the same pattern.
  736.  
  737.  If this feature undesirable, then you may like to make an initiation module
  738.  
  739.  that jumbles up the seeds or the numbers a bit. An obvious way of randomly
  740.  
  741.  choosing a seed, would be to store a fixed reference variable in memory.
  742.  
  743.  For example:
  744.  
  745.  
  746.  
  747.          proc randomise
  748.  
  749.            mov  al,[043253445h]
  750.  
  751.            mov  [byte random_seed1],al
  752.  
  753.            mov  al,[012345678h]
  754.  
  755.            mov  [byte random_seed2],al
  756.  
  757.            ret
  758.  
  759.          endp
  760.  
  761.  
  762.  
  763.  Anyway, I'm going to stop here as it's getting very close the deadline
  764.  
  765.  time. One day, I'll learn not to leave things till last minute. In the next
  766.  
  767.  part, I'll be hopefully finishing up this assembly series and moving on to
  768.  
  769.  my talks of sound/tracker programming (the interesting stuff).
  770.  
  771.  
  772.  
  773.  I'll be soon releasing a tracker that I have written called FunkTracker.
  774.  
  775.  With this will be the full source code listing. My discussions will be
  776.  
  777.  based around my knowledge and experience when producing current and past
  778.  
  779.  trackers and players, and discussing implementation and hardware issues. I
  780.  
  781.  also plan to discuss reverse engineering using microsoft CodeView, and plan
  782.  
  783.  to obtain hack docs on the AWE32 card. So this will be all coming up!.
  784.  
  785.  until next time.
  786.  
  787.  
  788.  
  789.  See ya
  790.  
  791.  :Jason Nunn
  792.  
  793.  
  794.  
  795.  
  796.  
  797. _____BSP Trees by Tom Verbeure
  798.  
  799.  
  800.  
  801.  Problem situation: sorting polygons is slow and can be incorrect for
  802.  
  803.  certain view-angles. Heavily influenced by Computer Graphics, Principles
  804.  
  805.  and Practice, I have written this small tutorial for BSP trees, which
  806.  
  807.  solves the problem for static objects and for every view angle.
  808.  
  809.  
  810.  
  811.  As I already said: Binary Space Partitioning Tree. Unlike many other
  812.  
  813.  abbreviations, this one really explains a lot of the algorithm: it uses a
  814.  
  815.  tree. It partitions space and it partitions in two parts.
  816.  
  817.  
  818.  
  819.  First: it is only usefull in static scenes: no 3D morphing or other goodies
  820.  
  821.  are allowed.
  822.  
  823.  
  824.  
  825.  Let's go to the 2D case, 3D is exactly the same.
  826.  
  827.  Take a sample scene:
  828.  
  829.  
  830.  
  831.          A\        -----   C|
  832.  
  833.            \   B       E    |
  834.  
  835.            ------   |
  836.  
  837.                  |
  838.  
  839.             /     .
  840.  
  841.            /      V
  842.  
  843.          D/
  844.  
  845.  
  846.  
  847.  The positive side of the polygons is the side with the defining
  848.  
  849.  character... Ignore V for now.
  850.  
  851.  
  852.  
  853.  One could sort this thing during rendering, but as there can be no correct
  854.  
  855.  sort criterium and sorting is slow, we don't want that. Besides, we have
  856.  
  857.  memory to spare :-)
  858.  
  859.  
  860.  
  861.  Now, we're going to build a tree that is totally viewpoint independent:
  862.  
  863.  
  864.  
  865.  Take polygon B as the root. Polygon B divides space in to parts: the
  866.  
  867.  positive and the negative side (Geee!) We have partitoned space in two.
  868.  
  869.  
  870.  
  871.  First, scrap B from the 'not-used' polygons-array and classify the
  872.  
  873.  remaining polygons. Group those on the + side, and those on the - side. As
  874.  
  875.  you can see, polygon C is both on the + and the - side. What to do? Create
  876.  
  877.  2 new polygons C+ and C-, erase C. Is there another complainer ? Nope: all
  878.  
  879.  poly's are on either the + or the - side. Now we have this situation:
  880.  
  881.  
  882.  
  883.                 B
  884.  
  885.                    / \
  886.  
  887.              A,C+,E       D,C-
  888.  
  889.  
  890.  
  891.  Not really a tree yet, but we've only started...
  892.  
  893.  
  894.  
  895.  Now, do the same thing for the groups at the child nodes, without caring
  896.  
  897.  about those in another child-node.
  898.  
  899.  
  900.  
  901.  For the + side of B, we have polys A,C+ and E. Take A as next node polygon.
  902.  
  903.  Neither C+ nor E are on it's negative side (we ignore D and C-). For the
  904.  
  905.  other node, take D as next node polygon. Only C- remains there, and it is
  906.  
  907.  on the negative side. That side of the tree is finished. We have the
  908.  
  909.  following situation:
  910.  
  911.  
  912.  
  913.                 B
  914.  
  915.                    / \
  916.  
  917.                   /   \
  918.  
  919.                  A     D
  920.  
  921.                   \     \
  922.  
  923.                  C+,E    C-
  924.  
  925.  
  926.  
  927.  There's one child with more that one poly left. Take C+ as node polygon, E
  928.  
  929.  become it's child, on the positive side. We're finished.
  930.  
  931.  Situation:
  932.  
  933.  
  934.  
  935.                 B
  936.  
  937.                    / \
  938.  
  939.                   /   \
  940.  
  941.                  A     D
  942.  
  943.                   \     \
  944.  
  945.                    C+    C-
  946.  
  947.                   /
  948.  
  949.                  E
  950.  
  951.  
  952.  
  953.  Now, what can we do with it? A lot... Suppose the viewpoint is at position
  954.  
  955.  V. In which order do we have to sort the polygons, when using a back to
  956.  
  957.  front rendering algorithm ? Answer: walk the tree, make sure all nodes
  958.  
  959.  (including childs) are visited.
  960.  
  961.  
  962.  
  963.  Start at the root. Is V on the positive side? Nope, well, we want the polys
  964.  
  965.  far away first, so walk the positive way. Are we on the positive side of A?
  966.  
  967.  Yep, walk the negative way. It is empty! Ah. Well, draw A first. The go the
  968.  
  969.  positive way. Are we positive of C+? Yep. Negative way of C+ is empty. Draw
  970.  
  971.  C+ poly. Go positive way of C+. E has no child, draw it. Go up until a
  972.  
  973.  non-empty branch is found, draw all node polygon not drawn already. We now
  974.  
  975.  arrive at B again. Draw it. Negative is not visited yet, walk it. We're
  976.  
  977.  negative of D. Positive way is empty. Draw D and go negative. C- has no
  978.  
  979.  child. Draw it. All nodes have been visited. The end.
  980.  
  981.  
  982.  
  983.  We have drawn the polygons in following order:
  984.  
  985.  
  986.  
  987.  A, C+, E, B, D, C- which is a correct order. The BSP tree has to be
  988.  
  989.  constructed only once and for all. From then on, sorting the polygons is
  990.  
  991.  always correct and in linear time. Standard sorting algorithms can be
  992.  
  993.  proved to be of n*log(n) order of time, so we have an increase in speed as
  994.  
  995.  well.
  996.  
  997.  
  998.  
  999.  Disadvantages:
  1000.  
  1001.  
  1002.  
  1003.  - Memory: one has to have the tree in memory. This can be substantial for
  1004.  
  1005.        lots of polygons.
  1006.  
  1007.  - Polygon splitting: one ends up with more split polygons. It is almost
  1008.  
  1009.        always unavoidable to do splitting.
  1010.  
  1011.  - Polygons are not allowed to move.
  1012.  
  1013.  
  1014.  
  1015.  A BSP tree is NOT unique: just pick another polygon as a node and one gets
  1016.  
  1017.  a different one. In this case, one can avoid splitting polygons: start with
  1018.  
  1019.  a root and build the following, correct, BSP tree:
  1020.  
  1021.  
  1022.  
  1023.             C
  1024.  
  1025.                /
  1026.  
  1027.               B
  1028.  
  1029.              / \
  1030.  
  1031.             A   D
  1032.  
  1033.            /
  1034.  
  1035.           E
  1036.  
  1037.  
  1038.  
  1039.  Tadaam! No polygon splitting!
  1040.  
  1041.  
  1042.  
  1043.  Building a tree with a few splitting as possible is an exponential of the
  1044.  
  1045.  number of polygons. As Foley and Van Dam says, just try a limited number of
  1046.  
  1047.  nodepolygons, pick the one with the least splitting and the tree will be
  1048.  
  1049.  good enough.
  1050.  
  1051.  
  1052.  
  1053.  Voila. That's it. Not too difficult I think. Notice BSP trees are also
  1054.  
  1055.  usefull to sort objects, by using planes that divide the space in such a
  1056.  
  1057.  way that Object A is on the negative and Object B is on the positive side
  1058.  
  1059.  of the plane. Very useful (only for non-intersecting objects).
  1060.  
  1061.  
  1062.  
  1063.  This text is written without the Bible (Computer Graphics, P&P) besides me,
  1064.  
  1065.  but since I read their chapter about BSP trees many times, it contains
  1066.  
  1067.  almost the same info.
  1068.  
  1069.  
  1070.  
  1071.  For polygon splitting algorithmes, there is one in Graphics Gems. I don't
  1072.  
  1073.  know which one, but buy all four books, you won't be disappointed... :-)
  1074.  
  1075.  
  1076.  
  1077.  Tom Verbeure
  1078.  
  1079.  Synergy Design
  1080.  
  1081.  
  1082.  
  1083. .,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,
  1084.  
  1085.  
  1086.  
  1087.  <<Back Issues>>
  1088.  
  1089.  
  1090.  
  1091. ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  1092.  
  1093.  
  1094.  
  1095. _____How to Get 'em
  1096.  
  1097.  
  1098.  
  1099.  After reading this issue of DemoNews, you may be wondering how you can get
  1100.  
  1101.  previous ones.  Well fear not!  There are two different ways to do so:
  1102.  
  1103.  
  1104.  
  1105.  1: FTP to hornet.eng.ufl.edu and go to /pub/msdos/demos/news/OLD_NEWS and
  1106.  
  1107.     start downloading anything you see.
  1108.  
  1109.  
  1110.  
  1111.  2: Now you can request back issues of DemoNews via e-mail.  Start a letter
  1112.  
  1113.     to listserver@oliver.sun.ac.za (any subject line) and in the body of the
  1114.  
  1115.     letter include "get demuan-list <index>" where INDEX refers to the
  1116.  
  1117.     index number of the issue.
  1118.  
  1119.  
  1120.  
  1121.     For example:  get demuan-list 43
  1122.  
  1123.  
  1124.  
  1125.     This would retrieve DemoNews #76 (part 1 of 2).
  1126.  
  1127.  
  1128.  
  1129.     For more recent issues that are split into multiple parts, you must send
  1130.  
  1131.     an individual request for each index number.
  1132.  
  1133.  
  1134.  
  1135. _____Descriptions
  1136.  
  1137.  
  1138.  
  1139. Issue  Index  Date      Size    Description
  1140.  
  1141. -----  -----  --------  ------  ----------------------------------------------
  1142.  
  1143.   75   41,42  12/18/94   68009  A DemoNews Reader, The Birth of Commercial
  1144.  
  1145.                                 Life, Editorial: Calm Before the Storm,
  1146.  
  1147.                                 Interview with Mello-D, US Demo Scene
  1148.  
  1149.                                 (Renaissance meeting), Jelly Tots and Pizza
  1150.  
  1151.                                 Shops, Review of Wired '94 Graphics.
  1152.  
  1153.  
  1154.  
  1155.   76   43,44  12/25/94   92589  Interview with EMF, DemoNews Readers Write,
  1156.  
  1157.                                 Kimba's Life Story, X-Mas in the Demo Scene,
  1158.  
  1159.                                 CORE, Demo & Music Database, Interview with
  1160.  
  1161.                                 Purple Motion/Future Crew, Interview with
  1162.  
  1163.                                 Krystall/Astek, Common Sense ][ by Perisoft,
  1164.  
  1165.                                 Its X-Mas in Africa, Interview with Maxwood
  1166.  
  1167.                                 of Majic 12, Assembly Part ][, Common Sense
  1168.  
  1169.                                 Response by Stony.
  1170.  
  1171.  
  1172.  
  1173.   77   45,46  01/01/95  101100  Chart History, Snowman Near-Disaster, Son of
  1174.  
  1175.                                 Snowman, The Party 1994, Making Waves, Using
  1176.  
  1177.                                 Assembly Part 2.
  1178.  
  1179.  
  1180.  
  1181.   78   47-49  01/08/95  111185  The Party 1994: Results and Reviews, Report
  1182.  
  1183.                                 by Stony and Friends, What happened to PC-
  1184.  
  1185.                                 Demo competition.  Editorial: TP94 = ASM94
  1186.  
  1187.                                 part 2.  Egg2: Trancescrambled Review, More
  1188.  
  1189.                                 on Fast Tracker 2.03.  General Rambling by
  1190.  
  1191.                                 Denthor.
  1192.  
  1193.  
  1194.  
  1195.   79   51     01/15/95   41832  A Day in the Life of Snowman, Ambient Sample
  1196.  
  1197.                                 CD 1, Where's the Sound Blaster, TP94
  1198.  
  1199.                                 Graphics review.
  1200.  
  1201.  
  1202.  
  1203.   80   55     01/22/95   27028  DemoNews/HTML, Traffic Jam, CodeThink(School);
  1204.  
  1205.                                 The Solo Sample CD
  1206.  
  1207.  
  1208.  
  1209. .,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,
  1210.  
  1211.  
  1212.  
  1213.  <<Closing Comments>>
  1214.  
  1215.  
  1216.  
  1217. ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  1218.  
  1219.  
  1220.  
  1221.  The quote this week comes from "Assembly Language for the PC, Third
  1222.  
  1223.  Edition". p.174
  1224.  
  1225.  
  1226.  
  1227.     "A program is never done...but it must be stopped somewhere."
  1228.  
  1229.  
  1230.  
  1231.  This was intended as a moral for programmers, but with a little rewording
  1232.  
  1233.  the message is applicable to many areas in life.
  1234.  
  1235.  
  1236.  
  1237.  See you in CyberSpace,
  1238.  
  1239.  
  1240.  
  1241.                         -Christopher G. Mann (Snowman)-
  1242.  
  1243.                             r3cgm@dax.cc.uakron.edu
  1244.  
  1245.  
  1246.  
  1247. ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,End.of.DemoNews.081.
  1248.  
  1249.  
  1250.  
  1251.