Patent ID: 12198270

DETAILED DESCRIPTION

In view of the above issues, as shown inFIG.1, a schematic diagram of a modeling system10is depicted comprising a server computing device12which includes one or more processors14, which can be communicatively coupled to a network22. The server computing device12further comprises non-volatile memory16storing a three-dimensional (3D) virtual model30and instructions32that, when executed by the processor14, cause the processor14to retrieve the 3D virtual model30from the non-volatile memory16. The 3D virtual model30can be of an aircraft or an aircraft component, or other manufactured parts or components, for example, as illustrated inFIG.8. The sizes of the 3D virtual model30are not particularly limited—the 3D virtual model30can be of micron-scale objects in such applications as printed circuit boards or medical devices, or of over-sized objects.

The 3D virtual model30is the mathematical representation of the surface geometry of an object, so that computer-rendered images of the object can be created from any angle. The 3D virtual model30can be a polygon mesh model.

The non-volatile memory16can further store a U-V mapping40, onto which one or more feature curves of the 3D virtual model30can be projected to produce a plurality of two dimensional curves (U-V curves). The U-V mapping is a parameterized surface and can be a piecewise polynomial mapping, such as a tensor product spline, between a two-dimensional rectangular parameter domain and three-dimensional space.

The server computing device12includes a network interface18to affect the communicative coupling to the network22and, through the network22, a client computing device24. The client computing device24comprises a display28which is configured to display a parameterized surface42which is outputted by the server computing device12. Network interface18can include a physical network interface, such as a network adapter.

The server computing device12can be a special-purpose computer, adapted for reliability and high-bandwidth communications. Thus, the system10can be embodied in a cluster of individual hardware server computers, for example. The processor14can be multi-core processors suitable for handling large amounts of information. The processor14is communicatively coupled to non-volatile memory16storing a 3D virtual model30, U-V mapping40, and instructions32which can be executed by the processor14to effectuate the techniques disclosed herein on concert with the client computing device24as shown and described below. The non-volatile memory16can be in a Redundant Array of Inexpensive Disk drives (RAID) configuration for added reliability. The processor14can also be communicatively coupled to graphical co-processors (GPU)20. Graphical co-processors20can expedite the technique disclosed herein by performing operations in parallel.

The processor14is configured to execute a modeling application15. The modeling application15is configured to retrieve a 3D virtual model30of an object from the non-volatile memory16, define a parameter domain, parameterize the 3D virtual model30over the parameter domain to thereby extract an outer surface of the 3D virtual model30, the outer surface including a plurality of faces, identify feature curves and bounding boxes in each of the plurality of faces of the outer surface, generate a parameterized surface42from the identified feature curves, and output the feature curves and the parameterized surface42.

FIG.2shows an illustration of a connectivity graph34which maps points in 3D space to the feature curves. Here, a 3D virtual model30of a toy car is shown with faces FACE01-FACE10 extracted as an outer surface of the 3D virtual model30. The connectivity graph34shows the connectivity of the different faces to each other. The connectivity graph34can be a connectivity tree or graph mapping the feature curves to the plurality of faces, and mapping points in the 3D space to the feature curves.

In this example, the connectivity graph34shows that FACE01 is connected to FACE02, FACE07, and FACE08. The feature curves extracted or identified in each face are also shown. For example, FACE01 is shown to have feature curves C1 through C7, while FACE07 is shown to have feature curves C92 through C97. In some configurations, only feature curves with arc lengths that are longer than a predetermined minimum length can be extracted.

To build the connectivity graph, a list36is generated of feature curve pairs that are proximate or adjacent to one another, which is subsequently used by the modeling application15to build a connectivity graph34mapping points in 3D space to the feature curves. To generate the list36, nearby points can be found for each point in each feature curve using a spatial indexing scheme, which contains data about the relative proximities of the feature curves to each other. The spatial indexing scheme can be configured as an RTREE, for example. The corresponding curve is found for each nearby point to obtain a set of unique nearby feature curves. To further refine the list36, additional computations can be performed to determine whether two feature curves among the unique nearby feature curves are proximate or adjacent to each other. This can be done by calculating geometric distance, for example, using a distance function, and determining that the approximate Hausdorff distance between the two feature curves is less than a predetermined threshold distance. Responsive to determining that the two curves are proximate or adjacent to each other, the feature curve pair is appended to the list36of feature curve pairs, thereby generating a list36of feature curve pairs that are proximate or adjacent to one another.

Alternatively or additionally, a principal axis of each feature curve can be calculated. It can be determined whether principal directions of the principal axes of the feature curves of the feature curve pair are aligned within a predetermined angle threshold. Responsive to determining that the principal directions of the principal axes of the feature curves of the feature curve pair are aligned within the predetermined angle threshold, the feature curve pair can be added to the list36of feature curve pairs that are adjacent to one another.

Alternatively or additionally, midpoints and end points of each feature curve can be projected. It can be determined whether the midpoints and the end points are separated within a predetermined distance. Responsive to determining that the midpoints and the end points are separated within the predetermined distance, the feature curve pair can be added to the list36of feature curve pairs that are adjacent to one another. The predetermined distance can be half a difference between the arc lengths of the feature curves of the feature curve pair, for example.

Alternatively or additionally, referring toFIG.3, the process of extracting features from the 3D virtual model30via the connectivity graph is schematically illustrated for three of the faces: face 01, face 03, and face 07. The small arrows on each of the three faces represent normals of each face. The normals of the connected faces are compared, and added as a feature if the angle difference between the normals is greater than a predetermined threshold. The predetermined threshold may be set between 45 to 90 degrees, for example. Here, the angle difference between the normals of face 01 and face 07 is determined to be greater than a predetermined threshold, so a first feature38ais extracted between face 01 and face 07. Likewise, the angle difference between the normals of face 01 and face 03 is determined to be greater than a predetermined threshold, so a second feature38bis extracted between face 01 and face 03. Boundaries38caround the faces 01, 03, 07 are subsequently extracted. When missing faces are detected, the faces are added, and the connectivity graph is updated.

For each feature curve pair in the list36, the two faces corresponding to the feature curve pair are obtained, and the two faces are added to the connectivity graph34. For example, the two faces corresponding to feature curves C7 and C8 are identified as face 01 and face 02, respectively. Likewise, the two faces corresponding to feature curves C1 and C92 are identified as face 01 and face 07, respectively. Accordingly, the modeling application15obtains face pairs corresponding to the feature curve pairs to obtain a list36of faces in the outer surface of the 3D virtual model30, and then adds this list36of faces to the connectivity graph34.

The list of features is subsequently outputted. The features38a,38bcan be organized and the curves joined into single features. A parameterized surface42can be generated from the generated feature curves. The feature curves C1-C199 and the parameterized surface42are subsequently outputted.

FIGS.4A and4Bshow an exemplary modeling method100according to an example of the present disclosure. The following description of method100is provided with reference to the software and hardware components described above and shown inFIGS.1through3. It will be appreciated that method100also can be performed in other contexts using other suitable hardware and software components.

At step102, a 3D virtual model is retrieved. At step104, an outer surface of the 3D virtual model is extracted, the outer surface including a plurality of faces. At step106, feature curves in each of the plurality of faces of the outer surface are identified. Step106can include a step106aof identifying feature curves in each of the plurality of faces of the outer surface with arc lengths that are longer than a predetermined minimum length.

