Isosurface extraction into splat hierarchy

• US 7,272,608 B2
• Filed: 12/31/2003
• Issued: 09/18/2007
• Est. Priority Date: 11/27/2002
• Status: Expired due to Fees

• Current Assignee: Zyvex Labs, Llc
• Original Assignee: Zyvex Labs, Llc
• Inventors: Parker, Eric, Udeshi, Tushar
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): RICE, HELENE R
• Application Number:
  US10/749,256
• Publication Number:
  US 20040162839A1
• Time in Patent Office: 1,357 Days
• Field of Search: 707/100, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes

Abstract

A method of extracting isosurface data from hierarchical node data, including providing hierarchical node data representing an object, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes. The method also includes determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, wherein each of the plurality of leaf node splats is based on scalar data corresponding to at least one of the plurality of leaf nodes. A plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface is also determined, wherein each of the plurality of non-leaf node splats is based on a plurality of splats each corresponding to a lower hierarchical node.

Claims

1. A method of extracting isosurface data from hierarchical node data, comprising:

providing hierarchical node data representing an object, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes; and

building a splat hierarchy from the hierarchical node data without converting the hierarchical node data into mesh data, wherein building the splat hierarchy comprises;

determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

determining a plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface, each of the plurality of non-leaf node splats based on a plurality of splats each corresponding to a lower hierarchical node.

2. The method of claim 1 wherein the hierarchical node data is 2-dimensional.

3. The method of claim 1 wherein the hierarchical node data is 3-dimensional.

4. The method of claim 1 wherein the hierarchical node data is in octree format.

5. The method of claim 1 wherein the hierarchical node data is in shared octree format.

6. The method of claim 1 wherein at least one of the pluralities of leaf node splats and non-leaf node splats are determined recursively.

7. The method of claim 6 wherein at least one of the pluralities of leaf node splats and non-leaf node splats are determined employing results matching.

8. The method of claim 1 wherein the scalar data is representative of leaf node material occupancy percentages.

9. The method of claim 1 wherein determining the plurality of leaf node splats includes approximating isosurface locations within at least one of the leaf nodes based on the scalar values.

10. The method of claim 9 wherein ones of the plurality of leaf node splats are each partially defined by a leaf node splat center that is an average of intermediate edge point locations, wherein the intermediate edge points approximate a predetermined scalar value along an intersection between the isosurface and leaf node faces.

11. The method of claim 9 wherein ones of the plurality of leaf node splats are each partially defined by a leaf node splat normal that approximates an isosurface normal.

12. The method of claim 9 wherein ones of the plurality of leaf node splats are each partially defined by a radius determined such that each of the of leaf node splats divides each corresponding leaf node into two portions.

13. The method of claim 12 wherein the radius of each of the plurality of leaf node splats is the minimum radius that permits the corresponding leaf node splat to divide the corresponding leaf node into two portions.

14. The method of claim 1 wherein each of the plurality of non-leaf node splats is partially defined by a plane based on a least square fit of a plurality of lower hierarchical splats.

15. The method of claim 1 wherein each of the plurality of non-leaf nodes splats is partially defined by a radius determined such that each of the of non-leaf node splats divides each corresponding non-leaf node into two portions.

16. The method of claim 15 wherein the radius of each of the plurality of non-leaf node splats is the minimum radius that permits the corresponding non-leaf node splat to divide the corresponding non-leaf node into two portions.

17. The method of claim 1 wherein each of the plurality of non-leaf node splats is partially defined by a normal and a cone encompassing a plurality of lower hierarchy splat normals.

18. The method of claim 1 further comprising compressing a splat hierarchy populated by the pluralities of leaf node splats and non-leaf node splats.

19. The method of claim 18 wherein compressing includes replacing a plurality of substantially coplanar lower hierarchy splats with a combine splat substantially coplanar with the plurality of lower hierarchy splats, having a radius larger than the individual radii of the plurality of lower hierarchy splats, and having a splat cone substantially encompassing a plurality of children splat normals.

20. A method of rendering isosurface data, comprising:

providing hierarchical node data representing an object having an isosurface, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes;

building a splat hierarchy from the hierarchical node data without converting the hierarchical node data into mesh data, wherein building the splat hierarchy comprises;

determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

determining a plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface, each of the plurality of non-leaf node splats based on a plurality of splats each corresponding to a lower hierarchical node; and

rendering a plurality of splats partially populating the splat hierarchy resulting from the determination of the pluralities of leaf node splats and non-leaf node splats.

21. The method of claim 20 wherein the plurality of rendered splats satisfy visibility conditions, wherein the splat hierarchy also includes a plurality of non-rendered splats.

22. The method of claim 21 wherein one of the visibility conditions is backface culling.

23. The method of claim 21 wherein one of the visibility conditions is viewpoint frustum culling.

24. The method of claim 21 wherein one of the visibility conditions compares splat screen sizes to threshold values.

