LDraw.org Discussion Forums
Duplicated or overlapping surfaces checker - Printable Version

+- LDraw.org Discussion Forums (https://forums.ldraw.org)
+-- Forum: LDraw Programs (https://forums.ldraw.org/forum-7.html)
+--- Forum: All Other Programs. (https://forums.ldraw.org/forum-26.html)
+--- Thread: Duplicated or overlapping surfaces checker (/thread-262.html)



Duplicated or overlapping surfaces checker - Damien Roux - 2011-08-03

I'm currently trying to model a huge patterned part (2552 serie) using automatic vectorization to avoid a long and boring time working with quad2dat or other patterning programs.

In order to complete that I would like to know if there is any program that can check if triangles have been duplicated, or if some surfaces are overlapping, partially covering each other. Usually, this can be done using the random colorization of LDview, and by carefully searching for the blinking areas while rotating the part ; but in my particular case, this method is not really achievable 'cause of the number of triangles involved.

If no program exists, does someone has an idea on how this can be checked?


Re: Duplicated or overlapping surfaces checker - Tim Gould - 2011-08-03

Will they all be co-planar? If so I reckon I could write a perl script to check. If not it all gets... complicated.

Tim


Re: Duplicated or overlapping surfaces checker - Tim Gould - 2011-08-03

If they are all co-planar checking is relativels straightforward. I'm assuming they lie on the xy plane...

This is crude and inefficient but should work (I think)

1) Break all quads into tris
2) Round all points to a fine grid (eg. 0.25LDU)
3) Cycle through all tris:
3a) Each tri has three points (x1,y1) (x2,y2) and (x3,y3)
Calculate u1=x2-x1, v1=y2-y1, u2=x3-x1, v2=y3-y1
Calculate det=v2*u1-v1*u2
3b) Cycle through all other points (x,y)
3ci) Set a=[v2*(x-x1) - v1*(y-y1)]/det, b=[u1*(y-y1) - u2*(x-x1)]/det
3cii) if (a>0) && (a<1) && (b>0) && (b<1) && (abs(a)+abs(b)<1)
then the two tris overlap


I'm fairly sure that should work although I may have made a slight error.

Tim


Re: Duplicated or overlapping surfaces checker - Damien Roux - 2011-08-03

Yeah, everything is coplanar. It might no longer be after projection on the part due to rounding errors, but the checks could be done before (while the patterned surface is still flat). If you would be ready to write some program for this, it would be very useful. I don't care if it takes half an hour to give the result. ^^

BTW, rounding to 0,25 LDU is not possible at all as I will lost a lot of details of the pattern. The pattern I'm making is quite precise and detailled. maybe too much but I can still simplify it afterwards.

I can post my WIP file here so you can have a look if you want. I'll do this soon...


Re: Duplicated or overlapping surfaces checker - Tim Gould - 2011-08-03

Whoops sorry. My first response wasn't meant to go through but I must have accidentally hit send. I cannot write a perl script for it any time soon.

Tim


Re: Duplicated or overlapping surfaces checker - Greg Teft - 2011-11-19

How'd you make out with this?

I had a co-planar algorithm that would check all loaded trines/quads in a .dat file for overlap by if they had the same normal and if more than one of line segments that defined their edges crossed. Coincidental edges were ignored unless there were more than one to avoid failing out on seams.
Unfortunately that got lost in-between computers, and I don't have it any more.
I'm currently reworking my lost Java API for parsing dat files.
You can Google algorithms for calculating normals, as well as angles or distance between lines. Linear Algebra was a long time ago for me, I'd have to look up them up myself!