System for conversion between the boundary representation model and a constructive solid geometry model of an object

• US 4,736,306 A
• Filed: 04/29/1985
• Issued: 04/05/1988
• Est. Priority Date: 04/29/1985
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Department of Energy
• Inventors: Emery, James D., Smith, Maurice L., Christensen, Noel C.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/728,367
• Time in Patent Office: 1,072 Days
• Field of Search: 364/513, 364/200 MS File, 364/900 MS File, 364/474, 364/191-193, 364/171, 364/188, 364/521, 364/522, 364/475
• US Class Current: 345/420
• CPC Class Codes: G05B 19/4097 characterised by using design data to control NC machines, e.g. CAD/CAM G05B19/4093 takes precedence
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: Y10S 706/92 Simulation

Abstract

A system converts from the boundary representation of an object to the constructive solid geometry representation thereof. The system converts the boundary representation of the object into elemental atomic geometrical units or I-bodies which are in the shape of stock primitives or regularized intersections of stock primitives. These elemental atomic geometrical units are then represented in symbolic form. The symbolic representations of the elemental atomic geometrical units are then assembled heuristically to form a constructive solid geometry representation of the object usable for manufacturing thereof. Artificial intelligence is used to determine the best constructive solid geometry representation from the boundary representation of the object. Heuristic criteria are adapted to the manufacturing environment for which the device is to be utilized. The surface finish, tolerance, and other information associated with each surface of the boundary representation of the object are mapped onto the constructive solid geometry representation of the object to produce an enhanced solid geometry representation, particularly useful for computer-aided manufacture of the object.

Claims

1. A method of manufacturing an object from a boundary representation thereof comprising:

cleaving said boundary representation of said object, which represents said object only by zero, one or two dimensional features thereof, into elemental atomic geometrical units;

assembling said I-bodies into assemblies having atomic geometrical forms which collectively form a constructive solid geometry representation of said object usable for manufacturing thereof;

utilizing said constructive solid geometry representation of said object to develop machine instructions for instruction one or more machines in a manufacturing process; and

controlling said machines to perform operations under control of said instructions to manufacture at least a portion of said object.

2. The method of claim 1 further comprising the step of representing said I-bodies in symbolic form;

said step of assembling utilizing the symbolic forms of said I-bodies.

3. The method of claim 2 wherein said step of representing comprises:

representing each I-body as a plurality of atomic constituent facts;

mapping said atomic constitutent facts so as to interrelate said facts, said facts describing said I-body in symbolic form.

4. The method of claim 1 wherein said step of cleaving utilizes sectioning surfaces to divide said object into I-bodies.

5. The method of claim 1 wherein said step of cleaving defines said I-bodies with the intersection of half-spaces, said half-spaces being formed by:

representing extended surfaces of said object which do not intersect a portion of the described volume of said object as grazing surfaces;

representing all other extended surfaces of said object as sectioning surfaces;

converting said grazing surfaces into half-spaces by providing a representation associated with each said grazing surface specifying which side of said surface said object resides;

defining the material to remove from said enclosing body;

sectioning said object with all intersecting said sectioning sufaces to form positive elemental atomic geometrical units (I-bodies);

sectioning said material to be removed with all intersecting said sectioning surfaces to form negative elemental atomic geometrical units or (I-bodies).

6. The method of claim 1 further comprising:

transferring information contained in the boundary representation of said object to said constructive solid geometry representation.

7. The method of claim 6 wherein said information is selected from a group consisting of volume, surface area of faces of said object, parallelism of face surfaces, face surface finish, face surface treatment and hole threading information.

8. The method of claim 1 wherein said step of cleaving comprising:

representing extended surfaces of said object which do not intersect a portion of the described volume of said object as grazing surfaces;

representing all other extended surfaces of said object as sectioning surfaces;

converting said grazing surfaces into half-spaces by providing a representation associated with each said grazing surface specifying which side of said surface said object resides;

forming an enclosing body from the intersection of said half-spaces;

subtracting the object represented by said boundary representation from said enclosing body to define the material to remove;

sectioning said object with all intersecting said sectioning surfaces to form positive atomic geometrical unit (I-bodies);

identifying each surface of each said positive I-body as a unique facelet shared only by an adjacent atomic geometrical unit;

sectioning said material to be removed with all intersecting said sectioning surfaces to form negative atomic geometrical units (I-bodies); and

