koobas.hobune.stream
Looking for triangles attached to a vertice
Hey guys,
taking a mesh into consideration. If I want to see all triangles a vertice is attached to, I did the following.
Loop start until triangle.length
if myVertice == mesh.vertices[triangle[i]] // found the same vertice in anouther or the same triangle
This works, but I don't like the idea of itirating to all Vertices for triangle length every time. Is there another way to solve this Problem?
Thanks, Sinith
Hey guys, thx for the quick answers.
I am still in the design phase and going through some ideas and tests before blueprinting everything.
Well the idea is to do a 3d pathfinding on a big sphere and I need this - find the vertices near me - feature. I want to have several objects doing this pathfinding simultaneously and they have to check on every vertices the next near vertices... So I guess this can cause some performance issues. So I could just set it up and then go for "just more memory" solution...
What I have been doing the last hour was to create a sphere from scratch. Here I have the solution to assign each vertices a latitude and a longitud. Just like earth I can calculate very easy the vertices next to the one the characters are currently on.
I just though maybe there is a neat little function that finds the vertices and triangles of near the current one.
Or maybe I just asked the question wrong.
Reading out Glurth answer now... this is a good approach as well. would definitely save up some time. I'll look into that.
Cheers and again thx for the answers! Singt
converted your answer to a comment. Also upvoted Q and comment, hopefully giving you enough rep to make comments now ;)
In general you want to cache the various arrays that the mesh object provides in a local variable when you need to access them more than once.
// C#
var verts = mesh.vertices;
var triangles = mesh.triangles;
for(int I = 0; I < triangles.length; I++)
{
if (vertex == verts[triangles[i]])
// ...
}
This I understand. Is the only way to look for the near triangle a iteration with a for loop? Has triangles not some kind of logic that can be implemented to make this faster?
No, there's no faster way. Triangles are just a collection of index data. If you already know the index of a particular vertex it would be faster since you don't need to compare vector3 values but only indices.
Actually in most cases when you try to find something in an array / collection there's no way around iterating through it. This is already the fastest you can get. Though a single for loop though a couple of thousand triangle indices is extremely fast anyways.
What's the exact problem you have? Do you have performance problems? Have you checked the profiler?
Here is some basic implementation:
internal static List<List<int>> neighborhood($$anonymous$$esh mesh)
{
int numVerts = mesh.vertices.Length;
int numTris = mesh.triangles.Length;
int[] localTris = mesh.triangles;
/// For each mesh vertex (index) store a list of the triangle indices
List<List<int>> vertexToTriangleList =
new List<List<int>>(mesh.vertices.Length);
/// Init list
for (int i = 0; i < numVerts; i++)
{
vertexToTriangleList.Add(new List<int>());
}
/// Store containing triangle indices for vertices
int stride = 3;
for (int i = 0; i < numTris; i += stride)
{
vertexToTriangleList[localTris[i + 0]].Add(i);
vertexToTriangleList[localTris[i + 1]].Add(i);
vertexToTriangleList[localTris[i + 2]].Add(i);
}
return vertexToTriangleList;
}
$$anonymous$$y meshes contain roughly 2,000,000 triangles - Runtime is 0.4 second. I'm not sure if my implementation is the most efficient (Intel Core i7-4700$$anonymous$$ @ 4 GHz)
If this actually causes you performance problems, you can always use the solution of " use more memory".
-At startup: build an array the same size as your mesh vertex array.
-Each element of this array stores a set/list of triangles the vertex belongs to.
-Once built, you can simply index to this array (using the vertex index) to get the list of triangles the vertex belongs to, without any need to loop.
Since you mentioned pathing, keep in $$anonymous$$d: multiple mesh vertices CAN potentially have the same position. In this case, they probabaly have different normals, but pathing won't care about that. Your initial loop could compare vertex positions, without worry about how long it takes.
