Two new scripting methods

Need help, or want to share a macro? Post here!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
User avatar
xxxajk
Posts: 10
Joined: Sat Jan 04, 2020 5:30 am

Two new scripting methods

Post by xxxajk »

After getting a nasty bug fixed (Thanks FreeCAD team!) I've been able to further my workbench, that I'll eventually release.

That said, here are the new python methods I would find super handy, because currently processing is taking way to long, and OCC should have the ability.
Here's the current problem:
I have to wait 6 hours for something that should be able to happen in under a minute, especially on a current modern 64bit machine.
And yeah, I'm aware of the Python GIL, I dislike it too. :-) Doesn't mean that OCC couldn't leverage threads and parallelize...

Why so long? Because I have to iterate each point, and there's thousands of them, and each vector check eats 1ms. After 1k points you are already at 1 second, not including the Python overhead, which isn't much.
3,600,000 points takes an hour to calculate, however an object with this many points displays pretty much instantly -- if this happened with something like an STL, well, I think you get the idea.

First one...

Code: Select all

pts =list of vectors, or vertexes
w = Part.Wire(some_edges) # could be a wire or face here...
w.areInside([list of vectors or vertexes], tolerance, checkFace) 
This is like isInside but for a list of points, and returns a list of points that all are inside, instead of a boolean.

Second idea is the same above but for a list of

Code: Select all

Part.LineSegment()
where the entire line must be inside.
This would be useful to figure out what parts of/all of a wire are inside.
chrisb
Veteran
Posts: 53919
Joined: Tue Mar 17, 2015 9:14 am

Re: Two new scripting methods

Post by chrisb »

Moved from Open discussion forum.
A Sketcher Lecture with in-depth information is available in English, auf Deutsch, en français, en español.
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Two new scripting methods

Post by edwilliams16 »

xxxajk wrote: Sun Mar 19, 2023 11:14 am

Code: Select all

pts =list of vectors, or vertexes
w = Part.Wire(some_edges) # could be a wire or face here...
w.areInside([list of vectors or vertexes], tolerance, checkFace) 
This is like isInside but for a list of points, and returns a list of points that all are inside, instead of a boolean.
One idea:
  • Make a uniform xy-grid over the face out to its BoundBox.
  • Loop over the cells and label them inside, outside or mixed.
  • For each point find in which grid cell it lies - modular arithmetic is all required
  • You are done unless the point is in a mixed cell, in which case use the usual isInside()
The last step can probably be done with array operations, speeding it up, so you don't loop in the interpreter. You might need numpy for vectorized array operations.
User avatar
xxxajk
Posts: 10
Joined: Sat Jan 04, 2020 5:30 am

Re: Two new scripting methods

Post by xxxajk »

edwilliams16 wrote: Mon Mar 20, 2023 1:33 am
  • Make a uniform xy-grid over the face out to its BoundBox.
Can't use a bounding box, polygons have concave parts.
edwilliams16 wrote: Mon Mar 20, 2023 1:33 am
  • Loop over the cells and label them inside, outside or mixed.
  • For each point find in which grid cell it lies - modular arithmetic is all required
  • You are done unless the point is in a mixed cell, in which case use the usual isInside()
The last step can probably be done with array operations, speeding it up, so you don't loop in the interpreter. You might need numpy for vectorized array operations.
Actually, once I have the wanted list Python is plenty fast enough, It's the individual calls to isInside() that is the issue. I need to check if points are on a face, and if I can just shove an entire list of points, and have OCC do it's magic in a fast way, that would be ideal.
jbi
Posts: 117
Joined: Sun Apr 24, 2016 3:28 pm

Re: Two new scripting methods

Post by jbi »

Don't know how important this is for you. At least a picture would help to understand. Is this a planar face? If so i would check with

Code: Select all

vec.distanceToPlane(basepoint, normal)
first, and just check the points which are within a tolerance of the face. If you are only on python you could do also multiprocessing and spread out the points evenly to the processes. Of course would be interesting how much speedup can be gained if you can send a list to this functions. Also edwilliams16 approach looks kinda smart. I guess if this function is your only remaining bootleneck you would get assistence. Maybe it is only on me but over the years working on a hobby project I found out a lot of ways to do things fast and optimize for speed, but getting the idea from the ground working was much more difficult. My original plan was to do multiple boolean cuts and some operations, which I estimated some years ago around with 10 hours. Now I do it within 200 sec. That's a factor of 180. And all with python and a little bit of numpy.
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Two new scripting methods

Post by edwilliams16 »

xxxajk wrote: Mon Mar 20, 2023 1:16 pm
edwilliams16 wrote: Mon Mar 20, 2023 1:33 am
  • Make a uniform xy-grid over the face out to its BoundBox.
Can't use a bounding box, polygons have concave parts.
Sure you can. The only purpose of the BB is to limit the size of the search grid.
FreeCAD has no control over the speed of isInside(). You need to go to Open Cascade for that. The best you can do here is reduce the number of required calls to it and/or to multiprocess them.
User avatar
xxxajk
Posts: 10
Joined: Sat Jan 04, 2020 5:30 am

Re: Two new scripting methods

Post by xxxajk »

