getEdgesReverseEdge


#1

following on from this thread ,there’s another reason why you would want to create your own function, a bug in the mxs function. If you try and get any reverse edge of any face with an open edge where the open edge is before our edge in the face and is also in the edge list to test then it’s not returned.
for example…

(
 	delete objects;
 	p = plane();
 	converttoMesh p;
 	edges = meshop.getedgesusingface p #{8, 16, 24, 32};
 	meshop.getEdgesReverseEdge p edges;
 )

will return #{}
though this can be fixed with the following…

(
 	delete objects;
 	p = plane();
 	converttoMesh p;
 	edges = meshop.getedgesusingface p #{8, 16, 24, 32} - meshop.getopenedges p;
 	meshop.getEdgesReverseEdge p edges;
 )

if you’re interested the fix in the source is pretty simple just need to fix the fix :slight_smile: meshop.cpp in the mxsagni project. change

if (e.f[0] == UNDEFINED || e.f[1] == UNDEFINED) break;  // LAM - 8/23/03 - defect 477328
if (e.f[0] == UNDEFINED || e.f[1] == UNDEFINED) continue; // LAM - 8/23/03 - defect 477328, LAM your fix sucked 

#2

for what its worth i rewrote the function from the idea noted in the comments in the original getedgesreverseedge function using MEdge::Selected. In most cases it’s generally abit slower but wins marginally when the number of inedges gets higher. It think the MEdge::Selected is probably quite slow. has some interesting “flip flop” logic in it anyway :slight_smile:

def_struct_primitive(meshop_getreverseedges, meshop, "getreverseedges");

Value* meshop_getreverseedges_cf(Value** arg_list, int arg_count)
{
	check_arg_count(getreverseedges, 2, arg_count);
	Mesh* mesh = get_meshForValue(arg_list[0], MESH_READ_ACCESS, NULL, getreverseedges);
	int numfaces = mesh->getNumFaces();
	int numedges = numfaces * 3;
	BitArray inedges(numedges);
	ValueToBitArrayM(arg_list[1], inedges, numedges, GetString(IDS_EDGE_INDEX_OUT_OF_RANGE), MESH_EDGESEL_ALLOWED, mesh);
	
	AdjEdgeList el(*mesh);
	Tab<MEdge>& edges = el.edges;
	Face* faces = mesh->faces;
	
	one_typed_value_local(BitArrayValue* edges);
	vl.edges = new BitArrayValue(numedges);

	for (int j=0; j<edges.Count(); j++) 
	{			
		MEdge& me = edges[j];
		if (!me.Selected(faces,inedges)) 
			continue;
			
		if(me.f[0] != UNDEFINED) 
		{
			if(inedges[me.f[0]*3 + faces[me.f[0]].GetEdgeIndex(me.v[0],me.v[1])])
				vl.edges->bits.Set(me.f[1]*3 + faces[me.f[1]].GetEdgeIndex(me.v[0],me.v[1]));
		}
		if(me.f[1] != UNDEFINED) 
		{
			if(inedges[me.f[1]*3 + faces[me.f[1]].GetEdgeIndex(me.v[0],me.v[1])])
				vl.edges->bits.Set(me.f[0]*3 + faces[me.f[0]].GetEdgeIndex(me.v[0],me.v[1]));
		}
	}
	return_value(vl.edges); 
}

#3

btw denis your final function doesn’t work in all cases, you can’t assume all reverse edges have reversed verts.

fn getReverseEdge4 mesh edg = 
 (
 	local  i = (edg - 1)/3 + 1, k = edg + (1 - i)*3
 
 	local vv = getface mesh i
 	vv = [vv[1],vv[2],vv[3],vv[1]]
 	vv = [vv[k+1],vv[k]]
 
 	k = 0
 	for f in (meshop.getfacesusingvert mesh vv[1]) while k == 0 where f != i do
 	(
 		local v = getface mesh f
 		if vv == [v[1],v[2]] then 
 			k = f*3 - 2 
 		else if vv == [v[2],v[3]] then 
 			k = f*3 - 1 
 		else if vv == [v[3],v[1]] then
 			k = f*3
 	)
 	k 
 )
 
 delete objects
 p = plane lengthsegs:1 widthsegs:1
 converttomesh p;
 meshop.flipNormals p 1;
 getReverseEdge4 p 5;

though it’s a trivial fix for a contrived case :wink:


#4

well… #5

fn getReverseEdge5 mesh edge = 
(
	local i = (edge - 1)/3 + 1 
	local n = edge + (1 - i)*3

	local vv = getface mesh i
	local v1 = vv[n]
	local v2 = if n < 3 then vv[n+1] else 1

	local k = undefined
	for f in (meshop.getfacesusingvert mesh v1) while k == undefined where f != i do
	(
		local vv = getface mesh f

		if v1 == vv[1] then
		(
			if v2 == vv[2] then k = 2 else if v2 == vv[3] do k = 0
		)
		else if v1 == vv[2] then
		(
			if v2 == vv[1] then k = 2 else if v2 == vv[3] do k = 1
		)
		else if v1 == vv[3] then
		(
			if v2 == vv[1] then k = 0 else if v2 == vv[2] do k = 1
		)
		if k != undefined do k = f*3 - k 
	)
	k 
)

