Random-access vector graphics

Details Random-access vector graphics Random-access vector graphics

2011-01-18

2011-01-18

Sajous, Wesner (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S552000, C345S555000, C382S232000, C382S253000, C382S305000, C382S282000, C711S216000

Reexamination Certificate

active

07872648

ABSTRACT:
A “Vector Graphics Encoder” encodes vector graphics in a randomly accessible format. This encoding format enables particular portions of encoded images to be directly accessed, at any desired level of zoom, without processing or otherwise decoding the entire image. This random-access format is based on a coarse image grid of partially overlapping cells wherein each cell is defined by a “texel program.” Unlike fixed-complexity cells used by conventional vector images, each cell defined by a texel program is locally specialized without requiring global constraints on the complexity of each cell. The texel program for each cell is provided as a variable-length string of tokens representing a locally specialized description of one or more of layers of graphics primitives overlapping the cell. Images are then rendered by interpreting the texel programs defining one or more cells.

REFERENCES:
patent: 5490258 (1996-02-01), Fenner
patent: 5526504 (1996-06-01), Hsu
patent: 5692177 (1997-11-01), Miller
patent: 5893086 (1999-04-01), Schmuck
patent: 6014733 (2000-01-01), Bennett
patent: 6654868 (2003-11-01), Tamatsu
patent: 6765584 (2004-07-01), Wloka
patent: 6795080 (2004-09-01), Lavelle
patent: 6873343 (2005-03-01), Chui
patent: 7158141 (2007-01-01), Chung
patent: 2004/0064483 (2004-04-01), Bulka et al.
patent: 2004/0117600 (2004-06-01), Bodas et al.
patent: 2004/0227767 (2004-11-01), Baroncelli et al.
patent: 2005/0063596 (2005-03-01), Yomdin et al.
patent: 2005/0219624 (2005-10-01), Zavitaev
patent: 2006/0044317 (2006-03-01), Bourd et al.
patent: 2006/0103665 (2006-05-01), Opala et al.
patent: 2008/0309676 (2008-12-01), Nehab et al.
Benson, D., and J. Davis, Octree textures, SIGGRAPH '02, 2002, pp. 785-790.
Blinn, J., How to solve a cubic equation, Part 2: The 11 Case, IEEE CG&A, 2006, vol. 26, No. 4, pp. 90-100.
Blythe, D., The Direct3D 10 system, Proc. of ACM SIGGRAPH HDR and systems, Jul. 2006, pp. 724-734, vol. 25, No. 3.
Brain, M., and A. Tharp, Perfect hashing using sparse matrix packing, Info. Sys., 1990, pp. 281-290, vol. 15, No. 3.
Cantlay, I. Mipmap-level measurement. GPU Gems II, 2005, pp. 437-449.
Carpenter, L., The A-buffer, an antialiased hidden surface method, ACM SIGGRAPH, 1984, pp. 103-108.
Czech, Z., G. Havas, and B. Majewski, Perfect hashing, Theoretical Computer Science 1997, pp. 1-143, vol. 182.
Debry, D., J. Gibbs, D. Petty, and N. Robins, Painting and rendering on unparameterized models. ACM SIGGRAPH, 2002, pp. 763-768.
Fox, E., L. Heath, Q. Chen, and A. Daoud, Practical minimal perfect hash functions for large databases, 1992, CACM, pp. 105-121, vol. 33, No. 1.
Fredman, M. L., J. Komlós, E. Szemerédi, Storing a sparse table with 0(1) worst case access time, J. of the ACM (JACM), Jul. 1984, pp. 538-544, vol. 31, No. 3.
Frisken, S., R. Perry, A. Rockwood, and T. Jones, Adaptively sampled distance fields: A general representation of shape for computer graphics, ACM SIGGRAPH, 2000, pp. 249-254.
Gaede, V., and O. Günther, Multidimensional access methods, ACM Computing Surveys, 1998, vol. 30, No. 2, pp. 170-231.
Goldman, R., T. Sederberg, and D. Anderson, Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves, CAGD, 1984, vol. 1, pp. 327-356.
Govindaraju, N., M. Lin, and D. Manocha, Fast and reliable collision culling using graphics hardware, Proc. of VRST, 2004, pp. 2-9.
Greiner, G., and K. Hormann, Efficient dipping of arbitrary polygons, ACM TOG, 1998, pp. 71-83, vol. 17, No. 2.
Heckbert, P., Fundamentals of texture mapping and image warping, M.S. Thesis, 1989, UC Berkeley, Dept. Of EECS.
Ho, Y., Application of minimal perfect hashing in main memory indexing, 1994, Masters Thesis, MIT.
Houston, B., M. B. Nielsen, C. Batty, O. Nilsson, K. Museth, Hierarchical RLE level set: A compact and versatile deformable surface representation, ACM Transactions on Graphics (TOG) Jan. 2006, pp. 151-175, vol. 25, No. 1.
Kraus, M., and T. Ertl, Adaptive texture maps, Graphics Hardware, 2002, pp. 7-15.
Lefebvre, S., H. Hoppe, Perfect spatial hashing, Int'l Conf. on Comp. Graphics and Interactive Techniques, 2006, pp. 579-588, Boston, Massachusetts.
Lefebvre, S., S. Hornus, and F. Neyret, Octree textures on the GPU, GPU Gems II, 2005, pp. 595-613.
Lefebvre, S., and F. Neyret, Pattern based procedural textures, Symposium on Interactive 3D Graphics, 2003, pp. 203-212.
Lefohn, A. E., S. Sengupta, J. Kniss, R. Strzodka, and J. D. Owens, Glift: Generic, efficient, random-access GPU data structures, ACM Transactions on Graphics (TOG), Jan. 2006, pp. 60-99, vol. 25, No. 1.
Loop, C., and J. Blinn, Resolution-independent curve rendering using programmable graphics hardware. ACM SIGGRAPH, 2005, 1000-1009.
Loviscach, J., Efficient magnification of bi-level textures, Int'l Conf. on Comp. Graphics and Interactive Techniques, ACM SIGGRAPH 2005.
Mehlhorn, K. 1982. On the program size of perfect and universal hash functions. Symposium on Foundations of Computer Science, 170-175.
Mirtich, B. 1996. Impulse-based dynamic simulation of rigid body systems. PhD Thesis, UC Berkeley.
Naor, M. and V. Teague, Anti-persistence: History independent data structures, Proc. 33rd ACM Symp. on Theory of Computing, 2001.
Östlin, A., and Pagh, R. 2003. Uniform hashing in constant time and linear space. ACM STOC, 622-628.
Pearson, P. K., Fast hashing of variable-length text strings, Communications of the ACM, Jun. 1990, pp. 677-680, vol. 33, No. 6.
Peercy, M., Olano, M., Airey, J., and Ungar, J. 2000. Interactive multi-pass programmable shading. ACM SIGGRAPH, 425-432.
Qin, Z., McCool, M., and Kaplan, C. 2006. Real-time texture-mapped vector glyphs. Symposium on Interactive 3D Graphics and Games, 125-132.
Ramanarayanan, G., Bala, K., and Walter, B. 2004. Feature-based textures. Eurographics Symposium on Rendering, 65-73.
Ray, N., Cavin, X., and Lévy, B. 2005. Vector texture maps on the GPU. Technical Report ALICE-TR-05-003.
Sager, T. 1985, A polynomial time generator for minimal perfect hash functions, CACM, 1985, pp. 523-532, vol. 28, No. 5.
Schmidt, J., and Siegel, A. 1990. The spatial complexity of oblivious k-probe hash functions, SIAM Journal on Computing, 19(5), 775-786.
Sen, P., Cammarano, M., and Hanrahan, P. 2003. Shadow silhouette maps. ACM SIGGRAPH, 521-526.
Sen, P., Silhouette maps for improved texture magnification, Symposium on Graphics Hardware, 2004, pp. 65-73.
Sutherland, I., and G. Hodgman, Reentrant polygon clipping, Communications of the ACM, 1974, pp. 32-42, vol. 17, No. 1.
Tarini, M., and P. Cignoni, Pinchmaps: Textures with customizable discontinuities, Eurographics Conf., 2005, pp. 557-568.
Teschner, M., B. Heidelberger, M. Müller, D. Pomeranets, and M. Gross, Optimized spatial hashing for collision detection of deformable objects, Proc. VMV, 2003, pp. 47-54.
Tumblin, J., and P. Choudhury, Bixels: Picture samples with sharp embedded boundaries, Symposium on Rendering, 2004, pp. 186-194.
Warnock, J., A hidden surface algorithm for computer generated halftone pictures, PhD Thesis, 1969, University of Utah.
Weiler, M., M. Kraus, M. Merz, and T. Ertl, Hardware-based ray casting for tetrahedral meshes, Proc. of the 14th IEEE Visualization 2003 (VIS'03), 2003, pp. 333-340.
Winner, S., M. Kelley, B. Pease, B. Rivard, and A. Yen, Hardware accelerated rendering of antialiasing using a modified A-buffer algorithm, ACM SIGGRAPH, 1997, pp. 307-316.
Winters, V., Minimal perfect hashing in polynomial time, BIT, 1990, vol. 30, No. 2, pp. 235-244.
Zobel, J., A. Moffat, and R. Sacks-Davis, Storage management for files of dynamic records, Proc. of the 4th Australian Database Conf., 1993, pp. 26-38.

Affiliated with

Also associated with

Rating

Random-access vector graphics does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Random-access vector graphics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random-access vector graphics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2644601