- Home /
Lower-level way to find NEARBY TRIANGLES on the mesh? (Answered.)
The only way I know to find nearby triangles is to simply LOOK IN THE VERTICES ARRAY
OTHER THAN LOOKING IN THE VERTICES ARRAY, does anyone know of any lower-level magic in Unity that gives you adjacent or nearby triangles in a running scene? The 1-ring? THUS FOR EXAMPLE...
Perhaps something at the shader level? Perhaps something at the OpenGL level? Does the 3D pipeline "know" this information in some way ? Perhaps something at the physics level?
Does anyone know the answer to this puzzle? Thanks!
Solution ...
was able to talk with a few people who work at the hardware level of the 3D pipeline. Confirmed that in fact (perhaps surprisingly) the 3D pipeline has absolutely no idea about where any triangles are. End of story. In a word, rendering happens in a vacuum of one triangle. So the answer is very simply NO.
Shared verts in models...
This question has raised the issue of the representation of verts in 3D models.
There appears to be a common misconception that it is "normal for" models to have shared verts where possible, or that verts "should be shared" or "are always" shared where possible.
This is quite wrong, the sharedness of verts in 3D models is random, and is just an artefact of how the model happened to be made. You definitely cannot rely on verts being shared where possible, in 3D.
I grabbed the basic Unity3D "sphere primitive" and looked at it. (Since a sphere is "smooth everywhere" it's a good example of a model where you could share vertices!)
It happens to have 339 verts not shared, that, could be shared. I then modified the model to have EVERY vert not-shared where possible, and then modified it again to have EVERY vert shared where possible.
Note that in all three cases, of course the model works exactly the same inside Unity3D or any other 3D graphics process. In 3D, whether or not verts that-could-be-shared, are shared or not, is totally irrelevant.
I produced a complete Unity project which you can download that includes all three models and lets you spin them, etc. Also, if you ever happen to need a sphere model that has NO shared, or ALL shared, verts-that-can-be-shred, the three models are included in the project.
in fact here is the link to the whole Unity project:
http://www.mediafire.com/?29fyhq2sjtrdj3q
full size images ..
http://s8.postimage.org/65yyvzqjp/339.jpg
http://s11.postimage.org/rju3h79hv/none.jpg
http://s11.postimage.org/9rhq0t70z/all.jpg
Now, this image shows the same model. But this time it has been changed so that there are zero shared verts.
Finally this image shows the same model, but with every vert shared where possible.
Once again here is the link to the whole Unity project:
http://www.mediafire.com/?29fyhq2sjtrdj3q
which also includes the three different meshes ("as seen in unity" "written with all-shared" "written with no-shared").
The app looks like this...you can spin 'em around and so on (my kids love playing with it! heh)
Answer by Statement · Dec 10, 2011 at 12:54 AM
Spatial culling might help you out here. There are many ways of doing this, but one of the more popular ones is probably the Octree. The idea is to store information in the tree about which triangles belong to which nodes. This obviously has a setup phase, but once the Octree is populated, getting the actual nearby triangles is much easier. Say you have triangle #379, and you want to find triangles that are close to it; you'd check which nodes that #379 is overlapping and you'll find all potential matches. So you'll get a subset of the triangles to work with, probably a few orders of magnitude less, which should quicken up your neighbor tests considerably.
You might be lucky and find some existing Octree implementation, but making your own can be a fun experience.
Well if the triangles move around too much, then the cost of building the Octree might weigh out the benefits of fast lookup. But look at it this way. Say you have 1000 triangles and need to check them against each other in your current solution. That's 1000*999 tests. Almost a million tests. With an octree, you'd probably do 2-3 tests per triangle to build the tree. That's 1000*3, 3000 tests. Then during the lookup, you'd have to access nodes, so that's another 3000 tests, and maybe inside each node there are 15-20 triangles so that's another 20000 tests. From a rough guesstimate, you're down from 1000k to 26k tests. But it's also a lot of memory management since you have to move around elements...
And I don't understand how you'd mix in mysql in this. But for mysql related storage, look into morton code curves. They might offer some help there.
The correct answer to the actual question is incredibly simple: the 3D pipeline does not know about triangle location.
But spatial culling generally is completely relevant and would be very useful to anyone new to the field so ticking this answer!
Down with un-answered questions!!
So we cannot assume any spatial structure of the triangles in the triangle array? By that I mean, two consecutive triangles {0,1,2, 3,4,5} for example could be far apart in my 3d space?
Answer by aldonaletto · Dec 10, 2011 at 12:39 AM
Since neighbor triangles in a mesh share one or more vertex (the vertex coordinates, not necessarily the vertex indexes!), one can loop over all triangles comparing their vertex coordinates to the desired triangle vertices - any match means that the triangle is a neighbor (not necessarily in the same plane):
var i: int = myTriangle * 3; // find the vertices of myTriangle...
var v1: Vector3 = vertices[triangles[i++]]; // and store them in
var v2: Vector3 = vertices[triangles[i++]]; // v1, v2 and v3
var v3: Vector3 = vertices[triangles[i]];
for (i = 0; i < triangles.length; i++){
// compare each vertex to v1, v2 and v3:
var v: Vector3 = vertices[triangles[i]];
if (v == v1 || v == v2 || v == v3){ // if any match found...
var nTri: int = i / 3; // get this triangle's number...
if (nTri != triNum){ // and if it's not myTriangle...
// triangle #nTri is neighbour of #myTriangle
}
}
}
NOTE: Different from the float equality operator (==), which only returns true if both operands are exactly the same, Vector3 equality operator returns true if both operands are close enough to be considered equal.
SPECIAL CASE: Some "well behaved" meshes (simple shapes, like Unity's cubes or planes) are constructed to avoid vertex duplication: if two or more triangles lie in the same face and share the same vertex, the vertex is stored only once. In these "well behaved" cases there's a much faster method to find neighbor triangles: loop over all triangles and compare their vertex indexes to the three ones of the main triangle - any match means that the triangle is a neighbor, and is in the same face:
var i: int = myTriangle * 3; // each triangle occupies 3 entries in the triangles array
var v1: int = triangles[i++]; // get v1, v2 and v3,
var v2: int = triangles[i++]; // the 3 vertex indexes of
var v3: int = triangles[i]; // triangle #myTriangle
for (i = 0; i < triangles.length; i++){
// compare each vertex index to v1, v2 and v3:
var v: int = triangles[i];
if (v == v1 || v == v2 || v == v3){ // if any common vertex found...
var nTri: int = i / 3; // find the triangle number...
if (nTri != myTriangle){ // and if it's diff from #myTriangle...
// triangle #nTri is neighbour of triangle #myTriangle
}
}
}
Int comparisons are way faster than Vector3 equality (which requires some internal distance evaluation). Obviously, this method is restricted to the "well behaved" cases above mentioned - if applied to a "badly behaved" mesh, some neighbors will not be found. If you're not sure about your meshes, it's better to compare the actual vertex coordinates using the first method.
Who gives this answer a downvote? Comparing the indices are the first thing that came to my $$anonymous$$d but like aldonaletto mentioned (maybe badly worded) if you have uv-seams or custom-normals for some faces / triangles the second method is the best way to do this without any extra data.
The OP didn't specify how his mesh looks like and writing NEARBY in caps doesn't make it any clearer what nearby means. Only true neighbors (only triangles that share an edge), only touching neighbors, or all triangles within a certain range (not necessary touching)? Distance based solutions are not very robust since you have to know at least the average size of your triangle. If the size vary too much at some spots you won't have any neighbors because the triangles in this area are quite big and somewhere else you might have too much because there are many, very small triangles.
Distance approaches also comes with heavy processing time due to the square-root unless you do a squared distance comparison.
I just want to know the reason for the downvote since it is a solution to the question (might not be the fastest) and it doesn't contain miss-information (except the "badly created" should be a "usual" ;) )
I downvoted, mostly because it doesn't change the time complexity of the algorithm and it doesn't account for the "nearby" triangles criteria. But I guess it's a better solution to distance checking every other point, so I'll leave it unvoted. Happy?
No offence meant / taken ;), You can vote whatever you think is right or wrong but a comment would be nice ;)
Yeah, I always try to add comments, but @Fattie had the comments covered. :)
I don't think this can be solved at the shader level - unless you just want to do some shader stuff with the neighbor triangles (draw them in a different color, for instance). OpenGL doesn't seem to have any function to help doing this job either, thus I afraid you will have to loop all triangles anyway - even if only once to create an auxiliary structure to speed things at runtime, like @Statement suggested, and your question now specifies (btw, I do believe you know how to loop over the triangles - the comments in the code are meant to help those who don't know).
SIDENOTE: Comparing vertices in a per-dimension basis seems faster, but may actually be slower due to the .NET interpretation overhead. I suppose the Vector3 == operator compiles to a single library function call, while any per dimension comparison will compile to lots of CIL instructions.
Answer by Trionet · Apr 24, 2016 at 05:11 PM
I've done this in a project before. I have a parallell list of MeshLinks I call them. They know all of their 3 adjancent triangles. With that you can also do a gathering of all triangles sharing a vertex through the neighbours neighbour and so on.
By also having a is_found boolean in the MeshLink you can check where you were and find any n adjancent triangles in O(n) time. You must ofcourse buffer the MeshLinks before hand. But then it is good to go. By some complex linear algorithms in searching adjancents you may also extend the mesh by splitting one in to 3 or 2 in to 4 without ever having to go through the whole mesh again.
In other words. Have you considered buffering all the adjancency of a mesh? It shouldn't be a performance issue then.
Answer by Tasarran · Dec 12, 2011 at 06:09 PM
There is no quick and easy way to do it, the only way is by comparing spatial coordinates, and this is why:
It might not be possible to explain w/o a picture, if I need to elaborate, I will.
In that cube example, there are two shared verts per square side, and that is ALL the shared points. The corner points are not shared between faces (squares), only between triangles on the same square. Any edge that is hard (such as the actual edges of the square faces) will not share vertices. In a sphere without hard edges, or UV boundaries, ALL vertices WILL be shared by at least one other triangle. Same thing goes for a mesh with no hard edges or UV boundaries.
If you have a cube in Unity, you have 12 triangles. They are paired in two triangles per face, each sharing two verts. Each side will have two triangles, not sharing verts with any of the other faces, except the two verts on the other triangle in the pair. The vertices from the separate sides will not share vertices, even though they are adjacent.
The only way to find out that the triangle on the other side of the hard border is adjacent, is to compare the actual coordinates of the points...
As you can see from the stats that Aldo posted (which are correct), if you have a cube, you basically have six squares that are INDEPENDANT of each other and share NO vertexes between them, and each of those squares is made up of two triangles which share two vertices each. So, Square One has Triangle One, made up of Vert 0,1,& 2. It also has Triangle Two, with Verts 1 (shared), 2(shared), & 3. This would be repeated all around: Square Two has Triangle Three (4,5,6), and Triangle Four (5,6,7), etc. Until you get to Square Six, with Triangle Eleven (20, 21, 22) and Triangle Twelve (21,22,23).
Twenty four vertices, twelve shared.
The point is, even though vertices lie on the same exact coordinate as another point, they are no necessarily shared.
If you move one of those corner vertices, you will rip the cube open, because the vertices on the other two squares are NOT shared, even though they share the same coordinates. You'd have to move all three corners of the involved squares to not rip the cube.
It's not like the real world where you can point to the corner of a cube and say "That point is common to all three sides."
It just doesn't work that way in Unity.
In the end, using search trees (one example of which is discussed above), or other sorts of data-manipulation techniques can help you speed up the process, but when you get down to it, the only way is brute-force looping and comparing.
Leaving it in as an answer...
I know it isn't a solution, but it is an answer; the answer is no, but I elaborate why...
HI @Tasarran, are you there? As we were discussing, your sentence: "In a sphere without hard edges, or UV boundaries, ALL vertices WILL be shared by at least one other triangle." is quite wrong.
If you have a look at the edits to the question, I have made some demonstrations of the issue for you.
In fact the download also includes all three example models. "Never shared" (as is often used by people manipulating mesh), "all shared", and the original unity sphere (which as it happens has a few hundred each way).
Your answer
Follow this Question
Related Questions
What are normals? 1 Answer
Shader wants normal , but the mesh does not have them 2 Answers
How to make sure two meshes have the same vertex count 0 Answers
Holes in procedural mesh 0 Answers