@Patrice Bertrand (PatB),

Quick note to say, +1 for moving away from BMesh.

This was mainly done because we had to get all modifiers working with BMesh but it gave a big performance hit too.

Provided cleaned up version of the patch which compiles in recent master.

Previous cleanup had error (source/target mixup), move into its own function svert_from_mvert.

Theres a problem I ran into, if you enable merge and increase the level, it gives this assert.

BLI_assert failed: /src/blender/source/blender/blenlib/intern/edgehash.c:94, edgehash_keyhash(), at 'v0 < v1'

	abort	/usr/lib/libc.so.6		0x7ffff50c1788	
	edgehash_keyhash	edgehash.c	94	0x1257dff	
	edgehash_lookup_entry	edgehash.c	171	0x1257dff	
	BLI_edgehash_lookup_p	edgehash.c	340	0x1257dff	
	CDDM_merge_verts	cdderivedmesh.c	2486	0xf9d574	
	arrayModifier_doArray_2	MOD_array.c	829	0xd9f345	
	applyModifier	MOD_array.c	1114	0xda0347

Whats happening is edges with 2 of the same verts are being created. Infact this looks more like a bug in CDDM_merge_verts (it doesn't support 2 different vertices pointint to the same target).

With only a small change this assert can be resolved.

 	/* now go through and fix edges and faces */
 	med = cddm->medge;
 	c = 0;
 	for (i = 0; i < totedge; i++, med++) {
		const unsigned int v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
		const unsigned int v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
		if (LIKELY(v1 != v2)) {

snip

Didn't commit this since I'm not sure its correct, since the resulting mesh can still be corrupt. (checked and with old code its not corrupt).

Attached file, with array_modifier_cleanup_f34cb95_v2.diff and the snipped above:

• load:
  array_crash.blend1 MBDownload
• press the Apply button.
• enter editmode
• crash/assert (Im using a debug build)

The error is that a loop has a vertex which is not in the loop's edge, see bmesh_core.c:

	if (!BM_vert_in_edge(l_iter->e, l_iter->v) || !BM_vert_in_edge(l_iter->e, l_iter->next->v))
		err |= (1 << 20);

So we need to know if CDDM_merge_verts needs to be able to support more use-cases, or if the data passed to it is incorrect.

Thank you for your thorough examination Campbell. I'm off for 3 days, but will do my best to correct this next week.

I cannot reproduce the crash. I checked out latest master, applied Campbell's array_modifier_cleanup_f34cb95_v2.diff, and loaded sample crash blend file, but no crash.

However, I do agree with the proposed patch in CDDM_merge_verts. actually, it seems likely that this was the intention of the programmer: not "I will skip edges where v1==v2", but rather "I will skip edges where both ends are mapped to the same point".

There is an important note in the header CDDM_merge_verts:

This function is currently only used by the Mirror modifier, so it skips any faces that have all vertices merged (to avoid creating pairs of faces sharing the same set of vertices). If used elsewhere, it may be necessary to make this functionality optional.

And indeed, this leads to a bug in situations such as this simple use case: take a cube, delete the YZ face to the right (with the greatest X value), then add array modifier on X axis with merge. The YZ face to the left disappears, because all of its vertices have been merged. But in this case, it is no good reason for deleting the face. So as the note says, this behaviour needs to be optionnal.

Another important remark is that doubles removal picks the first target vertex that it finds within the merge distance. Thus, the order in which candidates are tested matters, and it may be that in some cases this new algorithm will pick another nearby vertex as the former algorithm. Would this matter ? There is no precise promise as to which vertex will be picked, but it could cause (very minor) differences in old blend files.

Note that tot_time_doubles must be initialized at 0 not 1. This has no consequence since it is only there to measure the total time of calling find_doubles().

I propose a tiny optimization: write the sum_v3 result into each SortVertsElem instead of the coordinates, this will use up less memory, and do fewer calls to sum_v3.

A much more potent optimization would be to cache the vertex-doubles mapping of chunks N on N-1, and apply it again, with just a translation on vertex indices, to N+1 on N. On large meshes, the calls to find_doubles() add up to approximately half of the total time of do_array(). So this would be almost a 50% gain. Do you see any risk that it gives wrong results ? (Of course only for array chunks, not caps, or first-last).

I was not using a debug build, that's why I did not reproduce the assert(v1!=v2) crash. Ok now.

@Patrice Bertrand (PatB), suggest to first get this working without crashing before optimizing further.

Of course after that its worth exporting ways to speed it up more.

cache sum_v3 is simple speedup.

Not sure what you mean cache the vertex-doubles mapping of chunks N on N-1. I suppose you mean cache doubles in the middle of the array?

This might not always work, if the array scales... but we could just ignore that and treat all doubles as 1.0 scale.

@Campbell Barton (campbellbarton): I follow up on the patch's comment.

First, the remaining bug in CDDM_merge_verts, just a few lines below the one you had corrected. Indeed your correction was trashing edges where vertices are mapped to same target, but when handling polys, the mpolys using these edges were not dumped, which would lead to a corrupt mesh. So the same correction is added in the poly loop handling:

for (j = 0; j < mp->totloop; j++, ml++) {
 			unsigned int v1, v2;
 
 			med = cddm->medge + ml->e;
 			v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
 			v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
 			if (LIKELY(v1 != v2)) {

It seems to not crash anymore, as far as I can tell.

I included the translation of doubles mapping, which is quite simple and has a huge impact for high counts. Indeed I would have forgotten about scaling, which will increase the distances past the threshold. Now translation occurs only when there is no scaling.

I do have a tough problem that remains. As I mentionned, the way CDDM_merge_verts is dumping faces when all vertices are mapped is not correct for the array modifier. The correct behaviour, as I see it is: if all vertices are mapped AND the target vertices make up a face that is identical (same vertices, same order, or reverse order), then dump the face.

So I worked on implementing this as an alternative mode in CDDM_merge_verts. This required a function CDDM_poly_compare, that compares two polys of the mesh, after applying mapping to the first one. This function was very complex to write in a clean way, gave me a real headache. It works now, but shows poor performance, really spoiling all the benefits.

What we would need to make this faster is an equivalent of edgehash.c for polys: polyhash.c. But polys are much more difficult to compare than are edges. We could use a simplified hash table just to check that a match is possible. For example if we just hash together all vertices indices and check in the table that there is some poly with this hash. Then another poly can quickly be tested for possible existence. If the check is positive, then we do a full comparision. What do you think ?

It is not an easy task, but it seems to me that is the only way to quickly check the delete-face condition in the array modifier.

Just an additionnal point. When using caping, and in edit mode, the mesh of the cap objects are displayed, while in the original implementation they are not. Do you have any idea why ?

I found the cause of abnormal delay. Will post a correct and faster diff soon. Including using a GHash for identifying same polys fast.
In the meantime, no need to look at it... thanks.

@Campbell Barton (campbellbarton): I follow up on the latest patch's comment.

The latest release is super-fast now. On this test file F84638}, based on a Suzanne with subsurface at level 2, thus about 80kV, I get the following benchmark:

The Suzannes are overlapping,

1. With Merge ON, distance is 0.1

1.1) No Caps, Count=50
Old array modifier: 3.53 seconds
New array modifier: 0.24 seconds, ratio is x15

1.2) With Caps (same Suzanne used as cap start & end):
Old array modifier: 6.76 seconds
New array modifier: 0.27 seconds, ratio is x25

Behaviour of old modifier with caps is slow in an abnormal way, this has been reported recently.

2. With Mergo OFF,

2.1) No Caps, Count=50
Old array modifier: 3.11 seconds
New array modifier: 0.028 seconds, ratio is x110

2.2) With Caps (same Suzanne used as cap start & end):
Old array modifier: 3.13 seconds
New array modifier: 0.025 seconds, ratio is x125

