7 replies to this topic

[DevLiquidKnight]

I was wondering if there is an algorithm that can be used to find the implicit or parametric equation of a 3D model. For instance I saw here: http://www.leweyg.co...ad/impview.html That they found the equation of a Tie Fighter.

Can this be extended to say, find the equation of any surface? If so how is it done, what would be used? In this case, it seems he just used a series of preprocessor's but there must be a simpler way?

Edited by DevLiquidKnight, 12 December 2012 - 04:29 AM.

[Álvaro]

Can this be extended to say, find the equation of any surface?

No, there are surfaces that can't be expressed with implicit equations. For instance, a Möbius strip.

[DevLiquidKnight]

That is true, but it can be expressed explicitly using a parametric surface. Which is why I am asking. I am more interested in how one would go about doing it? Is there any algorithm that does this?

[Álvaro]

What is the input into the algorithm you are imagining?

[DevLiquidKnight]

Some sort of mesh I would guess would be the input.

[Bacterius]

This is kind of like the same deal as trying to use pi as a hash table. Since you heard that pi contains any given sequence of digits somewhere, why not just find the offset of that sequence in pi and use that to refer to the sequence, and boom! Infinite compression. Well, no, not so fast - the offset is usually going to be larger than the sequence itself, a direct result of information theory.

Your problem is essentially trying to approximate an arbitrary triangular mesh with a smaller list of bounded parametric equations. This works fine for simple surfaces, as you've seen, such as spheres, cylinders, tori, boxes, or any combination of those (this includes the detail-less TIE fighter you mention). But in general, this problem is hard.

You could look at NURBS, which are implicit approximations for simple, well-behaved surfaces. The idea is that you choose control points along your desired surface, and interpolate smoothly between them using a form of B-splines. But for complex, irregular surfaces, such as a tree, they don't work very well as they require roughly as many control points as you'd need triangles. So it's not a general-purpose solution, but it works well in practice if you use them for the right surfaces.

In reality, any algorithm which solves your problem will be plagued by the same issue. For well-behaved meshes, it'll work well, but for all other meshes, I suspect it will either:
- produce an output roughly the same size as the input
- take exponential time
- both of those

[rojohound]

There's a good tutorial on it here:
http://www.econym.demon.co.uk/isotut/

Also the K3DSurf forum has a bunch of info to help make the formulas.

[max343]

No, there are surfaces that can't be expressed with implicit equations. For instance, a Möbius strip.

Off the bat this seems wrong as the set of rational surfaces is a subset of the set of algebraic surfaces. Furthermore, the most trivial embedding of the strip into poly-RP^3 (or rational-R^3) doesn't contain any base points. So finding the implicit form _should_ be a matter of technicalities. But I haven't really thought this through.

Some sort of mesh I would guess would be the input.

Hmmmm. Generally this is a topic in algebraic geometry, and it's far from being the simplest question in this relatively advanced branch of mathematics. If I understand you correctly, you're interested in an implicit representation of a piecewise linear mesh. If so then there's a slight problem, you'll have to use Abs in your implicit representation, which basically means that your surface is no longer an algebraic variety. Algebraic geometry deals with algebraic varieties, so you'll have to improvise if you want to use these methods to find your implicit equation.

However, if you're just sticking fingers at this problem, you can unify a few simple implicit surfaces by just multiplicating them in order to obtain a more complex implicit surface. This is basically how most people come up with these models, they just use the ready building blocks (cylinder, sphere, tori, cone, etc...) and mash them together.