Object representation using distance functions

• US 9,024,949 B2
• Filed: 03/17/2005
• Issued: 05/05/2015
• Est. Priority Date: 10/13/2004
• Status: Active Grant

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Pictures Entertainment Incorporated (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Pictures Entertainment Incorporated (Sony Group Corp.)
• Inventors: Marino, Sebastian Mark, Neto, Murilo Gondim
• Primary Examiner(s): Richer, Aaron M
• Assistant Examiner(s): Prendergast, Roberta D
• Application Number:
  US11/083,306
• Publication Number:
  US 20060077203A1
• Time in Patent Office: 3,701 Days
• Field of Search: 345/419, 345/426
• US Class Current: 345/426
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

An embodiment of the present invention includes a technique to represent three-dimensional (3-D) object using signed distance functions. A bounding box containing an object is constructed in a 3-D coordinate system. The bounding box has at least a bounding plane. A ray is projected from a grid point on the bounding plane to the object with a pre-defined direction. The ray intersects a surface of the object at an intersection point. A parameterization value of the intersection point associated with the grid point is computed. The parameterization value corresponds to a distance from the grid point to the intersection point.

Claims

1. A system comprising:

a processor;

a memory coupled to the processor to contain instructions, when executed by the processor, that perform operations comprising;

constructing a bounding box having a volumetric shape and containing a three-dimensional (3-D) object in a 3-D coordinate system, the bounding box having at least a bounding plane having a grid point;

projecting a ray from the grid point on the bounding plane to the object with a pre-defined direction, the ray intersecting a surface of the object at an intersection point; and

computing a parameterization value of the intersection point associated with the grid point, the parameterization value corresponding to a distance from the grid point to the intersection point.

2. The system of claim 1 wherein the instructions causing the processor to perform constructing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

aligning the bounding box with at least one axis of the 3-D coordinate system.

3. The system of claim 2 wherein the instructions causing the processor to perform constructing further comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

determining principal resolution of a principal axis of the bounding box, the principal axis corresponding to a largest side of the bounding box; and

determining remaining resolutions of remaining axes according to the principal resolution.

4. The system of claim 1 wherein the instructions causing the processor to perform projecting comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

projecting the ray to the object at the intersection point being one of an entry point and an exit point.

5. The system of claim 4 wherein the instructions causing the processor to perform computing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

computing one of an entry value and an exit value corresponding to one of distances from the grid point to the entry point and the exit point, respectively.

6. The system of claim 4 wherein the instructions causing the processor to perform computing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

computing the distance being a positive value when the surface lies on a first side of the bounding plane and a negative value when the surface lies on a second side of the bounding plane.

7. The system of claim 1 wherein the instructions causing the processor to perform computing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

normalizing the parameterization value with respect to a reference value.

8. The system of claim 1 wherein the instructions causing the processor to perform projecting comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

projecting the ray to the object intersecting multiple surfaces of the object at multiple intersecting points.

9. The system of claim 7 the instructions further comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

saving the normalized parameterization value.

10. A system comprising:

a processor;

a memory coupled to the processor to contain instructions, when executed by the processor, that perform operations comprising;

retrieving a normalized parameterization value associated with a grid point on a bounding plane of a bounding box having a volumetric shape and containing a three-dimensional (3-D) object in a 3-D coordinate system, the normalized parameterization value corresponding to a distance from the grid point to an object point of the object, the object point being an intersection point between a ray projected from the grid point to a surface of the object with a pre-defined direction; and

reconstructing an object point of the object using the normalized parameterization value.

11. The system of claim 10 wherein the instructions causing the processor to perform reconstructing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

constructing the bounding box.

12. The system of claim 11 wherein the instructions causing the processor to perform constructing the bounding box comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

aligning the bounding box with at least one axis of the 3-D coordinate system.

13. The system of claim 12 wherein the instructions causing the processor to perform constructing further comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

determining principal resolution of a principal axis of the bounding box, the principal axis corresponding to a largest side of the bounding box; and

determining remaining resolutions of remaining axes according to the principal resolution.

14. The system of claim 10 wherein the instructions causing the processor to perform reconstructing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

de-normalizing the normalized parameterization value using a reference value.

15. The system of claim 10 wherein the instructions causing the processor to perform reconstructing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

determining the intersection point being one of an entry point and an exit point.

16. The system of claim 10 wherein the instructions causing the processor to perform reconstructing comprises instructions that, when accessed by the processor, causes the processor to perform operations comprising:

determining a relative side of the surface with respect to the bounding plane using a sign of the distance.

17. A computerized method comprising:

constructing a bounding box having a volumetric shape and containing a three-dimensional (3-D) object in a 3-D coordinate system, the bounding box having at least a bounding plane;

projecting a ray from a grid point on the bounding plane to the object with a pre-defined direction, the ray intersecting a surface of the object at an intersection point; and

computing a parameterization value of the intersection point associated with the grid point, the parameterization value corresponding to a distance from the grid point to the intersection point.

18. The method of claim 17 wherein constructing comprises

aligning the bounding box with at least one axis of the 3-D coordinate system.

19. The method of claim 18 wherein constructing further comprises:

determining principal resolution of a principal axis of the bounding box, the principal axis corresponding to a largest side of the bounding box; and

determining remaining resolutions of remaining axes according to the principal resolution.

20. The method of claim 17 wherein projecting comprises:

projecting the ray to the object at the intersection point being one of an entry point and an exit point.

21. The method of claim 20 wherein computing comprises:

computing one of an entry value and an exit value corresponding to one of distances from the grid point to the entry point and the exit point, respectively.

22. The method of claim 20 wherein computing comprises:

computing the distance being a positive value when the surface lies on a first side of the bounding plane and a negative value when the surface lies on a second side of the bounding plane.

23. The method of claim 17 wherein computing comprises:

normalizing the parameterization value with respect to a reference value.

24. The method of claim 17 wherein projecting comprises:

projecting the ray to the object intersecting multiple surfaces of the object at multiple intersecting points.

25. The method of claim 23 further comprising:

saving the normalized parameterization value.

26. A computerized method comprising:

retrieving a normalized parameterization value associated with a grid point on a bounding plane of a bounding box having a volumetric shape and containing a three-dimensional (3-D) object in a 3-D coordinate system, the normalized parameterization value corresponding to a distance from the grid point to an object point of the object, the object point being an intersection point of a ray projected from the grid point to a surface of the object with a pre-defined direction; and

reconstructing an object point of the object using the normalized parameterization value.

27. The method of claim 26 wherein reconstructing comprises

constructing the bounding box.

28. The method of claim 27 wherein constructing the bounding box comprises

aligning the bounding box with at least one axis of the 3-D coordinate system.

29. The method of claim 28 wherein constructing further comprises:

determining principal resolution of a principal axis of the bounding box, the principal axis corresponding to a largest side of the bounding box; and

determining remaining resolutions of remaining axes according to the principal resolution.

30. The method of claim 26 wherein reconstructing comprises

de-normalizing the normalized parameterization value using a reference value.

31. The method of claim 26 wherein reconstructing comprises:

determining the intersection point being one of an entry point and an exit point.

32. The method of claim 26 wherein reconstructing comprises:

determining a relative side of the surface with respect to the bounding plane using a sign of the distance.

33. An article of manufacture comprising:

a machine-accessible non-transitory storage medium including data that, when accessed by a machine, cause the machine to perform operations comprising;

constructing a bounding box having a volumetric shape and containing a three-dimensional (3-D) object in a 3-D coordinate system, the bounding box having at least a bounding plane;

projecting a ray from a grid point on the bounding plane to the object with a pre-defined direction, the ray intersecting a surface of the object at an intersection point; and

computing a parameterization value of the intersection point associated with the grid point, the parameterization value corresponding to a distance from the grid point to the intersection point.

34. The article of manufacture of claim 33 wherein the data causing the machine to perform constructing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

aligning the bounding box with at least one axis of the 3-D coordinate system.

35. The article of manufacture of claim 34 wherein the data causing the machine to perform constructing further comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

determining principal resolution of a principal axis of the bounding box, the principal axis corresponding to a largest side of the bounding box; and

determining remaining resolutions of remaining axes according to the principal resolution.

36. The article of manufacture of claim 33 wherein the data causing the machine to perform projecting comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

projecting the ray to the object at the intersection point being one of an entry point and an exit point.

37. The article of manufacture of claim 36 wherein the data causing the machine to perform computing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

computing one of an entry value and an exit value corresponding to one of distances from the grid point to the entry point and the exit point, respectively.

38. The article of manufacture of claim 36 wherein the data causing the machine to perform computing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

computing the distance being a positive value when the surface lies on a first side of the bounding plane and a negative value when the surface lies on a second side of the bounding plane.

39. The article of manufacture of claim 33 wherein the data causing the machine to perform computing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

normalizing the parameterization value with respect to a reference value.

40. The article of manufacture of claim 33 wherein the data causing the machine to perform projecting comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

projecting the ray to the object intersecting multiple surfaces of the object at multiple intersecting points.

41. The article of manufacture of claim 39 wherein the data further comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

saving the normalized parameterization value.

42. An article of manufacture comprising:

a machine-accessible non-transitory storage medium including data that, when accessed by a machine, cause the machine to perform operations comprising;

retrieving a normalized parameterization value associated with a grid point on a bounding plane of a bounding box having a volumetric shape and containing a three-dimensional (3-D) object in a 3-D coordinate system, the normalized parameterization value corresponding to a distance from the grid point to an object point of the object, the object point being an intersection point between a ray projected from the grid point to a surface of the object with a pre-defined direction; and

reconstructing an object point of the object using the normalized parameterization value.

43. The article of manufacture of claim 42 wherein the data causing the machine to perform reconstructing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

constructing the bounding box.

44. The article of manufacture of claim 43 wherein the data causing the machine to perform constructing the bounding box comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

aligning the bounding box with at least one axis of the 3-D coordinate system.

45. The article of manufacture of claim 44 wherein the data causing the machine to perform constructing further comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

determining principal resolution of a principal axis of the bounding box, the principal axis corresponding to a largest side of the bounding box; and

determining remaining resolutions of remaining axes according to the principal resolution.

46. The article of manufacture of claim 42 wherein the data causing the machine to perform reconstructing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

de-normalizing the normalized parameterization value using a reference value.

47. The article of manufacture of claim 42 wherein the data causing the machine to perform reconstructing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

determining the intersection point being one of an entry point and an exit point.

48. The article of manufacture of claim 42 wherein the data causing the machine to perform reconstructing comprise data that, when accessed by the machine, cause the machine to perform operations comprising:

determining a relative side of the surface with respect to the bounding plane using a sign of the distance.