Data rendering method for volumetric 3D displays

• US 20060017724A1
• Filed: 07/20/2005
• Published: 01/26/2006
• Est. Priority Date: 07/21/2004
• Status: Active Grant

• Current Assignee: Che-Chih Tsao
• Original Assignee: Che-Chih Tsao
• Inventors: Tsao, Che-Chih
• Granted Patent: US 7,701,455 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 15/04 Texture mapping

Abstract

The fundamental concept of expressing brightness level of a geometric primitive is to control the number of rendered display elements, representing desired brightness level, in the geometric primitive as a fraction of the maximum number of display elements, representing the maximum brightness level, that can be placed in it. There are two approaches to achieve this control: Point-based Rendering and Intersection-based Rendering. In Point-based Rendering, a geometric primitive is converted into a representation of sampling points and then the sampling points are rendered. In Intersection-based Rendering, the intersections of a geometric primitive with the frame slices are rendered. The basic procedure to render a texture-mapped surface is to divide the surface into a number of regions, each region having a different intensity range, and then render each region with a different density of display elements to represent different brightness level. The procedure of rendering a 3D volume with gray scale distribution is similar.

Claims

1. Method of displaying a geometric primitive with a desired brightness level in actual 3D space in a volumetric 3D display, said geometric primitive being a line or a surface, the volumetric 3D display comprising spatially distributed display elements for displaying volumetric 3D images, the method including the steps of:

(1) determining the minimum number, Nge_op, of display elements required to display said geometric primitive at full brightness, Br_op;

(2) determining the desired number, Nge, of display elements to display said geometric primitive at the desired brightness level based on the following relation;

(Nge/Nge_—

op)×

(Bge/Bge_—

f)=Br/Br_op,

wherein Br representing the desired brightness level of said geometric primitive, Bge_f representing full brightness level of said display element, Bge representing brightness level of said display element to be used to render said geometric primitive;

(3) rendering said geometric primitive with said desired number of display elements.

2. Method of claim 1, wherein

the step of determining the minimum number of display elements including the step of determining a reference number, Ns_op, of sampling points for representing said geometric primitive at full brightness, each said sampling point mapping to a pre-determined number, N_d, of display elements when said sampling point is at full brightness;

the step of determining the desired number of display elements including the step of determining a desired number, Ns, of sampling points for representing said geometric primitive and a desired dilating number, n_d, of display elements for each said sampling point based on the following relation;

