Rendering method and device by point interpolation

The present invention relates to 3D graphics, and more particularly to a method and apparatus for rendering 3D graphic data into a 2D image.

The method of rendering a point model, which is a model composed of a combination of points and having a three-dimensional shape, is different from the polygon-based rendering method in which rendering is performed by appropriately combining a plurality of existing polygons. For each projected and generated point, you can use a point-based rendering method that renders by generating planar splats such as rectangles and circles.

When the hue is determined for the pixels and rendered by such a conventional splatting method, the image quality is good, but there is a problem that the processing speed of the three-dimensional graphic data is lowered. Also, if filtering is applied to improve image quality, the speed will be even slower. However, faster rendering is required while performing navigation tasks where the camera or viewpoint moves.

<p> A technical problem to be solved by the present invention is to interpolate between points to project 3D graphic data onto a 2D screen at a high speed, and to provide a rendering method and an apparatus using point interpolation. ..</p>

<p> The rendering method by point interpolation according to the present invention for achieving the above-mentioned problems includes a step of projecting a three-dimensional point on a two-dimensional screen and a step of projecting each of the projected points.<u style="single">size</u>And the calculated stage<u style="single">size</u>It is characterized by including a step of generating a vertical line segment having the same hue as the projected point corresponding to the same length as the above, and a step of interpolating between the generated vertical line segments.</p><p> In the interpolation step, it is desirable to interpolate between the points intersecting with the generated vertical line segment with respect to the horizontal line of the two-dimensional screen.</p><p> In the interpolation step, it is desirable to interpolate between the intersecting points so that the hue changes sequentially.</p><p> In the interpolation step, it is desirable to interpolate between the intersecting points based on the hue of the points provided on the left or right side of the intersecting points.</p><p> In the step of interpolating, among the intersecting points, from the point provided on the left side to a predetermined point is interpolated to the hue of the point provided on the left side, and from the predetermined point to the right side of the intersecting points. It is desirable to interpolate up to the point provided in the above to the hue of the point provided on the right side.</p><p> The calculation step corresponds to the length at which no empty space is generated at the interpolation step, and the projected points of the projected points.<u style="single">size</u>It is desirable to calculate.</p><p> The rendering method by point interpolation according to the present invention for achieving the above object is characterized by including a step of projecting a three-dimensional point on a two-dimensional screen and a step of interpolating between the projected points.</p><p> In the interpolation step, it is desirable to interpolate between the projected points provided on the same horizontal line of the two-dimensional screen.</p><p> In the interpolation step, it is desirable to interpolate between the projected points so that the hue changes sequentially.</p><p> In the interpolation step, it is desirable to interpolate between the projected points based on the hue of the points provided on the left or right side of the projected points.</p><p> In the step of interpolating, among the projected points, from the point provided on the left side to a predetermined point is interpolated into the hue of the point provided on the left side, and the projected point from the predetermined point is interpolated. It is desirable to interpolate up to the point provided on the right side to the hue of the point provided on the right side.</p><p> It is desirable that the recording medium be readable by a computer in which a program for executing the above invention on a computer is recorded.</p><p> The rendering device by point interpolation according to the present invention for achieving the above object has a projection unit that projects a three-dimensional point on a two-dimensional screen and a projection unit that projects each of the projected points.<u style="single">size</u>To calculate<u style="single">size</u>The calculation unit and the calculated<u style="single">size</u>Produces a vertical line segment of the same hue as the projected point, which corresponds to the same length as<u style="single">size</u>It is characterized by including a generation unit and an interpolation unit that interpolates between the generated vertical line segments.</p><p> It is desirable that the interpolation unit interpolates between the points intersecting with the generated vertical line segment with respect to the horizontal line of the two-dimensional screen.</p><p> It is desirable that the interpolation unit interpolates between the intersecting points so that the hue changes sequentially.</p><p> It is desirable that the interpolation unit interpolates between the intersecting points based on the hue of the point provided on the left side or the point provided on the right side among the intersecting points.</p><p> The interpolation unit interpolates from the point provided on the left side to a predetermined point among the intersecting points into the hue of the point provided on the left side, and from the predetermined point to the right side of the intersecting points. It is desirable to interpolate up to the provided points into the hue of the points provided on the right side.</p><p> Said<u style="single">size</u>The calculation unit corresponds to the length at which no empty space is generated as a result of interpolation by the interpolation unit, and the projected points of each of the projected points.<u style="single">size</u>It is desirable to calculate.</p><p> The rendering device by point interpolation according to the present invention for achieving the above object is characterized by including a projection unit that projects a three-dimensional point on a two-dimensional screen and an interpolation unit that interpolates between the projected points. To do.</p><p> It is desirable that the interpolation unit interpolates between the projected points provided on the same horizontal line of the two-dimensional screen.</p><p> It is desirable that the interpolation unit interpolates between the projected points so that the hue changes sequentially.</p><p> It is desirable that the interpolation unit interpolates between the projected points based on the hue of the point provided on the left side or the point provided on the right side of the projected points.</p><p> The interpolation unit interpolates from the point provided on the left side to a predetermined point among the projected points into the hue of the point provided on the left side, and among the projected points from the predetermined point. It is desirable to interpolate up to the point provided on the right side into the hue of the point provided on the right side.</p>

