| 摘要 |
PROBLEM TO BE SOLVED: To generate the octal tree representation of a body in a nonprojection shape fast from polygon representation by generating a polygonally-sectioned voxel with some plane of a three-dimensional body and generating the octal tree by using a voxel decided to have a representative point inside. SOLUTION: A straight line Mr crosses the outline (r) or an (n)-gon at Mr1 -Mr3 on one side and at Mr4 -Mr6 on the other side each even-number of times, so it is judged that the point (r) is in an (n)-gon P. A straight line Ms passing a point (s) in a plane Q, on the other hand, crosses the outline of the (n)-gon P at Ms1 and Ms2 on one side of the point (s) and at Ms3 and Ms4 on the other hand each odd-number of times T, so it is judged that the point (s) is outside the (n)-gon. A voxel having the point (r) inside is called a black voxel and a voxel having it outside is called a white voxel. Then an octal tree is generated by using voxes having representative points inside. Consequently, this method is applicable even to a nonprojection body and the octal tree can be generated fast from polygon representation. |
