# Partial octree implementation

I am just now learning Scala a bit on my own time. I wrote some code that works, but was wondering if you could eyeball it to see if its structure can be improved. It is a partial octree implementation.

class octree(min_x:Double,
min_y:Double,
min_z:Double,
max_x:Double,
max_y:Double,
max_z:Double
){
var children:Array[octree] = new Array[octree](8)
val min = (min_x,min_y,min_z)
val max = (max_x,max_y,max_z)

def side(x:Double,y:Double):Int={
if(x<y) 1
else 0
}
def index(x:Double,y:Double,z:Double):Int={
val center=(0.5*(max._1+min._1),0.5*(max._2+min._2),
0.5*(max._3+min._3))
(side(center._1,x))|(side(center._2,y)<<1)|     (side(center._3,z)<<2)
}
var i=index(x,y,z)
print(" "+i)
if(children(i)==null){
var min2_x=min._1
var min2_y=min._2
var min2_z=min._3
var max2_x=max._1
var max2_y=max._2
var max2_z=max._3

val center=(0.5*(max._1+min._1),0.5*(max._2+min._2),
0.5*(max._3+min._3))

if((i&1)==0) max2_x=center._1
else min2_x=center._1
if((i&2)==0) max2_y=center._2
else min2_y=center._2
if((i&4)==0) max2_z=center._3
else min2_z=center._3

children(i) = new        octree(min2_x,min2_y,min2_z,max2_x,max2_y,max2_z)
children(i)
}
}
def find(x:Double,y:Double,z:Double):octree={
var i=index(x,y,z)
print(" "+i)
if(children(i)==null){
this
}
else children(i).find(x,y,z)
}
}


Some ideas:

• Properly indent your code and strictly adhere to some style guide. (For example it's very uncommon to have class name starting with a lowercase letter.) I recommend you to read some style guide or study the code of some publicly available libraries. This is very important for readability and future maintainability of your code. It doesn't matter if you will be reading it or somebody else. Code is written once but read many times.
• Define a custom class for vectors. (Having a function with 6 arguments is inconvenient and error prone and it is a signal for looking for alternative solutions).
• Use this class to implement vector operations on it.
• Variables that aren't modified should be declared val.
• side could be made local to the index method.
• center can be precomputed and reused.
• Instead of modifying variables when computing adding a node, it's often more idiomatic to describe the new cell declaratively. Using a helper function can shorten the code.
• Optimize recursive functions using tailrec, if possible.

After some refactoring:

case class Vector(x: Double, y: Double, z: Double) {
def +(that: Vector) = Vector(this.x + that.x,
this.y + that.y,
this.z + that.z);
def *(scalar: Double) = Vector(this.x * scalar,
this.y * scalar,
this.z * scalar);
}

class Octree(min: Vector, max: Vector) {
val children: Array[Octree] = new Array[Octree](8)
val center = (max + min) * 0.5

def index(p: Vector): Int = {
@inline
def side(x: Double, y: Double): Int =
if (x < y) 1
else 0
(side(center.x, p.x)) |
(side(center.y, p.y)<<1) |
(side(center.z, p.z)<<2)
}

@annotation.tailrec
final def add(point: Vector): Octree = {
var i = index(point)
debug(i)
if (children(i) == null) {
@inline
def pick(b: Int, f: Vector => Double, l: Vector, r: Vector): Double =
if (b == 0) f(l)
else f(r)
def split(v1: Vector, v2: Vector): Vector =
Vector(pick(i & 1, _.x, v1, v2),
pick(i & 2, _.y, v1, v2),
pick(i & 4, _.z, v1, v2));
children(i) = new Octree(
split(center, min),
split(max, center));
children(i)
} else
}

@annotation.tailrec
final def find(p: Vector): Octree = {
var i = index(p)
debug(i)
if(children(i) == null)
this
else
children(i).find(p)
}

private def debug(message: => Any) {
// if you comment out the print statement, message
// won't be evaluated, so even if it's computationally intensive,
// you don't need to comment out debug from the code.
print(message.toString)
}
}


Just a few remarks on your implementation.

(0) Define a vector type!

(1) The whole side thing and using bit patterns to guide your logic is very hard to follow.

(2) Usually an octree just forms a tree from the vertices contained within; your implementation works by representing the bounding cuboid at each level, which makes your code more complex.

Here's a C# sketch of what I mean in point (2):

public class Vec {
double[] XYZ;
public Vec(double x, double y, double z) { XYZ = new double[3] { x, y, z }; }
public double X { get { return XYZ[0]; } }
public double Y { get { return XYZ[1]; } }
public double Z { get { return XYZ[2]; } }
public double this[int i] { get { return XYZ[i]; } }
public bool Eq(Vec v) { return v.X == X && v.Y == Y && v.Z == Z; }
}

public class Octree {
int Idx;
Vec Item;
Octree L;
Octree R;
public static Octree Ins(Octree t, Vec v, int idx = 0) {
if (t == null) return new Octree { Idx = idx, Item = v };
if (t.Item.Eq(v)) return t;
return (0 <= v[t.Idx] - t.Item[t.Idx])
? new Octree { Idx = t.Idx, Item = t.Item, L = Octree.Ins(t.L, v, (idx + 1) % 3), R = t.R }
: new Octree { Idx = t.Idx, Item = t.Item, L = t.L, R = Octree.Ins(t.R, v, (idx + 1) % 3) };
}
public static bool Contains(Octree t, Vec v) {
if (t == null) return false;
if (t.Item.Eq(v)) return true;
return Octree.Contains(0 <= v[t.Idx] - t.Item[t.Idx] ? t.L : t.R, v);
}
}