Object representation using distance functions

• US 20060077203A1
• Filed: 03/17/2005
• Published: 04/13/2006
• 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 Coutinho
• Granted Patent: US 9,024,949 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• 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 method comprising:

constructing a bounding box 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.

2. The method of claim 1 wherein constructing comprises aligning the bounding box with at least one axis of the 3-D coordinate system.

3. The method of claim 2 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.

4. The method of claim 1 wherein projecting comprises:

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

5. The method of claim 4 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.

6. The method of claim 4 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.

7. The method of claim 1 wherein computing comprises:

normalizing the parameterization value with respect to a reference value.

8. The method of claim 1 wherein projecting comprises:

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

9. The method of claim 7 further comprising:

saving the normalized parameterization value.

10. A method comprising:

retrieving a normalized parameterization value associated with a grid point on a bounding plane of a bounding box 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.

11. The method of claim 10 wherein reconstructing comprises

constructing the bounding box.

12. The method of claim 11 wherein constructing the bounding box comprises

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

13. The method of claim 12 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

14. The method of claim 10 wherein reconstructing comprises

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

15. The method of claim 10 wherein reconstructing comprises:

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

16. The method of claim 10 wherein reconstructing comprises:

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

17. An article of manufacture comprising:

a machine-accessible medium including data that, when accessed by a machine, causes the machine to perform operations comprising;

constructing a bounding box 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 article of manufacture of claim 17 wherein the data causing the machine to perform constructing 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.

19. The article of manufacture of claim 18 wherein the data causing the machine to perform constructing further comprises data that, when accessed by the machine, causes 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.

20. The article of manufacture of claim 17 wherein the data causing the machine to perform projecting comprises data that, when accessed by the machine, causes 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.

21. The article of manufacture of claim 20 wherein the data causing the machine to perform computing comprises data that, when accessed by the machine, causes 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.

22. The article of manufacture of claim 20 wherein the data causing the machine to perform computing comprises data that, when accessed by the machine, causes 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.

23. The article of manufacture of claim 17 wherein the data causing the machine to perform computing comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

normalizing the parameterization value with respect to a reference value.

24. The article of manufacture of claim 17 wherein the data causing the machine to perform projecting comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

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

25. The article of manufacture of claim 23 the data further comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

saving the normalized parameterization value.

26. An article of manufacture comprising:

a machine-accessible medium including data that, when accessed by a machine, causes the machine to perform operations comprising;

retrieving a normalized parameterization value associated with a grid point on a bounding plane of a bounding box 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.

27. The article of manufacture of claim 26 wherein the data causing the machine to perform reconstructing comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

constructing the bounding box.

28. The article of manufacture of claim 27 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.

29. The article of manufacture of claim 28 wherein the data causing the machine to perform constructing further comprises data that, when accessed by the machine, causes 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.

30. The article of manufacture of claim 26 wherein the data causing the machine to perform reconstructing comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

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

31. The article of manufacture of claim 26 wherein the data causing the machine to perform reconstructing comprises data that, when accessed by the machine, causes the machine to perform operations comprising:

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

32. The article of manufacture of claim 26 wherein the data causing the machine to perform reconstructing comprises data that, when accessed by the machine, causes 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.

33. 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 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 system of claim 33 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.

35. The system of claim 34 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.

36. The system of claim 33 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.

37. The system of claim 36 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.

38. The system of claim 36 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.

39. The system of claim 33 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.

40. The system of claim 33 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.

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

saving the normalized parameterization value.

42. 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 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 system of claim 42 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.

44. The system of claim 43 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.

45. The system of claim 44 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.

46. The system of claim 42 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.

47. The system of claim 42 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.

48. The system of claim 42 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.