Computer graphics processing and selective visual display system – Computer graphics display memory system – Addressing
Reexamination Certificate
2011-06-21
2011-06-21
Broome, Said (Department: 2628)
Computer graphics processing and selective visual display system
Computer graphics display memory system
Addressing
C345S503000, C345S565000
Reexamination Certificate
active
07965297
ABSTRACT:
A “Variable-Rate Perfect Hasher” maps sparse variable-rate data of one or more dimensions into a hash table using a perfect hash function. In various embodiments, perfect hash tables are populated by first computing offset table address for each data point of a domain of sparse variable-rate data elements. Offset vectors are then computed for each offset table address based in part on the size of each data element by evaluating offset vectors in order of a sum of the data point addresses mapping to each offset vector. These offset vectors are then stored in the offset table. For each data point, the corresponding offset vector is then used to compute a hash table address. Data elements are then perfectly hashed into the hash table using the computed hash table addresses. The resulting hash tables support efficient random access of the variable-sized data elements stored therein.
REFERENCES:
patent: 5123245 (1992-06-01), Vilenius et al.
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: 6115802 (2000-09-01), Tock et al.
patent: 6216199 (2001-04-01), DeKoning et al.
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: 7146371 (2006-12-01), Hofstee et al.
patent: 7158141 (2007-01-01), Chung
patent: 2003/0128876 (2003-07-01), Yamaguchi
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/0219624 (2005-10-01), Zavitaev
patent: 2006/0044317 (2006-03-01), Bourd et al.
patent: 2006/0103665 (2006-05-01), Opala 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{dot over (o)}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 clipping 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., 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 Camp. Graphics and Interactive Techniques, ACM SIGGRAPH 2005.
Mehlhorn, K. 1982. On the program size of perfect and universal hash functions. Symposiumn 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.
Broome Said
Lyon & Harr LLP
Microsoft Corporation
Watson Mark A.
LandOfFree
Perfect hashing of variably-sized data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Perfect hashing of variably-sized data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfect hashing of variably-sized data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2674565