KR20130101332A - Conversion system and method for 3d object represented by triangle mesh to 3d object represented by dosurface - Google Patents

Abstract

PURPOSE: A system and a method for converting a 3D object represented by triangle meshes into a 3D object represented by depth on surface (DoSurface) are provided to classify straight lines defining DoSurface representation and perform calculation after mapping the straight lines to a normal plane, thereby simplifying a process to acquire intersections between triangles and straight lines. CONSTITUTION: A system for converting a 3D object represented by triangle meshes into a 3D object represented by DoSurface comprises a normal plane definition unit (100) to define a normal plane; a direction vector classification unit (200) to classify straight lines defining DoSurface representation; a normal plane conversion unit (300) to generate a conversion formula in which a direction vector of the classified straight lines is equal to a normal vector of the normal plane; a coordinate system conversion unit (400) to perform conversion of the coordinate system of a 3D object represented by triangle meshes using the conversion formula; a candidate straight line selection unit (500) to select straight lines that passes inside of a triangles in a converted coordinate system; and a depth value calculation unit (600) to calculate a distance from a star point of a straight line to the triangle in the converted coordinate system. [Reference numerals] (100) Normal plane definition unit; (200) Direction vector classification unit; (300) Normal plane conversion unit; (400) Coordinate system conversion unit; (500) Candidate straight line selection unit; (600) Depth value calculation unit; (AA) Conversion formula; (BB) Conversion coordinate system; (CC) Candidate straight line; (DD) Depth information

Description

Transform system and method for 3D object represented by triangle mesh to 3D object represented by DoSurface}

The present invention relates to a system and method for converting a three-dimensional object into a DoSurface representation method, and more particularly, a system and method for rapidly converting a three-dimensional object represented by a triangle mesh to a DoSurface (Depth on Surface) representation method. It is about.

Most 3D objects are represented by a triangular mesh, and there are many kinds of data. However, since a triangular mesh has arbitrary coordinates and connectivity information, a large amount of computation is required for rendering or recording data.

In contrast, the DoSurface expression method is simple because it is expressed as a set of line segments. In addition, there is an advantage that data recording can be easily performed through a run length representation. To take advantage of these advantages, it would be useful to convert a 3D object represented by a triangular mesh into a DoSurface representation.

The DoSurface expression method is a method of expressing and recording depth information of a three-dimensional object onto a three-dimensional surface. In order to represent and record the depth information on the three-dimensional surface, the distance from the three-dimensional surface to the defined points and points of contact with the object must be calculated. In order to calculate the distance, we need to calculate the intersection of triangles and straight lines.

The process of finding the intersection point of the object and the straight lines represented by the triangle mesh consists of checking whether the straight line and the triangle meet and finding the position of the intersection point. The process of finding the equation of the plane with triangles and the intersection of the plane and the straight line is the first step, and the process of determining whether the intersection is inside the triangle is the second step. However, it is inefficient to perform these two steps for all triangles to find the intersection point of each straight line.

In order to solve the problem of finding the intersection of triangles and straight lines, a method of reducing the amount of calculation of the intersection of triangles and straight lines by mapping the three-dimensional triangles to the two-dimensional plane and pre-calculating necessary data has been proposed. . Since this process can be performed independently for each triangle, a fast calculation method using a parallel processing method has also been proposed.

On the other hand, with respect to the technique for obtaining the intersection with the triangle, a number of other publications other than Yet Faster Ray-Triangle Intersection (IEEE Transaction on Visualization and Computer Graphics) (hereinafter referred to as 'prior literature').

The above-mentioned prior document relates to a method for obtaining an intersection point of a triangle and a straight line, and performs the above-described steps 1 and 2 after mapping the triangle on the 3D to the 2D coordinate system.

However, these methods also require unnecessary computation that requires the intersection of all triangles for a straight line.

In other words, if you define a normal plane that can quickly select the straight lines that each triangle can meet, and project the triangles on the normal plane, the process of steps 1 and 2 can further reduce the amount of computation. In addition, in the process of finding the intersection point, it is possible to convert 3D data represented by a triangular mesh into DoSurface expression method quickly and efficiently by using a parallel processing method as in the previous method.

Document name: Yet Faster Ray-Triangle Intersection (Journal: IEEE Transaction on Visualization and Computer Graphics, pages 434-438, Issue Date: May-June 2010).

The present invention has been made in view of the above problems, and the present invention effectively selects candidates of straight lines that each triangle can meet by using the characteristics of the DoSurface expression method, and performs transformation into a coordinate system that can easily calculate the intersection point. It is an object of the present invention to provide a system and method for quickly finding a candidate straight line and an intersection point that can meet a triangle in a transformed coordinate system.

