On Thursday, 22 September 2016 19:43:35 UTC+1, Jamie Clarkson wrote:
> Sure, as you say for your use case it might be best for you, and you might 
> need different information from the test anyway.   Usually in a fast ray 
> tracer you'd pre-calculate the inverse of the direction components and 
> store them (since you do LOTS of ray-bbox intersections for each ray while 
> traversing the bounding hierarchies) then the slab test is pure 
> multiplication and adds.  The branchless version then replaces all branch 
> tests with min/max operations.  I'd be interested if your div free version 
> is faster and doesn't need the precalculation/storage costs.
> Cheers,
> Jamie
I'm currently fiddling with the "no-division" version - it's not optimised. 
It doesn't actually avoid the division, unless all that is needed is a 
true/false (intersects) return - for a function that also returns the 
scalar along the ray the division is still needed, but it's not in the 
boundary check 

Easier to show : Original code (in my first post)

front_n = (x_front - s.X) / v.X
ripY = s.Y + front_n*v.Y
ripZ = s.Z + front_n*v.Z

if (front_n > 0) && (ymin <= ripY && ripY <= ymax) && (zmin <= ripZ && ripZ 
<= zmax) { ..etc ..

becomes  (completely non-optimized)


front_n_d = (x_front - s.X) // non-divided version
positive = (v.X > 0)


if (front_n_d > ) == positive &&
((ymin-s.Y)*v.X <= front_n_d*v.Y)==positive &&
(front_n_d*v.Y <= (ymax-s.Y)*v.X)==positive &&
((zmin-s.Z)*v.X <= front_n_d*v.Z)==positive &&
(front_n_d*v.Z <= (zmax-s.Z)*v.X))==positive {


(terms such as ymin-s.Y are reused many times .. I haven't remove them here 
as it obscures the math.)

the obvious alternative is to add an extra if positive .. else .. to 
simplify all those ==positive out of the condition.. *either way I'm not 
expecting it to be faste*r, but the *numerical errors should be much less*, 
since each side has only 1 multiply and 1 add/subtract, whereas the 
original form had all the math on one side of the boundary condition - 
consisting of a subtract followed by a divide ie (x_front - s.X) / v.X (or 
a multiplication by a reciprocal which adds more potential numerical 
error), compounded into an additional multiplication and add ie s.Y + 
front_n*v.Y - so in terms of numerical accuracy the non-multiply version 
should be much better.

however if the condition is true the divide is still required to get the 
scalar if needed :

front_n = front_n_d / v.X

So for multiple rays the pre-store of the reciprocal of v.X, v.Y, v.Z still 
make sense. 

For the usual raytracing bounding boxes a few errors, or slightly oversized 
bounding boxes are fine, but in my case the ray-box intersection is used to 
generate indexes for a 3d voxel array - so errors here can throw an index 
out of range (about 1 in 1 million rays, but still a run time panic for me)

You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Reply via email to