Jump to content

  • Log In with Google      Sign In   
  • Create Account


Finding Implicit Equations From 3D Objects


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 DevLiquidKnight   Members   -  Reputation: 834

Like
0Likes
Like

Posted 12 December 2012 - 04:26 AM

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.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12494

Like
0Likes
Like

Posted 12 December 2012 - 04:38 AM

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.

#3 DevLiquidKnight   Members   -  Reputation: 834

Like
0Likes
Like

Posted 12 December 2012 - 04:46 AM

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?

#4 Álvaro   Crossbones+   -  Reputation: 12494

Like
1Likes
Like

Posted 12 December 2012 - 04:56 AM

What is the input into the algorithm you are imagining?

#5 DevLiquidKnight   Members   -  Reputation: 834

Like
0Likes
Like

Posted 12 December 2012 - 11:49 AM

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

#6 Bacterius   Crossbones+   -  Reputation: 8318

Like
3Likes
Like

Posted 12 December 2012 - 10:08 PM

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

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#7 rojohound   Members   -  Reputation: 106

Like
1Likes
Like

Posted 13 December 2012 - 12:28 PM

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.

#8 max343   Members   -  Reputation: 340

Like
0Likes
Like

Posted 13 December 2012 - 05:20 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS