Approximate a Point Cloud with a surface

A place to share learning material: written tutorials, videos, etc.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Approximate a Point Cloud with a surface

Post by Chris_G »

Hello,
Following this question, that is an interesting challenge, that I would like to turn into a kind of tutorial.
The goal is to get a trimmed surface that approximate a point cloud.
pc_approx_1.png
pc_approx_1.png (46.8 KiB) Viewed 8583 times
The workflow will be as follows :
  1. Approximate the point cloud with a BSpline surface using the Reverse Engineering WB
    This surface will extend beyond the point cloud, and needs to be trimmed with boundary curves
    To do so, it will be easier to work on a flat plane
  2. Create a flat map of the point cloud on XY plane
  3. Extract the boundary points of this flat point cloud
  4. Approximate them with curves
  5. Map these curves back on the surface, and trim it
Here is the base file (an STL mesh, and the Point cloud generated with the Points Workbench)
Attachments
point-cloud-approx-1.FCStd
(259.19 KiB) Downloaded 166 times
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: Approximate a Point Cloud with a surface

Post by Chris_G »

Select the Point Cloud and activate the "Approximate BSpline Surface" of the Reverse Engineering Workbench.
It has many settings that need to be adjusted to get the best result, and that depends a lot on the complexity of the input point cloud.
rev-eng-point-cloud.jpg
rev-eng-point-cloud.jpg (185.62 KiB) Viewed 8480 times
The "Degree" values should be kept low. Values between 3 and 5 are usually enough
The number of "Control Points" should be kept low also. Around 10 to 20 is usually good.
"Size Factor" sets how much the approximating surface will extend outside the point cloud
The smoothing section can be tested and tweaked to get better results.

One point that is less obvious is the "User-defined u/v directions" with a placement.
This can be used to tweak the orientation of the approximating surface.
Be default it is unchecked.
- Clic "Create Placement" and Cancel the Approximation tool.
- Go back in the Tree View and Right-clic the placement object and select Transform
- Rotate the placement to set what you think should be the "natural" orientation of the surface, and exit editing
- Launch again the Approximation tool and check "User-defined u/v directions"
- Now, when clicking OK, you'll get a Warning Popup Window asking to select the placement.
- Go back to TreeView, select the placement
- Go back to task View and click OK, and this time it will compute the surface

You should end up with something like this :
Attachments
point-cloud-approx-2.FCStd
(269.75 KiB) Downloaded 134 times
Last edited by Chris_G on Sun Nov 21, 2021 6:31 pm, edited 2 times in total.
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: Approximate a Point Cloud with a surface

Post by Chris_G »

Now the BSpline surface needs to be trimmed by boundary curves.
Since the number of points of the point cloud is pretty high, it would be painful to select the boundary points by hand to generate approximating boundary curves.
So we will work in 2D, on the XY plane, for that task.

- Select the Point Cloud and the Approximating BSpline Surface
- Copy / Paste the following code in the Python console

Code: Select all

"""Select the Point Cloud and the approximating surface
This will generate a flat map of the point cloud on the XY plane"""

s = FreeCADGui.Selection.getSelection()
for so in s:
    if hasattr(so, "Points"):
        pc = so
    elif hasattr(so, "Shape"):
        face = so.Shape.Face1

progressbar = FreeCAD.Base.ProgressIndicator()
progressbar.start("flattening point cloud ...", len(pc.Points.Points))

shapes = []
for p in pc.Points.Points:
    u,v = face.Surface.parameter(p)
    shapes.append(Part.Vertex(FreeCAD.Vector(u,v)))
    progressbar.next()

progressbar.stop()

comp = Part.Compound(shapes)
Part.show(comp, "Flat Point Cloud")

This will generate a "Flat Point Cloud" object that is a flat representation of the Point cloud in the parametric space of the approximating surface.
Attachments
point-cloud-approx-3.FCStd
(380.95 KiB) Downloaded 449 times
Last edited by Chris_G on Sun Nov 21, 2021 6:35 pm, edited 3 times in total.
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: Approximate a Point Cloud with a surface

Post by Chris_G »