identifying each surface of each said negative I-body as a unique facelet shared only by an adjacent atomic geometrical unit.

9. The method of claim 8 wherein an I-group is a elemental geometric unit or shape which is the union of a set of non-overlapping I-bodies, said step of assembling comprising:

initially utilizing an enclosing I-group as a possible solution to begin assembly evaluation;

searching said possible solution for all pure positive I-groups;

deleting any pure negative I-groups in said possible solution to redefine said possible solution;

replacing any mixed I-group with a set of possible construction choices;

said possible construction choices being heuristically determined;

looking ahead to future recursions of said steps of searching, deleting and replacing for each of said possible construction choices to determine their relative feasilibity;

heuristically determining the best possible construction choices;

making said best possible construction choices newly selected possible solutions;

developing a constructive solid geometry solution by;

recursively repeating said steps of searching, deleting, replacing, looking ahead and heuristically determining on said newly selected possible solutions until said step of searching detects all pure positive I-groups indicating a solution has been reached.

10. The method of claim 9 wherein said step of searching includes replacing each said pure positive I-group with an intersection of half-spaces repesentation;

said step of developing further comprising converting said half-space representations developed by said step of replacing into constructive solid geometry solutions subsequent to said step of recursively repeating.

11. The method of claim 1 wherein an I-group is a non-elemental geometric unit or shape which is the union of a set of non-overlapping I-bodies;

said step of assembling comprising;

initially utilizing an enclosing I-group defining a possible solution comprising the set of all positive I-bodies and all negative I-bodies to begin assembly evaluation;

searching said possible solution for all pure positive I-groups;

deleting any pure negative I-groups in said possible solution to redefine said possible solution;

replacing any mixed I-group with a set of possible construction choices,;

heuristically determining the best possible construction choices of said set based upon a particular user'"'"'s manufacturing capabilities;

making said best possible construction chocies newly selected possible solutions; and

developing a constructive solid geometry solution by recursively repeating said steps of searching, deleting, replacing, and heuristically determining on said newly selected possible solutions until said step of searching detects all pure positive I-groups, thereby indicating a solution has been reached.

12. The method of claim 11 wherein said step of searching includes replacing all said pure positive I-groups with intersection of half-space representations;

said step of developing further comprising converting said half-space representations developed by said step of replacing into constructive solid geometry solutions subsequent to said step of recursively repeating.

13. The method of claim 11 wherein said step of searching further includes looking ahead to further recursions of said steps of searching, deleting and replacing for each of said possible construction choices to determine their relative feasibility.

14. The method of claim 11 wherein each possible solution has at most a single mixed I-group contained therein including both positive and negative I-bodies.

15. The method of claim 14 wherein said step of replacing includes developing a total minus negatives possible construction choice including:

(a) identifying each I-body within the mixed I-group of said possible solution;

(b) identifying a negative I-body within said mixed I-group;

(c) finding all negative I-bodies within said mixed I-group connected to said identified negative I-body;

(d) forming a complete I-group by adding I-bodies to said connected negative I-bodies, said I-group being defined by the surfaces grazing said connected negative I-bodies;

(e) subtracting said completed I-group developed by step (d) from mixed I-group;

(f) repeating steps b-e with said remaining mixed I-group until all negative I-bodies are part of a completed I-group to form said total minus negatives possible constructions choice.

16. The method of claim 15, wherein said step of forming includes the steps of:

locating missing facelets of said complete I-group;

determining if any I-bodies within said complete I-group are missing from said set of connected negative I-bodies using said located missing facelets;

adding said missing I-bodies to said connected negative I-bodies to form said completed I-group.

17. The method of claim 16 wherein said step of locating missing facelets includes the steps of:

identifying have-facelets, the union of all facelets of the individual I-bodies in said set of connected I-bodies;

identifying host of facelets as have-facelets which form part of each said grazing surfaces;

forming a set of mated facelets including said host facelets and those facelets which have duplicates within the set of said have-facelets;

forming a set of non-mated facelets including all facelets of I-bodies within said I-groups defined by said grazing surfaces of said connected negative I-bodies;

adding said non-mated facelets to a set of missing faces;

determining if said set of non-mated facelets or said set of mated facelets is null, signifying completion of said step of locating missing facelets;

repeating said steps of identifying have-facelets, identifying host of facelets, forming a set of mated facelets, forming a set of non-mated facelets, and adding if neither said set of mated facelets or said set of unmated facelets are null.