At step110, a connectivity graph is built for the one or more feature curves, which maps points in 3D space to the feature curves. Step110can include steps110a-f. At step110a, all points are identified for each feature curve. At step110b, nearby points are found for each point in each feature curve using a spatial indexing scheme. At step110c, the corresponding curve is found for each nearby point to obtain a set of unique nearby feature curves. Step110ddetermines whether two feature curves among the unique nearby feature curves are proximate or adjacent to each other. This can be done by calculating geometric distance, for example, using a distance function, and determining that the approximate Hausdorff distance between the two feature curves is less than a predetermined threshold distance. However, it will be appreciated that other additional or alternative methods can be used to identify adjacent feature curve pairs. At step110e, responsive to determining that the two curves are proximate or adjacent to each other, the feature curve pair is appended to a list of feature curve pairs to generate the list of feature curve pairs that are proximate or adjacent to one another. At step110f, for each feature curve, the two faces corresponding to the feature curve pair are identified to obtain face pairs corresponding to the feature curve pairs and obtain a list of faces in the outer surface, and the list of faces in the outer surface is added to the connectivity graph.

At step112, the features are extracted from the connectivity graph. Step112can include steps112a-d. At step112a, boundaries are extracted. At step112b, missing faces are detected. At step112c, the faces are repaired, and the connectivity graph is updated. At step112d, the normals for each pair of connected faces are computed and compared, evaluating whether an angle difference between normal of the connected faces is greater than a predetermined threshold. A feature curve is extracted based on the pair of connected faces, and added as a feature responsive to determining that the angle difference between the normals is greater than a threshold. At step114, the list of features is outputted. At step116, the features are organized, and the curves are joined into single features.

At step118, a parameterized surface is generated from the generated feature curves. At step120, the feature curves and the parameterized surface are outputted.

FIG.5is an image of an aircraft200according to some embodiments. It will be appreciated that the aircraft200or a component202thereof can be the object that is modeled by the 3D virtual model30in accordance with the system10and method100of the subject disclosure.

The systems and processes described herein have the potential benefit of building 3D parameterized surfaces that model complicated shapes accurately and efficiently without using an excessive number of control points, so that the feature curves of the 3D virtual model track the features of the 3D virtual model, including sharp edges or corners of the 3D virtual model, even on parts with complex geometric curvatures, such as wing panels of airplanes with many polygonal faces.

Thus, the 3D virtual model of the present disclosure improves accuracy. By reducing the number of control points in the 3D virtual model, the model becomes easier to work with for designers and programmers. Conventionally, designers and programmers would synthesize data represented in multiple separate geometric patches for each feature detected in the model, which was processor and memory intensive, so that the synthesized model could be input into analysis software programs. Producing a synthesized version of the patches and is a time-consuming, processor intensive, and memory intensive process. In contrast, the 3D virtual model of the present disclosure can save processor and memory resources by avoiding such laborious synthesis of separate geometries. Further, by detecting sharp feature curves on the 3D virtual model, they can be used as engineering features in computer-aided design (CAD) applications, thereby improving the technical compatibility of the model as compared to prior approaches.

The parameterized surfaces outputted by the systems and processes described herein can be used in various applications. For example, the parameterized surfaces can be used in additive manufacturing applications, for example, to optimize the weight, cost, and/or function of a 3D manufactured object through 3D model modifications. The parameterized surfaces can also be used to detect surface anomalies during inspection of the skin of manufactured or assembled parts of aircraft using three-dimensional modeling, for example.

FIG.6illustrates an exemplary computing system300that can be utilized to implement the system10and method100described above. Computing system300includes a logic processor302, volatile memory304, and a non-volatile storage device306. Computing system300can optionally include a display subsystem308, input subsystem310, communication subsystem312connected to a computer network, and/or other components not shown inFIG.6. These components are typically connected for data exchange by one or more data buses when integrated into single device, or by a combination of data buses, network data interfaces, and computer networks when integrated into separate devices connected by computer networks.

The non-volatile storage device306stores various instructions, also referred to as software, that are executed by the logic processor302. Logic processor302includes one or more physical devices configured to execute the instructions. For example, the logic processor302can be configured to execute instructions that are part of one or more applications, programs, routines, libraries, objects, components, data structures, or other logical constructs. Such instructions can be implemented to perform a task, implement a data type, transform the state of one or more components, achieve a technical effect, or otherwise arrive at a desired result.

