Method and apparatus for processing finite element meshing model5819070
Abstract
In a finite element meshing model, the number of elements sharing boundaries surrounding a node of interest are counted and whether the node is positioned inside or outside an outer circumference of the element mesh model is determined to detect errors. Errors are detected when the position of a node determined from the sum of the angles of the elements surrounding the node differs from the position of the node determined from boundary face connections. An error is also determined from the maximum and minimum angles of the external shape of a model formed from input data.
Claims
What is claimed is:
1. A finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
determining whether the node of interest is positioned inside or on an outer circumference of an analytic model consisting of finite elements on the basis of the counted value;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position,
wherein the error detection step includes a step of determining that the node of interest is positioned in a constricted part when all of the counts are not 2 and a number of appearances of a boundary whose count is 1 is not 2.
2. The method according to claim 1, wherein the error detection step comprises determining that the node of interest is a floating point if the count is 0.
3. The method according to claim 1, wherein the error detection step comprises determining that boundaries of elements surrounding the node of interest overlap each other if at least one of the counts is not less than 3.
4. The method according to claim 1, wherein
the analytic model is a three-dimensional model, and
the error detection step comprises determining that the node of interest is positioned in a constricted part if all of the counts are 1.
5. The method according to claim 1, wherein the analytic model is a three-dimensional model, and the error detection step includes a step of, when the node of interest is positioned on an outer circumference of an analytic model consisting of finite elements, performing finite element meshing data error detection on the basis of connection of boundaries between the elements.
6. The method according to claim 5, wherein the position determination step determining that the node of interest is positioned on an outer circumference of an analytic model consisting of finite elements when all of the counts are not 2, and
the error detection step includes the step of performing finite element meshing data error detection on the basis of connection of boundaries whose counts are 1.
7. The method according to claim 6, wherein the error detection step includes the steps of regarding boundaries whose counts are 1 as second elements, counting a number of second elements having each of the boundaries of the second elements, respectively, and, if all of the counts are not 2, determining that the node is positioned in a constricted part.
8. The method according to claim 6, wherein the error detection step includes the steps of regarding boundaries whose counts are 1 are regarded as second elements, counting a number of second elements sharing each of the boundaries between the second elements, respectively, and, when all of the counts are 2 but the second elements do not constitute one continuous element group, determining that the node is positioned in a constricted part.
9. A finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
obtaining a sum of internal angles around the node of interest in elements surrounding the node of interest;
determining whether the node of interest is positioned inside or on an outer circumference of an analytic model consisting of finite elements on the basis of the counted value and the sum of internal angles;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
outputting the detected errors,
wherein the error detection step includes a step of determining that the node of interest is positioned in a constricted part when all of the counts are not 2 and a number of appearances of a boundary whose count is 1 is not 2.
10. The method according to claim 9, wherein the analytic model is a two-dimensional model, and the error detection step includes a step of determining overlapping of elements if all of the counts are 2 and the sum of the internal angles is not 2 .pi..
11. The method according to claim 9, wherein the analytic model is a two-dimensional model, and the error detection step includes of step of performing finite element meshing data error detection on the basis of a number of appearances of a boundary whose count is 1 when all of the counts are not 2.
12. The method according to claim 11, wherein the error detection step includes a step of determining that the node of interest is positioned in a constricted part when all of the counts are not 2 and a number of appearances of a boundary whose count is 1 is not 2.
13. The method according to claim 11, wherein the error detection step includes the steps of, when all of the counts are not 2 and a number of appearances of the boundary whose count is 1 is 2, performing finite element meshing data error detection on the basis of whether the sum of the internal angles is between a maximum angle and a minimum angle of an external shape of the analytic model, and, when the sum of the internal angles is not between the maximum and the minimum angles, determining that an element is missing, the node of interest has an overlapping node, or the node is positioned on a boundary of another element.
14. The method according to claim 9, wherein
the analytic model is a three-dimensional model, and
the error detection step includes a step of determining overlapping of elements when all of the counts are 2 and the sum of the internal angles is not 4 .pi..
15. The method according to claim 9, wherein the analytic model is a three-dimensional model, and the error detection step includes a step of, when the node of interest is positioned on an outer circumference of an analytic model consisting of finite elements, performing finite element meshing data error detection on the basis of connection of boundaries between the elements.
16. The method according to claim 15, wherein the position determination step includes a step of determining that the node of interest is positioned on an outer circumference of an analytic model consisting of finite elements when all of the counts are not 2, and the error detection step includes a step of performing finite element meshing data error detection on the basis of connection of boundaries whose counts are 1.
17. The method according to claim 16, wherein the error detection step includes the steps of regarding boundaries whose counts are 1 as second elements, counting a number of second elements sharing each of the boundaries of the second elements, respectively, when all of the counts are 2 and the second elements constitute one continuous element group, performing finite element meshing data error detection on the basis of whether the sum of the internal angles is between a maximum angle and a minimum angle of an external shape of the analytic model, and, when the sum of the internal angles is not between the maximum and the minimum angles, determining that an element is missing, nodes overlapping each other, or a node is positioned on a boundary of another element.
18. A finite element meshing data error detection method of detecting an error in finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
determining whether the node of interest is positioned inside or on the outer circumference of an analytic model consisting of finite elements on the basis of the counted value;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
outputting the detected error,
wherein the analytic model is a two-dimensional model and the error detection step includes a step of determining that the node of interest is positioned in a constricted part when all of the counts are not 2 and a number of appearances of a boundary whose count is 1 is not 2.
19. A finite element meshing data error detection method of detecting an error in finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
determining whether the node of interest is positioned inside or on the outer circumference of an analytic model consisting of finite elements on the basis of the counted value and a sum of internal angles;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
outputting the detected error,
wherein the analytic model is a two-dimensional model and the error detection step includes the steps of, when all of the counts are not 2 and a number of appearances of a boundary whose count is 1 is 2, performing finite element meshing data error detection on the basis of whether the sum of the internal angles is between a maximum angle and a minimum angle of an external shape of the analytic model, and, when the sum of the internal angles is not between the maximum and the minimum angles, determining that an element is missing, the node of interest has an overlapping node, or a node is positioned on a boundary of another element.
20. A finite element meshing data error detection method of detecting an error in finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
determining whether the node of interest is positioned inside or on the outer circumference of an analytic model consisting of finite elements on the basis of the counted value;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
outputting the detected error, wherein the analytic model is a three-dimensional model, the positioning determination step determines that the node of interest is positioned on the outer circumference of an analytic mode consisting of finite elements when all of the counts are not 2, and the error detection step includes the steps of regarding boundaries whose counts are 1 as second elements, counting a number of second elements sharing each between the boundaries of the second elements, respectively, and, when all of the counts are not 2, determining that the node is positioned in a constricted part.
21. A finite element meshing data error detection method of detecting an error in finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
determining whether the node of interest is positioned inside or on the outer circumference of an analytic model consisting of finite elements on the basis of the counted value;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
outputting the detected error,
wherein the analytic model is a three-dimensional model, the positioning determination step determines that the node of interest is positioned on the outer circumference of an analytic mode consisting of finite elements when all of the counts are not 2, and the error detection step includes the steps of regarding boundaries whose counts are 1 as second elements, counting a number of second elements sharing each of the boundaries between the second elements, respectively, and, when all of the counts are 2 but the second elements do not constitute one continuous element group, determining that the node is positioned in a constricted part.
22. A finite element meshing data error detection method of detecting an error in finite element meshing data error detection method of detecting an error in finite element meshing data formed by segmenting an analytic model into finite elements, comprising the steps of:
counting a number of elements sharing each of boundaries between elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
determining whether the node of interest is positioned inside or on the outer circumference of an analytic model consisting of finite elements on the basis of the counted value;
detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
outputting the detected error,
wherein the analytic model is a three-dimensional model, the positioning determination step determines that the node of interest is positioned on the outer circumference of an analytic mode consisting of finite elements when all of the counts are not 2, and the error detection step includes the steps of regarding boundaries whose counts are 1 as second elements, counting a number of second elements sharing each of the boundaries between the second elements, respectively, when all of the counts are 2 but the second elements constitute one continuous element group, performing finite element meshing data error detection on the basis of whether a sum of internal angles around the node of interest in the second elements surrounding the node of interest is between a maximum angle and a minimum angle of an external shape of the analytic model, and, when the sum of the internal angles is not between the maximum and the minimum angles, determining that an element is missing, nodes overlap each other, or a certain node is positioned on a boundary of another element.
23. A method of extracting a side, a face or an element from finite element meshing model formed by segmenting an analytic model into finite elements, comprising the steps of:
when elements and nodes constituting the elements are stored in storage means so as to correspond to each other, and by regarding one side, face, or element as one segment, the segment is extracted from the finite element meshing model;
assigning to each segment an identifier generated on the basis of a combination of nodes constituting the segment;
forming and storing a segment list in which pieces of information of segments having the same identifier are consecutively arranged;
forming and storing an index table in which index values, each indicating a position in the segment list and a number of the segments having the same identifier, are arranged corresponding to the identifiers; and
by indicating an identifier, extracting segments having the identifier obtaining from said storage means information of nodes constituting the segments having the identifier, on the basis of the segment list and the index table.
24. The method according to claim 23, wherein the segments stored in the segment list are arranged in a decreasing or increasing order of the identifier.
25. The method according to claim 23, wherein the index value corresponding to each identifier in the index table is expressed by a number of segments corresponding to the identifier and a pointer indicating a first position in the segment list from which the segments having the same identifier are stored.
26. The method according to claim 25, wherein the point is multiplied by an integral value not less than 10, and the number of segments is added to the product, thereby storing the number and the pointer as one integral value in the index table.
27. The method according to claim 25, wherein the segment list and the index table are formed by a procedure of calculating a number of segments having the same identifier on the basis of the identifiers of segments, obtaining the pointer by adding the calculated numbers in an increasing or decreasing order of index value, and registering the information of each segment in the segment list on the basis of the pointer.
28. The method according to claim 23, further comprising a step of extracting a plurality of elements consisting of the same nodes as adjacent elements among the extracted segments having the same identifier.
29. The method according to claim 23, further comprising a step of removing segments consisting of the same nodes from the segment list, thereby allowing only segments not overlapping with other segments to remain in the segment list.
30. The method according to claim 29, wherein the segments are faces constituting a finite element meshing model, and free faces not shared by a plurality of elements are allowed to remain in the segment list.
31. The method according to claim 29, wherein the segments are sides constituting a finite element meshing model, and free edges not shared by a plurality of elements are allowed to remain in the segment list.
32. A method of extracting a side, face or an element from finite element meshing model formed by segmenting an analytic model into finite elements, comprising the steps of:
when elements and nodes constituting the elements are stored in storage means so as to correspond to each other, and by regarding one side, face, or element as one segment, the segment is extracted from the finite element meshing model;
assigning to each segment a first identifier which specifies an element including the segment;
assigning to each segment a second identifier which indicates an ordinal position of the segment in an element;
forming and storing a segment list in which the first and second identifiers of segments having an identifier generated on the basis of a combination of nodes constituting each segment are consecutively arranged, and
by indicating an identifier, extracting segments having the identifier and obtaining from said storage means information of nodes constituting the segments having the identifier, on the basis of the segment list.
33. The method according to claim 32, wherein the first identifier is multiplied by a predetermined integral value not less than the number of segments constituting one element, and the second identifier is added to the product, thereby storing the first and the second identifiers as one integral value in the segment list.
34. A method of extracting an element including a point P.sub.e in a finite element meshing model, comprising the steps of:
obtaining, starting from a known point P.sub.0 included in a given element E.sub.0 a face F.sub.0 of the element E.sub.0 which intersects a line segment connecting two points P.sub.e and P.sub.0 ;
obtaining an element E.sub.1 adjacent to the element E.sub.0 through the face F.sub.0 as a boundary;
obtaining a face F.sub.1, other than the face F.sub.0 of the element E.sub.1, which intersects the line segment connecting the points P.sub.e and P.sub.0 ;
repeating a process of extracting an element E.sub.2 adjacent to the element E.sub.1 through the face F.sub.1 ; and
extracting an element including the point P.sub.e by tracing the adjacent elements,
wherein the adjacent element extracting step includes the steps of:
when elements and nodes constituting the elements are stored in storage means so as to correspond to each other, and by regarding one side, face or element as one segment, the segment is extracted from the finite element meshing mode;
assigning to each segment an identifier generated on the basis of a combination of nodes constituting the segment;
forming and storing a segment list in which pieces of information of segments having the same identifier are consecutively arranged;
forming and storing an index table in which index values, each indicating a position in the segment list and a number of segments having the same identifier, are arranged corresponding to the identifiers;
by indicating an identifier, extracting segments having the identifier and obtaining from said storage means information of nodes constituting the segments having the identifier, on the basis of the segment list and the index table; and
extracting a plurality of elements consisting of the same nodes as adjacent elements among the extracted segments having the same identifier.
35. A method of extracting a side from a finite element meshing model, comprising the steps of:
extracting free faces from a three-dimensional finite element model;
by regarding the free faces as shell-like two-dimensional elements, extracting adjacent two-dimensional elements;
calculating an angle .theta. formed by the adjacent two-dimensional elements; and
extracting a boundary between the two-dimensional elements as a contour if a value of the angle .theta. satisfies 0.ltoreq..theta.<(.pi.-.differential.) or (.pi.+.differential.)<.theta.<2 .pi. where .differential. is a tolerance,
wherein the extracting of the free faces and adjacent two-dimensional elements is performed using information of nodes constituting segments having an identifier obtained from storage means, said information of nodes obtained by the steps of:
when elements and nodes constituting the elements are stored in the storage means so as to correspond to each other, and by regarding one side, face or element as one segment, the segment is extracted from the finite element meshing model,
assigning to each segment the identifier generated on the basis of a combination of nodes constituting the segment;
forming and storing a segment list in which pieces of information of segments having the same identifier are consecutively arranged;
forming and storing an index table in which index values, each indicating a position in the segment list and a number of the segments having the same identifier, are arranged corresponding to the identifier; and
by indicating an identifier, extracting segments having the identifier and obtaining from said storage means information of nodes constituting the segments having the identifier, on the basis of the segment list and the index table.
36. The method according to claim 35, further comprising the steps of:
adding a three-dimensional meshing model consisting of shell-like, two-dimensional elements to the extracted free faces and extracting adjacent two-dimensional elements; and
extracting a boundary between the two two-dimensional elements as a contour if a value of the angle .theta. satisfies .differential..ltoreq..theta.<(.pi.-.differential.) or (.pi.+.differential.)<.theta.<2 .pi.-.differential. where .differential. is a tolerance.
37. The method according to claim 35, further comprising the steps of:
setting .pi./180.ltoreq..differential..ltoreq..pi./18 as a default value of the tolerance .differential., and
allowing a user to designate an arbitrary value as the tolerance .differential. while using a program.
38. The method according to claim 35, wherein the free face extraction step includes a step of removing segments having the same nodes from the segment list, thereby extracting faces remaining in the segment list as free faces.
39. The method according to claim 35, wherein the adjacent two-dimensional element extraction step includes a step of extracting a plurality of elements, as adjacent faces, constituted by segments consisting of the same nodes among other extracted segments.
40. An apparatus for extracting a side, a face or an element from a finite element meshing model formed by segmenting an analytic model into finite elements, comprising:
means for storing elements and nodes constituting the elements so that the elements and the nodes correspond to each other;
means for regarding one side, face or element as one segment, assigning to each segment an identifier generated on the basis of a combination of nodes constituting the segment;
means for forming and storing a segment list in which pieces of information of segments having the same identifier are consecutively arranged;
means for forming and storing an index table in which index values, each indicating a position in the segment list and a number of segments having the same identifier, are arranged corresponding to the identifier; and
means for, by indicating an identifier, extracting segments having the identifier table and obtaining from said storage means information of nodes constituting the segments having the identifier on the basis of the segment list and the index table.
41. The apparatus according to claim 40, wherein the segments stored in the segment list are arranged in a decreasing or increasing order of the identifier.
42. The apparatus according to claim 40, wherein the index value corresponding to each identifier in the index table is expressed by a number of segments corresponding to the identifier and a pointer indicating a first position in the segment list from which the segments having the same identifier are stored.
43. The apparatus according to claim 42, wherein the pointer is multiplied by an integral value not less than 10, and the number of segments is added to the product, thereby storing the number and the pointer as one integral value in the index table.
44. The apparatus according to claim 42, wherein said means for forming and storing the segment list and the index table comprises:
means for calculating a number of segments having an identifier on the basis of the identifiers of segments;
means for obtaining the pointer by adding the calculated numbers in an increasing or decreasing order of index value; and
means for registering the pointer in the index table and the information of each segment in the segment list on the basis of the pointer.
45. The apparatus according to claim 40, further comprising means for extracting a plurality of elements consisting of the same nodes as adjacent elements among the extracted segments having the same identifier.
46. The apparatus according to claim 40, further comprising means for removing segments consisting of the same nodes from the segment list, thereby allowing only segments not overlapping with other segments to remain in the segment list.
47. An apparatus for extracting a side, a face or an element from a finite element meshing model formed by segmenting an analytic model into finite elements, comprising:
means for storing elements and nodes constituting the elements so that the elements and the nodes correspond to each other;
means for, by regarding one side, face or element as one segment, assigning to each segment a first identifier which specifies an element including a segment and a second identifier which indicates an ordinal position of the segment in the element;
means for forming and storing a segment list in which the first and second identifiers of segments having an identifier generated on the basis of a combination of nodes constituting each segment are consecutively arranged; and
means for, by indicating an identifier, extracting segments having the identifier and obtaining from said storage means information of nodes constituting the segments having the identifier, on the basis on the segment list.
48. The apparatus according to claim 47, wherein the first identifier is multiplied by a predetermined integral value not less than a number of segments constituting one element, and the second identifier is added to the product, thereby storing the first and the second identifiers as one integral-value in the segment list.
49. A method of extracting a contour from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, said finite element meshing model obtained by segmenting an analytic model into finite elements, comprising the steps of:
extracting free faces not shared by a plurality of elements from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
checking, when a number of free faces extracted from an element is not less than 2, whether two free faces sharing any one side of the element are extracted, and determining that a side shared by two free faces is a contour; and
extracting contours from the finite element meshing model stored in the storage means on the basis of the determined result.
50. The method according to claim 49, further comprising a step of, when a the number of free faces extracted from an element is not more than 1, determining that any sides of the element are not contours.
51. The method according to claim 49, further comprising a step of extracting overlapping contours, nodes at two ends of which have respective same node numbers, from the extracted contours.
52. A method of extracting a contour and a vertex from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, said finite element meshing model obtained by segmenting an analytic model into finite elements, comprising the steps of:
extracting free faces not shared by a plurality of elements from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
checking, when a number of free faces extracted from an element is not less than 2, whether two free faces sharing any one side of the element are extracted, and determining that a side shared by two free faces is a contour;
checking, when a number of sides determined as contours in an element is not less than 3, whether each of sides sharing one node of the element as an end point thereof is extracted as a contour, and, when all the sides sharing a node are extracted as contours, determining that the node is a vertex;
extracting contours and vertices from the finite element meshing model stored in the storage means on the basis of the determined result of said contour and vertex determining steps.
53. The method according to claim 52, wherein
the free face extraction step comprises extracting a free face from an element by checking, for all faces of the element, whether a face of the element is shared by another element,
the contour extraction step comprises checking whether two faces having one side of an element as sides thereof are extracted as free faces, and, if both of the two faces are extracted as free faces, determining that the side is a contour, and
the vertex extraction step comprises checking whether an edge having one node of each element as an end point thereof is extracted as a contour, and, if all of the sides are extracted as contours, determining that the node is a vertex.
54. The method according to claim 52, further comprising a step of, when a number of free faces extracted from an element is not more than 1, determining that any sides of the element are not contours.
55. The method according to claim 52, further comprising a step of, when a number of sides determined as contours in an element is not more than 2, determining that any nodes of the element are not vertices.
56. The method according to claim 52, further comprising a step of displaying the extracted vertices in a diagram with contours or free edges of the finite element meshing model to check the finite element meshing model.
57. A method of extracting a vertex from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, said finite element meshing model obtained by segmenting an analytic model into finite elements, comprising the steps of:
extracting free edges from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
checking, when a number of free edges extracted from an element is not less than 2, whether two free edges sharing one node of the element as end points thereof are extracted, and determining that a node shared by two free edges is a vertex; and
extracting vertices from the finite element meshing model stored in the storage means on the basis of the determined result.
58. The method according to claim 57, further comprising a step of, when a number of free edges extracted from an element is not more than 1, determining that any nodes of the element are not vertices.
59. The method according to claim 57, further comprising a step of displaying the extracted vertices in a diagram with contours or free edges of the finite element meshing model.
60. An apparatus for extracting a contour from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, and finite element meshing model obtained by segmenting an analytic model into finite elements, comprising:
free face extracting means for extracting free faces from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
first contour determining means for determining that any sides of an element are not contours, when a number of free faces extracted from the element is not more than 1;
second contour determining means for checking, when a number of free faces extracted from an element is not less than 2, whether two free faces sharing any one side of the element are extracted, and determining that a side shared by two free faces is a contour; and
extracting means for extracting contours from the finite element meshing model stored in the storage means on the basis of the determined result of said first and second contour determining means.
61. The apparatus according to claim 60, further comprising overlapping contour extracting means for extracting overlapping contours, nodes at two ends of which have respective same node numbers, from the extracted contours, to check mismatching between elements in the finite element meshing model on the basis of overlapping of contours.
62. An apparatus for extracting a contour and a vertex from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, said finite element meshing model obtained by segmenting an analytic model into finite elements, comprising:
free face extracting means for extracting free faces from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
first contour determining means for determining that any sides of an element are not contours, when a number of free faces extracted from the element is not more than 1;
second contour determining means for checking, when a number of free faces extracted from an element is not less than 2, whether two faces sharing any one side of the element are extracted, and determining that a side shared by two free faces is a contour;
first vertex determining means for determining that any nodes of an element are not vertices, when a number of sides determined as contours in the element is not more than 2;
second vertex determining means for checking, when a number of sides determined as contours in an element is not less than 3, whether each of sides sharing one node of the element as an end point thereof is extracted as a contour, and, when all the sides sharing a node are extracted as contours, determining that the node is a vertex; and
extracting means for extracting contours and vertexes from the finite element meshing model stored in the storage means on the basis of the determined result of said first and second contour determining means and said first and second vertex determining means.
63. The apparatus according to claim 62, further comprising meshing model displaying means for displaying the extracted vertices in a diagram with contours or free edges of the finite element meshing model to check the finite element meshing model.
64. An apparatus for extracting a vertex from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, said finite element meshing model obtained by segmenting an analytic model into finite elements, comprising:
free edge extracting means for extracting free edges from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
first vertex determining means for determining that any nodes of an element are not vertices, when a number of free edges extracted from an element is not more than 1; and
second vertex determining means for checking, when a number of free edges extracted from an element is not less than 2, whether two free edges sharing one node of the element as end points thereof are extracted, and determining that a node shared by two free edges is a vertex; and
extracting means for extracting vertices from the finite element meshing model stored in the storage means on the basis of the determined result of said first and second vertex determining means.
65. The apparatus according to claim 64, further comprising meshing model displaying means for displaying the extracted vertices in a diagram with contours or free edges of the finite element meshing model to check the finite element meshing model.
66. A computer program product comprising a computer usable medium having computer readable program code means for error detection in finite element meshing data formed by segmenting an analytic model into finite elements, said computer program product including:
computer readable program code means for counting a number of elements having each of boundaries of elements surrounding a node of interest, respectively, when reading out finite element meshing data composed based on nodes and stored in storage means;
computer readable program code means for determining whether the node of interest is positioned inside or on an outer circumference of an analytic model consisting of finite elements on the basis of the counted value;
computer readable program code means for detecting an error in the finite element meshing data corresponding to a position of the node of interest on the basis of the determined position; and
computer readable program code means for outputting the detected error.
67. The product according to claim 66, further comprising computer readable program code means for checking whether the node of interest is positioned inside or on an outer circumference of an analytic model consisting of finite elements.
68. The product according to claim 66, further comprising data of a finite element meshing model.
69. A computer program product comprising a computer usable medium having computer readable program code means for extracting a side, a face and an element from a finite element meshing model in finite element meshing data formed by segmenting an analytic model into finite elements, said computer program product comprising:
computer readable program code means for, when regarding one side, face or element as one segment and extracting the segment from a finite element meshing model composed based on nodes, assigning to each segment a first identifier which specifies an element including the segment, a second identifier which indicates an ordinal position of the segment in an element, and a combination of nodes constituting the segment;
computer readable program code means for forming and storing a segment list in which the first and second identifiers of segments having a third identifier are consecutively arranged;
computer readable program code means for forming and storing an index table in which index values, each indicating a position in the segment list and a number of the segments having the same third identifier, are arranged corresponding to the third identifiers; and
computer readable program code means for, by indicating a third identifier, extracting segments having the same third identifier and obtaining by indicating an identifier, information of nodes constituting the segments having the identifier, on the basis on the segment list and the index table.
70. The product according to claim 69, further comprising data of a finite element meshing model.
71. A computer program product comprising a computer usable medium having computer readable program code means for extracting a contour or a vertex from a finite element meshing model composed based on nodes and stored in storage means to find an incorrect data included in the finite element meshing model, said finite element meshing model obtained by segmenting an analytic model into finite elements, said computer program product comprising:
computer readable program code means for extracting free faces from an element by checking, for all faces of the element, whether each face of the element is shared by another element;
computer readable program code means for determining that any sides of an element are not contours, when a number of free faces extracted from the element is not more than 1;
computer readable program code means for checking, when a number of free faces from an element is not less than 2, whether two free faces sharing any one side of the element are extracted, and determining that a side shared by two free faces is a contour; and
computer readable program code means for extracting contours from the finite element meshing model stored in the storage means on the basis of the contour determined result.
72. The product according to claim 71, further comprising computer readable program code means for extracting a vertex by using data of the extracted contour.
73. The product according to claim 71, further comprising data of a finite element meshing model.
Description
BACKGROUND OF THE INVENTION
The present invention relates to a method and an apparatus for performing various processes for two-dimensional or three-dimensional finite element meshing models for use in, e.g., finite element analysis or boundary element analysis. More specifically, the present invention relates to detection of data errors in formed element meshing diagrams, relates to extraction of contours and vertices (acute portions in three-dimensional models and corners in two-dimensional models) of finite element meshing models, which can be used in displaying finite element meshing models and detecting errors that the meshing models have, and relates to extraction of sides, faces, and elements from finite element meshing models, which is useful in extracting a specific side, face, or finite element (these will be collectively referred to as segments hereinafter) from a finite element meshing model and usable in extraction of counters, surfaces, and overlapping elements of a finite element meshing model, extraction of adjacent elements in the model, and extraction of an element including an arbitrary point of the model.
With the recent rapid progress of computers, numerical analytic methods such as a finite difference method, a finite element method, and a boundary element method have become frequently used. Generally, these numerical analytic methods make use of a finite element meshing model formed by meshing an analytic model into a number of finite elements (meshing models used in the finite difference method, the finite element method, and the boundary element method will be collectively referred to as finite element meshing models hereinafter). Recently, three-dimensional element meshing models are commonly used because the computer performance has been improved.
(I) First, in data analysis using the finite element method, finite element meshing data formed by meshing an analytic model into finite elements is necessary. Generally, this finite element meshing data is interactively formed by an analyst by using a computer (particularly EWS). The element meshing data thus formed often has errors excluding input errors such as shape input errors.
Commonly, errors in element meshing data are classified into two categories: nonfatal errors which increase calculation errors by an analytic solver, but have no influence on calculations and fatal errors which make an analytic solver inexecutable or which lead to solutions under conditions different from those intended by an analyst. The former errors are generally caused by the shapes of individual elements, e.g., flat elements and distorted elements. These errors are detected by checking the shapes of individual elements. On the other hand, the latter errors result from, e.g., mismatching in links between elements. The latter errors will be described in more detail below.
Assume that thin plate-like elements in which all nodes are present on a two-dimensional plane will be called two-dimensional elements and elements having a volume and a three-dimensional shape will be called three-dimensional elements. Assume also that models consisting of two-dimensional elements will be called two-dimensional models and models consisting of three-dimensional elements will be called three-dimensional models.
Generally, element meshing data must satisfy the following conditions.
(1) No elements overlap each other.
(2) An analytic region is filled with elements.
(3) No overlapping nodes exist at the same position.
(4) No node is present on sides (faces in the case of a three-dimensional element) of an element.
(5) No constricted part is present in which elements of an analytic model connect to each other at one node (on one side in the case of a three-dimensional model).
(6) A node which is not used in the constitution of an element does not exist (such a node is referred as a floating node hereinafter).
FIGS. 9A to 10H are diagrams showing inappropriate meshing without satisfying these conditions. In these drawings, white and black dots indicate nodes, n.sub.1, n.sub.2, . . . indicate node numbers, and E.sub.1, E.sub.2, . . . indicate element numbers.
FIGS. 9A to 9F illustrate examples of inadequate element meshing in two-dimensional models. These figures are inappropriate for the following reasons.
In FIG. 9A, elements E.sub.1 and E.sub.2 are triangular elements consisting of nodes (n.sub.1 n.sub.2 n.sub.3) and (n.sub.3 n.sub.4 n.sub.1), respectively, and E.sub.3 is a quadrangular element consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.4). Accordingly, the element E.sub.3 overlaps the elements E.sub.1 and E.sub.2 (item (1) above).
In FIG. 9B, elements E.sub.1, E.sub.2, E.sub.3, and E.sub.4 are triangular elements consisting of nodes (n.sub.2 n.sub.3 n.sub.5), (n.sub.3 n.sub.4 n.sub.5), (n.sub.1 n.sub.2 n.sub.4), and (n.sub.2 n.sub.4 n.sub.5), respectively. An error occurs because the node n.sub.5 which is supposed to be present at the position of the asterisk in FIG. 9B exists inside the element E.sub.3. The elements E.sub.1, E.sub.2, and E.sub.4 partially overlap the element E.sub.3 (item (1) above).
In FIG. 9C, a hatched element consisting of nodes (n.sub.1 n.sub.2 n.sub.3) is missing (item (2) above).
In FIG. 9D, elements E.sub.1, E.sub.2, E.sub.3, and E.sub.4 are triangular elements consisting of nodes (n.sub.1 n.sub.2 n.sub.5), (n.sub.2 n.sub.3 n.sub.5), (n.sub.3 n.sub.4 n.sub.6), and (n.sub.4 n.sub.1 n.sub.6), respectively. The nodes n.sub.5 and n.sub.6 are present at the same position (item (3) above).
FIG. 9E, elements E.sub.1, E.sub.2, and E.sub.3 are triangular elements consisting of nodes (n.sub.1 n.sub.2 n.sub.4), (n.sub.2 n.sub.3 n.sub.5), and (n.sub.3 n.sub.4 n.sub.5), respectively. The node n.sub.5 exists on one edge of the element E.sub.1 (item (4) above).
FIG. 9F is an element meshing diagram including two triangular elements E.sub.1 and E.sub.2. A constricted part is formed at a node n.sub.1 (item (5) above).
FIGS. 10A to 10H illustrate examples of inadequate element meshing in three-dimensional models. The element meshing diagrams in FIGS. 10A to 10H are inappropriate for the following reasons.
In FIG. 10A, elements E.sub.1 and E.sub.2 are triangular prism elements consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.5 n.sub.6 n.sub.7) and (n.sub.1 n.sub.3 n.sub.4 n.sub.5 n.sub.7 n.sub.8), and an element E.sub.3 is a hexahedral element consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.4 n.sub.5 n.sub.6 n.sub.7 n.sub.8). The element E.sub.3 overlaps the elements E.sub.1 and E.sub.2 (item (1) above).
In FIG. 10B, elements E.sub.1, E.sub.2, E.sub.3, E.sub.4, and E.sub.5 are tetrahedral elements consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.4), (n.sub.3 n.sub.4 n.sub.6 n.sub.5), (n.sub.4 n.sub.1 n.sub.6 n.sub.5), (n.sub.1 n.sub.3 n.sub.6 n.sub.5), and (n.sub.1 n.sub.3 n.sub.4 n.sub.5), respectively. An error occurs since the node n.sub.5 which is supposed to exist inside the tetrahedron (n.sub.1 n.sub.3 n.sub.4 n.sub.6) is present inside the element E.sub.3. The elements E.sub.1 to E.sub.5 partially overlap each other (item (1) above).
FIG. 10C is an element meshing diagram including triangular prism elements E.sub.1 and E.sub.2 and a hexahedral element E.sub.3. These elements contact each other only on one side n.sub.1 n.sub.2 to form a constricted part (item (5) above).
In FIG. 10D, elements E.sub.1, E.sub.2, E.sub.3, and E.sub.4 are tetrahedral elements consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.4), (n.sub.1 n.sub.6 n.sub.2 n.sub.5), (n.sub.7 n.sub.5 n.sub.4 n.sub.1), and (n.sub.8 n.sub.5 n.sub.2 n.sub.4), respectively. An element consisting of nodes (n.sub.1 n.sub.5 n.sub.2 n.sub.4) is missing (item (2) above).
In FIG. 10E, elements E.sub.1, E.sub.2, E.sub.3, and E.sub.4 are triangular prism elements consisting of nodes (n.sub.1 n.sub.2 n.sub.9 n.sub.5 n.sub.6 n.sub.11), (n.sub.2 n.sub.3 n.sub.9 n.sub.6 n.sub.7 n.sub.11), (n.sub.3 n.sub.4 n.sub.10 n.sub.7 n.sub.8 n.sub.12), and (n.sub.4 n.sub.1 n.sub.10 n.sub.8 n.sub.5 n.sub.12), respectively. The nodes n.sub.9 and n.sub.10 exist in the same position and the nodes n.sub.11 and n.sub.12 exist in the same position (item (3) above).
In FIG. 10F, elements E.sub.1, E.sub.2 and E.sub.3 are triangular prism elements consisting of nodes (n.sub.1 n.sub.2 n.sub.9 n.sub.5 n.sub.6 n.sub.10), (n.sub.2 n.sub.3 n.sub.9 n.sub.6 n.sub.7 n.sub.10), and (n.sub.1 n.sub.3 n.sub.4 n.sub.5 n.sub.7 n.sub.8), respectively. The nodes n.sub.9 and n.sub.10 exist on faces of the element E.sub.3 (item (4) above).
In FIG. 10G, elements E.sub.1 and E.sub.2 are triangular prism elements consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.4 n.sub.5 n.sub.6) and (n.sub.3 n.sub.7 n.sub.6 n.sub.8 n.sub.9 n.sub.10). The node n.sub.7 exists on one face of the element E.sub.1 (item (4) above).
FIG. 10H is an element meshing diagram, analogous to FIG. 10C, including elements E.sub.1 and E.sub.2. These elements contact each other only on one side n.sub.1 n.sub.2 to form a constricted part (item (5) above).
Explanation of item (6) described above is omitted from these drawings.
The following five methods are commonly used as the conventional methods of detecting these fatal errors in element meshing data.
(1) Method of drawing free edges
A side used only by one element (i.e., a side, or an edge in the case of a three-dimensional element, not shared by two or more elements; which will be referred to as a free edge hereinafter) is extracted from an element meshing diagram and displayed. If there is mismatching between elements inside the element meshing diagram, a side where this mismatching occurs is displayed to show that there is an error. Accordingly, this method can find errors of items (2), (3), (4), and (5) above.
(2) Method of calculating area (volume) and barycenter
The areas (the volumes in the case of three-dimensional elements) of individual elements in an element meshing diagram are accumulated and compared with the value calculated from an analytic region. Also, the barycenter of a whole element meshing diagram is obtained from the areas (or volumes) of individual elements in the diagram and compared with the value calculated from an analytic region. This method can find errors of items (1) and (2) above.
(3) Method of extracting overlapping elements
This method extracts elements constituted by the same nodes. These extracted elements are overlapping elements. This method can find errors of item (1) above.
(4) Method of extracting floating node
This method checks whether each node is used in the constitution of an element. This method can find errors of item (6) above.
(5) Method of displaying element in reduced scale
This method reduces each element about its barycenter, displays the reduced elements, and checks errors of all elements in the displayed meshing diagram. This method can find all errors described above.
Of these five methods, the method (1) is generally used most frequently because the effect is largest and the processing is simple. The algorithm of the method (1) will be described in detail below.
FIG. 11 is a flow chart for explaining the algorithm of the method (1) for two-dimensional models. In FIG. 11, reference symbols R1 to R6 denote processes, and arrows in an opposite direction to the processing flow indicate repetition. Symbols E.sub.n, l.sub.i, and l.sub.j beside these arrows indicate the repeating numbers. E.sub.n is the total number of elements in an element meshing diagram, l.sub.i is the total number of sides constituting an element number E.sub.i, and l.sub.j is the total number of sides constituting an element number E.sub.j (these symbols have the respective same meanings throughout the remainder of this specification).
A process of extracting and displaying a free edge is as follows.
(1) In process R1, the element E.sub.i to be checked is set. In process R2, a side to be checked is set.
(2) In process R3, the element E.sub.j to be compared is set. In process R4, a side to be compared is set (E.sub.i .noteq.E.sub.j).
(3) In process R5, the node numbers at the two ends of the sides are compared to check whether these sides are the same. If the sides are the same, the repetition of processes R3, R4, and R5 is terminated, and the flow returns to process R1 to set a new side to be checked.
(4) If there is no same side, it is determined that this side is a free edge, and a diagram is displayed in process R6.
(5) The manipulations in processes R1 to R6 described in items (1) to (4) above are repeated for all elements.
In the case of three-dimensional models, the same processing is performed by replacing sides in this processing with edges of elements.
When the number of sides (edges) constituting one element is fixed at l.sub.n, the total repeating number for performing this processing is represented by the following expression:
(E.sub.n .times.l.sub.n).sup.2 /2 (1)
If a meshing diagram consists of identical shape elements, the total repeating numbers of triangular and quadrangular elements in two-dimensional models and of tetrahedral, pentahedral, and hexahedral elements in three-dimensional models are calculated from expression (1) as shown in the column "conventional method (1)" in FIG. 12.
Unfortunately, the following problems arise when these conventional element meshing data error detection methods explained above are executed to find errors in element meshing data.
In the method (1), it is necessary to finally output free edges to a graphic terminal or a plotter to allow an analyst to visually check and judge the result. For this purpose a display device is necessary. Also, the judgment of an analyst may lead to overlook. Especially when a very small portion is present in large-scale element meshing data or analytic region, the size of a side is relatively small compared to the size of the analytic region. Consequently, it is very difficult to reliably detect these sides. Additionally, it takes a long time to make general users who do not know the finite element method very well understand the meaning of the processing.
In the method (2), if an area (volume) or the position of a barycenter is wrong, this means some elements comprise errors but an element having an error cannot be specified. Consequently, a long time and much labor are required to find an element with the error. The method (2) also has a fatal drawback to be described later.
In the method (5), all elements must be checked and this requires a long time and much labor. Additionally, an element meshing diagram in which elements are reduced is basically, graphically displayed on a two-dimensional plane. Therefore, this method is difficult to apply to three-dimensional models.
Moreover, to perform a complete check, it is basically necessary to execute all of these five methods described above, and this requires a long calculation time and a long work time. Also, errors cannot be found in some cases only by executing the five methods. This will be briefly described below.
Generally, when a quadrangular (hexahedral) element contains triangular (triangular prism) elements as illustrated in FIG. 9A or 10A, only the methods (2) and (5) are effective among other methods. In the method (2), a problem arises if the areas (volumes) of the elements E.sub.1 to E.sub.3 are much smaller than the largest element. That is, the volumes or weights of these elements are sometimes canceled in a computer during the course of accumulating the areas (volumes) or weights of the individual elements, and this makes error detection impossible. This is the fatal drawback of the method (2). On the other hand, the method (5) cannot perform check if the number of elements is very large or cannot perform a three-dimensional check. This applies to the errors in FIGS. 9B and 10B.
In the method (1), the locations of errors can be readily known in two-dimensional models because free edges are in a one-to-one correspondence with the outlines of the analytic models. In three-dimensional models, however, the outlines are not necessarily represented by free edges. This often gives rise to confusion during the course of finding the locations of errors. This will be described below with reference to FIG. 13.
In FIG. 13, elements E.sub.1 and E.sub.2 are triangular prism elements consisting of nodes (n.sub.1 n.sub.2 n.sub.3 n.sub.5 n.sub.6 n.sub.7) and (n.sub.1 n.sub.3 n.sub.4 n.sub.5 n.sub.7 n.sub.8), respectively, and the broken line, i.e., a line constituted by nodes n.sub.1 and n.sub.5 is an outline. No problem arises if an outline is formed only by a single element. However, if an outline is shared by two elements as in this case, this outline is not displayed to result in confusion. Especially in predictive meshing diagrams in which outlines are in many instances not displayed for the reason above, the locations of errors of elements cannot be found even if these errors are displayed.
(II) Second, in displaying finite element meshing models, contours of the finite element meshing models are extracted and displayed in many cases. Contours indicate edges in the case of three-dimensional finite element models and, more specifically, are constituted by sides (boundaries between faces constituting elements) of elements. Contours are thus extracted and displayed because displaying all finite elements is time-consuming. In a three-dimensional model consisting of n elements, the number of contours is the triple root of n if it is calculated simply. This means that the display time can be greatly shortened, and this is particularly effective in display in the stage of trial and error for determining a visual point. Also, a number of diagrams must be displayed within short time periods in animation display of time-series analytical results, and one conventional method made this performable within a short time by the use of contours (Japanese Patent Laid-Open No. 4-346178).
Contours are also used to find mismatching between elements contained in an element meshing model, e.g., missing of an element (a meshing model is not completely filled with elements), a floating node (a node existing on a side of an element), and overlapping of nodes (two or more nodes are present at the same point). These findings are done by displaying contours, more specifically, by finding a contour present inside an element meshing model. That is, contours are supposed to be displayed only on the edges of a meshing model. Therefore, if a contour exists inside a meshing model, this means that there is mismatching between elements in that portion.
Conventionally, contours are substituted by sides (free edges) not shared by a plurality of elements. More specifically, contours are extracted by removing sides shared by two or more elements from all sides constituting all elements.
The conventional method of extracting contours (free edges) will be described below with reference to the flow chart in FIG. 21.
In step S801, an element (Ei) as an object to be checked is set. In step S802, one side of the element is set. In step S803, it is checked whether an element, except for Ei, having the same side as the set side is present. The same side means a side having the same node numbers at its two ends as those of the set side. In step S804, whether the set side is a free edge is checked. If it is determined in step S803 that an element having the same side is present, this side is not a free edge. If there is no element having the same side, this side is a free edge. If the set side is a free edge, the side is registered in a memory in step S805. If the set side is not a free edge, the flow advances to step S806 to proceed on to the next processing.
To perform the above processing for all sides of the element Ei, whether all sides are completely checked is checked in step S806. If NO in step S806, the flow returns to step S802 to set the next side. If YES is determined in step S807, the flow returns to step S801 to perform all these processing steps for all elements. When all elements are completely checked, in step S808 the registered free edges (contours) are displayed on a graphic display.
In this processing, the loop from step S806 to step S802 is repeated the same number of times as the number of sides constituting the element Ei. FIG. 22 shows the numbers of sides of principal three-dimensional elements.
In the processing shown in the flow chart of FIG. 21, the free edge determination in step S803 can be performed within a nearly fixed period of time, independently of the number of elements of a model, by checking only sides having the same sum of node numbers at their two ends as that of the set side. This is described in Japanese Patent Laid-Open No. 4-346178.
The flow chart in FIG. 21 shows that the time required for free edge extraction in this conventional method is directly proportional to the following expression: ##EQU1## where Li is the number of sides of an element Ei and elem is the number of elements.
The procedure of extracting free edges will be described in more detail below with reference to FIG. 21 by using a meshing model shown in FIG. 23.
FIG. 23 is a meshing diagram consisting of four triangular prism elements, in which reference symbols E1 to E4 denote element numbers. Black dots indicate nodes, and the numbers described near these nodes are node numbers. The elements E1 to E4 consist of the following nodes.
E1: n.sub.1 -n.sub.3 -n.sub.4 -n.sub.5 -n.sub.7 -n.sub.8
E2: n.sub.1 -n.sub.2 -n.sub.3 -n.sub.5 -n.sub.6 -n.sub.7
E3: n.sub.5 -n.sub.7 -n.sub.8 -n.sub.9 -n.sub.11 -n.sub.12
E4: n.sub.5 -n.sub.6 -n.sub.7 -n.sub.9 -n.sub.10 -n.sub.11
From this meshing model, free edges are extracted by the following procedure.
(1) An element E1 is set (step S801).
(2) A side n.sub.1 -n.sub.3 of the element E1 is set (step S802).
(3) Whether there is an element having the side n.sub.1 -n.sub.3 is checked (step S803). Since an element E2 has a side consisting of the same nodes, it is determined that the side n.sub.1 -n.sub.3 is not a free edge (step S804).
(4) Since the side n.sub.1 -n.sub.3 is not a free edge, the flow returns from step S806 to step S802, and a new side n.sub.3 -n.sub.4 is set (step S802).
(5) Free edge check is similarly performed for the side n.sub.3 -n.sub.4 (step S803). Since no element having the same side as this is found, it is determined that this side is a free edge (step S804).
(6) The side n.sub.3 -n.sub.4 is registered as a free edge (step S805).
(7) The manipulations (2) to (6) are repetitively executed for all of the remaining sides of the element E1. Consequently, sides n.sub.4 -n.sub.1 and n.sub.4 -n.sub.8 are additionally registered as free edges.
(8) The above operation is performed for the elements E2 to E4 by the loop returning from step S807 to step S801. As a result, nine sides (n.sub.1 -n.sub.2, n.sub.2 -n.sub.3, n.sub.2 -n.sub.6, n.sub.8 -n.sub.12, n.sub.6 -n.sub.10, n.sub.11 -n.sub.12, n.sub.12 -n.sub.9, n.sub.9 -n.sub.10, n.sub.10 -n.sub.11) are additionally registered as free edges.
FIG. 24 is a diagram formed by drawing the free edges extracted by the above operation (step S808). In FIG. 24, lines indicated by the broken lines, as hidden lines, in FIG. 23, are left indicated by the broken lines. A line connecting the nodes n.sub.1 -n.sub.9 and n.sub.3 -n.sub.11 is not displayed even though the line is an edge of the model, but this is not an error but the characteristic feature of a free edge (i.e., a side not shared by a plurality of elements).
In this operation shown in FIG. 21, the loop from step S807 to step S801 is repeated four times, and the loop from step S806 to step S802 is repeated nine times. Therefore, these loops are repeated a total of 36 times (in expression (2), Li is always 9 and the number of elements is 4).
Although the operation for three-dimensional models is described above, contours are similarly effective for two-dimensional finite element models and can be used to increase the display speed and find mismatching between segments. In two-dimensional models, contours indicate boundaries between analytic models (analytic regions). As in the case of three-dimensional models, contours correspond to free edges (sides not shared by a plurality of elements). In three-dimensional models, as illustrated in FIG. 24, there are sides not extracted as free edges although the sides are contours. In two-dimensional models, on the other hand, contours completely agree with free edges. Free edges in two-dimensional models can be extracted following the same procedure as for three-dimensional models shown in the flow chart of FIG. 21.
FIGS. 25A and 25B illustrate an example of extraction of free edges in two-dimensional element meshing models. FIG. 25A shows an element meshing model. This model consists of four quadrangular elements E1 to E4, and the constituent nodes of these elements are as follows.
E1: n.sub.1 -n.sub.8 -n.sub.6 -n.sub.2
E2: n.sub.2 -n.sub.6 -n.sub.7 -n.sub.3
E3: n.sub.4 -n.sub.7 -n.sub.9 -n.sub.5
E4: n.sub.6 -n.sub.8 -n.sub.9 -n.sub.7
Assume that in this model, nodes n.sub.3 and n.sub.4 are supposed to be the same node and an element is missing in a triangular region n.sub.3 -n.sub.4 -n.sub.7 indicated by a hatched region by a data formation error. FIG. 25B shows displayed free edges of this meshing diagram. A contour connecting nodes n.sub.3 -n.sub.4 -n.sub.7 is extracted and thereby mismatching in the element meshing model can be extracted.
In the above description, it is assumed that all elements are objects to be displayed. However, only some elements can be displayed depending on the type of model. That is, if each element has an attribute (e.g., material properties), contours can be extracted by using only elements having some attributes (this applies to the remainder of this specification).
In the above conventional contour extraction method using free edges, however, in the case of three-dimensional models it is in some instances impossible to find mismatching in element meshing contained in an analytic model. This will be described below by using an element meshing model shown in FIG. 26.
FIG. 26 is a meshing diagram consisting of four triangular prism elements, in which reference symbols E1 to E4 denote element numbers. Black dots and the numbers described near these black dots have the same meanings as in FIG. 23. The elements E1 to E4 are triangular prism elements consisting of the following nodes.
E1: n.sub.1 -n.sub.2 -n.sub.4 -n.sub.5 -n.sub.6 -n.sub.8
E2: n.sub.2 -n.sub.3 -n.sub.4 -n.sub.6 -n.sub.7 -n.sub.8
E3: n.sub.5 -n.sub.7 -n.sub.8 -n.sub.9 -n.sub.11 -n.sub.12
E4: n.sub.5 -n.sub.6 -n.sub.7 -n.sub.9 -n.sub.10 -n.sub.11
In this element meshing model, element meshing is mismatched in a face containing nodes n.sub.5 -n.sub.6 -n.sub.7 -n.sub.8. That is, the elements E1 and E2 are meshed by a line connecting nodes n.sub.6 -n.sub.8, but the elements E3 and E4 are meshed by a line connecting nodes n.sub.5 -n.sub.7. Consequently, faces of the elements are discontinuous on a face n.sub.5 -n.sub.6 -n.sub.7 -n.sub.8.
FIG. 27 shows free edges extracted and displayed from the above element meshing model by the conventional method. In FIG. 27, twelve free edges are extracted and displayed. However, all of the free edges displayed in FIG. 27 can be called contours (edges of the meshing model). Accordingly, it is impossible to find mismatching in the meshing model from this free edge diagram. Generally, the conventional method using free edges can find, in the case of a three-dimensional model, missing of elements, floating nodes, and overlapping nodes in the meshing model. However, this conventional method cannot find the discontinuity of faces of elements as described above.
On the other hand, even in two-dimensional models, it is sometimes not possible to find mismatching between elements. As an example, in FIG. 25A, if the element E2 is very small compared to the whole analytic region, particularly if the nodes n.sub.3, n.sub.4, and n.sub.7 are very close to each other, a depression formed by the nodes n.sub.3, n.sub.4, and n.sub.7 of the free edges shown in FIG. 25B becomes very small. As a consequence, this depression can be overlooked in some instances.
(III) Third, in displaying the external shape of a three-dimensional finite element meshing model, the surfaces of the model are often extracted. This is because displaying all elements is time-consuming. That is, the processing time is shortened by displaying only the surfaces of a three-dimensional model by hidden face processing, instead of displaying the whole model as a solid. Generally, the surfaces of a finite element model are the same as faces (to be referred to as free faces hereinafter) not shared by a plurality of elements. Accordingly, the surfaces are extracted by extracting these free faces.
Also, contours of models are often displayed as in the case of display of surfaces. Contours are edges on the surfaces of a model and, more specifically, constituted by sides (boundaries between faces constituting elements) of elements. This is a more simplified display form than the surface display. In a three-dimensional model consisting of n elements, the number of surfaces is the square root of n and the number of contours is the triple root of n if the calculations are done simply. Contours are commonly substituted by sides (free edges) not shared by a plurality of elements.
The characteristic feature of these simplified display methods is to be able to perform display within short time periods. Accordingly, the methods are effective in display in the stage of trial and error for determining a visual point. Also, a number of diagrams must be displayed within short time periods in animation display of time series analytical results, and one conventional method made this performable within a short time by the use of surfaces and contours as described above (Japanese Patent Laid-Open No. b 4-346178).
Contours are also used to find mismatching between elements contained in an element meshing model, e.g., missing of an element (a meshing model is not completely filled with elements), a floating node (a node existing on a side of an element), and overlapping of nodes (two or more nodes are present at the same point). These findings are done by displaying contours to check whether there is a contour present inside a model. That is, contours are supposed to be displayed only on the surfaces of a meshing model, and a contour is formed inside a meshing model due to any of these mismatchings.
As described above, free faces consist of faces of elements, free edges consist of sides of elements, and these faces and sides can be considered as parts constituting elements. Accordingly, these parts will be collectively referred to as segments hereinafter.
Segments such as free faces and free edges can be extracted by removing segments not shared by a plurality of elements. Various algorithms have been proposed as this method of removing shared segments at a high speed. These algorithms will be described below.
The first method is to mesh and group a meshing model into several regions. That is, one rectangular parallelpiped region containing a model is assumed and meshed into several partial regions, and elements inside each partial region and on the boundaries of the region are grouped. To check whether each segment is shared, only segments of elements in the same region (the same group) are checked. This method is effective when elements are uniformly distributed over a region, but the effect is insignificant if elements are concentrated into one portion. Therefore, the method is generally not used frequently.
The second method is an improvement of reducing the time required for one check. This method is described as a method of extracting free faces at a high speed in "Nakada et al.: Improvements in Three-Dimensional Meshing Diagram Formation Algorithm, Japan Simulation Society Ninth Simulation Technology Conference, pp. 61-64 (1990)". That is, this method uses the maximum value of node numbers constituting each segment as an index of the segment and immediately determines that segments are not the same if the indices of these segments disagree. Unfortunately, this method is not frequently used either because the method is not related to the improvement of decreasing the number of checks.
The third method uses the sum of nodes constituting each segment as an index of the segment and, in checking segments, checks only segments having the same index. The algorithm of this method is described as a method of extracting free faces and free edges in Japanese Patent Laid-Open No. 4-346178. This method is being extensively used since programming is easy and the effect is independent of the state of meshing.
FIG. 48 shows a flow chart of this method. A procedure of extracting segments not shared by a plurality of elements will be described below with reference to FIG. 48.
Prior to extracting segments not shared by a plurality of elements, a segment list and an index table are formed (steps B701 and B702). The segment list and the index table will be described next.
The segment list is a list registering all segments and consists of two items, "list number" and "segment node string", as illustrated in FIG. 49A. The list numbers are consecutive integral values starting from 1 and are addresses indicating the row numbers in this list. The segment node string is formed by arranging the numbers of nodes constituting each segment. Accordingly, the segment list in FIG. 29A registers segments of each element independently of those of other elements. Consequently, the number of rows in this list is given by expression (3) below: ##EQU2## where Si is the number of segments constituting the ith element and elem is the number of elements.
The index table consists of "index value" and "list number string" shown in FIG. 49B. The index values correspond to the index numbers of segments and are consecutive integral values starting from 1. These index values are addresses representing the row numbers in this table. The list number strings indicate the list numbers in the segment list. It is necessary to provide the same number of list number strings as the number of segments having the same index value. If the index value of a segment is known, the locations (addresses) in the segment list of segments having this index value can be known by using this table. In this table, it is necessary to provide the same number of rows as the number of possible index values. The maximum value of the sums of node numbers constituting segments is given by expression (4) below: ##EQU3## where N is the number of nodes of a model and m is the number of nodes constituting one segment.
To extract segments, the segment list is formed in step B701 in FIG. 48. This is done by sequentially registering segments of individual elements in the segment list. In step B702, the index values of the individual segments in the segment list formed in step B701 are obtained, and the list numbers in the segment list are registered in the rows of the corresponding index values in the index table. The formation of the segment list and the index table is thus completed.
Segments not shared by a plurality of elements are extracted by removing segments consisting of the same nodes from the list number strings in the index table formed. Steps B703 to B706 indicate a process of removing segments consisting of the same nodes.
In step B703, an index value (k) as a removable object is set. The number of segments registered in the kth row in the index table is checked. If the number is 1 or less, it is determined that this segment is not shared by a plurality of elements, and the flow advances to step B706. If two or more segments having the same index value exist, identical segments (segments consisting of the combination of the same nodes) in the segments in the kth row are removed from the index table in step B705. As described above, nodes constituting each segment can be obtained by referring to the list number in the segment list which corresponds to the list number string. The processing is step B705 is done by comparing the node numbers thus obtained.
In step B706, whether this operation is performed for all index values is checked. If all index values are not completely checked, the flow returns to step B703 to start checking the next index value. If all index values are completely checked, the processing of removing segments shared by a plurality of elements is completed. The segments remaining in the index table at that time are segments not shared by a plurality of elements.
Details of the above operation will be described below by taking extraction of free faces from an element meshing model as an example.
FIG. 50 is a meshing model consisting of two three-dimensional models. In FIG. 50, black dots indicate nodes and the numbers near these nodes indicate node numbers (this holds for the remainder of this specification). Elements E1 and E2 are tetrahedral elements consisting of nodes n.sub.1 -n.sub.2 -n.sub.3 -n.sub.4 and n.sub.3 -n.sub.1 -n.sub.4 -n.sub.5, respectively. The element E1 consists of four faces n.sub.1 -n.sub.2 -n.sub.3, n.sub.1 -n.sub.4 -n.sub.2, n.sub.2 -n.sub.4 -n.sub.3, and n.sub.3 -n.sub.4 -n.sub.1. The element E2 consists of four faces n.sub.3 -n.sub.1 -n.sub.4, n.sub.3 -n.sub.5 -n.sub.1, n.sub.1 -n.sub.5 -n.sub.4, and n.sub.4 -n.sub.5 -n.sub.3.
The process of extracting free faces from this meshing model will be described below with reference to the flow chart in FIG. 48.
(1) In step B701, the constituent nodes of the faces of the element E1 are sequentially registered in the list shown in FIG. 49A. This manipulation is also performed for the faces of the element E2, thereby obtaining a segment list (face list) shown in FIG. 51A.
(2) In step B702, the index value (the sum of the numbers of the nodes constituting a face) of each face in the face list obtained in the above step is calculated, and the list numbers in the face list are registered in the rows of the respective corresponding index values in the index table. An index table shown in FIG. 51B is obtained by registering all faces.
(3) In steps B703, B704, and B705, list numbers indicating overlapping faces (consisting of the same node numbers) are removed from the index table. This is done by removing faces (in the same row of the index table) having the same value and consisting of the combination of the same nodes. In this example, nothing is performed for index values, except index values 8 and 9, because the number of the registered faces is 1 or less in these index values. In each of the index values 8 and 9, however, two faces are registered. Therefore, the node numbers of these two faces are checked (by referring to the list numbers 4 and 5 or 3 and 6), thereby checking whether the two faces are the same. Since both of the two faces of the index value 8 consist of nodes 1, 3, and 4, it is determined that these two faces are the same, and the list numbers 4 and 5 are removed from the index table.
The faces (of list numbers 1, 2, 3, 6, 7, and 8) remaining in the index table after the above processing are free faces.
Extraction of free edges from element meshing models can be accomplished only by replacing faces, in the free face extraction process described above, with sides. The process of extracting free edges from the meshing model in FIG. 50 will be described next.
(1) In step B701 in FIG. 48, the constituent nodes of the sides of the element E1 are sequentially registered in the list shown in FIG. 49A. This manipulation is also performed for the sides of the element E2, thereby forming a segment list (side list) shown in FIG. 52A.
(2) In step B702, the index value (the sum of the numbers of the nodes constituting a side) of each side in this list is calculated, and the list numbers in the side list are registered in the corresponding rows of the index table. An index table in FIG. 52B is obtained by registering all sides.
(3) In steps B703, B704, and B705, list numbers indicating the same side are removed from this index table. In this example, nothing is done for index values 3, 8, and 9 because the number of registered sides is 1 or less in these index values. Since two or more sides are registered in each of index values 4, 5, 6, and 7, the node numbers of sides are checked in each index number to check whether overlapping sides are present. Consequently, it is determined that two sides in each of the index values 4 and 7 and two sides (list numbers 6 and 8) in the index value 5 are the same, and so these list numbers are removed from the index table.
The sides (of list numbers 1, 2, 4, 10, 12, and 11) remaining in the index table after the above processing are free edges.
FIG. 53 is a diagram formed by drawing the free edges thus extracted. In FIG. 53, the broken line indicates a segment indicated by the broken line in FIG. 50.
It is often necessary to know an element inside which a point present in an element meshing model is positioned. This is necessary when the field at that point is to be calculated, and the field at the point can be readily calculated by extracting an element containing the point and analyzing the element.
Conventionally, the extraction of an element including such a point is done by checking whether an element includes the point, and this check is performed for all elements. In the worst case, the check must be performed the number of times corresponding to the number of elements. In the case of a meshing model consisting of n elements, the average number of checks is n2.
Unfortunately, the segment list and the index table used in the conventional method have the drawback that the way these list and table store data is wasteful and in this way they waste memories. This drawback will be described below.
The segment list requires the same number of memories as the number of nodes constituting a segment for each segment. In the case of the face list shown in FIG. 51A, for example, three integral values (node numbers) must be registered for one segment. Accordingly, if the number of nodes constituting a segment is large, a large quantity of memories are required. Also, it is generally necessary to prepare identical number of memories for individual segments for the sake of convenience of a computer. The result is that memories are wastefully used for a segment constituted by a smaller number of nodes than the maximum number of nodes.
In the index table, on the other hand, it is always necessary to prepare larger memories for all index values since the number of segments to be registered for each index value is unknown. In the index table shown in FIG. 51B, for example, memories are so prepared as to be able to register five list numbers for each index value. In effect, however, only a maximum of two (index values 8 and 9) are used. Also, as can be seen from FIG. 51B, the number of segments registered in an index value differs from one index value to another. However, as in the case of segments, it is necessary to prepare identical number of memories for all index values. Consequently, memories are wastefully used for an index value having few segments.
As described above, the conventional method wastes memories. As a consequence, a large amount of memories are required for large-scale models (models having a large number of elements), and so computers incorporating only a small amount of memories cannot process such models.
Assuming, for example, that free faces are extracted from a meshing model consisting of 1,000,000 hexahedral elements and 1,000,000 nodes, memories used by the conventional segment list and index table in this case will be calculated and described in detail below.
First, memories required by the face list are calculated. Since faces constituting each element are quadrangles, segment information requires memories corresponding to four integers (16 bytes if 4 bytes are necessary for each integer; this holds for the remainder) per segment. The number of rows in the list is 6,000,000 from expression (3) because one element consists of six faces. Accordingly, 96M (16.times.6,000,000) bytes of memories are required for the segment list.
Memories necessary for the index table are calculated next. The present inventors experientially know that the maximum number of segments having the same index value is usually 8 to 10 in one meshing model. Therefore, if this table is allowed to register up to 10 segments (faces) having the same index value, 40 bytes (4 bytes.times.10) of memories are used per index value. The number of rows in the table is approximately 4,000,000 (accurately (4,000,000-3)). Accordingly, approximately 160 Mbytes (40.times.4,000,000) of memories are required for the index table.
As a result, a total of 256 Mbytes (96M+160M) of memories are necessary for this meshing model. This memory capacity is large even for present computers, and so general computers cannot process this model.
Also, the conventional index table can no longer perform processing if the number of segments having the same index value exceeds a limiting range. For example, the index table shown in FIG. 51B becomes unable if the number of segments having the same index value is 6 or more. This conflicts with the above explanation that the maximum number of segments having the same index value is 8 to 10. However, the case explained above is merely a general case and based on the fact that 10 or more segments are possible.
The conventional method of displaying free edges in place of contours also has the drawback that a line which is supposed to be displayed as a contour is not displayed. As an example, in the contours illustrated in FIG. 53, lines consisting of nodes n.sub.1 -n.sub.4, n.sub.4 -n.sub.3, and n.sub.3 -n.sub.1 are not displayed even though these lines should be displayed because they are the edges of the model.
Moreover, in the conventional method of extracting an element including a point, it is necessary to check whether an element includes a point for all elements. Accordingly, if a large number of points exist, a long time is required for the extraction.
SUMMARY OF THE INVENTION
As described above, the conventional method of item (1) above has the drawback that it is difficult to reliably detect errors in element meshing data even by paying close attention and using much labor to perform the error detection.
The present invention has been made in consideration of the above problem and has as its object to easily find and classify errors in element meshing data and automatically correct some errors.
To achieve the above object, the present invention checks the following three items for all nodes.
(1) The number of elements sharing boundaries between elements (to be referred to as surrounding elements hereinafter) which surround a node.
(2) The total sum of the angles of the surrounding elements around the node.
(3) If boundary faces each consisting of only one element (these faces will be called free faces hereinafter) are extracted from the boundaries between the surrounding elements, whether all these free faces connect to each other through sides (only in the case of a three-dimensional model).
Also, a maximum angle .phi..sub.max and a minimum angle .phi..sub.min of the external shape of an analytic model are used as input data for the check.
Of the above three items, the position of each node in an analytic model is known by items (1) and (2). If the results in the two methods are conflicting, it is determined that there is an error in a part of an element constituted by this node. Also, an error in the external shape of a three-dimensional model is found by item (3). If an outline having an angle outside the range of the maximum angle .phi..sub.max and the minimum angle .phi..sub.min of the external shape of an analytic model is found when these angles are used as input data, this portion is regarded as an error. That is, the standards of error determination can be changed in accordance with the type of an alytic model.
Also, the present invention has been made to solve the problem of item (2) above and has as its object to provide a method and apparatus for extracting contours and vertices from finite element meshing models, which can readily find the discontinuity (including very small errors in a two-dimensional model) of faces of elements in a three-dimensional model and mismatching between the elements.
To achieve the above object, a method of extracting a contour from a finite element meshing model according to the present invention comprises the steps of extracting a free face not shared by a plurality of elements from a three-dimensional finite element meshing model, and extracting a contour by using data of the extracted free face.
A method of extracting a contour and a vertex from a finite element meshing model according to the present invention comprises the steps of extracting a free face not shared by a plurality of elements from a three-dimensional finite element meshing model, extracting a contour by using data of the extracted free face, and extracting a vertex by using data of the extracted contour.
In the free face extraction step, a free face is extracted from an element by checking, for all faces of the element, whether a face of the element is shared by another element, in the contour extraction step, whether two faces having one side of an element as sides thereof are extracted as free faces is checked, and, if both of the two faces are extracted as free faces, it is determined that the side is a contour, and in the vertex extraction step, whether a side having one node of each element as an end point thereof is extracted as a contour is checked, and, if all of the sides are extracted as contours, it is determined that the node is a vertex.
In the contour extraction step, if the number of free faces extracted from one element is not more than 1, it is determined that all sides of the element are not contours. In the vertex extraction step, if the number of contours extracted from one element is 2 or less, it is determined that all nodes of the element are not vertices.
The method further comprises the step of extracting overlapping contours, nodes at two ends of which have the respective same node numbers, from the extracted contours, and using the overlapping of the contours in checking mismatching between elements in the element meshing model. The method further comprises the step of checking a meshing model by displaying vertices in a diagram which displays contours or free edges of the model.
A method of extracting a vertex from a finite element meshing model according to the present invention comprises the steps of extracting a free edge from a two-dimensional finite element meshing model, and obtaining a vertex from data of the extracted free edge.
In the free edge extraction step, a free edge of one element is extracted by checking, for all sides of the element, whether a side of the element is shared by another element, and in the vertex extraction step, whether two sides having one node of each element as end points thereof are free edges is checked, and, if both of the two sides are free edges, it is determined that the node is a vertex. In the vertex extraction step, if the number of free edges extracted from one element is 1 or less, it is determined that all nodes of the element are not vertices. The method further comprises the step of checking a meshing model by displaying vertices in a diagram which displays contours or free edges of the model.
An apparatus for extracting a contour from a finite element meshing model according to the present invention comprises free face extracting means for extracting a free face from an element by checking, for all faces of the element, whether a face of the element is shared by another element, first contour determining means for determining that all sides of an element are not contours, if the number of free faces extracted from the element is 1 or more, and second contour determining means for checking, if the number of free faces extracted from one element is 2 or more, whether two faces having one side of the element as sides thereof are extracted as free faces, and, if both of the two faces are extracted as free faces, determining that the side is a contour. The apparatus further comprises mismatching checking means for extracting overlapping contours, nodes at two ends of which have the respective same node numbers, from the extracted contours, and checking mismatching between elements in the element meshing model on the basis of the overlapping of the contours.
An apparatus for extracting a contour and a vertex from a finite element meshing model according to the present invention comprises free face extracting means for extracting a free face from an element by checking, for all faces of the element, whether a face of the element is shared by another element, first contour determining means for determining that all sides of an element are not contours, if the number of free faces extracted from the element is 1 or less, second contour determining means for checking, if the number of free faces extracted from one element is 2 or more, whether two faces having one side of the element as sides thereof are extracted as free faces, and, if both of the two faces are extracted as free faces, determining that the side is a contour, first vertex determining means for determining that all nodes of an element are not vertices, if the number of contours extracted from the element is 2 or less, and second vertex determining means for checking, if the number of contours extracted from one element is 3 or more, whether a side having one node of the element as an end point thereof is extracted as a contour, and, if all the sides are extracted as contours, determining that the node is a vertex. The apparatus further comprises meshing model checking means for checking a meshing model by displaying vertices in a diagram which displays contours or free edges of the model.
An apparatus for extracting a vertex from a finite element meshing model according to the present invention comprises free edge extracting means for extracting a free edge from an element by checking, for all faces of the element, whether a face of the element is shared by another element, first vertex determining means for determining that all nodes of an element are not vertices, if the number of free edges extracted from the element is 1 or less, and second vertex determining means for checking, if the number of free edges extracted from one element is 2 or more, whether two sides having one node of the element as end points thereof are extracted as free edges, and, if both of the two edges are extracted as free edges, determining that the node is a vertex. The apparatus further comprises meshing model checking means for checking a meshing model by displaying vertices in a diagram which displays contours or free edges of the model.
In the above arrangements, attention is focused on information of surfaces (free faces) of an element meshing model. If faces adjacent to each other in one element are free faces, both of the two faces are necessarily contours of the analytic model. Accordingly, contours are obtained even for a portion in which faces of elements are discontinuous. Also, in the present invention, vertices are supposed to be positioned at corners of contours. Therefore, if a vertex is positioned in some other portion, this indicates that there is mismatching between elements in this portion of the vertex.
The present invention also has been made to solve the problem of item (3) above and has as its object to provide a method and apparatus for extracting sides, faces, and elements from finite element meshing models, which can extract segments from large-scale meshing models even by using computers incorporating only a small amount of memories, which can faithfully display contours, and which can extract an element including an arbitrary point in a model at a high speed.
To achieve the above object, a method of extracting a side, a face, or an element from finite element meshing data according to the present invention, in which if elements and nodes constituting the elements are so stored as to correspond to each other, one side, face, or element is regarded as one segment, and the segment is extracted from a finite element meshing model, comprising the steps of assigning to each segment an index value characterizing a combination of nodes constituting the segment, forming a segment list in which pieces of information of segments having the same index value are consecutively arranged and an index table showing a relationship between the index values and positions in the segment list, and extracting segments having the same index value on the basis of the segment list and the index table, thereby obtaining information of nodes constituting the extracted segments.
The information stored in the segment list is expressed by a first identifier which specifies an element having each segment and a second identifier which indicates the ordinal number of the segment in the element. The segments stored in the segment list are arranged in decreasing or increasing order of index value. The first identifier is multiplied by a predetermined integral value equal to or larger than the number of segments constituting one element, and the second identifier is added to the product, thereby storing the first and the second identifiers as one integral value. The information of each index value in the index table is expressed by the number of segments corresponding to the index value and a pointer indicating a first position in the segment list from which the segments are stored. The pointer is multiplied by an integral value equal to or larger than 10, and the number of segments is added to the product, thereby storing the number and the pointer as one integral value.
The method further comprises the step of extracting a plurality of elements, as adjacent elements, constituted by segments consisting of the same nodes among other extracted segments. The method further comprises the step of removing segments consisting of the same nodes from the segment list, thereby allowing only segments not overlapping each other to remain in the segment list.
A method of extracting an element including a point P.sub.e in a finite element meshing model according to the present invention comprises the steps of obtaining, starting from a known point P.sub.0 included in a given element E.sub.0, a face F.sub.0 of the element E.sub.0 which intersects a line segment connecting two points P.sub.e and P.sub.0, obtaining an element E.sub.1 adjacent to the element E.sub.0 through the face F.sub.0 as a boundary, obtaining a face F.sub.1, other than the face F.sub.0, of the element E.sub.1, which intersects the line segment connecting the points P.sub.e and P.sub.0, repeating processing of obtaining an element E.sub.2 adjacent to the element E.sub.1 through the face F.sub.1, and extracting an element including the point P.sub.e by tracing the adjacent elements.
A method of extracting a side from a finite element meshing model according to the present invention comprises the steps of extracting free faces from a three-dimensional finite element model, regarding the free faces as shell-like, two-dimensional elements and extracting adjacent two-dimensional elements, calculating an angle .theta. formed by the adjacent two-dimensional elements, and extracting a boundary between the two two-dimensional elements as a contour if a value of the angle .theta. satisfies 0.ltoreq..theta.<(.pi.-.differential.) or (.pi.+.differential.)<.theta.<2 .pi. where .differential. is a tolerance. The method further comprises the step of adding a three-dimensional meshing model consisting of shell-like, two-dimensional elements to the extracted free faces and extracting adjacent two-dimensional elements, wherein a boundary between the two two-dimensional elements is extracted as a contour if a value of the angle .theta. satisfies .differential..ltoreq..theta.<(.pi.-.differential.) or (.pi.+.differential.)<.theta.<2 .pi.-.differential. where .differential. is a tolerance.
An apparatus for extracting a side, a face, or an element from finite element meshing data according to the present invention comprises means for storing elements and nodes constituting the elements so that the elements and the nodes correspond to each other, means for regarding one side, face, or element as one segment and assigning to each segment an index value characterizing a combination of nodes constituting the segment, means for forming a segment list in which pieces of information of segments having the same index value are consecutively arranged and an index table showing a relationship between the index values and positions in the segment list, and means for extracting segments having the same index value on the basis of the segment list and the index table and obtaining information of nodes constituting the extracted segments on the basis of a correspondence between each element and the nodes constituting the element.
The information stored in the segment list is expressed by a first identifier which specifies an element having each segment and a second identifier which indicates the ordinal number of the segment in the element. The segments stored in the segment list are arranged in decreasing or increasing order of index value. The first identifier is multiplied by a predetermined integral value equal to or larger than the number of segments constituting one element, and the second identifier is added to the product, thereby storing the first and the second identifiers as one integral value. The information of each index value in the index table is expressed by the number of segments corresponding to the index value and a pointer indicating a first position in the segment list from which the segments are stored. The pointer is multiplied by an integral value equal to or larger than 10, and the number of segments is added to the product, thereby storing the number and the pointer as one integral value.
In the above arrangements, in the segment list, each segment is expressed by two items, the element number and the local segment number, regardless of the number of constituting nodes. Also, the index table is expressed by two items, the number of corresponding segments and the first list number, regardless of the number of segments having the same index value. As a result, in the segment list and the index table only two integers of memories are consumed per segment and per index value, respectively. This makes effective use of memories feasible. Additionally, since contours are extracted as edges between free faces, all contours are extracted without any omission. Furthermore, an element including a point is extracted by tracing adjacent elements. Therefore, an element of interest can be reached by advancing retrieval almost linearly and hence is reached within a short time period.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a flow chart for explaining the flow of the first embodiment of the present invention;
FIG. 2 is an element meshing diagram for explaining details of the process flow in the first embodiment of the present invention;
FIGS. 3A to 3D are views for explaining details of the process flow in the first embodiment of the present invention;
FIG. 4A is a flow chart for explaining the flow of the second embodiment of the present invention;
FIG. 4B is a flow chart for explaining the flow of the second embodiment of the present invention;
FIG. 5 is an element meshing diagram for explaining details of the process flow in the second embodiment of the present invention;
FIGS. 6A to 6D are views for explaining details of the process flow in the second embodiment of the present invention;
FIGS. 7A to 7D are views for explaining details of the process flow in the second embodiment of the present invention;
FIG. 8A is a block diagram showing the configuration of a computer system which realizes the first and second embodiments;
FIG. 8B is a view showing an example of the configuration of an external storage medium used when data and programs are loaded in a RAM 173 in FIG. 8A;
FIGS. 9A to 9F are views showing examples of errors in meshing diagrams of two-dimensional models;
FIGS. 10A to 10H are views showing examples of errors in meshing diagrams of three-dimensional models;
FIG. 11 is a flow chart for explaining a conventional algorithm for detecting errors in element meshing data in a two-dimensional model and the problem of the algorithm;
FIG. 12 is a view comparing the repeating number of data error detection in a conventional method with that in the present invention;
FIG. 13 is a view for explaining the process flow of a conventional element meshing data error detection method and the problem of the method;
FIG. 14 is a flow chart showing the process flow in the third embodiment of the present invention;
FIG. 15 is a view showing the processing result in the third embodiment of the present invention;
FIG. 16 is a flow chart showing the process flow in the fourth embodiment of the present invention;
FIG. 17 is a flow chart showing the process flow in the fifth embodiment of the present invention;
FIG. 18 is a flow chart showing the process flow in the sixth embodiment of the present invention;
FIG. 19 is a view showing one application of the sixth embodiment of the present invention;
FIG. 20A is a block diagram showing the configuration of a computer in this embodiment;
FIG. 20B is a view showing an example of the configuration of an external storage medium used when data and programs are loaded in a RAM 73 in FIG. 20A;
FIG. 21 is a flow chart for explaining a conventional process flow;
FIG. 22 is a view for explaining the repeating number;
FIG. 23 is a view for explaining an actual finite element meshing model;
FIG. 24 is a view for explaining an actual finite element meshing model;
FIGS. 25A and 25B are views for explaining an actual finite element meshing model;
FIG. 26 is a view for explaining an actual finite element meshing model;
FIG. 27 is a view for explaining an actual finite element meshing model;
FIG. 28 is a flow chart showing the process flow in the seventh embodiment;
FIG. 29 is a flow chart showing a detailed process flow in A101 in FIG. 28;
FIG. 30 is a flow chart showing a detailed process flow in A102 in FIG. 28;
FIG. 31 is a flow chart showing a detailed process flow in A103 in FIG. 28;
FIGS. 32A and 32B are views showing the formats of a list and a table formed during the processing in the seventh embodiment;
FIG. 33 is a view for explaining segments in the seventh embodiment;
FIGS. 34A and 34B are views for explaining segments in the seventh embodiment;
FIG. 35 is a view for explaining practical processing when segments are faces in the seventh embodiment;
FIGS. 36A and 36B are views for explaining practical processing when segments are faces in the seventh embodiment;
FIG. 37 is a view for explaining practical processing when segments are sides in the seventh embodiment;
FIGS. 38A and 38B are views for explaining practical processing when segments are sides in the seventh embodiment;
FIG. 39 is a flow chart showing the process flow in the eighth embodiment;
FIG. 40 is a view for explaining practical processing when segments are faces in the eighth embodiment;
FIGS. 41A and 41B are views for explaining practical processing when segments are faces in the eight embodiment;
FIG. 42 is a flow chart showing the process flow in the ninth embodiment;
FIG. 43 is a flow chart showing the process flow in the tenth embodiment;
FIG. 44 is a view showing practical processing in the tenth embodiment;
FIGS. 45A and 45B are views for explaining practical processing in the tenth embodiment;
FIGS. 46A and 46B are views for explaining the eleventh embodiment;
FIG. 47A is a block diagram showing the configuration of a computer which realizes this embodiment;
FIG. 47B is a view showing an example of the configuration of an external storage medium used when data and programs are loaded in a RAM 163 in FIG. 47A;
FIG. 48 is a flow chart for explaining one prior art;
FIGS. 49A and 49B are views showing the formats of a list and a table formed during the processing in the prior art;
FIG. 50 is a view for explaining practical processing in the prior art;
FIGS. 51A and 51B are views for explaining practical processing when segments are faces in the prior art;
FIGS. 52A and 52B are views for explaining practical processing when segments are sides in the prior art; and
FIG. 53 is a view for explaining the result of practical processing in the prior art.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
The characteristic features of the present invention will become apparent by the following description of several preferred embodiments of the invention. Note that the present invention is not limited to these embodiments and also contains combinations of the embodiments.
FIG. 8A is a block diagram showing the configuration of a computer for effectuating the first and second embodiments. In FIG. 8A, the computer comprises a display unit 171 such as a graphic display (CRT or FLCD); a CPU 172 for controlling arithmetic operations; a RAM 173 as an auxiliary storage. The RAM 173 has an area 173a for storing data of finite element meshing models, an area 173b for storing a table formed in accordance with the correspondence of surrounding elements (sides and faces) of nodes or sides, and an area 173c used when programs are externally downloaded. An input unit 174 is a keyboard or a pointing device which inputs data and operation instructions, or an interface for a floppy disk drive or a communication device which inputs data of finite element meshing models or programs. A ROM 175 stores control procedures of the CPU 172. The CPU 172 processes input data from the input unit 174 in accordance with the procedures stored in the ROM 175 or with programs loaded from the input unit 174 into the RAM 173, and displays the result on the display unit 171. FIG. 8B shows the configuration of an external storage medium 170 such as a floppy disk. This external storage medium 170 has a directory 170a, a finite element meshing model storage area 170b, and a program storage area 170c including a surrounding element count module and an element meshing error detection module.
(First Embodiment)
As the first embodiment of the present invention, a case in which the present invention is applied to a two-dimensional model will be described below.
FIGS. 1 to 3D are views for explaining this embodiment. FIG. 1 is a flow chart for finding errors in an element meshing diagram. In FIG. 1, reference symbols P1, P2, . . . denote processes; n.sub.n, the total number of nodes; r.sub.j and r.sub.n, the numbers of rows in tables shown in FIGS. 3A to 3D; and E.sub.n and l.sub.i, the repeating numbers of elements and sides, respectively, as in FIG. 11. Note that in FIG. 1, a new element setting process and a new node setting process in each repetition which correspond to processes R1 and R2 in FIG. 11 are omitted. FIGS. 2 to 3D are views for explaining details of the process flow in FIG. 1. FIG. 2 is an element meshing diagram taken as an example, and FIGS. 3A to 3D illustrate a process of forming tables in process P1 in FIG. 1 in the element meshing diagram in FIG. 2. In FIGS. 2 to 3D, an element E.sub.1 and a node n.sub.0, for example, are the same as the element E.sub.1 and the node n.sub.0 in FIGS. 9A to 9F. In the tables shown in FIGS. 3A to 3D, the columns "node n.sub.i " and "node n.sub.j " show the numbers of nodes directly connecting to the node n.sub.0 through sides n.sub.0 n.sub.i and n.sub.0 n.sub.j of the element E.sub.n having the node n.sub.0 as its constituent node. The columns "side n.sub.0 n.sub.i " and "side n.sub.0 n.sub.j " show the numbers of appearances of these sides. The numerical values shown in FIGS. 3A to 3D are stored in the area 173b in FIG. 8A.
The element meshing diagram around the node n.sub.0 is checked by the process, shown in the flow chart of FIG. 1, for finding errors in an element meshing diagram.
›Process P1!
In process P1, the number of elements having boundaries (to be referred to as surrounding sides hereinafter) of elements surrounding the node n.sub.0, FIG. 2, as their own sides, is counted. This manipulation is done by performing the processing explained below and forming a table P1-(4) in FIG. 3D.
P1- (1)
The element E.sub.1 having the node n.sub.0 as its constituent node is extracted, and numbers n.sub.1 and n.sub.2 of two nodes directly connecting to n.sub.0 through sides are stored in the columns "n.sub.i " and "n.sub.j ", respectively. Also, information indicating that sides n.sub.0 n.sub.j and n.sub.0 n.sub.2 have appeared once is stored in the columns "side n.sub.0 n.sub.j " and "side n.sub.0 n.sub.j ", respectively, thereby obtaining a table P1-(1) in FIG. 3A.
P1-(2)
The second element E.sub.2 having the node n.sub.0 as its constituent node is extracted, and numbers n.sub.2 and n.sub.3 of two nodes directly connecting to n.sub.0 through sides are added to the columns "n.sub.i " and "n.sub.j ", respectively. Whether sides n.sub.0 n.sub.2 and n.sub.0 n.sub.3 have already appeared is checked by checking the elements previously stored in this table, i.e., the element E.sub.1 stored in P1-(1) (therefore, r.sub.j =1 in FIG. 1). Since the side n.sub.0 n.sub.2 has appeared once, 2 and 1 are stored. At the same time, the column of the number of appearances of the side n.sub.0 n.sub.2 of the element E.sub.1 is rewritten by 2. The result is a table P1-(2) in FIG. 3B.
P1-(3)
The third element E.sub.3 having the node n.sub.0 as its constituent node is extracted, and numbers n.sub.3 and n.sub.4 of two nodes directly connecting to n.sub.0 through sides are added to the columns "n.sub.i " and "n.sub.j ", respectively. Whether sides n.sub.0 n.sub.3 and n.sub.0 n.sub.4 have already appeared is checked by checking the elements previously stored in this table, i.e., the elements E.sub.1 and E.sub.2 (r.sub.j =2). Since the side n.sub.0 n.sub.3 has appeared once as a side of E.sub.2, 2 and 1 are stored. At the same time, the column of the number of appearances of the side n.sub.0 n.sub.3 of the element E.sub.2 is rewritten by 2. Consequently, a table P1-(3) in FIG. 3C is obtained.
P1-(4)
The above operation is repeatedly executed for all elements having the node n.sub.0 as their constituent nodes. The result is P1-(4) in FIG. 3D. Note that in FIG. 1, r.sub.n indicates the number of rows (in this embodiment r.sub.n =5) in the final table.
›Process P2!
In process P2, the internal angles around the node n.sub.0 of the surrounding elements are added to obtain a total sum .phi.. That is, the total sum .phi. of the internal angles in FIG. 2 is given by the following equation:
.phi.=.phi..sub.1 +.phi..sub.2 +.phi..sub.3 +.phi..sub.4 +.phi..sub.5 (=2 .pi.) (5)
Note that this process of adding the internal angles can be performed rapidly when it is done during the repetition of E.sub.n as in process P1 as illustrated in FIG. 1.
›Process P3!
In process P3, the numbers of appearances (the columns "side n.sub.0 n.sub.i " and "side n.sub.0 n.sub.j " in P1-(4) in FIG. 3D) of surrounding sides are checked from P1-(4) (FIG. 3D) formed in process P1, and are classified into four categories below:
(1) The number of appearances of a surrounding side is "0", i.e., P1-(4) in FIG. 3D has no row (r.sub.n =0)
(2) "3" or more is present as the number of appearances of a surrounding side.
(3) "1" is present as the number of appearances of a surrounding side.
(4) All numbers of appearances of surrounding sides are "2".
In the case of item (3) above, the number of surrounding sides which appear once are simultaneously counted.
The element meshing diagram in FIG. 2 corresponds to (4).
If this processing corresponds to item (2) above, the operation can escape the repetition during the course of the processing. Therefore, as illustrated in FIG. 1, the processing is completed when repeated to the row number r.sub.n in P1-(4) of FIG. 3D.
›Process P4!
In process P4, item (1) classified in process P3 is branched.
If the number of appearances of a surrounding side is "0" (i.e., if n.sub.0 surrounding side exists), this means that the node n.sub.0 is a floating node. Accordingly, the flow advances to process P41 to output a message indicating that this node is a floating node and proceeds on to a check of the next node.
›Process P5!
In process P5, item (2) classified in process P3 is branched.
That is, the presence of a surrounding side which appears three times or more indicates that some surrounding elements of the node n.sub.0 overlap each other. The error explained earlier in FIG. 9A is found by performing this check for nodes indicated by the black dots in FIG. 9A (each black dot in FIGS. 9A to 10H indicate a node at which an error can be found). The flow branches to process P51 to output a message indicating that there are overlapping elements and proceeds on to a check of the next node.
›Process P6!
In process P6, item (3) classified in process P3 is branched.
That is, the presence of a surrounding side which appears only once shows that the node n.sub.0 is positioned on the outer circumference of the analytic model and this surrounding side appearing once is an outline. Accordingly, the flow advances to process P61 to check the number (already counted in process P3) of surrounding sides whose number of appearances is "1", thereby confirming that the number is "2". If the number is other than "2", this indicates that this analytic model has a constricted part shown in FIG. 9F. Therefore, a message indicating this information is output in process P64, and the flow advances to a check of the next node.
If the number of surrounding sides whose number of appearances is "1" is 2 in process P61, the sum .phi. of the internal angles around the node n.sub.0 is checked in process P62. If .phi. falls outside the range of the maximum angle .phi..sub.max and the minimum angle .phi..sub.min of the external shape of the analytic model given by the analyst, this means that there is an error shown in FIG. 9C, 9D, or 9E. Accordingly, a message indicating this information is output in process P63, and the flow advances to a check of the next node.
If .phi. is within the range of the data given by the analyst, no problem arises and hence the flow directly advances to a check of the next node.
›Process P7!
In process P7, item (4) classified in process P3 is processed.
That is, when all numbers of appearances of surrounding sides are "2", the node n.sub.0 is positioned inside the analytic model. Therefore, in process P7 whether the sum of the internal angles around the node is 2 .pi. (radian) is checked. If the sum is not 2 .pi., there is an error shown in FIG. 9B. Accordingly, a message indicating this error is output in process P71. If the sum is 2 .pi., the flow directly advances to a check of the next node because there is no problem. In the case of the meshing diagram shown in FIG. 2, it is determined in this processing that there is no abnormality in elements around the node n.sub.0.
Processes P1 to P7 explained in FIG. 1 are repetitively executed for all nodes.
In this processing, if the number of sides constituting one element is held constant at l.sub.n n, the total repeating number is approximated by the following expression:
n.sub.n .times.r.sub.n .times.(E.sub.n .times.l.sub.n /2+1)(6)
Assume that n.sub.n is E.sub.n /2 and r.sub.n is 6 in a triangular element and n.sub.n is E.sub.n and r.sub.n is 4 in a quadrangular element. In this case, if an element meshing diagram consists only of triangular elements (l.sub.n =3) and quadrangular elements (l.sub.n =4), the total repeating numbers in this embodiment are as illustrated in the rows of "two-dimensional model" in FIG. 12.
If .phi. in process P62 is within the range of data given by the analyst, surrounding sides whose number of appearances is "1" represent the outlines of the analytic model. Therefore, the check can be performed more reliably when it is done by graphically displaying these surrounding sides.
In this embodiment, various errors in an element meshing diagram are found and the corresponding messages are output. However, it is also possible to automatically make corrections for the following items.
(1) In process P41, erase a node to which a message indicating a floating node is output.
(2) In proces |
