Methods, apparatus and computer program products for modeling three-dimensional colored objects

• US 6,853,373 B2
• Filed: 04/25/2001
• Issued: 02/08/2005
• Est. Priority Date: 04/25/2001
• Status: Expired due to Term

• Current Assignee: 3D Systems, Inc. (3D Systems Corporation)
• Original Assignee: Raindrop Geomagic, Inc. (3D Systems Corporation)
• Inventors: Williams, Steven P., Edelsbrunner, Herbert, Fu, Ping
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/842,304
• Publication Number:
  US 20020158880A1
• Time in Patent Office: 1,385 Days
• Field of Search: 345/419, 345/420, 345/423, 345/427, 345/619
• US Class Current: 345/419
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Methods, apparatus and computer program products can generate light weight but highly realistic and accurate colored models of three-dimensional colored objects. The colored model may be generated from a second plurality of points that define a coarse digital representation of the surface and at least one texture map containing information derived from a first plurality of colored points that define a fine digital representation of the surface. This derivation is achieved by mapping points within the texture map to the fine digital representation of the three-dimensional surface. Colored scan data may be used to construct the fine digital representation as a triangulated surface (i.e., triangulation) using a wrapping operation. This triangulated surface may be a two-manifold with or without nonzero boundary and the colored scan data may constitute raw point data with each datum comprising three real numbers (x-,y-, z-coordinates) providing geometric information and three integer numbers (r-,g-,b-values) providing color information. Operations are then performed to create the coarse digital representation from the fine digital representation and also preferably create a plurality a texture maps from the fine and coarse digital representations. One map may contain color information and another map may recover geometric detail lost in the simplification process associated with generating the coarse digital representation from the fine digital representation. An additional map may also be generated that corrects for differences in directions of normal vectors associated with the coarse and fine digital representations.

Claims

1. A method of modeling a three-dimensional object, comprising:

generating a model of a three-dimensional surface of the object from a second plurality of points that define a coarse digital representation of the three-dimensional surface and a texture map containing information derived by mapping points within the texture map to a fine digital representation of the three-dimensional surface that is defined by a first plurality of three-dimensional colored points, by;

generating a quadrangulation of the three-dimensional surface from the first plurality of three-dimensional colored points;

converting the quadrangulation into the second plurality of points; and

determining the texture map for the coarse digital representation of the three-dimensional surface by determining for a first texel in the texture map a respective texel coordinate that identifies a first spatial point on the coarse digital representation of the three-dimensional surface and projecting the first spatial point to a first object point on the fine digital representation of the three-dimensional surface.

2. The method of claim 1, wherein said step of determining a texture map comprises the step determining a color map by assigning a color associated with the first object point to the first texel.

3. The method of claim 2, wherein the second plurality of points constitute vertices of a coarse triangulation;

wherein the first plurality of three-dimensional colored points constitute vertices of a fine triangulation; and

wherein the color associated with the first object point y is determined by a function x(y), where;

χ

(y)=α

χ

(a)+β

χ

(b)+γ

X(c),

abc is a triangle on the fine triangulation that contains y and α

, β

, γ

are the barycentric coordinates of y defined such that α

+β

+γ

=1 and α

a+β

b+γ

c=y.

4. The method of claim 3, wherein patch boundaries of the quadrangulation Q trace u-coordinate and v-coordinate lines;

and wherein said step of determining a texture map comprises the steps of;

determining a displacement map by assigning a height difference δ

(y) between the first spatial point x and the first object point y to the first texel, where

y=x+δ

(y)·

n_x

 

and n_x is a vector that extends in a direction from the first spatial point to the first object point and is normal to the coarse digital representation of the three-dimensional surface at the first spatial point;

determining a perturbed normal map by;

constructing an orthonormal frame (N, T, B) defined for N=n_x,

where T and B are the tangent and binormal directions at the first spatial point, respectively; and

determining a triplet (λ

,μ

,u)ε

[−

1,+1]³ where;

n_y=λ

·

N+μ

·

T+u·

B

 

and n_y is a normal vector at the first object point as expressed in the orthonormal frame.

