Method for generating a mesh representation of a region characterized by a trunk and a branch thereon
View Patent ↗The present invention provides a meshing method, called grafting, that lifts the prior art constraint on abutting surfaces, including surfaces that are linking, source/target, or other types of surfaces of the trunk volume. The grafting method locally modifies the structured mesh of the linking surfaces allowing the mesh to conform to additional surface features. Thus, the grafting method can provide a transition between multiple sweep directions extending sweeping algorithms to 2¾-D solids. The method is also suitable for use with non-sweepable volumes; the method provides a transition between meshes generated by methods other than sweeping as well.
1. A method, practiced on a computer, of generating a mesh representation of a region characterized by a trunk and a branch thereon, comprising:
a) Determining a first trunk mesh;
b) Determining a second trunk mesh by adjusting the portion of the first mesh proximal the boundary surface between the trunk and the branch to substantially conform thereto;
c) Determining a branch mesh from the portion of the second mesh within said boundary surface and the geometry of the branch; and
d) Displaying the mesh representation on a computer screen.
2. The method of claim 1 , wherein the trunk comprises a 2½-dimensional region, and wherein determining a first trunk mesh comprises sweeping the volume of the trunk.
3. The method of claim 1 , wherein the branch comprises a 2½-dimensional region, and wherein determining a branch mesh comprises sweeping the volume of the branch.
4. The method of claim 1 , wherein determining a second trunk mesh comprises:
a) Determining the boundary of said boundary surface;
b) Determining a 1-dimensional mesh at least twice as fine as the first trunk mesh along said boundary;
c) Identifying pairs of nodes of the first trunk mesh defining intersections of the 1-dimensional mesh and the first trunk mesh; and
d) Moving a node from each pair to said boundary.
5. The method of claim 4 , wherein moving a node comprises determining which node of each pair will, if moved, produce the highest quality mesh elements, and moving that node.
6. The method of claim 4 , wherein moving a node comprises determining which node of each pair is closest to the boundary, and moving that node.
7. The method of claim 4 , wherein determining a second trunk mesh further comprises determining if the boundary spans the diagonal of any element of the second trunk mesh after moving nodes to the boundary, and if so, then moving one of the other nodes of said element to the boundary.
8. The method of claim 4 , wherein determining a second trunk mesh further comprises smoothing the portion of the first trunk mesh inside the boundary after moving nodes to the boundary.
9. The method of claim 4 , wherein determining a second trunk mesh further comprises smoothing the portion of the first trunk mesh outside the boundary after moving nodes to the boundary.
10. The method of claim 4 , wherein determining a second trunk mesh further comprises adding a pillow of mesh elements directly inside the boundary.
11. The method of claim 4 wherein determining a second trunk mesh further comprises smoothing the portion of the first trunk mesh beneath the boundary surface after moving nodes to the boundary.
12. A method of using a computer to generate a computer-readable mesh representation of a region characterized by a computer-readable representation of a trunk and a computer-readable representation of a branch thereon, comprising:
a) Determining a first trunk mesh from the computer-readable representation of the trunk;
b) Determining a second trunk mesh by adjusting the portion of the first mesh proximal the boundary surface between the trunk and the branch to substantially conform thereto;
c) Determining a branch mesh from the portion of the second mesh within said boundary surface and the geometry of the branch; and
d) Displaying the computer-readable mesh representation on a computer screen.
13. The method of claim 12 , wherein the trunk comprises a 2½-dimensional region, and wherein determining a first trunk mesh comes sweeping the volume of the trunk.
14. The method of claim 12 , wherein the branch comprises a 2½-dimensional region, and wherein determining a graft mesh comprises sweeping the volume of the branch.
15. The method of claim 12 , wherein determining a second trunk mesh comprises:
a) Determining the boundary of said boundary surface;
b) Determining a 1-dimensional mesh at least twice as fine as the first trunk mesh along said boundary;
c) Identifying pairs of nodes of the first trunk mesh defining intersections of the 1-dimensional mesh and the first trunk mesh; and
d) Moving a node from each pair to said boundary.
16. The method of claim 15 , wherein moving a node comprises determining which node of each pair will, if moved, produce the highest quality mesh elements, and moving that node.
17. The method of claim 15 , wherein moving a node comprises determining which node of each pair is closest to the boundary, and moving that node.
18. The method of claim 15 , wherein determining a second trunk mesh further comprises determining if the boundary spans the diagonal of any element of the second trunk mesh after moving nodes to the boundary, and if so, then moving one of the other nodes of said element to the boundary.
19. The method of claim 15 , wherein determining a second trunk mesh further comprises smoothing the portion of the first trunk mesh inside the boundary after moving nodes to the boundary.
20. The method of claim 15 , wherein determining a second trunk mesh further comprises smoothing the portion of the first trunk mesh outside the boundary after moving nodes to the boundary.
21. The method of claim 15 , wherein determining a second trunk mesh further comprises adding a pillow of mesh elements directly inside the boundary.
22. The method of claim 15 wherein determining a second trunk mesh further comprises smoothing the portion of the first trunk mesh beneath the boundary surface after moving nodes to the boundary.