<p> According to the rendering method and apparatus by point interpolation according to the present invention, it is possible to interpolate between points and render 3D graphic data into a 2D image at a high speed.</p>

Hereinafter, the rendering method and apparatus by point interpolation according to the present invention will be described in detail with reference to the attached drawings.

FIG. 1 is a flowchart showing an embodiment of a rendering method by point interpolation according to the present invention.

First, the 3D point model shown in Fig. 6A is input and converted into a predetermined data format (stage 100). Here, the three-dimensional point model is composed of a combination of points. Hereinafter, the points forming the point model will be referred to as image points. Such an image point has 3D data so that the point model has a 3D shape.

The data format of the image point can be embodied in various ways. Examples of such image points include the Simple Texture (ST: Simple Texture) format and the Point Cloud (PC: Point Cloud) format. The simple texture format means a format that expresses image point data as hue information and depth information. Here, the depth information refers to the distance information from the viewpoint to the image point. The point cloud format means a format that expresses image point data as hue information and geometric information. Here, the hue information is information related to the hue information of the image point, and the geometric information means information related to the position of the image point.

After the 100th stage, select the corresponding LOD from the LODs (Level Of Detail) already provided (110th stage). That is, in the 110th step, the effective resolution of the image point is selected from a plurality of resolutions. In the 110th stage, the resolution of the image point can be selected according to the depth of the image point. Here, the depth of the image point means the distance from the viewpoint to the image point. For example, in the 110th stage, LOD1 to 4 are provided, the resolution is set to LOD1&gt; LOD2&gt; LOD3&gt; LOD4, and LOD is selected from LOD1 to 4 according to the depth of each image point.

After the 110th step, the depth of the image point is calculated for each image point forming the 3D point (120th step).

After the 120th step, the points are interpolated (130th step). The signal output in the 130th stage is input to a display device such as a liquid crystal panel and displayed as shown in FIG. 6B.

FIG. 2A is a flowchart showing an embodiment of the rendering method by point interpolation according to the present invention for the 130th step.

First, the 3D point is projected on the 2D screen (200th stage). 9A and 10A are graphs showing an example in which a 3D point is projected on a 2D screen in the 200th stage.

In the 200th stage, of each projected 2D point<u style="single">size</u>Is calculated (step 210). 2D points calculated in the 210th stage<u style="single">size</u>Corresponds to the length at which no empty space is generated for the result interpolated in the 230th stage.<u style="single">size</u>Is.

Calculated in stage 210<u style="single">size</u>Generates a vertical line segment that is the same length as and has the same hue as the 2D point (stage 220). Here, the vertical line segment means a line segment that is perpendicular to the two-dimensional screen. It is desirable that the position of the vertical line segment generated in the 220th step is set with reference to the center of the vertical line segment of the two-dimensional point.

For example, referring to FIG. 7A, in the 200th step, 2D points are projected on the 2D screen at (3,2), (2,5), (4,8) and (3,11). .. In the 220th stage, a vertical line segment composed of (2,2), (3,2) and (4,2) is generated for (3,2) points, and for (2,5) points. A vertical line segment composed of (1,5), (2,5) and (3,5) is generated, and (3,8), (4,8) and (4,8) and (4,8) and (4,8) points are generated. A vertical line segment composed of (5,8) is generated, and a vertical line segment composed of (2,11), (3,11) and (4,11) is generated for the (3,11) point. Generated. 9B and 10B are graphs showing the results of performing the 220th step with respect to the graphs shown in FIGS. 9A and 10A, which are the results of performing the 200th step.

Interpolate between the vertical line segments generated in step 220 to a given hue, as shown in Figure 7B (step 230). In the 230th step, the horizontal line of the 2D screen is interpolated between the vertical line segment generated in the 220th step and the intersecting point. For example, referring to the three horizontal lines shown in Figure 7A, interpolate between (3,2) and (3,5) and interpolate between (3,5) and (3,8). Interpolates between (3,8) and (3,11). 9C and 10C are graphs showing the results of performing the 230th step with respect to the graphs shown in FIGS. 9B and 10B, which are the results of performing the 220th step.

The method of interpolating between points in the 230th step is as follows.

First, the hues between the points are interpolated so that the hues between the points change from the hues of the points provided on the left side to the hues of the points provided on the right side in order. For example, when the point provided on the left side is red and the point provided on the right side is blue, the points between the two points are interpolated so as to gradually change from red to blue with the left side as a reference.

Second, the left side interpolates to the hue of the point provided on the left side, and the right side interpolates to the hue of the point provided on the right side, with reference to a predetermined point between the points. Here, a predetermined point between points means a point set by a predetermined ratio provided between both points. For example, if the default ratio is 50:50, the point from the point on the left to the midpoint is interpolated to the hue of the point on the left, and the point from the midpoint to the point on the right is on the right. Interpolates to the hue of the points provided in.

Third, the points are interpolated based on the hue of the points provided on the left or right side. For example, when interpolating based on the hue of the points provided on the left side, if the hue of the points provided on the left side is yellow, all the points are interpolated in yellow.

It is desirable to remove the splats that are included in each object and become visible through filtering such as SAF (Splat Adaptive Filtering) for the results interpolated in the 230th step. 9D and 10D are graphs showing the results of SAF with respect to the graphs shown in FIGS. 9C and 10C, which are the results of performing the 230th step.

FIG. 2B is a flowchart showing another embodiment of the rendering method by point interpolation according to the present invention for the 130th step.

First, as shown in FIGS. 9A and 10A, a 3D point is projected onto a 2D screen (stage 200).

Interpolate between the 2D points projected in the 200th stage (240th stage). The points to be interpolated in the 240th stage are points provided on the same horizontal line of the 2D screen. For example, referring to FIG. 8A, the two-dimensional points projected in the three rows of the horizontal line are (3,2) and (3,11). In the 240th step, the hues from (3,3) to (3,10) are interpolated. The method of interpolating between points in the 240th step is the same as that in the 230th step.

FIG. 3 is a flowchart showing an embodiment of the order of interpolation in the 130th step of the rendering method by point interpolation according to the present invention.

First, initialize the values in row i of the horizontal line and column j of the vertical line (stage 300). In the 300th step, set the i and j values to 1 respectively.

After the 300th step, it is determined whether or not the pixel provided in (i, j) has a z value (step 305). If it is determined to have a z-value in step 305, this is the pixel in which the pixel corresponds to the 2D point on which the 3D point was projected in step 200, or the vertical line generated in step 220. It means that it corresponds to the pixel corresponding to the minute.

If it is determined in step 305 that the pixel provided at (i, j) has a z value, the (i, j) coordinate value is saved as the first coordinate (step 310).

After the 310th step, add 1 to the j value (step 315) and compare the magnitudes of the j value and the critical value J (step 320). The critical value J in the 320th stage is the number of pixels of the vertical line on the two-dimensional screen.

If it is determined in the 320th step that the j value is larger than the critical value J, 1 is added to the i value and the j value is set to 1 (step 325).

After the 325th step, the magnitudes of the i value and the critical value I are compared (step 330). The critical value I in the 330th stage is the number of pixels of the horizontal line on the two-dimensional screen.

