The last month has been a bit of a ride. Elin needed to have an operation, so I have had to deal with baby issues almost exclusively, picking up, dropping off and most daily maintenance. We are about to sign a purchase agreement for an apt, so that kept us busy through a few nights, pondering over options. And my day job has this deadline this weekend that has also been squeezing additional hours from my days, not to mention that Elin is running for office in this little town so her schedule is even more bloated than mine.
My personal tasks were left on a very slow broil, but I managed to finish the solid mesh reconstruction using the BSP trees, adjacency graphs and iterative linear solvers. Just as I am typing this, I added the final bits to the implementation, but I have yet to test this on actual crap data. The idea is sound and simple, and the only involved part was to create the geometric links between the cells, using a very similar concept as the sub-hyperplane of the bsp tree, but making sure that it is cut against the borders of every cell.
Why this works out is because you can set up the neighbor relations as a square linear matrix, set up the data so that the area between each cell corresponds to the relation between each coefficient in the matrix. And since the total area of each cell is always larger or equal to any other separating area, it fits within a weak diagonal dominant linear system that will always have an inverse. Hence, it will always produce a consistent output. ( but the output could be visually unfavorable if the state of the geometry is too bad). Magic of mathematics and robust computations. Mx =b. M is the matrix of your neighbour relations, x is your unbounded known cells and b is your internal unknowns. But, you don’t really need to do the computations using a matrix, that is more just to prove that the idea works. Using a linear solver, give all the unknowns a starting value of zero, all the known unbounded cells that touch points at infinity a -1. Then just solve and update each value of the bounded cells in an iterative fashion, the solution will converge on the correct values over time(or until that each iterations incremental effects is less than some sensible small number).
After this, I am creating some demos and tests for blogging and bragging and so moving into creating UI stuff and making all this hard ass magic do wonderful things to geometry with application features.
I can now do robust correction on bad geometry coming in to ensure that the geometry being operated on is good and legal. The geometry that passes the input guards will run to completion, unconditionally and producing exact results. The output geometry is free from any manifold issues such as self intersections and t-junctions.
Garbage in, Gold nuggets out. Geometric Alchemy?
V 