[(Ns×

n_)/(Ns_—

op×

N_—

d)×

(Bge/Bge_—

f)=Br/Br_—

op;

the step of rendering said geometric primitive including the steps of;

(i) distributing said desired number of sampling points in said geometric primitive and computing coordinates of each of the desired sampling points;

(ii) rendering each of the computed sampling points with said dilating number of display elements.

3. Method of claim 2, wherein

said geometric primitive being a line;

the step of determining a reference number of sampling points for displaying said geometric primitive at full brightness including the steps of;

(a) computing the minimum number of sampling points required to fill the line with said display elements in three orthogonal directions respectively;

(b) selecting the maximum of the three numbers computed from step (a) as said reference number, Ns_op;

the step of distributing said desired number of sampling points including the step of distributing the sampling points evenly in the line.

4. Method of claim 2, wherein

said geometric primitive being a surface;

said sampling points being distributed among one or more sub-surfaces, said sub-surfaces being closely stacked with a spacing among adjacent sub-surfaces;

the step of determining a reference number, Ns_op, of sampling points for representing said geometric primitive at full brightness including the step of determining an optimum number of sampling points for each sub-surface, the optimum number of sampling points representing a sub-surface at full brightness, the sum of all said optimum numbers for said sub-surfaces being equal to Ns_op;

the step of determining a desired number, Ns, of sampling points for representing said geometric primitive including the step of selecting a number of sampling points for each sub-surface, the total number of sampling points on all said sub-surfaces being equal to Ns;

the step of distributing said desired number of sampling points including the steps of distributing the selected number of sampling points for each sub-surface in each corresponding sub-surface.

5. Method of claim 4, further including the step of determining a minimum value of said spacing based on orientation and position of said surface with respect to spatial distribution of the display elements so that display elements mapped by adjacent sampling points do not overlap.

6. Method of claim 4, wherein

said surface being a triangular surface, said sub-surfaces being triangular as well;

the step of determining the optimum number of sampling points for a sub-surface including the steps of;

(a) determining an optimum number of sampling points for each of the three edges of the sub-surface, the optimum number of sampling points for an edge being the minimum number of sampling points required to fill the edge with said display elements at full brightness;

(b) defining the edge having the highest optimum number, Ns_op_d, of sampling points as directional edge, defining the edge having the lowest optimum number, Ns_op_b, of sampling points as base edge;

(c) determining the optimum number of sampling points for a sub-surface based on the value Ns_op_d×

Ns_op_b/2;

the step of selecting a number of sampling points for a sub-surface including the step of determining a number, Ns_d, of sampling points on the directional edge and a second number, Ns_b, of sampling points on the base edge, and determining the selected number of sampling points for a sub-surface based on the value Ns_d×

Ns_b/2;

the step of distributing sampling points in a sub-surface including the steps of;

(a) computing coordinates of said Ns_d sampling points on the directional edge and of said Ns_b sampling points on the base edge;

(b) constructing a mesh system over the sub-surface by conceptually drawing mesh lines from each of said Ns_b sampling points on the base-edge in a direction parallel to the directional-edge, and drawing mesh lines from each of said Ns_d sampling points on the directional-edge in a direction parallel to the base-edge;

(c) placing a sampling point to each intersection of the mesh lines that falls within the sub-surface;

7. Method of claim 6, wherein the step of determining the number Ns_d and the number Ns_b including (a) the step of computing the two numbers based on the orientation of the triangular surface with respect to the structure of display elements and (b) the step of adjusting the numbers to give meshes of approximately equal spacing in the two rendering directions.

8. Method of claim 1, wherein

the step of determining the minimum number of display elements including the steps of:

(i) computing the intersections of said geometric primitive with frame slices of the structure of the display elements, each said intersection comprising a small bitmap, each pixel of said small bitmap comprising one of said display elements;

(ii) stitching said intersections together into a composite bitmap;

(iii) fully rendering said composite bitmap at full brightness, said composite bitmap having a total number of Np_CBM_f pixels;

the step of determining the desired number of display elements including the step of determining a desired number, Np_CBM, of pixels for rendering said composite bitmap based on the following relation;

(Np_CBM/Np_CBM_f)×

(Bge/Bge_f)=Br/Br_op.

the step of rendering said geometric primitive including the steps of;

(i) re-rendering said composite bitmap with the desired number of pixels;

(ii) rendering said intersections according to the re-rendered composite bitmap.

9. Method of claim 1, wherein said brightness level being a brightness level of one of primary colors, the method further including the step of displaying the geometric primitive with brightness level of other primary colors in order to display said geometric primitive in desired color level.

12. Method of claim 1, wherein

said surface being a triangular surface;

the step of representing each said corresponding region of the surface with sampling points including the steps of;

a. constructing a mesh system comprising intersecting mesh lines for placing sampling points at intersections of the mesh lines, said mesh system having a mesh density required to render said triangular surface at a brightness ratio equal to the brightness ratio of said corresponding region;

b. placing sampling points according to the mesh system but only at the intersections located within said corresponding region.

13. Method of claim 12, further including:

the step of assigning each pixel of the texture map with a region index pointing to the corresponding region on said surface mapped by the intensity range of the pixel and setting up a data structure of said region index of each pixel of the texture map with respect to the location of the pixel in the texture map;

the step of mapping said mesh system to the texture map by proportion and thereby each intersection of mesh lines mapping to one pixel on the texture map; and

the step of checking if an intersection of mesh lines falls within the corresponding region by using the data structure to check if the region index of the pixel mapped to by the intersection matches the corresponding region under rendering.

10. Method of displaying a surface carrying a monochromatic texture map in actual 3D space in a volumetric 3D display, the volumetric 3D display comprising spatially distributed display elements for displaying volumetric 3D images, the method including the steps of:

(1) dividing the intensity scale of the texture map into a number of different intensity ranges, each said intensity range mapping to a different region on the texture map;

(2) mapping each said region of the texture map to a corresponding region on said surface;

(3) assigning a brightness ratio to each said corresponding region based on the intensity range mapped to the region, said brightness ratio being defined as the ratio of desired brightness to full brightness;

(4) rendering each said corresponding region of the surface with a different density of said display elements to represent different brightness ratio.

11. Method of claim 10, wherein the step of rendering each said corresponding region of the surface including the step of representing the region with sampling points by distributing the sampling points at a desired point density and by mapping each said sampling point to a desired number, called dilating number, of said display elements, combination of the desired point density and the desired dilating number forming the brightness ratio of the region.

14. Method of claim 10, wherein said monochromatic texture map being one filed of a color texture map, the method further including the step of displaying the surface carrying texture maps of other primary colors in order to display the surface with the color texture map.

15. Method of displaying a 3D volume with a distribution of monochromatic intensity scale in actual 3D space in a volumetric 3D display, the volumetric 3D display comprising spatially distributed display elements for displaying volumetric 3D images, the method including the steps of:

(1) dividing the intensity scale of the 3D volume into a number of different intensity ranges, each said intensity range thereby mapping to a different spatial region in the 3D volume;

(2) assigning a brightness ratio, BR, to each said spatial region in the 3D volume based on the corresponding intensity range mapped to the spatial region, said brightness ratio being defined as the ratio of desired brightness to full brightness;

(3) rendering each said spatial region with a different density of said display elements to represent different brightness ratio;

the step including the step of representing the spatial region with sampling points by distributing the sampling points at a desired point density using a desired mesh system and by mapping each said sampling point to a desired number, called dilating number n_pd, of said display elements, a mesh system comprising intersecting mesh lines for placing sampling points at intersections of the mesh lines, combination of the desired point density and the desired dilating number forming the brightness ratio of the spatial region;

the step of representing each said spatial region with sampling points including the steps of;

a. constructing a reference mesh system and setting a reference dilating number, N_d, said reference mesh system having a mesh density required to render the whole 3D volume at full intensity when said reference dilating number is used;

b. determining said desired mesh system and said desired dilating number based on the following relation;

[(Ns×

n_—

p)/(Ns_—

op×

N_—

d)]×

(Bge/Bge_—

f)=BR,

wherein Ns representing the number of sampling points for rendering the whole 3D volume using the desired mesh system, Ns_op representing the number of sampling points for rendering the whole 3D volume using the reference mesh system, Bge_f representing full brightness level of said display element, Bge representing brightness level of said display element to be used to render said geometric primitive;

c. placing sampling points according to the desired mesh system and only at the intersections located within said spatial region;

16. Method of claim 15, wherein said 3D volume comprising 3D data voxels, the method further including:

the step of assigning each of the voxels with a region index pointing to the corresponding spatial region mapped by the intensity range of the voxel and setting up a data structure of said region index of each voxel with respect to the location of the voxel in the 3D volume;

the step of mapping said desired mesh system to the 3D volume and thereby each intersection of mesh lines mapping to one voxel in the 3D volume;

the step of checking if an intersection of mesh lines falls within the corresponding spatial region by using said data structure to check if the region index of the voxel mapped to by the intersection matches the corresponding spatial region under rendering.

17. Method of claim 15, wherein said 3D volume comprising 3D data voxels, the method further including:

the step of assigning each of the voxels with a region index pointing to the corresponding spatial region mapped by the intensity range of the voxel and setting up a data structure of said region index of each voxel with respect to the location of the voxel in the 3D volume;

the step of mapping the voxels of a same region index to a desired mesh system corresponding to each said spatial region and thereby each voxel in the 3D volume mapping to one or more intersections of mesh lines;

18. Method of claim 15, wherein said monochromatic intensity scale being an intensity scale of one of primary colors, the method further including the step of displaying the 3D volume with brightness scale of other primary colors in order to display said 3D volume in desired color level.

19. Method of claim 15, farther including:

the step of defining a scan box within the space of the 3D volume;

the step of defining a small 3D volume corresponding to the space covered by the scan box;

the step of rendering and displaying said small 3D box; and

the step of displaying the original 3D volume at a reduced brightness ratio.