Storage medium having stored thereon image processing program and image processing apparatus

• US 20090244063A1
• Filed: 06/23/2008
• Published: 10/01/2009
• Est. Priority Date: 04/01/2008
• Status: Active Grant

• Current Assignee: Nintendo Company Limited
• Original Assignee: Nintendo Company Limited
• Inventors: Dohta, Takuhiro
• Granted Patent: US 8,259,107 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: A63F 13/52 involving aspects of the displayed game scene
• CPC Class Codes: A63F 13/95 Storage media specially adapted for storing game information, e.g. video game cartridges
• CPC Class Codes: A63F 2300/206 Game information storage, e.g. cartridges, CD ROM's, DVD's, smart cards
• CPC Class Codes: A63F 2300/66 for rendering three dimensional images
• CPC Class Codes: A63F 2300/6615 using models with different levels of detail [LOD]
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2210/36 Level of detail

Abstract

A virtual plane surface PL is divided into a plurality of square regions such that the closer distance to a virtual camera VP a square region is located at, the smaller areas the square region is divided into. Distance information 41 indicative of distances of respective vertices composing each of the square regions from the virtual plane surface PL is read from the internal main memory 11e. Further, coordinate points of positions, which are distanced from respective vertices, which compose polygonal shape regions included in each of the square regions, by distances indicated by the read distance information in a direction perpendicular to the virtual plane surface PL, are used as polygon vertices, which define polygons, whereby the polygons corresponding to the curved surface SF are generated. From each of the square regions, substantially a common number of polygons are generated. In this manner, appropriate polygon information of the curved surface SF which is capable of securing a drawing quality can be generated.

Claims

1. A computer readable storage medium (11e) having stored thereon an image processing program for drawing an image of a curved surface as viewed from a virtual camera situated in a virtual three-dimensional space, an undulation of the curved surface being defined by a distance from a virtual plane surface arranged in the virtual three-dimensional space, the image processing program causing a computer to execute:

a plane surface division step of dividing the virtual plane surface into a plurality of polygonal shape regions such that the closer a region is to the virtual camera, the smaller areas the region is divided into;

a first distance reading step of reading, from storage means, distance information indicative of distance from the virtual plane surface, with respect to respective vertices of the plurality of polygonal shape regions;

a first coordinate point calculation step of calculating coordinate points of position which are respectively distanced from the vertices composing the plurality of polygonal shape regions by distances indicated by the distance information, which is read in the first distance reading step, in a direction perpendicular to the virtual plane surface;

a polygon generation step of generating polygons by using the coordinate points calculated in the first coordinate point calculation step as polygon vertices which define the polygons, the number of the polygons being substantially constant in each of the plurality of the polygonal shape regions; and

a drawing step of drawing an image of the polygons which are generated in the polygon generation step, the image as being viewed from the virtual camera.

2. The computer readable storage medium having stored thereon the image processing program according to claim 1, wherein

the plane surface division step

includes a size evaluation value calculation step of calculating a size evaluation value indicative of a size of an image of each of the plurality of the polygonal shape regions as viewed from the virtual camera, and

divides each of the plurality of the polygonal shape regions such that the size evaluation value calculated in the size evaluation value calculation step becomes equal to or lower than a predetermined threshold value.

3. The computer readable storage medium having stored thereon the image processing program according to claim 2, wherein the size evaluation value calculation step calculates, as the size evaluation value, an area of an image of a sphere having a great circle which is inscribed in or circumscribed around each of the plurality of polygonal shape regions, the area of the image as being viewed from the virtual camera.

4. The computer readable storage medium having stored thereon the image processing program according to claim 2, wherein

the plane surface division step further includes:

a first division step of dividing the virtual plane surface into a first predetermined number of regions;

a division necessity determination step of determining, with respect to each of the first predetermined number of regions generated in the first division step, whether or not the size evaluation value calculated in the size evaluation value calculation step is equal to or lower than the threshold value; and

a second division step of further dividing a region, among the first predetermined number of regions, whose size evaluation value is determined not to be equal to or lower than the threshold value in the division necessity determination step, into the first predetermined number of regions,

