Finding the Shape of a Room

Below is an animation of the primitive extraction and meshing algorithm. The algorithm looks at a horizontal slice of the point cloud and extracts a large number of candidate rectangles (magenta) that describe data in the cloud.

It then runs a scoring test to see how well the data fits the model and greedily adds good rectangles to the 2D mesh model (in yellow). What we end up with is a nice line-based approximation of the shape of the room, that also captures some nooks and crannies like door/window jambs.

Not visualized here are several thousands of rectangles that the algorithm rejects for having a poor fitness score. (There are about 45,000 rectangles in total.)