Fractal generation, as for video graphic displays

• US 4,694,407 A
• Filed: 06/11/1985
• Issued: 09/15/1987
• Est. Priority Date: 06/11/1985
• Status: Expired due to Term

• Current Assignee: RCA Corporation (General Electric Company)
• Original Assignee: RCA Corporation (General Electric Company)
• Inventors: Ogden, Joan M.
• Primary Examiner(s): Krass, Errol A.
• Assistant Examiner(s): TRANS, VINCENT N
• Application Number:
  US06/743,623
• Time in Patent Office: 826 Days
• Field of Search: 364/518, 364/521, 364/577, 364/578, 364/604, 364/728, 340/732, 340/744, 340/749, 340/747, 358/30, 358/138, 358/209, 382/9, 382/42
• US Class Current: 345/441
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77

Abstract

Fractals are generated based on their self-similarity properties. This is done by convolving a basic shape, or "generator pattern", with a "seed pattern" of dots, in each of different spatial scalings. The convolution results are then combined to define a multi-dimensional object, identifiable as a fractal. Two-dimensional sections of this object are used in generating graphic images for video display.

Claims

1. A method of generating fractals comprising the steps of:

convolving generator patterns with seed patterns of dots to generate convolution results for each of a plurality of sample spaces, such spaces being consecutively ordinally numbered in order of their successively more sparse sampling;

expanding the convolution results in each of the higher numbered sample spaces through interpolation to a sampling density comparable to that in a lower numbered sample space;

combining samples of the convolution results and the expanded convolution results of similar sampling density on a corresponding sample-by-sample basis; and

carrying out said steps of expanding through interpolation and said steps of combining so as to result in the expanded convolution results of each of the higher numbered sample spaces ultimately being combined with the convolution results in said first sample space, thereby generating said fractals.

2. A method of generating a fractal comprising the steps of:

providing a seed pattern of dots in each of a a plurality of sample spaces consecutively ordinally numbered first through n^th, said first sample space being regularly sampled in a plurality of dimensions, and each other sample space being regularly sampled in those dimensions more sparsely than the sample space with the next lower ordinal number;

providing a generator pattern in a normalized sample space;

performing a spatial convolution of said generator pattern with the respective seed patterns in each of the sample spaces;

expanding, by means of interpolating, the spatial convolution result obtained in each said other sample space to the sampling density of said first sample space and combining the expanded spatial convolution result with the spatial convolution result obtained in said first sample space, to result in said fractal.

3. A method for generating a fractal as set forth in claim 2 wherein said expanding and combining step comprises the steps of;

expanding by means of interpolation the spatial convolution result obtained in the n^th sample space to the sampling density of the (n-1)^th sample space;

combining the expanded spatial convolution result obtained in the n^th sample space with the spatial convolution result obtained in the (n-1)^th sample space;

thereafter successively combining in each of the (n-2)^th through first sample spaces the spatial convolution result obtained in that sample space and an expanding result previously obtained in the next-higher-numbered sample space; and

expanding, by means of interpolation, the result of combining in each sample space other than the first, to the sampling density of the next-lower-numbered sample space, said fractal resulting from combining in said first sample space.

4. A method of generating a fractal as set forth in claim 3 wherein said combining is additive.

5. A method of generating a fractal as set forth in claim 2 wherein said combining is additive.

6. A method of generating fractals as set forth in claim 2 further comprising the steps of:

repeating said steps of choosing a seed pattern of dots in each of said plurality of sample spaces, of choosing a generator pattern in a normalized sample space, of performing a spatial convolution in each of the sample spaces, of expanding and of combining, wherein the choice of seed patterns is changed in the course of repetition, to result in a series of fractals including at least one further fractal in addition to said fractal.

7. A method of generating fractals as set forth in claim 2 further comprising the steps of:

repeating said steps of choosing a seed pattern of dots in each of said plurality of sample spaces, of choosing a generator pattern in a normalized sample space, of performing a spatial convolution in each of the sample spaces, of expanding and of combining, wherein the positioning of the seed patterns relative to reference points in space is changed in the course of repetition, to result in a series of fractals including at least one further fractal in addition to said fractal.

8. A method of generating fractals as set forth in claim 2 further comprising the steps of:

repeating said steps of choosing a seed pattern of dots in each of said plurality of sample spaces, of choosing a generator pattern in a normalized sample space, of performing a spatial convolution in each of the sample spaces, of expanding and of combining, wherein the generator pattern is rotated in at least one of the sample spaces during the course of repetition, to result in a series of fractals including at least one further fractal in addition to said fractal.

9. A method of generating fractals as set forth in claim 8 further comprising the steps of:

repeating said steps of choosing a seed pattern of dots in each of said plurality of sample spaces, of choosing a generator pattern in a normalized sample space, of performing a spatial convolution in each of the sample spaces, of expanding and of combining, wherein the seed pattern is rotated in at least one of the sample spaces during the course of repetition, to result in a series of fractals including at least one further fractal in addition to said fractal.

10. A method of generating fractals as set forth in claim 2 further comprising the steps of:

repeating said steps of choosing a seed pattern of dots in each of said plurality of sample spaces, of choosing a generator pattern in a normalized sample space, of performing a spatial convolution in each of the sample spaces, of expanding and of combining, wherein the seed pattern is rotated in at least one of the sample spaces during the course of repetition, to result in a series of fractals including at least one further fractal in addition to said fractal.

11. A method of generating in sampled form a first raster-scanned video signal comprising the steps of:

providing for each field scan a seed pattern of dots in each of a plurality of sample spaces consecutively ordinally numbered first through n^th, said first sample space being regularly sampled in a plurality of dimensions, and each other sample space being regularly sampled in those dimensions more sparsely than the sample space with the next lower ordinal number;

providing for each field scan a respective generator pattern for each of said plurality of sample spaces consecutively ordinally numbered first through n^th ;

performing a spatial convolution of each generator pattern with the seed pattern sampled at the same sampling density in accordance with a raster scanning pattern, to obtain for each field scan a convolution result at that respective sampling density;

expanding by means of interpolation those convolution results of lower sampling density and combining the convolution results at similar sampling densities;

obtaining in response to said expanding and combining steps the combination of those convolution results in a raster-scanned sample space; and

converting each level sample of said combination of convolution results to a respective level sample of said first raster-scanned video signal in accordance with an established scheme.

12. The method of claim 11 wherein said step of converting each level sample of said combination of convolution results converts each level to respective level samples of each of first, second and third raster-scanned video signals.

13. The method of claim 12 wherein said first, second and third video signals are red video signal, green video signal, and blue video signal, respectively.

14. A method for generating a composite video signal using the first video signal generated by the method steps of the claim 11 in combination with the steps of:

generating at least one further video signal raster-scanned in synchronism with said first raster-scanned signal; and

selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis, to generate said composite signal.

15. The method of claim 14 wherein said selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis is controlled at least in part using a map stored in a synchronously scanned memory.

16. The method of claim 14 wherein said selecting from said first video signal on a time-division-multiplex basis is carried out by the steps of:

assigning an order of priority to the portions of each said further video signal and to the portions of said first raster-scanned video signal in certain ranges; and

generating said composite video signal by selecting for each successive sample thereof the one of the samples of said first video signal and each further video signal having the highest assigned priority.

17. A fractal generator comprising:

means for generating raster scanned seed patterns of dots in each of a multiplicity of two-dimensional sample spaces consecutively ordinally numbered first through n^th and successively more sparsely sampled;

means for defining a generator pattern disposed over an array of grouped pixel locations;

means for extracting, from said raster scanned seed patterns in each of said sample spaces, successive arrays of grouped pixel locations similar to that over which said generator pattern is disposed;

means for convolving in each sample space said generator pattern array and each successive array of grouped pixel locations from the raster scanned seed pattern in that sample space to obtain a respective convolution result;

respective means, associated with each sample space except the first for expanding through interpolation a function sampled in that space to the sampling density of the next lower numbered sampling space;

means for deriving from the convolution result in said n^th sample space the function which is subsequently expanded through interpolation by said means for expanding a function sampled in said n^th space; and

respective means for combining in each of said first through (n-1)^th sample spaces the convolution result in that sample space with the function expanded through interpolation to the sampling density of that sample space, thereby to generate in each of said second through (n-1)^th sample spaces the function sampled in that space which is subsequently expanded through interpolation by said means for expanding a function in that space, and to generate in said first sample space said fractal, which exhibits variation in amplitude.

18. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 17 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator for generating different color video signals.

19. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 17 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator, for generating different intensity video signals.

20. A method of generating a fractal comprising the steps of:

providing a seed pattern of dots in a normalized sample space, which is regularly sampled along spatial coordinates in a plurality of dimensions;

providing a generator pattern in said normalized sample space;

convolving said generator pattern with said seed pattern to generate convolution results;

writing said convolution results into a first memory having storage locations identifiable to respective sets of integral values of said spatial coordinates;

expanding at least portions of said convolution results through interpolation in each of said plurality of dimensions, a number of times;

writing the once-expanded convolution results into a second memory having storage locations identifiable to respective sets of integral values of said spatial coordinates;

writing the plurally-expanded convolution results into respective further memories, each having storage locations identifiable to respective sets of integral values of said spatial coordinates;

reading out in parallel scanning successive storage locations in said first, second and further memories, and

combining the parallel-scanning read-outs for generating successive samples of the a fractal.

21. A method of generating fractals as set forth in claim 20 including in addition to the steps therein set forth the steps of:

repeating the steps set forth in claim 20 in each of successive fields of said parallel scanning scanning of successive storage locations in said first, second and further memories; and

changing, between fields of said parallel scanning of successive storage locations in said first, second and further memories, the offsets of the respective parallel scannings as referred to the parallel scanning of the memories during their writing, thereby to animate the generated fractals.

22. A method of generating a fractal as set forth in claim 21 wherein said combining is additive.

23. A method of generating a fractal as set forth in claim 20 wherein said combining is additive.

24. A method of generating first video signal comprising said method of generating a fractal as set forth in claim 20 in combination with the further steps of:

converting each successive level sample of the generated fractals to a sample of video signal in accordance with an established scheme; and

converting each sequence of raster-scanned video signal samples thus generated to a respective portion of said first video signal.

25. A method for generating a composite video signal using the first video signal generated by the method steps of the claim 24 in combination with the steps of:

generating at least one further video signal raster-scanned in synchronism with said first raster-scanned signal; and

selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis, to generate said composite signal.

26. The method of claim 25 wherein said selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis is controlled at least in part using a map stored in a synchronously scanned memory.

27. The method of claim 25 wherein said selecting from said first video signal on a time-division-multiplex basis is carried out by the steps of:

assigning an order of priority to the portions of each said further video signal and to the portions of said first raster-scanned video signal in certain ranges; and

generating said composite video signal by selecting for each successive sample thereof the one of the samples of said first video signal and each further video signal having the highest assigned priority.

28. A fractal generator for generating a raster-scanned fractal in sampled-data form that exhibits variation in amplitude, comprising:

a plurality of bit-map-organized memories, consecutively ordinally numbered first through n^th with respective addressable arrays of storage locations for storing respective fractal components of successively larger scale;

respective means for raster scanning each of said bit-map-organized memories in synchronism with the others during a read cycle;

means for combining each set of fractal component samples read out in parallel from said plurality of bit-map-organized memories, for each of the successive addresses in their synchronous raster scans, thereby to generate one of the successive samples of said raster scanned fractal in sampled-data form; and

means for selectively adjusting the offsets of the respective raster scans of said bit-map-organized memories between each of successive raster scans in their read cycle, relative to order in which the respective fractal components were stored in the addressable arrays of storage locations in said bit-map-organized memories, thereby to animate the generated fractal.

29. A fractal generator as set forth in claim 28, where n is an integer at least three, said fractal generator including:

means for scanning through the storage locations of each of said bit-map-organized memories in parallel during a write cycle;

means for generating dots at selected intervals in the write cycle;

means for convolving each of said dots with a generator pattern to generate convolution results in sampled data form as a fractal component of smallest scale;

means for writing said fractal component of smallest scale into said first bit-map-organized memory;

means expanding said convolution results through interpolation in each spatial dimension, for generating convolution results in expanded sampled-data form as a fractal component of next-to-smallest scale;

means for writing said fractal component of next-to-smallest scale into said second bit-map-organized memory;

means further expanding said convolution results through interpolation in each spatial dimension for generating (n-2) additional fractal components of successively larger scale; and

means for writing each said additional fractal component into a respective one of said bit-map-organized memories other than the first and second of them.

30. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 28 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator, for generating different color video signals.

31. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 28 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator, for generating different intensity video signals.

32. A method of generating a fractal comprising the steps of:

providing a seed pattern of dots in a first sample space, which is regularly sampled in a plurality of dimensions;

providing a generator pattern;

convolving said seed pattern of dots in said first sample space with the generator pattern in said first sample space, thereby to generate spatial convolution results in said first sample space;

storing said spatial convolution results in a memory with storage locations mapping said first sample space;

selecting portions of said mapped first sample space for retrieval of spatial convolution results to be attributed to other sample spaces ordinally numbered second through n^th, n being an integer at least three, each of which other sample spaces is regularly sampled in each of said plurality of dimensions less densely than sample spaces with lower ordinal numbering than its own;

expanding, by means of interpolating, the spatial convolution result obtained in each other sample space to the sampling density of said first sample space and combining the expanded spatial convolution result with the spatial convolution result obtained in said first sample space, to result in said fractal.

33. A method of generating a fractal as set forth in claim 32 wherein said expanding and combining step comprises the steps of:

expanding by means of interpolation the spatial convolution result obtained in the n^th sample space to the sampling density of the (n-1)^th sample space;

combining the expanded spatial convolution result obtained in the n^th sample space with the spatial convolution result obtained in the (n-1)^th sample space;

thereafter successively combining in each of the (n-2)^th through first sample spaces the spatial convolution result obtained in that sample space and an expanding result previously obtained in the next-higher-numbered sample space; and

expanding, by means of interpolation, the result of combining in each sample space other than the first, to the sampling density of the next-lower-numbered sample space, said fractal resulting from combining in said first sample space.

34. A method of generating a fractal as set forth in claim 33 wherein said combining is additive.

35. A method of generating a fractal as set forth in claim 32 wherein said combining is additive.

36. A method of generating in sampled form a first raster-scanned video signal comprising the steps of:

providing, prior to an initial field scan in a sequence of field scans in said video signal, a seed pattern of dots, which dots fall on selected ones of sample locations located periodically in each of the dimensions of one of a plurality of sample spaces, which sample spaces are consecutively ordinally numbered first through n^th and are successively more sparsely sampled;

providing, prior to an initial field scan in each said sequence of field scans, a generator pattern;

performing a spatial convolution of said seed pattern with a generator pattern to obtain sample-data convolution results in a normalized sample space;

during each subsequent field scan, re-sampling by raster scan in each of said sample spaces selected portions of the sampled-data convolution results in the normalized sample space, for generating respective convolution results in each of the ordinally numbered sample spaces;

during each subsequent field scan, expanding by means of interpolation the selected portions of the convolution results for higher numbered sample spaces to the sampling densities of lower numbered sampled spaces and combining selected convolution results at similar sampling densities;

obtaining in response to said expanding and combining steps the combination of those convolution results in a raster-scanned sample space; and

converting each level sample of said combination of convolution results to a respective level sample of said first raster-scanned video signal in accordance with an established scheme.

37. The method of claim 36 wherein said step of converting each level sample of said combination of convolution results converts each level to respective level samples of each of first, second and third raster-scanned video signals.

38. The method of claim 37 wherein said first, second and third video signals are red video signal, green video signal, and blue video signal, respectively.

39. A method for generating a composite video signal using the first video signal generated by the method steps of claim 36 in combination with the steps of:

generating at least one further video signal raster scanned in synchronism with said first raster-scanned signal; and

selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis, to generate said composite signal.

40. The method of claim 39 wherein said selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis is controlled at least in part using a map stored in a synchronously scanned memory.

41. The method of claim 39 wherein said selecting from said first video signal and said at least one further video signal on a time-division-multiplex basis is carried out by the steps of:

assigning an order of priority to the portions of each said further video signal and to the portions of said first raster-scanned video signal in certain ranges; and

generating said composite video signal by selecting for each successive sample thereof the one of the samples of said first video signal and each further video signal having the highest assigned priority.

42. A fractal generator comprising:

means for generating a raster scanned seed pattern of dots in the first of a multiplicity of two-dimensional sample spaces consecutively ordinally numbered first through n^th and successively more sparsely sampled;

means for defining a generator pattern disposed over an array of grouped pixel locations;