the division necessity determination step determines, with respect to respective regions additionally generated in the second division step, whether or not the size evaluation value thereof calculated in the size evaluation value calculation step is equal to or lower than the threshold value, and

the plane surface division step repeatedly executes the division necessity determination step and the second division step until the size evaluation value of all the generated regions become equal to or lower than the threshold value.

5. The computer readable storage medium having stored thereon the image processing program according to claim 4, wherein

the first division step equally divides the virtual plane surface into the first predetermined number of regions, and

the second division step equally divides the region, among the first predetermined number of regions, whose the size evaluation value is determined not to be equal to or lower than the threshold value in the division necessity determination step, into the first predetermined number of regions.

6. The computer readable storage medium having stored thereon the image processing program according to claim 5, wherein

the virtual plane surface is a quadrangular plane surface,

the polygonal shape is of a quadrangular shape,

the first division step divides the quadrangular virtual plane surface into quarters by two straight lines which are each formed by connecting middle points of two facing sides of the quadrangular virtual place surface, and

the second division step divides the quadrangular region, whose size evaluation value is determined not to be equal to or lower than the threshold value in the division necessity determination step, into quarters by two straight lines which are each formed by connecting middle points of two facing sides of the quadrangular region.

7. The computer readable storage medium having stored thereon the image processing program according to claim 6, wherein

the image processing program further causes the computer to execute a re-division step of dividing each of the plurality of polygonal shape regions, which are generated in the plane surface division step, into a second predetermined number of small regions which are each of a quadrangular shape,

the first distance reading step reads the distance information of respective vertices composing each of the quadrangular small regions, which are generated in the re-division step, from the storage means,

the first coordinate point calculation step calculates coordinate points of positions which are respectively distanced from of the vertices composing each of the quadrangular small regions generated in the re-division step by distances indicated by the distance information read in the first distance reading step in a direction perpendicular to the virtual plane surface, and

the polygon generation step generates polygons respectively having the coordinate points calculated in the first coordinate point calculation step as the polygon vertices.

8. The computer readable storage medium having stored thereon the image processing program according to claim 7, wherein

the polygon generation step includes a triangle generation step of generating two triangle polygons corresponding to two triangle regions which are obtained by dividing each of the quadrangular small regions, which are generated in the re-division step, by a diagonal line therethrough.

9. The computer readable storage medium having stored thereon the image processing program according to claim 8, wherein

the re-division step equally divides each of the quadrangular regions generated in the plane surface division step into an even number of small regions, respectively, in two directions along adjacent sides of each of the quadrangular region,

the triangle generation step includes:

an outer-circumference extraction step of extracting outer-circumference small regions, from among the second predetermined number of small regions, which each includes a part of sides composing each of the quadrangular regions generated in the plane surface division step as at least one of sides composing each of the small regions, and

a diagonal line selection step of selecting, with respect to outer-circumference small regions, among the outer-circumference small regions extracted by the outer-circumference extraction step, which include vertices composing each of the quadrangular regions generated in the plane surface division step, diagonal lines including the vertices as diagonal lines for dividing the quadrangular outer-circumference small regions, and also of selecting, with respect to outer-circumference small regions, among the outer-circumference small regions extracted by the outer-circumference extraction step, which do not include the vertices composing each of the quadrangular regions generated in the plane surface division step, the diagonal lines for dividing the quadrangular outer-circumference small regions such that the diagonal lines of the outer-circumference small regions adjoining respectively are approximately perpendicular to each other.

10. The computer readable storage medium having stored thereon the image processing program according to claim 6, wherein the polygon generation step includes a triangle generation step of generating two triangle polygons corresponding to two triangle regions obtained by dividing each of the quadrangular regions, which are generated in the plane surface division step, by a diagonal line therethrough.

11. The computer readable storage medium having stored thereon the image processing program according to claim 1, wherein the image processing program further causes the computer to execute:

a field of view determination step of determining whether or not each of the polygonal shape regions generated in the plane surface division step is in an out-of-view region, which is not included in the image as viewed from the virtual camera; and

