How to quickly eliminate elements with lowest face count?


#21

(i’m already home. i was fast as sdk :). it’s not true. i’m just leaving 5min from the office)

well… yeah. it’s very hard to simply beat sdk … but it’s possible to do using smart algorithms. because the pure sdk makes your test for 2000ms

so your algorithm beats sdk.

that’s actually why i’m very skeptical about the MСG.


#22

Hi Denis and Jorge,

Thank you for replying. I guess I have spawned a nice contest between the two of you. But I have the feeling you do that a regular basis here at CGTalk? :slight_smile:

I have tried the script Denis posted, but the function still takes about 2 minutes.

And I couldn’t really follow your discussion from there on.

Jorge, you stated you have ‘a different MXS approach’ that is much quicker. Would you like to share that one?

I’m also really interested in using the SDK, but I haven’t ever used it before, although I’m familiar with Visual Studio and can program quite a bit in C++.

I have already scripted a lot of functions in Maxscript, but I guess the SDK would do all of that much faster.

Only thing is that I don’t know how steep the learning curve is and I’m limited in my time.

Is it doable with the SDK or is one of you open for business?


#23

If Denis is whiling to do a SDK version of it I will. It’s just 20 short lines of code.


#24

sure i want to see your algorithm… i can show my sdk getMeshAllElements function, but i have to disappoint you. there is no anything smart there. it’s just only the right way of using max sdk.
is it OK for you anyway?


#25

I am not asking you to share your code, but if you would like to convert my algorithm to a SDK version and share it here.


#26
(
        	/**********************************************************************
        		DESCRIPTION:	Get all mesh elements
        		AUTHOR:			Jorge Rodríguez
        		DATE:			09.19.2013
        
        		PARAMETERS:
        			node:	An Editable_mesh
        		RETURNS:
        			An Array of Bitarrays, where each Bitarray has the faces
        			of the Mesh element.
        		NOTES:
        			You can speed it up around 30% by unrolling the k loops.
        	**********************************************************************/
        	
        	fn GetAllMeshElements node =
        	(
        		try(heapsize = 536870912L)catch(print "Can't Allocate Heap") -- For large meshes

        		local tmesh = snapshotasmesh node
        		local faces = #{1..tmesh.numfaces}
        		local verts = for v = 1 to tmesh.numverts collect #()
        		local elements = #()
        		
        		for j in faces do
        		(
        			f = getface tmesh j
        			for k = 1 to 3 do append verts[f[k]] j
        		)
        		
        		for i in faces do
        		(
        			element = #(i)
        			for j in element where faces[j] do
        			(
        				faces[j] = false
        				f = getface tmesh j
        				for k = 1 to 3 where verts[f[k]] != undefined do
        				(
        					join element verts[f[k]]
        					verts[f[k]] = undefined
        				)
        			)
        			append elements (element as bitarray)
        		)
        		return elements
        	)
        	
        -- 	gc()
        -- 	st = timestamp(); sh = heapfree
        -- 	elements = GetAllMeshElements $
        -- 	format "time:% ram:% faces:% elements:%
%
" (timestamp()-st) (sh-heapfree) $.numfaces elements.count elements
        )
  Below is a test mesh: 
(
 	with undo off with redraw off
 	(
 		delete objects
 		node = converttopoly (box lengthsegs:10 widthsegs:10 heightsegs:10)
 		polyop.breakverts node #{1..node.numverts}
 		for j = 1 to 4 do polyop.meshsmoothbyface node #{1..node.numfaces}
 		converttomesh node
 	)
 )

– time:1686 ram:29915448L faces:307200 elements:600

Unrolling the k loops it is a little faster:
 -- time:1277 ram:29916136L faces:307200 elements:600

Maxscript select a specific number of elements?
Align UV script optimizations
#27

no problem! wait a little…


#28

Pushing it further, here are the results for a 3.5M faces mesh:

(
   	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
   	)
   )

– time:25877 ram:335283840L faces:3551232 elements:1734

With unrolled k loops:
– time:20391 ram:335283584L faces:3551232 elements:1734


#29

my sdk routine returns

time:4835 ram:74632L faces:3551232 elements:1734

