Apparatus and method for forming 2D views of a structure from 3D point data

Abstract

An apparatus and method are described for forming 2D views of a structure from 3D point data. In the present invention, a plane is specified and triangulated meshes are intersected with the plane to form a group of polylines. The significant features of each polyline are then extracted, and the features are then connected to form intersection polylines that closely approximate the intersection polylines that would be generated by intersecting the real 3D structure with the specified plane. The final 2D view consists of the connected features extracted from the polylines.

What is claimed is:  
     
       1. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       means for identifying a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points;  
       means for forming a sequence of features from each group of polyline points, wherein a feature is a geometric shape selected from a group of geometric shapes, wherein the group of geometric shapes includes line segments and arcs, and wherein operation of the means for forming reduces a measurement noise; and  
       means for joining consecutive features in each group of polyline points to form a 2D view.  
     
     
       2. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       means for identifying a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points;  
       means for forming a sequence of features from each group of polyline points;  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for identifying a number of intersection polylines includes:  
       means for forming a mesh representation from a 3D scan cloud, the mesh representation having a plurality of mesh lines that form a plurality of triangles;  
       means for identifying false triangles in the plurality of triangles, and removing any identified false triangles to form a number of meshes;  
       means for inserting a first plane into the number of meshes to identify the intersection polylines.  
     
     
       3. The apparatus of  claim 2  and further comprising means for inserting additional planes into the number of meshes to identify the intersection polylines. 
     
     
       4. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       means for identifying a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points;  
       means for forming a sequence of features from each group of polyline points;  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for identifying a number of intersection polylines includes:  
       means for forming a mesh representation from a 3D scan cloud, the mesh representation having a plurality of mesh lines that form a plurality of triangles;  
       means for inserting a plane into the mesh representation to define a continuous polyline that has a number of intersection points such that each place where a mesh line intersects the plane defines an intersection point, each pair of adjacent intersection points having a spacing; and  
       means for breaking the continuous polyline into the number of intersection polylines by breaking the continuous polyline each time the spacing between adjacent intersection points exceeds a predefined value.  
     
     
       5. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       means for identifying a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points;  
       means for forming a sequence of features from each group of polyline points;  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for identifying a number of intersection polylines includes:  
       means for forming a mesh representation from a 3D scan cloud, the mesh representation having a plurality of mesh lines that form a plurality of triangles;  
       means for inserting a plane into the mesh representation;  
       means for identifying scan points within a specified distance of the plane as identified points; and  
       means for connecting the identified points to form the number of intersection polylines.  
     
     
       6. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       means for identifying a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points;  
       means for forming a sequence of features from each group of polyline points; and  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for forming includes:  
       means for examining each group of polyline points in a first order to form a sequence of examined groups of polyline points;  
       for an examined group of polyline points, means for placing the polyline points from the examined group of polyline points into a sequence of point sets; and  
       means for forming the sequence of features from the sequence of point sets by forming a feature from the polyline points in each point set.  
     
     
       7. The apparatus of  claim 6  wherein the means for placing includes: 
       means for forming a point set of the sequence of point sets by identifying a seed point and a number of remaining points in an examined group of polyline points, the seed point defining a first member of the point set;  
       means for examining the remaining points in a second order to form a sequence of examined points; and  
       for an examined point, means for fitting a line to the examined point and each member in the point set, adding the examined point to the point set when the line satisfies a fit criteria, and leaving the examined point and any remaining points that are separated from the seed point by the examined point in the examined group of polyline points when the line fails to satisfy the fit criteria.  
     
     
       8. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       means for identifying a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points;  
       means for forming a sequence of features from each group of polyline points;  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for joining consecutive features includes:  
       means for merging two adjacent features to form a single feature, each adjacent feature having an inner endpoint and an outer endpoint, the inner endpoints of the two adjacent features lying closest together, the outer endpoints of the two adjacent features lying furthest apart;  
       means for testing the single feature to determine if the single feature satisfies a fit criteria; and  
       means for returning the single feature to two de-merged adjacent features when the fit criteria fails.  
     
     
       9. The apparatus of  claim 8  and further including: 
       means for identifying the outer endpoints of the two de-merged adjacent features;  
       means for identifying an intersection point between the two de-merged adjacent features; and  
       means for extending each de-merged feature to include the intersection point when the intersection point lies between the outer endpoints.  
     
     
       10. The apparatus of  claim 9  and further comprising means for forming a segment connected to the inner endpoints of the adjacent features when the intersection point lies outside of the outer endpoints. 
     
     
       11. An apparatus for forming 2D views of a 3D structure from a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points, the apparatus comprising: 
       means for forming a sequence of features from each group of polyline points, wherein a feature is a geometric shape selected from a group of geometric shapes, wherein the group of geometric shapes includes line segments and arcs, and wherein operation of the means for forming reduces a measurement noise; and  
       means for joining consecutive features in each group of polyline points to form a 2D view.  
     
     
       12. An apparatus for forming 2D views of a 3D structure from a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points, the apparatus comprising: 
       means for forming a sequence of features from each group of polyline points; and  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for forming includes:  
       means for examining each group of polyline points in a first order to form a sequence of examined groups of polyline points;  
       for an examined group of polyline points, means for placing the polyline points from the examined group of polyline points into a sequence of point sets; and  
       means for forming the sequence of features from the sequence of point sets by forming a feature from the polyline points in each point set.  
     
     
       13. The apparatus of  claim 12  wherein the means for placing includes: 
       means for forming a point set of the sequence of point sets by identifying a seed point and a number of remaining points in an examined group of polyline points, the seed point defining a first member of the point set;  
       means for examining the remaining points in a second order to form a sequence of examined points; and  
       for an examined point, means for fitting a line to the examined point and each member in the point set, adding the examined point to the point set when the line satisfies a fit criteria, and leaving the examined point and any remaining points that are separated from the seed point by the examined point in the examined group of polyline points when the line fails to satisfy the fit criteria.  
     
     
       14. An apparatus for forming 2D views of a 3D structure from a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points, the apparatus comprising: 
       means for forming a sequence of features from each group of polyline points;  
       means for joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the means for joining consecutive features includes:  
       means for merging two adjacent features to form a single feature, each adjacent feature having an inner endpoint and an outer endpoint, the inner endpoints of the two adjacent features lying closest together, the outer endpoints of the two adjacent features lying furthest apart;  
       means for testing the single feature to determine if the single feature satisfies a fit criteria; and  
       means for returning the single feature to two de-merged adjacent features when the fit criteria fails.  
     
     
       15. The apparatus of  claim 14  and further including: 
       means for identifying the outer endpoints of the two de-merged adjacent features;  
       means for identifying an intersection point between the two de-merged adjacent features; and  
       means for extending each de-merged feature to include the intersection point when the intersection point lies between the outer endpoints.  
     
     
       16. The apparatus of  claim 15  and further comprising means for forming a segment connected to the inner endpoints of the adjacent features when the intersection point lies outside of the outer endpoints. 
     
     
       17. A method for forming 2D views of a 3D structure from a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points, the method comprising the steps of: 
       forming a sequence of features from each group of polyline points, wherein a feature is a geometric shape selected from a group of geometric shapes, wherein the group of geometric shapes includes line segments and arcs, and wherein operation of the means for forming reduces a measurement noise; and  
       joining consecutive features in each group of polyline points to form a 2D view.  
     
     
       18. A method for forming 2D views of a 3D structure from a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points, the method comprising the steps of: 
       forming a sequence of features from each group of polyline points;  
       joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the step of forming includes:  
       examining each group of polyline points in a first order to form a sequence of examined groups of polyline points;  
       for an examined group of polyline points, placing the polyline points from the examined group of polyline points into a sequence of point sets; and  
       forming the sequence of features from the sequence of point sets by forming a feature from the polyline points in each point set.  
     
     
       19. The method of  claim 18  wherein the step of placing includes: 
       forming a point set of the sequence of point sets by identifying a seed point and a number of remaining points in an examined group of polyline points, the seed point defining a first member of the point set;  
       examining the remaining points in a second order to form a sequence of examined points; and  
       for an examined point, fitting a line to the examined point and each member in the point set, adding the examined point to the point set when the line satisfies a fit criteria, and leaving the examined point and any remaining points that are separated from the seed point by the examined point in the examined group of polyline points when the line fails to satisfy the fit criteria.  
     
     
       20. A method for forming 2D views of a 3D structure from a number of intersection polylines, the intersection polylines having groups of polyline points such that each intersection polyline has a group of polyline points, the method comprising the steps of: 
       forming a sequence of features from each group of polyline points;  
       joining consecutive features in each group of polyline points to form a 2D view; and  
       wherein the step of joining consecutive features includes:  
       merging two adjacent features to form a single feature, each adjacent feature having an inner endpoint and an outer endpoint, the inner endpoints of the two adjacent features lying closest together, the outer endpoints of the two adjacent features lying furthest apart;  
       testing the single feature to determine if the single feature satisfies a fit criteria; and  
       returning the single feature to two de-merged adjacent features when the fit criteria fails.  
     
     
       21. The method of  claim 20  and further including: 
       identifying the outer endpoints of the two de-merged adjacent features;  
       identifying an intersection point between the two de-merged adjacent features; and  
       extending each de-merged feature to include the intersection point when the intersection point lies between the outer endpoints.  
     
     
       22. The method of  claim 21  and further comprising the step of forming a segment connected to the inner endpoints of the adjacent features when the intersection point lies outside of the outer endpoints. 
     
     
       23. The method of  claim 22  and further comprising the step of forming a segment connected to the inner endpoints of the adjacent features when the intersection point lies outside of the outer endpoints. 
     
     
       24. An apparatus for forming 2D views of a 3D structure, the apparatus comprising: 
       a memory device which stores 3D point data that corresponds to a structure;  
       a processor, coupled to the memory device, and operative to analyze 3D point data, wherein the processor is operative to identify plane of interest, and wherein the processor is further operative to generate a 2D view of the 3D structure based on a group of intersection polylines, where the group of intersection polylines corresponds to intersections between the plane of interest and the 3D point data that corresponds to the structure, and wherein the processor is operative to form a sequence of features based on the group of intersection polylines, wherein the processor is operative to remove measurement noise from the group intersection polylines.  
     
     
       25. The apparatus of  claim 24  further comprising a user interface device coupled with the processor, wherein the identified plane of interest is determined by the processor based on user input through the user interface device.