Auto 'verlet' cages discussion

Automatic cages are nearly possible. I made a simple function that examined a single surface mesh and attempted to create "sensible" links from it's basic shape.

- iteriate through the verts
- for each vert, create a verlet
- for each verlet link 3 more by:

looping through
trying to snap to 90 degree (or 45 degree) angles and prioritising the closest.

By doing this, we can be fairly sure of some stability, but at the end of the day I believe the best approach is to create a series of simple pre-defined primitive stable cages.

A cube, tetra, etc... and perhaps a small utility to import your model and fit the cage to it.

On the other hand, perhaps it's possible to examine the model and create a rough approximation of the shape, and fit an already existing stable cage to it.

Any thoughts?

Another thought is exporting your model with a cage mesh called "cage". The triangle topology would already provide the stable links you need. This seems most promising (except you cannot specify wheels or weights). A problem arises trying to discover what the crosslink would be.

Then when imported, we parse, get the info and destroy the hidden cage mesh.

i started to work on this idea but came to the conclusion that in order to make it stable AND fast as possible i decided to just make them by hand.

now if a person were to write an editor where you could make/delete links and test them in the same environment then you would have a winner.

The tetrahedron should be a stable shape. And you can make a cube out of tetrahedrons in a few different ways. I would search Google for code to take a 3D solid and convert it to a set of non overlapping tetrahedrons. I'd be willing to bet that some methematician has already solved the problem.

Try searhcing here you might find a paper on making a model into tetrahedrons. Or hell, search for verlets, you might find some papers on those that are of use.

http://citeseer.nj.nec.com/cs?cs=1&q=tetrahedrons+AND+vertex&submit=Documents&co=Expected+Citations&cm=50&cf=Any&ao=Expected+Citations&am=20&af=Any

I found one paper which referred to "tetrahedradias...tionsomething"

Anyhow, here's some papers with that word. I think it means to make something into a collection of tetrahedrons.

http://citeseer.nj.nec.com/cs?cs=1&q=tetrahedrization&submit=Documents&co=Expected+Citations&cm=50&cf=Any&ao=Expected+Citations&am=20&af=Any

I have allready done that in my 2D engine... If somebody has any use for this I will reveal what I've learned...

Symmetrical objects are easy... they are very stable, but I had to find a way to do very assymetrical objects, so I just auto-link every point to every point. I also have an all-purpose editor for creating objects and manual spring insertion. I have researched this alot and I think there's no allpurpose solution for this.

Secondly, some objects need supporting invisible points, that keep the object from bending. For example one hard object to model is a long pilar for example. If you just all the pilar's points together, it will wobble. You need invisible extra points for both sides of triangles, that will keep the structure stiff.

And for stability issues, I discovered a great thing, that hasn't been mentioned anywhere in the articles about mass-spring systems:

Sort your springs in lenght order and update the constraints from shortest to longest. That will provide more stability and the structures don't even invert so easily.



A screengrab from my editor. (btw. thanks yappy for Xlnt 2, I will register soon)


Here's a typical pilar structure... notice the yellow circles. They are supporting points. Also the weights of different particles affect the stability of the structure.

I believe that for realistic simulation of objects, you really have to link all particles to all particles. That ofcourse is out of question, if your going to make vertex-level sollution for collisions. But if you use spheres, then 10-point object for example would have 45 springs. And the springs are pretty fast to calculate, so that's not so big of a deal.

I was gonna write a evolving thingamugummie that "evolves" constraints, eventually converging on an optimal configuration. What would be the best way to export this data if I made a system to figure it out?

Any kind of text file I expect... I am doing an auto constraints thing with mixed success too, and will post results if anything useful comes out of it.

i could see a way to train a neral net/genetic algorythm to do it for you i.e. you try one set of constraints, adjust its fitness based on accuricy/number of nodes etc... after a while you could get a fairly accurite one to use, it would be slow so you couldnt do it dynamicly in your prog but instead of an editor

of course, it couldn't be dynamically done, as every new variation on the structure would need to be simulated. Nueral nets could work, but in this situation, artificial evolution is probably optimal. You coud even add artificial spedups that check to see how many "succsessful" configurations have certain constraints, and then replicate those constraints alot.

On a side note, I'm doing revision 3 of my system. further "haloified" ie, split into Many Many files. Although I hope to make the system easily upgradable, as the user will add some fields in various types, add an include statement, and add a new file with the new part. So basically, you will be able to have different constraints and different collision entities. Oh yeah, and for any that don't know, my system uses very fast custom collisions that are mostly mathamatical. ie, equation for sphere, equation for quad. I still need to add friction to non quad objects though.

Also a side note, I've made my system quite easy to setup and use. Exspecially with my new convenience functions:

Graphics3D 640,480,0,2

Include "cam code.bb"
Include "verletlib.bb"
Include "verlet entities/cube.bb"
Include "worlds/quad box.bb"

SeedRnd MilliSecs()

st3.structure=vcube.structure()
repetitions st3,10

PositionEntity cam,0,-50,-200

While Not KeyHit(1)
 update
 dophysics
 positionreps 
 docam
 RenderWorld
 Flip
Wend

hmmm. experemented slightly with doing evolving constraints. I originally thought of simply running two entities at once with the same velocities-one with all constraints, and one with several missing. yet even with a single one missing, the structure behaved too differently overall. It looked fine, but accumelated errors to rapidly. I think I have a solution. I could make it so that the system fed an algorithm the current old/new coordinates of each verlet. then it would do all the physics, and do all the constraints. After that, you store all the positions, and do the same thing, only with some of the consttraints missing. then add the sum of the differences to the cumalitive total for this arrangment of constraints. Each run could be like 1000 steps or somthing. at the end it would divide the total displacement by the number of constraints. The lower your score is, the better. I believe this would pretty much work. If the object completly fell apart, the score would be horrible, as when it tries it with all constraints on, the verlets would move dramatically, adding a bunch to the score. This is kinda difficult to implement, but it would be really, really, cool. If it works, I might even try to port it to other systems, as for them stable objects may be differently configured.

I *think* I figured out how to do the above. Have two verlet entities, each with the same configuration. One of them is the constraint configuration being tested, while the other has all constraints. Then, simply run the first entity, take all the old/new values from the 1st one to the second one. run the second one, and findo uot the cummalitive error, which is added to the total error. after 1000 steps or somthing, the sim is stopped, the fitness recorded, and the next configuration tested. After all the configurations have been tested, it might tally up the score of each configuration using that constraint. This gives you a good idea of what constraints most add to the stability of the structure. You could create a bunch of configurations, each with the top constraint as well as some random constraints. Some configs would be completly random, and some might be crossovers.