means for extracting, from said raster scanned seed pattern, successive arrays of grouped pixel locations similar to that over which said generator pattern is disposed;

means for convolving in said first sample space said generator pattern array and each successive array of grouped pixel locations from the raster scanned seed pattern in said first sample space to obtain a convolution result for each sample point in said first sample space;

means, responding to at least portions of the convolution result for said first sample space, for re-scaling them by resampling to be at the sampling densities of said sample spaces other than the first, to obtain respective convolution results for said other sample spaces;

respective means, associated with each sample space except the first for expanding through interpolation a function sampled in that space to the sampling density of the next lower numbered sampling space;

means for deriving from the convolution result in said n^th sample space the function which is subsequently expanded through interpolation by said means for expanding a function sampled in said n^th space; and

respective means for combining in each of said first through (n-1)^th sample spaces the convolution result in that sample space with the function expanded through interpolation to the sampling density of that sample space, thereby to generate in each of said second through (n-1)^th sample spaces the function sampled in that space which is subsequently expanded through interpolation by said means for expanding a function in that space, and to generate in said first sample space said fractal.

43. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 42 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator, for generating different color video signals.

44. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 42 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator, for generating different intensity video signals.

45. A fractal generator comprising:

a bit-map-organized memory for storing the first and smallest-in-relative-scale of a plurality, at least three in number, of consecutively ordinally numbered fractal components, respectively of successively larger scale;

means multiply raster scanning said bit-map-organized memory on a time-division-multiplex basis during a read-out cycle for supplying a plurality, n in number, of raster-scanned read-out signals;

means for adjusting the relative time delays of the first through n^th of said memory read-out signals respective to each other;

means for expanding, through interpolation, each of the second through n^th of the delay-adjusted memory read-out signals, and combining them with the first fractal component for generating samples of raster-scanned fractal, which exhibit variation in amplitude.

46. A fractal generator as set forth in claim 45 including, for the purpose of fractal animation:

means for adjusting from field scan to field scan the relative offsets between the multiple raster scanning of said bit-map-organized memory; and

within said means for adjusting the relative time delays of said memory read-out signals, means for re-adjusting those time delays from field scan to field scan.

47. A fractal generator as set forth in claim 46 including:

means for scanning through the storage locations of said bit-map-organized memory during a write cycle;

means for generating dots at selected intervals in that scanning;

means for convolving each of said dots with a generator pattern to generate convolution results in sampled-data form; and

means for writing said convolution results in sampled-data form into said bit-map-organized memory.

48. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 46 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each at least one said fractal generator, for generating different color video signals.

49. Video signal generating appratus comprising at least one fractal generator as set forth in claim 46 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each of said at least one fractal generator, for generating different intensity video signals.

50. A fractal generator comprising:

a memory storage dot intensity information in selected ones of its storage locations corresponding to points in a plural-dimensional space;

means for raster scanning the storage locations of said memory on a time-division-multiplex basis at successively lower spatial frequencies in each dimension of space to generate a number n at least three of consecutively ordinally numbered memory output signals;

a number n of convolvers consecutively ordinally numbered, respectively connected to convolve a generator pattern with the memory output signal having the same ordinal number as its own;

means for adjusting the spatial frequency phases, as referred to said first convolver convolution result, the convolution results of each of the other convolvers second through n^th ; and

means for expanding through interpolation each of the phase-adjusted respective convolution results from the second through n^th convolvers to the same sampling density as the convolution results from said first convolver and combining the expanded convolution results with each other and the convolution results from said first convolver, thereby to generate a fractal exhibiting variation in amplitude.

51. A fractal generator as set forth in claim 50, arranged for generating animated fractals by including:

means for changing, between successive field scans, the spatial offsets of the raster scannings at successively lower spatial frequencies; and

means, within said means for adjusting the spatial frequency phases, for making such adjustments between successive field scans.

52. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 51 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator for generating different color video signals.

53. Video signals generating apparatus comprising at least one fractal generator as set forth in claim 51 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator for generating different intensity video signals.

54. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 50 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator for generating different color video signals.

55. Video signal generating apparatus comprising at least one fractal generator as set forth in claim 50 in combination with:

means responsive, at least at selected times, to different amplitudes of the fractal generated by each said at least one fractal generator for generating different intensity video signals.