Method and system for rendering 3D distance fields

Patent metadata

Field	Value
Publication number	US-9336624-B2
Application number	US-24654408-A
Country	US
Kind code	B2
Filing date	Oct 7, 2008
Priority date	Oct 7, 2008
Publication date	May 10, 2016
Grant date	May 10, 2016

Abstract

A method and system renders a 3D model of a 3D object as an image including image samples. The 3D model is a distance field, and the distance field includes surface cells representing portions of a surface of the 3D object. A set of image samples in the image is determined in an object-order phase for each surface cell. Each surface cell is then processed independent of other surface cells. The processing casts a ray, in an image order phase from each image sample in the set of image samples, through the surface cell to determine a contribution of the surface cell to the image sample, and then the image is rendered.

First claim

We claim:

1. A method for rendering a 3D model of a 3D object as an image including image samples, wherein the 3D model is a distance field, and the distance field includes surface cells representing portions of a surface of the 3D object, comprising the steps of:
determining, in an object-order phase for each surface cell, a set of image samples in the image;
processing each surface cell, independent of other surface cells, wherein the processing of each surface cell further comprises:
casting a ray, in an image order phase from each image sample in the set of image samples, through the surface cell to determine a contribution of the surface cell to the image sample, wherein the casting determines, using the distance field, if an entry point where the ray enters the surface cell and an exit point where the ray exits the surface cell are both inside the surface, and if true, the contribution is determined from the entry point; and

rendering the image, wherein steps of the method are performed by a processor.

2. The method of claim 1 , wherein the surface cell has a bounding box, and the determining further comprises:
projecting the bounding box onto the image to determine the set of image samples.

3. The method of claim 1 , wherein the image samples have a different resolution than pixels in the image that is rendered.

4. The method of claim 1 , wherein the distance field includes distance field samples., and further comprising:
reconstructing the distances from the distance field samples using a continuous function.

5. The method of claim 4 , wherein the distance field samples are signed, and a change of the sign of the distance field samples of two adjacent vertices of the surface cell indicates that the portion of the surface intersects an edge of the surface cell between the two adjacent vertices at a point of intersection.

6. The method of claim 5 , wherein the method includes cell coordinates, model coordinates, eye coordinates, clip coordinates, and window coordinates, and further comprising:
locating a minimum and maximum of the point an intersection using the window coordinates.

7. The method of claim 6 , further comprising:
transforming the cell coordinates to the window coordinates, via, the model coordinates, the eye coordinates, and clip coordinates using a set of transformation matrices;
transforming the coordinates of he point of intersection to the clip coordinates; and
comparing the coordinates of the point of intersection with a range [−1, 1] to determine if the portion of the surface is visible.

8. The method of claim 5 , further comprising:
reconstructing the distance field at the point of intersection.

9. The method of claim 1 , further comprising:
projecting the surface cell to the set of pixels using window coordinates.

10. The method of claim 9 , further comprising:
transforming parameters of the rays ray parameters from window coordinates to cell coordinates.

11. The method of claim 1 , further comprising:
combining the contributions using a depth buffer.

12. The method of claim 1 , wherein each surface cell is processed only once for the determining and casting steps.

13. The method of claim 1 , wherein the image is super-sampled.

14. The method of claim 1 , wherein the image is sub-sampled.

15. The method of claim 1 , wherein the method uses cell coordinates, model coordinates, eye coordinates, clip coordinates, and window coordinates.

16. The method of claim 15 , further comprising:
transforming the cell coordinates to the window coordinates, via the model coordinates, the eye coordinates, and clip coordinates using a set of transformation matrices.

17. The method of claim 16 , in which a cell matrix

C
=

(

C
S

0

0

C
Ox

0

C
S

0

C
Oy

0

0

C
S

C
Oz

0

0

0

1

)

,

is used to transform the cells coordinates to the model coordinates, where C S is size of the surface cell, and C O are coordinates of an origin of the surface cell in the model coordinates.

18. The method of claim 16 , wherein the eye coordinates are transformed to the clip coordinates by a projection matrix using a size of a viewing frustrum.

19. The method of claim 18 , wherein the projection matrix represents an orthographic projection.

20. The method of claim 18 , wherein the projection matrix represents a perspective projection.

21. The method of claim 16 , wherein the clip coordinates of visible portions of the object lie in a unit cube (−1, −1, −1) to (1, 1, 1).

22. The method of claim 21 , wherein the visible portions are determined using normals of the surface cells.

23. The method of claim 22 , further comprising:
transforming coordinates of the normals from the object coordinates to the eye coordinates by multiplication with a transposed inverse of a modelview transformation.

24. The method of claim 16 , wherein the clip coordinates are transformed to the window coordinates by the viewport matrix, which depends on a size of the image.

25. The method of claim 16 , in which the transforming is linear.

26. The method of claim 16 , in which the transforming is non-linear.

27. The method of claim 1 , wherein the distance field includes distance field samples, and further comprising:
reconstructing the distances from the distance field using a tri-linear reconst

Assignees

• Sullivan Alan
• Frisken Sarah F
• Perry Ronald N
• Mitsubishi Electric Res Lab

Inventors

• Sullivan Alan
• Frisken Sarah F
• Perry Ronald N

Classifications

• G06T15/08 Primary

  Volume rendering · CPC title

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T15/06

  Ray-tracing · CPC title

• G06T19/00

  Manipulating three-dimensional [3D] models or images for computer graphics · CPC title

• G06T17/10

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title