home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_02_03 / 2n03047a < prev    next >
Text File  |  1991-01-15  |  15KB  |  532 lines
  1.  
  2. ;-------------------------------------------------------------------
  3. ; BEZ.ASM -- Logic to quickly compute the points along a bezier curve.
  4. ;
  5. ;      Assembly :  TASM BEZ;
  6. ;
  7. ;      Should be linked with Turbo-C V2.0 small memory model.
  8. ;
  9. ; Author : Bob Zigon
  10. ; Date   : July 23, 1989
  11. ;-------------------------------------------------------------------
  12.  
  13. ;
  14. ; NOTE : This code is assembled with the .287 directive to avoid the 
  15. ;        generation of the unnecessary FWAITS on an AT or '386 class 
  16. ;        machine. If this code is to be executed on an 8087, the
  17. ;       .287 directive must be commented out.
  18. ;
  19.         .287
  20.  
  21.         dosseg
  22.         .model small
  23.  
  24. ;-------------------------------------------------------------------
  25. ;                          EQUATES
  26. ;-------------------------------------------------------------------
  27. MaxControl   equ 10               ; Max number of control points
  28. MaxDivisions equ 151              ; Max number of divisions for t
  29.  
  30. ;-------------------------------------------------------------------
  31. ;                        VARIABLE DECLARATIONS
  32. ;-------------------------------------------------------------------
  33.         .data
  34.         extrn _XvpMin:word,_XvpMax:word,_YvpMin:word,_YvpMax:word
  35.         extrn _XCpMin:qword,_XCpMax:qword,_YCpMin:qword,_YCpMax:qword
  36.         extrn _XCpScr:word,_YCpScr:word,_XCp:qword,_YCp:qword
  37.         extrn _XCurve:qword,_YCurve:qword
  38.  
  39. K1        dq ?                      ; Coefficient for transforming X
  40. Q1        dq ?
  41. K2        dq ?                      ; Coefficient for transforming Y
  42. Q2        dq ?
  43.  
  44. T         dq MaxControl dup (?)
  45. BCoef     dq MaxControl dup (?)     ; Double Prec array of Binomial Coefficients
  46. OneMinusT dq MaxControl dup (?)
  47. NumTerms  dw ?                      ; Number of terms in the summations
  48.  
  49.         .code
  50.         public _Binomial, _BezierToScreen, _WToVConst
  51.         public XformWXtoScr, XformWYtoScr
  52.  
  53. ; -------------------------------------------------------------------
  54. ; Binomial  -- This routine precomputes the table of binomial coefficients
  55. ;              for a given number of control points.
  56. ;
  57. ;    The table of N coefficients is computed according to the
  58. ; following recursive formula :
  59. ;
  60. ;         N       N-1       N-1
  61. ;        C   =  C      +  C
  62. ;         i       i         i-1
  63. ; 
  64. ; C Prototype :
  65. ;
  66. ;        void Binomial(short int NumControl)
  67. ;
  68. ; Input    : 4[BP] -- Number of control points > 1
  69. ; Output   : The BCoef array is filled with the coefficients.
  70. ; -------------------------------------------------------------------
  71. NumControl  equ  4[bp]
  72.  
  73. _Binomial proc near
  74.       push bp
  75.       mov bp,sp
  76.       push si
  77.       push di                     ; Save in case Register Variables = ON
  78.  
  79.       mov ax,NumControl
  80.       mov NumTerms,ax
  81. ;
  82. ; Begin by initializing the BCoef array to
  83. ;
  84. ;   1.0   0  0  0 .... 0
  85. ;         <--- N-1 ---->
  86. ;
  87.       fld1
  88.       fstp qword ptr BCoef        ; Store the 1.0
  89.       fwait
  90.       lea di,BCoef+8
  91.       mov cx,ax
  92.       dec cx
  93.       shl cx,1
  94.       shl cx,1
  95.       cld
  96.       xor ax,ax
  97.       push ds
  98.       pop es                      ; Init ES for the STOSW
  99.       rep stosw                   ; Now store lots of Zeros
  100.  
  101.       mov ax,NumTerms
  102.       cmp ax,MaxControl           ; Number of control points > Number allocated?
  103.       jle Bi10
  104.          xor ax,ax
  105.          mov NumTerms,ax
  106.          jmp short Bi80
  107. ;
  108. ; Now begin the recursive generation of the BCoef array in situ.
  109. ;
  110. ; The equivalent C code is :
  111. ;
  112. ;    for (j = 1; j < NumTerms; j++)
  113. ;    {
  114. ;       Last = 0.0
  115. ;       for (k = 0; k<=j; k++)
  116. ;       {
  117. ;          Temp     = BCoef[k]+Last
  118. ;          Last     = BCoef[k]
  119. ;          BCoef[k] = Temp
  120. ;       }
  121. ;    }
  122. ;
  123.  
  124. Bi10: mov ax,1                    ; AX is j
  125. Bi20: cmp ax,NumTerms
  126.       je Bi80
  127.          fldz                     ; Last is on the stack
  128.          xor bx,bx                ; BX is k
  129.          lea di,BCoef
  130. Bi30:    cmp bx,ax
  131.          ja Bi40
  132.             fld qword ptr [di]    ; Load BCoef[k]
  133.             fld st                ; Duplicate top of stack
  134.             fadd st,st(2)         ; Temp = BCoef[k]+Last
  135.             fxch                  ; Temp <-> BCoef[k]
  136.             fstp st(2)            ; Store BCoef[k] to Last and pop
  137.             fstp qword ptr [di]   ; Store Temp out to BCoef[k]
  138.             add di,8              ; Adv to next BCeof
  139.             inc bx
  140.             jmp Bi30
  141. Bi40:    fstp st                  ; Clean up the coprocessor stack
  142.          fwait
  143.          inc ax
  144.       jmp Bi20
  145.  
  146. Bi80: pop di
  147.       pop si
  148.       mov sp,bp                   ; Pop of the local variables
  149.       pop bp                      ; Reset BP
  150.       ret
  151. _Binomial endp
  152.  
  153. ; -------------------------------------------------------------------
  154. ; _BezierToScreen -- Compute the points along the Bezier curve and
  155. ;                    transform them to screen coordinates.
  156. ;
  157. ; C Prototype :
  158. ;
  159. ;    void BezierToScreen(short int, short int, short int *, short int *)
  160. ;
  161. ; Input  :  4[BP] -- Number of divisions of the parameter
  162. ;           6[BP] -- Number of Control Points
  163. ;           8[bp] -- Ptr to X Screen Coordinates
  164. ;          10[bp] -- Ptr to Y Screen Coordinates
  165. ;
  166. ; Output : The array of X and Y screen coordinates.
  167. ; -------------------------------------------------------------------
  168. TDivisions   equ 4[bp]
  169. NP           equ 6[bp]
  170. XV           equ 8[bp]
  171. YV           equ 10[bp]
  172.  
  173. _BezierToScreen proc near
  174.       local u:qword,du:qword
  175.       local XCurvePtr:word,YCurvePtr:word
  176.       local NumCurvePts:word=AutoSize
  177.       push bp
  178.       mov bp,sp
  179.       sub sp,AutoSize             ; Allocate some local variables
  180.       push si
  181.       push di                     ; Save in case Register Variables = ON
  182.  
  183.       mov ax,NP
  184.       lea si,_XCp
  185.       lea di,_XCpScr
  186.       call XformWXtoScr           ; Convert XCp to screen coordinates
  187.  
  188.       mov ax,NP
  189.       lea si,_YCp
  190.       lea di,_YCpScr
  191.       call XformWYtoScr           ; Convert YCp to screen coordinates
  192. ;
  193. ; Now, compute the coordinates of the curve.
  194. ;
  195.       mov ax,word ptr TDivisions
  196.       inc ax
  197.       mov NumCurvePts,ax          ; Number of points on the curve
  198.  
  199.       fld1
  200.       fidiv word ptr TDivisions
  201.       fstp du                     ; du = 1/TDivisions
  202.       fldz
  203.       fstp u                      ; u = 0.0
  204.       fwait
  205.       lea ax,_XCurve
  206.       mov XCurvePtr,ax
  207.       lea ax,_YCurve
  208.       mov YCurvePtr,ax
  209.  
  210. ;
  211. ; Since the address of _XCp and _YCp doesn't change, why push them
  212. ; on the stack every time you need to call Bezier. Push them
  213. ; once here, and clean up on exit.
  214. ;
  215.       lea ax,_YCp
  216.       push ax
  217.       lea ax,_XCp
  218.       push ax
  219.  
  220. BS10: mov ax,NumCurvePts
  221.       or ax,ax                    ; EXIT when no more points to compute
  222.       jz BS20
  223.          mov ax, word ptr u+6
  224.          push ax
  225.          mov ax, word ptr u+4
  226.          push ax
  227.          mov ax, word ptr u+2
  228.          push ax
  229.          mov ax, word ptr u
  230.          push ax
  231.  
  232.          call Bezier              ; Compute X(t) and Y(t)
  233.          add sp,2*4               ; Pop the t parameter
  234.  
  235.          mov si,YCurvePtr
  236.          fstp qword ptr [si]      ; Save and pop Y(t)
  237.          add si,8
  238.          mov YCurvePtr,si
  239.  
  240.          mov si,XCurvePtr
  241.          fstp qword ptr [si]      ; Save and pop X(t)
  242.          add si,8
  243.          mov XCurvePtr,si
  244.  
  245.          fld u
  246.          fadd du
  247.          fstp u                   ; Increment u by du
  248.          fwait
  249.  
  250.          dec NumCurvePts          ; 1 less point to consider
  251.       jmp short BS10
  252.  
  253.  
  254. BS20: add sp,2*2                  ; Pop address of _XCp and _YCp
  255.       mov ax,TDivisions
  256.       inc ax
  257.       lea si,_XCurve
  258.       mov di,XV
  259.       call XformWXtoScr           ; Convert X curve values to screen coordinates
  260.  
  261.       mov ax,TDivisions
  262.       inc ax
  263.       lea si,_YCurve
  264.       mov di,YV
  265.       call XformWYtoScr           ; Convert Y curve values to screen coordinates
  266.  
  267.       pop di
  268.       pop si
  269.       mov sp,bp                   ; Pop of the local variables
  270.       pop bp                      ; Reset BP
  271.       ret
  272. _BezierToScreen endp
  273.  
  274. ; -------------------------------------------------------------------
  275. ; XformWXtoScr -- transform world X coordinates to X screen coordinates.
  276. ;
  277. ; Input  :  AX -- Number of points
  278. ;           SI -- Ptr to Double Precision World X values
  279. ;           DI -- Ptr to Word Screen X values
  280. ;
  281. ; Transform is :
  282. ;
  283. ;   X' = Q1 + K1*X
  284. ;
  285. ;   K1 = (XvpMax-XvpMin)/(XCpMax-XCpMin)
  286. ;   Q1 = XvpMin - K1*XCpMin
  287. ;
  288. ; -------------------------------------------------------------------
  289. XformWXtoScr proc near
  290.       fld Q1
  291.       fld K1
  292. XFX10:
  293.       or ax,ax
  294.       jz XFX20                    ; Exit when AX = 0
  295.          fld st                   ; Dup the top of stack
  296.          fmul qword ptr [si]      ; X*K
  297.          add si,8
  298.          fadd st,st(2)            ; X*K+Q
  299.          fistp word ptr [di]      ; Store the Screen coordinate
  300.          add di,2
  301.          dec ax                   ; 1 less point to consider
  302.       jmp short XFX10
  303.  
  304. XFX20:
  305.       fstp st
  306.       fstp st                     ; Clean up the stack
  307.       ret
  308. XformWXtoScr endp
  309.  
  310. ; -------------------------------------------------------------------
  311. ; XformWYtoScr -- transform world Y coordinates to Y screen coordinates.
  312. ;
  313. ; Input  :  AX -- Number of points
  314. ;           SI -- Ptr to Double Precision World Y values
  315. ;           DI -- Ptr to Word Screen Y values
  316. ;
  317. ; Transform is :
  318. ;
  319. ;   Y' = Q2 - K2*Y
  320. ;
  321. ;   K2 = (YvpMax-YvpMin)/(YCpMax-YCpMin)
  322. ;   Q2 = K2*YCpMax + YsMin
  323. ;
  324. ; Note : Since the screen values for Y start in the upper left hand
  325. ;        corner instead of the lower left hand corner, this routine
  326. ;        inverts the Y coordinate.
  327. ; -------------------------------------------------------------------
  328. XformWYtoScr proc near
  329.       fld Q2
  330.       fld K2
  331. XFY10:
  332.       or ax,ax
  333.       jz XFY20                    ; Exit when AX = 0
  334.          fld st                   ; Dup the top of stack
  335.          fmul qword ptr [si]      ; Y*K
  336.          add si,8
  337.          fsubr st,st(2)           ; Q-Y*K
  338.          fistp word ptr [di]
  339.          add di,2
  340.          dec ax                   ; 1 less point to consider
  341.       jmp short XFY10
  342.  
  343. XFY20:
  344.       fstp st
  345.       fstp st                     ; Clean up the stack
  346.       ret
  347. XformWYtoScr endp
  348.  
  349. ; -------------------------------------------------------------------
  350. ; WToVConst -- Calculate the constants used to perform the window
  351. ;              to viewport transformations in XformWXtoScr and
  352. ;              XformWYtoScr.
  353. ;
  354. ; C Prototype :
  355. ;
  356. ;     void WToVConst(void);
  357. ;
  358. ; -------------------------------------------------------------------
  359. _WToVConst proc near
  360.      fild _XvpMax
  361.      fisub _XvpMin
  362.      fld _XCpMax
  363.      fsub _XCpMin
  364.      fdiv
  365.      fst K1                  ; K1 = (XvpMax-XvpMin)/(XCpMax-XCpMin)
  366.      fmul _XCpMin
  367.      fisubr _XvpMin
  368.      fstp Q1                 ; Q1 = XvpMin - K1*XCpMin
  369.  
  370.      fild _YvpMax
  371.      fisub _YvpMin
  372.      fld _YCpMax
  373.      fsub _YCpMin
  374.      fdiv
  375.      fst K2                  ; K2 = (YvpMax-YvpMin)/(YCpMax-YCpMin)
  376.      fmul _YCpMax
  377.      fiadd _YvpMin
  378.      fstp Q2                 ; Q2 = K2*YcpMax + YvpMin
  379.      ret
  380. _WToVConst endp
  381.  
  382. ; -------------------------------------------------------------------
  383. ; Bezier -- local subroutine used to compute the actual value of
  384. ;              X(t) and Y(t).
  385. ;
  386. ; Input  :  4[BP] -- Double Precision value of t, the parameter
  387. ;        : 12[BP] -- Ptr to X Control Points.
  388. ;          14[bp] -- Ptr to Y Control Points.
  389. ;
  390. ; Output : ST(1) -- Double Precision X when the polynomial is
  391. ;                      evaluated at t and the X Control Points.
  392. ;          ST(0) -- Double Precision Y when the polynomial is
  393. ;                      evaluated at t and the Y Control Points.
  394. ; -------------------------------------------------------------------
  395. ParamT   equ qword ptr 4[bp]
  396. XCp      equ 12[bp]
  397. YCp      equ 14[bp]
  398.  
  399. Bezier proc near
  400.       push bp
  401.       mov bp,sp
  402.  
  403.       lea di,T
  404.       mov ax,NumTerms
  405.       mov bx,ax
  406. ;
  407. ; Compute the T array.
  408. ;
  409. ; 1   T   T**2   T**3   T**4    T**5 ....
  410. ;
  411.       fld ParamT
  412.       fld1
  413. B10:     fst qword ptr [di]
  414.          dec ax
  415.          or ax,ax
  416.          jz B50                   ; EXIT when AX = 0
  417.          fmul st,st(1)
  418.          add di,8
  419.       jmp B10
  420.  
  421. B50:  fstp st                     ; Clean up the stack
  422.       fstp st
  423.       lea di,OneMinusT
  424. ;
  425. ; Compute the OneMinusT array.
  426. ;
  427. ; 1   1-T   (1-T)**2   (1-T)**3   (1-T)**4    (1-T)**5 ....
  428. ;
  429.       fld1
  430.       fld ParamT
  431.       fsub
  432.       fld1
  433. B60:     fst qword ptr [di]
  434.          dec bx
  435.          or bx,bx
  436.          jz B70                   ; EXIT when BX = 0
  437.          fmul st,st(1)
  438.          add di,8
  439.       jmp B60
  440.  
  441. B70:  lea di,T
  442.       fst qword ptr [di]          ; Copy (1-T)**N to T**0
  443.       fstp st
  444.       fstp st
  445. ;
  446. ; Now multiply the T array by the OneMinusT array.
  447. ;
  448.       add di,8
  449.       mov ax,NumTerms
  450.       sub ax,2
  451.       mov bl,8
  452.       mul bl
  453.       lea si,OneMinusT
  454.       add si,ax                   ; SI points to (1-T)**(N-1)
  455.  
  456.       mov ax,NumTerms
  457.       sub ax,2
  458.  
  459. B80:  or ax,ax
  460.       jz B90
  461.          fld qword ptr [si]      ; Get element from 1-T
  462.          fmul qword ptr [di]     ; Multiply by T**i
  463.          fstp qword ptr [di]     ; Save product back to T
  464.          sub si,8
  465.          add di,8
  466.          dec ax
  467.       jmp B80
  468.  
  469. ;
  470. ; Now form the term by term product of the T array and the BCoef array.
  471. ;
  472. B90:  lea si,T
  473.       lea di,BCoef
  474.       mov ax,NumTerms
  475.  
  476. B100: or ax,ax
  477.       jz B120
  478.          fld qword ptr [si]       ; Get a T element
  479.          fmul qword ptr [di]      ; Multiply by a binomial coefficient
  480.          fstp qword ptr [si]
  481.          add si,8
  482.          add di,8
  483.          dec ax
  484.       jmp B100
  485.  
  486. ;
  487. ; Now that the T array has the product of the T array, the OneMinusT array,
  488. ;   and the Binomial coefficients, form the dot product of the T array
  489. ;   with the XCp array to produce X(t).
  490. ;
  491. B120: lea si,T
  492.       mov di,XCp
  493.       mov ax,NumTerms
  494.       fldz
  495.  
  496. B200: or ax,ax
  497.       jz B210
  498.          fld qword ptr [si]       ; Load a term from T
  499.          fmul qword ptr [di]      ; Multiply by an XCp
  500.          faddp                    ; Accumulate in stack top
  501.          add si,8
  502.          add di,8
  503.          dec ax
  504.       jmp B200
  505.  
  506. B210:
  507. ;
  508. ;   Now form the dot product of the T array with the YCp array to
  509. ;   produce Y(t).
  510. ;
  511.       lea si,T
  512.       mov di,YCp
  513.       mov ax,NumTerms
  514.       fldz
  515.  
  516. B220: or ax,ax
  517.       jz B230
  518.          fld qword ptr [si]       ; Load a term from T
  519.          fmul qword ptr [di]      ; Multiply by an YCp
  520.          faddp                    ; Accumulate in stack top
  521.          add si,8
  522.          add di,8
  523.          dec ax
  524.       jmp B220
  525.  
  526. B230:
  527.       mov sp,bp                   ; Pop of the local variables
  528.       pop bp                      ; Reset BP
  529.       ret
  530. Bezier endp
  531.        end
  532.