Draw triangle in 3D numpy array in python

Question

Let's say I have a 3D-array (rectangular cuboid) with some shape, for example (48, 32, 64). I have 3 points in this cube with some coordinates. x1 = (10, 20, 30) x2 = (21, 15, 34) x3 = (33, 1, 62)

I need to draw filled plane in this 3D-array limited by this points, e.g. draw triangle in 3D array. In 2D case we can do it with openCV: Triangle Filling in opencv

import numpy as np
a = np.zeros((48, 32, 64), dtype=np.uint8)
x1 = (10, 20, 30)
x2 = (21, 15, 34)
x3 = (33, 1, 62)
a = draw_3D_triangle(a, x1, x2, x3)

But what is the easiest way to do so in 3D case?

Answer 1

(EDITED: I had previously forgot to include the code for full_triangle()).

---

Assume you have an algorithm that draws lines, like Bresenham's Algorithm and assume it can be generalized to the N-dim case.

Luckily the raster-geometry package has such an N-dim implementation of the Bresenham algorithm.

(Disclaimer: I am the main author of the package.)

Let A, B, C be the coordinate of the vertices of the triangle ABC.

---

If you need to draw only the outer shape, you can just use the algorithm using the various combinations of the points to form the lines: AB, BC, CA.

In code, that would simply be:

import numpy as np
import raster_geometry as rg


a, b, c = (1, 1), (3, 7), (6, 4)
coords = set(rg.bresenham_lines((a, b, c), closed=True))
print(coords)
# {(1, 2), (6, 4), (3, 2), (4, 6), (5, 5), (2, 2), (2, 3), (3, 6), (2, 4), (4, 3), (3, 7), (2, 5), (1, 1), (5, 3)}
arr = rg.render_at((10, 10), coords)
print(arr.astype(int))
# [[0 0 0 0 0 0 0 0 0 0]
#  [0 1 1 0 0 0 0 0 0 0]
#  [0 0 1 1 1 1 0 0 0 0]
#  [0 0 1 0 0 0 1 1 0 0]
#  [0 0 0 1 0 0 1 0 0 0]
#  [0 0 0 1 0 1 0 0 0 0]
#  [0 0 0 0 1 0 0 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0]]

If you need to draw a full triangle, you can do the following:

• draw a line from point A to point B
• draw a line from C to a point in the AB line, for every point in the line.

Although this may not be the most efficient approach, it will work reasonably well. It is possible that some points near the vertices may be missed. In that case, it is sufficient to repeat the same procedure looping through all three vertices.

In code, this could read:

import numpy as np
import raster_geometry as rg


def full_triangle(a, b, c):
    ab = rg.bresenham_line(a, b, endpoint=True)
    for x in set(ab):
        yield from rg.bresenham_line(c, x, endpoint=True)


a, b, c = (1, 1), (3, 7), (6, 4)
coords = set(full_triangle(a, b, c))
print(coords)
# {(1, 2), (6, 4), (5, 4), (3, 2), (3, 3), (5, 5), (4, 6), (4, 5), (4, 4), (1, 1), (2, 3), (4, 3), (2, 2), (3, 6), (3, 7), (2, 5), (5, 3), (3, 4), (2, 4), (3, 5)}
arr = rg.render_at((10, 10), coords)
print(arr.astype(int))
# [[0 0 0 0 0 0 0 0 0 0]
#  [0 1 1 0 0 0 0 0 0 0]
#  [0 0 1 1 1 1 0 0 0 0]
#  [0 0 1 1 1 1 1 1 0 0]
#  [0 0 0 1 1 1 1 0 0 0]
#  [0 0 0 1 1 1 0 0 0 0]
#  [0 0 0 0 1 0 0 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0]]

---

Note that while the examples are in 2D, they work for N-dim. For example, the 3D triangle you are after can be generated with:

x1 = (10, 20, 30)
x2 = (21, 15, 34)
x3 = (33, 1, 62)
coords = set(full_triangle(x1, x2, x3))
arr = rg.render_at((48, 32, 64), coords)

Answer 2

In order to render your 3d triangle you must project it to 2d, either by using some ready made solution, for example mplot3d or you can manually project the 3d data to 2d.

The simplest projection is orthographic. You can achieve this by simply ignoring the z dimension of the data.

For perspective projection, divide the 3d data by the z value:

import numpy as np

p1 = (10, 20, 30)
p2 = (21, 15, 34)
p3 = (33, 1, 62)

tri3d = np.array([p1, p2, p3])
ortho2d = tri3d[:, :2]
proj2d = tri3d[:, :2] / tri3d[:, 2:]

print(tri3d)
print(ortho2d)
print(proj2d)

result:

[[10 20 30]
 [21 15 34]
 [33  1 62]]
[[10 20]
 [21 15]
 [33  1]]
[[0.33333333 0.66666667]
 [0.61764706 0.44117647]
 [0.53225806 0.01612903]]

You can then use the same triangle filling you referred to in your question. Some considerations are the bounds of the space you are in, and the scale of any projected triangle. Notice that the projected coordinates are all quite small. In which case you might scale them up by some factor (equivalent to the focal length in a camera calibration matrix).