[share] Eliminate redundant replicated vertices with jit.gl.model + gl.multiple
If you find yourself with duplicate (triplicate, quadruplicate, etc!) vertices when using [jit.gl.model] and sending its matrix to set the vertex positions of a [jit.gl.multiple], and then when you rotate an individual vertex and get a render like this:
I made a patch that eliminates all redundant vertices. Let me know if there's any issues with it.
with most complex shapes you get an average vertex reduction of about 6x. I just tested this with the duck.dae. Normally just piping it's position matrix into jit.gl.multiple, I was getting around ~10fps, but using my reduction patch I was able to get ~32fps. And the render output looked exactly the same.
is it possible to use this reduced vertex matrix and still get a good [jit.gl.mesh @poly_mode 0 0] or will there be gaps between the faces?
super cool! thanks for sharing.
do use this technique with jit.gl.mesh you would also have to provide an index matrix to tell the mesh how to use the vertices to draw triangles.
you might want to consider creating an abstraction for this and submitting it to the Toolbox:
https://cycling74.com/community/?q=toolbox
Cool. I'll look into the index mesh. You know any links that would give me more insight into this?
I was considering submitting this, but I'm a little hesitant. Besides never having submitted an abstraction before and what that process is like, I don't think my method of filtering through [coll]s is all that great. I'm definitely open to better solutions.
Cheers
i guess I don't really understand how jit.gl.mesh draws faces from an input matrix. I'm guessing whatever the reason, that's why jit.gl.model outputs a matrix of redundant vertex points...? Does jit.model also draw those points as well or are they only present in the output matrix?
considering the action is only performed at initialization, i think your method is fine.
yes, if an index matrix is not supplied, then vertices must be duplicated when drawing a triangle mesh. the mesh loading library we use for jit.gl.model (assimp) doesn't support index matrices, so that's why gl.model doesn't use them.
for info on the index matrix, you can refer to the opengl documentation on index buffers:
http://openglbook.com/chapter-3-index-buffer-objects-and-primitive-types.html
index buffers are useful to reduce memory, but don't generally offer a speed increase (from my understanding).
ok, index buffer matrix is pretty straightforward. your link and the contributions here: https://cycling74.com/forums/jit-gl-mesh-index-matrix-example/ clear it up. But those examples show how to manually create one. The next step is automating the process. I've been looking at the vertex coordinates in alignment with alternative groupings of sets of vertices/indices, to see if any patterns pop out so I can generate some math to organize an index buffer. Any guidance with this? I want to be able to load any model and have the vertices reduced (which it already does) and the index buffer built. Is something like this possible? I'm guessing a script/code will be the easiest way of going about it.
Nice.. thank you!
there was an issue with model that have multiple drawgroups. this newest patch should have the ability to successfully build gl.multiple and gl.mesh for all drawgroups or for a single drawgroup. I also cleaned up a bunch of the objects and patching made things a little more clear.
i also fixed the index array issue, which i already mentioned in the facebook group and the c74 article, but not here. Scattered releases, but the one posted here should be the final one, before some brave soul wants to make an external out of it or reprogram it in [js]
if you try to reduce the vertices of a larger model and you get the spinning wheel (or whatever the windows equivalent is) and Max is hanging/stalling, give it some time. It's trying to iterate a huge list from the output matrix and store it into the coll. I've successfully run this with models that have greater than 50,000 vertices, although those took 5 minutes of an unresponsive Max app. Then when i've reindexed them, that took about 2 hours... definitely looking for more optimized methods if anyone has insight.
cheers
Meshlab (http://meshlab.sourceforge.net/) for poly reduction and you will never look back. Try 50-100+ megs Obj's decimated in seconds, probably millions of vertices, I work sometimes with 3D scan data. of course you wont get those result on a machine from 2000, but if your machine is fairly modern 2013 and up you should be fine. All it does are meshing operations, hundreds of them, and it does them extremely well highly recommended, it's my go to for complex geometry. PC & Mac.
I never used Meshlab, I use Meshmixer, but the problem is that whenever you import the 3D model into jit.gl.model, the amount of vertices drastically increases for the reasons discussed above.
Also few months ago I made a java external that removes all the duplicates from the geometry matrix that comes from jit.gl.model (you can find it here https://cycling74.com/forums/jit-gl-model-keep-mesh-coherent-when-applying-vertex-manipulations/) but it doesn't create an index matrix. Therefore it is useful only if you work with points.
@T
Hey very cool, yours processes it much quicker than mine does! However I think it might be eliminating too many vertices. Check the attachments. Really eager to figure out what's going on here, maybe I'm doing something wrong, because really happy at how quickly this processes the matrix as compared to mine.
@Greg Finger
Hey Greg, I think I know what is causing the problems in your example. My algorithm was made for models that not symmetrical in more than one dimension (although I didnt know that until now:). So it works with ducks, mushrooms etc but as it looks like not with spheres. I always work with non-symmetrical shapes so I never encountered the problem.
The way my algorithm works is approximately like that:
if (Ax-Bx)+(Ay-By)+(Az-Bz)=0, then ignore B
...which is good enough criteria for non-symmetrical models or models that are symmetrical only across one dimension.
As soon as I will have time to check out your indexing I will add that to the java code, fix the bug and share it here. It might take a while because time is not my friend and I am a total Java beginner. So if anyone else wants to join the party, please do:)
i can't help with the java, but i can explain the indexing a little. the original matrix from the gl.model is already organized in groups of 3 for the index array. So the first three points is the vertices for a triangular face. The second group of three is another face and so on. So in my programming I made sure to keep the original array of points organized exactly how it came out of gl.model, and just referenced the reduced final vertex array: in the original array, every vertex changed its xyz-position value to the index number of its matching vertex in the reduced vertex array.
say the original array was
0, 0 0 0
1, 0 0 1
2, 0 1 0
3, 0 0 0
4, 1 0 0
5, 0 1 0
the reduced vertex array would of course be
0, 0 0 0
1, 0 0 1
2, 0 1 0
3, 1 0 0
and the re-indexed array would be
0, 0
1, 1
2, 2
3, 0
4, 3
5, 2
not sure if you needed that explained or you already knew it, but my patching is just a convoluted way of comparing these lists/arrays
Thanks a lot Greg, this is very helpful! One more thing: did you noticed by any chance if these duplicates/triplicates/etc. are spread across the whole matrix (that comes from jit.gl.model) or is there any logic behind it...like for instance "the duplicate would be never more than 3/whatever cells away from its twin"? I guess it can be anywhere really...?
So i took the matrix output from my simplest icosphere, and assigned index values for each vertex based on the order which they appear. Naturally this gives the first 3 vertices index values of 0, 1, 2, respectively. From there you can see when each vertex is repeated, and when a new one is brought in. For instance, vertex index 1 gets completely used (5 times) before index 6 or greater even gets established.
I grouped them in three for easier comprehension.
0 1 2
0 3 1
3 4 1
4 5 1
5 2 1
6 2 5
7 2 6
7 0 2
8 9 10
8 10 3
10 4 3
10 11 4
10 9 11
9 6 11
9 7 6
9 8 7
0 7 8
0 8 3
4 11 5
11 6 5
with the last patch i posted, you can visualize how the index array is grouped (and gets built) by: turning on jit.world, dropping in a high polygon count model, clicking the bang for reduce vertices, turning on the gl.mesh and then clicking the bang for rebuild index. i've attached an icosphere with a higher polygon count.
you can also check [coll unSort] inside [p vertexReduction] > [p matrixConcat+CompileIntoColl] to see the original vertex xyz position data in the order that the model outputs.
i'm not quite sure the logic it uses to output/index/sort vertices.
Here is the hopefully debugged Java external with added index matrix. My very ruff estimation is that it works "1000 times" faster as the Max version. What would take Max weeks to process (literally) this external does in 5 to 15 minutes. Therefore I find it essential when working with larger models.
Thanks again to Greg Finger for sharing the essential knowledge behind index matrix!
And let me know if there will be any problems
Wow! this is super fast. very impressive. just tested it quickly, but later on i'll give it some deeper testing.
i'm not sure if you saw my latest (june 4) post here: https://cycling74.com/tutorials/getting-better-framerates/
it seems like you had the same idea as me with saving the vertex position/index array jitter matrix with the "write" function. Definitely a smart idea.
Another thing i added was the original texcoord + normal (lighting) arrays. So instead of culling the original 8 planes down to just the first 3 planes and then doing my organizing / elimination process, i kept all 8 planes of information and still organized it and eliminated duplicates according to the first 3 planes, but made sure to have the other 5 planes still attached to the surviving vertices.
Another thing you'll want to add is something to deal with the multiple drawgroups. Take dwarf1.ms3d for example (you can find it just by searching dwarf in the Max Browser). It has four drawgroups: Shoulder, Head, Torso, Axe, in that order. The gl.model by default is on drawgroup 0, which outputs all the drawgroup in order sequentially. So using your patch, you would only see the Axe, since that is the last drawgroup matrix that is output. I think i ended up solving this by, when i first [bang] the gl.model, it queries the model to see how many drawgroups there are. Then it essentially creates a large matrix by combining all matrices it receives. Once it receives the number of matrices equal to the drawgroup amount, then it pushes out that whole thing to be processed for duplicate elimination. --This can still be done outside of java pretty easily, not sure you need to integrate this into your code--
I think with the addition of texture coordinate + lighting normal support and also support of model's with multiple drawgroups, this external you made should be officially supported by Cycling74 or at least be added to their Package Manager (or Toolbox). It's very very awesome.
If any of this is still unclear, i can try to explain it better. If you knew this stuff already, sorry about all the words :P
cheers!
here's an example of multiple drawgroup support using max objects:
also just wanted to note, that a 58k vertex object that took 2 hours 15 minutes to process in my method (3 minutes to reduce vertices, the rest of the time to build the index array), took about 4 seconds total in yours. wow.
Hey Greg, thanks for your feedback!
I am aware of the multiple draw-groups and the openGL matrix format but personally I never work with them. I get my models from 123D catch app ---> Meshmixer so I never have more than one draw group. Also I am into points and lines rather than surfaces so I stick to geometry only.
However, thank you for adding the multiple draw-groups to the patch and when I find some extra time I will probably add texture and light planes. It makes sense if there is a need for that.
Btw, in case you would like to increase the performance of your patch (which includes texture and light planes), I guess you could use a great external xray.jit.cellvalue (http://www.mat.ucsb.edu/whsmith/xray/xray.jit.cellvalue.html). What this external does is that it keeps only cells in the matrix that are specified by the "map" in its right inlet. So for instance If you send in a "10x1" matrix with a map " 3 4 5" the output will be a "3x1" matrix that holds only cells 3, 4 and 5 from initial matrix. So in your case I assume you have already have the map (which cells to keep)...However, xray.jit.cellvalue unfortunately runs only in 32-bit mode.
ah, gotcha. ya i'd say if you had the time to include texture + normals definitely do it. I know it'd help me a lot, but i'm sure it could come in use to others. I'm very serious when i say this is a worthy addition to either the Package Manager or Toolbox. It's great work. A friend of mine has some java knowledge, so i'm sure he can take a look about the textures/normals as well if you're busy.
i've heard xray being mentioned a lot, guess i should check it out. 32 bit is definitely unfortunate though.
xray is supported on 64 bit. download it via the package manager.
Thank Rob, that is totally awesome news!
@Greg: I'll try to find some free time next week but I would be more than happy if your friend could help.
sent you an email (using the email address found on your website) about the code. this thread would get really messy discussing bits and pieces about the code, so better to do it with email, and then post the finished product here.