Now I do have some afterthoughts that I wish to share here.

1. Comparing 2 polys with arbitrary number of loops, one of them being mapped, is very complex. I strived to make it clean and readable, but it still is complex and thus not very satisfactory. Has this need been met and handled before ?

2. So as to limit the number of full polys comparisions, I am using a GHash object for a first level parsing. The Ghash is using MPolys as keys, the hash function is the sum of all vertices, and the compare function adds comparing a Xor of all vertices. I did not find anything better, since 2 polys can be identical with different starting loops, and different direction. Still this first-level parsing of identical polys does give a significant filter. In the case of the Suzanne sample file, I get:
3. processed polys: 425 088
4. polys with all vertices merged: 27 083
5. polys that matched in GHash: 1585
6. polys that matched complete comparision: 1364

So this GHash stuff avoided 95% of full poly compare.

All of this is pretty much optimized, but it is complex. So the question is: is this level of optimization worth all the added code, which of course comes with added possible bugs...

@Patrice Bertrand (PatB)

Checked the new patch and it works very well, though I didn't go over new merge code line-by-line to validate.

Only one concern with the changes, that is with CDDM_merge_verts,

I'd rather not have CDDM_merge_verts accept args depending on each modifier, Instead pass in an argument to define which cases to test for.

For eg it could take a flag, rather then naming flags ARRAY or MIRROR, name based on what they do, can add comments within enum { ... } noting flags typical usage.

