Super-super fast Point Inclusion test for Cylinder/Breps?

The inbuilt PointInBrep is way too slow. So I will make my own.

Using VB.NET I’ve been struggling for a day to try to make the PointInclusion filter foc cylinders as fast as possible, but it seems it gets only slower the more I try to optimize (indicating my excellent .NET skills). Currently it takes about 20-30 seconds to filter 50’ points (something is seriously worng), and it should be possible to come down to say 500-300ms I’m sure (planar box test is less than 8 ms for 50.000 pts).


Edit: Hm, removing pre-allocation of list.Capacity brought it down to 5-9 sek (pre-allocating list Capacity is an old Delphi-trick that obviously doesn’t work well in .NET…). But there’s still a bit of work to get down under 300 ms…
Edit 2: It also seems like the Solver keeps a cache of output values, because the output pointlist almost doubles its item count for each time the solver is run. Hm.

Anyway, the following is the current scenario :

  • The filter typically processes some 50.000 mesh points.
  • Points inside the Brep Cylinder are listed in one list
  • Points outside the Brep Cylinder are listed in another list
  • Cylinder Brep can change Height between runs
  • Cylinder Brep can change Radius between runs
  • Cylinder Brep can change Inclination between runs
  • Cylinder Brep can change 3D Position between runs

Fig.1. This is an example result with a leaning cylinder.

I’ve tried to transform the Cylinder and the POint Cloud to horizontal (which then can determine inclusion very super fast, testing points only for radius-distance and height) but the Transform took forever. Must have done something wrong.

Example code which is so slow (I commented away the BoundingBox test because it didn’t run any faster . I also try to re-use lines etc, by only changing the start- and end-points instead of creating new instances. All those tricks, but still soo sloow :

            For Each mesh_pt As Point3d In MeshPoints

                '//
                '// BOX INCLUSION (Raw test)
                '// 

                '//If (mesh_pt.Z < BBox.Max.Z) And
                '//   (mesh_pt.Z > BBox.Min.Z) And
                '//   (mesh_pt.X > BBox.Min.X) And
                '//   (mesh_pt.X < BBox.Max.X) And
                '//   (mesh_pt.Y > BBox.Min.Y) And
                '//   (mesh_pt.Y < BBox.Max.Y) Then

                ''// 
                ''// CYLINDER INCLUSION
                ''// 

                '// re-using curve : 

                crv.SetStartPoint(cylC)
                crv.SetEndPoint(mesh_pt)

                '// Curve/Brep Intersection

                If Intersect.Intersection.CurveBrep(crv, cyl_brep, 0.001, overlapCurves, intersectPoints) 
                  And (intersectPoints.GetUpperBound(0) < 0) Then
                    insidePts.Add(mesh_pt)
                Else
                    outsidePts.Add(mesh_pt)
                End If
            Next

So what is the super-super fastest (specialized approach for each basic Brep form (sphere, cyl, box, torus, cones) which also will be tilted?

// Rolf

1 Like

In general I would probably go for an as coarse as possible mesh approximation of your (closed) cylinder, then use Intersection.MeshRay to intersect a ray with the mesh that starts at the point to test in the direction of the inclination. If you have an even number of intersections, the point is inside the cylinder; if you get zero or an odd number of intersections, the point is outside the cylinder.

You could also approach it algebraically for the cylinder case, by defining the two capping planes of the cylinder and knowing the radius (which you do). A point is inside if 1) the signed distance Plane.DistanceTo(Point3d) to the capping planes (use the normals pointing away from the cylinder) is negative in both cases ( then the point is between the planes), and 2) the distance of the point to the cylinder’s axis line is smaller than the radius. If either of these two prerequisites is not met, the point is outside the cylinder.

For all other cases you can use similar algebraic approaches:

  • box: signed distance should be negative to all 6 planes having their normal pointing outward
  • sphere: distance to sphere center should be smaller than radius
  • torus: use a smart combination of planes and distances
  • cone: you could calculate the distance from the base plane and calculate the radius at that distance; then for positive radii check to see if the distance to the inclination line is smaller than the radius.

Before I looking deeper into your suggestions (thanks for that BTW) I need to point out that the Cylinder is a Nurbs brep (and the other shapes are too).

I’m trapping mesh vertices (from sometimes extremely bad meshes)

