Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
2006-04-18
2006-04-18
Chauhan, Ulka (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S179000, C345S420000, C345S467000, C345S468000, C703S002000, C382S199000
Reexamination Certificate
active
07030881
ABSTRACT:
A method converts a two-dimensional object to a two-dimensional distance field. The object is represented as a set of boundary descriptors and a fill rule. The set of boundary descriptors is preprocessed and a spatial hierarchy is constructed from the preprocessed set of boundary descriptors. A cache of intersections is initialized. The spatial hierarchy is queried at a set of locations to determine a set of distances at the locations. The query invokes a distance function at each location to determine an unsigned distance. A sign of the unsigned distance is determined from the cache of intersections, the location, and the fill rule. The set of distances is used to construct the two-dimensional distance field.
REFERENCES:
patent: 5155813 (1992-10-01), Donoghue et al.
patent: 5202928 (1993-04-01), Tomita et al.
patent: 5255357 (1993-10-01), Byron et al.
patent: 5386502 (1995-01-01), Minagawa et al.
patent: 5828380 (1998-10-01), Lin
patent: 5867173 (1999-02-01), Ballard et al.
patent: 5940080 (1999-08-01), Ruehle et al.
patent: 6396492 (2002-05-01), Frisken et al.
patent: 6828965 (2004-12-01), Rockwood
patent: 2002/0097912 (2002-07-01), Kimmel et al.
patent: 2002/0130877 (2002-09-01), Perry et al.
patent: 2004/0189639 (2004-09-01), Perry et al.
patent: 2004/0189644 (2004-09-01), Frisken et al.
patent: 2004/0189661 (2004-09-01), Perry et al.
patent: 2004/0189662 (2004-09-01), Frisken et al.
patent: 1241621 (2002-09-01), None
patent: 1244059 (2002-09-01), None
Payne, B., Toga, A., “Distance Field Manipulation of Surface Models” IEEE 0272-17-16/92/0100-0065, Jan. 1992, pp. 65-71.
Satherley, R., Jones, M.W., “Hybrid Distance Field Computation” University of Wales Swansea, 2001, pp. 1-16.
Russ, J.C., “The Image Processing Handbook” CRC Press LLC, 2002, pp. 425-429.
Hu, C., Hersch, R., “Parameterizable Fonts Based on Shape Components” IEEE CG&A, May/Jun. 2001, vol. 21, No. 3, pp. 70-85.
Klein et al. “Reconstruction and simplification of surfaces from contours,” Proceedings of the Seventh Pacific Conference on Computer Graphics and Applications, pp. 198-207, 1999.
Frisken et al. “Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics,” SIGGRAPH, Computer Graphics Proceedings, pp. 249-254, 2000.
Perry et al. “KIZAMU: A System for Sculpting Digital Characters,” SIGGRAPH, Computer Graphics Proceedings, pp. 47-56, 2001.
Betrisey, C., Blinn, J. F., Dresevic, B., Hill, B., Hitchcock, G., Keely, B., Mitchell, D. P., J. C. and Whitted, T. 2000. Displaced Filtering for Patterned Displays. InProc. Society for Information Display Symp.pp. 296-299.
Cook, R. 1986. Stochastic Sampling in Computer Graphics. InACM Transactions on Graphics, pp. 51-72.
Desbrun, M. and Gascuel, M-P. 1995. Animating Soft Substances with Implicit Surfaces, InProc. SIGGRAPH 1995. pp. 287-290.
Frisken, S., Perry, R., Rockwood, A. and Jones, T. 2000, Adaptively Sampled Distance Fields: a General Representation of Shape for Computer Graphics. InProceedings ACM SIGGRAPH 2000, pp. 249-254.
Frisken, S. and Perry, R. 2002. Efficient Estimation of 3D Euclidean Distance Fields from 2D Range Images. InProc. IEEE/ACM SIGGRAPH Volume Visualization and Graphics Symposium 2002, pp. 81-88.
Frisken, S. and Perry, R. 2003. Simple and Efficient Traversal Methods for Quadtrees and Octrees. To appear inJournal of Graphics Tools. See also MERL technical report TR2002-41.
Gupta, S. and Sproull, R. 1981. Filtering Edges for Grayscale Displays. InComputer Graphics15(3), pp. 1-5.
Hersch, R. 1987. Character Generation Under Grid Constraints. InProceedings ACM SIGGRAPH 1987, pp. 71-80.
Hersch, R., Betrisey, C., Bur, J. and Gurtler A. 1995. Perceptually Tuned Generation of Grayscale Fonts. InIEEE CG&A, Nov., pp. 78-89.
Herz, J. and Hersch, R. 1994. Towards a Universal Auto-hinting System for Typographic Shapes.Electronic Publishing, 7(4), pp. 251-260.
Hoff, K., Zaferakis, A., Lin, M. and Manocha, D. 2001. Fast and Simple 2D Geometric Proximity Queries Using Graphics Hardware. In Proc. Interactive 3D Graphics'01.
Hu, C. and Hersch, R. 2001. Parameterizable Fonts Based on Shape Components. InIEEE CG&AMay/Jun., pp. 70-85.
Itoh, K. and Ohno, Y. 1993. A Curve Fitting Algorithm for Character Fonts. In Electronic Publishing 6(3), pp. 195-205.
Johnson, D. and Cohen, E. 1998. A Framework For Efficient Minimum Distance Computations. InProc. IEEE International Conference on Robotics and Automation, pp. 3678-3684.
Jones, T. and Perry, R. 2000. Antialiasing with Line Samples. InProceedings Eurographics Rendering Workshop, pp. 197-205.
Lee, M., Redner, R. and Uselton, S. 1985. Statistically Optimized Sampling for Distributed Ray Tracing. InProceedings ACM SIGGRAPH 1985, pp. 61-67.
McNamara, R., McCormack, J. and Jouppi, N. 2000. Prefiltered Antialiased Lines Using Half-Plane Distance Functions. InProc. SIGGRAPH/Eurographics Workshop on Graphics Hardware 2000, pp. 77-86.
Mitchell, D. 1987. Generating Antialiased Images at Low Sampling Rates. InProc. ACM SIGRRAPH 1987, pp. 65-72.
Mitchell, D. 1996. Consequences of Stratified Sampling In Graphics. InProc. ACM SIGRRAPH 1996, pp. 277-280.
O'Regan, K., Bismuth, N., Hersch, R. and Pappas, A. 1996. Legibility of Perceptually-Tuned Grayscale Fonts. InProc. IEEE Int. Conf. Image Processing, pp. 537-540.
Osher, S., and Sethian, J. 1988. Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton—Jacobi Formulations,Journal of Computational Physics, pp. 12-49.
Perry, R. and Frisken, S. 2001. Kizamu: A System for Sculpting Digital Characters. InProceedings ACM SIGGRAPH 2001, pp. 47-56.
Platt, J. 2000. Optimal Filtering for Patterned Displays. InIEEE Signal Processing Letters, 7(7), pp. 179-180.
Nishita, T., Sederberg, T., and Kakimoto, M. (1990) Ray Tracing Trimmed Rational; Surface Patches. Computer Graphics, vol. 24, No. 4, Aug. 1990.
Schneider, P. 1990. An Algorithm for Automatically Fitting Digitized Curves. InGraphics Gems I, ed. A. Glassner, pp. 612-626.
Shamir, A. and Rappoport A. 1998. Feature-based Design of Fonts Using Constraints. InProc. Electronic Publishing 1998, pp. 93-108.
Sramek, M. and Kaufman, A. 1999. Alias-Free Voxelization of Geometric Objects. InIEEE Transactions on Visualization and Computer Graphics, 3(5), pp. 251-266.
Turkowski, K. 1982. Anti-Aliasing Through the Use of Coordinate Transformations. InACM Trans on Graphics, 1(3) pp. 215-234.
Westover, L. 1990. Footprint Evaluation for Volume Rendering. InProceedings ACM SIGGRAPH 1990, pp. 367-376.
Whitted, T. 1980. An Improved Illumination Model for Shaded Display. InCommunications of the ACM, 23(6), pp. 343-349.
Zongker, D., Wade, G. and Salesin, D. 2000. Example-Based Hinting of TrueType Fonts. InProceedings ACM SIGGRAPH 2000, pp. 411-416.
Frisken Sarah F.
Perry Ronald N.
Brinkman Dirk
Chauhan Ulka
Curtin Andrew J.
Mitsubishi Electric Research Laboratories Inc.
Prendergast Roberta
LandOfFree
Method for converting two-dimensional objects to distance... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for converting two-dimensional objects to distance..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for converting two-dimensional objects to distance... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3558189