home *** CD-ROM | disk | FTP | other *** search
/ Virtual Reality Homebrewer's Handbook / vr.iso / vr386 / objrend.asm < prev    next >
Assembly Source File  |  1996-03-19  |  11KB  |  544 lines
  1.     TITLE    OBJREND - RENDERER SUPPORT MATH IN ASSEMBLER
  2.  
  3.     COMMENT $
  4.  
  5. // 26/12/93 by Dave Stampe
  6. // All algorithms and code (c) 1993 by Dave Stampe
  7.  
  8. /*
  9.  This code is part of the REND386 project, created by Dave Stampe and
  10.  Bernie Roehl.
  11.  
  12.  Copyright 1992, 1993, 1994 by Dave Stampe and Bernie Roehl.
  13.  
  14.  May be freely used to write software for release into the public domain;
  15.  all commercial endeavours MUST contact BOTH Bernie Roehl and Dave Stampe
  16.  for permission to incorporate any part of this software into their
  17.  products!  Usually there is no charge for under 50-100 items for
  18.  low-cost or shareware, and terms are reasonable.  Any royalties are used
  19.  for development, so equipment is often acceptable payment.
  20.  
  21.  ATTRIBUTION:  If you use any part of this source code or the libraries
  22.  in your projects, you must give attribution to REND386, Dave Stampe,
  23.  and Bernie Roehl in your documentation, source code, and at startup
  24.  of your program.  Let's keep the freeware ball rolling!  No more
  25.  code ripoffs please.
  26.  
  27.  CONTACTS: dstampe@psych.toronto.edu, broehl@sunee.uwaterloo.ca
  28.  See the COPYRITE.H file for more information.
  29. */
  30.  
  31. This file has object and poly depth-sorting code and object
  32. bounding sphere view-volume clipping routines.  It also computes
  33. the screen extent of the object bounding sphere (roughly) and
  34. preclears object flags for rendering.
  35.  
  36. Both quicksort and insertion sort are supplied, to optimally
  37. support poly counts from 2 to 2000.
  38.  
  39.  
  40.  
  41. /* Contact: dstampe@sunee.waterloo.edu */
  42.  
  43.         $
  44.  
  45.     .MODEL large
  46.     .386
  47.  
  48.     .DATA
  49.  
  50. include 3dstruct.inc
  51. include viewdata.inc
  52.  
  53.     .CODE RENDERER
  54.  
  55.  
  56.  
  57. ;/********* QUICKSORT OF OBJECT OR POLYS BY DEPTH *******/
  58.  
  59. ; uses near ptrs for speed
  60. ; sorta in descending order
  61.  
  62. ;/* m, n actually near ptrs into array */
  63. ;/* es is seg. of array throughout */
  64. ;/* keep array under 64K in size!  */
  65.  
  66. ;static void qsort_iter(int m, int n)
  67. ;   NEAR for speed
  68.  
  69.  
  70. m    equ    [bp+6]
  71. n    equ    [bp+4]
  72.  
  73. qsort_iter  PROC NEAR
  74.  
  75.     push    bp
  76.     mov    bp,sp
  77.     mov    si,m           ; end of sort tree?
  78.     cmp    si,n
  79.     jge    end_of_sort
  80.  
  81.     mov    di,n        ; setup for pass
  82.     add     di,8
  83.     mov    eax,DWORD PTR es:[si].DS_depth
  84. gloop:
  85. fmax:                ; find one less than current
  86.     add    si,8
  87.     cmp    DWORD PTR es:[si].DS_depth,eax
  88.     jg    fmax
  89. fmin:                           ; find one grater than current
  90.     sub    di,8
  91.     cmp    DWORD PTR es:[di].DS_depth,eax
  92.     jl    fmin
  93.  
  94.     cmp    si,di        ; swap or subdivide?
  95.     jge    nonswap
  96.  
  97.     mov    ebx,DWORD PTR es:[si]   ; just swap entries, try next
  98.     mov    edx,DWORD PTR es:[di]
  99.     mov    DWORD PTR es:[di],ebx
  100.     mov    DWORD PTR es:[si],edx
  101.     mov    ebx,DWORD PTR es:[si+4]
  102.     mov    edx,DWORD PTR es:[di+4]
  103.     mov    DWORD PTR es:[di+4],ebx
  104.     mov    DWORD PTR es:[si+4],edx
  105.     jmp    gloop
  106.  
  107. nonswap:                ; swap and subdivide
  108.     mov    si,m
  109.     mov    ebx,DWORD PTR es:[si]
  110.     mov    edx,DWORD PTR es:[di]
  111.     mov    DWORD PTR es:[di],ebx
  112.     mov    DWORD PTR es:[si],edx
  113.     mov    ebx,DWORD PTR es:[si+4]
  114.     mov    edx,DWORD PTR es:[di+4]
  115.     mov    DWORD PTR es:[di+4],ebx
  116.     mov    DWORD PTR es:[si+4],edx
  117.  
  118.     sub    di,8            ; pivot - 1
  119.     cmp    si,di
  120.     jge    skip_qs1
  121.     push    si        ; m argument
  122.     push    di        ; n argument
  123.     call    near ptr qsort_iter
  124.     pop    di
  125.     pop    si
  126. skip_qs1:
  127.     add    di,16        ; pivot + 1
  128.     cmp    di,WORD PTR n
  129.     jge    end_of_sort
  130.     push    di        ; m argument
  131.     push    WORD PTR n    ; n argument
  132.     call    near ptr qsort_iter
  133.     add    sp,4
  134. end_of_sort:
  135.     pop    bp
  136.     retn
  137.  
  138. qsort_iter  endp
  139.  
  140.  
  141.  
  142. ; quicksort of poly/object array
  143. ;
  144. ; void qsort_dsort(DSORT far *first, DSORT far *last);
  145.  
  146.  
  147. first    equ    [bp+8]          ; arguments
  148. last    equ    [bp+12]
  149.  
  150.     PUBLIC    _qsort_dsort
  151.  
  152. _qsort_dsort    proc    far
  153.  
  154.     .386
  155.     push    ebp
  156.     mov    ebp,esp
  157.  
  158.     push    edx
  159.     push    ecx
  160.     push    esi
  161.     push    edi
  162.  
  163.     mov    ax,WORD PTR first+2    ; args must be in same segment
  164.     cmp    ax,WORD PTR last+2
  165.     jne    no_sort
  166.  
  167.     les    di,DWORD PTR first      ; sanity check
  168.     mov    si,WORD PTR last
  169.     cmp    di,si
  170.     jae    no_sort
  171.  
  172.     push    di                      ; start sort
  173.     push    si
  174.     call    near ptr qsort_iter
  175.     add    esp,4
  176.  
  177. no_sort:
  178.     pop    edi
  179.     pop    esi
  180.     pop    ecx
  181.     pop    edx
  182.  
  183.     mov    esp,ebp
  184.     pop    ebp
  185.     ret
  186.  
  187. _qsort_dsort    endp
  188.  
  189.  
  190. ;/********* FAST SORT OF OBJECT OR POLYS BY DEPTH *******/
  191.  
  192.  
  193. ; insertion sort of poly/object array
  194. ; faster than quicksort if less than 16 items
  195. ; sorts in descending order
  196. ;
  197. ; void insertion_dsort(DSORT far *first, DSORT far *last);
  198.  
  199.  
  200. first    equ    DWORD PTR [bp+8]          ; arguments
  201. last    equ    DWORD PTR [bp+12]
  202.  
  203.     PUBLIC    _insertion_dsort
  204.  
  205. _insertion_dsort    proc    far
  206.  
  207.     push    ebp                     ; di is start/current pivot
  208.     mov    ebp,esp                 ; si is end marker
  209.                     ; bx is search pointer
  210.     push    edx                     ; eax is comparison
  211.     push    esi
  212.     push    edi
  213.  
  214.     mov    ax,WORD PTR first+2    ; args must be in same segment
  215.     cmp    ax,WORD PTR last+2
  216.     jne    no_sort
  217.  
  218.     les    di,DWORD PTR first
  219.     mov    si,WORD PTR last
  220.  
  221. outer_loop:                             ; sanity/finished check
  222.     cmp    di,si
  223.     jae    end_sort
  224.  
  225.     mov    bx,di                   ; search ptr
  226.     mov    eax,080000001h        ; comparison value : init to big_neg
  227.     mov    dx,bx            ; records biggest found
  228. find_loop:
  229.     cmp    eax,es:[bx].DS_depth    ; biggest so far?
  230.     jge    dont_swap
  231.  
  232.     mov    eax,es:[bx].DS_depth    ; record
  233.     mov    dx,bx
  234. dont_swap:
  235.     add    bx,8    ; size DSORT    ; next item
  236.     cmp    bx,si                   ; past last?
  237.     jbe    find_loop
  238.  
  239.     cmp    dx,di            ; no swap needed?
  240.     je    no_swap_req
  241.  
  242.     mov    bx,dx
  243.     mov    eax,DWORD PTR es:[di]   ; swap current with smallest
  244.     mov    edx,DWORD PTR es:[bx]
  245.     mov    DWORD PTR es:[bx],eax
  246.     mov    DWORD PTR es:[di],edx
  247.     mov    eax,DWORD PTR es:[bx+4]
  248.     mov    edx,DWORD PTR es:[di+4]
  249.     mov    DWORD PTR es:[di+4],eax
  250.     mov    DWORD PTR es:[bx+4],edx
  251.  
  252. no_swap_req:
  253.     add    di,8    ; size DSORT
  254.     jmp    outer_loop
  255.  
  256. end_sort:
  257.     pop    edi               ; finished!
  258.     pop    esi
  259.     pop    edx
  260.  
  261.     mov    esp,ebp
  262.     pop    ebp
  263.     ret
  264.  
  265. _insertion_dsort    endp
  266.  
  267.  
  268.  
  269.  
  270. ;/************ OBJECT-CLIPPING BY VIEW VOLUME **************/
  271.  
  272. ;#define OUT_OF_VIEW 0x8000000L    // returned if we can't see object
  273.  
  274. ;long obj_clip_by_volume(OBJECT *obj)
  275.  
  276.  
  277. obj    equ    DWORD PTR [bp+8]          ; arguments
  278.  
  279. center_z   equ    DWORD PTR [bp-4]      ; locals
  280. center_z4  equ    DWORD PTR [bp-8]
  281.  
  282. tx    equ    DWORD PTR es:[bx].O_sphx  ; bounding sphere center
  283. ty    equ    DWORD PTR es:[bx].O_sphy
  284. tz    equ    DWORD PTR es:[bx].O_sphz
  285. r    equ    DWORD PTR es:[bx].O_sphr  ; bounding sphere radius
  286.  
  287.  
  288.     PUBLIC    _obj_clip_by_volume
  289.  
  290. _obj_clip_by_volume    proc    far
  291.  
  292.     .386
  293.     push    ebp
  294.     mov    ebp,esp
  295.     sub    esp,12
  296.  
  297.     push    esi
  298.     push    edi
  299.     push    ecx
  300.  
  301.     les    bx,obj
  302.  
  303.     mov    eax,_VS_fact7     ; convert center Z to camera coords
  304.     mov    edx,tx
  305.     sub    edx,_VS_iview_x
  306.     imul    edx
  307.     mov    esi,eax
  308.     mov    edi,edx
  309.  
  310.     mov    eax,_VS_fact8
  311.     mov    edx,ty
  312.     sub    edx,_VS_iview_y
  313.     imul    edx
  314.     add    esi,eax
  315.     adc    edi,edx
  316.  
  317.     mov    eax,_VS_fact9
  318.     mov    edx,tz
  319.     sub    edx,_VS_iview_z
  320.     imul    edx
  321.     add    esi,eax
  322.     adc    edi,edx
  323.  
  324.     shrd    esi,edi,27 ;29-PRESCALEZ    ; shift is prescaled
  325.     mov    center_z4,esi
  326.     sar    esi,2 ;PRESCALEZ           ; now un-prescaled
  327.     mov    center_z,esi
  328.  
  329.     add    esi,r
  330.     cmp    esi,_VS_hither
  331.     jl    outofview        ; too close
  332.  
  333.     sub    esi,r
  334.     sub    esi,r
  335.     cmp    esi,_VS_yon
  336.     jg    outofview        ; too far
  337.  
  338.  
  339.     mov    eax,_VS_fact1   ; convert X coord to camera space
  340.     mov    edx,tx
  341.     sub    edx,_VS_iview_x
  342.     imul    edx
  343.     mov    esi,eax
  344.     mov    edi,edx
  345.  
  346.     mov    eax,_VS_fact2
  347.     mov    edx,ty
  348.     sub    edx,_VS_iview_y
  349.     imul    edx
  350.     add    esi,eax
  351.     adc    edi,edx
  352.  
  353.     mov    eax,_VS_fact3
  354.     mov    edx,tz
  355.     sub    edx,_VS_iview_z
  356.     imul    edx
  357.     add    esi,eax
  358.     adc    edi,edx
  359.  
  360.     shrd    esi,edi,29    ; now camera x coord of center
  361.  
  362.                 ; DO LEFT PLANE TEST
  363.     mov    eax,_VS_left_C    ; multiply by slope
  364.     neg    eax
  365.     imul    center_z
  366.     shrd    eax,edx,29
  367.     mov    ecx,eax
  368.     sub    ecx,r
  369.  
  370.     mov    eax,_VS_left_M    ; second term
  371.     imul    esi
  372.     shrd    eax,edx,29
  373.  
  374.     cmp    ecx,eax
  375.     jg    outofview    ; too far left
  376.  
  377.     mov    eax,_VS_right_C ; DO RIGHT PLANE TEST
  378.     neg    eax
  379.     imul    center_z
  380.     shrd    eax,edx,29
  381.     mov    ecx,eax
  382.     sub    ecx,r
  383.  
  384.     mov    eax,_VS_right_M
  385.     imul    esi
  386.     shrd    eax,edx,29
  387.  
  388.     neg    eax
  389.     cmp    ecx,eax
  390.     jg    outofview     ; too far right
  391.  
  392.     mov    eax,_VS_fact4    ; compute Y coord of center
  393.     mov    edx,tx
  394.     sub    edx,_VS_iview_x
  395.     imul    edx
  396.     mov    esi,eax
  397.     mov    edi,edx
  398.  
  399.     mov    eax,_VS_fact5
  400.     mov    edx,ty
  401.     sub    edx,_VS_iview_y
  402.     imul    edx
  403.     add    esi,eax
  404.     adc    edi,edx
  405.  
  406.     mov    eax,_VS_fact6
  407.     mov    edx,tz
  408.     sub    edx,_VS_iview_z
  409.     imul    edx
  410.     add    esi,eax
  411.     adc    edi,edx
  412.  
  413.     shrd    esi,edi,29     ; y coord in camera space of center
  414.  
  415.     mov    eax,_VS_bot_C   ; BOTTOM PLANE CLIP
  416.     neg    eax
  417.     imul    center_z
  418.     shrd    eax,edx,29
  419.     mov    ecx,eax
  420.     sub    ecx,r
  421.  
  422.     mov    eax,_VS_bot_M
  423.     imul    esi
  424.     shrd    eax,edx,29
  425.  
  426.     cmp    ecx,eax
  427.     jg    outofview     ; too far down
  428.  
  429.  
  430.     mov    eax,_VS_top_C   ; TOP PLANE CLIP
  431.     neg    eax
  432.     imul    center_z
  433.     shrd    eax,edx,29
  434.     mov    ecx,eax
  435.     sub    ecx,r
  436.  
  437.     mov    eax,_VS_top_M
  438.     imul    esi
  439.     shrd    eax,edx,29
  440.  
  441.     neg    eax
  442.     cmp    ecx,eax         ; too far up
  443.     jg    outofview
  444.  
  445.     mov    eax,center_z4    ; return Z if OK
  446.     jmp    ret_32
  447.  
  448. outofview:
  449.     mov    eax,OUT_OF_VIEW    ; flag, none of sphere in view volume
  450. ret_32:
  451.     shld    edx,eax,16    ; return value in both EAX and DX:AX
  452.  
  453.     pop    ecx
  454.     pop    edi
  455.     pop    esi
  456.  
  457.     mov    esp,ebp
  458.     pop    ebp
  459.     ret
  460.  
  461. _obj_clip_by_volume    endp
  462.  
  463.  
  464.  
  465. ;/********* ESTIMATE SCREEN WIDTH FOR REP SELECT ***********/
  466.  
  467. ; only use if object has passed preclip!
  468. ; returns -1 if error
  469. ;
  470. ; long compute_obj_screen_size(OBJECT *obj, long center_z);
  471.  
  472. obj     equ    DWORD PTR [bp+8]          ; arguments
  473. center_z equ    DWORD PTR [bp+12]
  474.  
  475. r     equ    DWORD PTR es:[bx].O_sphr  ; bounding sphere radius
  476.  
  477.     PUBLIC    _compute_obj_screen_size
  478.  
  479. _compute_obj_screen_size   proc    far
  480.  
  481.     .386
  482.     push    ebp
  483.     mov    ebp,esp
  484.  
  485.     les    bx,obj
  486.     mov    eax,r              ; /* size = scale*radius/distance */
  487.     imul    DWORD PTR _VS_scx
  488.     shrd    eax,edx,8       ;  /* range-extended <16.16> -> <32.0> */
  489.     sar    edx,8
  490.     idiv    DWORD PTR center_z
  491.     sar    eax,6              ;  /* 2x true size so it's diameter */
  492.  
  493.     shld    edx,eax,16    ; result in eax AND dx:ax
  494.  
  495.     mov    esp,ebp
  496.     pop    ebp
  497.     ret
  498.  
  499. _compute_obj_screen_size  endp
  500.  
  501.  
  502. ;/********* CLEAR OBJECT FLAGS FOR RENDERING ***********/
  503.  
  504. ; a representation must be current!
  505. ;
  506. ; void prerender_clear_object(OBJECT *obj);
  507.  
  508. obj    equ    DWORD PTR [bp+8]           ; arguments
  509.  
  510.  
  511.     PUBLIC    _prerender_clear_object
  512.  
  513. _prerender_clear_object   proc    far
  514.  
  515.     .386
  516.     push    ebp
  517.     mov    ebp,esp
  518.  
  519.     les    bx,obj
  520.     les    bx,es:[bx].O_currep   ; current object representation
  521.     mov    ax,es:[bx].R_nverts
  522.     les    bx,es:[bx].R_verts
  523. clear_loop:
  524.     mov    DWORD PTR es:[bx].V_nvptr,0
  525.     mov    WORD PTR es:[bx].V_zxflag,0   ; clears outcode and flags
  526.     add    bx,SIZE VERTEX
  527.     dec    ax
  528.     jne    clear_loop
  529.  
  530.     mov    esp,ebp
  531.     pop    ebp
  532.     ret
  533.  
  534. _prerender_clear_object  endp
  535.  
  536.  
  537.  
  538.     end
  539.  
  540.  
  541.  
  542.  
  543.  
  544.