Fastest way to find coincident polygons

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 20/10/2012 at 17:01, xxxxxxxx wrote:

Let us say that I have a list of CPolygon values and I want to remove from the list all the elements that produce similar faces.

As it is now, my listing is:
**

auxiliary method

def is_in(p1,p2) :

a1=p1.a
     b1=p1.b
     c1=p1.c
     d1=p1.d
     a2=p2.a
     b2=p2.b
     c2=p2.c
     d2=p2.d

a1=(a1==a2 or a1==b2 or a1==c2 or a1==d2)
     b1=(b1==a2 or b1==b2 or b1==c2 or b1==d2)
     c1=(c1==a2 or c1==b2 or c1==c2 or c1==d2)
     d1=(d1==a2 or d1==b2 or d1==c2 or d1==d2)

return (a1 and b1 and c1 and d1)

the code that does the deletion

i=0
while(i<len(pol_list)) :
     delete=False
     p1=pol_list _
     j=i+1
     while(j<len(pol_list)) :
          p2=pol_list[j]
          if is_in(p1,p2) :
               delete=True
               pol_list.pop(j)
               j=j+1
     if delete:
          pol_list.pop(i)
     else:
          i=i+1
**

It works, but it is way too slow.
Is there a faster method?

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 20/10/2012 at 18:59, xxxxxxxx wrote:

Doesn't the SendModelingCommand() Optimize give you the same result?
And it's pretty fast.

Cheers
Lennart

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 02:00, xxxxxxxx wrote:

It doesn't
The Optime command will delete ONE face out of two coincident faces. What I need is to delete BOTH coincident faces.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 04:47, xxxxxxxx wrote:

I just made it almost twice as fast by taking into account the fact that, due to the way I'm creating the geometry, there can only be, at most, another coincident face in the face list. This means that, in the face list, if a coincident face is found, I'm sure that aren't any more possible coincident faces. So, my code advances in the cycle as soon as a coincident face is found (and both are deleted)
**
i=0
while(i<len(pol_list)) :
     delete=False
     p1=pol_list _
     j=i+1
     while(j<len(pol_list)) :
          p2=pol_list[j]
          if is_in(p1,p2) :
               delete=True
               pol_list.pop(j)
               break
          j=j+1
     if delete:
          pol_list.pop(i)
     else:
          i=i+1
**

Even so, this is still slow. Isn't there a faster method?

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 06:39, xxxxxxxx wrote:

What are your calc times now for how many polys?

  
print '%s Polygons' %(len(pol_list))   
now = c4d.GeGetTimer()   
your code   
print '%s ms' %(c4d.GeGetTimer() - now)

I would imagine using for loops with xrange
and compare lists might shave off some time.

Cheers
Lennart

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 10:40, xxxxxxxx wrote:

Here are a few results:

3750 Polygons
2206 deleted
5424 ms

1470 Polygons
854 deleted
868 ms

306 Polygons
178 deleted
41 ms

I included the number of faces deleted.
What do you mean by "compare lists"?

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 15:27, xxxxxxxx wrote:

Ok, I changed the way faces are created and now it is super fast
Now, I just need to understand why it is now showing the mesh when my object is selected.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 16:11, xxxxxxxx wrote:

Glad to hear that!
Was it your poly creation process that helped
or the search method? If it was the method , let us know

By lists I meant there are tons of algorithms out that there
that fit the bill depending of the intended use.

I recently made a polygon CoPlanar checker, testing
all kinds of algo's and got a 2550 polygon search down to 26ms.
(It of coarse get slower with the polycount but at
40000 polys it is at a managable 400ms.)

I'd be happy to help but it's hard to know as of why your mesh
disappears without some basic info how you run your plugin.
It sounds like a cache issue.

Cheers
Lennart

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 16:25, xxxxxxxx wrote:

I made it work changing the creation process, not the search/deletion method
Now, only the outer faces are generated. All faces that are interior to my object are not generated at all.

As for it disappearing, I guess it was due to the fact that I was registering the object with c4d.OBJECT_GENERATOR|c4d.OBJECT_INPUT|c4d.OBJECT_POLYGONOBJECT
when all I actually needed was c4d.OBJECT_GENERATOR

Anyway, the object is using splines that are dragged into an Include list and, as soon as they are in the list and my object is selected, they are not drawn in the editor. As soon as my object is deselected, they are drawn again. I still need to find out why.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 16:50, xxxxxxxx wrote:

So I guess they might be touched, see if your dependence list is doing its thing correct.

Cheers
Lennart

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 21/10/2012 at 18:24, xxxxxxxx wrote:

I'm touching all the object in the list as I read it.
It is working fine. Still a few things to fix, but it is working, step by step