Object modeling in multi-dimensional space

• US 20140267253A1
• Filed: 03/17/2014
• Published: 09/18/2014
• 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
• Granted Patent: US 9,542,779 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• 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 for inserting a new face in a polygonal mesh, the method comprising:

receiving input corresponding to a polygonal mesh having a plurality of faces;

receiving an input corresponding to a selection of a face (f_m) of the plurality of faces;

receiving an input corresponding to a direction vector (d);

receiving an input corresponding to a modified target plane (p_m);

receiving an input corresponding to a threshold angle θ

; and

for each edge (e) of the selected face f_m;

determining each adjacent face (f_adj) to selected face f_m; 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 θ

.

2. The method of claim 1 wherein the new face has a normal orthogonal to e and d.

3. The method of claim 1 wherein the new face has zero area.

4. The method of claim 1 wherein each of the plurality of faces are planar.

5. A computer-implemented method of updating a polygonal mesh, the method comprising:

receiving input corresponding to a polygonal mesh having a plurality of faces;

receiving an input corresponding to a selection of a face (f_m) of the plurality of faces, wherein f_m has a plurality of vertices;

receiving an input corresponding to a modified target plane (p_m);

for each vertex (v) of f_m;

determining fan of faces (F_fan) connected to v, excluding f_m;

determining all affected faces (F_aff) in F_fan;

computing new vertices (V_new);

replacing v with all points in 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 in F_fan;

determining a previous face f_p relative to f_i in F_fan;

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

otherwise, replacing v in f_i with V_sel.

6. The 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 method of claim 5 wherein computing new vertices (V_new) further comprises intersecting every successive triple of faces in F_affto get the intersection points V_new.

8. The method of claim 5 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-program product tangibly embodied in a non-transitory computer-readable storage medium, including instructions configured to cause a data processing system to:

receive input corresponding to a polygonal mesh having a plurality of faces;

receive an input corresponding to a selection of a face of the plurality of faces;

receive an input corresponding to a direction vector;

receive an input corresponding to a target plane;

receive an input corresponding to a threshold angle θ

, the threshold angle θ

defining the maximum angle that a side can be extended without requiring an insertion of a new face; and

extend the selected face towards the target plane based on the direction vector and the threshold angle.

10. The computer program product of claim 9 further including instructions configured to cause the data processing system to:

determine an adjacent face for each edge of the selected face; and

at each edge, determine a new face needs to be inserted if no adjacent face exists or if the adjacent face has an angle greater than (90°

-threshold angle θ

) relative to the direction vector.

11. The computer program product of claim 10 wherein the plurality of faces are planar.

12. The computer program product of claim 10 further including instructions configured to cause the data processing system to:

insert a new face having two vertices of the particular edge only; and

set a normal of the new face to a cross product of the particular edge'"'"'s direction and the direction vector.

13. 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 input corresponding to a polygonal mesh having a plurality of faces;

receiving an input corresponding to a selection of a face (f_m) of the plurality of faces;

receiving an input corresponding to a direction vector (d);

receiving an input corresponding to a modified target plane (p_m);

receiving an input corresponding to a threshold angle θ

; and

for each edge (e) of the selected face f_m;

determining each adjacent face (f_adj) to selected face f_m; 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 θ

.

14. The system of claim 13 wherein the new face has a normal orthogonal to e and d.

15. The system of claim 13 wherein the new face has zero area.

16. The system of claim 13 wherein each of the plurality of faces are planar.

17. 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 input corresponding to a polygonal mesh having a plurality of faces;

receiving an input corresponding to a selection of a face (f_m) of the plurality of faces, wherein f_m has a plurality of vertices;

receiving an input corresponding to a modified target plane (p_m);

for each vertex (v) of f_m;

determining fan of faces (F_fan) connected to v, excluding f_m;

determining all affected faces (F_aff) in F_fan;

computing new vertices (V_new);

replacing v with all points in 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 in F_fan;

determining a previous face f_p relative to f_i in F_fan;

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 when f_p is not in F_aff; and

otherwise, replacing v in f_i with V_sel.

18. The system of claim 17 wherein determining all affected faces (F_aff) in F_fan includes adding the first, last, and all faces intersecting p_m to F_aff.

19. The system of claim 17 wherein computing new vertices (V_new) further comprises intersecting every successive triple of faces in F_aff to get the intersection points V_new.

20. The system of claim 17 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.