Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


#ActualBacterius

Posted 12 December 2012 - 10:14 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

#2Bacterius

Posted 12 December 2012 - 10:09 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
- all of the above

#1Bacterius

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 complicated mesh, 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
- all of the above

PARTNERS