Patent ID: 6933939

Claim:
A method for correcting an adaptively sampled distance field of a model, the adaptively sampled distance field including a plurality of cells, each cell storing a plurality of distance values at vertices of the cell, the cells including interior cells, surface cells, and exterior cells, and neighboring cells having a common edge, comprising: marking selected cells as unprocessed cells; marking surface cells as processed cells; marking a particular vertex of each unprocessed cell as a minimum vertex, the minimum vertex having a minimum absolute value distance value; sorting the unprocessed cells in an ascending order of the minimum vertices; and a) appending, for each common edge of each unprocessed cell, in the sort order, distance values of neighboring processed cells to the common edge; b) adjusting the distance values of the vertices of the unprocessed cell according to the appended distance values of the edges and the distance values of the vertices; c) marking the unprocessed cell as processed; and repeating steps a, b, and c until all cells are processed.