If it is determined in the 320th step that the j value is smaller than the critical value J, it is determined whether or not the pixel provided in (i, j) has the z value (step 335).

If it is determined that the j value is greater than the critical value J in the 320th stage and the i value is less than or equal to the critical value I in the 330th stage, the process proceeds to the 335th stage and is provided in (i, j). Determine if the pixel given has a z-value.

If it is determined in the 335th step that the pixel provided in (i, j) does not have the z value, 1 is added to the j value in the 315th step.

If it is determined in step 335 that the pixel provided at (i, j) has a z value, the (i, j) coordinate value is saved as the second coordinate (step 340).

After the 340th step, the hue between the 1st coordinate saved in the 310th step and the 2nd coordinate saved in the 340th step is interpolated in the same manner as in the 230th step (step 345).

After the 345th step, if it is determined in the 305th step whether or not the pixel located at the 2nd coordinate saved in the 340th step has a z value, the pixel located at the 2nd coordinate has a z value. Therefore, it is saved as the first coordinate in the 310th step, and the 315th step is performed.

If it is determined in step 305 that the pixel provided in (i, j) does not have a z value, 1 is added to the j value (step 350), and the j value and critical value J are added. Compare the sizes of (stage 355).

If it is determined in the 355th step that the j value is equal to or less than the critical value J, it is determined in the 305th step whether or not the pixel provided at (i, j) has the z value.

If the j value is judged to be larger than the critical value J in the 355th step, 1 is added to the i value and the j value is set to 1 (360th step).

If it is determined in the 365th step that the i value is equal to or less than the critical value I, it is determined in the 305th step whether or not the pixel provided in (i, j) has the z value.

FIG. 4 is a block diagram showing an embodiment of a rendering device by point interpolation according to the present invention. The rendering device by point interpolation includes a data input unit 400, an LOD selection unit 410, a depth calculation unit 420, and a point. It is configured to include an interpolation processing unit 430.

The data input unit 400 inputs the three-dimensional point model shown in FIG. 6A via the input terminal IN. Here, the three-dimensional point model consists of a combination of points. Hereinafter, the points forming the point model will be referred to as image points. Such image points have 3D data so that the point model has a 3D shape.

The image point data format can be embodied in various ways. Examples of such image points include a simple texture format and a point cloud format. The simple texture format means a format that expresses image point data as hue information and depth information. Here, the depth information refers to information regarding the distance from the viewpoint to the image point. The point cloud format means a format that expresses image point data as hue information and geometric information. Here, the hue information is information related to the hue information of the image point, and the geometric information means information related to the position of the image point.

The LOD selection unit 410 selects the corresponding LOD from the LODs provided in advance. That is, the LOD selection unit 410 selects the effective resolution of the image point from the plurality of resolutions. In the LOD selection unit 410, the resolution of the image point can be selected according to the depth of the image point. Here, the depth of the image point means the distance from the viewpoint to the image point. For example, the LOD selection unit 410 provides LOD1 to 4, sets the resolution to LOD1&gt; LOD2&gt; LOD3&gt; LOD4, and selects LOD from LOD1 to 4 according to the depth of each image point.

The depth calculation unit 420 calculates the depth of the image point for each image point forming the three-dimensional point.

The point interpolation processing unit 430 performs interpolation processing between points and outputs the processed result via the output terminal OUT. The signal output by the point interpolation processing unit 430 is input to a display device such as a liquid crystal panel and displayed as shown in FIG. 6B.

FIG. 5 is a block diagram showing an embodiment of the point interpolation processing unit 430 of the rendering apparatus based on the point interpolation according to the present invention. The point interpolation processing unit 430 includes the projection unit 431,<u style="single">size</u>Calculation unit 432, vertical<u style="single">size</u>It is configured to include a generation unit 433 and an interpolation unit 434.

The projection unit 431 projects a three-dimensional point onto a two-dimensional screen. 9A and 10A are graphs showing an example in which a three-dimensional point is projected on a two-dimensional screen by the projection unit 431.

