Plotting implicit equations
Hey guys.
Can anyone point me to a resource (paper/article/page/etc.) on plotting implicit equations? I'm writing a real-time-feedback graphing calculator as an exercise, and the obvious brute-force method of checking every X,Y against the equation is neither fast enough nor accurate enough (since you need to use some sort of epsilon in case the pixel isn't *exactly* on the curve).
Any ideas?
i think marching cubes is good and efficient way to visualize implicit equations
Wikipedia - Marching Cubes
shouldn't be too hard to adapt to 2d if needed.
method is quite old tough, so there might be newer and better ways of doing this out there.
Wikipedia - Marching Cubes
shouldn't be too hard to adapt to 2d if needed.
method is quite old tough, so there might be newer and better ways of doing this out there.
Quote:Original post by rxa
i think marching cubes is good and efficient way to visualize implicit equations
Wikipedia - Marching Cubes
shouldn't be too hard to adapt to 2d if needed.
method is quite old tough, so there might be newer and better ways of doing this out there.
Yup, the 2D method is marching squares. But the question is, how does that help with implicit equations? As far as I can tell, it's for generating a contour from a scalar field...
Quote:Original post by nullsquaredQuote:Original post by rxa
i think marching cubes is good and efficient way to visualize implicit equations
Wikipedia - Marching Cubes
shouldn't be too hard to adapt to 2d if needed.
method is quite old tough, so there might be newer and better ways of doing this out there.
Yup, the 2D method is marching squares. But the question is, how does that help with implicit equations? As far as I can tell, it's for generating a contour from a scalar field...
Exactly. Fill the scalar field with values from any function.
Quote:Original post by phresnel
Exactly. Fill the scalar field with values from any function.
Oh, I didn't quite think of it that way. Interesting, I'll try it!
(Of course, this is still brute force, and won't solve the speed issue. So if anyone has any input on that, it's appreciated.)
As long as you can't analitically break down the function, I guess there is brute force only.
I have experimented with implicits, too. It was for displaying, if you want, 2-manifolds in 3-space (i.e. surfaces in 3d, I was only interesting in ray tracing the parts where f(x,y,z)=0). I used a spatial partitioning scheme with naive structure (i.e. split at median), and inside the nodes I used random sampling of the function to find whether the node represents an interface of the function, or if it's completely empty. I used that information to optimize ray marching.
To some degree, this thing was quite performant and relatively easy to implement, but the traversal/intersection noise was hard to tackle.
I have experimented with implicits, too. It was for displaying, if you want, 2-manifolds in 3-space (i.e. surfaces in 3d, I was only interesting in ray tracing the parts where f(x,y,z)=0). I used a spatial partitioning scheme with naive structure (i.e. split at median), and inside the nodes I used random sampling of the function to find whether the node represents an interface of the function, or if it's completely empty. I used that information to optimize ray marching.
To some degree, this thing was quite performant and relatively easy to implement, but the traversal/intersection noise was hard to tackle.
Do you know about interval arithmetic? Basically you generalize your functions to take intervals [x0,x1] and [y0,y1] and return results of the form [z0,z1]. You define the output range so that z0 is a lower bound for the function over [x0,x1] X [y0,y1] and z1 is an upper bound. It's described more here: http://en.wikipedia.org/wiki/Interval_arithmetic.
Using interval arithmetic you can do a recursive algorithm where you start with large regions of x,y space. You can apply your interval function, and if the output range doesn't contain a solution you can reject whole regions of x,y space. For regions where there may or may not be a solution, you can recurse onto smaller subregions like a quadtree. When your functions are slowly varying this can save a lot of computations.
Here's a paper that may help, and describes some extensions to the interval method.
Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables
Using interval arithmetic you can do a recursive algorithm where you start with large regions of x,y space. You can apply your interval function, and if the output range doesn't contain a solution you can reject whole regions of x,y space. For regions where there may or may not be a solution, you can recurse onto smaller subregions like a quadtree. When your functions are slowly varying this can save a lot of computations.
Here's a paper that may help, and describes some extensions to the interval method.
Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables
Thanks a bunch for the links & info, guys. Definitely some nice food for thought.
I'll come back and post again once I try all these different approaches [smile]
I'll come back and post again once I try all these different approaches [smile]
If you can assume that your level set has just one connected component, then one thing you can do is, after finding a point on it, to just follow the curve around. You can do this with either triangles or squares; what you do is mirror your square/triangle about a face that intersects the curve.
I like triangles (or more generally simplices) for this since I think this actually makes the math a little easier; plus it's faster in higher dimensions since the number of vertices of a simplex grows linearly in the dimension of the space while the number for a cube grows exponentially. It also avoids ambiguous cases.
You'll probably understand the basic idea just after skimming the Wikipedia article on simplicial continuation.
As for finding an initial point on the manifold, that's "just" root-finding, which you do with some combination of grid search, stochastic search, bisection/subdivision, and/or Newton's method. If it's easy to compute the Hessian I might do Newton's method from randomly-chosen starting points, with random restarts if I get stuck. If not, I'd do roughly the same thing but with a Newton variant of Nelder Mead.
I'll also throw an alternative thought out there: Your curve is also described by the Hamiltonian dynamics,
dx/dt = R(pi/2) grad(f)
where f is the function and R(pi/2) is a 90-degree rotation matrix... Actually, this only works so long as grad(f) is never zero; you can partially get around this by working at the level of accelerations or higher derivatives. You get the corresponding equations of motion by taking the fact that f(x(t)) must be zero for all time and differentiating both sides w.r.t time.
[Edited by - Emergent on April 13, 2010 8:49:25 PM]
I like triangles (or more generally simplices) for this since I think this actually makes the math a little easier; plus it's faster in higher dimensions since the number of vertices of a simplex grows linearly in the dimension of the space while the number for a cube grows exponentially. It also avoids ambiguous cases.
You'll probably understand the basic idea just after skimming the Wikipedia article on simplicial continuation.
As for finding an initial point on the manifold, that's "just" root-finding, which you do with some combination of grid search, stochastic search, bisection/subdivision, and/or Newton's method. If it's easy to compute the Hessian I might do Newton's method from randomly-chosen starting points, with random restarts if I get stuck. If not, I'd do roughly the same thing but with a Newton variant of Nelder Mead.
I'll also throw an alternative thought out there: Your curve is also described by the Hamiltonian dynamics,
dx/dt = R(pi/2) grad(f)
where f is the function and R(pi/2) is a 90-degree rotation matrix... Actually, this only works so long as grad(f) is never zero; you can partially get around this by working at the level of accelerations or higher derivatives. You get the corresponding equations of motion by taking the fact that f(x(t)) must be zero for all time and differentiating both sides w.r.t time.
[Edited by - Emergent on April 13, 2010 8:49:25 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement