Methods and apparata for rapid computer-aided design of objects in virtual reality and other environments

• US 6,629,065 B1
• Filed: 09/30/1999
• Issued: 09/30/2003
• Est. Priority Date: 09/30/1998
• Status: Expired due to Term

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Dani, Tushar H., Gadh, Rajit
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARCIA OTERO, EDUARDO
• Application Number:
  US09/409,569
• Time in Patent Office: 1,461 Days
• Field of Search: 703/1, 345/420, 345/664, 345/679
• US Class Current: 703/1
• CPC Class Codes: G06F 30/17 Mechanical parametric or variational design
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2219/2016 Rotation, translation, scaling
• CPC Class Codes: G06T 2219/2021 Shape modification

Abstract

Apparata and methods for rapid design of objects/shapes in Computer-Aided Design (CAD) tools and in Virtual Reality (VR) environments are described. The underlying geometric representation of the objects within the design tool is optimized so that design activities such as modeling, editing, rendering, etc. can be processed extremely rapidly, thereby enhancing the response time of the design tool. The representation is preferably provided in two parts, which may be referred to as a “design intent model” and a “shape model”. The design intent model is a higher-level representation wherein elements are arranged in hierarchical parent-child relationships which record the elements'"'"' assembly sequence. The shape model is a lower-level representation storing more detailed information about the elements and their relationships. During editing of the design, the user acts on the design intent model, and the design intent model is mapped to the shape design model so that it is updated to reflect the changes therein. The design intent model is in many cases sufficient by itself to allow basic editing of the model and rendering of the edited model, but where editing operations grow sufficiently complex that the design intent model lacks sufficient information to allow the operation to be performed, the shape model can be relied upon for the information necessary to complete the operation.

Claims

1. A method of constructing a geometric model in a CAD system wherein time is measured in serial time steps, the geometric model being formed from two or more geometric elements in attached relationship, the method comprising:

a. in a first time step,

1. attaching a subject geometric element to one or more prior geometric elements already within the geometric model, the subject geometric element and the prior geometric elements to which it is attached thereby being in a parent-child relationship wherein

(1) the subject geometric element constitutes a child element, and

(2) the prior geometric elements to which it is attached constitute parent elements;

2. outputting the geometric model after the subject geometric element is attached;

b. in a later time step,

(1) modifying the subject geometric element by moving or resizing it within the geometric model;

(2) computing the boundary of the modified subject geometric element and any geometric elements constituting child elements with respect to the subject geometric element, without computing the boundary of any geometric elements constituting parent elements with respect to the subject geometric element; and

(3) outputting the geometric model after the subject geometric element is modified.

2. The method of claim 1 wherein:

a. the first time step includes;

(1) storing the shape of the subject geometric element;

(2) storing the location of the subject geometric element with respect to its parent elements, and

b. wherein the later time step includes;

(1) updating the stored shape of the subject geometric element;

(2) updating the stored location of the subject geometric element with respect to its parent elements;

(3) where the subject geometric element is resized, updating the location of any geometric elements constituting child elements with respect to the subject geometric element;

(4) without altering the locations of the parent elements of the subject geometric element.

3. The method of claim 2 wherein the first time step includes identifying all parallel faces within the subject geometric element.

4. The method of claim 2 wherein the first time step includes identifying all parallel faces between the subject geometric element and each prior geometric element already within the geometric model.

5. The method of claim 1 further comprising the steps of:

a. determining the distances between the subject geometric element and all elements of the geometric model which are neither parents nor children of the subject geometric element;

b. if any determined distance is less than a predefined amount, checking for intersection between the subject geometric element and the element of the geometric model which corresponds to the distance.

6. The method of claim 5 wherein the distances between the elements are determined between their convex hulls.

7. The method of claim 5 wherein the intersection check includes the step of determining whether there is intersection between the convex hulls of the subject geometric element and the element of the geometric model which corresponds to the determined distance.

8. The method of claim 5 wherein the intersection check includes the step of determining whether there is intersection between the boundary representations of the subject geometric element and the element of the geometric model which corresponds to the determined distance.

9. The method of claim 5 wherein the intersection check includes the steps of:

a. determining whether there is intersection between the convex hulls of the subject geometric element and the element of the geometric model which corresponds to the determined distance; and

b. if intersection between the convex hulls is found, determining whether there is intersection between the boundary representations of the subject geometric element and the element of the geometric model which corresponds to the determined distance.

10. The method of claim 1 further comprising the steps of:

a. prior to modifying the subject geometric element, determining the distances between the subject geometric element and all elements of the geometric model which are neither parents nor children of the subject geometric element;

b. after modifying the subject geometric element, checking for intersection between the subject geometric element and some subset of the elements of the geometric model which are neither parents nor children of the subject geometric element.

11. The method of claim 10 further comprising the step of ranking all elements of the geometric model which are neither parents nor children of the subject geometric element by their proximity to the subject geometric element.

12. The method of claim 11 wherein the elements of the geometric model which are neither parents nor children of the subject geometric element are checked for intersection with the subject geometric element in the order of their proximity rank.

13. The method of claim 10 wherein the distances between the elements are determined between their convex hulls.

14. The method of claim 10 wherein the intersection check between the subject geometric element and the subset of the elements of the geometric model is performed by checking for intersection between the convex hulls of these elements.

15. The method of claim 14 wherein if intersection is detected between the subject geometric element and any other element,

a. the boundaries of all geometric elements within the geometric model are computed, and

b. at least some of the computed boundaries are checked for intersection between elements.