- Home /
Move Objects arround Vertices Array
Hey Guys,
I´m working on a project which includes a deforming terrain. On this ground are walking and running animals and humans. Cause the ground is deforming (gets mountains etc.)... I cannot use a mesh collider for the animals to get good information about their Y-position. (The x-z positions,... in this case the walk direction, is based on an AI-script). The problem about the mesh collider is, that I have to update it 100 times a second (´cause this is the amount of deformations in a second). So I thought a long time about it and came to the conclusion that it could be possible to get the right Y-Position about the following way:
The objects searches the 3 nearest vertices of the ground It looks how the distance to the object relates to another ... So in case of the nearest as base! Take all the values together + 1 .... Than... divide 1 / this combined value Then multiply the new value with the relation value of each value.. And so they will get good results...
Here an example:
Distance for nearest vertices = 0.2; middle vertices = 0.5; farthest vertices = 0.7 The y-values of them are : 0.3, 0.8, and 0.9 So the relation between the nearest and the middle is (0.2/0.5) = 0.4 So the relation between the nearest and the farthest is (0.2/0.7) ~ 0.29 All together: 0.29+0.4+1 = 1.69 1/1.69 ~ 0,59
Now... Distance 1: 1*0.59 = 59 % Distance 2: 0.4*0.59 = 23,6 % Distance 3: 0.29*0.59 = 17,11%
Take these values with the Y-Value of the vertices.... 0.59*0,3 0.236*0,8 0.1711*0,9 All three together: 0,177+0,1888+0,15399 = 0,51979
This means ... that with the object distanced to the 3 nearest vertices in this way... it has the Y-value...0,51979 Do you think this is the right way ?! I know it is really confusing... Maybe you have worked with something similar ... The objects jumps up a little bit... but often it works quite good... i attached a video ... maybe you can give me a better solution how to calculate a Y-value based of an array of the vertices of a deforming mesh.
Thanks for reading guys...
Thanks Fattie,...
I got your idea. I thought a long time about your posting. Up to now my way of your method is slow, too. Cause the Terrain has around 11000 mesh.triangles. So the algorithm to find the right triangles is quite slow for 20-30 objects... Or am I doing something wrong?!
$$anonymous$$y workaround:
Find closest vertex Find all triangles which share this closest vertex Last step "which one encloses the Point"... - sorry I´ve no idea how to solve this...:-/
But all in all it is really slow:-/ isn´t it?!
I really think you should delete it from the Forum web site -- it is not suitable for the forum and much better here.
Answer by Fattie · Jan 12, 2012 at 07:57 AM
Hi tobias !!! I have great news for you.
AHHHHH ! You posted an image showing that THE GRID IS COMPLETELY REGULAR! When seen from overhead, your grid is completely regular like a chess board. Great news!
Before beginning work on the game, renumber all the vertices entries so that they obey a simple relationship to that plain!
So you need only know the XZ coordinates of your character, and you can easily map that to the "grid" of 100x100.
Now you need to find the Y point relative to that square.
If we could trust that the square is not bent: looking at the next image, simply find the height of E and F by leaping from AB and CD respectively. They lerp EF to find the height of X.
Unfortunately the square ABCD is two triangles, so it is bent!
So you must find out which directed side of the line CB is the point X on! Fortunately this is a well known-problem!
http://www.blackpawn.com/texts/pointinpoly/default.html
http://www.gamedev.net/topic/542870-determine-which-side-of-a-line-a-point-is/
http://paulbourke.net/geometry/insidepoly/
here is how to do it:
function pseudocode to find if point (P) is left or right of line (AB) P A B
{
//is "p" on the "right" side of any general directed line AB ?
rightOfLineFactor = (aX-bX) * (pY-bY) - (aY-bY) * (pX-bX);
if ( rightOfLineFactor > 0.0 )
// it is on the right of the line
// in this case travel from G to E in the final step explained below!
else
// it is on the left!
// in this case travel from G to F in the final step explained below!
}
{Just to be clear, in that code fragment, "AB" are local variables! I am not referring to "our" AB. In fact you would use such a routine to decide which side of our line "CB" the point X falls upon. Also obviously, where it refers to "xy" that would be "xz" in the context we are working, of course.}
You have now incredibly quickly found which triangle it is in, on the whole plain. You get another raise at your job at Nintendo!
Finally - again since everything is in a grid - just lerp lerp lerp lerp to find the height. Here's a diagram:
Just lerp along CB (use either the horizontal or vertical travel of X) to find the new point G.
Then finally you must travel from either G to E, or, G to F to at last get the height of X.
So ultimately you have the height of X with incredibly few calculations - awesome.
There are a couple of important points:
(1) the idea of making the grid a completely regular plain, is an incredibly good idea. If you were working at Nintendo they'd give you a raise. In fact it is such a good idea that: say the plain was NOT a completely regular grid: you would have to REMAKE the mesh so that it WAS a completely regular grid. Anything you can do at compile-time that saves you massive amounts of work at runtime, is an incredibly good idea.
(2) To repeat, if you do find that your grid is not regular (say for some reason it goes haywire on one side or whatever) - it fact you will actually have to remake the grid so that it is regular.
(3) If you are not yet familiar with renumbering vertices and so on- you will have to learn how :)
(4) When you are doing (3), there is a very important fact you need to know. Amongst people who are new to working in 3D, there is a common misconception that vertices in 3D models "have to be" shared, or "usually are" shared, when you get the model out of Maya or whatever. In fact that is totally and absolutely wrong. There is absolutely no reason at all that vertices in a 3D model have to be shared (even if they can be).
In practice in the real world any model you get contains a mess of shared/not-shared vertices - you absolutely cannot rely on them being either shred or not-shared.
To repeat, it is critical to understand this point!
If you are new to fooling around with 3D models, it is very important to realise this fact. If you are doing mesh manipulation work, it is SOP that you first have to change the mesh so that it is "all not shared" or "all shared" depending on what is convenient for you and for whatever type of work you are doing.
Now, here is a useful long discussion about it: note the three images:
http://answers.unity3d.com/questions/193695/in-unity-is-there-a-fast-way-to-find-nearby-triang.html
Be sure to download the three models and experiment. So when you rewrite the mesh so that the vertices are regularly counted across and down, in this situation it will be best if make sure they are "all shared". BTW by sheer luck, it may be that your mesh model is already organised so that all the vertices count across and then down in rows -- if so, your job is done.
One final happy point!
n your VERY SPECIAL CASE of a completely regular grid: Notice the pseudo code for "side of line".
In fact, the factors ....
(aX-bX)
(aY-bY)
are always the same!!!!!!!!!!!!!!!!!!!!!!!!!!!! If you wish, replace them with fixed values. You're just got another raise at your job at Nintendo! :) Personally: the solution is so elegant and the code is so fast that I would personally just leave it as the variables, so that if you or anyone uses the code in the future it will work perfectly regardless. Or at least, make a clear comment in your code to that effect. (If you end up using your "side of AB" routine in other situations, you will be annoyed that it does not work if you have the fixed values ! :) )
ONE VERY FINAL POINT!
f you want to be a real-smart arse, it might be that it is NOT GOOD ENOUGH to merely find EXACTLY where the point X sits on the triangles. You may have to smooth it - interpolate - as if the points on the mesh represent some theoretical platonic surface that is smooth.
In the unlikely case that you need to do this, almost certainly the approach to take is to use Catmull-Rom splines to produce an interpolation concept. Fortunately they are very easy to use, and, because of your incredible "regular grid" feature, again very easy in your specific clever situation, so you get yet ANOTHER raise at your Nintendo job. Calculating Catmull-Rom splines (which is easy) is beyond the scope of this question so you'd have to look it up and apply it to your special situation.
In my opinion, you would very likely never do this: if the original grid was not smooth enough: I would simply build a finer grid before beginning the show.
{Indeed, deciding on the size of that grid, is a big part of tuning the game so it works well. In practice you will probably annoyingly have to build a rig for tuning that factor - so you can easily try hundreds of different specific grid sizes. As usual, where building !@£!@$ rigs to tune setup factors, is more work than the game itself!}
Don't forget too: it is very likely you will not just "move" your character to the "new position" you have found on the grid. Almost certainly, you will lerp the position of the character from measurement-to-measurement, as the character goes about his business (just like any movement, at all, in any video game - do not even mention that the "camera follow point" of the character would almost certainly be again smoothed, in all meaningful situations) so it is very likely it would be pointless to further smooth your underlying measuring operations.
But I just wanted to mention it for the record.
Fattie... you are the best. Give me a day or two to realize your idea... Thanks sooo much. This is incredible :)
Hey,... now I transfered your tip to a script. I want to thank you so much. It works perfectly... absolut smooth and incredible fast !!! I reorganized my mesh in the start function so that just the rest has to be calculated in realtime... and it does with 2ms duration :)
that is GREAT!!!! 2 ms is my sort of ms.
anyone reading don't forget this critical tip which may be helpful ...
http://answers.unity3d.com/questions/193695/in-unity-is-there-a-fast-way-to-find-nearby-triang.html
Good luck $$anonymous$$r. T !!
Answer by tobias2000 · Jan 11, 2012 at 11:22 PM
a different solution on page 3 ... chapter 2.6 ....
does anyone get it ?! It´s quite a lot math, but I think it could solve the problem really egelent...
http://www.sci.utah.edu/~csilva/papers/dagstuhl97.pdf
cheerio to all
This paper is not really relevant to you.
If you DO want to find a random triangle which contains a given point (on an irregular mesh), that is a huge amount of work and it is a whole other question. HOWEVER note that you are working in strictly 2D -- from overhead -- XZ only.
Note that that paper does contain in passing at 2.6 an interesting, but not necessarily the best, approach for finding if a point is in a 2D triangle. Again, IF this was relevant to you, you COULD take that approach - but really the whole thing is irrelevant to your job. (If you are big in to finding if a point is in a triangle, there is a huge amount of research and papers on that, and you should check out the classic books by Ericson, Leyngel, etc!)
There is absolutely no doubt that the best solution here is to pre-arrange the grid regularly as seen from overhead. Then ensure all the vertices numbers are even across and down. Finally it is trivial to get a height anywhere using a SQUARE, and just ignoring the triangles. This is an incredibly fast solution and you had a fantastic idea to make the grid regular. So the job is done and you get a raise.
Your answer
![](https://koobas.hobune.stream/wayback/20220613062857im_/https://answers.unity.com/themes/thub/images/avi.jpg)