25. The method of claim 20 wherein the rendering is performed recursively.

26. A processing system for extracting isosurface data from hierarchical node data, comprising:

means for providing hierarchical node data representing an object, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes; and

means for building a splat hierarchy from the hierarchical node data without converting the hierarchical node data into mesh data, wherein the means for building the splat hierarchy comprises;

means for determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

means for determining a plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface, each of the plurality of non-leaf node splats based on a plurality of splats each corresponding to a lower hierarchical node.

27. The system of claim 26 wherein at least one of the means for determining the pluralities of leaf node splats and non-leaf node splats includes means for recursive determination.

28. The system of claim 27 wherein the recursive determination means is configured to employ results matching.

29. The system of claim 26 wherein the scalar data is representative of leaf node material occupancy percentages.

30. A processing system for rendering isosurface data, comprising:

means for providing hierarchical node data representing an object, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes;

means for building a splat hierarchy from the hierarchical node data without converting the hierarchical node data into mesh data, wherein the means for building the splat hierarchy comprises;

means for determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

means for determining a plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface, each of the plurality of non-leaf node splats based on a plurality of splats each corresponding to a lower hierarchical node; and

means for rendering a plurality of splats partially populating the splat hierarchy.

31. The system of claim 30 wherein the means for rendering the plurality of splats includes means for verifying that ones of the plurality of splats satisfy visibility conditions, wherein the splat hierarchy also includes a plurality of non-rendered splats.

32. The system of claim 31 wherein one of the visibility conditions is backface culling.

33. The system of claim 31 wherein one of the visibility conditions is viewpoint frustum culling.

34. The system of claim 31 wherein one of the visibility conditions compares splat screen sizes to threshold values.

35. The system of claim 30 wherein the rendering means includes means for performing rendering recursively.

36. A program product, comprising:

a computer-readable storage medium;

means recorded on the medium for providing hierarchical node data representing an object, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes; and

means recorded on the medium for building a splat hierarchy from the hierarchical node data without converting the hierarchical node data into mesh data, wherein the means for building the splat hierarchy comprises;

means recorded on the medium for determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

means recorded on the medium for determining a plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface, each of the plurality of non-leaf node splats based on a plurality of splats each corresponding to a lower hierarchical node.

37. The program product of claim 36 wherein at least one of the means for determining the pluralities of leaf node splats and non-leaf node splats includes means recorded on the medium for recursive determination.

38. The program product of claim 37 wherein the recursive determination means is configured to employ results matching.

39. The program product of claim 36 wherein the storage medium is a magnetic recording medium.

40. The program product of claim 36 wherein the storage medium is an optical recording medium.

41. The program product of claim 36 wherein the storage medium is a network distribution medium.

42. A program product, comprising:

a computer-readable storage medium;

means recorded on the medium for providing hierarchical node data representing an object, the hierarchical node data including a lowest hierarchy level having a plurality of leaf nodes and a plurality of higher hierarchy levels each having a plurality of non-leaf nodes each encompassing ones of the plurality of leaf nodes;

means recorded on the medium for building a splat hierarchy from the hierarchical node data without converting the hierarchical node data into mesh data, wherein the means for building the splat hierarchy comprises;

means recorded on the medium for determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

means recorded on the medium for determining a plurality of non-leaf node splats each corresponding to one of the plurality of non-leaf nodes that includes a portion of the isosurface, each of the plurality of non-leaf node splats based on a plurality of splats each corresponding to a lower hierarchical node; and

means recorded on the medium for rendering a plurality of splats partially populating the splat hierarchy.

43. The program product of claim 42 wherein the means for rendering the plurality of splats includes means for verifying that ones of the plurality of splats satisfy visibility conditions, wherein the splat hierarchy also includes a plurality of non-rendered splats.

44. The program product of claim 43 wherein one of the visibility conditions is backface culling.

45. The program product of claim 43 wherein one of the visibility conditions is viewpoint frustum culling.

46. The program product of claim 43 wherein one of the visibility conditions compares splat screen sizes to threshold values.

47. The program product of claim 42 wherein the rendering means includes means for performing rendering recursively.

48. The program product of claim 42 wherein the storage medium is a magnetic recording medium.

49. The program product of claim 42 wherein the storage medium is an optical recording medium.

50. The program product of claim 42 wherein the storage medium is a network distribution medium.

51. A method of extracting isosurface data from a scalar field, comprising:

providing scalar field data; and

building a splat hierarchy from the scalar field data without converting the scalar field data into mesh data, including;

determining a plurality of leaf node splats each corresponding to one of the plurality of leaf nodes that includes a portion of an isosurface, each of the plurality of leaf node splats based on scalar data corresponding to at least one of the plurality of leaf nodes; and

determining a plurality of non-leaf node splats each based on a plurality of lower hierarchical splats.