In addition, the present invention provides a system and method for converting three-dimensional data represented by a triangular mesh into a DoSurface expression method quickly and efficiently by enabling parallel processing of finding an intersection point with a straight line for each triangle. There is a purpose.

The present invention for achieving the technical problem relates to a system for converting a three-dimensional object represented by a triangular mesh to the DoSurface representation method, the normal plane definition unit for defining a normal plane; A direction vector classification unit classifying straight lines defining a DoSurface representation method; A normal plane transform unit for generating a transform equation for transforming the direction vectors of the classified straight lines to match the normal vector of the normal plane; A coordinate system transformation unit which performs coordinate system transformation on the three-dimensional object represented by the triangle mesh using the transformation equation; A candidate straight line selector which selects straight lines passing through the triangle in the transform coordinate system; And a depth value calculator for calculating a distance from a starting point of a straight line to a triangle in the transform coordinate system. .

The direction vector classification unit may classify the straight lines according to the direction of the direction vector of the straight lines.

The normal plane transform unit may convert the classified straight lines using homography.

In addition, the coordinate system conversion unit, by converting the coordinates of the three-dimensional point represented by the triangle mesh to the conversion equation generated through the normal plane conversion unit, characterized in that for generating the converted coordinates.

The candidate straight line selecting unit may project a triangle on a normal plane in the transformed coordinate system generated by the coordinate system transform unit, and select straight lines passing through the projected triangle.

The candidate straight line selecting unit may select a primary candidate straight line using the maximum / minimum value of the projected triangular coordinate values, and select a straight line passing through the inside of the actual triangle among the selected straight lines.

The depth calculator calculates a distance from the starting point of the straight line to the three-dimensional plane by substituting the starting point of the converted straight line into the plane equation of the converted triangle.

On the other hand, the present invention relates to a method for converting a three-dimensional object represented by a triangular mesh to the DoSurface representation method, the method comprising the steps of: (a) the normal plane definition unit defines a normal plane; (b) the direction vector classifier classifying the straight lines defining the DoSurface representation method; (c) generating a transform equation for transforming the direction vectors of the straight lines classified by the normal plane transform unit to match the normal vector of the normal plane; (d) performing a coordinate system transformation on the three-dimensional object represented by the triangular mesh by the coordinate system transformation unit by using the transformation formula; (e) the candidate straight line selector selecting the straight lines passing through the triangle in the transform coordinate system; And (f) a depth calculator calculating a distance from a start point of a straight line to a triangle in the transform coordinate system; .

According to the present invention as described above, it is possible to convert the three-dimensional object represented by the triangle mesh to the DoSurface expression method, and the intersection of the triangle and the straight line by classifying and calculating the straight lines defining the DoSurface expression method by mapping to a normal plane It can simplify the process of finding and since the process of finding each intersection is independent, there is an effect that parallel processing can be used.

1 is an overall configuration diagram conceptually showing a system for converting a three-dimensional object represented by a triangular mesh according to the present invention to the DoSurface representation method.
2 is an overall flowchart of a method for converting a three-dimensional object represented by a triangular mesh into a DoSurface representation method according to the present invention.

Specific features and advantages of the present invention will become more apparent from the following detailed description based on the accompanying drawings. It is to be noted that the detailed description of known functions and constructions related to the present invention is omitted when it is determined that the gist of the present invention may be unnecessarily blurred.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will now be described in detail with reference to the accompanying drawings.

A system for converting a 3D object represented by a triangular mesh according to the present invention to a DoSurface representation method will be described with reference to FIG. 1 as follows.

FIG. 1 is a schematic diagram schematically illustrating a system S for converting a three-dimensional object represented by a triangular mesh into a DoSurface representation method according to the present invention. As shown in FIG. 1, the normal plane defining unit 100 and a direction vector are illustrated. The classification unit 200, the normal plane transformation unit 300, the coordinate system transformation unit 400, the candidate straight line selection unit 500, and the depth value calculation unit 600 are included.

The normal plane definition unit 100 defines a normal plane.

In this case, the defined normal plane is a plane arbitrarily defined in order to easily and conveniently convert to DoSurface, that is, a process of finding an intersection between a triangle and a straight line.

)로 표현되며, 법선벡터는

과

의 외적으로 구한

가 된다. The planes are two direction vectors perpendicular to each other (

) And the normal vector is

and

Externally obtained

.

번째 직선과 정규평면이 만나는 점(

)은 다음의 [수식 1] 과 같이 두 개의 방향벡터의 선형조합으로 표현된다. 그리고 직선의 방향벡터는 정규평면의 법선벡터와 같은 방향을 가진다.During the straight line that defines how DoSurface is represented

Point where the fourth straight line meets the normal plane (

) Is expressed as a linear combination of two direction vectors as in Equation 1 below. The direction vector of the straight line has the same direction as the normal vector of the normal plane.

[Equation 1]

