How to quickly eliminate elements with lowest face count?


#67

easiest way to get up and running extending MXS with the SDK is…


#68

interesting story. i’ve looked at my old script and found that i search elements by edges (not vertices). i’ve check max (editable_poly and editable_mesh). they both ‘think’ that an element is a set of faces isolated by edges!!!

delete objects
m = converttomesh (plane widthsegs:2 lenghtsegs:2)
meshop.deletefaces m #{3..6}
update m
meshop.getelementsusingface m 1

in my understanding if faces are connected by a vert they are members of the same element. in all my tools i use this theory.


#69

Updated Tests


#70

Jorge is that for my STL version using reserve(16) on the vert arrays ? or the “traditional” using AdjFaceList & ElementFromFace ? never mind i’ve noticed the links :slight_smile: Try the STL version

here the maxalloc.h file

#ifndef __MAXMALLOC_H__
 #define __MAXMALLOC_H__
 
 #include "maxheapdirect.h"
 #include <memory>
 #include <limits>
 #include "..\resource\resource.h"
 
 //********************************************************************************************
 // stl allocator using max_new
 
 template <typename T> class MaxAlloc
 {
 public:
 
 	typedef size_t	size_type;
 	typedef ptrdiff_t difference_type;
 	typedef T*		pointer;
 	typedef const T*  const_pointer;
 	typedef T&		reference;
 	typedef const T&  const_reference;
 	typedef T		 value_type;
 
 	template <typename U> struct rebind { typedef MaxAlloc[u] other; };
 	MaxAlloc() throw() {}
 	MaxAlloc(const MaxAlloc&) throw() {}
 	template <typename U> MaxAlloc(const MaxAlloc[u]&) throw() {}
 	~MaxAlloc() throw() {}
 	MaxAlloc& operator=( const MaxAlloc& )			{ return *this; } 
 	pointer address(reference r) const				{ return &r; }
 	const_pointer address(const_reference c) const	{ return &c; }
 	size_type max_size() const { return (std::numeric_limits<size_t>::max)() / sizeof(T); }
 	void construct( pointer p, const_reference c )  { new( reinterpret_cast<void*>(p) ) T(c); }
 	void destroy( pointer p ) { (p)->~T();  }
 
 	pointer allocate(size_type n, const void* = NULL)
 	{
 		void* p = MAX_new(n * sizeof(T));
 		if(p == NULL) throw  RuntimeError(GetString(IDS_STL_MEMORY_ALLOCATION_FAILED)); // throw std::bad_alloc();
 		return pointer(p);
 	}
 	void deallocate(void* p, size_type )
 	{
 		if(p == NULL) return;
 		MAX_delete(p);
 	}
 }; 
 
 template <typename T1, typename T2>
 bool operator==( const MaxAlloc<T1>&, const MaxAlloc& ) throw() { return true; }
 
 template <typename T1, typename T2>
 bool operator!=( const MaxAlloc<T1>&,  const MaxAlloc& ) throw() { return false; }
 
 //********************************************************************************************
 // stl allocator using max_mallox
 
 template <typename T> class MaxMallocAlloc
 {
 public:
 
 	typedef size_t	size_type;
 	typedef ptrdiff_t difference_type;
 	typedef T*		pointer;
 	typedef const T*  const_pointer;
 	typedef T&		reference;
 	typedef const T&  const_reference;
 	typedef T		 value_type;
 
 	template <typename U> struct rebind { typedef MaxMallocAlloc[u] other; };
 
 	MaxMallocAlloc() throw() {}
 	MaxMallocAlloc( const MaxMallocAlloc& ) throw() {}
 	template <typename U> MaxMallocAlloc( const MaxMallocAlloc[u]& ) throw() { }
 	~MaxMallocAlloc() throw() {}
 	MaxMallocAlloc& operator=( const MaxMallocAlloc& )  { return *this;  }
 	pointer address( reference r ) const { return &r; }
 	const_pointer address( const_reference c ) const {  return &c; }
 	size_type max_size() const { return (std::numeric_limits<size_t>::max)()/sizeof(T); }
 	void construct( pointer p, const_reference c )  { new( reinterpret_cast<void*>(p) ) T(c); }
 	void destroy( pointer p ) { (p)->~T();  }
 
 	pointer allocate( size_type n, const void* = NULL )
 	{
 		void* p = MAX_malloc(n * sizeof(T));
 		if(p == NULL) throw RuntimeError(GetString(IDS_STL_MEMORY_ALLOCATION_FAILED)); //throw std::bad_alloc();
 		return pointer(p);
 	}
 	void deallocate( void* p, size_type )
 	{
 		if( p == NULL ) return;
 		MAX_free(p);
 	}
 }; 
 
 template <typename T1, typename T2>
 bool operator==( const MaxMallocAlloc<T1>&, const MaxMallocAlloc& ) throw(){ return true; }
 
 template <typename T1, typename T2>
 bool operator!=( const MaxMallocAlloc<T1>&,  const MaxMallocAlloc& ) throw() { return false; }
 
 #endif 

