aUCBLogo Demos and Tests / test_bsp_tree2
to test_bsp_tree2
local [t1]
perspective
clearScreen
WindowMode
setPC HSBA 0 0 0 0.5
(rerandom 654)
tt=triangle randxyz randxyz randxyz
pr tt
(rerandom int TimeMilli)
tree1=bsp_tree [0 0][400 300] (list tt) 0 0
updateGraph
end
to go
running=true
i=0
clearText
while [running]
[ print i
(rerandom i)
clearScreen
tt=triangle randxyz randxyz randxyz
(rerandom int TimeMilli)
tree1=bsp_tree [0 0][400 300] (list tt) 0 0
updateGraph
ch=readchar
if ch==char 27 [running=false]
if ch=="- [i=i-2]
if ch==char wxk_space [i=i+2]
]
end
to randx
output (random 600)-300
end
to randy
output (random 500)-250
end
to randz
output (random 500)-250
end
to randxyz
output (list randx randy randz)
end
be triangle p1 p2 p3
setPenColor HSBA random 360 1 1 0.1
PenUp
setPosXYZ p3
PenDown
Polygon
[ setPosXYZ p1
setPosXYZ p2
setPosXYZ p3
]
PenUp
end
to alpha a b
if ((norm a) != 0) and2 ((norm b) !=0)
[ output abs arccos (0+a*b)/(Norm a)/(Norm b)
]
output 0
end
be bsp_tree center size polys axis depth
if (norm size) < 4 [stop]
local [sub1 sub2 l inside in1 in2
p1 p2 p3 t t1 t2 t3 t4 x y z]
if axis==0 [x=1 y=2 z=3]
if axis==1 [x=2 y=3 z=1]
if axis==2 [x=3 y=1 z=2]
setPosXYZ xyz center.x center.y center.z
setFloodColor HSBA depth/10*360 1 1 0.1
fillRect -xyz size.x size.y size.z xyz size.x size.y size.z
;pause
sub1=[]
sub2=[]
l=polys
inside=[]
in1=[]
in2=[]
while [not empty? l]
[ t=first l
l=butFirst l
ifelse (t'p1).x >= center.x
[ ifelse (t'p2).x >= center.x
[ ifelse (t'p3).x >= center.x
[ inside=fput t inside
][ partition
]
][ ifelse (t'p3).x >= center.x
[ partition4
][ partition2
]
]
][ ifelse (t'p2).x <= center.x
[ ifelse (t'p3).x <= center.x
[ inside=fput t inside
][ partition6
]
][ ifelse (t'p3).x <= center.x
[ partition5
][ partition3
]
]
]
]
polys=inside
erase [[][l inside p1 p2 p3 t t1 t2 t3 t4]]
;comment[
if not empty? in1 [
sub1=bsp_tree
xy center.x+size.x/2 center.y center.z
xy size.x/2 size.y size.z
in1
modulo axis+1 3
depth+1
erase [[][in1]]
]
if not empty? in2 [
sub2=bsp_tree
xy center.x-size.x/2 center.y center.z
xy size.x/2 size.y size.z
in2
modulo axis+1 3
depth+1
erase [[][in2]]
]
;]
be xyz x y z
if axis==0 [output (list x y z)]
if axis==1 [output (list y z x)]
if axis==2 [output (list z x y)]
end
be partition
p2=xyz center.x
(t'p1).y-((t'p1).x-center.x)/((t'p1).x-(t'p3).x)*((t'p1).y-(t'p3).y)
(t'p1).z-((t'p1).x-center.x)/((t'p1).x-(t'p3).x)*((t'p1).z-(t'p3).z)
p3=xyz center.x
(t'p2).y-((t'p2).x-center.x)/((t'p2).x-(t'p3).x)*((t'p2).y-(t'p3).y)
(t'p2).z-((t'p2).x-center.x)/((t'p2).x-(t'p3).x)*((t'p2).z-(t'p3).z)
p1=xyz (t'p1).x (t'p1).y
p1_=xyz (t'p3).x (t'p3).y
a1=alpha p2-p1 p3-p1
a1_=alpha p2-p1_ p3-p1_
if a1_ < a1 [p1=p1_]
t1=triangle p1 p2 p3
in1=fput t1 in1
; t2=triangle t'p1 p1 p2
; in1=fput t2 in1
t3=triangle t'p2 p2 p3
in1=fput t3 in1
t4=triangle t'p3 p3 p1
in2=fput t4 in2
end
be partition2
p2=xyz center.x (t'p1).y+((t'p1).x-center.x)/((t'p1).x-(t'p2).x)*((t'p2).y-(t'p1).y)
p3=xyz center.x (t'p1).y+((t'p1).x-center.x)/((t'p1).x-(t'p3).x)*((t'p3).y-(t'p1).y)
p1=xyz (t'p3).x (t'p3).y
p1_=xyz (t'p1).x (t'p1).y
a1=alpha p2-p1 p3-p1
a1_=alpha p2-p1_ p3-p1_
if a1_ < a1 [p1=p1_]
t2=triangle t'p1 p3 p1
in2=fput t2 in2
t3=triangle t'p2 p2 p3
in2=fput t3 in2
t4=triangle t'p3 p3 p1
in1=fput t4 in1
end
be partition3
d2=((t'p1).x-(t'p2).x)
ifelse d2==0
[ p2=xyz center.x (t'p1).y
][ p2=xyz center.x (t'p1).y+((t'p1).x-center.x)/d2*((t'p2).y-(t'p1).y)
]
d3=((t'p1).x-(t'p3).x)
ifelse d3==0
[ p3=xyz (t'p3).x center.y
][ p3=xyz center.x (t'p1).y+((t'p1).x-center.x)/d3*((t'p3).y-(t'p1).y)
]
p1=xyz (t'p2).x (t'p2).y
p1_=xyz (t'p1).x (t'p1).y
a1=alpha p2-p1 p3-p1
a1_=alpha p2-p1_ p3-p1_
if a1_ < a1 [p1=p1_]
t1=triangle p1 p2 p3
in2=fput t1 in2
; t2=triangle t'p1 p1 p2
; in2=fput t2 in2
t3=triangle t'p2 p2 p3
in2=fput t3 in2
t4=triangle t'p3 p3 p1
in1=fput t4 in1
end
be partition4
d2=((t'p1).x-(t'p2).x)
ifelse d2==0
[ p2=xyz center.x (t'p1).y
][ p2=xyz center.x (t'p1).y+((t'p1).x-center.x)/d2*((t'p2).y-(t'p1).y)
]
d3=((t'p2).x-(t'p3).x)
ifelse d3==0
[ p3=xyz (t'p3).x center.y
][ p3=xyz center.x (t'p2).y+((t'p2).x-center.x)/d3*((t'p3).y-(t'p2).y)
]
p1=xyz (t'p1).x (t'p1).y
p1_=xyz (t'p3).x (t'p3).y
a1=alpha p2-p1 p3-p1
a1_=alpha p2-p1_ p3-p1_
if a1_ < a1 [p1=p1_]
t1=triangle p1 p2 p3
in2=fput t1 in2
t2=triangle t'p1 p1 p2
in2=fput t2 in2
t3=triangle t'p2 p2 p3
in2=fput t3 in2
t4=triangle t'p3 p3 p1
in1=fput t4 in1
end
be partition5
d2=((t'p1).x-(t'p2).x)
ifelse d2==0
[ p2=xyz center.x (t'p1).y
][ p2=xyz center.x (t'p1).y+((t'p1).x-center.x)/d2*((t'p2).y-(t'p1).y)
]
d3=((t'p2).x-(t'p3).x)
ifelse d3==0
[ p3=xyz (t'p3).x center.y
][ p3=xyz center.x (t'p2).y+((t'p2).x-center.x)/d3*((t'p3).y-(t'p2).y)
]
p1=xyz (t'p3).x (t'p3).y
p1_=xyz (t'p1).x (t'p1).y
a1=alpha p2-p1 p3-p1
a1_=alpha p2-p1_ p3-p1_
if a1_ < a1 [p1=p1_]
t1=triangle p1 p2 p3
in2=fput t1 in2
t2=triangle t'p1 p1 p2
in2=fput t2 in2
t3=triangle t'p2 p2 p3
in2=fput t3 in2
t4=triangle t'p3 p3 p1
in1=fput t4 in1
end
be partition6
d2=((t'p1).x-(t'p3).x)
ifelse d2==0
[ p2=xyz center.x (t'p1).y
][ p2=xyz center.x (t'p1).y+((t'p1).x-center.x)/d2*((t'p3).y-(t'p1).y)
]
d3=((t'p2).x-(t'p3).x)
ifelse d3==0
[ p3=xyz (t'p3).x center.y
][ p3=xyz center.x (t'p2).y+((t'p2).x-center.x)/d3*((t'p3).y-(t'p2).y)
]
p1=xyz (t'p1).x (t'p1).y
p1_=xyz (t'p2).x (t'p2).y
a1=alpha p2-p1 p3-p1
a1_=alpha p2-p1_ p3-p1_
if a1_ < a1 [p1=p1_]
t1=triangle p1 p2 p3
in2=fput t1 in2
t2=triangle t'p1 p1 p2
in2=fput t2 in2
t3=triangle t'p2 p2 p3
in2=fput t3 in2
t4=triangle t'p3 p3 p1
in1=fput t4 in1
end
end