,

는 임의의 상수값을 가지게 된다.
here,

,

Will have any constant value.

The direction vector classifier 200 classifies the straight lines defining the DoSurface representation method according to the direction of the direction vector.

At this time, straight lines with the same direction vector are made into one group. The straight lines in the group perform the normal plane transform unit 300, the coordinate system transform unit 400, the candidate straight line selector 500, and the depth value calculator 600 to be performed next. In this case, the smaller the number of groups, the shorter the conversion time.

The normal plane transformation unit 300 generates a conversion equation for converting the direction vectors of the straight lines classified into one group to match the normal vector of the normal plane.

Specifically, the normal plane transformation unit 300 needs a rotation transformation process to make the direction vectors of the straight lines equal to the normal vector of the normal plane. In this case, the transformation may be performed by using 4 × 4 homography.

The coordinate system conversion unit 400 performs coordinate system transformation on the three-dimensional object represented by the triangular mesh using the above conversion formula.

In detail, the coordinate system conversion unit 400 generates coordinates converted by substituting coordinates of three-dimensional points represented by a triangle mesh into a conversion equation generated by the normal plane conversion unit 300.

의 방향벡터의 선형 조합으로 표현된다.
In this case, since the connectivity information of the triangle does not change, only the coordinate values need to be converted. The transformed coordinate system is used to define the normal plane.

It is expressed as a linear combination of the direction vectors of.

The candidate straight line selector 500 selects straight lines passing through the triangle in the transform coordinate system.

Specifically, the candidate straight line selector 500 projects a triangle on a normal plane and selects straight lines passing through the projected triangle in the transform coordinate system generated by the coordinate system transform unit 400.

의 방향벡터의 선형 조합으로 표현되어 있기 때문에, 정규 평면에 사영된 삼각형의 좌표는

의 계수가 된다.In this case, the coordinates of the triangle in the converted coordinate system

Since it is expressed as a linear combination of the direction vectors of, the coordinates of the triangle projected on the normal plane are

Becomes the coefficient of.

Then, a straight line that can be a candidate is primarily selected using the maximum / minimum value of the projected triangle coordinate values, and a straight line passing through the actual triangle is selected from among the straight lines.

The depth calculator 600 calculates a distance from the starting point of the straight line to the triangle in the transform coordinate system.

In detail, the depth calculator 600 may calculate the distance from the starting point of the straight line to the 3D plane by inserting the starting point of the converted straight line into the plane equation of the converted triangle.

In general, many operations are required to find the intersection of triangles and straight lines, but it can be confirmed that the calculated coordinate system can be calculated with very simple operation.

Hereinafter, a method of converting a 3D object represented by a triangular mesh using a system according to the present invention to a DoSurface representation method will be described with reference to FIG. 2.

2 is a flowchart illustrating a method of converting a 3D object represented by a triangular mesh into a DoSurface representation method according to the present invention. As shown, the normal plane defining unit 100 defines a normal plane (S10), The direction vector classification unit 200 classifies the straight lines defining the DoSurface representation method according to the direction of the direction vector (S20).

The normal plane transformation unit 300 generates a conversion equation for converting the direction vectors of the straight lines classified into one group to match the normal vector of the normal plane (S30). In this case, the normal plane transformation unit 300 performs transformation by using homography of 4x4 size.

Then, the coordinate system conversion unit 400 performs a coordinate system transformation on the three-dimensional object represented by the triangular mesh using the above transformation equation (S40). In this case, the coordinate system conversion unit 400 generates coordinates converted by substituting coordinates of three-dimensional points represented by a triangular mesh into a conversion equation generated by the normal plane conversion unit 300.

In addition, the candidate straight line selector 500 selects straight lines passing through the triangle in the transform coordinate system (S50). In this case, the candidate straight line selector 500 selects which straight line passes inside the projected triangle by projecting a triangle on a normal plane in the transformed coordinate system generated by the coordinate system transform unit 400. Therefore, a straight line that can be a candidate is primarily selected using the maximum / minimum value of the projected triangle coordinate values, and a straight line passing through the actual triangle inside is selected.

Subsequently, the depth calculator 600 calculates a distance from the starting point of the straight line to the triangle in the transform coordinate system (S60). In this case, the depth calculator 600 may calculate the distance from the starting point of the straight line to the 3D plane by substituting the starting point of the converted straight line into the plane equation of the converted triangle.

Meanwhile, the normal plane defining unit 100 and the direction vector classifying unit 200 perform a process only once for one object, and the normal plane transforming unit 300 and the coordinate system converting unit 400 are the direction vector classifying unit 200. ) Is the number of groups created in the The process through the candidate straight line selector 500 and the depth value calculator 600 is a method for all triangles. At this time, since each triangle can be performed independently, parallel processing is possible for these two parts.

