Notifications
Clear all

[Closed] How to quickly eliminate elements with lowest face count?

Denis, which is your fastest implementation so far with returning array?

1 Reply
(@denist)
Joined: 10 months ago

Posts: 0

this is what i have finally stuck with:

def_struct_primitive(meshop_getAllElements, meshop, "getAllElements");
Value* meshop_getAllElements_cf(Value** arg_list, int count)
{
	check_arg_count_with_keys(getAllElements, 1, count);
	Mesh* mesh;
	BOOL deleteIt = FALSE;
	TriObject *pTri;

	if (is_node(arg_list[0]))
	{
		INode* node = arg_list[0]->to_node();
		TimeValue t = MAXScript_time();
		pTri = GetTriObjectFromNode(node, t, deleteIt);
		if (pTri)
		{
			mesh = &pTri->GetMesh(); 
		}
	}
	else if (is_mesh(arg_list[0])) 
	{
		mesh = arg_list[0]->to_mesh();
	}

	if (mesh)
	{
		int level = is_number(key_arg(level)) ? key_arg(level)->to_int() : (key_arg(level) == n_verts) ? 1 : (key_arg(level) == n_faces) ? 3 : 3;

		int numf = mesh->numFaces;
		BitArray faces(numf);
		faces.SetAll();
		int numv = mesh->numVerts; 
		Tab<Tab<int>> verts;
		verts.SetCount(numv);

 		Array* elements = new Array(0);  

		for (int i = 0; i < numf; i++)
		{
			Face& f = mesh->faces[i]; 
			for (int k = 0; k < 3; k++) verts[f.v[k]].Append(1, &i);
		}

 		for (int i = 0; i < numf; i++) if (faces[i])
		{
			Tab<int> element;
			element.Append(1, &i);
 			BitArray fbits(numf);
			BitArray vbits(numv);

			for (int j = 0; j < element.Count(); j++) 
			{
				int fi = element[j];
				if (!fbits[fi])
				{
					Face& f = mesh->faces[fi]; 
					for (int k = 0; k < 3; k++) 
					{
						int v = f.v[k];
						if (vbits[v]) continue;

						element.Append(verts[v].Count(), verts[v].Addr(0));
						vbits.Set(v);
					}
					fbits.Set(fi);
					faces.Clear(fi);
				}
			}
			if (level == 3) elements->append(new BitArrayValue(fbits));
			else if (level == 1) elements->append(new BitArrayValue(vbits));
		}
		return elements;
	}
	return &undefined;
}

it gives me an option to get elements of verticies for almost free.

all memory is used by data for return to mxs anyway

there is no leak in system memory

with slight modification this method might be changed do return elements for specified faces or only one face

Thank you Denis. I’ll give it a try. I have a possible optimization which gives me 30% in C# but I am still working it out, haven’t touched this code for a very long time until now.

My original MXS function does return both faces and verts with no time penalty almost :). I just trimmed it for this thread.

Have this one too in the old MXS

There are a lot of information and tests here, so I decided to do an all in one test to have a better understanding of the performance of the different implementations.

     Test where performed on Max 2014 Win 7 using this object: 
(
         	with undo off with redraw off
         	(
         		delete objects
         		node = converttopoly (box lengthsegs:17 widthsegs:17 heightsegs:17)
         		polyop.breakverts node #{1..node.numverts}
         		for j = 1 to 5 do polyop.meshsmoothbyface node #{1..node.numfaces}
         		converttomesh node
         	)
         )
     [MXS (original algorithm)]( http://forums.cgsociety.org/showpost.php?p=8027554&postcount=26) 
     time:22641 ram:17302352L faces:3551232 elements:1734
     
     [MXS (unrolled k loops)]( http://forums.cgsociety.org/showpost.php?p=8027554&postcount=26) 
     time:16795 ram:335369624L faces:3551232 elements:1734
     
     [SDK (Klunk's SDK Implementation)]( http://forums.cgsociety.org/showpost.php?p=8027866&postcount=55) 
     time:1064 ram:111304L faces:3551232 elements:1734

SDK (Klunk’s STL Implementation)
time:575 ram:111384L faces:3551232 elements:1734

     [SDK (Denis's SDK Implementation)]( http://forums.cgsociety.org/showpost.php?p=8027929&postcount=58) 
     time:1011 ram:111304L faces:3551232 elements:1734
     
     C# (returned array)

time:1056 ram:2175576L faces:3551232 elements:1734

     C# (void - algorithm only)
     time:970 ram:728L faces:3551232 elements:undefined
Page 7 / 7