18. The method of claim 15 wherein said step of finding all negative I-bodies connected to said identified negative I-body comprises:

using said identified negative I-body as a seed unit;

identifying all facelets of said seed unit;

determining which of said negative I-bodies within said mixed group have facelets corresponding to the facelets of said seed unit;

adding said negative I-bodies having corresponding facelets to said seed unit to form a larger seed unit;

repeating said steps of identifying, determining, and adding until all negative I-bodies connected to said identified negative I-body are adding together.

19. The method of claim 15 wherein said step of developing a total minus negatives possible construction choice further comprises determining the presence of cycling by determining if said mixed I-group is the same as said connected negative I-bodies, said step of subtracting occurring when cycling is not determined.

20. The method of claim 14 wherein said step of replacing includes developing a union of positives possible construction choice including:

identifying each I-body within the mixed I-group of said possible solution;

identifying a positive I-body within said mixed I-group;

finding all positive I-bodies within said mixed I-group connected to said identified positive I-body;

forming a completed I-group by adding I-bodies to said connected positive I-bodies, said completed I-group being defined by the surfaces grazing the completed set of said connected positive I-bodies;

substituting said completed I-grouped for said mixed I-group in said possible solution to form a union of positive possible construction choice.

21. The method of claim 20 wherein said step of forming includes the steps of:

locating missing facelets of said complete I-group;

determining if any I-bodies within said complete I-group are missing from said set of connected positive I-bodies using said located missing facelets;

adding said missing I-bodies to form said completed I-group.

22. The method of claim 21 wherein said step of locating missing facelets includes the steps of:

identifying have-facelets as the union of all facelets of the individual I-bodies in said set of connected I-bodies;

identifying host of facelets as have-facelets which form part of each said grazing surfaces;

forming a set of mated facelets including said host facelets and those facelets which have duplicates within the set of said have-facelets;

forming a set of non-mated facelets including all facelets of I-bodies within said I-group defined by said grazing surfaces of said connected positive I-bodies;

adding said non-mated facelets to a set of missing facelets;

determining if said set of non-mated facelets or said set of mated facelets is null, signifying completing of said step of locating missing facelets;

repeating said steps of identifying have-facelets, identifying host of facelets, forming a set of mated facelets, surfaces of said object as sectioning surfaces;

means responsive to said first means for representing for converting said grazing surfaces into halfspaces by providing a representation associated with each said grazing surface specifying on which side of said surface said object resdies;

defining the material to remove from said enclosed body;

first means, responsive to said second means for representing, for sectioning said object with all intersecting said sectioning surfaces to form positive elemental atomic geometrical units (I-bodies);

second means, responsive to said second means for representing, for sectioning said material to be removed with all intersecting said sectioning surfaces to form negative elemental atomic geometrical units (I-bodies).

23. The method of claim 20 wherein said step of finding all positive I-bodies connected to said identified positive I-body comprises:

using said identified positive I-body as a seed unit;

identifying all facelets of said seed unit;

determining which of sid positive I-bodies within said mixed group have facelets corresponding to the facelets of said seed unit;

adding said positive I-bodies having corresponding facelets to said seed unit to form a larger seed unit;

repeating said steps of identifying, determining, and adding until all positive I-bodies connected to said identified negative I-body are added together.

24. The method of claim 20 further comprising determining the presence of cycling by determining if said mixed I-group is the same as said set of completed connected positive I-bodies, the detection of cycling inhibiting said step of substituting.

25. The method of claim 14 wherein said step of replacing includes developing a union of sections possible construction choice including:

identifying a sectioning surface in the mixed I-group of said possible solutions;

dividing the mixed I-group into first and second sub-groups defined by said sectioning surface;

producing a possible expression of the union of said first and second sub-groups;

iterating said step of identifying, dividing and producing for each sectioning surface of said mixed I-group to form additional possible expressions; and

heuristically selecting the best expression from said possible expressions.

26. The method of claim 1 wherein said zero, one and two dimensional features are vertices, edges and surfaces, respectively.

27. The method of claim 1 wherein said step of controlling said machine controls said machine to manufacture substantially all of said object.

28. A method manufacturing an object from a boundary representation thereof comprising:

cleaving said boundary representation of said object, which represents said object only by zero, one or two dimensional features thereof, into elemental atomic geometrical units (I-bodies);