5. The method of claim 1, wherein said converting step comprises the steps of:

decomposing the quadrangulation into a quadrangular grid; and

decimating the quadrangular grid through a sequence of track contractions that are prioritized by an error function.

6. The method of claim 1, wherein said converting step comprises:

decomposing the quadrangulation into a quadrangular grid;

creating a dual graph of the quadrangular grid; and

removing whiskers from the dual graph using a simplification operation that is driven by a priority queue that orders whiskers by a respective error their removal causes to the quadrangular grid.

7. The method of claim 6, wherein the respective error is a mean. square error.

8. The method of claim 1, wherein said converting step comprises the steps of:

decomposing the quadrangulation into a quadrangular grid; and

generating an intermediate triangulation from the quadrangular grid using a decomposition operation that preserves vertices of the quadrangular grid and patch boundaries from the quadrangulation.

9. The method of claim 8, further comprising the step of decimating the intermediate triangulation into a coarse triangulation using a sequence of edge contractions that preserve patch boundaries from the quadrangulation.

17. The method of claim 4, where T=N×

d/∥

N×

d∥ and

B=T×

N and d is a direction of a v-coordinate line passing through the first spatial point xε

Q.

10. A method of modeling a three-dimensional object, comprising:

generating a model of a three-dimensional surface of the object from a second plurality of points that define a coarse digital representation of the three-dimensional surface and a texture map containing information derived by mapping points within the texture map to a fine digital representation of the three-dimensional surface that is defined by a first plurality of three-dimensional colored points, by;

determining the texture map for the coarse digital representation of the three-dimensional surface by determining for a first texel in the texture map a respective texel coordinate that identifies a first spatial point on the coarse digital representation of the three-dimensional surface and projecting the first spatial point to a first object point on the fine digital representation of the three-dimensional surface.

11. The method of claim 10, wherein said step of determining a texture map comprises determining a color map by assigning a color associated with the first object point to the first texel.

12. The method of claim 10, wherein said step of determining a texture map comprises determining a displacement map by assigning a height difference between the first spatial point and the first object point to the first texel.

13. The method of claim 10, wherein said step of determining a texture map comprises determining a displacement map by assigning a height difference δ

(y) between the first spatial point x and the first object point y to the first texel, where

y=x+δ

(y)·

n_x

and n_x is a vector that extends in a direction from the first spatial point to the first object point and is normal to the coarse digital representation at the first spatial point.

14. The method of claim 10, wherein said step of determining a texture map comprises the step of determining a perturbed normal map by assigning a difference between a first normal at the first spatial point and a second normal at the first object point to the first texel.

15. The method of claim 14, wherein said step of determining a texture map comprises the step of determining a perturbed normal map by constructing an orthonormal frame (N, T, B) defined for N=n_x, where T and B are the tangent and binormal directions at the first spatial point, respectively.

16. The method of claim 15, wherein said step of determining a perturbed normal map comprises determining a triplet (λ

, μ

,u)ε

[−

1, +1]³ where;

n_y=λ

·

N+μ

·

T+u·

B

and n_y is a normal vector at the first object point as expressed in the orthonormal frame.

18. A method of modeling a three-dimensional object, comprising the step of:

generating a model of a three-dimensional surface of the object from a second plurality of points that define a coarse digital representation of the three-dimensional surface and a texture man containing information derived by mapping points within the texture man to a fine digital representation of the three-dimensional surface that is defined by a first plurality of three-dimensional colored points, said generating step comprising;

generating a guadrangulation of the three-dimensional surface from the first plurality of three-dimensional colored points;

converting the guadrangulation into the second plurality of points; and

constructing the texture man for the coarse digital representation of the three-dimensional surface using a parametrization ψ

of the quadrangular patches on the guadrangulation, said constructing step comprising;

determining for a first texel in the texture map a respective texel coordinate that, using ψ

<sup>−

1</sup>, identifies a first spatial point on the coarse digital representation of the three-dimensional surface; and

projecting along a normal from the first spatial point to a first object point on the fine digital representation of the three-dimensional surface.

19. A method of modeling a three-dimensional object, comprising the step of:

