I am implementing the last part of my robust back-end, a solid mesh reconstruction using adjacency graphs and opacity metrics between cells. Allows me to automatically fix up any errors that appears in the input geometry. The idea is super simple actually, it was used in the paper I base my implementation on and it works through simple heuristics to create the most likely outcome from a set of input polygons. You can´t just make any error become correct, but you can create a consistent set through the cells generate by the BSP partitioning by labeling the cells as solid/not-solid ,in a consistent manner in the BSP tree, and use the BSP tree to produce a solid polygonal surface. Using some trivial heuristics to decide when two neighboring cells are solid or not, is how you are able to fix simple mistakes in the surface and create a 2 manifold output. If the area between two cells is mostly covered by input geometry, you can say that one cell is solid the other is not. If the area between two cells is mostly covered by no input geometry, they are either both solid or both not, you label all cells that touch the “infinite” points at the borders as not solid.

And since the result of each cell depends on the results of another cell, you need to solve the unknown bounded cells in an iterative fashion until the change in the system becomes less then some threshold.

A Gauss-Seidel iterative linear solver is trivial to implement. I just need to add an adjacency graph into a special build of the BSP tree where the polygons do not use any sort of neighbor information to share and re-use border planes.

Lots of fun to implement over the Easter break, out here in the country side.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s