[Performance] Accel2D initilization Bottlenecks

[jfranmatheu]

Accel2D initilization Bottlenecks

Related issues: #842 - #1246 - #1423

The initialization of the Accel2D takes some seconds to complete (4-7) with just 6k faces in the tests performed in 2 different PCs, both with Windows 11, AMD cpu and NVIDIA gpu.

After reviewing the code I've seen there's room for improvements without major changes.

Performance bottlenecks:

As we see in the 'collect' and 'insert verts' sections, we can cache the results of Point_to_Point2Ds for each vertex to avoid repeated calls.

# collect all involved pts so we can find bbox
        with time_it('collect', enabled=Accel2D.DEBUG):
            bbox = BBox2D()
            with time_it('collect verts', enabled=Accel2D.DEBUG):
                bbox.insert_points(pt for v in verts for pt in Point_to_Point2Ds(v.co, v.normal))
            with time_it('collect edges and faces', enabled=Accel2D.DEBUG):
                bbox.insert_points(
                    pt
                    for ef in chain(edges, faces)
                    for ef_pts in zip(*[Point_to_Point2Ds(v.co, v.normal) for v in ef.verts])
                    for pt in ef_pts
                )

.........

# inserting verts
        with time_it('insert verts', enabled=Accel2D.DEBUG):
            for v in verts:
                for pt in Point_to_Point2Ds(v.co, v.normal):
                    tot_inserted += 1
                    i, j = self.compute_ij(pt)
                    self._put((i, j), v)

In the 'insert edges and faces', we see the same bottleneck issue, but we can pre-compute the ij coordinates and cache them to avoid extra compute. We can also remove the dedundant BBox2D creation for faces since we can directly compute min/max from the cached ij coordinates, which will speed up the code as well.

 # inserting edges and faces
        with time_it('insert edges and faces', enabled=Accel2D.DEBUG):
            for e in edges:
                self._insert_edge(e)
            for ef in faces:
                ef_pts_list = zip(*[Point_to_Point2Ds(v.co, v.normal) for v in ef.verts])
                for ef_pts in ef_pts_list:
                    tot_inserted += 1
                    bbox2 = BBox2D((self.compute_ij(pt) for pt in ef_pts))
                    mini, minj, maxi, maxj = int(bbox2.mx), int(bbox2.my), int(bbox2.Mx), int(bbox2.My)
                    sizei, sizej = maxi - mini + 1, maxj - minj + 1
                    if (spread := sizei*sizej) > max_spread[0]: max_spread = (spread, sizei, sizej)
                    for i in range(mini, maxi + 1):
                        for j in range(minj, maxj + 1):
                            self._put((i, j), ef)

Implications

• Laggy Tools
• Bad user experience (no interactive tools + long waits = frustration)

Proposed Solution

• Pre-compute and cache data to avoid bottlenecks.
• Long-term caching and partial-updating.
• Cython, CPYthon or similar.
• Change the accel2d to a more efficient structure in python.