generating a model of a three-dimensional surface of the object from a second plurality of points that define a coarse digital representation of the three-dimensional surface and a texture mar containing information derived by mapping points within the texture map to a fine digital representation of the three-dimensional surface that is defined by a first plurality of three-dimensional colored points, said generating step comprising;

generating a subdivision surface model from the first plurality of three-dimensional colored points;

converting the subdivision surface model into the second plurality of points; and

determining the texture map for the coarse digital representation of the three-dimensional surface by;

determining for a first texel in the texture map a respective texel coordinate that identifies a first spatial point on the coarse digital representation of the three-dimensional surface; and

projecting the first spatial point to a first object point on the fine digital representation of the three-dimensional surface.

20. A method of modeling a three-dimensional colored object, comprising:

generating a colored model of a surface of the colored object from a coarse triangulation of the surface and a texture map containing information obtained by mapping points within the texture map to a fine triangulation of the surface that has colored vertices derived from three-dimensional colored scan data, said generating step comprising generating the texture map as a color map containing an array of texels; and

wherein a first texel in the array of texels retains color information derived from mapping a center and at least a first corner of the first texel to respective spatial points on the coarse triangulation.

21. The method of claim 20, wherein the first texel retains color information derived from mapping a center and each corner of the first texel to respective spatial points on the coarse triangulation.

22. The method of claim 21, wherein the color information is derived from mapping the respective spatial points on the coarse triangulation along normal projections to respective object points on the fine triangulation.

23. A method of modeling a three-dimensional colored object, comprising the step of:

generating a colored model of a surface of the colored object from a coarse triangulation of the surface and a texture man containing information obtained by manning points within the texture map to a fine triangulation of the surface that has colored vertices derived from three-dimensional colored scan data, said generating step comprising generating the texture map as a color map containing an array of texels having a plurality of texture domains therein;

wherein a first texture domain in the plurality of texture domains comprises I columns and k rows of texels;

wherein a first texel in the Ith column of the first texture domain retains color information derived from mapping at least one of a center or corner of the first texel to a first patch on the coarse triangulation; and

wherein a second texel in the first texture domain retains color information derived from mapping at least one of a center or corner of the second texel to a second patch on the coarse triangulation that is contiguous with the first patch at a patch boundary.

24. A method of modeling a three-dimensional colored object, comprising the steps of:

generating a coarse triangulation model from a fine triangulation model of a colored object that has colored vertices corresponding to physical locations on the colored object that have been digitally scanned; and

generating a texture map having an array of texture domains therein that retain color information derived by mapping each texture domain to respective quadrangular patches on the coarse triangulation model and mapping spatial points on the quadrangular patches to object points on the fine triangulation model;

wherein said step of generating a texture map comprises generating the texture map as a color map containing an array of texels having a plurality of texture domains therein;

wherein a first texture domain in the plurality of texture domains comprises I columns and k rows of texels;

wherein a first texel in the Ith column of the first texture domain retains color information derived from mapping at least one of a center or corner of the first texel to a first quadrangular patch on the coarse triangulation model; and

wherein a second texel in the first texture domain retains color information derived from mapping at least one of a center or corner of the second texel to a second quadrangular patch on the coarse triangulation model that is contiguous with the first quadrangular patch at a patch boundary.

25. A method of modeling a three-dimensional colored object, comprising the steps of:

capturing colored shape detail as three-dimensional point data from a physical object, with each datum comprising three real numbers providing geometric information and three integer numbers providing color information; and

converting the captured color shape detail into a coarse digital model of the physical object and a model enhancing texture map that maps points therein to the coarse digital model and retains color information derived from mapping points within the coarse digital model to a finer digital model derived from the captured colored shape detail, said converting step comprising;

generating a fine triangulation model of the physical object by wrapping the three-dimensional point data;

generating a fine quadrangular grid model of the physical object by shaping the wrapped point data; and

simplifying the fine quadrangular grid model into a coarse quadrangular grid model by removing tracks from the fine quadrangular grid model that contribute relatively little to the shape of the fine quadrangular grid model when compared to other tracks within the fine quadrangular grid model.

