First of all, no idea exactly how to put this out or even where to ask, so please bear with me.

In the software we are developing, we have shapes that describe a scenario... think of it as a highly simplified svg. In our case we only have rectangles (half a dozen, give or take), defined by their height, width, rotation and position of the center.

We need to render a matrix (ie. 2d array) with the image of this scenario (150x100px) at a high frequency (roughly every 10 ms), but I cannot find an algorithm or a library to do so; Best I've been able to accomplish is ~50ms with a home made algorithm but it's not good enough.

My own algorithm roughly does:

drawing = [[0 for i in width] for _ in height]

for shape in shapes:
   __calculate_intersection(shape, 0, width, 0, height)


def __calculate_intersection(shape, x1, x2, y1, y2):
     global drawing
     if x1 == x2 or y1 == y2:
            return
     if x1   1 == x2 and y1   1 == y2:
            # If we are in a single cell, it is just 
            # checking whether the center of the cell is inside the object
            if drawing[x1][y1] == 0:
                if shape.is_point_in_obj(x1, y1):
                    drawing[x1][y1] = 100
            return

     if shape.bounding_box() does not touch our drawing:
            return 

     else:
            # if the area intersects the object bbox, 
            # then we iterate the recursion by dividing
            # the area along its longer side
            if i2 - i1 > j2 - j1:
                self.__calculate_intersection(o, i1, i1   (i2 - i1) // 2, j1, j2)
                self.__calculate_intersection(o, i1   (i2 - i1) // 2, i2, j1, j2)
            else:
                self.__calculate_intersection(o, i1, i2, j1, j1   (j2 - j1) // 2)
                self.__calculate_intersection(o, i1, i2, j1   (j2 - j1) // 2, j2)
            return

Clearly I need a better algorithm. Is there such thing out there? Or even better, are there any Python libraries to accomplish this goal? Or will I have to go into some GPU programming? How come the Tkinter Canvas can render it in less that 1ms at HD quality and I am struggling with such simple requirements?

CodePudding user response：

Quick description of solution:

• compute the coordinates of the four vertices, and sort by increasing Y (a full sort is not necessary, there are 8 possible orderings);

• split the polygon in three areas with horizontals (you get 2 triangles and a trapezoid);

• for the three areas, draw all horizontals at integer ordinates that cross them, and compute the two intersections with the oblique edges;

• fill the horizontal runs between the intersections.

CodePudding user response：

There are a lot of ways. An easy and fast way that works well for this case is:

1. Initialize the matrix with 0s
2. For each shape:
   • For each line that the shape touches:
     • Add 1 to the pixel on the left boundary of the shape. If that would be off the left edge of the image, then just add the 1 to the start of the line.
     • Add -1 to the pixel just after the right boundary of the shape. If that would be off the right edge of the image, then just skip it. (If it would be off the left edge, then you shouldn't have done this line -- the shape doesn't touch it).
3. When all the shapes are done, for each line:
   • calculate the running total of each line, changing pixels to 100 (black) where the sum is > 0, and 0 where the sum == 0.

In that way, any pixels that is covered by a shape will be colored black. This is quite quick, since you only process the edges of the individual shapes, with all the area-coloring done in a single pass at the end.