JP3733207B2 - Polyhedron generation method, polyhedron generation apparatus, recording medium, and color image processing apparatus - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a polyhedron generation method, a polyhedron generation device, a recording medium, and a color image processing device .
[0002]
[Prior art]
It is widely known that there are three attributes (brightness, hue, and saturation) as elements constituting a color. As an example of assigning these three attributes to orthogonal coordinates and expressing them in a three-dimensional Euclidean space, the RGB color space, the XYZ color space, and the like are widely used.
[0003]
Among various color spaces, there is a uniform perceptual color space as a combination of distance and color difference in the space. Among them, the CIE 1976-Lab space (hereinafter simply referred to as “Lab color space”) is one of uniform perceptual color spaces often used for analyzing the color mapping state and the color reproduction region of each color device. In order to analyze the color mapping state and the color reproduction area of each color device, it is necessary to measure or calculate the color (Lab value) output from the color device and plot it in the Lab color space. Here, plotting means writing the data on a graph. In the case of a two-variable plot, a point sequence or the like is written at a coordinate position on a plane such as an XY coordinate. However, when the coordinate is configured as a space, a 3D rendering function must be used.
[0004]
The 3D rendering system reproduces an object in space as a two-dimensional image in a pseudo manner by generating an image mapped onto a certain projection plane through a preset observation position. Furthermore, functions such as rotation and enlargement / reduction are often added in order for the operating user to observe the situation in more detail. By using such a function, it has been conventionally performed to visualize color data scattered in a color space.
[0005]
[Problems to be solved by the invention]
There are many types of 3D rendering systems that provide the 3D rendering function described above. Among them, there are some which need to match the normal vectors of the triangular polygons to be drawn for the convenience of hidden surface processing.
[0006]
However, there is no technical disclosure of a technique for matching the normal vectors of the polygon group by automatic processing for a polyhedron composed of triangular polygons. For this reason, in the three-dimensional rendering system in which the normal vectors of the triangular polygons to be drawn must coincide with each other because of hidden surface processing, it has been impossible to draw a polygon group having irregular normal vectors.
[0007]
Here, in the three-dimensional rendering system, the relationship between the order of the three vertices of the registered triangular polygon and the direction of the normal vector of the triangular polygon will be described with reference to FIG.
[0008]
Considering the normal vector in a triangular polygon, the length is uniquely determined, but its direction must be clearly defined as necessary. Therefore, when viewed in the order of the registered vertices, the direction of the normal vector is defined as the direction of advance in the same way as the direction of the right-handed screw. In the case of a triangular polygon registered in the clockwise direction of 04 → 19 → 05, the normal vector is directed in the back direction, which is the same as the case where the right screw advances when it rotates clockwise. On the other hand, in the case of a triangular polygon registered as 04 → 11 → 05, the normal vector is directed in the forward direction, which is the same as the direction that proceeds when the right screw is rotated counterclockwise. From this example, it can be seen that the normal vectors of the triangular polygon registered as 04 → 19 → 05 and the triangular polygon registered as 04 → 11 → 05 do not match.
[0009]
In addition, when such a triangular polygon group whose normal vectors do not match is displayed in the above-described system, there is a problem that a triangular polygon that should be originally drawn may not be displayed.
[0010]
The present invention aims to solve such inconveniences.
[0011]
[Means for Solving the Problems]
The polyhedron generation method according to the present invention is, for example, a polyhedron generation method used in a polyhedron generation apparatus that generates a polyhedron using a triangular polygon, and the normal vector of the triangular polygon and an internal point of the polyhedron are used to generate the polyhedron. If the inner product of the vector into triangles is negative, characterized by having a changing step of Ru is changed normal vectors of the triangles in the polyhedron generating device. Another polyhedron generation method according to the present invention is, for example, a polyhedron generation method used in a polyhedron generation device that generates a polyhedron using a triangular polygon, the normal vector of the triangular polygon, and the polyhedron of the polyhedron According to the present invention, the polyhedron generating device has a changing step of changing a normal vector of the triangular polygon according to whether or not an inner product with a vector from an internal point to the triangular polygon is negative. A color image processing apparatus according to the present invention uses, for example, the above-described polyhedron generation method.
[0012]
Polyhedron generating apparatus according to the present invention, for example, a polyhedron generating unit for generating a polyhedron with triangular polygon, and the normal vector of the triangle polygon, from the internal point of the polyhedron with the vector to the triangles If the inner product is negative, and changes the normal vectors of the triangular polygons. Another polyhedron generating apparatus according to the present invention is a polyhedron generating apparatus that generates a polyhedron using, for example, a triangular polygon, and the normal vector of the triangular polygon and the internal point of the polyhedron to the triangular polygon. The normal vector of the triangular polygon is changed according to whether or not the inner product with the vector is negative. A color image processing apparatus according to the present invention includes, for example, the polyhedron generation apparatus described above.
[0013]
In the recording medium according to the present invention, for example, the inner product of the step of generating a polyhedron using a triangular polygon, the normal vector of the triangular polygon, and the vector from the internal point of the polyhedron to the triangular polygon becomes negative. In this case, a program for causing a computer to execute a step of changing a normal vector of the triangular polygon is recorded. Another recording medium according to the present invention includes, for example, a step of generating a polyhedron using a triangular polygon, an inner product of a normal vector of the triangular polygon, and a vector from an internal point of the polyhedron to the triangular polygon. A program for causing a computer to execute a step of changing a normal vector of the triangular polygon according to whether or not is negative is recorded.
[0030]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, the present invention will be described in detail with reference to the drawings.
[0031]
A first embodiment of the present invention will be described with reference to FIGS.
[0032]
First, a schematic configuration of the present invention will be described. FIG. 6 shows an example of a three-dimensional rendering system 10 (polyhedron generation device) that provides a 3D rendering function in the color image processing apparatus 1.
[0033]
The three-dimensional rendering system 10 includes a data generation unit 11, a data change unit 12, and a display unit 13. Reference numeral 14 denotes a file system for storing the generated polyhedron data. Reference numeral 15 denotes a memory used in an embodiment described later.
[0034]
Here, the data generation means 11 takes in a sequence of points scattered in the coordinate space, derives a triangle from the search target side, and generates the vertex of the triangle as a data group of triangular polygons constituting the polyhedron. Through such polyhedron generation processing, the vertices of each triangular polygon are registered in the file system 14 as a set of data.
[0035]
The data changing means 12 calculates the normal vector of each triangular polygon constituting the polyhedron and matches the normal vector of all the triangular polygons constituting the polyhedron by appropriately changing the normal vector as necessary. Let That is, first, one point is set inside the generated polyhedron. Normally, the centroid point obtained from the triangular polygon coordinates is within the polyhedron, so that the centroid point is used as the inner point, but it is not necessary to be the centroid point. Next, a set of registered vertex data of triangular polygons is extracted. As the vertex data, an outer product vector is obtained from the registered order and the coordinate data of the vertex, and this is used as a normal vector. Next, a centroid point as a triangle of the triangular polygon is obtained, and a vector connecting the internal point and the centroid point as a triangle is calculated by obtaining a vector with the internal point. Next, an inner product of the calculated vector and the normal vector is taken, and the order of the registered vertex data is appropriately changed as necessary using the obtained scalar value. By such processing, the normal vectors of all the triangular polygons are matched.
[0036]
The display means 13 displays the polyhedron in which the normal vectors after matching the order of the vertices of the triangular polygons constituting the polyhedron are all matched.
[0037]
Hereinafter, preferred examples according to the present invention will be described in detail with reference to the drawings.
[0038]
FIG. 1 is a flowchart showing a polyhedron generation process surrounding a sequence of points scattered in a coordinate space. First, in step S11, initialization processing is performed. Here, the first triangle is searched. The first triangle is searched in the vicinity of the extreme point such as the maximum value or the minimum value of the point sequence scattered in the coordinate space. Next, in step S12, the sides to be searched are reorganized, and the sides to be searched are registered in the file system 14.
[0039]
In step S13, it is determined whether or not the search is completed by sequentially examining the edges registered in step S12. If the search is not completed, the process proceeds to step S14, where the address of the search target side is accessed, and the coordinate data and the like of the side registered in the file system 14 are extracted.
[0040]
In step S15, it is verified whether a new triangle can be derived from the search target side based on the coordinate data extracted from the file system 14, and a new vertex candidate is searched. If it is determined in step S16 that the new vertex candidate does not overlap with the one already registered, if it is a new registration target, additional registration is performed in the file system 14 in step S17. By sequentially searching in this way and deriving new triangles from each triangle and registering them, polygon data can be generated.
[0041]
2 described above, as shown in FIGS. 4 and 5, it is possible to automatically generate a polyhedron that surrounds a point sequence scattered in a coordinate space. Next, in the three-dimensional rendering system, the relationship between the order of the three vertices of the registered triangular polygon and the direction of the normal vector of the triangular polygon will be described with reference to FIG.
[0042]
Considering the normal vector in a triangular polygon, the length is uniquely determined, but its direction must be clearly defined as necessary. Therefore, in the present invention, when viewed in the order of the registered vertices, the direction of the normal vector is defined as the direction of the normal vector, and the normal of all the triangular polygons constituting the polyhedron is defined. Performs processing to align vector directions.
[0043]
In the example shown in FIG. 9 described above, in the case of a triangular polygon registered in the clockwise direction of 04 → 19 → 05, the normal vector faces in the back direction, and the two triangular polygons are adjacent to each other. The normal vectors indicate completely opposite directions. In such a case, the direction of the normal vector is changed. Specifically, as shown in FIG. 3, the normal vectors are aligned by rearranging 04 → 19 → 05 and re-registering 04 → 05 → 19.
[0044]
In order to make all the normal vectors of the triangular polygons constituting the polyhedron coincide, the normals of all the triangular polygons need to be set outward. To do this, if a vector is calculated from the point inside the polyhedron (inner point or centroid) to the centroid of each triangle, the inner product of the vector and the normal vector is taken, and the inner product value becomes negative A process of changing the registration order of the vertex data of the triangular polygon may be performed.
[0045]
FIG. 1 is a flowchart for explaining a data change process for examining the vectors of each triangular polygon and changing the registration order of vertices in order to match the normal vectors of all the triangular polygons constituting the polyhedron.
[0046]
First, in step S411, initialization processing is appropriately performed. In the data reading process in step S412, each triangular polygon data recorded in the file system 14 is read. In step S413, the barycenter of the polyhedron is calculated based on the coordinates of the read triangular polygon data. In the reading process in step S421, the vertex coordinates are read again.
[0047]
In the vector calculation process in step S422, the center of gravity of the triangle is obtained, and the vector A directed to the center of gravity of the triangle is calculated from the center of gravity of the polyhedron obtained in step 413. In the normal vector calculation processing in step S423, normal vector components are calculated based on the registered vertex order, and in the inner product calculation processing in step S424, the inner product calculation of the normal vector and the vector A is performed.
[0048]
The determination process in step S425 is configured to branch to the rearrangement process in step S426 when the calculated inner product value is a negative number. In the rearrangement process in step S426, a process of exchanging the second and third data which are the vertex data of the triangular polygon registered in the file system 14 is performed. In the end determination process of step S427, it is determined whether or not the reading has been completed by referring to the file structure. If the reading has not ended, the process returns to the reading process of step S421, and if the reading has ended, the end process of step S428 is performed. Proceed to ending processing.
[0049]
By appropriately changing the vertex registration order as described above, the normal vectors of all the triangular polygons constituting the polyhedron can be matched.
[0050]
Next, a second embodiment of the present invention will be described with reference to FIG.
[0051]
In this example, as shown in FIG. 6, in the process of generating and changing a polyhedron, instead of reading and processing data already registered in the file system 14 and the like as in the example of the first embodiment, Data read processing is executed using the memory 15.
[0052]
First, in the initialization processing 511 in step S511, initialization processing is performed as appropriate. In the data reading process in step S152, the point sequence data recorded in the file system 14 is read. The search end determination process in step S513 is the same process as step S13 in FIG. 2, and the search registration process in step S514 is a process substantially similar to the process from S14 to S17 in FIG.
[0053]
In this example, without registering in the file system 14 here, the process proceeds to the next process while temporarily retaining the data on the memory 15.
[0054]
In the center-of-gravity point calculation process in step S515, the data of the triangular polygon recorded on the memory 15 is accessed to calculate the center-of-gravity point of the polyhedron. In the coordinate extraction process in step S521, the data on the memory 15 is accessed again, and the vertex coordinate data is extracted. In the vector calculation process in step S522, a centroid point of the triangle is obtained, and a vector A directed to the centroid point of the triangle is calculated from the centroid point of the polyhedron obtained in step S515. In the normal vector calculation process in step S523, a normal vector component is calculated based on the registered order of vertices, and in the inner product calculation process in step S524, an inner product calculation of the normal vector and the vector A is performed.
[0055]
In the determination process of step S525, when the calculated inner product value is a negative number, the process branches to the rearrangement process of step S526. In the rearrangement process in step S526, the second and third data that are the vertex data of the triangular polygons registered in the memory 15 are exchanged. In the end determination process in step S527, it is determined whether or not the process has been completed by referring to a pointer or the like that refers to registered data. If it has not been completed, the process returns to the extraction process in step S521. Proceeding to an end process, an end process such as a data write / save process on the memory 15 and a memory 15 release process is appropriately performed.
[0056]
Next, a third embodiment of the present invention will be described with reference to FIG.
[0057]
In this example, after the point sequence data of FIG. 4 is input, a process for sequentially displaying the retrieved triangular polygons on the display means 13 at the stage of constructing the polyhedron of FIG. 5 is provided.
[0058]
First, in the data reading process in step S611, the point sequence data recorded in the file system 14 is read. In the center point calculation process in step S612, the center point (internal point) when the polyhedron is configured is calculated from the maximum value and the minimum value of each coordinate component in each data.
[0059]
The search end determination process in step S613 is a process corresponding to S13 in FIG. 2, and the search end determination process is repeated until the process ends. In the search process of step S621, a triangular polygon to be newly registered is searched and temporarily registered in a temporary area. In the vector calculation process in step S622, a vector A heading from the center point of the polyhedron obtained in step S612 to any one of the three vertices forming the triangular polygon is calculated.
[0060]
In the normal vector calculation process in step S623, a normal vector component is calculated based on the order of the tentatively registered vertices, and in the inner product calculation process in step S624, an inner product calculation of the normal vector and the vector A is performed. .
[0061]
In the determination process of step S625, when the calculated inner product value is a negative number, the process branches to the rearrangement process of step S626. In the rearrangement process in step S626, the second and third data that are the vertex data of the triangular polygons registered in the memory 15 are exchanged. In the drawing process in step S627, the triangular polygon with the normal vector optimized is additionally displayed on the display means 13, and the additional operation is repeated until all the searches are completed.
[0062]
The present invention may be applied to a system composed of a plurality of devices or an apparatus composed of a single device. Needless to say, the present invention can also be applied to a case where the present invention is achieved by supplying a program to a system or apparatus. In this case, by reading a storage medium storing a program represented by software for achieving the present invention into the system or apparatus, the system or apparatus can enjoy the effects of the present invention.
[0063]
【The invention's effect】
According to the present invention, the normal vector of the triangular polygon is changed according to whether or not the inner product of the normal vector of the triangular polygon and the vector from the internal point of the polyhedron to the triangular polygon is negative. Therefore, the inconvenience caused by the direction of the normal vector can be solved.
[Brief description of the drawings]
FIG. 1 is a flowchart showing a data change process at the time of generating polygon data constituting a polyhedron according to the first embodiment of the present invention.
FIG. 2 is a flowchart showing generation processing of polygon data constituting a polyhedron.
FIG. 3 is an explanatory diagram showing an example in the case where the directions of normal vectors match in the relationship between the order of vertices registered in a triangular polygon and the normal vectors;
FIG. 4 is an explanatory diagram showing a point sequence scattered in a coordinate space.
FIG. 5 is an explanatory diagram showing a configuration of a polyhedron surrounding a sequence of points scattered in a coordinate space.
FIG. 6 is a block diagram illustrating a configuration example of a three-dimensional rendering system.
FIG. 7 is a flowchart showing a data change process using a memory when generating polygon data constituting the polyhedron according to the second embodiment of the present invention;
FIG. 8 is a flowchart showing a data change process for performing drawing when generating polygon data constituting the polyhedron according to the second embodiment of the present invention;
FIG. 9 is an explanatory diagram showing an example in which the directions of normal vectors are different from each other in the relationship between the order of vertices registered in a triangular polygon and the normal vector.
[Explanation of symbols]
10 Polyhedron generator (3D rendering system)
11 Data generating means 12 Data changing means 13 Display means 14 File 15 Memory