26. The method of claim 25, wherein said converting step comprises:

generating a first map that maps each quadrangular patch on the coarse quadrangular grid model to a respective texture domain in the texture map; and

generating a second map that maps spatial points on the coarse quadrangular grid model to object points on the fine triangulation model.

27. The method of claim 26, wherein the texture map is created so that each texture domain has at least two texels therein that map to different patches on the coarse quadrangular grid model.

28. A method of modeling a colored object, comprising the steps of:

automatically generating a triangulation model of the colored object that is defined by a plurality of quadrangular patches that extend within respective continuous grid tracks that loop around the triangulation model, from three-dimensional colored scan data that identify location and color of points on the colored object; and

generating a texture map that contains information derived from mapping spatial points on the triangulation model to object points on another model derived from the colored scan data;

wherein the texture map comprises a plurality of texture domains; and

wherein a first texture domain in the plurality of texture domains includes interior texels that map to a first quadrangular patch in the triangulation model and peripheral texels that map to at least a second quadrangular patch in the triangulation model.

29. The method of claim 28, wherein the second quadrangular patch shares a patch boundary with the first quadrangular patch.

30. A method of modeling a three-dimensional object, comprising the step of:

generating a texture map having at least a first texture domain therein that comprises at least a first peripheral texel retaining color information derived from mapping the first peripheral texel to a first patch on a quadrangulation model of the three-dimensional object and at least a first interior texel retaining color information derived from mapping the first interior texel to a second patch on the quadrangulation model.

31. The method of claim 30, wherein the first and second patches share a common patch boundary.

32. A method of modeling a three-dimensional object, comprising the step of:

decimating a fine quadrangular grid model of the three-dimensional object into a coarse quadrangular grid model of the three-dimensional object by removing tracks from the fine quadrangular grid model that contribute relatively little to the shape of the fine quadrangular grid model when compared to other tracks within the fine quadrangular grid model.

33. The method of claim 32, wherein said decimating step is performed using a sequence of edge contractions that are prioritized by an error function.

34. The method of claim 32, wherein said decimating step comprises the steps of:

creating a dual graph of the fine quadrangular grid model; and

removing whiskers from the dual graph using a simplification operation that is driven by a priority queue that order whiskers by a respective error their removal causes to the quadrangular grid.

35. A computer program product that models three-dimensional objects and comprises a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:

computer-readable program code that generates a coarse triangulation model from a fine triangulation model of a colored object that has colored vertices corresponding to physical locations on the colored object that have been digitally scanned; and

computer-readable program code that generates a texture map having an array of texture domains therein that retain color information derived by mapping texels within the texture domains to spatial points on quadrangular patches on the coarse triangulation model and to object points on the fine triangulation model;

wherein said computer-readable program code that generates a texture map comprises computer-readable program code that generates a texture map as a color map containing an array of texels having a plurality of texture domains therein;

wherein a first texture domain in the plurality of texture domains comprises I columns and k rows of texels;

wherein a first texel in the Ith column of the first texture domain retains color information derived from mapping at least one of a center or corner of the first texel to a first quadrangular patch on the coarse triangulation model; and

wherein a second texel in the first texture domain retains color information derived from mapping at least one of a center or corner of the second texel to a second quadrangular patch on the coarse triangulation model that is contiguous with the first quadrangular patch at a patch boundary.

36. A computer program product that models three-dimensional colored objects and comprises a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising:

computer-readable program code that decimates a fine quadrangular grid model of the three-dimensional object into a coarse quadrangular grid model of the three-dimensional object by removing tracks from the fine quadrangular grid model that contribute relatively little to the shape of the fine quadrangular grid model when compared to other tracks within the fine quadrangular grid model.

37. The computer program product of claim 36, wherein said computer-readable program code that decimates a fine quadrangular grid model of the three-dimensional object into a coarse quadrangular grid model of the three-dimensional object, comprises:

computer-readable program code that creates a dual graph of the fine quadrangular grid model; and

computer-readable program code that removes whiskers from the dual graph using a simplification operation that is driven by a priority queue that order whiskers by a respective error their removal causes to the quadrangular grid.