This makes the function a bit more re-usable and we can add more flags if we need without having some other part of the code call CDDM_merge_verts with ARRAY arg, just because that happens to match up with what it requires at the time.

Apart from this minor stuff, it seems good for inclusion in Blender.

Included a cleanup patch:

• use camel case for struct name.
• no need to pass dm to cddm_poly_compare
• style.

Cleaned up diff:

Diff ontop of your diff (only so you can see what changed):

@Campbell Barton (campbellbarton):

Thanks. I'm glad you find it ok, and thrilled to get my first contribution into blender. Maybe second if the noise/displace makes it !

I will try to get the minor style things right on my next job.

You are right regarding CDDM_merge_verts not using the caller's name as an argument but something more meaningful instead. It could be CDDM_MERGE_VERTS_DUMP_IF_MAPPED and CDDM_MERGE_VERTS_DUMP_IF_EQUAL. It's a bit long, but quite meaningful.

Last thing would be to remove the old_if_odd_count / new_if_even_count switch, and the one remaining printf, and it's ready to go !

One additional minor point: do you agree that

dist3 = 3 * dist;

Could be replaced by:

dist3 = 1.733 * dist;

Where 1.733 is > sqrt(3).

Indeed if sqrt(x^2 + y^2 + z^2) < d, then the greatest possible value of (x+y+z) is, because of symetry, reached with x=y=z, and thus at sqrt(x^2 + x^2 + x^2), which is sqrt(3) * |x|.

It won't have a big impact on performance, but it is mathematically valid, and could be used in other remove_doubles stuff.

@Patrice Bertrand (PatB)

Rather just leave it at 3 for now, and prepare the patch for inclusion in master (after 2.71 release).

Then we can check on other changes.

@Campbell Barton (campbellbarton): oups! I just realized I forgot your cleanup patch of april 24th. Sorry. I will integrate it and post a new patch quickly.

Hey, great work!
The performance improvements look nice.

I wonder if you also plan to look into other changes here, like make the Array Modifier create instances. That would be really nice. Sorry for the off topic, but I thought I mention this, in case this is related to this refactor.

@Thomas Dinges (dingto) What do you mean "make the Array Modifier create instances" ? Like what's happening when you apply a modifier ?