does it work now?
:wink:


#5

the sdk single edge method…

def_struct_primitive(meshop_getreverseedge, meshop, "getreverseedge");

Value* meshop_getreverseedge_cf(Value** arg_list, int arg_count)
{
	check_arg_count(getreverseedge, 2, arg_count);
	Mesh* mesh = get_meshForValue(arg_list[0], MESH_READ_ACCESS, NULL, getreverseedge);
	int edge = arg_list[1]->to_int() - 1;

	int numfaces = mesh->numFaces;
	Face* faces = mesh->faces;

	int fi = edge/3;
	int ei = edge%3;
	int v0 = faces[fi].v[ei];
	int v1 = faces[fi].v[(ei+1)%3];

	int reverseedge = -1;
	for(int f = 0; f < numfaces; ++f)
	{
		if(f == fi) continue;
		Face& face = faces[f];
		if(face.GetVertIndex(v0) < 3 && face.GetVertIndex(v1) < 3)
		{
			reverseedge = f * 3 + face.GetEdgeIndex(v0,v1);
			break;
		}
	}
	return Integer::intern(++reverseedge);
}

#6

having look into the getedgesreverseedge function a bit more the criticism in the thread I linked to about it being completely unoptimized and poorly written is pretty wide of the mark. For what it does (return all the reverse edges of the input) you would be hard pressed to do it any faster. Yes you can get a single edge quicker, and using the same method to duplicate getedgesreverseedge is faster as long as the input is less the 1/5 of the total number edges after that getedgesreverseedge starts to win hands down. And yes you can collect all the edge pairs quicker but if you still need specific edges you still need to search the resultant array.

something like…


(
	fn GetFacesBorderEdges mObj faces =
	(
		fedges = meshop.getEdgesUsingFace mObj faces;
		fedges * (meshop.getEdgesReverseEdge mObj -fedges) + (fedges * meshop.getOpenEdges mObj);
	)

	delete objects;
	sph = Sphere segs:200;
	converttomesh sph;
	faces = #{1..8600, 15401..25400, 31801..39600};

	t = timestamp()
	sph.selectededges = GetFacesBorderEdges sph faces;
	format "t = %
" (timestamp() - t);
)

would perhaps be a fairer test of it’s performance (though GetFacesBorderEdges might not be the best)


#7

been working in this area again and it seems the fastest way to get reverse edge / adjacent face is a brute force bi directional linear seach. In most general cases adjacent faces have similar indices. so the core routines would look like this…

inline int getVertIndex(DWORD* vi, int v) { return *vi == v ? 0 : *(vi+1) == v ? 1 : *(vi+2) == v ? 2 : 3; }

#if 1
inline int getEdgeIndex(DWORD* vi, int v0, int v1)
{
	int v0i = *vi == v0 ? 0 : *(vi+1) == v0 ? 1 : 2;
	int v1i = *vi == v1 ? 0 : *(vi+1) == v1 ? 1 : 2;
	return (2 * (v0i + v1i - 1)) % 3;
}
#else
inline int getEdgeIndex(DWORD* vi, int v1, int v2)
{
	int v1i = v1 == vi[0] ? 0 : v1 == vi[1] ? 1 : 2;
	int v2i = v2 == vi[0] ? 0 : v2 == vi[1] ? 1 : 2;

	if((v1i == 0 && v2i == 1) || (v1i == 1 && v2i == 0)) return 0;
	if((v1i == 1 && v2i == 2) || (v1i == 2 && v2i == 1)) return 1;
	return 2;
}
#endif

inline int getReverseEdge(Face* faces, int nfaces, int fi, int a, int b)
{
	int ui = fi + 1,  di = fi - 1, redge = UNDEFINED;
	while(di >= 0 || ui < nfaces)
	{
		if(ui < nfaces)
		{
			Face& face = faces[ui];
			if(getVertIndex(face.v, a) < 3 && getVertIndex(face.v, b) < 3)
			{
				redge = ui * 3 + getEdgeIndex(face.v,a, b); break;
			}
		}
		if(di >= 0)
		{
			Face& face = faces[di];
			if(getVertIndex(face.v, a) < 3 && getVertIndex(face.v, b) < 3)
			{
				redge = di * 3 + getEdgeIndex(face.v, a, b); break;
			}
		}
		++ui; --di;
	}
	return redge;
}

inline int getAdjFace(Face* faces, int nfaces, int fi, int a, int b)
{
	int ui = fi + 1,  di = fi - 1, adjface = UNDEFINED;
	while(di >= 0 || ui < nfaces)
	{
		if(ui < nfaces)
		{
			Face& face = faces[ui];
			if(getVertIndex(face.v, a) < 3 && getVertIndex(face.v, b) < 3)
			{
				adjface = ui; break;
			}
		}
		if(di >= 0)
		{
			Face& face = faces[di];
			if(getVertIndex(face.v, a) < 3 && getVertIndex(face.v, b) < 3)
			{
				adjface = di; break;
			}
		}
		++ui; --di;
	}
	return adjface;
}

it even performs well on mesh with complete randomized faces. and is only marginally slower than cached AdjEdgeList routine.