[Closed] Order Vertex neighbors
Can anyone suggest an algorithm to ‘order’ vertex neighbors (direct connected indexes)? Or a way to collect neighbors in order?
the order is a list where every next index in the list connected to the previous (if it’s possible). Let’s do it for Mesh where we have only triangle faces.
here is something very simple without any optimization… it’s more like a pseudo – code:
vv =
(
m = $.mesh
num = m.numverts
vv = for k=1 to num collect #()
for k=1 to m.numfaces do
(
_vv = getface m k
append vv[_vv[1]] #(int _vv[2], int _vv[3])
append vv[_vv[2]] #(int _vv[3], int _vv[1])
append vv[_vv[3]] #(int _vv[1], int _vv[2])
)
for k=1 to num do
(
do
(
add = 0
for n=2 to vv[k].count do
(
if vv[k][1][1] == vv[k][n][1] do
(
insertitem vv[k][n][2] vv[k][1] 1
vv[k][n] = #()
add += 1
)
if vv[k][1][1] == vv[k][n][2] do
(
insertitem vv[k][n][1] vv[k][1] 1
vv[k][n] = #()
add += 1
)
if vv[k][1][vv[k][1].count] == vv[k][n][1] do
(
append vv[k][1] vv[k][n][2]
vv[k][n] = #()
add += 1
)
if vv[k][1][vv[k][1].count] == vv[k][n][2] do
(
append vv[k][1] vv[k][n][1]
vv[k][n] = #()
add += 1
)
)
if add > 0 do vv[k] = for p in vv[k] where p.count > 0 collect
(
if (p[1] == p[p.count]) do deleteitem p p.count
p
)
)
while (add != 0)
for n=2 to vv[k].count do join vv[k][1] vv[k][n]
vv[k] = vv[k][1]
)
vv
)
any ideas about smarter algorithm or/and optimization are welcome
what’s in “order” ? i.e. what constitutes the first neighbour ? and the next ? and so on
the first ‘neighbour’ in the list doesn’t matter. I only need all other be connected to the previous if it’s possible. also direction of the order doesn’t matter as well.
when i say ‘ordered’ i mean list of neighbours in adjacent order.
i’m sure there was an old nvidia program to calculate the an optimal triangle strip rendering a given closed mesh in directx or opengl.
can’t find it but something like this seems helpful:
https://www.researchgate.net/publication/221546511_Fast_Mesh_Rendering_Through_Efficient_Triangle_Strip_Generation