though the bottleneck for sdk in this case is creating the mxs return array.


#30
(

  			    t = timestamp()

  			    m = heapfree

  			    ee = getmeshallelements $

  			    format "time:% memory:% faces:% elements:%
" (timestamp() - t) (m - heapfree) $.numfaces ee.count

  )

  -- time:1787 memory:111168L faces:3551232 elements:1734



#31

what memory usage ?


#32

here is a translation to c++ sdk. (maybe Klvnk can optimize it better)

def_visible_primitive(getMeshAllElements2, "getMeshAllElements2");
 Value* getMeshAllElements2_cf(Value** arg_list, int count)
 {
 	check_arg_count(getMeshAllElements2, 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 numf = mesh->numFaces; 
 		BitArray faces(numf);
 		faces.SetAll();
 
 		int numv = mesh->numVerts; 
 		Tab<Tab verts;
 		verts.SetCount(numv);
 		BitArray vbits(numv);
 		vbits.SetAll();
 
 		 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);
 
 			for (int j = 0; j < element.Count(); j++) 
 			{
 				int fi = element[j];
 				if (faces[fi])
 				{
 					Face f = mesh->faces[fi]; 
 					faces.Clear(fi);
 					for (int k = 0; k < 3; k++)
 					{
 						int v = f.v[k];
 						if (vbits[v])
 						{
 							for (int n = 0; n < verts[v].Count(); n++)
 							{
 								int fi = verts[v][n];
 								element.Append(1, &fi);
 							}
 							vbits.Clear(v);
 						}
 					}
 				}
 			}
 			BitArray fbits(numf);
 			//fbits.ClearAll(); //not needed at all
 			for (int j = 0; j < element.Count(); j++) fbits.Set(element[j]);
 			faces &= ~fbits; // nor really needed
 			elements->append(new BitArrayValue(fbits));
 		}
 		if (pTri && deleteIt) pTri->AutoDelete();
 		return elements;
 	}
 	return &undefined;
 }
 

there are couple things for optimization but it will not change the performance dramatically.
this version is very close by performance to mine.


#33

memory:111168L

(see above… i’ve added the info)


#34

but this memory is mostly the size of returned mxs array of bitarrays.
i don’t use it this way in my tools. i have my own class BitArrayTab (which is an array of only bitarray type items)
in this case the memory usage is almost ZERO


#35

your machine is a bit faster than mine I get

time:4995 ram:74556L faces:3551232 elements:1734
time:6246 ram:74372L faces:3551232 elements:1734
time:7362 ram:74372L faces:3551232 elements:1734


#36

time:8778 ram:74372L faces:3551232 elements:1734

get progressively slower an leaks memory like a sieve !

time:9024 ram:74372L faces:3551232 elements:1734


#37

i have no idea why it’s progressive slower… but honestly i did do a profiling. i could put some sh*t in the code.

about my machine… sorry :slight_smile:


#38

what do you get with a more “trad” version


def_struct_primitive(meshop_getElements, meshop, "getElements");

Value* meshop_getElements_cf(Value** arg_list, int arg_count)
{
	check_arg_count(getElements, 1, arg_count);
	Mesh* mesh = get_meshForValue(arg_list[0], MESH_READ_ACCESS, NULL, getElements);

	AdjEdgeList ae(*mesh);
	AdjFaceList af(*mesh, ae);

	int numfaces = mesh->getNumFaces();
	BitArray faces(numfaces);
	BitArray elementfaces(numfaces);

	one_typed_value_local(Array* result);
	vl.result = new Array(0);
	for(int i=0; i < numfaces; ++i) 
	{
		if(!faces[i]) 
		{
			elementfaces.ClearAll();
			mesh->ElementFromFace(i, elementfaces, &af);
			vl.result->append(new BitArrayValue(elementfaces));
			faces |= elementfaces;
		}
	}
	return_value(vl.result);
}

#39

this is about the same what i do in my sdk version.
i have ~1800ms for 3.5M mesh


#40

yeah it’s difficult to know whether AdjEdgeList & AdjFaceList are not “overkill” for ElementFromFace and quick tests susgests that collecting the final array takes about 25% of the time.