I hear the big thing that could happen one day with respect to modifiers is having them node based. Although in most cases the modifier stack being sort of linear (one after the other) is fine. But with a node based scheme, you could for example have an array node, then a separate-loose-parts node, then a select-random-part node that picks one loose part, then another modifier applied to the selected loose parts. Or another use case would be a duplicate node with outputs A and B, then different modifiers applied to each outputs, then a Join node. Or different displace-only modifiers merged into a mix node...

My latest diff related to the new merging is maybe a little far-fetched, and still experimental. I wouldn't want it to delay the rest, which I believe is ready for the trunk.

Another word on the present algorithm based on a filter on the sum of coordinates: my tests show that the number of actual distance comparisions is linear with the distance used in sum compare, so that replacing 3*dist with sqrt(3)*dist divides the number of comparisions by almost 2. And the profiler says this actual distance comparisions is the single most executed line in the merge.

@Patrice Bertrand (PatB). are you available to update the patch and prepare for inclusion in master?

@Campbell Barton (campbellbarton) : Yes, sure, what should I do exactly ?

@Patrice Bertrand (PatB): As far as I know, when you use the Array Modifier at the moment, the results are not instanced for the render engines. So if you take the default cube, and add an array modifier, you then have N cubes, but they are all different meshes, instead of 1 instanced mesh, which saves memory then during render time. @Campbell Barton (campbellbarton) probably knows this better. :)

@Thomas Dinges (dingto): I don't know what you mean, can you explain some more ? It seems to me the array modifier, in its new implementation, does the same as all modifiers do: it takes a derived mesh as input, and produces a derived mesh as output.

@ dingto, array modifier is a generate modifier as is its purpose is to generate geometry that can be take into account by other modifiers.

When Brecht talked about removing dupliverts old code, we claimed for not removing it without a feature to replace it.
Instances distributions are managed by particles or dupliverts.

Of course a tool like array modifier to manage instances would be interesting and easy to understand.
In fact, I already often use dupliverts with a duplivert parent mesh made with array modifier.

But is modifiers' stack a good place for tools about instance ?

I guess you know what Instancing means? :) http://en.wikipedia.org/wiki/Geometry_instancing

When you have 4 spheres, duplicated with ALT+D, the objects share the same mesh datablock, the render engine will then instance the spheres, and we don't waste our memory.
If you use the Array Modifier to duplicate the sphere, the result is not instanced. I don't know how to simplify this more.

Modifiers don't support instancing, if someone plans to work on this rather discuss elsewhere.

@Patrice Bertrand (PatB), The patch doesn't apply to master, would you be able to update it and double check it works correctly? (also remove/comment printf's and generally make it ready to commit)

@PadB,

Committed temp-array-modifier branch rB6647a3517e7865c6936d81d084630ffb9811612f

To finalize & test the patch, its less trouble then commandeering the patch off each other,

I'd like to give you commit access to Blender, I think it would be good if you could finalize the patch in the branch and then commit to master.

Being you coding on this modifier, wouldn't it be a good moment to add a randomization parameter to each transform channel? Once i saw an addon with this trivial yet useful feature.

+1 for giving @Patrice Bertrand (PatB) commit rights! :D

@Patrice Bertrand (PatB), just wanted to give a quick feedback:
We're now able to create huge scenes that we were not able to create before because we needed so much geometry it always crashed blender - now we don't even feel that the array mod is working. This is outstanding and much much appreciated! Great work, thanks so much.

I'm personally still hoping to have the mod stack rewritten soon to get your other modifier idea accepted - mabye @Campbell Barton (campbellbarton) can put this on the table on the next dev talk.

Thanks a lot for your feedback @Thomas Beck (plasmasolutions), this is really a heartwarming reward.

I do hope all the work on noise modifier will not be trashed, I am convinced it brings usefull features, randomness being key to realism, and many expressed interrest.

As for the talked-about node-based modifier design, it would probably start with a design document giving overall purpose and principles. I would be very interrested to read how knowledgeable developpers see it, and would be happy to participate.

