Lower-level way to find NEARBY TRIANGLES on the mesh? (Answered.)

[Fattie]

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 …
I 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 …

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)

[aldonaletto]

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*];*

for (i = 0; i < triangles.length; i++){
// compare each vertex to v1, v2 and v3:
var v: Vector3 = vertices[triangles*];*
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][1] 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*; // triangle #myTriangle*
for (i = 0; i < triangles.length; i++){
// compare each vertex index to v1, v2 and v3:
var v: int = triangles*;*
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.
[1]: http://unity3d.com/support/documentation/ScriptReference/Vector3-operator_eq.html

[Statement]

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.

[Trionet]

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.

[Tasarran]

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.