a region exclusion step of excluding a region, among the polygonal shape regions generated in the plane surface division step, which is determined to be in the out-of-view region in the field of view determination step, from target regions which are subject to processing in the first distance reading step, the first coordinate point calculation step and the polygon generation step.

12. The computer readable storage medium having stored thereon the image processing program according to claim 1, wherein

the image processing program further causes the computer to execute:

a reference point setting step of setting points on the virtual plane surface, the points being interrelated to the distance information and stored in the storage medium, as reference points with respect to which normal vector information is generated,

an outer-circumference point setting step of setting, on the virtual plane surface, two points which are distanced from each reference point by a predetermined unit distance in a predetermined first direction, and of setting another two points which are distanced from each reference point by the unit distance in a second direction which is perpendicular to the first direction;

a second distance reading step of reading, from the storage medium, the distance information on each reference point set in the reference point setting step and on the four points set in the outer-circumference point setting step;

a second coordinate point calculation step of calculating coordinate points of positions which are respectively distanced from each reference point and the four points by distances indicated by the distance information read in the second distance reading step in a direction perpendicular to the virtual plane surface;

a normal vector calculation step of calculating normal vectors of four triangle polygons, which each includes as vertices thereof, a point corresponding to each reference point, a point corresponding to either of the two points which are distanced from each reference point in the first direction, and a point corresponding to either of the two points which are distanced from each reference point in the second direction, among the five coordinate points calculated in the second coordinate point calculation step; and

an average calculation step of calculating an average value of the four normal vectors calculated in the normal vector calculation step, and of interrelating the average value to information indicative of the position of each reference point on the virtual plane surface so as to be stored in the storage medium,

the polygon generation step includes a normal vector setting step of reading a normal vector from the storage medium and set the normal vector to each of the polygon vertices.

13. The computer readable storage medium having stored thereon the image processing program according to claim 1, wherein

the image processing program further causes the computer to execute a normal vector reading step of reading, from the storage medium, normal vector information indicative of a tilt of the curved surface at each of the coordinate points calculated in the first coordinate point calculation step, and

the polygon generation step includes a normal vector setting step of setting the normal vector information read in the normal vector reading step as the normal vector information of each of the polygon vertices corresponding to each of the coordinate points.

14. The computer readable storage medium having stored thereon the image processing program according to claim 13, wherein, in the storage means, the normal vector information is stored as image information such that positions and colors composing the image correspond to respective positions and normal vectors on the curved surface, respectively.

15. The computer readable storage medium having stored thereon the image processing program according to claim 1, wherein, in the storage means, the distance information is stored as image information such that positions and colors composing the image correspond to respective positions on the curved surface and distances from the virtual plane surface, respectively.

16. The computer readable storage medium having stored thereon the image processing program according to claim 1, wherein the curved surface is a landform arranged in the virtual three-dimensional space.

17. An image processing apparatus for drawing an image of a curved surface as viewed from a virtual camera situated in a virtual three-dimensional space, an undulation of the curved surface being defined by a distance from a virtual plane surface arranged in the virtual three-dimensional space, the image processing apparatus comprising:

plane surface division means for dividing the virtual plane surface into a plurality of polygonal shape regions such that the closer a region is to the virtual camera, the smaller areas the region is divided into;

first distance reading means for reading, from storage means, distance information indicative of the distance from the virtual plane surface, with respect to respective vertices of the plurality of polygonal shape regions;

first coordinate point calculation means for calculating coordinate points of positions which are respectively distanced from each of the vertices composing the polygons corresponding to the plurality of polygonal shape regions by distances indicated by the distance information read by the first distance reading means in a direction perpendicular to the virtual plane surface;

polygon generation means for generating polygons by using the coordinate points calculated by the first coordinate point calculation means as polygon vertices defining each of the polygons, the number of the polygons being substantially constant in each of the plurality of the polygonal shape regions; and

drawing means for drawing an image of the polygons which are generated in the polygon generation step, the image as being viewed from the virtual camera.