<u style="single">size</u>The calculation unit 432 is a unit of each 2D point projected on the 2D screen by the projection unit 431.<u style="single">size</u>To calculate.<u style="single">size</u>Two-dimensional points calculated by calculation unit 432<u style="single">size</u>Corresponds to the length at which no empty space is generated with respect to the result interpolated by the interpolation unit 434.<u style="single">size</u>Is.

vertical<u style="single">size</u>Generation unit 433<u style="single">size</u>Calculated by calculation unit 432<u style="single">size</u>Generates a vertical line segment with the same hue as the 2D point at the same length as. Here, the vertical line segment means a line segment that is perpendicular to the two-dimensional screen. vertical<u style="single">size</u>It is desirable that the position of the vertical line segment generated by the generation unit 433 is set with reference to the center of the vertical line segment of the two-dimensional point.

For example, referring to FIG. 7A, the projection unit 431 projects 2D points on the 2D image at (3,2), (2,5), (4,8) and (3,11). There is. vertical<u style="single">size</u>In the generator 433, a vertical line segment composed of (2,2), (3,2) and (4,2) is generated for the (3,2) point, and for the (2,5) point. A vertical line segment composed of (1,5), (2,5) and (3,5) is generated, and (3,8), (4,8) and (4,8) and (4,8) and (4,8) points are generated. A vertical line segment composed of (5,8) is generated, and a vertical line segment composed of (2,11), (3,11) and (4,11) is generated for (3,11). Will be done. 9B and 10B are perpendicular to the graphs shown in FIGS. 9A and 10A, which are the results of processing by the projection unit 431.<u style="single">size</u>It is a graph which shows the result of processing by the generation part 433.

The interpolation unit 434 is vertical as shown in FIG. 7A.<u style="single">size</u>Interpolates between the vertical line segments generated by the generation unit 433 to a predetermined hue. Here, the interpolation unit 434 is perpendicular to the horizontal line of the two-dimensional screen.<u style="single">size</u>Interpolate between the points that intersect the vertical line segment generated by the diameter generator 433. For example, referring to the three horizontal lines shown in Figure 7A, interpolate between (3,2) and (3,5) and interpolate between (3,5) and (3,8). Then interpolate between (3,8) and (3,11). 9C and 10C are vertical<u style="single">size</u>It is a graph which shows the result of processing with the interpolation part 434 with respect to the graph shown in FIG. 9B and FIG. 10B which are the result of processing by the generation part 433.

The method of interpolating between points by the interpolation unit 434 is as follows.

First, the hues between the points are interpolated so that the hues between the points change from the hues of the points provided on the left side to the hues of the points provided on the right side in order. For example, when the point provided on the left side is red and the point provided on the right side is blue, the points between the two points are interpolated so as to gradually change from red to blue with the left side as a reference.

Second, the left side interpolates to the hue of the point provided on the left side, and the right side interpolates to the hue of the point provided on the right side, with reference to a predetermined point between the points. Here, a predetermined point between points means a point set by a predetermined ratio provided between both points. For example, if the default ratio is 50:50, the point from the point on the left to the midpoint is interpolated to the hue of the point on the left, and the point from the midpoint to the point on the right is on the right. Interpolates to the hue of the points provided in.

Third, the points are interpolated based on the hue of the points provided on the left or right side. For example, when interpolating based on the hue of the points provided on the left side, if the hue of the points provided on the left side is yellow, all the points are interpolated in yellow.

It is desirable to remove the splats that are included in each object and become visible through filtering such as SAF for the result of interpolation processing by the interpolation unit 434. 9D and 10D are graphs showing the results of SAF on the graphs shown in FIGS. 9C and 10C, which are the results of processing by the interpolation unit 434.

Vertical as in one embodiment shown in FIG.<u style="single">size</u>It does not include the generator 433 and can be implemented as follows.

Vertically between the 2D points generated by projecting the 3D points onto the 2D screen as shown in FIGS. 9A and 10A by the projection unit 431.<u style="single">size</u>Vertical at generator 433<u style="single">size</u>Is not generated, and the interpolation unit 434 interpolates between the points. Here, the points to be interpolated refer to points provided on the same horizontal line on the two-dimensional screen. For example, referring to FIG. 8A, the two-dimensional points projected in the three rows of the horizontal line are (3,2) and (3,11). The interpolation unit 434 interpolates the hues from (3,3) to (3,10). The method of interpolating between points by the interpolation unit 434 is performed by the method described above.