While the present invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. It will be appreciated by those skilled in the art that numerous changes and modifications may be made without departing from the invention. Accordingly, all such appropriate modifications and changes, and equivalents thereof, should be regarded as within the scope of the present invention.

100: normal plane definition unit 200: direction vector classification unit
300: normal plane conversion unit 400: coordinate system conversion unit
500: candidate straight line selector 600: depth value calculator

Claims (14)

A normal plane definition unit 100 defining a normal plane;
A direction vector classification unit 200 for classifying straight lines defining a DoSurface representation method;
A normal plane transform unit 300 generating a transform equation for converting the direction vectors of the classified straight lines to match the normal vector of the normal plane;
A coordinate system transformation unit 400 for performing coordinate system transformation on the three-dimensional object represented by the triangle mesh using the transformation equation;
A candidate straight line selector 500 that selects straight lines passing through the triangle in the transform coordinate system; And
A depth value calculator 600 for calculating a distance from a start point of a straight line to a triangle in the transform coordinate system; A system for converting a three-dimensional object represented by a triangular mesh including a to a DoSurface representation method.
The method of claim 1,
The direction vector classification unit 200,
And converting a three-dimensional object represented by a triangular mesh into a DoSurface representation method according to the direction of the direction vector of the straight lines.
The method of claim 1,
The normal plane conversion unit 300,
A system for converting a three-dimensional object represented by a triangular mesh into a DoSurface representation method, characterized by converting the classified straight lines using homography.
The method of claim 1,
The coordinate system conversion unit 400,
DoSurface expression method for a three-dimensional object represented by a triangular mesh, characterized in that for generating the transformed coordinates by substituting the coordinates of the three-dimensional point represented by the triangle mesh to the conversion equation generated by the normal plane transformation unit 300 System to convert.
The method of claim 1,
The candidate straight line selector 500,
In the transformation coordinate system generated by the coordinate system transformation unit 400, a 3D object represented by a triangular mesh is characterized by projecting a triangle on a normal plane and selecting straight lines passing through the projected triangle by a DoSurface expression method. System to convert.
6. The method according to claim 1 or 5,
The candidate straight line selector 500,
DoSurface representation method for 3D objects represented by a triangle mesh characterized in that the primary candidate line is selected by using the maximum / minimum value of the projected triangle coordinate values, and the straight line passing through the inside of the selected triangle is selected. System to convert.
The method of claim 1,
The depth value calculator 600,
A system for converting a three-dimensional object represented by a triangular mesh into a DoSurface representation method by calculating the distance from the starting point of the straight line to the three-dimensional plane by substituting the starting point of the converted straight line into the planar equation of the converted triangle. .
(a) the normal plane definition unit 100 defining a normal plane;
(b) the direction vector classifying unit 200 classifying the straight lines defining the DoSurface representation method;
(c) generating, by the normal plane transformation unit 300, a transformation equation for converting the direction vectors of the classified straight lines to match the normal vector of the normal plane;
(d) the coordinate system transformation unit 400 performing coordinate system transformation on the three-dimensional object represented by the triangle mesh using the transformation formula;
(e) the candidate straight line selector 500 selecting the straight lines passing through the triangle in the transform coordinate system; And
(f) calculating, by the depth calculator 600, a distance from a starting point of a straight line to a triangle in the transform coordinate system; How to convert a three-dimensional object represented by a triangular mesh comprising a DoSurface representation.
The method of claim 8,
In the step (b)
And the direction vector classifier (200) classifies the straight lines according to the directions of the direction vectors of the straight lines.
The method of claim 8,
In the step (c)
The normal plane transformation unit 300 converts the classified straight lines using a homography (homography) method for converting a three-dimensional object represented by a triangle mesh to a DoSurface representation method.
The method of claim 8,
In the step (d)
The coordinate system conversion unit 400 generates a coordinate converted by substituting the coordinates of the three-dimensional points represented by the triangle mesh to the conversion equation generated through the step (c), to generate the converted coordinates How to convert an object to DoSurface representation.
The method of claim 8,
In the step (e)
The candidate straight line selector 500 projects a triangle on a normal plane and selects straight lines passing through the projected triangle in the transform coordinate system generated through the step (d). How to convert dimensional objects to DoSurface representation.
The method according to claim 8 or 12,
In the step (e)
The candidate straight line selector 500 selects a primary candidate straight line using the maximum / minimum value of the projected triangle coordinate values, and selects a straight line passing through the actual triangle from the selected straight lines. How to convert represented three-dimensional objects into DoSurface representation.
The method of claim 8,
In the step (f)
The depth calculator 600 calculates the distance from the starting point of the straight line to the three-dimensional plane by substituting the starting point of the converted straight line into the plane equation of the converted triangle. How to convert an object to DoSurface representation.

Images