System and method for generating adaptively sampled distance fields with bounded distance trees
View Patent ↗A method generates an adaptively sampled distance field of an object by first defining a candidate cell of the adaptively sampled distance field. Then, distance values for the candidate cell are determined and stored in a bounded distance tree. The candidate cell is recursively subdividing into subdivided cells of the adaptively sampled distance field while determining and storing corresponding distance values of the subdivided cells in the bounded distance tree until a termination condition is reached. Lastly, the distance values are appended to the corresponding cells to generate the adaptively sampled distance field of the object.
1. A method for generating an adaptively sampled distance field of an object, comprising:
defining a candidate cell of the adaptively sampled distance field;
determining and storing distance values of the candidate cell in a bounded distance tree;
recursively subdividing the candidate cell into subdivided cells of the adaptively sampled distance field while determining and storing corresponding distance values of the subdivided cells in the bounded distance tree until a termination condition is reached; and
appending the distance values to the corresponding cells to generate the adaptively sampled distance field of the object.
2. The method of claim 1 further comprising:
arranging the cells of the adaptively sampled distance field in first hierarchical layers of the adaptively sampled distance field; and
arranging the corresponding distance values in second hierarchical layers of the bounded distance, and the termination condition is the number of second hierarchical layers.
3. The method of claim 1 further comprising:
arranging the cells of the adaptively sampled distance field in first hierarchical layers; and
arranging the corresponding distance values in second hierarchical layers, and the termination condition is an error measure associated with each distance value.
4. The method of claim 1 further comprising:
storing the bounded distance tree as an array; and
storing an associated validity bit for each distance value in the array, the validity bit indicating whether the distance value is valid.
5. The method of claim 4 further comprising:
storing the array in a hardware cache; and
storing the adaptively sampled distance field as a contiguous array in a main memory, the array storing the bounded distance tree being substantially smaller than the contiguous array.
6. The method of claim 1 further comprising:
associating a cell type with the candidate cell and the subdivided cells, the cell types include interior, exterior, and surface cells; and
performing the subdividing, determining and storing steps only for surface cells.
7. The method of claim 6 further comprising:
subdividing interior and exterior cells within a predetermined distance of a surface of the object.
8. The method of claim 1 further comprising:
determining the distance values by a distance function.
9. The method of claim 1 further comprising:
determining the distance values by interpolation.
10. The method of claim 1 wherein the candidate cell is a root cell of the adaptively sampled distance field during an initial generation of the adaptively sampled distance field.
11. The method of claim 1 wherein the candidate cell is a previously generated cell of the adaptively sampled distance field during a partial regeneration of the adaptively sampled distance field.
12. The method of claim 1 further comprising:
initializing fields of each cell, the fields including an error measure.