Order Vertex neighbors


#1

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.


#2

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 :yum:


#3

what’s in “order” ? i.e. what constitutes the first neighbour ? and the next ? and so on


#4

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.


#5

whats adjacent order ?


#6

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