How to quickly eliminate elements with lowest face count?

#1

Hi everyone,

I have 3DSMax meshes with a face count between 1.000.000 and 3.000.000 faces, consisting of multiple elements.

I would like to keep the elements with the highest face count and delete the rest.

I already have a function that detaches all elements one by one, then counts the face count per detached element and only keeps the element that has the most faces.

Unfortunately this function is really slow, and 3DSMax is sometimes using up to 50 gigabytes of RAM to do the detaching.

So I wanted to ask you if there is a smarter way to do this.

I thought of several other ways, for example shoot a ray from a viewport and select the element that is hit by the ray. But I have no clue of how to do that :slight_smile:

Or could 3DSMax emulate a mouse click somewhere in the viewport and select the element that is click on?

Because I always know where the largest element is located, so that could be a help.

Thanks for any feedback!

#2

#1 collect all elements (set of faces that makes an element)

fn collectElements node =
(
    local getElement = meshop.getElementsUsingFace
    local elements = #{}
    local faces = #{1..node.numfaces}

    while not faces.isempty do
    ( 
        doIt = on
        for face in faces while doIt do
        (
             append elements (getElement node face)
             faces -= elements
             doIt = off
        )
    )
    elements
)
elements = collectElements node -- where node is a mesh object

#2 sort elements by numberset

fn sortByNumberset a b = (a.numberset - b.numberset)
qsort elements sortByNumberset

#3 collect N first (or last) elements and delete them

faces = #{}
for k=1 to N do join faces elements[k]
meshop.deletefaces node faces
#3

Do you think that will work? :wink:

#4

not really :slight_smile: i just hope. it was written and sent from my phone. never tested.
but it’s very close to work

#5

c’mmon! the only thing is to subtract the last element…
for anyone who is not good enough in max scriptit or a little PolyTools3Dish get the fixed version:

fn collectElements node =
(
    local getElement = meshop.getElementsUsingFace
    local elements = #{}
    local faces = #{1..node.numfaces}

    while not faces.isempty do
    ( 
        doIt = on
        for face in faces while doIt do
        (
            element = getElement node face
            append elements element
            faces -= element
            doIt = off
        )
    )
    elements
)
#6

You are practicing a lot of
ish
lately I’ve seen.
How would that be to be a little PolyTools3Dish I wonder.

 Ah, I feel a little PolyTools3Dish today, so I will tell you the other missing one::) 

local elements = #{}
 local elements = #()

I supposed that. I’m just bodering you, as any good PolyTools3Dish would do.

#7

However, you don’t want to run that code on a 3M faces mesh with 2K elements, really.

#8

first… let’s think it was a trick… it’s a very known thing when students better remember a lesson where their teacher made a mistake.

second, it’s only available and fastest (IMHO) method to find all elements via mxs for 3M mesh

third, i exactly know why it is slow via mxs or built-in sdk… and why i rewrote this part of mesh sdk to make it works faster.

#9

and fourth…

how to collect all elements the fastest way:

find all edge pairs (+ reversed) iterating all faces

grow from a face using the fact that mesh edges are faceID +0, +1, +2

that will be the fastest method and good to be used with 3m meshes

#10

I love enumeration, and much more that “H”! :slight_smile:

We know there is no way to beat the SDK with pure MXS. However for 3M faces mesh we could have some “decent” MXS solution.

But meshop.getElementsUsingFace() is almost useless for this, not that much due to the amount of faces, but what really makes it slow is the amount of elements.

A simple test reveals how the performance decrease with the amount of elements rather than with the amount of faces, which is logical.

For the same 13K faces mesh but different number of elements I get this results:
time:4 ram:752L - 1 element
time:79526 ram:1704232L - 13K elements

#11

You see, what you said it was the only and fastest way in your previous post seems to be obsolete now.
I am intrigued to know how that algorithm would work.

#12

meshop.getElementsUsingFace is very-very slow if you want to find ALL elements. but there is no way(!) to it faster for one single element specified by a face.

but if the goal is to find ALL elements we can use a shortcut. two are available:
#1 by verts
#2 by edges

for c++ sdk they both are almost the same by performance (i’m using #1)
for mxs #2 is a little faster (at least it was faster the last time i’ve tested it)

the idea is to make our own growing algorithm using pre-built neighbors data (vert or edge).

#13

Can you measure the different MXS and SDK algorithms you have with this model?

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

Using meshop.getElementsUsingFace() I get this result:
– time:46063 faces:307200 elements:600

Using a different MXS approach I get this:
– time:1249 faces:307200 elements:600

#14

poly (MNMesh) makes internal data neighbors. that makes any grow/shrink for poly much faster than for mesh.
that’s exactly why some tools i make with only editable poly support.

but it’s not possible to stay only with epoly solution. most mesh deformations work better with mesh anyway.

about your test… i don’t really understand what we are testing. honestly i’ve never used meshsmoothbyface and have no idea what does it do.

#15

ah… i got it. it’s a mesh example to test for collecting all elements? right?

i can check it. tomorrow probably.

#16

Right, just a mesh. I used meshsmoothbyface to add some faces to each element.

#17

– time:46063 is expected… you can find several threads on this forum where told why is it.

– time:1249 looks very-very good. and it’s very interesting for me could my sdk beat it or not…

(but ram:29916176L really scares me ;))

#18

i was too interesting, and by my bike i’m in the office — :slight_smile:

t1 = timestamp()
 m1 = heapfree
 getMeshElements n
 format "time:% memory:%
" (timestamp() - t1) (m1 - heapfree)
 >>> time:204 memory:39696L

here what i have…

and sure the list:

#(#{1..512}, #{513..1024}, #{1025..1536}, #{1537..2048}, #{2049..2560}, #{2561..3072}, #{3073..3584}, #{3585..4096}, #{4097..4608}, #{4609..5120}, #{5121..5632}, #{5633..6144}, #{6145..6656}, #{6657..7168}, #{7169..7680}, #{7681..8192}, #{8193..8704}, #{8705..9216}, #{9217..9728}, #{9729..10240}, ...)
#19

The SDK can do the same in 15ms or less.

Dam, you got it before I deleted it. I didn’t want to leave any clue.
Ok, yes memory usage is high, but I have tested it with a 3.5M mesh and had no problem at all. Very stable, does not leak any memory. So it is usable.

The Heap usage is around (numfaces*100) bytes, so for a 3.5M faces mesh is about 350Mb

#20 
>>> time:204 memory:39696L

This is with the SDK right? There is no way to get those numbers with pure MXS!