Code archives/3D Graphics - Misc/2D BSP
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
This demonstrates how bsp trees work in 2 dimensions. I will be expanding it to include a third axis. This wasn't such a big deal after all, now was it? | |||||
;2-Dimensional BSP Tree ;by Joshua Klint AppTitle "2-Dimensional BSP Tree" Graphics 700,320,16,2 SetBuffer BackBuffer() Type node Field x1,y1,x2,y2,nx#,ny# Field child.node[1] Field index,flags Field red,green,blue End Type Global intersectedx# Global intersectedy# Global countnodes Global master.node ClsColor 255,255,255 logstring$="Click and drag to create a node." Repeat For n.node=Each node Color 0,0,0 x#=(n\x2-n\x1)/2+n\x1 y#=(n\y2-n\y1)/2+n\y1 Line x,y,x+n\nx*6,y+n\ny*6 Color n\red,n\green,n\blue Line n\x1,n\y1,n\x2,n\y2 Color 0,0,0 Text n\x1,n\y1,n\index Next If pointwithinrect(MouseX(),MouseY(),0,0,399,300) If MouseHit(1) If Not drawmode logstring$="" drawmode=True x1=MouseX() y1=MouseY() x2=x1 y2=y1 EndIf EndIf If MouseDown(1) x2=MouseX() y2=MouseY() Color 255,0,0 Line x1,y1,x2,y2 Color 200,200,200 For n.node=Each node If intersectlines(x1,y1,x2,y2,n\x1,n\y1,n\x2,n\y2) Line intersectedx,0,intersectedx,300 Line 0,intersectedy,400,intersectedy EndIf Next Else If drawmode drawmode=False logstring$="Created new node." For n.node=Each node If intersectlines(x1,y1,x2,y2,n\x1,n\y1,n\x2,n\y2) logstring="Created multiple nodes." Exit EndIf Next n.node=New node n\red=Rnd(255) n\green=Rnd(255) n\blue=Rnd(255) n\x1=x1 n\y1=y1 n\x2=x2 n\y2=y2 nx#=y2-y1 ny#=x2-x1 l#=Sqr(nx^2+ny^2) n\nx=nx/l n\ny=-ny/l n\index=countnodes countnodes=countnodes+1 If master.node=Null master=n Else placenode n,master EndIf EndIf EndIf EndIf If master<>Null Color 0,0,0 displaybsptree master,550,20,60 EndIf Color 208,207,192 Rect 0,300,400,2 Rect 400,0,2,GraphicsHeight() Color 0,0,0 Text 5,304,logstring Flip Cls Forever Function pointwithinrect(x#,y#,boxx#,boxy#,width#,height#) If x>boxx If x<boxx+width If y>boxy If y<boxy+height Return True EndIf EndIf EndIf End Function Function intersectlines(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#,segment=True) den#=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1) If den=0.0 Return False ua#=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den ub#=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den If segment If ua>1.0 Or ua<0.0 Or ub>1.0 Or ub<0.0 Return False EndIf intersectedx#=x1+ua*(x2-x1) intersectedy#=y1+ua*(y2-y1) Return True End Function ;If result=0 point is on line. ;If result=1 point is behind line. ;if result=-1 point is in front of line. Function pointonline(x#,y#,x1#,y1#,x2#,y2#) m#=(y2-y1)/(x2-x1) b#=-m*x1+y1 yvalue#=m*x+b If yvalue=y Return 0 If yvalue>y Return -1*Sgn(x2-x1) If yvalue<y Return 1*Sgn(x2-x1) End Function Function placenode(n.node,m.node) result=pointonline(n\x1,n\y1,m\x1,m\y1,m\x2,m\y2) result2=pointonline(n\x2,n\y2,m\x1,m\y1,m\x2,m\y2) If result=-1 result=0 If result2=-1 result2=0 If result<>result2 intersectlines(n\x1,n\y1,n\x2,n\y2,m\x1,m\y1,m\x2,m\y2,False) n2.node=New node n2\x1=intersectedx n2\y1=intersectedy n2\x2=n\x2 n2\y2=n\y2 n\x2=intersectedx n\y2=intersectedy n2\index=countnodes n2\nx=n\nx n2\ny=n\ny n\red=Rnd(255) n\green=Rnd(255) n\blue=Rnd(255) countnodes=countnodes+1 If m\child[result2]=Null m\child[result2]=n2 Else placenode n2,m\child[result2] EndIf EndIf If m\child[result]=Null m\child[result]=n Else placenode n,m\child[result] EndIf End Function Function displaybsptree(n.node,x,y,width,layer=0) Text x,y,n\index,1,1 offset=width/2^layer If n\child[0]<>Null Line x,y,x-offset,y+40 displaybsptree n\child[0],x-offset,y+40,width,layer+1 EndIf If n\child[1]<>Null Line x,y,x+offset,y+40 displaybsptree n\child[1],x+offset,y+40,width,layer+1 EndIf End Function |
Comments
None.
Code Archives Forum