The logic processor302can include one or more physical processors (hardware) configured to execute software instructions. Additionally or alternatively, the logic processor302can include one or more hardware logic circuits or firmware devices configured to execute hardware-implemented logic or firmware instructions. Processors of the logic processor302can be single-core or multi-core, and the instructions executed thereon can be configured for sequential, parallel, and/or distributed processing. Individual components of the logic processor302optionally can be distributed among two or more separate devices, which can be remotely located and/or configured for coordinated processing. Aspects of the logic processor302can be virtualized and executed by remotely accessible, networked computing devices configured in a cloud-computing configuration. In such a case, these virtualized aspects are run on different physical logic processors of various different machines, it will be understood.

Non-volatile storage device306includes one or more physical devices configured to hold instructions executable by the logic processors to implement the methods and processes described herein. When such methods and processes are implemented, the state of non-volatile storage device306can be transformed—e.g., to hold different data.

Non-volatile storage device306can include physical devices that are removable and/or built-in. Non-volatile storage device306can include optical memory (e.g., CD, DVD, HD-DVD, Blu-Ray Disc, etc.), semiconductor memory (e.g., ROM, EPROM, EEPROM, FLASH memory, etc.), and/or magnetic memory (e.g., hard-disk drive, floppy-disk drive, tape drive, MRAM, etc.), or other mass storage device technology. Non-volatile storage device306can include nonvolatile, dynamic, static, read/write, read-only, sequential-access, location-addressable, file-addressable, and/or content-addressable devices. It will be appreciated that non-volatile storage device306is configured to hold instructions even when power is cut to the non-volatile storage device306.

Volatile memory304can include physical devices that include random access memory. Volatile memory304is typically utilized by logic processor302to temporarily store information during processing of software instructions. It will be appreciated that volatile memory304typically does not continue to store instructions when power is cut to the volatile memory304.

Aspects of logic processor302, volatile memory304, and non-volatile storage device306can be integrated together into one or more hardware-logic components. Such hardware-logic components can include field-programmable gate arrays (FPGAs), program- and application-specific integrated circuits (PASIC/ASICs), program- and application-specific standard products (PSSP/ASSPs), system-on-a-chip (SOC), and complex programmable logic devices (CPLDs), for example.

The terms “module,” “program,” and “engine” can be used to describe an aspect of the modeling system10typically implemented in software by a processor to perform a particular function using portions of volatile memory, which function involves transformative processing that specially configures the processor to perform the function. Thus, a module, program, or engine can be instantiated via logic processor302executing instructions held by non-volatile storage device306, using portions of volatile memory304. It will be understood that different modules, programs, and/or engines can be instantiated from the same application, service, code block, object, library, routine, API, function, etc. Likewise, the same module, program, and/or engine can be instantiated by different applications, services, code blocks, objects, routines, APIs, functions, etc. The terms “module,” “program,” and “engine” can encompass individual or groups of executable files, data files, libraries, drivers, scripts, database records, etc.

Display subsystem308typically includes one or more displays, which can be physically integrated with or remote from a device that houses the logic processor302. Graphical output of the logic processor executing the instructions described above, such as a graphical user interface, is configured to be displayed on display sub system308.

Input subsystem310typically includes one or more of a keyboard, pointing device (e.g., mouse, trackpad, finger operated pointer), touchscreen, microphone, and camera. Other input devices can also be provided.

