Jump to content
  • Advertisement
Sign in to follow this  
nullsquared

Plotting implicit equations

This topic is 3080 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
Quote:
Original post by nullsquared
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...


Exactly. Fill the scalar field with values from any function.

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!