Abstract:
A system and method for forming a model of an underground geological formation is disclosed wherein a quantity of non-solid material of the type which solidifies at volumetric positions impinged upon by preselected incident energy as used. Memory means are provided which have uniquely addressable location for storing data indicative of the desired and actual material states at respective volumetric positions. Means are additionally for scanning the data and sequentially directing the energy at supported, non-blocking, volumetric positions in the medium volume.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates in general to beam-activated objectformation systems and relates in particular to novel methods and apparatus by means of which such systems may be employed for the construction of objects having complex geometrical form. 
     It is to be noted, however, that while the invention will be described with reference to particularized methods, embodiments and end uses, the invention is not limited to such particularizations. Those having ordinary skill in the art and access to the teachings of this specification will recognize additional implementations and utilization within the invention&#39;s scope. 
     2. Background Art 
     The composition and structure of underground geologic formations can be of enormous significance for disciplines such as natural-resource prospecting and earthquake prediction. Considerable effort is accordingly expended on the process of first obtaining and then analyzing data concerning such formations. 
     It is in the analysis phase of this process, however, that the format in which obtained data is presented to a human interpreter often significantly impacts the extent to which intra-data patterns can be perceived and their associated geophysical significance fully ascertained. This format dependence can be seen in the case of the three-dimensional reflective seismic survey, which is currently the principal technique for collecting data regarding the subject formations. Because the typical first-stage output of such a survey is a voluminous matrix of numerical values which in themselves are of limited comprehensibility, an attempt is usually made to convert the output into a more user-compatible form. The industry thus makes extensive use of expedients such as two-dimensional visual graphics of either hard-copy or computer-display variety. Furthermore, output visual effects of a pseudo three-dimensional nature are also currently achievable through an augmentation of the two-dimensional media by means of such additional graphical techniques as isometric contouring employing either color coding or perspective views. 
     Although these full two-dimensional and pseudo three-dimensional approaches are often very useful for a broad range of interpretive purposes, it has now been perceived that there are numerous instances where the availability of a true three-dimensional physical model of the subject formations would be decidedly advantageous. However, the typically-complex nature of these formations, in conjunction with the necessity for representational accuracy, renders conventional model-building techniques, which are usually manually-implemented, either physically inadequate or economically prohibitive. 
     An alternative technology which initially presents itself as a candidate for desired model-construction tasks is the ensemble of beam-activated object-formation techniques whose fundamental concepts are set forth in patents issued to W. K. Swainson. (See, for example, U.S. Pat. Nos. 4,041,476 and 4,238,840, as well as related U.S. Pats. Nos. 4,078,229; 4,288,861 and 4,333,165). Basically, the U.S. Pat Nos. 4,041,476 and 4,238,840 and references disclose apparatus for producing a three-dimensional model which includes a volume of liquid medium characterized by its solidification where impinged upon by intersecting energy beams of uniquely different properties. 
     While U.S. Pat. No. 4,041,476 (col. 12, line 10-12) and U.S. Pat. No. 4,238,840 (col. 10, line 64-66) suggest that underground geologic formations are a class of objects which can be effectively reproduced in three dimensions through the use of the disclosed system, neither reference teaches anything which, as a practical matter, would enable one to do so. 
     The U.S. Pat. Nos. 4,041,476 and 4,238,840 references disclosed a pattern-dependent, pattern-sequenced approach in which a reproduced surface is constructed by directly tracking the loci of points on the surface to be copied. The practical obstacles encountered in the use of such surface tracking are a consequence of the approach&#39;s failure to address three concurrent constructional requirements; namely, first, viewability of presently-constructed volume elements; second, non-blockage of subsequently-constructed volume elements; and third, element supportability. 
     The &#34;viewability&#34; requirement can best be illustrated by reference to the U.S. Pat. No. 4,041,476 reference&#39;s method, wherein an object is formed by means of constructional &#34;writing&#34; at a beam-illuminated intersection point located within an object-formation medium. It is apparent that a given point must be viewably accessible by the beams in order for them to intersect and the writing to be consequently effectuated. 
     The difficulty is in attempting to assure such viewability at all regions of a given complex surface, which can include multiple peaks and valleys, overhangs and other complex formations. 
     The &#34;non-blockage&#34; requirement, referred to earlier, is related to the &#34;viewability&#34; requirement in that a written point in the object-formation medium should not block the writing of a subsequent point. As it is not difficult to conceive of written blockages which no possible repositioning of write beams could circumvent, the rotating surface-tracking approach disclosed in the two references does not solve this second of the complex-modeling requirements. 
     The third requirement of surface-element supportability concerns the practical necessity for assuring that a given written element be provided with some form of structural support. While the sequential element-to-element progression which characterizes the aforemetioned references&#39; surface-tracking technique tends to assure that each written point of a simple surface will be supported by virtue of being contiguously disposed to the most-recent previously-written element, such is not the case with the modeling of complex surface formations wherein, for example, the tip of an overhang might be encountered prior to its supporting portion. Further, the unresolved problems of viewability-obstruction and subsequent-element blockage can prevent significant portions of the desired model from being sequentially constructed. 
     It thus becomes apparent that although the references&#39; general suggestions envisions complex surface modeling, they contain nothing which points the way toward the construction of complex objects such as true three-dimensional representations of underground geologic formations. 
     SUMMARY OF THE INVENTION 
     The present invention generally provides a method and apparatus for a beam-activated object-formation system in which constructional writing is performed on a co-ordinate-sequenced instead of surface-sequenced basis. The invention accordingly includes the establishment of both an object-formation volume and an associated coordinate system referenced to elemental units of this volume (voxels). The desired object is specified in terms of a provided pattern and is referenced to the voxels. Object formation is then effectuated by coordinately sequencing through the volume and constructionally writing at sequence-encountered, voxels which are pattern specified; i.e., specified as containing pattern elements to be written. A method-associated end product is thereby formed as a further-provided aspect of the present invention. 
     One aspect of the invention provides that the co-ordinate sequencing generally proceeds from a core region of the volume to a construct-encompassing peripheral region. The sequencing progression may be advantageously performed in terms of the successive generally parallel layers, radii and ordinal angles of a cylindrical coordinate system which the invention also provides. 
     Another aspect of the invention provides that the medium volume be augmented with construction-support mechanisms such as volume-defining wall members and a volume-penetrating anchor. With respect to such support mechanisms, constructional writing may be restricted to specified volume elements which are supportedly disposed contiguous to either one of the support mechanism or a previously-written element. 
     A third aspect of the inventions pertains to the constructional writing of only the outer surface of the model. By eliminating the time required to write at interior voxels, a model is constructed more quickly. If desired, the non-solid medium contained within the written surfaces may be drained from the volume and replaced with quick-setting filler. 
     A fourth aspect of the invention provides drain means for the unsolidified medium, within the written surface, in the form of a tubular volume-penetrating anchor which extends through the written surface and acts as a spout after model formation. 
     A fifth aspect of the invention pertains to the augmentation of the co-ordinate sequencing procedure by identifying voxels which have been previously written and voxels which are supportable. 
     A resequencing feature is configured to interrupt the coordinate sequencing process and return to previously-sequenced voxels which are pattern-specified and presently supported but which were not previously written because of not having been supported at the time of the previous sequencing. The writing of a voxel caues the contiguous voxels to be identified as supportable. 
     For the particularized context of complex-object modeling, the core-to-peripheral sequencing and construction-support features of the invention sequentially enable the provided beamactivated construction technique to be one in which present viewability is maximized, subsequent blockage minimized and structural supportability provided. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a cubic terrestrial section of an example underground geologic formation, the construction of a three-dimensional model of which is one purpose of the present invention; 
     FIG. 2 is schematic illustration of a beam-activated object-formation system which in accordance with the co-ordinatesequencing principles of the present invention has been configured to generate a three-dimensional model of the geologic formation of FIG. 1; 
     FIG. 3 is a flowchart of the basic co-ordinate-sequenced construction method of the present invention; 
     FIG. 4a and 4b schematically illustrate the angles, radii and layers of a cylindrical co-ordinate system utilizable in the practice of the present invention; 
     FIG. 5 is an overview flowchart of a procedure by means of which important aspects of the construction method of FIG. 3 may be implemented; and 
     FIG. 6 through 10 present a detailed expansion of the flowchart of FIG. 5. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In FIG. 1, an underground geologic formation 110, encompassed within exemplary cubic terrestrial section 120, is shown. FIG. 2 schematically illustrates a beam-activated object-formation system 200 for generating within object-formation volume 240 a three-dimensional model representative of the complex formation of interest 110. 
     System 200 comprises a volume 240 of object-formation medium 290. Activationably communicating with the formation medium in the system is a beamed-energy apparatus in the form of first and second directed-beam sources 294 and 296, conveniently lasers having respectively different central wavelengths. The system also includes controller 230 for appropriately controlling the object-formation action of the beamed-energy sources 294,296. 
     The system 200 further includes both a suitable input stage 210 for generating object-specification data and an intermediate stage 220 for converting the data into controller-compatible format. 
     The operation of the system 200 is generally depicted in FIG. 3. The process begins at stage 310 with the establishment of an object-formation volume within which the surface of interest is to be constructed. 
     In the second stage 320,(FIG. 3) a suitable co-ordinate system is established to effectively subdivide the volume 240 into a plurality of unique, locationally-identifiable volume elements 242 (FIG. 2). By analogy to the denomination of picture elements of a visual display as &#34;pixels&#34;, the resulting volume elements are conveniently labeled &#34;voxels&#34;. 
     The next stage 330 (FIG. 3) encompasses the provision of an object-specification pattern which in effect, identifies those voxels which are to be occupied by the constructed surface. The pattern is appropriately formatted in terms of the co-ordinate system which was established in stage 320 so that the appropriate voxels may be addressed for constructive writing, as subsequently explained. 
     Object-formation itself then occurs at stage 340. This is performed in a one-step or multi-step manner. In the single-step process, the volume is scanned in a co-ordinate-sequenced manner; i.e., by systematically addressing the co-ordinates of the established reference frame. Such a progression is, in its basic form, essentially independent of surface shape. However, as will be explained in detail below, system 200 departs from the systematic addressing of contiguous voxels to avoid the writing of blocking and non-supported voxels. Accordingly, in an alternative multi-step process, a plurality of scan patterns may be tried before the surface can be successfully reconstructed. 
     The writing process is finally completed at stage 346 with the actual execution of a constructional writing at those pattern-specified voxels in the sequence in which they are encountered in the course of successful co-ordinate sequencing. Of course, stages 344 and 346 may be concurrently excecuted in the single-step process. 
     1. The Basis Coordinate Sequencing Scheme 
     The described system is configured to reproduce complex surfaces because it substantially reduces the possibility that earlier written voxels will block the beams from reaching voxels which are to be written later in the scanning process. To reduce the encountering of blocking or non-supported voxels during the sequencing through voxel addresses, the sequencing is preferably carried out in accordance with a &#34;core-to-peripheral&#34; philosophy. Since the volume-penetrating write beams preferably originate from directed-beam sources positioned exterior to the construction volume, viewability tends to be maximized, and blockage correspondingly minimized, when object segments located at more-interior regions of the construction volume are written before those located at more-exterior regions. Instances are accordingly minimized wherein prior-written, but peripherally-positioned, segments block beam accessibility to voxels which are pattern-specified but positioned at less-accessible interior locations. 
     The foregoing philosophy is implemented by defining a volumetrically-innermost area from, and around, which the constructed object will grow by accretion. Naturally, the innermost region need not necessarily coincide with either the physical center of the object as finally formed or the physical center of the overall construction volume. 
     The implementation of the basic sequencing process is performed by configuring controller 230 such that coordinate sequencing generally proceeds from the now-established core region to a relatively surrounding peripheral region. 
     2. The Coordinate System 
     A further degree of performance improvement may be achieved by utilizing a co-ordinate system which has been specially tailored to enhance the effectiveness of the core-to-periphery construction process. The basic features of the preferred coordinate system are schematically illustrated with respect to a volume 440 in the side view of FIGS. 4a and the top view of FIG. 4b, as a volumetrically-rectangulated cylindrical coordinate system by virtue of the manner in which it effectively applies rectangulated cylindrical indexing to a volumetrically-aligned array of substantially equal, mutually-contiguous cubic voxels. 
     This unique co-ordinate system accordingly includes a cylindrical axis 410 which is positioned at a predetermined location within the volume 440. Axis 410 is circumscribed by a plurality of parallel, volumetrically-contiguous voxel layers as will be explained. Each voxel may be identified by an address in the form of &#34;L, R, A&#34;. The &#34;L&#34; address identifies the level of the voxel in the volume. As shown in FIG. 4a, voxel layer 411, is located at address L 2  while voxel layer 412 occupies sites at L 1  addresses. 
     The &#34;R&#34; address of the voxels is illustrated by reference to voxel layer 412. The locus 412, shown as having L 1  addresses, is seen in FIG. 4b, as being at a &#34;radial&#34; distance R 5 , from the axis; the &#34;radial&#34; distance is here defined as the larger of the two projections of the horizontal radius vector to the addressed voxel from the axis 410 upon the sides of the volume 240 considered as a cube and is conveniently measured in voxel units. 
     As may thus be seen from example locus 412, each of the coordinate system&#39;s constant R loci comprises a rectangulated, perimeteral succession of contiguous voxels. Each voxel within the locus is assigned an angular index &#34;A&#34; indicative of its position within the perimeteral succession. These angular indexes may effectively be &#34;measured&#34; from a predetermined reference ray, which in the example depicted in FIG. 4b is ray 495. 
     Returning to FIG. 2, controller is accordingly configured to establish a volumetrically-rectangulated cylindrical co-ordinate system, such as that described above, with respect to volume 240. Locus 244 within volume 240 schematically represents one of the resulting voxel loci for a constant R coordinate. 
     In the &#34;core-to-periphery&#34; constructional sequencing method the controller 230 may be further configured to initiate coordinate sequencing at the chosen zero-layer, zero-radius origin (i.e., at address 0, 0, 0) and to proceed on a generally successive radius-by-radius basis. At each radius, the voxels of the bottom-most level are addressed on an angle index-by-angle index basis successively begining with index one until all angular indexes have been addressed. The level address, L, is then incremented by one and the angular sequencing repeated. When the topmost level is completed, the bottom-most level is returned to and radius incremented. 
     The core-to-periphery, cylindrically-successive progression tends to minimize problems relating to blockage by pre-written voxels, since segments interior from the sources 294,296 tend to be written first, thus again tending to avoid situations in which the prior writing of closer segments blocks the attempted subsequent writing of more-distant segments. 
     B. Structural Support 
     The third of the previously-discussed complex-construction requirements was that the written voxels posses some form of structural support. Support may be provided by the walls 250 of the volume. Additionally, support means 255 may be imbedded in the volume, preferably along the reference axis of the coordinate system. In system 200 this anchor member advantageously takes the specific illustrated form of rod 260. It is necessary that support be composed of material that chemically or physically adhere to the formed voxels. A simple solution to this problem is to supply supports of the same composition as that of the solidified voxels, i.e., of the material produced from the medium 290 by action of laser beams produced by sources 294,296. Unique supports, appropriate to the particular object being modelled, may be designed and constructed immediately prior to actual model construction. Object segment 270 which in its illustrated condition is not yet supportedly contiguous to any of the peripheral-surface members is nevertheless supportedly stabilized by virtue of rod 260&#39;s volume-interior disposition. Accordingly, anchor rod 260 effectively provides not only construct-initiation support but also a means by which a newly-forming solid may be restrained from movement while solidification is taking place. 
     Superimposed on the generally followed scan pattern is the added stipulation that constructional writing be restricted to substantially only those sequence-encountered, pattern-specified voxels which are structurally supportable. Such support is a result of either being disposed volumetrically contiguous to a determinable one of either the support means 250 walls, the support means 255, or a previously-written voxel. Means are accordingly provided to identify supportable voxels so that non-blocking, supportable surface elements are written. If the walls are to be used as support means they must be of a material to which the formed solid voxels adhere but they must be transparent to the activating laser beams. 
     It should be recognized that there may be instances where a present writing could be effectuated and support ultimately assured, despite the fact that there is no present support for the voxel in question. For example, the viscosity properties of a given formation medium can be such as to effectively provide sufficient temporary support, enabling a subject written voxel to remain essentially suspended at a given location in the formation volume until joined by subsequently-constructed object segments. 
     It is possible that pattern specified voxels will not be written when sequence-encountered because they presently lack support; e.g., voxels at the tip of an overhanging hooked formation. A supported writing at a given voxel effectively creates support for voxels in volumetrically-adjacent co-ordinate positions. Because some of these adjacent voxels may have been previously sequenced but not written by virtue of not having been supported at the time of the previous sequencing, a supported writing creates the possibility that additional segments of the given object could be constructed by returning for constructional writing to such newly-supportable, previously-sequenced voxels. A more specific aspect of the invention thus includes a rescanning to pick up previously scanned but unwritten voxels. Accordingly, controller 230 is preferably configured such that the basic co-ordinate sequencing includes provisions for returning for constructional writing to previously-sequenced voxels which are both pattern-specified and presently supported but which were not previously written because of not having been supported at the time of the previous sequencing. In a preferred practice and configuration of the invention, the co-ordinate sequencing which then follows such &#34;returned writing&#34; can begin not at the voxel from which sequencing was diverted, but rather at the rescanned, newly-supported voxel itself. 
     With special regard to both the preferred cylindrical coordinate system and the preferred rescan sequence it may be noted that because several previously-scanned voxels are typically contiguous to a given presently-written voxel, the issue can arise as to which of these contiguous voxels is to be first chosen for resequencing in the event that two or more satisfy the given resequencing criteria. As will become further apparent from the software flowcharts and program listings subsequently presented, priorities in a preferred practice of the invention are set in accordance with an &#34;opportunity-maximization&#34; standard in which the sequencing returns to that voxel which in general will result in the greatest number of previously-scanned voxels being sequenced through again. For example, in the preferred cylindrical system, three previously-scanned voxels will be contiguous to a given general voxel: first, the same-layer, same angular index, previous-radius voxel (inner-square); second, the same-radius, same angular index, previous-layer voxel (subjacent); and third, the same-layer, same-radius, previousangle voxel. In view of the preferred sequencing procedure in which for each radius, all levels are scanned, and for each level all angles are scanned, the order in which the three previous voxels have just been here listed is also an ordinal ranking of the relative number of previous-scanned voxels available in a return to that voxel. The listed order accordingly becomes the general priority hierarchy in which the contiguous voxels are rescanned. It may be noted for the sake of completeness that the procedure is slightly different for corner voxels. Because these voxels do not, strictly speaking, possess the first type of previous contiguous voxel, the rescan at the corners is performed only with respect to the second and third voxel types. As a final related parenthetical note with regard to the corner voxels, it may be observed that while each of the other voxels in a given square possesses only one contiguous, same-level, exterior-square voxel, the corner voxels possess two such exterior, and non-diagonal, contiguities. 
     The time required for the object-construction process can be significantly reduced by restricting constructional writing to a thin shell which defines the subject surface. If required for support, strength, or rigidity, interior bracing may be provided by including such bracing in the constructional sequence. Toward this end, only the medium at surface-defining voxels is solidified, with remnant unsolidified medium being drained from the volume following the completion of the subject sequencing and solidification. Accordingly, the system 200 includes a drain mechanism for such purposes in the form of tubular anchor 260, the inner channel of which communicates with the non-solidified medium under the reproduced surface. 
     C. Controller Formatting 
     To identify non-blocking supportable voxels, a write-control field is established. Basically, the co-ordinate address of each voxel is linked to data bits which include first a status flag W indicative of whether the associated voxel is pattern-designated for writing. Each of the locations also include a second status flag SP indicative of whether the associated voxel is structurally supportable by being disposed volumetrically contiguous to a determinable one of either a support mechanism or a previously-written voxel. Finally, each location is provided with a third status flag PW indicative of whether the medium occupying the voxel has been previously written. 
     The system&#39;s beamed-energy apparatus writes at substantially only those locations which are both pattern-designated (i.e., W=1) and supported (i.e., SP=1). When a voxel is written, the support (SP) flags of volumetrically-contiguous voxels are set to &#34;1&#34;, its PW (previously written) flag is set to &#34;1&#34;. To effectuate resequencing, so that previously encountered but thenunsupported voxels can be written if now supported, the PW flags of the voxels are utilized. Specifically, previously-sequenced locations are returned to if they are both pattern-specified (W=1) and presently supported (SP=1) but which were not previously written (PW=0) because of not having been supported at the time of said previous sequencing. Sequence-encountered locations which are in previously-written status can be by-passed. 
     D. Computer Software Routine 
     1. Program Flowcharts 
     A computer software routine by means of which a computerized system controller could be configured to implement major aspects of a preferred version of the invention is presented first in overview form in FIG. 5, then in expanded form in FIGS. 6 through 10, and finally in terms of a program in a language quite similar to PL/1, listed below. It will become apparent that the subject flowcharts, especially when considered in conjunction with the foregoing detailed discussion and the following program listing, are largely self-explanatory. 
     2. Program Listing 
     A program listing for carrying out the object formation process described herein is found in the patented file as Attachment A, and is incorporated by reference. 
     While the preceding description was based on an assumed cubical configuration of both the enclosing volume 240 and the individual voxels, it may be equally convenient to operate with a cylindrical volume 240 and voxels that are of wedge, disk, or other naturally formed shapes. The programming sequence for construction may then be based on conventional cylindrical coordinates or any of seversl co-ordinates systems that will suggest themselves to the skilled artesian. The natural relationship of the construction sequence procedures to those applicable to such other co-ordinate systems will similarly be readily apparent to the skilled artesian having the benefit of these teachings and, for brevity, will not be addressed in further detail. 
     The preceding description has presented, in detail, exemplary preferred ways in which the concepts of the present invention may be applied. Those skilled in the art will recognize that numerous alternatives encompassing many variations may readily be employed without departing from the spirit and scope of the invention as set forth in the appended claims.