Fast Ray/Line<->Plane intersection in BASIC

[D.J.Peters]

ray/line<> plane intersection can be usefull for collision detection and ray tracing ...
if you get for example 30 fps this means
320*200*50=1,920,000 intersection tests per second

Joshy

Code: Select all

type VECTOR3D
  as single x,y,z
  as single dummy
end type

type PLANE_t
  as VECTOR3D Position
  as VECTOR3D Normale
  as VECTOR3D A
  as VECTOR3D B
  as single   MaxWidth,NP,DN
  as single   al,be,ga
end type

dim shared Plane   as PLANE_t
dim shared Texture as integer ptr

' 2x2 pixel in this case
sub CreateTexture()
  if Texture<>0 then return
  Texture=callocate(2*2*4)
  Texture[0]=&HFFFFFF
  Texture[2]=&HFFFFFF
end sub

sub VecRotate( _
          byref RetVec as VECTOR3D, _
                SrcVec as VECTOR3D, _
                a      as single, _
                b      as single, _
                g      as single)
  a*=atn(1)/45
  b*=atn(1)/45
  g*=atn(1)/45
  dim as single cox = Cos(a), coy = Cos(b), coz = Cos(g)
  dim as single six = Sin(a), siy = Sin(b), siz = Sin(g)

  dim as single Y = SrcVec.Y * cox - SrcVec.Z * six
  dim as single Z = SrcVec.Y * six + SrcVec.Z * cox
  dim as single X = SrcVec.X * coy +        Z * siy
         RetVec.Z =-SrcVec.X * siy +        Z * coy
         RetVec.X =        X * coz -        Y * siz
         RetVec.Y =        X * siz +        Y * coz
end sub

const ScreenWidth = 320
const ScreenHeight= 240
const MiddleWidth = ScreenWidth *0.5
const MiddleHeight= ScreenHeight*0.5
const ScaleInv    = 1/ScreenWidth

Function ShowPoint(X as integer, _
                   Y as integer) as integer
  dim as VECTOR3D ODES=any,HitP=any
  dim as single L=any ' length of ray if hits
  dim as integer u=any,v=any ' texture coords
  ' shot a ray thrue every pixel
  With ODES
    .X = (X-MiddleWidth ) * ScaleInv
    .Y = (MiddleHeight-Y) * ScaleInv
    .Z = 1
  End With
  With Plane
    ' dot = ray * plane normale
    .DN=ODes.x*.Normale.x _
       +ODes.y*.Normale.y _
       +       .Normale.z ' rey.destination.z is = 1
    if .DN=0 then return &H5555CC
    L= .NP/.DN ' parallel or far away
    if (L<1) or (L>.MaxWidth) then return &H5555CC
    ' get ray hitpont
    HitP.x=ODes.x*L-.Position.x
    HitP.y=ODes.y*L-.Position.y
    HitP.z=       L-.Position.z
    ' rotate it back in camera space
    VecRotate HitP,HitP,-.al,-.be,-.ga
    
    ' optional get texture coords
    u=abs(HitP.x/.MaxWidth)*32
    v=abs(Hitp.z/.MaxWidth)*32
    ' texture is in this case 2x2
    u and=1:v and=1':u shl=1
  end with
  return texture[u+v]
End Function

sub Render
  dim as integer ptr lpScreen
  lpScreen=screenptr
  For y as integer=0 to ScreenHeight-1
    For X as integer=0 to ScreenWidth-1
      *lpScreen=ShowPoint(x,y)
      lpScreen+=1
    next
  next
end sub




'
' main
'
dim as single w
dim as double t1,t2
dim as integer frames,fps
ScreenRes ScreenWidth,ScreenHeight,24,,1
CreateTexture
Plane.MaxWidth=512*40

t1=timer
while inkey<>chr(27)
  With Plane
    .Normale.x=0:.Normale.y=1:.Normale.z=0
    .A.x      =0:.A.y      =0:.A.z      =1
    .B.x      =1:.B.y      =0:.B.z      =0
    VecRotate .Normale,.Normale,.al,.be,.ga
    VecRotate .A      ,.A      ,.al,.be,.ga
    VecRotate .B      ,.B      ,.al,.be,.ga
    .NP=.Normale.x*.Position.x _
       +.Normale.y*.Position.y _
       +.Normale.z*.Position.z
    screenlock:cls
    Render
    locate 1,1:print fps
    screenunlock
    .Position.y=sin(w*3)*300-350
    .al=sin(w*2.0)* 15
    .be=cos(w    )*360
    .ga=sin(w*0.5)*  5
    w+=0.005:if w>(atn(1)*8)  then w=0
  end with
  frames+=1
  if frames=100 then
    t2=timer
    fps=frames/(t2-t1)
    t1=t2:frames=0
  end if
  sleep 20
wend