// Rolf

Ok, then either try the mesh/ray intersection method (this works in general) or try to see if you can somehow re-interpret the BRep as cylinder, cone, torus, etc.

I do create the cylinder (and other shapes) internally inside the component (New Cylinder.ToBrep()), so I can use any of the basic types.


Edit: BTW, do you have any idea why the number of output points keep growing at each run of the solver?

First run now takes about 1.2 sec, but for each run it more than double the time (and input is 46.840 points, while the points “outside” has grown to 482.243… after only a few runs…

What is going on here? Is there any port-cache I should poke on at the beginning of each solver run?

// Rolf

You’ll have to post some code to find out why this happens. Off the top of my head, you’re either re-using lists and not clearing them, or maybe using the same list instance as input and output.

Here’s the slow code that multiplies its output cnt (I was just about to try Intersection.LineCylinder instead of Intersection.CurveBrep but quickly uncommented it, hopefully it still compiles):

Imports System.Collections.Generic

Imports Grasshopper.Kernel
Imports Rhino.Geometry
Imports Rhino

Namespace RIL.GH.Filters

    Public Class RILGH_CylPtInclusionSolver_TMP
        Inherits GH_Component

        Private m_DA As IGH_DataAccess

        ''' <summary>
        ''' Initializes a new instance of the MyComponent1 class.
        ''' </summary>
        Public Sub New()
            MyBase.New("Cylinder Point Inclusion Solver", "PtsInCylSolver",
                    "Tilt or Resize while filtering points inside the bounds of a cylinder.",
                    "RIL", "Filters")
        End Sub

        ''' <summary>
        ''' Registers all the input parameters for this component.
        ''' </summary>
        Protected Overrides Sub RegisterInputParams(pManager As GH_Component.GH_InputParamManager)
            '// Make default XY plane
            Dim XYPLane As Vector3d = New Point3d(0, 0, 10) - New Point3d(0, 0, 0)
            '// Register In-ports
            pManager.AddPointParameter("Rotation center", "C", "Rotation center.", GH_ParamAccess.item, New Point3d(0, 0, 0))
            pManager.AddPointParameter("Cylinder Height & Tilt", "H", "A 3D height-center Point determining the Height and the Inclination of the Cylinder.", GH_ParamAccess.item, New Point3d(0, 0, 10))
            pManager.AddNumberParameter("Radius", "R", "Radius of the inclusion Cylinder.", GH_ParamAccess.item, 10)
            pManager.AddPointParameter("Point Cloud", "Pts", "Points to test for inclusion.", GH_ParamAccess.list)
            pManager.AddNumberParameter("Tolerance", "T", "Tolerance for inclusion test.", GH_ParamAccess.item, 0.01)
            pManager.AddBooleanParameter("ON/OFF", "ON", "Activate execution by setting value to True.", GH_ParamAccess.item, False)
            pManager.AddGeometryParameter("CoGeo", "CoGeo", "Additional Geometry to be equally Transformed.", GH_ParamAccess.list)
        End Sub

        ''' <summary>
        ''' Registers all the output parameters for this component.
        ''' </summary>
        Protected Overrides Sub RegisterOutputParams(pManager As GH_Component.GH_OutputParamManager)
            pManager.AddPointParameter("Points Inside Box", "BIn", "Points residing inside the Bounding Box.", GH_ParamAccess.list)
            pManager.AddPointParameter("Points Outside Box", "BOut", "Points residing outside the Bounding Box.", GH_ParamAccess.list)
            pManager.AddPointParameter("Cylinder Center", "CC", "Point in the center of the Cylinder Bounding Box.", GH_ParamAccess.item)
            pManager.AddTextParameter("Score", "Score", "Score after several attempts.", GH_ParamAccess.item)
            pManager.AddBrepParameter("Brep", "Brep", "Brep for debugging.", GH_ParamAccess.item)
            pManager.AddGeometryParameter("TxGeo", "TxGeo", "Co-Transformed geometries.", GH_ParamAccess.list)
        End Sub


        Private Const IN_C = 0
        Private Const IN_H = 1
        Private Const IN_R = 2
        Private Const IN_Pts = 3
        Private Const IN_Tol = 4
        Private Const IN_On = 5
        Private Const IN_CoGeo = 6

        Private Const OUT_BIn = 0
        Private Const OUT_BOut = 1
        Private Const OUT_CC = 2
        Private Const OUT_Score = 3
        Private Const OUT_Brep = 4
        Private Const OUT_TxGeo = 5


        ''' <summary>
        ''' Provides the Inport value of C - Rotation center
        ''' </summary>
        Private Function GetInputC() As Point3d
            Dim m_C As New Point3d
            If Not m_DA.GetData(IN_C, m_C) Then
                Print("# Error - Invalid Point input.")
            End If
            Return m_C
        End Function


        ''' <summary>
        ''' Provides the Inport value of C - Rotation center
        ''' </summary>
        Private m_H As New Point3d
        Protected Property InH() As Point3d
            Get
                If Not m_DA.GetData(IN_H, m_H) Then
                    Print("# Error - Invalid Point input.")
                End If
                Return m_H
            End Get
            Set(ByVal value As Point3d)
                m_H = value
            End Set
        End Property


        ''' <summary>
        ''' Provides the Inport value of R - Radius
        ''' </summary>
        Private m_R As Double
        Protected ReadOnly Property InR() As Double
            Get
                If Not m_DA.GetData(IN_R, m_R) Then
                    Print("# Error - Invalid Radius value.")
                End If
                Return m_R
            End Get
        End Property


        Dim m_Pts As New List(Of Point3d)
        Protected ReadOnly Property InPts() As List(Of Point3d)
            Get
                If Not m_DA.GetDataList(IN_Pts, m_Pts) Then
                    Print("# Error - Invalid Point cloud input.")
                End If
                Return m_Pts
            End Get
        End Property


        ''' <summary>
        ''' Provides the Inport value of T - Tolerance
        ''' </summary>
        Private m_T As Single
        Protected ReadOnly Property InT() As Single
            Get
                If Not m_DA.GetData(IN_Tol, m_T) Then
                    Print("# Error - Invalid Tolerance value.")
                End If
                Return m_T
            End Get
        End Property



        ''' <summary>
        ''' Disable or Enable Solver Execution
        ''' </summary>
        Dim m_On As Boolean
        Protected ReadOnly Property InOn() As Boolean
            Get
                If Not m_DA.GetData(IN_On, m_On) Then
                    Print("# Error - Invalid Point cloud input.")
                End If
                Return m_On
            End Get
        End Property



        ''' <summary>
        ''' Provides the Inport value of CoBreps - A bunch of related breps meant to be equally Transformed
        ''' </summary>
        Private m_CoGeo As New List(Of GeometryBase)
        Protected ReadOnly Property InCoGeo() As List(Of GeometryBase)
            Get
                If Not m_DA.GetDataList(IN_CoGeo, m_CoGeo) Then
                    Print("# Error - Invalid breps input.")
                    Return Nothing
                End If
                Return m_CoGeo
            End Get
        End Property


        ''' <summary>
        ''' Derives an inclination vector (as well as height-) axis based on Center point (C) and Height point (H)
        ''' </summary>
        Private Function ZAxis(ByRef aCenterPt As Point3d, ByRef aHeightPt As Point3d) As Vector3d
            Dim v As Vector3d = aHeightPt - aCenterPt
            Return v
        End Function


        ''' <summary>
        ''' Creates a Cylinder at last specified position InC and inclination Plane ( = ZAxis(InH-InC))
        ''' </summary>
        Private Function AsCylinder(ByRef aCenterPt As Point3d, ByRef aHeightPt As Point3d) As Cylinder
            Dim zaxis_tmp As Vector3d = ZAxis(aCenterPt, aHeightPt)
            Dim plane As New Plane(aCenterPt, zaxis_tmp)
            Dim circle As New Circle(plane, InR)
            Return New Cylinder(circle, zaxis_tmp.Length)
        End Function

        Private Function BrepCylinder(ByRef aCenterPt As Point3d, ByRef aHeightPt As Point3d) As Brep
            Return AsCylinder(aCenterPt, aHeightPt).ToBrep(True, True)
        End Function



        ''' <summary>
        ''' This is the method that actually does the work.
        ''' </summary>
        ''' <param name="DA">The DA object is used to retrieve from inputs and store in outputs.</param>
        Protected Overrides Sub SolveInstance(DA As IGH_DataAccess)
            '//
            '// Set class wide access to Data Accessor
            '//

            m_DA = DA
            If Not InOn Then Return

            '//
            '// ANIMATE CYLINDER BREP
            '//

            Dim tolerance As Single = InT
            Dim cp As New Point3d(GetInputC)
            Dim hp As New Point3d(InH)
            Dim insidePts As New List(Of Point3d)
            Dim outsidePts As New List(Of Point3d)

            '//
            '// AUTO-FIT
            '// 

            Dim cylC As New Point3d
            Dim cyl_brep As Brep
            Dim score(0 To 2) As Integer
            Dim score_ix As Integer = 0

            '// -1 to 1. But for now, run only one laps.
            For i As Integer = -1 To -1
                '/
                '/ Clear lists if running multiple rounds
                '/

                insidePts.Clear()
                outsidePts.Clear()

                '/
                '/ Attempt to Translate (Move) Cylinder
                '/

                cp.X += i
                hp.X += i
                cyl_brep = BrepCylinder(cp, hp)

                '//
                '// FILTER CYLINDER
                '//

                Dim BBox As New BoundingBox(cyl_brep.GetBoundingBox(True).GetCorners())
                cylC = BBox.Center

                DA.SetData(OUT_CC, cylC)

                Dim cyl_tmp As Cylinder = AsCylinder(cp, hp)
                'Dim line_tmp As New Line(cylC, hp)
                'Dim isectPt1 As Point3d
                'Dim isectPt2 As Point3d


                Dim crv As New LineCurve(cp, hp)
                Dim inside_cnt As Integer = 0
                For Each mesh_pt As Point3d In InPts

                    '//
                    '// BOX INCLUSION (Raw test)
                    '// 

                    If (mesh_pt.Z < BBox.Max.Z) And
                       (mesh_pt.Z > BBox.Min.Z) And
                       (mesh_pt.X > BBox.Min.X) And
                       (mesh_pt.X < BBox.Max.X) And
                       (mesh_pt.Y > BBox.Min.Y) And
                       (mesh_pt.Y < BBox.Max.Y) Then

                        ''// 
                        ''// CYLINDER INCLUSION
                        ''// 

                        'line_tmp.To = mesh_pt

                        crv.SetStartPoint(cylC)
                        crv.SetEndPoint(mesh_pt)
                        Dim overlapCurves As Curve()
                        Dim intersectPoints As Point3d()


                        If Intersect.Intersection.CurveBrep(crv, cyl_brep, tolerance, overlapCurves, intersectPoints) And (intersectPoints.GetUpperBound(0) < 0) Then
                            'If Intersect.Intersection.LineCylinder(line_tmp, cyl_tmp, isectPt1, isectPt2).Multiple Then
                            insidePts.Add(mesh_pt)
                            inside_cnt += 1
                        Else
                            outsidePts.Add(mesh_pt)
                        End If
                        outsidePts.Add(mesh_pt)
                    End If
                Next
                score(score_ix) = inside_cnt

                'Threading.Thread.Sleep(200)
                'Threading.Thread.Wait(200)
            Next

            '//
            '// OUT-PORTS
            '// 

            DA.SetDataList(OUT_BIn, insidePts)
            DA.SetDataList(OUT_BOut, outsidePts)
            DA.SetData(OUT_CC, cylC)
            DA.SetData(OUT_Score, score(2).ToString())
            DA.SetData(OUT_Brep, cyl_brep)
            DA.SetDataList(OUT_TxGeo, Nothing)
        End Sub


        ''' <summary>
        ''' Icons need to be 24x24 pixels.
        ''' </summary>
        Protected Overrides ReadOnly Property Icon() As System.Drawing.Bitmap
            Get
                Return My.Resources.Resource_Icon.ICO_Experimental
            End Get
        End Property

        ''' <summary>
        ''' Gets the unique ID for this component. Do not change this ID after release.
        ''' </summary>
        Public Overrides ReadOnly Property ComponentGuid() As Guid
            Get
                Return New Guid("EDACD053-B7CE-4A9D-B7E3-099067F03AAD")

            End Get
        End Property
    End Class

End Namespace

// Rolf

The list m_Pts is not cleared when the component runs again.

        Protected ReadOnly Property InPts() As List(Of Point3d)
            Get
                m_Pts.Clear(); ' clear the input list for the next run
                If Not m_DA.GetDataList(IN_Pts, m_Pts) Then
                    Print("# Error - Invalid Point cloud input.")
                End If
                Return m_Pts
            End Get
        End Property

Ah, there it was. Thank you very much!

Many cups of coffee later I also realized that the std Delphi behaviour of “boolean short-circuit” isn’t default in VB.NET. This code runs in full every time, although a majority of points would drop out already at first Z test (yes, I’m doing very specific optimizations at times)

                If (mesh_pt.Z < BBox.Max.Z) And   <- 70% of cases should breake here
                   (mesh_pt.Z > BBox.Min.Z) And
                   (mesh_pt.X > BBox.Min.X) And
                   (mesh_pt.X < BBox.Max.X) And
                   (mesh_pt.Y > BBox.Min.Y) And
                   (mesh_pt.Y < BBox.Max.Y) Then

Changing And into AndAlso should make significant difference on performance :


Edit: Ops, should of course be testing for outside instead, using ‘OrElse’ in order to short circuit, like so:

                '// Test outside (cheapest test)
                If (mesh_pt.Z > BBox.Max.Z) OrElse
                   (mesh_pt.Z < BBox.Min.Z) OrElse
                   (mesh_pt.X < BBox.Min.X) OrElse
                   (mesh_pt.X > BBox.Max.X) OrElse
                   (mesh_pt.Y < BBox.Min.Y) OrElse
                   (mesh_pt.Y > BBox.Max.Y) Then
                    '// OUTSIDE
                    outsidePts.Add(mesh_pt)
                Else
                    '// INSIDE

(The above "BoundingBox exclusion" executes in less than 100ms for 43.000 pts)

More coffee. Again thank’s for spending your time!

// Rolf

As a side note, you may want to consider investing time learning C#. The syntax is the similar, but I find it much more readable:

if (mesh_pt.Z < BBox.Max.Z && // <- if this fails, the other tests will NOT be performed
    mesh_pt.Z > BBox.Min.Z &&
    mesh_pt.X > BBox.Min.X &&
    mesh_pt.X < BBox.Max.X &&
    mesh_pt.Y > BBox.Min.Y &&
    mesh_pt.Y < BBox.Max.Y)
{
// 
}

// a property:
List<Point3d> InPts 
{
    get 
    {
        m_Pts.Clear();
        if (!m_DA.GetDataList(IN_Pts, m_Pts)) Print("# Error - Invalid Point cloud input");
        return m_Pts;
    }
}

Try to convince an old Delphi guy about that! But yes, C# is not as verbose as Delphi and VB but it’s also about what you are used to. VB looks a bit like poor mans Delphi, very similar. At least in verbosity…

But at least VB has its type declarations on the right side. On the right side, that is. :slight_smile:

I played around a bit with Golang though, which comes from the C family, and I liked that. Type declarations where they should be, and not so much bells and wistles. No inheritance though, only interfaces.

But but, when I have the time I might look into C# as well. For now I just want to get things to happen. :slight_smile:

// Rolf

BTW …
out of curiosity, I tried that in a Rhino Python script.
Looks like transforming a point cloud of about 100,000 points takes about 1~2 ms … at least that’s what the script says. ( Using System.Diagnostics.Stopwatch )
And transforming about 100,000 point objects (same points) takes 50 ms.

I’m coming from the C++ and Java world, so I do have my own skewed view on code & readability :smile: I guess it is what you’re used to…

Wow! Then I must have done something wrong. Didn’t try too much, it was late at night, and coffee level running low and…

It sounds like I should take another look at this, really. Thanks for trying this!

(is it that a subset of mesh vertices is somehow slower to transform than “complete” objects, or something like that? I’m doing all this in non-baked GH geometry only - except for the mesh - if it has any significance)

You’re from the elite. :sunglasses:

// Rolf

Hmm …which objects are you transforming ?
( I mean object as RhinoCommon class / structure )

The 50 ms were for Geometry.Point objects … but different objects give different results.
I just tried for a mesh ( Geometry.Mesh ) => 10 ms
And for Geometry.Point3d’s => 9 ms

(always 100,000 points / vertices )

EDIT:

Clearing the undo nuffer ( command ClearUndo in Rhino ),
both the mesh and the Point3d’s take 6 ms

MORE EDIT:

I think I have to say why the buffer undo matters.
My scripts, just to be sure that the transformation happened,
draw the transformed objects.

Still …Actually I don’t know why the undo buffer makes the script slower here … :confused:

I don’t know what difference it makes, but in my case I tried transforming a subset of a “deconstructed” mesh, like so

Fig.1. GH def

Fig. 2. Mesh with a “flat cylinder” inside (barely visible) and the red points are filtered as being “inside” a BoundingBox of the cylinder. Next step to filter points inside the (leaning) cylinder.

But the above steps could be skipped altogether if I could only transform the disc (cylinder) together with the mesh points (around the center of the disc (cylinder), and then only do radius test (forcing horizontal radii before test), like so (VB.NET)

For Each pt In PtList

    '// Skip pts above and under

    If pt.Z > BBox.Max.Z OrElse
       pt.Z < BBox.Min.Z Then
           '// Outside
    Else

       '// OK, so now we are "between" the top and bottom surface of the cylinder.
       '// Make sure radii test of pts are made "horizontal" (same Z level)

       pt.Z = center_pt.Z

       // Now test if within radii of cylinder ( = inside)

       If center_pt.DistanceTo(pt) <= radius Then
           '// Inside
        Else
           '// Outside
       End if
   End If

Next

Should be super fast if Transform isn’t the bottleneck. I will try this.


Edit: The mesh I’m testing my code on (terrible quality, but that is part of the point with my test). I’m starting from a “centroid” of all points in the mesh:

mesh_to_forum.3dm (2.9 MB)

… the essential code to ge the “point centroid” :

        '// Sum all axis values based on the mesh vertices

        For Each pt As Point3d In MeshPts
            x_tmp += pt.X
            y_tmp += pt.Y
            z_tmp += pt.Z
        Next

        '// Average values per axis

        Dim C_avr As Point3d
        C_avr.X = x_tmp / MeshPts.Count
        C_avr.Y = y_tmp / MeshPts.Count
        C_avr.Z = z_tmp / MeshPts.Count
        
        '// The centroid : 
        
        Return C_avr

This centroid is then used as the center for the “bottom circle” that defines the cylinder to which heigth is added. My test case is:

  • Cylinder Height 10 mm
  • Cylinder Radii = 25
  • Cylinder Tilt angle XZ (Y axis) = -25 degrees

With these settings I get the following number of points (for a BBox) in 15 ms :

// Rolf

Q1: Is it possible to temporarily shut off “undo”?

Q2: Can multiple Transforms be “added” together into one? Why I’m asking is that I may change several input parameters and then rerun the solver, like

  • Position (for loop inside Solver adding and subtracting X,Y, Z values in steps and re-run)
  • Radius of Cylinder.
  • Height of Cylinder
  • Inclination of Cylinder (3D rotation of cylinder center axis)

I would like to “add” all these parameter changes into one Transform before doing the inclusion tests.

I also would like to “export” a Transform representing the final orientation to the outport to let also other “satellite” objects align with the Cylinder after each solution.

// Rolf

  1. I remember that there is something in the Options to adjust the undo settings … but, as usual, I’m unable to find it now …:blush:

  2. Sure:
    http://developer.rhino3d.com/api/RhinoCommonWin/html/M_Rhino_Geometry_Transform_op_Multiply_1.htm
    Just one thing.
    If I remember correctly (I think so) the docs are misleading:
    The result corresponds to applying first B, and then A

Perhaps this? (has both Set and Get methods…) :

Rhino.RhinoDoc.UndoRecordingEnabled

http://developer.rhino3d.com/api/RhinoCommonWin/html/P_Rhino_RhinoDoc_UndoRecordingEnabled.htm

// Rolf

I’m a bit late to the party, but Cylinder inclusion testing can be extremely fast. What you need to do however is find the central axis of the cylinder, then project each point to that axis. If the projection parameter > 1.0 then the point is outside (specifically above), if the projection parameter < 0.0 then the point is outside (specifically below). If the projection is 0 ≤ t ≤ 1 then you need to measure the actual distance to the point on the axis at t. If this distance is ≤ the cylinder radius, the point is inside.

You’d be hard pressed to come up with something faster than that, it’s a very quick rejection for a lot of points and a point-point distance measure for the remainder.