Now, one easy way to get the trimming curves is simply to create a sketch (the default one, on XY plane), and draw a closed wire that contours the point cloud and jump to the surface trimming part.
point-cloud-approx-4.FCStd
(384.99 KiB) Downloaded 127 times

However, we may also want to extract the points that are on the boundary of the point cloud and use them to create approximating curves.
For this purpose, we need to draw a bounding wire in a sketch, as above, but this time, the wire must always be outside of the point cloud, by an offset.
pc_approx_2.png
pc_approx_2.png (20.53 KiB) Viewed 8343 times
These curves will be used to detect the closest points of the point cloud.
Then :
- Select the Contour Sketch, and the flat Point Cloud and run the following script in the python console :

Code: Select all

"""Select the flat point cloud
and the sketch that contours it
This will create objects that contain boundary vertexes"""

# Number of samples by unit length
scan_factor = 60
detection_radius = 5


def reduce_point_cloud(point_cloud, edge, fac=5):
    """returns the vertexes of point_cloud that are near to edge"""
    d, pts, info = point_cloud.distToShape(edge)
    tube = Part.makeTube(edge, d * fac)
    f1 = Part.Face(Part.Wire([tube.Edge2]))
    f2 = Part.Face(Part.Wire([tube.Edge3]))
    so = Part.Solid(Part.makeShell([tube,f1,f2]))
    com = so.common(point_cloud)
    return com


s = FreeCADGui.Selection.getSelection()
for so in s:
    if hasattr(so, "Constraints"):
        ie = so.Shape.Edges
    elif hasattr(so, "Shape"):
        pc = so.Shape

for i, e in enumerate(ie):
    red_pc = reduce_point_cloud(pc, e, detection_radius)  # to reduce compute time
    points = [FreeCAD.Vector(1e50, 0, 0)]
    num = int(scan_factor * e.Length)
    FreeCAD.Console.PrintMessage(f"Searching Boundary Points for Edge{i+1} with {num} samples\n")
    progressbar = FreeCAD.Base.ProgressIndicator()
    progressbar.start("Searching Boundary Points ...", num)
    for p in e.discretize(num):
        iv = Part.Vertex(p)
        d, pts, info = red_pc.distToShape(iv)
        if pts[0][0].distanceToPoint(points[-1]) > 1e-7:
            points.append(pts[0][0])
        else:
            print("ignoring duplicate point")
        progressbar.next()
    progressbar.stop()
    verts = [Part.Vertex(p) for p in points[1:]]
    Part.show(Part.Compound(verts), f"Boundary Points {i+1}")


It should generate a "Boundary Points" object for each edge of the sketch, as below :
pc_approx_3.png
pc_approx_3.png (64.57 KiB) Viewed 8343 times
In the above script, two variables can be tweaked :

Code: Select all

scan_factor = 60
detection_radius = 5
scan_factor is the number of samples on each edge, used to search for the boundary points, it can be increased if the script miss some points, but it will increase compute time accordingly. Or it can be reduced to make the script faster.

detection_radius is used in a pre-filter phase where a tube is built along the detection edges, to isolate the candidate boundary points.
If the detection edge is at a constant offset distance from point cloud, this can be set to 2 or 3. But if the script miss full portions of boundary points, this value probably needs to be increased.

point-cloud-approx-5.FCStd
(390.47 KiB) Downloaded 132 times
Last edited by Chris_G on Thu Nov 25, 2021 5:35 pm, edited 4 times in total.
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: Approximate a Point Cloud with a surface

Post by Chris_G »

Now that we have isolated the boundary points of the point cloud, it is possible to approximate them with bspline curves.
Select all the Boundary_Points objects in the Tree-View and launch the Approximate tool of the Curves WB.
Here again, some tweaking will probably be needed in order to get the best result.
Some oscillation of the curve may appear :
pc_approx_4.png
pc_approx_4.png (60.63 KiB) Viewed 8319 times

This can be fixed by using the "Smoothing Algorithm" Method, instead of "Parametrization", in the Approximation_Curve objects.
But that Method doesn't guarantee that the curve passes by the first and last points exactly, so the "Clamp Ends" property must be set to True.
Attachments
point-cloud-approx-6.FCStd
(394.21 KiB) Downloaded 130 times
Last edited by Chris_G on Tue Nov 23, 2021 6:31 pm, edited 1 time in total.
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: Approximate a Point Cloud with a surface