As I wrote earlier, I don't understand why things like noise/displace modifier should be kept on hold waiting for global modifier overhaul.

There is also one interresting sideline development that I believe deserves some more thoughts, although I did not retain it in the final array modifier. It's a totally new algorithm for finding doubles within a mesh, that gives huge performance gains for very heavy meshes (see comment here above for details). Which also made me think that "remove doubles" could be a modifier all by itself. It would not alleviate the need for a "merge option" within other modifiers such as mirror or array, because checking for merge in a specific use case can be optimised better (such as translating merge mapping as we do in the array modifier). But there are cases where the possibility of stacking modifiers and finally removing doubles would be very usefull. The "remove doubles" modifier would be very easy to implement now, since we have all the algorithms ready, after work on the array modifier merge. If it was developped, then it could, and should, use my proposed algorithm whenever nverts is above some threshold, around 50k. But I'm digressing here.

I just discovered this patch, and i want to thanks you a lot @Patrice Bertrand (PatB)
As @Plasmasolution said, this is outstanding and super usefull for my everyday work. Great job !

About remove doubles modifier:
As we are in place for it, I take Array modifier as example.
Merging array ends after curve deform on a circle is such a problematic case.

A supplementary merge/remove doubles modifier would fit here very well.

Sry for posting a little offtopic. (good idea!@Patrice Bertrand (PatB))

@Campbell Barton (campbellbarton): do you support the idea of a dedicated "merge doubles" modifier. It would fit in the general idea that what can be done as an non-reversible operation should also be possible to achieve through a modifier. If OK, I can deliver this within a week or two.

@Patrice Bertrand (PatB), re: remove doubles modifier - Blender modifiers almost never make doubles.

(Edge-Split is exception, but in that case it makes no sense... so split then remove)

@Karja Krähwald (karja)'s Example is a good one, In that case we could have a remove-doubles modifier, that only takes boundary-verts into account.

Are there any other examples where you might use a remove doubles modifier? - I'd like to check on possible uses first.

Campbell, this would also be useful when using the solidify modifier and you need some areas of the object to have zero thickness (right now you can't do that as otherwise you get Z-fighting and shading errors).

Otherwise the scene might require more objects, and sometimes it is useful to have one big object for some scene elements as opposed to a bunch of smaller ones.

Note that although we call it "remove doubles", (as in "problem"), the operation is really "remove near vertices". In that sense, even though few modifiers would actually create doubles, many could generate very close vertices. The array modifier would do this simply if using scaling (through a scaled empty object), then each instance gets smaller and smaller, and vertices get nearer. Shrinkwrap modifier could also quite often yield vertices that are very close to each other and could be simplified by a "remove doubles".

Maybe a "limited dissolve" modifier could be useful too. The idea in both cases being to simplify the final result of modifiers.

Is there a reason why this differential is still open (apart from talking about new ideas ;) )? Since it was commited I guess we can close it (in that case @Patrice Bertrand (PatB), simply 'abandon' it).

I will prepare a few examples where i think its useful, but it takes 1 or 2 days.

Have experimented with some ideas.
Main purpose i have found in operations where you want to

• tear
• pluck
• peel
• break
• (and so on)

geometry, and of course the other way around.

Benefits i see are especially for animation and deform on smooth meshes. With a "merge"-modifier you could assign overlapping edges to 2 or more different vertexgroups and move them with bones or curves asunder.

A merge option for meshobject + meshobject (like target object) could handle more - Linked Duplicates with Mask would be responsible for more fragments, so you have only one mesh to work on.
Also comes in place where two sets of modifiers should not affect eachother (Solidify always takes whole mesh) and 2 objects are needed, but result object shall appear as connected.
A little like Array cap settings without modifier dependencys. I dont know if this is feasible.

@Karja Krähwald (karja)
Added: T41748, please move discussion on remove-doubles modifier there