Communication subsystem312is configured to communicatively couple various computing devices described herein with each other, and with other devices. Communication subsystem312can include wired and/or wireless communication devices compatible with one or more different communication protocols. As non-limiting examples, the communication subsystem can be configured for communication via a wireless telephone network, or a wired or wireless local- or wide-area network by devices such as a 3G, 4G, 5G, or 6G radio, WIFI card, ethernet network interface card, BLUETOOTH radio, etc. In some embodiments, the communication subsystem can allow computing system10to send and/or receive messages to and/or from other devices via a network such as the Internet. It will be appreciated that one or more of the computer networks via which communication subsystem312is configured to communicate can include security measures such as user identification and authentication, access control, malware detection, enforced encryption, content filtering, etc., and can be coupled to a wide area network (WAN) such as the Internet.

The subject disclosure includes all novel and non-obvious combinations and subcombinations of the various features and techniques disclosed herein. The various features and techniques disclosed herein are not necessarily required of all examples of the subject disclosure. Furthermore, the various features and techniques disclosed herein can define patentable subject matter apart from the disclosed examples and can find utility in other implementations not expressly disclosed herein.

To the extent that terms “includes,” “including,” “has,” “contains,” and variants thereof are used herein, such terms are intended to be inclusive in a manner similar to the term “comprises” as an open transition word without precluding any additional or other elements.

Further, the disclosure comprises configurations according to the following clauses.

Clause 1. A modeling system comprising: at least one processor, communicatively coupled to non-volatile memory storing a three-dimensional (3D) virtual model and instructions that, when executed by the processor, cause the processor to: retrieve a 3D virtual model of an object; extract an outer surface of the 3D virtual model, the outer surface including a plurality of faces; identify feature curves in each of the plurality of faces of the outer surface; generate a parameterized surface from the identified feature curves; and output the feature curves and the parameterized surface.

Clause 2. The modeling system of clause 1, wherein the instructions, when executed by the processor, further cause the processor to: generate a list of feature curve pairs that are adjacent to one another; obtain face pairs corresponding to the feature curve pairs; obtain a list of faces in the outer surface; add the list of faces to a connectivity graph mapping points in 3D space to the feature curves; compute normals for each pair of connected faces; and for each pair of connected faces, evaluate whether an angle difference between normals of the connected faces is greater than a predetermined threshold; and responsive to determining that the angle difference between the normals of the connected faces is greater than the predetermined threshold, extract a feature curve based on the pair of connected faces.

Clause 3. The modeling system of clause 1 or 2, wherein a spatial indexing scheme is used to generate the list of feature curve pairs that are adjacent to one another.

Clause 4. The modeling system of any of clauses 1 to 3, wherein, to generate the list of feature curve pairs that are adjacent to one another, for each feature curve pair: a principal axis of each feature curve is calculated; it is determined whether principal directions of the principal axes of the feature curves of the feature curve pair are aligned within a predetermined angle threshold; and responsive to determining that the principal directions of the principal axes of the feature curves of the feature curve pair are aligned within the predetermined angle threshold, the feature curve pair is added to the list of feature curve pairs that are adjacent to one another.

Clause 5. The modeling system of any of clauses 1 to 4, wherein, to generate the list of feature curve pairs that are adjacent to one another, for each feature curve pair: midpoints and end points of each feature curve are projected; it is determined whether the midpoints and the end points are separated within a predetermined distance; responsive to determining that the midpoints and the end points are separated within the predetermined distance, the feature curve pair is added to the list of feature curve pairs that are adjacent to one another.

Clause 6. The modeling system of any of clauses 1 to 5, wherein responsive to determining that the midpoints and the end points are separated within the predetermined distance, and the predetermined distance is greater than half the difference between the arc lengths of the feature curves of the feature curve pair, the feature curve pair is added to the list of feature curve pairs that are adjacent to one another.

Clause 7. The modeling system of any of clauses 1 to 6, wherein the connectivity graph maps the feature curves to the plurality of faces, and maps points in the 3D space to the feature curves.

Clause 8. The modeling system of any of clauses 1 to 7, wherein the processor is further configured to generate tiles based on the generated feature curves and the parameterized surface.

Clause 9. The modeling system of any of clauses 1 to 8, wherein feature curves with arc lengths longer than a predetermined minimum length are extracted from the plurality of faces.

