Object modeling in multi-dimensional space

• US 10,127,720 B2
• Filed: 12/12/2016
• Issued: 11/13/2018
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Environmental Systems Research Institute Incorporated
• Original Assignee: Environmental Systems Research Institute Incorporated
• Inventors: Lipp, Markus, Mueller, Pascal
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US15/376,512
• Publication Number:
  US 20170132838A1
• Time in Patent Office: 701 Days
• Field of Search: 345420, 345423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/30 Polynomial surface description
• 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 2219/2021 Shape modification

Abstract

Embodiments of the invention include a method inserting a new face in a polygonal mesh comprising receiving an input corresponding to: a polygonal mesh having a plurality of faces, a selection of a face (f_m) of the plurality of faces, a direction vector (d), a modified target plane (p_m), and a threshold angle θ. For each edge (e) of the selected face fm, the method further includes determining each adjacent face (f_adj) to selected face fm, and inserting a new face at edge e if no adjacent face exists or if f_adj is substantially parallel to p_m and within threshold θ. In some embodiments, the new face has a normal orthogonal to e and d.

Claims

1. A computer-implemented method comprising:

receiving a first input corresponding to a selection of a face (f_m) on a multi-faced, three dimensional (3D) polygonal mesh rendered on a display, wherein f_m has a plurality of vertices;

receiving a second input corresponding to a modified target plane (p_m) to be extended from f_m;

for each vertex (v) of f_m;

determining faces (F_aff) connected to v to change by extending f_m to p_m;

computing new vertices (V_new) for F_aff based on p_m;

replacing v with the corresponding V_new;

for each face (f_i) in F_aff;

finding vertices V_sel to insert;

determining a next face f_n relative to f_i;

determining a previous face f_p relative to f_i;

inserting the vertices V_sel after v in f_i when f_n is not in F_aff;

inserting the vertices V_sel before v in f_i when f_p is not in F_aff; and

rendering the updated polygonal mesh on the display.

2. The computer-implemented method of claim 1 further comprising:

replacing v in f_i with V_sel when f_n and f_p are in F_aff.

3. The computer-implemented method of claim 1 wherein the determined faces (F_aff) excludes (f_m).

4. The computer-implemented method of claim 1 wherein when f_i intersects p_m then add f_i to F_aff.

5. The computer-implemented method of claim 1 wherein (F_aff) is a fan (F_fan) of faces.

6. The computer-implemented method of claim 5 wherein determining all affected faces (F_aff) in F_fan includes adding the first, last, and all faces intersecting p_m to F_aff.

7. The computer-implemented method of claim 1 wherein computing new vertices (V_new) further comprises intersecting every successive triple of faces in F_aff to get the intersection points V_new.

8. The computer-implemented method of claim 1 wherein finding vertices V_sel to insert further comprises:

adding a first vertex of V_new to V_sel when f_i is the first face; and

adding the last vertex of V_new to V_sel when f_i is the last face; and

otherwise, adding the previous vertex v(i−

1) and the current vertex v_i of V_new to V_sel.

9. A computer-implemented system, comprising:

one or more processors; and

one or more non-transitory computer-readable storage mediums containing instructions configured to cause the one or more processors to perform operations including;

receiving a first input corresponding to a selection of a face (f_m) on a multi-faced, three dimensional (3D) polygonal mesh rendered on a display, wherein f_m has a plurality of vertices;

receiving a second input corresponding to a modified target plane (p_m) to be extended from f_m;

for each vertex (v) of f_m;

determining faces (F_aff) connected to v to change by extending f_m to p_m;

computing new vertices (V_new) for F_aff based on p_m;

replacing v with the corresponding V_new;

for each face (f_i) in F_aff;

finding vertices V_sel to insert;

determining a next face f_n relative to f_i;

determining a previous face f_p relative to f_i;

inserting the vertices V_sel after v in f_i when f_n is not in F_aff;

inserting the vertices V_sel before v in f_i when f_p is not in F_aff; and

rendering the updated polygonal mesh on the display.

10. The computer-implemented system of claim 9 wherein the one or more non-transitory computer-readable storage mediums further contain instructions configured to cause the one or more processors to perform operations including:

replacing v in f_i with V_sel when f_n and f_p are in F_aff.

11. The computer-implemented system of claim 9 wherein the determined faces (F_aff) excludes (f_m).

12. The computer-implemented system of claim 9 wherein when f_i intersects p_m then add f_i to F_aff.

13. The computer-implemented system of claim 9 wherein (F_aff) is a fan (F_fan) of faces.

14. The computer-implemented system of claim 13 wherein determining all affected faces (F_aff) in F_fan includes adding the first, last, and all faces intersecting p_m to F_aff.

15. The computer-implemented system of claim 9 wherein computing new vertices (V_new) further comprises intersecting every successive triple of faces in F_aff to get the intersection points V_new.

16. The computer-implemented system of claim 9 wherein finding vertices V_sel to insert further comprises:

adding a first vertex of V_new to V_sel when f_i is the first face; and

adding the last vertex of V_new to V_sel when f_i is the last face; and

otherwise, adding the previous vertex v(i−

1) and the current vertex v_i of V_new to V_sel.

17. A computer-program product tangibly embodied in a non-transitory computer-readable storage medium including instructions configured to cause a processor to:

receive a first input corresponding to a selection of a face (f_m) on a multi-faced, three dimensional (3D) polygonal mesh rendered on a display, wherein f_m has a plurality of vertices;

receive a second input corresponding to a modified target plane (p_m) to be extended from f_m;

for each vertex (v) of f_m;

determine faces (F_aff) connected to v to change by extending f_m to p_m;

compute new vertices (V_new) for F_aff based on p_m;

replace v with the corresponding V_new;

for each face (f_i) in F_aff;

find vertices V_sel to insert;

determine a next face f_n relative to f_i;

determine a previous face f_p relative to f_i;

insert the vertices V_sel after v in f_i when f_n is not in F_aff;

insert the vertices V_sel before v in f_i when f_p is not in F_aff; and

render the updated polygonal mesh on the display.

18. The computer-program product of claim 17 wherein the instructions are further configured to cause a processor to:

replace v in f_i with V_sel when f_n and f_p are in F_aff.

19. The computer-program product of claim 17 wherein the determined faces (F_aff) excludes (f_m).

20. The computer-program product of claim 17 wherein when f_i intersects p_m then add f_i to F_aff.