[/u][/u][/u][/u]

A C# version of the algorithm isn’t too bad, but passing the array back to Max takes too long unfortunately and it uses a lot of memory from the Heap.

it’s much the same for the SDK 25% is taken up by append :slight_smile:

just about my final version

typedef std::vector < int, MaxAlloc < int > > ivector;

def_struct_primitive(meshop_getAllElements, meshop, "getAllElements");

Value* meshop_getAllElements_cf(Value** arg_list, int count)
{
	check_arg_count(getAllElements, 1, count);
	Mesh* mesh = get_meshForValue(arg_list[0], MESH_READ_ACCESS, NULL, getAllElements);
	int numv = mesh->numVerts; 
	int numf = mesh->numFaces; 
	BitArray faces(numf);
	
	std::vector < ivector, MaxAlloc < ivector > > verts(numv);
	for(std::vector < ivector, MaxAlloc < ivector > >::iterator it = verts.begin(); it != verts.end(); ++it) it->reserve(16);

	one_typed_value_local(Array* result);
	vl.result = new Array(0);

	Face* faceptr = mesh->faces;
	for(int i = 0; i < numf; ++i, ++faceptr)
	{
		verts[faceptr->v[0]].push_back(i);	
		verts[faceptr->v[1]].push_back(i);
		verts[faceptr->v[2]].push_back(i);
	}
	faceptr = mesh->faces;
	for(int i = 0; i < numf; ++i) 
	{
		if(faces[i]) continue;	
		ivector element;
		element.reserve(4096);
		element.push_back(i);

		for(unsigned int j = 0; j < element.size(); ++j) 																	
		{
			int fi = element[j];
			if(faces[fi]) continue;
			Face& f = faceptr[fi]; 
			for(int k = 0; k < 3; ++k)
			{
				int v = f.v[k];
				if(verts[v].empty()) continue;
				element.insert(element.end(), verts[v].begin(), verts[v].end());  // cannot use iterators with this here
				verts[v].clear();
			}
			faces.Set(fi); 
		}
		BitArray fbits(numf);
		for(ivector::iterator it = element.begin(); it != element.end(); ++it) fbits.Set(*it);		
		vl.result->append(new BitArrayValue(fbits));
	}
	return_value(vl.result);
}

#71

c# sdk to mxs values casting is much slower than c++ sdk.


#72

this is fastest version for me:

{
 	int numf = mesh->numFaces; 
 	int numv = mesh->numVerts; 
 	Tab<Tab verts;
 	verts.SetCount(numv);
 
 	 Tab<BitArray> elements;  
 	 for (int i = 0; i < numf; i++) if (faces[i])
 	{
 		Face& f = mesh->faces[i]; 
 		for (int k = 0; k < 3; k++) 
 		{
 			if (!verts[f.v[k]]) verts[f.v[k]] = new Tab<int>();
 			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);
 
 		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 (!verts[v]) continue;
 
 					element.Append(verts[v]->Count(), verts[v]->Addr(0));
 					delete verts[v];
  					verts[v] = NULL;
 				}
 				fbits.Set(fi);
 				faces.Clear(fi);
 			}
 		}
 		elements.Append(1, &fbits);
 	}
 	return elements;
 }

where faces is all faces.
i’ve excluded return to mxs from computation it this snippet.


#73
verts[v] = NULL;

should be replaced with

delete verts[v];
verts[v] = NULL;


#74

also i’ve understood that AdjFaceList method doesn’t work for me in many cases. if ‘elements’ share a vert they are one elements in my algorithms.


#75

it’s true. i’ve fixed that. thanks


#76

If I ever get it to compile I’ll try it.


#77

scrub that this bloody hopeless :slight_smile:

the files without cgsoc whacky formating


#78

Thank you Klunk! This one compiled without issues and it’s pretty fast. I’ve updated the tests post.

PD: @Admin will someone ever update/fix/improve the formatting options of this forum (among other things)?


#79

yeah, you could quite easily create meshes to slow it back down, models with lots of 32 face fans for example (though you could add a maximum faces per vert hint to the function argument list) but for genearal quad meshes you could even drop it to say 12 to decrease the memory foot print a tad.


#80

should be… but it crashes the function for big meshes with ** system exception **

i’ve reverted everything back to Tab<Tab<int>>…


#81

I use the same logic. Basically, if by moving one face you alter another, they must belong to the same element.

If you convert to poly the model from your example, it will be broken in two elements, and you have to manually weld the vertices to preserve the topology of the mesh.


#82

should be… but it crashes the function for big meshes with ** system exception **

have you tried a “safe” delete Denis? (though I don’t think it’s causing the crash)

if(verts[v]) delete verts[v];
verts[v] = NULL;

#83

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


#84

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


#85

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


#86

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