Post by Chris_G »

Now that we have a closed boundary wire around the flat point cloud, the following script will map it back on the 3D surface and generate a trimmed surface with it.
- Select the Boundary objects and the untrimmed surface
- copy / paste :

Code: Select all

"""Select the approximating surface (untrimmed)
and the flat curve objects that bound the flat point cloud
This will map these curves on the target surface and trim it"""

flat_curves = []
s = FreeCADGui.Selection.getSelection()
for so in s:
    try:
        face = so.Shape.Face1
    except AttributeError:
        flat_curves.extend(so.Shape.Edges)

curvesOnSurf = []
pl = Part.Plane().toShape()
proj = pl.project(flat_curves)
for e in proj.Edges:
    fc, fp, lp = pl.curveOnSurface(e)
    cos = fc.toShape(face.Surface, fp, lp)
    if isinstance(cos, Part.Edge):
        curvesOnSurf.append(cos)

w = Part.Wire(curvesOnSurf)
nf = Part.Face(face.Surface, w)
nf.validate()
Part.show(nf, "Trimmed Surface")
And we should get the awaited trimmed surface :
pc_approx_5.png
pc_approx_5.png (95.22 KiB) Viewed 8315 times
Attachments
point-cloud-approx-7.FCStd
(425.45 KiB) Downloaded 134 times
Devy
Posts: 9
Joined: Mon Oct 09, 2017 9:47 pm

Re: Approximate a Point Cloud with a surface

Post by Devy »

This is great! Thanks for going through the trouble. A tutorial showing this off was very needed.

I'll have to look at getting a better fit of the BSpline surface to the point cloud, I noticed the version you made still is off by a small amount on some of the edges (see attached). I wonder if making a couple different surfaces based off different sections of the point cloud would allow the surface to approximate better?

I also am curious to see how adjacent surfaces could blend into other surfaces made with the techniques you outlined here. For example, the scanned data this point cloud comes from has fillets that should connect to some boundaries of the surface made here.
Attachments
Example of surface being off from point cloud/stl
Example of surface being off from point cloud/stl
Screenshot 2021-11-23 201130.png (144.96 KiB) Viewed 8302 times
User avatar
Chris_G
Veteran
Posts: 2578
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: Approximate a Point Cloud with a surface

Post by Chris_G »

Devy wrote: Wed Nov 24, 2021 1:07 am I noticed the version you made still is off by a small amount on some of the edges (see attached).
I didn't make much attempts with the approx surface.
Devy wrote: Wed Nov 24, 2021 1:07 am I wonder if making a couple different surfaces based off different sections of the point cloud would allow the surface to approximate better?
The simpler the point cloud, the more chance to get a good approximation surface.
Devy wrote: Wed Nov 24, 2021 1:07 am I also am curious to see how adjacent surfaces could blend into other surfaces made with the techniques you outlined here. For example, the scanned data this point cloud comes from has fillets that should connect to some boundaries of the surface made here.
When the goal is to get a good watertight model, then you can only use this technique for the main starting surface, but the other surfaces that connect it must use more precise algorithms.
paullee
Veteran
Posts: 5097
Joined: Wed May 04, 2016 3:58 pm

Re: Approximate a Point Cloud with a surface

Post by paullee »

Thanks! Seems to be a good way to create landform surface (vs Mesh) from scanned point cloud ? :D

Pinging HakanSeven and Joel.
HakanSeven12 wrote: Ping
Joel_graff wrote: Ping
User avatar
HakanSeven12
Veteran
Posts: 1481
Joined: Wed Feb 06, 2019 10:30 pm

Re: Approximate a Point Cloud with a surface

Post by HakanSeven12 »

There's a reason to using mesh instead of shape :) shapes are very powerful but slow. Mesh is very simple and fast to process. I have tons of points and triangles. Also some of my tools specifically need mesh functions.

That method looks great. But I don't think to use this type of surfaces in Trails.
Post Reply