In the present invention, as shown in FIG. 11, the image quality of the two-dimensional image is deteriorated, but the processing speed of the three-dimensional graphic data can be increased. Therefore, it can be effectively used when a processing speed faster than the image quality is required such as navigation work.

The present invention can be embodied as a computer-readable code on a computer-readable recording medium (including all devices having an information processing function). Computer-readable recording media include all types of recording devices in which data read by computer systems is stored. Examples of computer-readable recording media include ROMs, RAMs, CD-ROMs, magnetic tapes, floppy (registered trademark) disks, and optical data storage devices.

In order to aid in such understanding of the present invention, the embodiments shown in the drawings have been described with reference to them, but this is merely an example, and those skilled in the art will appreciate various modifications and equal other practices. You can see that the form is possible. Therefore, the true technical scope of the invention must be determined by the claims.

INDUSTRIAL APPLICABILITY The present invention is suitably used in a technical field related to graphics of a three-dimensional image.

<figref num="1">It is a flowchart which shows one Embodiment of the rendering method by the point interpolation by the present invention.</figref><figref num="2A">It is a flowchart which shows one Embodiment with respect to the 130th step of the rendering method by the point interpolation by the present invention.</figref><figref num="2B">It is a flowchart which shows the other embodiment with respect to the 130th step of the rendering method by the point interpolation by this invention.</figref><figref num="3">It is a flowchart which shows one Embodiment of the order of interpolation in the 230th step of the rendering method by the point interpolation by this invention.</figref><figref num="4">It is a block diagram which shows one Embodiment of the rendering apparatus by the point interpolation by the present invention.</figref><figref num="5">It is a block diagram which shows one Embodiment of the point interpolation processing part of the rendering apparatus by the point interpolation by this invention.</figref><figref num="6A">It is a graph explaining one embodiment of the rendering method and apparatus by the point interpolation by the present invention.</figref><figref num="6B">It is a graph explaining one embodiment of the rendering method and apparatus by the point interpolation by the present invention.</figref><figref num="7A">It is a graph explaining one embodiment of the rendering method and apparatus by the point interpolation by the present invention.</figref><figref num="7B">It is a graph explaining one embodiment of the rendering method and apparatus by the point interpolation by the present invention.</figref><figref num="8A">It is a graph explaining one embodiment of the rendering method and apparatus by the point interpolation by the present invention.</figref><figref num="8B">It is a graph explaining one embodiment of the rendering method and apparatus by the point interpolation by the present invention.</figref><figref num="9A">It is a graph which shows an example which the 3D point was projected on the 2D screen in the 200th stage.</figref><figref num="9B">It is a graph which shows the result of performing the 220th step with respect to the graph shown in FIG. 9A which is the result of performing the 200th step.</figref><figref num="9C">It is a graph which shows the result of performing the 230th step with respect to the graph shown in FIG. 9B which is the result of performing the 220th step.</figref><figref num="9D">It is a graph which shows the result of having performed SAF with respect to the graph shown in FIG. 9C which is the result of having performed the 230th step.</figref><figref num="10A">It is a graph which shows an example which the 3D point was projected on the 2D screen in the 200th stage.</figref><figref num="10B">It is a graph which shows the result of performing the 220th step with respect to the graph shown in FIG. 10A which is the result of performing the 200th step.</figref><figref num="10C">It is a graph which shows the result of performing the 230th step with respect to the graph shown in FIG. 10B which is the result of performing the 220th step.</figref><figref num="10D">It is a graph which shows the result of having performed SAF with respect to the graph shown in FIG. 10C which is the result of having performed the 230th step.</figref><figref num="11">It is a graph explaining the effect of the rendering method and the apparatus by the point interpolation by the present invention.</figref>

400 data entry section 410 LOD selection 420 Depth calculation unit 430 Point interpolation processing unit 431 Projection section 432 <u style="single">size</u>Calculation department 433 vertical<u style="single">size</u>Generator 434 Interpolator