Patent ID: 6995766
Filing Date: 2006-02-07
Classification: G06T

Abstract:
1. A hierarchical lattice generating method comprising: a generating step of generating a hierarchical lattice by dividing a group of cells that are composed of vertices and line segments present in a predetermined area, in accordance with a resolution; a representing step of representing a boundary surface, which is provided in the area, in the hierarchical lattice by hierarchically dividing cells in a vicinity of a boundary surface in the boundary surface; a first step of assigning a first value as an initial value to all of the vertices in the area in an initial state; a second step of assigning a second value to each of vertices in focus, out of the vertices in the area that have the first value, if any cell to which each of the vertices in focus belongs includes the boundary surface and otherwise assigning a third value to each of the vertices in focus, out of the vertices in the area that have the first value; and a third step of dividing each of the cells, out of all of the cells in the area, to which vertices that have the second value belong, assigning the third value to a vertex that is newly generated by the dividing if vertices at both ends of a line segment that has the newly generated vertex as a midpoint have the third value, and otherwise assigning the first value to the newly generated vertex.