Claims (23)

A polyhedron generation method used in a polyhedron generation device that generates a polyhedron using a triangular polygon,
And the normal vector of the triangle polygon, if the inner product between the vector from the internal point of the polyhedron to the triangles is negative, the changing step of Ru is changed normal vectors of the triangles in the polyhedron generating device A polyhedron generation method characterized by comprising: A polyhedron generation method used in a polyhedron generation device that generates a polyhedron using a triangular polygon,
Causing the polyhedron generating device to change the normal vector of the triangular polygon according to whether or not the inner product of the normal vector of the triangular polygon and the vector from the internal point of the polyhedron to the triangular polygon is negative A polyhedron generating method comprising a changing step. The polyhedron generating device polyhedron generating method according to claim 1 or 2, characterized in that a three-dimensional rendering system. The polyhedron generation method according to claim 1, wherein the internal point of the polyhedron is a center of gravity of the polyhedron. 5. The polyhedron generation method according to claim 1, wherein the normal vector of the triangular polygon is defined by a registration order of vertices of the triangular polygon. 6. The polyhedron generation method according to claim 1, further comprising a display step of displaying the polyhedron on a display unit of the polyhedron generation device. The polyhedron generating method according to claim 1, further comprising a triangular polygon generating step of generating the triangular polygon from a point sequence scattered in a coordinate space. A polyhedron generating device that generates a polyhedron using triangular polygons,
An apparatus for generating a polyhedron , wherein the normal vector of the triangular polygon is changed when the inner product of the normal vector of the triangular polygon and the vector from the internal point of the polyhedron to the triangular polygon is negative. A polyhedron generating device that generates a polyhedron using triangular polygons,
The normal vector of the triangular polygon is changed according to whether or not the inner product of the normal vector of the triangular polygon and the vector from the internal point of the polyhedron to the triangular polygon is negative. Polyhedron generator. The polyhedron generating device, polyhedron generating apparatus according to claim 8 or 9, characterized in that a three-dimensional rendering system. The polyhedron generating device according to any one of claims 8 to 10, wherein the internal point of the polyhedron is a center of gravity of the polyhedron. 12. The polyhedron generation device according to claim 8, wherein the normal vector of the triangular polygon is defined by the registration order of the vertices of the triangular polygon. The polyhedron generation device according to any one of claims 8 to 12, wherein the polyhedron is displayed on a display unit of the polyhedron generation device. The polyhedron generation device according to claim 8, wherein the triangular polygon is generated from a point sequence scattered in a coordinate space. Creating a polyhedron using triangular polygons;
A program for causing a computer to execute a step of changing the normal vector of the triangular polygon when the inner product of the normal vector of the triangular polygon and the vector from the internal point of the polyhedron to the triangular polygon is negative A recording medium characterized by recording. Creating a polyhedron using triangular polygons;
Changing the normal vector of the triangular polygon according to whether or not the inner product of the normal vector of the triangular polygon and the vector from the internal point of the polyhedron to the triangular polygon is negative. A recording medium on which a program to be executed is recorded. The recording medium according to claim 15 or 16, wherein the program is a program applicable to a three-dimensional rendering system. The recording medium according to claim 15, wherein the internal point of the polyhedron is a center of gravity of the polyhedron. The recording medium according to claim 15, wherein the normal vector of the triangular polygon is defined by a registration order of vertices of the triangular polygon. The recording medium according to claim 15, further comprising a display step of displaying the polyhedron on display means of the polyhedron generating apparatus. The recording medium according to any one of claims 15 to 20, further comprising a triangular polygon generation step of generating the triangular polygon from a point sequence scattered in a coordinate space. A color image processing apparatus using the polyhedron generation method according to claim 1. A color image processing apparatus comprising the polyhedron generation apparatus according to claim 8.

Images