@Kolosso As you are working in 3D you should use an octree. The principal is basically the same except they are split into eight nodes instead of four to cope with the extra dimension.

Check out these links for some reference material. (The code examples aren’t lua)

http://www.flipcode.com/archives/Introduction_To_Octrees.shtml

http://www.gamasutra.com/view/feature/131625/octree_partitioning_techniques.php

https://github.com/Nition/UnityOctree/

Getting the frustrum in Codea is a little tricky to understand but doesn’t require too much typing because it can extracted directly from Codea’s transform matrices using the OpenGL plane extraction technique described in the links below.

http://www.lighthouse3d.com/tutorials/view-frustum-culling/clip-space-approach-extracting-the-planes/

http://www.lighthouse3d.com/tutorials/view-frustum-culling/clip-space-approach-implementation-details/

To be honest it was a bit of a pain to port so I’ll save you the trouble

Note: It also implements the radar method from the same tutorial so it actually has two independent representations of the frustrum.

Edit: Whoops I missed off a couple of extra links.

Extracting frustrum planes

http://www.txutxi.com/?p=444

AABB intersect algorithm

http://www.txutxi.com/?p=584

http://old.cescg.org/CESCG-2002/DSykoraJJelinek/

```
Frustrum = class()
Frustrum.planes = {"near","left","right","bottom","top","far"}
function Frustrum:init()
self.camPos = vec3(0,0,0)
self.planes = {}
for i, name in ipairs(Frustrum.planes) do
self.planes[name] = {abc=vec3(0,0,0),d=0}
end
end
function Frustrum:setPerspective(angle,ratio,near,far)
self.ratio = ratio
self.near = near
self.far = far
angle = math.rad(angle)
self.tang = math.tan(angle * 0.5)
self.height = near * self.tang
self.width = self.height * ratio
self.sphereY = 1.0/math.cos(angle)
self.sphereX = 1.0/math.cos(math.atan(self.tang * ratio))
end
function Frustrum:setCamera(p,l,u)
self.z = (l - p):normalize()
self.x = self.z:cross(u):normalize()
self.y = self.x:cross(self.z)
self.camPos = p
self:setPlanes()
end
local function setPlane(p,m,a,b,c,d,s)
p.abc.x =(m[a]*s) + m[4]
p.abc.y = (m[b]*s) + m[8]
p.abc.z = (m[c]*s) + m[12]
p.d = (m[d]*s) + m[16]
p.di = -p.d
end
function Frustrum:setPlanes(vMatrix,pMatrix)
vMatrix = vMatrix or viewMatrix()
pMatrix = pMatrix or projectionMatrix()
local m = vMatrix * pMatrix
setPlane(self.planes.left,m,1,5,9,13,1)
setPlane(self.planes.right,m,1,5,9,13,-1)
setPlane(self.planes.bottom,m,2,6,10,14,1)
setPlane(self.planes.top,m,2,6,10,14,-1)
setPlane(self.planes.near,m,3,7,11,15,1)
setPlane(self.planes.far,m,3,7,11,15,-1)
end
function Frustrum:radarTestPoint(p)
local v = p - self.camPos
local pcz = v:dot(self.z)
local near, far = self.near,self.far
if pcz > far or pcz < near then
return false
end
local pcy = v:dot(self.y)
local aux = pcz * self.tang
if pcy > aux or pcy < -aux then
return false
end
local pcx = v:dot(self.x)
aux = aux * self.ratio
if pcx > aux or pcx < -aux then
return false
end
return true
end
function Frustrum:radarTestSphere(p,r)
local result = true
local v = p - self.camPos
local pcz = v:dot(self.z)
local near, far = self.near,self.far
if pcz > far + r or pcz < near - r then
return false
elseif pcz > far - r or pcz < near + r then
-- intersect
end
local pcy = v:dot(self.y)
local d = self.sphereY * r
local aux = pcz * self.tang
if pcy > aux+d or pcy < -aux-d then
return false
elseif pcy > aux-d or pcy < -aux+d then
-- intersect
end
local pcx = v:dot(self.x)
d = self.sphereX * r
aux = aux * self.ratio
if pcx > aux+d or pcx < -aux-d then
return false
elseif pcx > aux-d or pcx < -aux+d then
-- intersect
end
return result
end
function Frustrum:planeTestBounds(min,max)
for i,name in ipairs(Frustrum.planes) do
local plane = self.planes[name]
local p = vec3(
plane.abc.x > 0 and max.x or min.x,
plane.abc.y > 0 and max.y or min.y,
plane.abc.z > 0 and max.z or min.z
)
if p:dot(plane.abc) < plane.di then
return false
end
end
return true
end
function Frustrum:planeTestPoint(vec)
for i,name in ipairs(Frustrum.planes) do
local plane = self.planes[name]
if v:dot(plane.abc) < plane.di then
return false
end
end
return true
end
```

Usage example

```
frustrum = Frustrum()
-- set up frustrum with values from perspective and camera.
perspective(angle,ratio,near,far)
frustrum:setPerspective(angle,ratio,near,far)
camera(eye.x,eye.y,eye.z,centre.x,centre.y,centre.z,up.x,up.y,up.z)
frustrum:setCamera(eye,centre,up)
-- tests whether an AABB intersects / is inside frustrum using the extents
frustrum:planeTestBounds(bounds.min,bounds.max)
-- tests whether a Point is inside the frustrum
frustrum:planeTestPoint(vec)
```