User-selection is now slow because we aren't using the octree-opitmization

[GoogleCodeExporter]

Is it somehow possible to use the octree optimization again when searching for 
collision by the user's view vector?

Original issue reported on code.google.com by nin...@gmail.com on 21 Nov 2011 at 4:15

[GoogleCodeExporter]

The issue at hand isn't the algorithm itself, but simply that the data we are 
searching is far too much. The octree was powerful because it allowed fast 
volumetric searching, rather than per-cube.

Thinking about optimiaztions:
1. Rays will only intersect blocks facing air (think: top-most blocks + tunnels)
2. Rays are projected into the view-volume, ever out of it
3. We never want to select air blocks; pointless search

Realistically an iterative ray approach isn't bad: we keep stepping at uniform 
distances, localize the coordinate (i.e. cast to integer), check if within 
bounds, and if it is a non-air block, success. The problem with this though is 
the resolution is a massive heuristic variable and we are not guaranteed to 
find the correct intersecting cube. If our ray barely clips into the corner of 
a cube, it is unlikely we will detect it. What we could do is compute the 
perfect distance each step should take to guarantee intersection checking, but 
that is unknown.

Original comment by nin...@gmail.com on 22 Nov 2011 at 12:04

[GoogleCodeExporter]

Current approach:

Let O be the origin of the casting ray, and D be the direction of the casting 
ray. We know that dy = D.y - O.y, and the same for all other deltas. Since our 
world is in 3D (x, y, z), we can work in three planes: x-y, x-z, z-y. Using the 
trivial line-slope formulate of y = mx + b, we can find the first colliding 
positions (column of cubes perpendicular to the testing plane) of each plane, 
and then find the intersecting cube by apply the intersection of all three 
columns.

Original comment by nin...@gmail.com on 22 Nov 2011 at 12:14

[GoogleCodeExporter]

I always over-complicate things; found a simple solution. I'm back to just 
splitting the world into half's and doing a binary search based on priority 
(closeness of cubes)

Original comment by nin...@gmail.com on 22 Nov 2011 at 12:25

• Changed state: Done