Clause 10. The modeling system of any of clauses 1 to 9, wherein the extraction of feature curves includes the extraction of bounding boxes associated with the feature curves; and the bounding boxes represent a geometry of the plurality of faces.

Clause 11. A modeling method comprising steps to: extract an outer surface of the three-dimensional (3D) virtual model, the outer surface including a plurality of faces; identify feature curves in each of the plurality of faces of the outer surface; generate a parameterized surface from the identified feature curves; and output the feature curves and the parameterized surface.

Clause 12. The modeling method of clause 11, further comprising steps to: generate a list of feature curve pairs that are proximate or adjacent to one another; obtain face pairs corresponding to the feature curve pairs; obtain a list of faces in the outer surface; add the list of faces to a connectivity graph mapping points in 3D space to the feature curves; compute normals for each pair of connected faces; and for each pair of connected faces, evaluate whether an angle difference between normals of the connected faces is greater than a predetermined threshold; and responsive to determining that the angle difference between the normals of the connected faces is greater than the predetermined threshold, extract a feature curve based on the pair of connected faces.

Clause 13. The modeling method of clause 11 or 12, wherein a spatial indexing scheme is used to generate the list of feature curve pairs that are proximate or adjacent to one another.

Clause 14. The modeling method of any of clauses 11 to 13, wherein, to generate the list of feature curve pairs that are adjacent to one another, for each feature curve pair: a principal axis of each feature curve is calculated; it is determined whether principal directions of the principal axes of the feature curves of the feature curve pair are aligned within a predetermined angle threshold; and responsive to determining that the principal directions of the principal axes of the feature curves of the feature curve pair are aligned within the predetermined angle threshold, the feature curve pair is added to the list of feature curve pairs that are adjacent to one another.

Clause 15. The modeling method of any of clauses 11 to 14, wherein, to generate the list of feature curve pairs that are adjacent to one another, for each feature curve pair: midpoints and end points of each feature curve are projected; it is determined whether the midpoints and the end points are separated within a predetermined distance; responsive to determining that the midpoints and the end points are separated within the predetermined distance, the feature curve pair is added to the list of feature curve pairs that are adjacent to one another.

Clause 16. The modeling method of any of clauses 11 to 15, wherein responsive to determining that the midpoints and the end points are separated within the predetermined distance, and the predetermined distance is greater than half the difference between the arc lengths of the feature curves of the feature curve pair, the feature curve pair is added to the list of feature curve pairs that are adjacent to one another.

Clause 17. The modeling method of any of clauses 11 to 16, wherein the connectivity graph maps the feature curves to the plurality of faces, and maps points in the 3D space to the feature curves.

Clause 18. The modeling method of any of clauses 11 to 17, further comprising generating tiles based on the generated feature curves and the parameterized surface.

Clause 19. The modeling method of any of clauses 11 to 18, wherein the extraction of feature curves includes the extraction of bounding boxes associated with the feature curves; and the bounding boxes represent a geometry of the plurality of faces.

Clause 20. A modeling system comprising: at least one processor, communicatively coupled to non-volatile memory storing a three-dimensional (3D) virtual model and instructions that, when executed by the processor, cause the processor to: retrieve a 3D virtual model of an object; extract an outer surface of the 3D virtual model, the outer surface including a plurality of faces; identify feature curves and bounding boxes of the feature curves from the plurality of faces of the outer surface; generate a list of feature curve pairs that are adjacent to one another; obtain face pairs corresponding to the feature curve pairs; compute normals for each pair of connected faces; for each pair of connected faces, evaluate whether an angle difference between normals of the connected faces is greater than a predetermined threshold; and responsive to determining that the angle difference between the normals of the connected faces is greater than the predetermined threshold, extract a feature curve based on the pair of connected faces; generate a parameterized surface from the generated feature curves; and output the feature curves and the parameterized surface.