assemblies said I-bodies into assemblies having atomic geometrical forms which collectively form a constructive half-space geometry representation of said object usable for manufacturing thereof;

utilizing said constructive solid geometry representation of said object to develop machine instructions for instructing one or more machines in a manufacturing process; and

controlling said machines to perform operations under control of said instructions to manufacture at least a portion of said object.

29. The method of claim 28 further comprising the step of representing said I-bodies in symbolic form;

said step of assembling utilizing the symbolic forms of said I-bodies.

30. The method of claim 28 wherein said zero, one and two dimensional features are vertices, edges and surfaces, respectively.

31. The method of claim 28 wherein said step of controlling said machine controls said machine to manufacture substantially all of said object.

32. A system of manufacturing an object from a boundary representation thereof comprising:

means for cleaving said boundary representation of said object, which represents said object only by zero, one or two dimensional features thereof, into elemental atomic geometrical units (I-bodies);

means responsive to said means for cleaving for assembling said I-bodies into assemblies having atomic geometrical forms which collectively form a constructive solid geometry representation of said object;

means for developing machine instructions for instructing one or more machines in a manufacturing process from said constructive solid geometry representation of said object; and

manufacturing means, responsive to said machine instructions and including one or more machines, for manufacturing said object.

33. The system of claim 32 further comprising means for representing said I-bodies in symbolic form;

said means for assembling utilizing the symbolic forms of said I-bodies developed by said means for representing.

34. The system of claim 33 wherein said means for representing comprises:

means for factually representing each I-body as a plurality of atomic constituent facts;

means responsive to said means for factually representing for mapping said atomic constituent facts so as to interrelate said facts, said facts describing said I-body in symbolic form.

35. The system of claim 32 wherein said means for cleaving includes means for sectioning said object surfaces to divide said object into I-bodies.

36. The system of claim 32 wherein said means for cleaving includes means for defining said I-bodies with the intersection of half-spaces, said means for cleaving further including:

first means for representing extended surfaces of said object which do not intersect a portion of the described volume of said object as grazing surfaces;

second means for representing all other extended surfaces of said object as sectioning surfaces;

means responsive to said first means for representing for converting said grazing surfaces into halfspaces by providing a representation associated with each said grazing surface specifying on which side of said surface said object resides;

defining the material to remove from said enclosed body;

first means, responsive to said second means for representing, for sectioning said object with all intersecting said sectioning surfaces to form positive elemental atomic geometrical units (I-bodies);

second means, responsive to said second means for representing, for sectioning said material to be removed with all intersecting said sectioning surfaces to form negative elemental atomic geometrical units (I-bodies).

37. The system of claim 32 further comprising:

means for transferring information contained in the boundary representation of said object to said constructive solid representation of said object to said constructive solid geometry representation thereof.

38. The system of claim 37 wherein said information is selected from a group consisting of volume, surface area of faces of said object, parallelism of face surfaces, face surface finish, face surface treatment and hole threading information.

39. The system of claim 32 wherein said means of cleaving comprises:

first means for representing extended surfaces of said object which do not intersect a portion of the described volume of said object as grazing surfaces;

second means for representing all other extended surfaces of said object as sectioning surfaces;

means, responsive to said first means for representing for converting said grazing surfaces into half-spaces by providing a representation associated with each said grazing surface specifying which side of said surface said object resides;

means, responsive to said means for converting for forming an enclosing body from the intersection of said halfspaces;

means, responsive to said means for forming, for subtracting the object represented by said boundary representation from said enclosing body to define the material to remove;

first means, responsive to said second means representing, for sectioning said object with all intersecting said sectioning surfaces to form positive I-bodies units;

first means, responsive to said first means for sectioning, for identifying each surface of each said positive I-body as a unique facelet shared only by an adjacent atomic geometrical unit;

second means, responsive to said means for subtracting and said second means, for representing sectioning said material to be removed with all intersecting said sectioning surfaces to form negative atomic geometrical units (I-bodies); and

second means, responsive to said second means for sectioning, for identifying each surface of each said negative I-body as a unique facelet shared only by an adjacent atomic geometrical unit.

40. The system of claim 32 wherein said zero, one and two dimensional features are vertices, edges, and surfaces, respectively.

41. The system of claim 32 wherein said manufacturing means manufactures substantially all of said object.