edwilliams16 wrote: Mon Mar 20, 2023 6:36 pm
xxxajk wrote: Mon Mar 20, 2023 1:16 pm
edwilliams16 wrote: Mon Mar 20, 2023 1:33 am
  • Make a uniform xy-grid over the face out to its BoundBox.
Can't use a bounding box, polygons have concave parts.
Sure you can. The only purpose of the BB is to limit the size of the search grid.
FreeCAD has no control over the speed of isInside(). You need to go to Open Cascade for that. The best you can do here is reduce the number of required calls to it and/or to multiprocess them.
It's not that simple.
FWIW I've already tried various python "solutions" (cough) and so far, all of them increased the time. :lol: :lol:

Qt's threads/thread pools: FAIL, can't get any concurrency (GIL) :roll:
Multiprocessing module: FAIL, too much overhead (huge amounts of data) :roll:

To be quite clear here...
I'm not finding a point which is in a simplistic box, etc. I could write that myself, and actually have some 40 years ago...

To become a little more tuned in, I guess I need you (and everyone else probably) to try a small example...
Create a polygon with 4000 vertexes and try to find 800 sets of points (1600 total points) inside of it, you will be sitting there for quite a while.
Now try doing the same thing over 100-200 of these, some of which have 40,000 vertexes. Go to bed, come back in the morning, and if you don't run out of memory and swap (Have managed to reduce the memory recently) you'll unsurprisingly find it still spinning it's wheels.

It's all because of the silly GIL, which can be easily bypassed on the C++ side, and reduce a 10 minute point scan to a sub-second one, and one hour to a minute (which I could actually tolerate).

I'm not asking or looking for a "pythonic solution" because there are none, zero, zip, zilch, empty, void, and null. :roll:

I'm asking for either someone who knows OCC to point me in the right direction, or take the bull by the horns and write it once they realize how awesome it would be to do this, or to collaborate with me.

Python uses C/C++ under the hood for several reasons, and most of them is due to the GIL. It's why we have stuff like numpy...

I DO appreciate the attempts to offer something that works for very simple things. Just please try to understand the actual scope of the problem, and how useful these could be. Who knows, even cloud points might actually generate in a reasonable amount of time. (tried it, that workbench hates me, spins for an hour on the simplest things)

I'm not the usual "normal" FreeCAD user, I use it programmatically for most of the things I do. And for the few things that I don't I only use the part workbench.
Drafting? Meh, I can calculate my own lines/polygon, and I don't need to deal with the 10 clicks to set a value... if I can be bothered to find it in all of the menus. I pretty much feel the same way with all the other GUI workbench stuff, save for the Part workbench, which just works, and is super easy to understand.
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Two new scripting methods

Post by edwilliams16 »

xxxajk wrote: Mon Mar 20, 2023 11:40 pm
To become a little more tuned in, I guess I need you (and everyone else probably) to try a small example...
Create a polygon with 4000 vertexes and try to find 800 sets of points (1600 total points) inside of it, you will be sitting there for quite a while.
Now try doing the same thing over 100-200 of these, some of which have 40,000 vertexes. Go to bed, come back in the morning, and if you don't run out of memory and swap (Have managed to reduce the memory recently) you'll unsurprisingly find it still spinning it's wheels.
I'm taking you literally. You have polygons with 40000 vertices? A polygon is a planar figure, right? You must have over-digitized something.

Check out https://ir.nctu.edu.tw/bitstream/11536/ ... 100010.pdf ON THE COMPLEXITY OF POINT-IN-POLYGON
ALGORITHMS
User avatar
xxxajk
Posts: 10
Joined: Sat Jan 04, 2020 5:30 am

Re: Two new scripting methods

Post by xxxajk »

edwilliams16 wrote: Mon Mar 20, 2023 11:57 pm
xxxajk wrote: Mon Mar 20, 2023 11:40 pm
To become a little more tuned in, I guess I need you (and everyone else probably) to try a small example...
Create a polygon with 4000 vertexes and try to find 800 sets of points (1600 total points) inside of it, you will be sitting there for quite a while.
Now try doing the same thing over 100-200 of these, some of which have 40,000 vertexes. Go to bed, come back in the morning, and if you don't run out of memory and swap (Have managed to reduce the memory recently) you'll unsurprisingly find it still spinning it's wheels.
I'm taking you literally. You have polygons with 40000 vertices? A polygon is a planar figure, right? You must have over-digitized something.

Check out https://ir.nctu.edu.tw/bitstream/11536/ ... 100010.pdf ON THE COMPLEXITY OF POINT-IN-POLYGON
ALGORITHMS
Nope! not overdigitized, just very detailed. next post will have the demo. Only freezes FreeCAD for 02:03.176966
If it was pure python and could use all 16 cpu's it would take something like 7 or so seconds... C++ helper will be vastly faster I would hope.
User avatar
xxxajk
Posts: 10
Joined: Sat Jan 04, 2020 5:30 am

Re: Two new scripting methods

Post by xxxajk »

Well, here's the demo.
You must have the Marz Guitar Design Workbench installed, but that's just to show how even Qt threads can't help.

https://github.com/FreeCAD/FreeCAD/issu ... 1477182444
Post Reply