Interval Arithmetic
Author
I'm trying to speed up a ray marcher I quickly wrote by using interval arithmetic, but I'm not sure I quite understand what I am doing.
Given that I have a volume in 3d space defined by 3 intervals, one for each axis, plus an equation for an implicit surface, say a sphere. If I substitute the variables for the sphere with the intervals and evaluate the function, then I get another interval. If the high value of the interval is less than zero then volume is entirely inside the sphere, if the low value is higher greater than zero then the volume is entirely outside of the sphere. Otherwise the volume straddles the sphere. Is this correct?
Also, is it possible to perform an operation between an interval and a scalar? eg [3, 5] + 4 = [7, 9]? If so are +/-/*/'/' all done in a piecewise fashion as you would between two scalars?
[Edited by - Thergothon on April 8, 2008 9:29:39 AM]
You can look at OpenTissue. They have an interval library which might be interesting...
Quote:Original post by Thergothon
If I substitute the variables for the sphere with the intervals and evaluate the function, then I get another interval.
Bad news, this doesn't work if you merely substitute the variables. The typical problem is x = [-1, 1] and f(x) = x - x = 0, yet f([-1,1]) = [-2,2] includes points which are not actual results.
You will have to either under-approximate or over-approximate the actual result (the easiest solution with intervals is to over-approximate). Then, you can prove your property only one way (for instance, if the interval is over-approximated, then not being in the approximate interval means you're not in the actual interval either, but you can be in the approximate interval without being in the actual interval).
Quote:Also, is it possible to perform an operation between an interval and a scalar? eg [3, 5] + 4 = [4, 9]? If so are +/-/*/'/' all done in a piecewise fashion as you would between two scalars?
Yes, '+' and '-' work this way. Division and multiplication are slightly more complex, since you have to compute the minimum and maximum of the four products:
[a,b] * [c,d] = [min P, max P]; P = { a*c, b*c, a*d, b*d }
Author
Thanks for the help guys. I just realized I also made a mistake in the first post with the addition example, which probably made my question more confusing than it should have been. Embarrassing. Sorry.
Anyway, this is what I've got for interval/scalar arithmetic:
is that correct? All the interval/interval stuff I've figured out from various papers I've read, they just seem to skip over interval/scalar stuff.
Finally, for testing intervals against functions in N-dimensional space, should I be substituting all the intervals in all axes into the function simultaneously, or should I be testing each axis independently?
Anyway, this is what I've got for interval/scalar arithmetic:
interval& interval::operator += (float scalar) { a += scalar; b += scalar; return *this;}interval& interval::operator -= (float scalar) { a -= scalar; b -= scalar; return *this;}interval& interval::operator *= (float scalar) { if(scalar < 0.0f) std::swap(a, b); a *= scalar; b *= scalar; return *this;}is that correct? All the interval/interval stuff I've figured out from various papers I've read, they just seem to skip over interval/scalar stuff.
Finally, for testing intervals against functions in N-dimensional space, should I be substituting all the intervals in all axes into the function simultaneously, or should I be testing each axis independently?
Correct in theory, incorrect in application. Naive application of floating point arithmetic can lead to inversions in the upper and lower bounds of your interval due to all the special case situations that can happen when working with inexact floating point arithmetic. Since it looks like you're using C++, seriously consider giving boost::interval a try.
Author
I'll give boost::interval a try now that I have a grasp on how this stuff actually works. Thanks.
Edit: Interval arithmetic is amazing. My ray tracer for implicits is now well over 30 times faster than it was. Time to check out affine arithmetic.
[Edited by - Thergothon on April 8, 2008 10:05:17 PM]
Edit: Interval arithmetic is amazing. My ray tracer for implicits is now well over 30 times faster than it was. Time to check out affine arithmetic.
[Edited by - Thergothon on April 8, 2008 10:05:17 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
