A STUDY OF
TWODIMENSIONAL LINE DRAWING
TRANSLATION TO
THREEDIMENSIONAL DATA
BY MAKOTO KATO
A THESIS SUBMITTED IN FULFILLMENT OF THE REQUIREMENTS
FOR THESIS RESEARCH AND PROGRAMMING
DEGREE OF MASTER OF ARCHITECTURE
IN POST PROFESSIONAL PROGRAM
SCHOOL OF ARCHITECTURE AND PLANNING
UNIVERSITY OF COLORADO AT DENVER
SPRING, 1990
THESIS TITLE
BY
ADVISER
ACADEMIC YEAR
A Study of TwoDimensional Line Drawing
Translation to ThreeDimensional Data
Makoto Kato
Prof. Robert W. Kindig
Prof. Soontom Boonyatikan
Spring, 1990
Accepted by School of Architecture and Planning, University
of Colorado at Denver in partial fulfillment of the requirements for Thesis
Research and Planning.
.......................... Chairman
(Prof. Won Jin Tae)
Committee Members
(Prof. Soontom Boonyatikan)
(Prof. Robert W. Kindig)
CONTENTS
ABSTRACT 1
INTRODUCTION
PURPOSE 2
FUTURE EXPECTATION OF THIS PROGRAM 3
PARTl:CAADComputer Aided Architectural Design
BACKGROUND 6
COMPUTER IN ARCHITECTURAL DESIGN 7
......THE SURVEY OF ARCHITECTURAL DESIGN 8
ARTIFICIAL INTELLIGENCE IN ARCHITECTURE 10
CAD SYSTEM ENVIRONMENT 11
3D GRAPHICS SYSTEM AS AN ARCHITECTUAL TOOL 13
PART2: INTERPRETATION OF LINE DRAWING BY COMPUTER
INTERPRETATION METHOD 15
LINE DRAWING CLASSIFICATION 16
PROCEDURE 19
PRIDM 21
PYRAMID 22
POLYHEDRA 23
PART3: PROGRAM
SOURCE AND RESOURCE FOR PROGRAMMING 25
THE ORGANIZATION OF THIS PROGRAM
......FILE DESCRIPTIONS 25
DATA STRUCTURE 26
MAINFRAME 27
EXPLANATION OF EACH PROCEDURE 2 8
DRAWING 29
INTERPRET 33
INSPECTION 34
PRISM 37
POLY 45
EXECUTION OF PROGRAM 5 7
POTENTIAL OF THIS PROGRAM 63
APPENDIX: 6 4
PROGRAM LIST
REFERENCE LIST
ABSTRACT:
As the capability of the computer is progressing, the CAD system is
getting closer to the architectural work. There are many kinds of software for
CAD systems, and some of them are equipped 3D modeling feature.
However, as a matter of fact, most CAD systems have been utilized just as
rendering tools for presentation, that is, few kinds of software are available
for the actual design process. The computer has been known for dealing with
a large amount of calculation in a short time, namely, it has significant
capability of numerical tasks. Meanwhile, in another field, the computer and
the software are becoming more sophisticated tool which perform non
numerical tasks such as thinking jobs.
As the computer developed, graphics became one of the most
important aspects in the function of the computer. The graphics are
represented on the screen by transacting the coordinates, on the contrary, the
computer never reacts unless the user inputs numerical factors. As long as
the coordinates is maintained in the memory of the computer, representing
3D objects on the plane monitor screen is not very difficult, today. The
difficulty stems from the method of inputting or developing 3D coordinates.
On the screen, the drawing is merely a collection of lines or a collection of
2D coordinates to the computer even if the drawing is a 3D object, because
the computer monitor represents 2D plane; that is X & Y, and the computer
doesn't have any thought or imagination which human does. This is the
radical reason that the user should assign many commands during operation
even for drawing lines in order to make the computer develop the 3D
coordinates. In today's computer graphics system, these commands are
substituting for the way of human thinking, and it is obvious that the weak
point of the system can be ascribed to a large number of commands.
The CAD system is a tool and won't replace architects. However, the
potential of the computer is unpredictable, and it will support architects with
not only drafting but also thinking tasks such as designing. Hereafter, the
CAD system has to aim to be more a sophisticated tool which has less
number of commands, and which can be used by the architect easily and
frequently. And more flexible three dimensional interface which can treat
abstract objects, such as sketches, will be required for future CAD system to
be utilized in not only the rendering process but also the actual design
process.
INTRODUCTION:
PURPOSE:
The aim of this research is to evolve a method of translation of a line
drawing of a solid on a plane to a three dimensional coordinates. This
research is giving importance to abstract drawings, which has no exact
dimensions such as sketch, rather than precise draftings. The reason is that
today's CAD systems are very powerful as a drafting tools, however, there
are quite a few CAD systems which are effective to the actual design
process. Because, in the actual design process, abstract line drawings of
three dimensional objects are very important for designers to focus their
attentions on the spatial volume and the form, and present CAD system are
not equipped with such a flexible interpretational algorithm.
During the past twenty years, the background of this research has
been developed in both architecture field and engineering field. In
engineering field, the CAD system received great attention even if the
capacity of the computer was not strong enough, or even if the good system
was expensive because of mass production system. However, In architecture
field, the system was not so capable tool because one planning is available
for only one project in most cases, and it was too expensive and too weak to
utilize for each project, so that some theories and algorithm, which were
researched in the past, couldn't get attention and couldn't achieve success.
Particularly, the computational speed of representation of 3D objects was too
slow to use. But last ten years, the capacity of the computer was developed
significantly, and some systems or programs became useful even for the 3D
graphics. At present, the computer is still developing rapidly. The super
computer will be a kind of integrated expert system, and the personal
computer will also have a great capability which only the super computer
has, today. Therefore, more sophisticated algorithm will be able to be
adopted to the future CAD system.
Some of algorithm in this research, which we can not find in
conventional CAD systems, are based on the human interpretation of line
drawing because some of the line drawings can not be interpreted
mathematically. Adding some human interpretation makes the computer
interpret the line drawing of solid on the plane screen as a three dimensional
solid easier, and developing this kind of algorithm will make the use draw
3D objects like a sketching on the paper without assigning many commands.
Practically, this is one of the inevitable research to advance the CAD system
drastically, and to transform today's CAD system to a real architectural tool.
This is one of the primitive program, which is equipped with those
new algorithm. This program differ from the conventional 3D CAD system
in terms of interrupting a 2D drawing as a 3D object. After drawing an object
on a screen, this program interprets a direction of each surface and create 3D
data (coordinates) of not only visible surfaces but also hidden surfaces
automatically. Eventually, this algorithm reduces the amount of annoying
command works of present system; therefore, this can be utilized in many
ways to upgrade the CAD system. In addition, being accompanied with free
hand drawing recognition algorithm, which interpret lines, curves, comers,
etc, the system will be really powerful, in other words, will be easy tool to
use.
FUTURE EXPECTATION OF THIS PROGRAM:
The algorithm of interpretation of 2D line drawings as 3D solids is
inevitable to be the true integrated 3D CAD system. In this research, only the
method of translation from a 2D drawing to 3D coordinates data was
concerned. The reason is that the method of interpreting drawings has some
patterns in theory, and by formulating those method, drawings can be
interpreted. However, another things such as the interpretation of the free
hand drawings doesn't have any theory because those drawings are
interpreted by human experience in most cases. Those kind of research are
classified in AI (Artificial Intelligence) field which deals with human
experiences. If a drawing is clear enough, that can be interpreted by this
algorithm, but if not, the help of AI will be required. At present, still AI is
under development, so that continuing this research is important as well.
If the computer interprets the relation of lines, drawing on the
computer could be easier, and modification of lines will be done without any
command automatically. Therefore, when the algorithm of this program is
connected to the free hand drawing recognition algorithm, the system will
more powerful and more convenient. Users will be able to draw objects
without any command, so that they can concentrate on designing.
Not only algorithms or programs, but the computer environment will
be developed. Particularly, the input device and the monitor screen are
crucial things for the architectural CAD system because those are substituting
pencil and paper. At present, MOUSE and DIGITIZER are the most popular
input devices, but those are much different from conventional drawing tools.
As a monitor device, there is no special device at present, and too difficult to
understand large drawings because of the small screen. In near future, new
monitor device should be concerned, and if one screen is not enough for
architectural work, more than two screens should be recommended as well.
IMAGE OF NEAR FUTURE CAD SYSTEM
eleuation
r \
V J
elevation
Vs_________________________________________t
Near future CAD system will equip additional large input
device which serve both as a input and a monitor. A current
working drawing may be shown on the large device, and at the
same time, the other monitor may keep showing another
drawings.
I will not say the future CAD system replaces pen and paper even if
the system will be more sophisticated tool. Those are fundamental tools for
designing, and it's almost impossible that the computer devices imitates
many kinds of paper quality and pen pressure. But it can be a real design
supportive tool which works almost same tool as pencils and papers, and
sometimes it will be more useful. And the CAD program as a rendering tool
will increase speed more and show more realistic, or sharper, pictures.
Consequently, the future CAD system will have both the actual design
function and the rendering function and will be utilized from the beginning to
the end of architectural projects.
This program has algorithm to create 3D coordinates from line
drawings on the screen. Therefore, many types of application programs can
be developed from this program,this program can be combined into another
application programs, such as 'mass volume calculation', 'shadow
simulation',etc. The following picture is just a possible user application
utilizing this program.
This program maintains 2D coordinates of original drawing
and 3D coordinates created by computer in the memory. By
modifying those coordinates, many applications can be
concerned.
PARTI: CAAD
Computer
Aided
Architectural
Design
BACKGROUND:
The development of computer aided design occurred in earnest
in the early 60's. The system allowed engineers to generate designs at
interactive graphics terminal, and manipulating drawing displayed on the
screen by use of lightpen and keyboard. Many that interactive computer
aided design system were installed in automobile and aero space firms
by the end of the 60's. Since then, computer aided design had been
increasingly widely employed in various aspects of mechanical, civil,
electrical, chemical., and industrial engineering.
The application of computer aided design in architecture
followed slowly behind application in engineering. The main reason of
slow response was obviously economic. Automobile and aerospace
firms are capable of investing capital in expensive equipment because of
the big budget for the design of one product, while the design cost must
be be kept to a small fraction of the project in architectural firms. Since
early CAD system costs hundreds of thousands or even millions of
dollars, they were out of concern of architects.
However, as the technology continued to develop, and as costs
of the system dropped significantly, it slowly became an reality to the
architects, and first installations of interactive computer graphics
systems in architectural offices began to appear in the early 70s.
Basic research in computer aided architectural design has been
supported by a few government and private agencies and private
foundations. Several universities, such as MIT, Pennsylvania State
University, CarnegieMellon University, etc, have carried out quite
extensive research programs. Some institutes have focused on building
description and space planning issues and also artificial intelligence
orientation. In addition to carrying out research activities, many school
of architecture now offer courses in computer aided design.
The 80's came about as a turning point of the computer aided
architectural design system. Network system was introduced in the
working area providing the opportunity of using big capacity
computers. And some computer languages were developed specially for
the purpose of computer graphics, such as AutoLISP. Moreover, low
cost personal computer systems are developing quickly as well, and
increasingly being installed in architectural firms.
COMPUTER IN ARCHITECTURAL DESIGN:
The first 'successful' use of computers in architectural field was
in procedures where large amount of calculation were done, such as
structural and energy analysis, relieving designers from tedious tasks.
The next major advancement in CAD system came about with the
development of computer graphics, which are currently used as a
drafting tool by many designers. This use of computer, however, is still
limited and doesn't affect the actual design process. There are many
factors that architects don't use computer in the design. The main point
is that still pen and pencil is much, more convenient than the computer,
because architects have to deal with many information, theories and
problems at a same time, and designing goes back and forward all the
time. And abstract forms, which are mainly come from architects'
imagination and experience, is dealt in main design phase. Speaking of
the system, some programs have very good qualities, but the more
programs become powerful, the more commands users need to
remember. This is the most crucial point of present CAD system. The
next generation CAD system must aim to reduce the number of
commands maintaining present functions and each CAD command and
menu should be easy to use.
Even so, practically, the CAD system has great potential to be a
real architectural supporting system. The present system and program
are also very useful in terms of 3D view function, even though user
need to practice to operate efficiently. The CAD system can help
architects to transform design drawings directly into working drawings
and enable them to continue making design decisions throughout the
construction document phase. A consequence is that the preparatory
frontend work that is done early in a project becomes increasingly
important (Figure 1.1).
Accompanying with the Artificial Intelligence computer system
the CAD system will be able to deal with complicated tasks including
some thinking tasks. But it is not necessary to fully automate the
process of design in order to significantly improve design productivity
and quality. On the contrary, it is necessary to decide which tasks could
but should not be computed by the system and how computational and
manual design practices can be combined effectively without losing
design continuity.
INTERRELA TIONSUIP
BETWEEN COMPUTER AND DESIGN PROCESS:
Computer
Design Process
Freehand drawing recognition
(straight line recognition)
(curved line recognition)
(comer recognition)
$
Error recognition & correction
(Interrelation among lines)
3D drawing recognition
(hidden line interpretation)
(hidden surface interpretation)
Data base
(environmental data)
(predefined furniture)
Dimension
(numerical factor)
Freehand drawing or sketch
(rough)r 
1st stage drawing
(rough)
2nd stage drawing
(rough)
=*f
3rd stage drawing
(precise)
.
drafting (precise)
Figure (1.1)
There are two problems of interaction between designer and
computer in CAD. The first is the description and graphic representation
of 3D objects. Second is the formalization of comprehensive and
complicated design procedure. In order to solve those and improve CAD
system, we need to explore the architectural design process and thinking
mechanism in architectural design.
Design Stages:
In early stage of design, architects do some creative thinking and
research, specification, hypothesis, physical representation, analysis,
evaluation, comparison, modification, and hypothesis, physical
8
representation ...(repeat). In time, the architects take pencils and paper.
For the first drawing, soft pencils are used to sketch abstract
representations on tracing paper. And modifications are made by
moving, taping, and overlaying pieces of paper. Tens of, hundreds of
these unsealed drawing may be drawn in early design process. During
iteration of the design, graphical representations become more elaborate.
The 2D design process are 'space allocation' and 'general
circulation paths'. The 3D design process are 'spatial performance' in
order to achieve wellproportioned overall dimensions, and 'visual
performance' in order to achieve welldesigned exterior and
environment.
In final stage of design process, the basic hypothesis become
more important and the design effort is focused on subparts and detail.
And cooperation is needed from consultants in various specialized
engineering fields. Att this stage, the 2D design process is 'drawing '
with appropriate numerical value for computation, such as floor plan,
elevation, section, etc. And the 3D design process is 'perspective
rendering' in order to inform the appearance of the building.
Phase of Design:
Design is claimed to consist of two phases. The first is 'pre
sketching phase' as problem understanding or formulation. And the
second is 'sketching phase' as problem solution.
In presketching phase, three tasks of thinking are included.
First, the subjects gather information from the problem documents
(information acquisition). Second, they interpret this information to
generate design criteria (problem interpretation). Third, the information
gained about the problem is stored by a memory mechanism in order to
guide future activities (problem representation).
In sketching phase, a solution for a design problem is usually
equivalent to providing appropriate physical object descriptions. A
design solution can be seen as a physical object description that starts
from a relatively abstract formulation and progressively becomes more
specific. Four cognitive mechanisms are identified to represent this
phase;
1 Generation of partial solution
2 Integration of solution
3 Assessment of solution
4 Sketching and visual perception
ARTIFICIAL INTELLIGENCE IN ARCHITECTURE>
The concept of the Artificial Intelligence computer is to solve
abstract problems, such as interpretation of plans or drawings. The way
to interpret problems done by AI computer is very similar to the way
done by the human brain.
Initially, the AI algorithm was researched for imitating the
mechanism of complicated human judgement, such as nuclear reactor
control or surgical cure support,etc. The algorithm of the AI program is
formatted similar to a neural network of the human brain, so that it
learns and increases knowledge; that is, multiplies judgement data base
by itself. Therefore, AI computer is very effective to the architectural
work that many thinking tasks need to be done.
Using AI algorithm, the free hand recognition system was
already researched and achieved success. In architectural drafting, there
are many rules to present plans, elevations, sections, etc. However, In
order to understand designer's rough sketches or abstract drawing in
early stage of design, we must input many information of
interpretational judgement from our experience. Moreover; architects
usually need to consider enormous amount of information to make a
decision or to design, Environment, Structure, Circulation, of course
Design, etc. As a matter of fact, in order to make the AI computer
handle those information, a huge capacity of data base is required, and
user have to replace every information about each project except
common data base. The followings are four examples of difficulties to
AI computer as an ideological or cultural subsystem;
1 Formalization of concept:
For example, what is the concept of privacy (visual,
auditory, dimensional) ? Can it be represented in a certain set
of rule?
2 Procedure:
Is it possible to run algorithm to resolve conflictive situation?
How can it compare the performance of 2 layouts in terms of
privacy?
3 Data:
For example, it is well known that as individual
"appropriate" a certain amount of space around him. It is a
volume of comfort and privacy. How should it be measured?
In terms of distances, area, volume?
4 Computer output:
Should an architectural drawing be generated, the quantity of
which is measured not only in terms of the quantity of
information it carries, but also in terms of aesthetics? If not,
the computer generated drawing may not be accepted by
professionals.
The capability of the AI computer of reading and interpreting
and evaluating plans is still in a part of science fiction. But the AI
computer already has a ability to translate free hand drawings into fine
drawings in 2D, and some easy conditional judgement can be done. As
a matter of fact, the AI system doesn't have to be so intelligent as
human, and also it is almost impossible, because design decision done
by human depends on not only architects' experience but also architects'
creativity. Even if judgements can not be done by the AI system, it will
be able to interpret and evaluate drawing with help of the user. Although
there are many conceptual difficulties, it is obvious that the artificial
intelligence approach becoming more important in Computer Aided
Architectural Design in near future.
But one thing we should keep in our mind that the use of any
computer tool to aid the design has a prerequisite: the computer can
arrange existing things but never have creativity that's why the final
decision always depends on the designer. Even with the best tool,
architect will be necessary to solve and to make a decision in any
architecture which perfectly suits to human needs.
Although the ability of CAD system depends on the program,
the capacity of the computer itself should be concerned as a different,
aspect of the CAD system, as well.
During the past ten years, the capacity of the computer
progressed remarkably in terms of memory capacity and computational
speed, and both of them are critical matters for the computer aided
graphic design, particularly. The computer which equips high capacity
computer processor can compute and show graphics very quickly, and
even complicated graphics can be changed the view point without lag.
But the cost of the system is out of investment range in most of
architectural firms. Speaking of the personal computer, today's personal
computer has (or more) ability of the super computer in the past.
Comparing to ten years ago, in which average processor was 4bit or 8
bit, the present average personal computer, whose processor is 32bit,
became very powerful and fast. And memory capacity changed from
Kilobytes to Megabytes. So, graphic managemental capacity,
especially in terms of speed, was developed notably. Several
workstation CAD system became almost real time (nolag) operation
system, which is ten or twenty times as fast calculation as the system ten
years ago.
Even average hundreds dollar personal computer with enough
memory capacity, most of computational waiting time for graphic
generation or modification are almost in bearable limits, except some
commands such as 'remove hidden line'. The progress of the computer
is so quick. In next two years, 'laptop' portable computers are going to
equip same capacity of the present personal computer, and the personal
computer will have 64 bit processor soon.
As the computer science technology developed, the computer
system has been changed as well. The multiuser systems became more
efficient than individual small capacity computers. That allows several
users to share main facility, including large capacity computer system,
using large scale computer networks. It also makes transference of files
between computer terminals easier.
Input and Monitor Devices
There is one more reason that CAD system doesn't prevail in
architectural field. That is a weakness of input interface. Comparing to
conventional designing tools, computer input devices; MOUSE and
DIGITIZER, are much different and awkward to design. The most
radical difference between conventional designing tools and computer
input devises is that a plane for moving hands and the other plane for
observing drawing result are not same. Those computer input devises
are available for picking point on the screen, such as digitizing map or
editing lines. There are another devices called LIGHTPEN and PEN
DIGITIZER. Comparing to present popular devices, those have a
possibility to be a designing computer input devices because the
digitizing tablet represents paper and the digitizing pen represents
pencils.
Speaking of monitor device, the definition of the screen will be
improved more. But the most important issue about monitor screen in CAD
system is the size of screen. When drawing size is large, today's display is
not useful sometime because zoom out screen is too ambiguous to see detail,
and zoom up screen is hard imagine whole design. Therefore, as a designing
monitor screen, using more than two displays or introducing multiwindow
system in large screen is recommended, so that designer can observe several
views at once.
Recently, a new input interface was developed in SEIKO
Electrical Industry. That has electricpen and large LCD tablet (you can
imagine as a screen of calculator), which also function as a monitor
screen. This system can be connected to personal computer with sketch
recognition system and writing recognition system, and now, as a
whole, that system has a capability to translate free hand plan drawing
into fine drawing. The cost of those system is: program $3000, input
device also $3000. It is not expensive investment even for individual
user.
As a example of above, the computer input interface also need to
be change to more useful and humanoriented devise for designers. And
program must more flexible, in other words, more sophisticated.
3D GRAPHICS SYSTEM AS AN ARCHITECTUAL TOOL:
The description and the 2D representation of 3D objects are an
important part of design process in architecture. Since 3D modeling system
had been developed, the CAD system increased the efficiency of the design
process by allowing the designer to review design solutions in 3D without
making models. And today, the ability of graphic representation, especially
in terms of 3D, is a key of CAD system. In terms of drafting, the present
CAD system has remarkable ability and many useful functions such as
COPY, MIRROR, or ZOOM, etc, but the function of the system has not
been changed for a long time in spite of development of the computer. And
because of so many commands and requirement of precision, however,
today's CAD system has been awkward tool for actual design process. In
order to be a real architectural design tool which can be utilized in creative
work, still there are many problems and theories to be solved.
At present, many programs use "solid" 3D shapes, modeled either as
enclosed forms (boundary representation ) or as true solid volumes
(constructive solids geometry ). Such models provide the designer with the
option of realistic shading, and they can be "scalped" as well, as if they were
made of modeling clay. Speaking of the method of input 3D object, some 3D
programs come with libraries of standard architectural forms and also allow
for drawing and saving custom forms as work progress.
In conventional architectural work, sketching has always been
important. As a result of that CAD systems don't have any 3D object
recognition algorithm, users has not been able to work on 3D graphics
easily. They always need to assign any base 2D surface such as plan or
elevation because the computer can handle 2D object, then, the object is
recognized as a 3D object by assigning the other dimension such as height or
width. In AutoCAD program, in order to work in 3D drawing, user need to
specify the coordinates system which fixes the direction of a base plane. As a
matter of fact, many user annoying how to set up coordinates system and
how to change this.
The conventional 3D graphics is called '2&1/2D graphics'
theoretically, because it must be defined by 2D and ID separately. Shortly, it
is a kind of expanded model of 2D system. Although it develops 3D data
eventually, the system is not interpreting an object as a solid. According to
Crosley (1988), "The true integration of 3D means that plans, elevations,
and sections can be drawn within the same model data base" (121). Crosley
goes on to point out that when any modifications are made in a perspective or
a axonometrical view, the same modifications would occur automatically in
plans and elevations as well, because those are sharing the same data base.
Not only a modification of lines, the real integrate 3D system should be able
to add another objects or change form in perspective or axonometrical view;
that is, more flexible 3D interrace can support a sculptural approach,
encouraging the exploration of vertical space and form. As matter of a fact,
when many walls have to be drawn in same height, 2&1/2D is more
convenient than 3D, so we can not ignore some useful functions in 2&1/2D.
But the 2&1/2D graphics algorithm and almost considerable function are
invented, it just depends on computational speed. In order to progress into
next phase, a real 3D graphics algorithm, namely, 3D object recognition
algorithm should be added to conventional 3D graphics system.
PART2: INTERPRETATION OF LINE
DRAWING BY COMPUTER
INTERPRETATION METHOD:
Interpreting drawings is much different from calculation tasks. In
order to interpret drawings, the drawing must be transferred into some
computational factors somehow. Some algorithms of interpretation of line
drawing were proposed in the past. Those can be classified into two
categories, one is based on 'pattern recognition method', and the other is
based on geometrical, in other words, 'mathematical method'.
The pattern recognition method is very effective to drawings which
consist of basic objects. Those objects are predefined and stored in the data
base, so this method is also called 'datacollection method'. When any
drawing is input, the computer refer the drawing to the data base, then if the
configuration of the drawing is same one in the data base, the computer
defines the drawing as one object. The advantage of this method is if data
base contains data of figures which is simple but hard to interpret
mathematically, such as a pyramid or a hippedend roof, etc, the computer
can interpret without any difficulty. Although this method is effective when
the object is a synthesis of some simple solids, it has no effect when the
object has some concave parts or can not be separated into simple solids.
Also in order to utilize this to a real design, huge data base will be required.
The geometrical interpretation method is to recognizes the object by
classifying the relationship between lines and configuration of junctions. In
order to avoid confusion of drawings it works with assumptions. Some
examples of the assumption are:
a Every edge is shared by exactly two faces,
b Each line in a line drawing is to correspond to
some edge of an object,
c Every surface doesn't have any thickness.
.........................................etc.
Using those assumptions, the computer classifies the characteristic
of lines, then using those classified lines, each line junction in the drawing
is also classified. If there is no contradiction among those junctions. The
drawing was interpreted as an object. Although this algorithm is very
powerful to the trihedral object (each vertex has no more than three lines),
when the object has slant surfaces and lines, or when the object has
interrupted lines, it is not so useful because of restricted assumptions and
rules.
As a result, the best algorithm of the interpretation of line drawings
must has good points of both algorithms, then each algorithm supports the
other's weak points. And in order to be a more powerful system, it should
be accompanied with Artificial Intelligence algorithm which represents the
human experience because people always draw lines by their experience.
I
n this program, although every process is a set of calculation, most of
evaluations of conditions are based on the human experiences. And as we
know, the computer can do only one thing at once. Therefore, whenever the
computer goes into next step, if there is any possibility, it must check every
possibility. At the beginning, this program examines if a line drawing is a
primal solid, such as cube, prism, or pyramid, etc, because it's easy to
interpret these objects referring to our experience. In case that an object is
not a primal solid, the program goes into another procedures which are
dealing with a nonprimal solid.
LINE DRAWING CLASSIFICATION:
In the object recognition algorithm, the interpretation of line
drawing is the most important and effective for designing with the computer
because objects are usually drawn on the paper by drawing edges of the
object; that is wire flame model. Each line of the wire flame model
represents boundary of two area, or a surface and background. The people
can interpret the object on the paper as a mass or a solid, however, today's
3D graphics system isn't equipped with the algorithm to interpret drawing
as a solid. As a matter of fact, this assumption doesn't work in real
designing because drawing lines doesn't always represents the boundary.
The line sometimes expresses texture of the surface or doesn't make any
sense, shortly mistake, or on the contrary, designers sometimes forget to
draw lines where those should be. In order to interpret those difference, the
computer actually need to infer designers intention from the drawing.
However, algorithm of interpretation of real drawing is out of ability of
usual program, it's in a field of Artificial Intelligence computer. Therefore,
only a simple wire frame model drawing is concerned in this paper.
Speaking of line drawings interpretation method, two kinds of
representation methods are concerned. Those are what Sugihara (1986)
calls, "hiddenpartdrawn line drawing and hiddenparteliminated line
drawing "(1516) (Figure 2.1).
Hiddenpartdrawn
line drawing
Hiddenparteliminatcd
line drawing
Figure 2.1
The hiddenpartdrawn line drawing is effective to represent
backsides of the object, which we can not see. But, different expression of
line must be used for hidden lines, and sometimes the drawing becomes
complicated because of many lines especially on the computer monitor
screen. The hiddenparteliminated line drawing doesn't represent any
hidden part. However, the people have an ability to guess the hidden part of
the object from our experience unless the object is so complicated.
Moreover, this method is more natural and clear to imagine the object
because of less lines. Therefore, The hiddenparteliminated line drawing is
concerned as one of the best methods, and this research is dealing with it.
Even if a line drawing is simple, sometimes the line drawing can not
be interpreted mathematically. For example, pyramid, this object classified
in a elementary solid group, but the computer can not interpret if a base
figure is threesides, foursides, or more than five. On the other hand, even
if a drawing is complicated, it is very easy to interpret the line drawing by
referring to our experience. The human experience will help to interpret line
drawings, especially hidden side. There is a premise: the computer doesn't
have to guess more than people can do. If there are some suppositions,
computer may choose most common and easiest way.
In the hiddenparteliminated line drawings, the drawings has many
kinds of characteristics. Those can be classified in some categories. A
diagram shows the classification of line drawings and some line drawings
of solids are shown as examples (Figure 2.2).
LINE DRAWING CLASSIFICATION:
Figure (2.2)
PROCEDURE:
In order to make the interpretation easy, some initial settings for
drawings should be provided to the program. Grid patterns are the most
important setting for input drawings because this assigns the drawing style,
such as axonometric or oblique (Figure 2.3). Moreover, the drawing style
effects to the interpretational procedure, especially the determination of the
surface orientation. Even if the direction and the length of a line is same, the
characteristic of the line in 3D is different in each drawing style. When the
drawing is so simple like a box, the computer may interpret the drawing
method as well, but if drawing is not simple, it is very difficult to infer the
characteristic of lines. In addition, one more reason for the grid indication is
the grid leads drawings.
DRAWING STYLES ( PROJECTION SYSTEM):
I I
ORTHOGRAPHIC OBLIQUE
AXONOMETRIC
!1
ISOMETRIC TRIMETRIC OBLIQUE
Figure (2.3)
As a another style, there is a PERSPECTIVE. This drawing
method is very effective to check the mass proportion which
people actually see. The algorithm of translation from 3D
coordinates to 2D perspective view is not difficult, but the
opposite way is too complicated to understand the interrelation
of lines, especially in case of the drawing of objects has slant
surfaces.
This program deals with the oblique style. In this style, the direction
of surfaces are classified into seven categories (Figure 2.3). Three surfaces
out of seven surfaces are base surfaces which are parallel to the XZ plane,
the YZ plane, and the XY plane each. Another three surfaces are defined as
middle surfaces of two base surfaces, such as a surface which is a rotated
XZ plane around Z axis. The rest one is the surface which is not belonging
to any those categories, or it can be said as a middle surface of two of those
six surfaces.
CLASSIFICATION OF SURFACE DIRECTION:
Figure (2.3)
'fig' values are used in program
According to the grid pattern, X axis, Y axis, and Z axis are
predefined as a 2D vectors. Each surfaces are examined if contour lines of a
surface are on those axes. For example, the surface which are parallel to the
XZ plane (fig=l) consists of X axis and Z axis. In fact, this definition is not
always correct because the surface may have some inclined lines. Therefore,
the definition of contour lines in this program has a more flexible one which
checks contour lines as a whole.
As a matter of fact, even flexible definition has one problem. In case
of that drawing has a parallelogram, it is very difficult to determine without
observing the drawing as a whole that if that figure is really a parallelogram
surface or merely a rotated rectangle. It is not impossible to deal with this
kind of problem mathematically. But the AI system is more suitable for this
kind of problem.
The following are examples of the interpretation procedure of 3D
object line drawings. The computer can not inspect the drawing as a whole
at once like people observe drawings. Therefore, the computer examines the
drawing each segment by each segment, then when every segment is 'true',
the computer judges the drawing is a certain kind of objects. As I mentioned
before, some elementary objects can be interpreted by referring to our
experience because those figures have certain characteristics, and by
checking those, drawings can be interpreted much easier.
The characteristic of prism is that it has two same figures in parallel,
and every side surface is rectangle. Therefore, the drawing should have
some sets of parallel lines.
This program examines if the drawing has a such characteristic or
not, then if the program judges every parts much to this characteristic, the
program goes on to definition procedure.
Parallel lines between two parallel surfaces.
These lines are called 'Height Line' in program.
Some pairs of parallel lines which one belongs to a top
surface and the other belongs to a bottom surface.
These lines are called 'Base Checking Line' in program.
In case that any line is interrupted by any surface, In order to make
the computer understand the line is interrupted, this program uses different
values to the point from regular point values. If the length of one of those
parallel lines is shorter than normal lines, the computer refer to the point
value, then if the value means interruption, the program outputs 'true' and
goes on checking.
(research only, not programmed)
The characteristic of pyramid (in this research, Tetrahedron is also
concerned as a same characteristic) is that two triangles are joined at one
line. Joining of two triangle doesn't always mean the drawing is a pyramid.
Therefore, in case that the drawing is simple enough, the computer can
assume that the drawing is a pyramid. The point of the pyramid
interpretation is how to, and where to define the apex.
First, create two supplemental lines (2D) from the middle point of
visible lines of the base (line 1&2 in a diagram), then calculate 2D
coordinates of crossing point. Second, from the apex, set a vertical
supplemental line (2D) and pull it down to the base. If the distance between
the crossing point and the vertical line is small enough, even if the point is
not exactly on the line, define the 3D coordinates of the apex using 2D
coordinates of the crossing point and length of vertex.
However, the apex is not always located in the center of the object.
If the crossing point and the vertical line is not close enough, the other
calculation method must be done. First, create one supplemental line (2D)
from one of the vertexes of the base to a opposite side line. Second, from
the apex, set a vertical supplemental line (2D) and pull down to the base.
Even if these lines are 2D, assume that the angle of these two line is 90
degree and that the line is perpendicular to the base. From the 2D
coordinates of the crossing point, define 3D coordinates of the apex.
2 2
This procedure is for the object which doesn't belong to any
elementary object. Therefore, the program doesn't try to find specific
characteristics of the object, just follows the general characteristic of the
object. It is different from Prism or Pyramid that the hidden line and hidden
surface must be calculated each by each.
First, the program defines surfaces which no part of surface is
obstructed by any surface. Because the contour line of the surface is closed;
so that no modification is required. Each surface is classified by checking the
configuration of contour line, then defined as 3D surfaces.
In many case, the hiddenparteliminated line drawing has surfaces
which is partlyhidden or completelyhidden inside of contour line. As a
second procedure, the program modifies partlyhidden surfaces. From our
experience, the location of the hidden point or the hidden line of the partly
hidden surface can be guessed. Therefore, this procedure creates new lines
or modifies old lines and encloses incomplete contour line, so that a partly
hidden surfaces change into a completelyvisible surface, and defines 3D
surfaces. Then third, if there is any remained surface inside of contour line,
find that surface and define using 3D coordinates of vertexes which already
defined. After finishing third procedure, the computer already has a 3D data
of the inside surfaces.
Fourth, define 3D coordinates of the base using the contour lines.
The method is to refer to the contour line. The hidden line of the base are
assumed that it is a same figure as a figure of contour lines, which doesn't
belong to the base, with Z axis value is zero. Except some lines of those
which are perpendicular to the base, the computer transfers only X and Y
values of those lines into the base.
At last, using those 3D data of inside surfaces and the base, calculate
the rest of surfaces and define 3D data of those surfaces.
2 4
PART3: PROGRAM
SOURCES AND RESOURCES FOR PROGRAMMING:
a: Programming Language : THINK's Light Speed Pascal
b: Computer : Macintosh 2 & Mouse
c: Reference Books about programming and graphics:
Pascal on the MachintoshGraphical Approach
THINK's Lightspeed PascalUser's Manual
Inside Machintosh I, II, III
3D graphics
d: Some procedures from my previous thesis
e: Geometry
THE ORGANIZATION OF THIS PROGRAM:
Units in this project (shown by the build order);
Runtime.lib
Interface.lib
PrinterCalls.lib
MacPrint.p
Script.p
UDemoUtils.p
ABOUT
DRAWING
INSPECTION
PRISM
POLY
INTERPRET
DEMO
MAIN
:automatically installed in project (predefined program)
automatically installed in project (predefined program)
library for the Toolbox Print Manager (predefined program)
:interface programs for printing (predefined program)
:interface programs for Script Manager (predefined program)
:a file for global variables and utilities (predefined program)
:a file for indicating the initial screen
:a file for setting window and inputting a drawing
:a file for finding a certain line or examining a surface figure
:a file for interpreting a drawing of prism
:a file for interpreting a drawing of polyhedra
:a file for main routine of the interpretation procedures
:a file for demonstration after interpretation
:a file for main routine for whole program
Procedures in each Unit (shown by build order)
ABOUT DoAbout
DRAWING......... pro7, proA, alteration, linedraw, screen, drawing
INSPECTION either, oneline, nextline, rectangle, twothree
PRISM prejudge, evaluation, prismjudge, prismdefine, prism2
POLY............ contour, polydefine, check, classify, segA, complete, modify
incomplete, remain, hidden 1, hidden3, hidden
INTERPRET startingpoint, initial, prism 1, polyhedra, interpret
DEMO threetwo, location, setting, original, demo, PRINT
MAIN............ MAINPRO (main routine)
Following variables are main variables to pursue this program. 2D
data consists of point variables and line variables. Using those 2D data, this
program creates 3D data of points and surfaces of an object, eventually.
2 Dimensional:
point: X[n] 2D X coordinates of point #n
Y[n] 2D Y coordinates of point #n
F[n] point classification
F[n]=0: comer (point on point)
F[n]=l: T junction (point on line)
line: Line[n, 1 ] start point number of line #n
Line[n,2] end point number of line #n
Line[n,3] line classification
Line[n,3]=0,2,4 : line of inside
Line[n,3]=l,3,5 : line of contour
note: In case that line[n,3] is 0 or 1, those means checked 0 time,
2 or 3 means checked 1 time, 4 or 5 means checked 2 times.
3 Dimensional:
point: TX[n] 3D
TY[n] 3D
TZ[n] 3D
surface: SFN
VNB[n]
SPN[n,m]
X coordinates of point #n
Y coordinates of point #n
Z coordinates of point #n
the number of surfaces
the number of vertexes of surface #n
point number of #m point of surface #n
note: Line data is common to 2D.
26
Main frame of this program consists of three main procedures, which
are 'drawing', 'interpret', and 'demo'. The procedure 'drawing' has a role
of indicating initial screen, setting up drawing screen, and inputting a line
drawing on the screen. After drawing, the program proceeds to the
procedure 'interpret' and create 3D coordinates of the line drawing. Finally,
using those 3D coordinates, the program demonstrates some different views
such as perspective and plan. The procedure 'print' is an addition procedure
to print out the demonstration screen.
MAIN FLOW CHART
EXPLANATION OF EACH PROCEDURE:
The main program consists of many procedures. Each procedure
explains variables which were used in the procedure, and shows flow chart
of the program graphically. The order of procedures is different from built
order for reasons of making program understandable. In addition, some flow
charts explain only one case in some cases, but it is not big concern in a flow
chart because every case is sharing same concept.
I abbreviated explanations of procedure 'DoAbout', 'demo' and the
other procedure which belongs to 'demo' because these are just one of
examples of applications and these procedures are not main subjects to my
research, and because those kinds of programs can be seen in many books
about computer graphics. I also omitted to print out 'MacPrint.p', 'Script.p'
and 'UDemoUtils.p' because I adopted from predefined Machintosh
program without any modification. If one wants to take a look at or study
those, please refer to Libraries and Interfaces in the application of THINK's
Lightspeed Pascal.
Signs in procedures:
(START) : start f procedure
(END) : end of procedure
execution statement
procedure
condition statement
INDEX of Units:
DRAWING 29
INSPECTION 3 3
INTERPRET 34
PRISM 3 7
POLY 45
screen, linedraw, pro7, proA, alteration,
either, oneline, nextline, rectangle, twothree
startingpoint
initial, prism2, prejudge, evaluateline, prismjudge,
prismdefine
polyhedra, contour, complete, segA, check, classify,
modify, incomplete, remain, polydefine, hidden,
hidden l,hidden3,
screen
.OB: Drawing screen indication,
constants:
distance: refer to diagram
left,top,right,bottom: X, Y screen coordinates for setting
drawing screen
variables:
xd,yd,xe,ye: coordinates of defined points on drawing screen
remain: for setting drawing window on the screen
2 9
linedraw
JOB: Draw line drawings on the screen and create 2D data,
variables:
k: current number of lines
j: current number of points
hor, ver: screen coordinates for a start point of a line
horizontal,vertical: screen coordinates for a end point of a line
xi,yi: 2D coordinates for inputting data
ml: total number of lines
mp: total number of points
(START)
{flag: end of drawing}
(END)
(setting current point number and line number)
(dummy coordinates of starting point}
(coordinates correction}
(setting startpoint of a line}
(flag: end of drawing}
{inspection and defining of start point}
(define start point of line}
(flag)
(inspection and defining of a new line}
(setting new current line number}
proA
JOB: Inspect if a new point is located at any exist point,
or if it is on any exist line.
variables:
x[n],y[n],f[n]: refer to data structure
p,q: checking variables
bot, act,result,flag, mark: flags
a,b,c,d,e,h,g,u,v: substitute variables
3 1
pro7
JOB: Inspect if a new line is passing over any exist point.
variables:
r: checking variable
result, mark: flags
a,b,c,d,e,h,g,u,v: substitute variables
(START)
{define end point of line)
{In case new point is on exist line,
no need to do this procedure)
{ignore first line)
{if new line is passing any exist point)
{if 'r' is max point number)
21
T= r+1
alteration
OB: Correct 2D coordinates to the nearest defined point for data.
variables:
hx,hy: coordinates error
{correct coordinates to nearest defined point)
{from screen coordinates system
to standard coordinates system)
X Y
v L
32
x
startingpoint
JOB: Find start point number for calculation,
the lowest and the most right side.
variables:
start: start point number for calculation
n,m: just variables
{set two points
numbers)
{check from #1 until max
point number)
{compare Y coordinates)
{choose poinr number which
has lower Y coordinates)
{In case of that both Y coordina
are same, compare X coordinate:
and choose point number which
higher X coordinates)
initial: refer to PRISM
prism2 : refer to POLY
polyhedra : refer to PRISM
onelinel
JOB: Find one line which has point number 'p', then output point number
'q' which is the other side of the line. In case that line number comes up
to max line number, 'O' will be output instead.
variables:
p: current base point number
j: checking variable (different from variable for point number)
either
JOB: Choose one of two lines comparing with one base line,
variables:
cx,cy: variables for a vector of a base line
vx[l],vy[l]: variables for a vector of one line
vx[2],vy[2]: variables for a vector of the other line
pn[l],pn[2]: next point numbers for two lines
ln[l],ln[2]: next line numbers for two lines
turn: explain below
sna,snb,csa,csb: sin values and cos values for two lines
select: flag
about 'turn':
turn=l:
tum=2:
{choose clockwise first line from base line}
/
' > (base line)
{choose counterclockwise first line from base line}
/
> (base line)
When a vector of the base line is fixed on X axis, relations between
the base line and the other 2 lines are classified as follows;
sna*snb>0
sna>0 & snb>0 > Xj/. i i
sna<0 & snb<0 i i i i
'yr* "kr
sna*snb<0 f
sna*snb=0 : :
csa*csb>0 h
csa*csb<^ i
csa*csb=0 ...k i i >
According to values of sin and cos, and a value of 'turn', this
procedure choose one proper line, and output a line number, the other point
number of the line, and a vector of the line as ln[l],pn[lj, and vx[l],vy[l].
nextpoint
JOB: Find next base line and next base point,
variables:
startpoint: current base point number
the other: refer to another procedure
prism2
JOB:This is a main routine of the prism interpretation procedure.
According to a base line (initial) find a base surface (rectangle),
then examine if a line drawing is a primal solid.
There are three condition judgements if the drawing is a prism
or not. If the program proceeds to 'prismdefine', a variable of
'define' becomes T, this means the drawing was interpreted, or
if the program skips to the end with 'define=0', the program
proceeds to polyhedra interpretation procedure.
variables:
base: classification variable
fig: classification variable
(STA RT)
beginpoint=start
{find base surface according to
base line)
{hag)
{classification of base surface}
{flag}
{examine if a line drawing
is prism or not)
{flag}
{define 3D coordinates of prism}
{flag}
(END)
3 7
initial
JOB: Find a base line.
variables:
base: classification variable
beginpoint: start point number of a contour of a surface
curline: current base line number
count: number of lines of a surface
prism, pyramid, define: flags
[  rectangle 
JOB: According to a value of 'base', find a base surface and specify a
characteristic of the base surface.
variables: "
beginpoint: start point number of a contour of a surface
base: classification variable
(START)
(base=l: a base line on X axis
base=2 : a base line on Y axis]
(find a line connected to a base line)
{according to a relation of two lines,
choose base surface classification]
(setting a variable for number of
lines of a surface]
{judge base suface classification
with all lines of a surface]
{if come back to start point
for checking]
(END)
3 9
A following diagram shows classification procedure from 'initial' to
'prejudge'.
40
[_prejudge 
JOB: Classify base surface into three pattern for procedure 'prismjudge'
variables:
fig: classification variable
{using values from 'rectangle',
classify conditions of base surface
into three categories for 'prismjudge'}
(fig=l : surfaces which are in parallel
with each other on XZ surface
{fig=2 : surfaces which are in parallel
with each other on YZ surface
(fig=3 : surfaces which are in parallel
with each other on XY surface}
{fig=0: nonprism}
11 prismjudge
JOB: According to a value from 'prejudge', examine if line drawing is
prism or not.
variables:
cex,cey,cfx,cfy,fp,fx,fy,fcl: substitute variables
bx,by: checking base variables
hx,hy: checking base variables (height line vector)
poly: the number of lines of a base surface
j,p,q: checking variables
prism, result: flag
 prismdefine 
JOB: If'prismjudge' outputs 'prism=l', means the line drawing is a
prism, creates 3D coordinates of the line drawing
variables:
sfn: the number of surfaces (=poly+2)
vnb: the number of vertex (=poly+l; start point is double)
spn[n,m],tx[n],ty[n],tz[n]: refer to data structure
vn,vm: substitute point numbers
Flow chart of "prismjudge"
Z7
VZ7
fZJ/
(no height line)
{come back to
beginpoint.
end of check}
Flow chart of "prismjudge"
(START)
___ i ________
sfn=poly+2
vnb[ l]=poly+l
vnb[sfn]=poly+l fatrfacc)
vnb[m1=5
{the numb< r of surfaces)
(the number of lines of a
vn=beginpoint
tx[vn]=0
ty[vn]=0
tz[vn1=0
{3D
coodinatcs of
base point)
spn[l,l]=vn
spn[2,2]=vn
tx[vm]=tsx
ty[vm]=tsy
tzfvm]=tsz
spn[sfn,vnb]=vm
spnf2,3)=vm
jn=l
d=l
jn=jn+l
startpoint=vn
cx=hx
cy=hy________
nextpoint
X
sx=cx
sy=cy
X
twothree
X
vn (new} =startpoint
tx[vn(new) l=tx[vn{oId)J+tsx
ty[vn {new} ]=ty[vn {old )]+tsy
tz[vn{new)]=tz[vn{old)]+tsz
{if there is a exisbi . ^
point on the^^^f r9 \S Y.axis
drawing, height^lini
use that point number, ryes
If not, create  a=startpojnt~
new point number)
no
SX=CX
sy=cy
a=mp+add
twothree
in
vm=a
tx[vm{new)J=tx[vm{old}]+tsx
ty[vm{new}]=ty[vm{old)]+tsy
tzfvm {new) ]=tz[ vm {old) ]+tsz
spnf l,jn)=vn
spn[jn,l]=vn
spn[jn,5]=vn
spn[sfn,vnbjn+l]=vm
spn[jn,4]=vm
spn[jn+l,2]=vn
spn[jn+l,3J=vm
(END)
SIMULATION OF DEFINING 3D SURFACES:
Surface
number:
poly=6
X\V^i\Vs7 sfn=Poly+2=8
ZxNN^lXV vnb[l]=poly+l=7
/r~7\ 3
3 4 ! i, ,6
5 V O z A
6 1,7 /
1,7
7^7
ZZ7
/ 7
define:
spnf l,2]=vn
spn[2,l]=vn
spn[2,5]=vn
spn[3,2]=vn
spn[2,4]=vm
spn[3,3]=vm
spn[8,6]=vm
define:
spn[l,4]=vn
spn[4,lj=vn
spn[4,5]=vn
spn[5,2]=vn
spn[4,4]=vm
spn[5,3]=vm
spn[8,4]=vm
define:
spn[ l,6]=vn
spn[6,l]=vn
spn[6,5]=vn
spn[7,2]=vn
spn[6,4J=vm
spn[7,3]=vm
spn[8,2]=vm
define:
spn[l,l]=vn
spn[2,2]=vn
spn[2,3]=vm
spn[8,7]=vm
vm:(point number)
vn:(point number)
beginpoint
/ /.
/ // 1 $
define:
spn[l,3]=vn
spn[3,l]=vn
spn[3,5J=vn
spn[4,2]=vn
spn[3,4]=vm
spn[4,31=vm
spn[8,5]=vm
define:
spn[l,5]=vn
spn[5,l]=vn
spn[5,5]=vn
spn[6,2]=vn
spn[5,4]=vm
spn[6,3]=vm
spn[8,3]=vm
define:
spn[l,7]=vn
spn[7,l )=vn
spn[7,5]=vn
spn[7,4]=vm
spn[8,l j=vm
/ 7
(return to beginpoint......stop......END)
44
11 polyhedra]
JOB: This is a main routine of polyhedra interpretation,
variables:
int: interrupted point number
j: checking variable
contour
JOB: Find all lines of contour and change a value of line classification to T.
This means contour line and checked one time.
variable:
result, flag, mark: flag
j,a,b,c,d,e,h,g: checking values
complete
&
seg A )
JOB: Find a surface which has a closed contour line.
The computer checks contour line by both clockwise and
counterclockwise to avoid miss going.
(It happens when a surface has a interrupted line.)
variables:
flag, result,mark, act: flag
k,a,b,c: checking variables
str,cxr,cyr,cur: keeping variables for switching the way to check
stl,cxl,cyl,cul: keeping variables for switching the way to check
rl: a variable to decide the direction to check (right or left)
stb: keeping variable of point number for checking if contour line is
closed.
(START)
{ find the first line of the first surface.)
1 initial vector for
countcrclockwasc}
in order to avoid miss going,
computer checks contour line
of a surface using two direction.)
{ as checking is going, the computer
puts the information of the line, in
order to define the direction of the
surface when the surface was confirmed
as a completely visible surface. )
when contourline is closed, the computer
checks the figure of the surface and determine which
surface classification this surface belongs to. )
(define 3D surface )
II classify I [
JOB: Record characteristic of each line of a contour line to decide the
direction of a face when the contour line is closed.
variables:
cls[nj: classification variables for each line characteristic
ox, oy: vrialbles for a vector of not X, Y, nor Z axis.
Method:
When a line is parallel to the X axis, it is recorded in cls[ 1 ]
When a line is parallel to the Y axis, it is recorded in cls[2]
When a line is parallel to the Z axis, it is recorded in cls[3]
When a line is not belong to those three, it is recorded in cls[4]
When a line is belong to none of those, it is recorded in cls[5]
check 
JOB: According to classify', define surface direction ('fig' value).
Method:
In case count=3 (triangle)
For example, 2 lines belong to cls[l] or cls[2] (X and Y), assume the
surface as a XY plane (fig=3). 'flg=2' or 'fig=l' is also same method.
In case the contour line is not like those, 'fig=0' will be output in order to
avoid defining the surface.
In case count= 4 (tetragon)
For example, if 2 lines belong to cls[ l] (X), and if more than one line
belong to cls[2] (Y), assume the surface as a XY plane (fig=3). Tig=2' or
'fig=l' is also same method.
In case 2 lines belong to one of base axis, and the other 2 lines belong to
cls[4], this surface will be classified as a slant rectangle (fig= 4, 5, or 6).
In case none of those, define 'fig=0'.
In case count >4 (polygon)
If cls[3]=() and cls[4]
either X or Y axis except one line, therefore, assume the surface as a XY
plane (fig=3).'fig=2' or 'fig= 1' is also same method.
In case none of those, define 'fig=0'.
 incomplete
JOB: Find a surface which is obstructed by any surface. The computer starts
to check from interrupted point, then after checking two lines, assume
'fig' value. When a line is not on the axis which it should be, line
creation and modification are executed, (continued to next page)
variables:
act, flag, result, face: flag
stp, cex,cey: keeping variables for sending values into 'modify'
opp, icx, icy, ist, icu: keeping variables for second surface.
(START)
{find first line)
no
cx=x[plx[q] icx=cx
cy=yfp]ylq] icy=cy
startpoint=q ist=start point
curline=j icu=curline
(facc=l: the line has one incomplete surface)
{facc=2: the line has two incomplete surface)
{ i?? are valiablcs to keep currcntline information)
p=q;j=i
yes
nextpoint
classify
determine 'fig'
face=face2
tum=opp
cx=icx
cy=icy
startpoint=ist
curline=icu
count=2
count=count+l
stp=startpoint
nextpoint
(END)
oneline
{find second line)
cx=x[p]x[q]
cy=y[p]y[ql
startpoint=q
curline=j
{ in order to use 'turn' value from next time, need to calculate the
geometrical relation between the first line and the second line and
define the value)
{ from those two lines, assume 'fig' value)
{ as long as the checking
current line is on the surface
keep searching changing point)
{ use values 'int' and 'stp', modify the surface)
{ in case of that two partlyhidden surfaces are attached
each other,go back to define the other surface)
4 9
 modify J
JOB: According to the 'fig' value, modify 2D coordinates of the
interrupted point, and create new line if necessary.
Method:
First, assume the obstructed figure is a rectangle.
Modify 2D coordinates of the interrupted point to where it should be.
Create new line between 'int' and 'stp'.
If there are two obstructed surfaces attached together, the program executes
this procedure again.
MODIFICATION MEHTOD with formula.
5 0
remain
JOB: Find a surface whose every contour line classification (line[n,3]) is
'2', this means every line was checked once. 3D coordinates of all
edges should be already defined; therefore, what this procedure
needs to do is defining the order of point number.
variables:
flag: flag
(START)
curline=j
p=line[j,l]
q=line[j,2]
cx=x[qx[p]
cy=y[q]y[p]
startpoint=p
beginpoint=p
spn[sfn,l]=p
count=l
nextline
{in this procedure, llic program
assumes that the drawing contains
only one undefined inside surface)
{ for the othc case, this procedure
need to be modify)
{ the computer simply find out
a remained onctimcchcckcd
line which already has 3D
coordinates)
{ no need to define
3D coordinates, but
define vertex number
of the surface)
( END)
polydefine I
JOB: Define a surface as a 3D surface which was checked in 'complete' or
'incomplete'. Checking start point number and current line variables
(dst, dex, dey, dcu) are input from those procedure.
variables:
result: flag
m, a, b: checking variable
icx, icy,ist,icu: keeping variables
(continued to next page)
(START)
i cx=dcx startpoint=dst
 cy=dcy curline=dcu
tx[startopint]=0
ty[startpoint]=0
tz[startpoint]=0
vnb[sfn]=count+l
spn[sfn, 1 )=startpoint
d?? values arc inputted from
previous procedure }
the origin point of the first
surface was defined as (0,0,0)}
turn=2 m=l
! m=m+l
back to the
previous line
tum=l
tum=2
i
this is an additional
procedure for incomplete
surfaces, because next line
can not be found according
to a 'turn' value, in case of that,
the computer find another line)
a=line[curline,l]
b=line[curline,2]
line[curline,l]=b
line[curline,2]=a
(exchange the order of point
number of a line, because
this procedure is a key to
avoid overlap defining)
(skip defining a line rr::> which already checked once)
line(curline,3)= ine[curline,3]+2
( +2 means checking once }
spnfsfn,m]=spn[sfn,l]
a=line[curlinevl ]
b=line[curline,2]
tx[b]=tx[a]+tsx
ty[b]=ty[a]+tsy
tzb]=tz[a]+tsz
sfn=sfn+l
(END)
[defining the 3D coordinates
of the point)
f
spn[sfn,m]=startpoint
j line[curline,3]=line[curline,3]+2
+2 means checking once }
j hidden
JOB: This is a main routine of hidden surface procedure. First, find two lines
belong to a hidden surface and find contour line of the surface (hidden 1),
then start to trace contour line. In case there is no contour line where it
should be, find reference line and transfer to the surface (hidden3).
Finally, when contour line is closed, define the surface as a 3D.
variables:
hid, flag, result: flag
tt: variable for elevation of a surface to compare
qq, jj: point number and line number of the one of two base lines
a, b, c, d, cxa, cya, cza, cxb, cyb, czb: variables for calculation
(START)
( at this satge, the computer find
base two lines wlhich arcincluded
in hidden surface)
define (tt) I Uhs va'uc >s used 10 compare
I ~~~~~ the elevation of with a reference line)
a=x[qjx[p]
b=y[q]yfp]
C=x[qq]x[p] ( check geometrical relation between these two lines
d=y[qq]y[p] in order to know which line is the first, and second)
spn[sfn,l]=q
spn[sfn,2]=p
spn[sfn,3]=qq
3D define)
spn[sfn,l]=qq spnsfn,2]=p spnsfn,3]=q
beginpoint=q beginpoint=qq
curline=jj curline=j
line[jj,3]=line[jj,3]+2 line[j,3]=line[j,3]+2
q=qq
sfn=sfn+l
hid=hid+l
I____
f transfer the values of those lines into
oj (
hidden3
global valiablc, and send in to 'hiddcn3'}
! hidden 1 j
JOB: This procedure is executed from second hidden surface.
Find two base lines belong to hidden surface, whose point number of
one side is 'p'. Then output values of the other side point numbers and
the line numbers of those two lines (q, j) & (qq, jj).
variables:
flag, mark, result: flags
c: classification variable for cases
qqq, pp, dj, dc, jjj; keeping variables
Method:
Find a point which has 2 lines whose classification value are '3' and 1 line
whose classification value is '5'.
The first hidden surface, which is the base surface of the object, has been
already defined; therefore, there are lines whose line classification are '5'.
The point of hidden surface should have 2 lines whose line classification
are 3', and some point may have 1 line whose classification is '5'.
jl hidden3 
JOB: Trace a contour line of a hidden surface. And define the surface as a 3D
when it's closed.
variables:
flag, result: flag
aa, bb, cc: variables for 3D vector of a reference line
po: variable for a point number of a new point
TRANSFERENCE OF REFERENCE LINE :
reference lines
The rest of hidden surfaces:
(START)
count=4
(END)
EXECUTION OF PROGRAM:
How to draw:
When this program is executed, the initial screen will come up. Then
click anywhere on the screen to proceed to the drawing screen. One segment
can be drawn by clicking and holding, dragging, and releasing mouse (this
method is same as drawing a line, not poly line, in MacDraw 2). After
completing drawing, clicking left and top comer finishes input procedure and
makes the program proceed into interpretation procedure.
Drawing input:
1 4
POLYHEDA
During drawing a line drawing, this program reads 2D coordinates of
each point from drawing window, and creates data of the line drawing.
These data will be a base for interpretation. Followings are data of line
drawings above, which are developed according to those drawings.
The most important thing in input procedure is that no matter how
users draw a line drawing, program interprets drawing identically, only
difference is location of point number.
Data of points:
PRISM
1 2 3 4 5 6 7 8 9 10 11
X 150 120 180 180 220 220 120 210 210 250 250
Y 160 130 130 110 110 70 70 160 140 140 100
POLYHEDRA
1 2 3 4 5 6 7 8 9 10 11 12 13
X 140 110 170 200 110 130 130 170 190 190 200 150 150
Y 150 120 120 150 60 60 100 100 120 80 90 80 100
f 0 0 0 0 0 0 0 0 0 0 0 0 1.
57
Data of lines:
PRISM
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
start 1 2 3 4 5 6 7 1 8 8 9 9 10 10 11
end 2 3 4 5 6 7 2 8 3 9 4 10 5 11 6
POLYHEDRA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
start 1 2 3 4 2 5 6 7 3 8 9 10 4 10 13 12
end 2 3 4 1 5 6 7 8 8 9 10 11 11 12 12 6
classify 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1
(after 'contour' procedure)
PRISM
total number of lines = 15
total number of points =11
start point number = 6
POLYHEDRA
total number of lines = 16
total number of points =13
start point numter = 5
After finishing drawing, this program executes interpretation
procedures, and creates 3D data of objects. The interpretation of prism is
different from the polyhedra's one, and it doesn't use all 2D data. On the
other hand, The interpretation of polyhedra uses 2D data fully; moreover, it
creates additional 2D data in order to interpret drawings, too. A following
table is polyhedra 2D data which modified during interpretation procedure.
And following diagrams show 3D coordinates of each vertex of line
drawings above.
MODIFIED POLYHEDRA DATA
POINT:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
X 140 110 170 110 130 T3?T T7tr 190 190 200 150 130 140
Y 150 120 120 150 60 60 100 100 120 80 90 80 120 90
f 0 0 0 0 0 0 0 0 0 0 0 0 1 0
LINE:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
start T 3 IT 5 6 6 8 8 9 9 11 4 10 13 12 13 7 11 14 14
end 2 3 4 1 5 6 7 8 8 9 10 11 11 12 12 6 9 13 14 5 1
classify 5 4 4 5 5 5 4 4 4 4 4 5 5 5 4 5 4 4 5 5 5
(after 'hidden' procedure)
Created 3D data:
1:1100.60.601 8:11060.601
1:10,60,60)
2:000,0^60)
12:000,60,0)
7:0 00,0,0)
9:(40,60,40)
3:(40,0f60)
4:140,0,40)
10:10,60,40)
I 1:10,60,0)
6:10,0,0)
2:(0.iK60)
SilO.O.O)1
7:(2 1,0,40)
4:(60,60,60)
3:160,0,60)
9:160,40,40)
8:160,0,40)
"7v,I:(60,60,0)
0:160,40,0)
After developing 3D coordinates of the object, a plan, a elevation,
and some perspective views are demonstrated for confirmation of 3D
coordinates, finally. Then, the program proceeds to printing routine to print
out the demonstration screen. Following pages are examples of print out.
ORIGINRL
PLAN
PERSPECTIVE
o
VO
ORIGINAL
m
PLAN
PERSPECTIUE
ELEURTI ON
VO
POTENTIAL OF THIS PROGRAM
Within two semester, in order to accomplish whole process, some
limitation were set up.
The object of this program is one line drawing.
As a input drawing procedure, drawing method was programmed in one
method (45 degree) and no drawing error correction algorithm (no erase
function) was programmed, this means any drawing error is not allowed in
this time. If one makes drawing mistake, needs to stop the program and go
back to start.
As a interpretational procedure, prism and some part of polyhedra were
dealt. The conditional judgements were limited and were not sufficient
enough to interpret many drawings at present. In addition, the line drawing
must be corrected because the computer doesn't interpret the drawing if it
doesn't have lines where those should be.
In order to make this program interpret drawings which have slant surfaces
or which is combination of pyramid and box, more condition judgements are
required.
However, this program can be a base of an integrated program of line
drawing interpretation. By increasing conditional judgements this program
will be able to interpret more objects including drawings with minor errors
and increasing transitive values allowing the user to draw in many drawing
methods. By modifying 3D data, synthesis of more than two line drawings
could be interpreted eventually. As a next step, the issue need to be
concerned is, how the incorrect drawing should be dealt. It is supposed to be
corrected automatically if it is minor error, but if not, what should the
computer do? And as a another interpretational method AI program should be
concerned as well.
APPENDIX:
04/19/90 22:44
DRAWING
Page 1
unit DRAW;
interface
uses
UDemoUtils, About;
v a r
x; array[1..30] of integer;
y: array[1 ..30] of integer;
f: array[1 ..30] of integer;
line: array[1..30, 1..3] of integer;
ml, mp, start: integer;
k, j: integer;
const
distance = 10;
left = 0;
top = 40;
right = 640;
bottom = 480;
procedure pro7 (var pm, act: integer);
procedure proA (var pm, bot, act, xi, yi: integer);
procedure alteration (var xi, yi: integer);
procedure linedraw;
procedure screen;
procedure drawing;
implementation
procedure pro7 (var pm, act: integer);
var
r, result: integer;
a, b, c, d, e, h, g: integer;
begin
if act <> 1 then
begin
:= pm;
:= 0;
line[k, 2]
line[k, 3]
act := 0;
r := 1;
result :=
1;
if k <> 1 then
while (result <> 0) and (r <> j 1) do
begin
a = x[line[k, 1]] div 10
b = y[line[k, 1]] div 10
c = x[line[k, 2]] div 10
d = y[line[k, 2]] div 10
e = x[r] div 10;
h = y[r] div 10;
g = ((b d) e + (a * d
b c) (a c) h);
if g = 0 then
if a = c then
if ((b < h) and (h < d)) or ((b > h) and (h > d)) then
{put x[r],y[r] into line [k,1]line[k,2]}
04/19/90 22:44
DRAWING
Page 2
begin
result := 0;
f[r] := 1; { interrupted mark }
end
else
r := r + 1
else if ((a < e) and (e < c)) or ((a > e) and (e > c)) then
begin
result := 0;
f[r] := 1;
end
else
r := r + 1
else
r := r + 1;
end;{while}
end
else
begin
act := 0;
line[k, 2] := pm;
line[k, 3] ;= 0;
end
end;
procedure proA (var pm, bot, act, xi, yi: integer);
v a r
a, b, c, d, e, h, g: integer;
flag, result, mark: integer;
m, n; integer;
begin
if k >= 2 then
begin {1}
m := 1;
flag := 0;
while flag = 0 do
begin {while1}
if (x[m] = xi) and (y[m] = yi) then
begin
flag ;= 1;
pm := m;
end
else if m = j 1 then
begin {2}
flag := 1;
n := 1;
result := 0;
while result = 0 do
begin {while2}
a := x[line[n, 1]] div 10;
b := y[line[n, 1]] div 10;
c := x[line[n, 2]] div 10;
04/19/90 22:44 DRAWING Page 3 d := y[line[n, 2]] div 10; e := xi div 10; h := yi div 10; g := ((b d) e + (a d b c) (a c) h); if g = 0 then {put(hor,ver) int line[n,1][n,2]]} begin {3} if a = c then if ((b < h) and (h < d)) or ((b > h) and (h > d)) then mark := 1 {do} else mark := 2 {don't} else if ((a < e) and (e < c)) or ((a > e) and (e > c)) then mark := 1 else mark := 2; case mark of 1: begin result := 1; x[j] := xi; y[j] := yi; f[j] := 1; pm := j; j := j + 1; if bot = 2 then act := 1; end; 2: begin if n = k 1 then begin result ;= 1; x[j] := xi; yUl > yi; f[j] := 0; pm := j; j := j + 1; end else n := n + 1; end end {case} end {3} else ifn = k1then begin result := 1; x[j] := xi; y[j] := yi; f[j] := 0; pm := j; j := j + 1; end else
04/19/90 22:44
DRAWING
Page 4
n := n + 1;
end {while2}
end {2}
else
m := m + 1;
end {while1}
end {1}
else
begin
x[j] := xi;
y[j] := yi;
m := 0;
pm := j;
j := j + 1;
end
end;
procedure alteration (var xi, yi: integer);
v a r
hx, hy: integer;
begin
hx := xi mod distance;
hy := yi mod distance;
if ((xi div distance) + (yi div distance)) mod 2 = 0 then
if hy < distance hx then
begin
xi := xi  hx;
yi := yi  hy;
end
else
begin
xi := xi + (distance  hx);
yi := yi + (distance  hy);
end
else if hy < hx then
begin
xi := xi + (distance hx);
yi := yi hy;
end
else
begin
xi := xi hx;
yi := yi + (distance hy);
end;
xi := xi;
yi := (bottom top) yi;
end;
procedure linedraw;
var
hor, ver, horizontal, vertical: integer;
04/19/90 22:44
DRAWING
Page 5
xi, yi, xic, yic: integer;
pm, bot, act; integer;
begin
k := 1;
j := 1;
xi := 100;
yi := 100;
while (xi > 20) and (yi > 20) do
begin
bot := 1;
repeat
getmouse(hor, ver);
until Button;
xi := hor;
yi := ver;
alteration^, yi);
xic := xi; { keep valiable for }
yic := yi; { click miss transaction }
Moveto(hor, ver);
if (xi > 10) and (yi > 10) then
begin
proA(pm, bot, act, xi, yi);
line[k, 1] := pm;
bot := 2;
while Button do
begin
Penpat(white);
lineto(hor, ver);
getmouse(horizontal, vertical);
penpat(black);
lineto(horizontal, vertical);
end;
xi := horizontal;
yi ;= vertical;
alteration(xi, yi);
if (xi = xic) and (yi = yic) then { click miss transaction }
{ do nothing }
else
begin
proA(pm, bot, act, xi, yi);
pro7(pm, act);
k := k + 1;
end
end
else
begin
MoveTo(20, 20);
writedraw('END');
ml := k 1;
MoveTo(20, 30);
writedraw(TOTAL LINE NUMBERS, ml);
mp := j 1;
MoveTo(20, 40);
04/19/90 22:44
DRAWING
Page 6
writedrawfTOTAL POINT NUMBER = mp);
end
end;
end;
procedure screen;
v a r
xd, yd, xe, ye, i: integer;
savePort: GrafPtr;
begin ,
{ShowDrawing;} ""
{SetRect(remains, left, top, right, bottom);}
{SetDrawingRect(remains);}
savePort := GetNewWindow(RsrclD(1), nil, Pointer(1));
(SetWRefCon(DemoWindow, Ord4(SELF));}
SetPort(savePort);
DemoWindow := savePort;
SizeWindow(DemoWindow, right left, bottom top, true);
MoveWindow(DemoWindow, left, top, true);
SelectWindow(DemoWindow);
ShowWindow(DemoWindow);
DoAbout;
xd := 0;
yd := 0;
repeat
repeat
PaintOval(yd, xd, yd + 1, xd + 1);
xe := xd + distance;
ye ;= yd + distance;
PaintOval(ye, xe, ye + 1, xe + 1);
xd := xd + 2 distance;
until xd > right;
xd := 0;
yd := yd + 2 distance;
until yd > bottom top;
i := 0;
repeat
FrameOval(0 + i, 0 + i, 20 i, 20 i);
i ;= i + 2
until i >= 10;
end;
procedure drawing;
v a r
r: integer;
begin
screen;
linedraw;
for r := 1 to mp d o
04/19/90 22:44
DRAWING
Page 7
begin
MoveTo(x[r] 15, (bottom top) y[r]);
writedraw(r);
end
end;
end.{ UNIT INPUT }
04/13/90 22:43
INSPECTION
Page 1
unit INSPECTION;
i nterface
uses
DRAW;
v a r
cx, cy, ox, oy: integer;
vx: array[1..2] of integer;
vy: array[1..2] of integer;
pn: array[1..2] of integer;
In; array[1..2] of integer;
p, q: integer;
turn, startpoint, curline, beginpoint, count: integer;
base, fig: integer;
sx, sy, tsx, tsy, tsz: integer; {twothree}
procedure either;
procedure oneline;
procedure nextpoint;
procedure rectangle;
procedure twothree;
implementation
procedure either;
v a r
sna, snb, csa, csb: real;
select; integer;
begin
sna := cx vy[1 ] cy vx[1 ];
snb := cx vy[2] cy vx[2];
if (cx / 10 vx[1] + cy / 10 vy[1]) = 0 then
csa := 0
else
csa := (cx / 10 vx[1] + cy / 10 vy[1 ]) / sqrt((sqr(cx / 10) + sqr(cy / 10)) (sqr(vx[1 ]) +
sqr(vy[1 ])));
if (cx vx[2] + cy vy[2]) = 0 then
csb := 0
else
csb := (cx / 10 vx[2] + cy / 10 vy[2]) / sqrt((sqr(cx / 10) + sqr(cy / 10)) (sqr(vx[2J) +
sqr(vy[2])));
if sna snb > 0 then
if ((sna < 0) and (csa > csb)) or ((sna > 0) and (csa < csb)) then
select := 1
else
select := 2
else if sna snb < 0 then
if sna < 0 then
select := 1
else
select := 2
else if sna > snb then { in case of sna*snb=0 )
select := 2
04/13/90 22:43
INSPECTION
Page 2
else
select := 1;
case turn of
1:
begin
if select = 2 then
begin
vx[1] := vx[2];
vy[1] := vy[2];
pn[1 ] := pn[2];
ln[1] := ln[2]
end
end;
2:
begin
if select = 1 then
begin
vx[1] := vx[2];
vy[1] := vy[2];
pn[1] ;= pn[2];
ln[1] := ln[2]
end
end
end { case }
end;
procedure oneline;
v a r
flag: integer;
begin
flag := 0;
while flag = 0 d o
begin
if j <> curline then
if line[j, 1] = p then
begin
flag := 1;
q := line[j, 2]
end
else if line[j, 2] = p then
begin
flag := 1;
q := liney, 1]
end
else if j = ml + 1 then
begin
flag := 1;
q := 0;
j := j 1
end
else
{ transaction for the case of}
{ that' mp=curline }
{ valiable adjustment }
04/13/90 22:43
INSPECTION
Page 3
j := j + 1
else
j := j + 1
end
end;
procedure nextpoint;
v a r
flag: integer;
begin
p := startpoint;
j := 1;
oneline;
vx[1] := x[q]  x[p];
vy[i] := y[q]  y[p];
pn[1] := q;
ln[1] := j;
flag := 1;
while flag <> 0 do
begin
j := j + 1;
oneline;
if q <> 0 then
begin
vx[2] := x[q]  x[p];
vy[2] := y[q]  y[p];
pn[2] ;= q;
ln[2] := j;
either
end
else
flag := 0
end;
startpoint := pn[1 ];
cx ;= vx[1 ];
cy := vy[1 ];
curline := ln[1]
end;
procedure rectangle;
v a r
flag: integer;
begin
if base = 0 then
base := 0
else if base = 3 then
fig := 3
else
begin {1}
startpoint := q;
turn := 2;
nextpoint;
04/13/90 22:43
INSPECTION
Page 4
case base of
1:
begin
if cx = 0 then
base := 4
else
begin
ox := cx;
oy := cy;
base := 5
end
end;
2:
begin
if cx = 0 then
base := 6
else
begin
ox := cx;
oy := cy;
base := 7
end
end
end;{ case }
flag := 0;
count := 2;
while flag = 0 do
begin
nextpoint;
case base of
4:
begin
if (cy <> 0) and (cx <> 0) then
base ;= 8
end;
5:
begin
if (cy <> 0) and ((oy / ox) <> (cy / cx)) then
base := 8
end;
6:
begin
if (cx <> cy) and (cx <> 0) then
base := 0
end;
7:
begin
if (cx <> cy) and ((oy / ox) <> (cy / cx)) then
base := 0
end;
otherwise
base := base {no change}
04/13/90 22:43
INSPECTION
Page 5
end; {case }
if startpoint = beginpoint then
begin
count := count + 1;
flag ;= 1 { completed }
end
else if f[startpoint] = 1 then
begin
base := 0;
flag := 2 { incomplete }
end
else
begin
flag := 0;
count := count + 1
end
end { while }
end {1}
end;
procedure twothree;
begin {if grid=1 then }
case fig of
1:
begin
tsx := sx;
tsy := 0;
tsz := sy {div 4 {undecided}
end;
2:
begin
tsx := 0;
tsy := 2 * sx;
tsz := sy  sx
end;
3:
begin
tsx := sy  sx;
tsy := sy * 2;
tsz := 0
end
end
{else if grid=2 then (for another grid pattern)}
end;
end. {UNITINSPECTION}
04/18/90 23:57
PRISM
Page 1
unit PRISM;
i nterface
uses
DRAW, INSPECTION;
v a r
{ 3D SURFACE VALIABLES }
sfn; integer;
vnb; array[1..30] of integer;
spn: array[1..30, 1..30] of integer;
tx: array[1..30] of integer;
ty: array[1..30] of integer;
tz: array[1..30] of integer;
{ surface number }
{ the number of vertexes of surface#? }
{ vertex number of surface# & vertex order# }
{ }
3D COORDINATES OF VERTEX }
{ )
procedure prejudge;
procedure evaluateline (var fp, bx, by: integer);
procedure prismjudge;
procedure prismdefine;
procedure prism2 (var define: integer);
implementation
var
hx, hy: integer;
poly, prism: integer;
procedure prejudge;
var
flag: integer;
begin
fig := 0;
case base of
4:
begin
if count = 4 then
begin {1}
j := 1; {check point}
flag := 0;
while flag = 0 do
begin { while1 }
p := startpoint;
oneline;
it (y[q] y[p]) = Mq] *[p]) then
begin
flag := 1;
base := 2;
cx := x[q] x[pj;
cy := y[q] y[pj;
turn := 2;
curline := j;
beginpoint := q;
{ find Y axis }
04/18/90 23:57
PRISM
Page 2
q := p;
rectangle;
if (flag = 1) and (count = 4) and (base = 6) then
fig := 3
else
fig := 2
end
else if j = ml then
begin
flag := 1;
fig := 3
end
else
j := j + 1
end { while1 }
end {1}
else
fig := 1
end;
5:
begin
if count = 4 then
fig :* 2
else
fig := 1
end;
6:
begin
if count = 4 then
fig := 3
else
fig := o
end;
7:
fig := 0;
8:
fig := 1;
0:
fig := 0;
end { case }
end;
procedure evaluateline (var fp, bx, by: integer);
v a r
result: integer;
begin {4}
bx := cx;
by := cy;
{ checking if there is a height line }
{ at the point on base (X,Y,Z) axis }
04/18/90 23:57
PRISM
Page 3
cx := cx;
cy := cy;
startpoint := p;
nextpo i n t;
result := 1;
case fig of
1:
begin
if cx = cy then
result := 1
else
result := 0
end;
2:
begin
if cy = 0 then
result ;= 1
else
result ;= 0
end;
3:
begin
if cx = 0 then
result := 1
else
result := 0
end
end; {case}
if result = 1 then
begin {5}
q := pn[1 ]; { checking if that line is truely }
if f[q] = 1 then { height line or not,check length }
begin
if (abs(cx) <= abs(hx)) and (abs(cy) <= abs(hy)) then
prism := 0
else
prism := 2
end
else if (abs(cx) = abs(hx)) and (abs(cy) = abs(hy)) then
begin {7}
nextpoint; { only the case of (cx,cy)=(hx,hy) }
if (cx / cy) = (bx / by) then { check bx,by }
begin {8}
q := pn[1 ];
if f[q] = 1 then { interrupted mark}
begin
if abs(cx) < abs(bx) then
prism := 0
else
prism := 2
end
else
begin
04/18/90 23:57
PRISM
Page 4
if (abs(cx) = abs(bx)) and (abs(cy) = abs(by)) then
prism := 0
else
prism := 2
end
end {8}
else
begin {9}
case fig of { in case of that the point }
1,2: { doesn't have line to (bx,by) }
prism := 2;
3:
begin
if bx >= 0 then
prism := 0
else
prism := 2
end
end { case }
end; {9}
if prism = 0 then
if fp = beginpoint then
prism := 1;
end {7}
else
prism := 2
end {5}
else
prism := 2
end; {4}
procedure prismjudge;
v a r
cex, cey, cfx, cfy: integer;
bx, by: integer;
fp, fx, fy, fcl: integer;
flag, result: integer;
begin
p := start;
j := 1:
flag := 0;
curline := 0; {new curline default}
while flag = 0 d o
begin { while1 }
oneline;
case fig of
1:
begin
beginpoint := start;
if (x[q] x[p]) = (y[q] y[p]) then
begin
{ find Y axis for base height }
04/18/90 23:57
PRISM
Page 5
flag := 1;
hx := x[p] x[q];
hy := y[p] y[q];
prism := 1;
end
else if j = ml + 1 then
prism := 2
else
j := j + 1
end;
2:
begin
beginpoint := start;
if y[q] = y[p] then { find X axis for base height }
begin
flag := 1;
hx := x[p] x[q];
hy := y[p] y[q];
prism := 1;
end
else if ] = ml + 1 then
prism := 2
else
j := j + 1
end;
3:
begin
if x[q] = x[p] then { find Z axis for base height }
begin
flag ;= 1;
hx := x[q] x[p];
hy := y[q] y[p];
prism := 1;
end
else if j = ml + 1 then
prism := 2
else
j := j + 1
end
end { case }
end; { while1 }
if prism <> 2 then
begin {1}
j := 1;
flag := 0;
while flag = 0 do
begin { while2 }
case fig of
1:
begin
oneline;
if y[p] = y[q] then {X axis}
04/18/90 23:57
PRISM
Page 6
flag := 1
else
j := j + 1
end;
2:
begin
oneline;
if Mq] x[p]) = (y[q] y[p]) then {Y axis}
flag := 1
else
j := j + 1
end;
3:
begin
turn := 1;
cx ;= x[p] x[q);
cy := y[p] y[q];
startpoint := q;
beginpoint := q;
curline := ln[1 ];
nextpoint;
flag := 1
end
end { case }
end; { while2 }
case fig of
1. 2;
begin
curline := j;
startpoint := q;
cx := x[p]  x[q];
cy := y[p]  y[q]
end;
3;
begin
curline ;= ln[1 ];
startpoint ;= p;
cx ;= cx;
cy := cy
end
end; { case }
case fig of
1:
begin
turn := 2
end;
2, 3:
begin
turn := 1
end
end; {case}
prism := 0;
04/18/90 23:57
PRISM
Page 7
poly := 1; {cut 0}
while prism = 0 do { start to evaluate }
begin { while3 }
poly := poly + 1;
cex := cx;
cey := cy;
nextpoint;
fp := startpoint;
fx := cx;
fy := cy;
fcl ;= curline;
cfx := cx;
cfy := cy;
vx[1] := cx;
vy[1] := cy;
case fig of
1:
begin
vx[2] := 1;
vy[2] := 1;
end;
2:
begin
vx[2] := 1;
vy[2] := 0;
end;
3:
begin
vx[2] := 0;
vy[2] ;= 1;
end
end; { case }
cx := cex;
cy := cey;
either;
case fig of
1:
begin
if (vx[1 ] / vy[1 ]) = 1 then
result := 0
else
result := 1
end;
2:
begin
if vy[1] = 0 then
result := 0
else
result := 1
end;
3:
begin
it vx[1] = 0 then
{
{
checking for that a height line is hiding }
{ behind visible surfaces or not }
}
{ result=1 ...exist }
{ result=0....no }
04/18/90 23:57
PRISM
Page 8
result := 0
else
result := 1
end
end; { case }
cx := cfx;
cy := cfy;
if result = 1 then
evaluateline(fp, bx, by);
if prism <> 2 then
begin
startpoint := fp;
cx := fx;
cy := fy;
curline := fcl
end
end { while3 }
end {1}
end;
procedure prismdefine;
v a r
vn, vm: integer;
a, b, c, d, m, add: integer;
cex, cey, spt: integer;
flag, result: integer;
jn, fcl: integer;
begin
sfn := poly + 2;
vnb[1] := poly + 1;
vnb[sfn] := poly + 1;
for m := 2 to sfn 1 do
begin
vnb[m] := 5
end;
vn := beginpoint;
case fig of
1, 2:
begin
tx[vn] := 0;
ty[vn] := 0;
tz[vn] := 0
end;
3:
begin
tx[vn] := 0;
ty[vnj := 0;
tz[vn] := hy
end
end;
spn[1, 1] := vn;
04/18/90 23:57
PRISM
Page 9
spn[2, 2] := vn;
J := 1;
flag := 0;
repeat {find point of the base}
curline := 0;
p := vn;
oneline;
if ((x[p] x[q]) = hx) and ((y[p] y[q]) = hy) then
begin
vm := q;
curline := j;
flag := 1
end
else
j := j + 1;
until flag = 1;
case fig of {define point of base}
1:
fig := 2;
2:
fig := 3;
3:
fig := 1
end;
sx := (hx);
sy ;= (hy);
twothree;
tx[vm] := tsx;
ty[vm] := tsy;
tz[vm] := tsz;
case fig of { return}
1:
fig := 3;
2:
fig := 1;
3:
fig := 2
end;
spnfsfn, poly + 1] := vm;
spn[2, 3] := vm;
jn := 1;
add := 1;
repeat
jn := jn + 1;
if jn = 2 then
begin
turn := 1;
startpoint := vn;
cx := hx;
cy := hy
end
else
turn := 2;
04/18/90 23:57
PRISM
Page 10
nextpoint;
sx := cx;
sy := cy;
twothree;
tx[startpoint] := tx[vn] + tsx;
ty[startpoint] := ty[vn] + tsy;
tz[startpoint] := tz[vn] + tsz;
vn := startpoint;
cex := cx;
cey := cy;
spt := startpoint;
fcl := curline;
turn := 1;
nextpoint;
case fig of
1:
begin
if cx = cy then {Yaxis}
if f[startpoint] = 1 then
result ;= 0 {no}
else
begin
result := 1 ;{yes}
a := startpoint
end
else
result := 0
end;
2:
begin
if cy = 0 then {Xaxis}
if f[startpoint] = 1 then
result := 0 {no}
else
begin
result := 1 ;{yes}
a := startpoint
end
else
result := 0
end;
3:
begin
if cx = 0 then {Yaxis}
if f[startpoint] = 1 then
result := 0 {no}
else
begin
result := 1 ;{yes}
a := startpoint
end
else
result := 0
{judge if ther is height line }
{ checking if [vm] point is }
{ hidden or not (no point number) }
04/18/90 23:57
PRISM
Page 11
end
end;
cx ;= cex;
cy ;= cey;
startpoinl := spt;
curline := fcl;
turn := 2;
if result = 0 then {new vertex create)
begin
a := mp + add;
add := add + 1
end;
sx := cx;
sy := cy;
twothree;
tx[a] := tx[vm] + tsx;
ty[a] := ty[vm] + tsy;
tz[a] := tz[vm] + tsz;
vm := a;
spn[1, jn] := vn;
spnfjn, 1] ;= vn;
spn[jn, 5] := vn;
spn[sfn, (poly + 1) jn + 1] := vm;
spn[jn, 4] := vm;
if jn <> vnb[sfn] then
begin
spn[jn + 1,2]:= vn;
spn[jn + 1, 3] := vm
end;
until jn = vnb[sfn];
procedure prism2 (var define; integer);
begin
beginpoint := start;
p := start;
rectangle;
define := 0;
if base <> 0 then
begin
prejudge;
if fig <> 0 then
begin
prismjudge;
if prism = 1 then {1:ok, 2:no)
begin
prismdefine;
define := 1
end
end
end;
04/18/90 23:57
PRISM
Page 12
end;
end. { UNITPRISM }
04/16/90 03:05
POLY
Page 1
unit POLY;
interface
uses
DRAW, INSPECTION, PRISM;
v a r
int: integer;
procedure contour;
procedure polydefine (act: integer);
procedure check;
procedure classify;
procedure segA (var k, str, stl, cxr, cyr, cxi, cyl, cur, cul, result: integer);
procedure complete;
procedure modify (stp, cex, cey: integer);
procedure incomplete;
procedure remain;
procedure hiddenl (var qq, jj; integer);
procedure hidden3 (tt: integer);
procedure hidden;
mplementation
var
els: array[1..5] of integer; { complete }
dst, dcx, dcy, dcu: integer; { input valiable for 'polydefine' }
procedure contour;
var
result, flag, mark: integer;
a, b, c, d, e, h, g: integer;
begin
j := 1;
curline ;= 0;
result := 0;
repeat
if j = mp + 1 then
begin
int := 0;
result := 1
end
else if f[j] = 1 then
begin
int := j;
result := 1
end
else
j := j + 1
until result = 1;
turn := 2;
04/16/90 03:05
POLY
Page 2
result := 0;
repeat
cx := 1; { dummy vector }
cy := 1; { to find first line }
curline := 0;
startpoint := start;
flag ;= 0;
while flag = 0 do
begin { while }
nextpoint;
line[curline, 3] := 1;
if int = 0 then
if startpoint = start then
begin
flag := 1;
result := 1
end
else { dummy }
else if f[startpoint] = 1 then
begin
turn ;= 1;
flag := 1
end
else
begin {1}
a := x[line[curline, 1]] div 10;
b := y[line[curline, 1]] div 10;
c := x[line[curline, 2]] div 10;
d ;= y[line[curline, 2]] div 10;
e := x[int] div 10;
h := y[int] div 10;
g := (b d) e + (a d b c) (a c) h;
if g = 0 then
if a = c then
if ((b < h) and (h < d)) or ((b > h) and (h > d)) then
mark := 1 {yes}
else
mark ;= 0 {no}
else if ((a < e) and (e < c)) or ((a > e) and (e > c)) then
mark := 1
else
mark ;= 0
else
mark := 0;
if mark = 1 then
begin
j := 1;
p := int;
curline := 0;
oneline;
curline := j;
cx := x[p] x[q];
cy := y[p] y[q];
04/16/90 03:05
POLY
Page 3
startpoint := q;
linefcurline, 3] := 1
end;
if startpoint = start then
begin
flag ;= 1;
result ;= 1
end
end {1}
end { while }
until result = 1
end;
procedure polydefine (act: integer);
v a r
result, m, a, b: integer;
icx, icy, ist, icu: integer;
begin
cx := dcx;
cy := dcy;
startpoint := dst;
curline := dcu;
if sfn = 1 then
begin
tx[startpoint]
ty[startpoint]
tz[startpoint]
end;
vnb[sfn] := count
set coordinates of origin point
0;
0;
0
1;
spn[sfn, 1]
turn := 2;
m := 1;
repeat
m ;= m + 1;
icx := cx;
icy := cy;
ist := startpoint;
icu := curline;
nextpoint;
if act = 1 then
begin
case fig of
1:
startpoint;
{ keep valiables }
{ for the case of}
{ act=1 (incomplete)}
{ in case of 'incomplete', a next line
{ sometimes can not be found correctly
following 'turn'. }
if (cy = 0) or (cx = 0) then
result := 0 (go on}
else
result := 1; {change}
if (cx / cy = 1) or (cx = 0) then
result := 0
else
}
04/16/90 03:05
POLY
Page 4
result := 1;
3:
if (cy = 0) or (cx / cy = 1) then
result := 0
else
result := 1
end;{ case }
if result = 1 then
begin
cx := icx;
cy := icy;
startpoint := ist;
curline := icu;
turn := 1;
nextpoint;
turn := 2;
act := 0
end
end;
if line[curline, 2] <> startpoint then
begin { exchange point numbers }
a := line[curline, 1];
b := line[curline, 2];
line[curline, 1] := b;
line[curline, 2] := a
end;
if m <> vnb[sfn] then
begin
If (line[curline, 3] <> 3) and (line[curline, 3] <> 2) then
begin { if 3 or 2, the line already has a 3D coordinates }
sx := cx;
sy := cy;
twothree;
a := line[curline, 1];
b := line[curline, 2];
tx[b] := tx[a] + tsx;
ty[bj := ty[a] + tsy;
tz[b] := tz[a] + tsz
end;
spn[sfn, m] := startpoint;
line[curline, 3] := line[curline, 3] + 2
end
until m = vnb[sfn];
line[curline, 3] := line[curline, 3] + 2;
spn[sfn, m] := spn[sfn, 1];
sfn := sfn + 1
end;
procedure check;
begin
if count = 3 then
04/16/90 03:05
POLY
Page 5
{ about 'fig=4,5,6':
{
begin
if (cls[1 ] = 1) and (cls[2] = 1) then
fig := 3
else if (cls[1 ] = 1) and (cls[3] = 1) then
fig := 1
else if (cls[2] = 1) and (cls[3] = 1) then
fig := 2
else
fig := 0
end
else if count = 4 then ,
begin
if ((cls[1] = 2) and (cls[3] >= 1)) or ((cls[1 ] >= 1) and (cls[3] = 2)) then
fig := 1
else if ((cls[2] = 2) and (cls[3] >= 1)) or ((cls[2] >= 1) and (cls[3] = 2)) then
fig := 2
else if ((cis[1 ] = 2) and (cls[2] >= 1)) or ((cls[1] >= 1) and (c!s[2] = 2)) then
fig := 3
else if (cls[4] = 2) and (cls[1 ] = 2) then
}
fig := 4
}
else if (cls[4] = 2) and (cls[2] = 2) then
}
fig := 5
}
else if (cls[4] = 2) and (cls[3] = 2) then
}
fig := 6
fig5=fig1 +fig2.}
else
fig := o
end
else
begin
if (cls[3] = 0) and (cls[4] <= 1) and (cls[5] = 0) then
fig := 3
else if (cls[2] = 0) and (cls[4] <= 1) and (cls[5] = 0) then
fig := 1
else if (cls[1 ] = 0) and (cls[4] <= 1) and (cls[5] = 0) then
fig := 2
else
fig := 0
end
end;
{
{
{
{
In the procedure 'twothree',there is no
translate valiable defined.
According to the value of (ox,oy),
those valiable could be defined easily,
or use two 'fig' value, such as
procedure classify;
begin
if cy = 0 then
cls[1] := cls[1] + 1
else if cx / cy = 1 then
04/1 6/90 03:05
POLY
Page 6
cls[2] := cls[2] + 1
else if cx = 0 then
cls[3] := cls[3] + 1
else if cls[4] = 0 then
begin
ox := cx;
oy := cy;
cls[4] := 1
end
else if (ox = cx) and (oy = cy) then
cls[4] := cls[4] + 1
else
cls[5] := cls[5] + 1
end;
procedure segA (var k, str, stl, cxr, cyr, cxI, cyl, cur, cul, result: integer);
v a r
act, rl, stb, mark: integer;
begin
count := 1;
repeat
rl := count mod 2;
case rl of
1: { R  clockwise }
begin
startpoint := str;
cx ;= cxr;
cy := cyr;
curline := cur;
turn := 2;
nextpoint;
count := count + 1;
str := startpoint;
cxr := cx;
cyr := cy;
cur := curline
end;
0: { L  counterclockwise }
begin
startpoint := stl;
cx := cxI;
cy := cyl;
curline := cul;
turn := 1;
nextpoint;
count := count + 1;
stl := startpoint;
cxI := cx;
cyl := cy;
cul := curline
end
end; { case }
04/16/90 03:05
POLY
Page 7
if f[startpoint] <> 1 then
begin {1}
classify;
if count <> 2 then
if startpoint = stb then
begin {2}
check;
if fig <> 0 then
begin
act := 0; { distingish from 'incomplete' }
polydefine(act);
mark ;= 1;
result := 1;
end
else
begin
k := k + 1;
mark := 1
end
end {2}
else
begin
stb := startpoint;
mark := 0
end
else
begin
stb ;= startpoint;
mark := 0
end
end {1}
else
begin
k ;= k + 1;
mark := 1
end
until mark = 1;
end;
procedure complete;
v a r
flag, result, k, c, a, b: integer;
str, stl, cxr, cyr, cxI, cyl, cur, cul: integer;
begin
flag := 0;
c := 1;
while flag = 0 do
begin { while1 }
k := 1;
result := 0;
while result = 0 do
04/1 6/90 03:05 POLY Page 8
begin {while2 }
cls[1] := 0;
cls[2] := 0;
cls[3] := 0;
cls[4] := 0;
cls[5] := 0;
if k = ml + 1 then
begin
flag := 1;
result := 1
end
else if sfn = 1 then
begin {1}
j := 1;
p := start;
curline := 0; { default }
if c = 1 then
begin
repeat
oneline;
if x[q] < x[p] then
begin
str := q; {clockwise ........ R }
stl := p; {counterclockwise L }
cxr ;= x[p] x[q];
cyr ;= y[p] y[q];
cxI ;= cxr;
cyl := cyr;
cur := j;
cul := j;
beginpoint := p;
c := c + 1;
result := 1
end
else
begin
j := j + 1;
result := 0
end
until result = 1
end
else
begin
repeat
oneline;
if x[q] < x[p] then
begin
str ;= p;
stl := q;
cxr ;= x[q] x[p];
cyr := y[q] y[p];
cxI := cxr;
cyl := cyr;
{clockwise ....... R }
{counterclockwise L }
04/16/90 03:05
POLY
Page 9
cur := j;
cul := j;
beginpoint := q;
result := 1
end
else
begin
j := j + 1;
result := 0
end
until result = 1
end;
dst := str; { d?? are }
dcx := cxr; { valiables }
dcy := cyr; { for polydefine }
dcu := cur; { }
cx := cxr; { for only 'classify' }
cy := cyr;
classify;
segA(k, str, stl, cxr, cyr, cxI, cyl, cur, cul, result)
end {1}
else if line[k, 3] = 2 then
begin {2}
str := line[k, 1]; (clockwise ......... R }
stl := line[k, 2]; (counterclockwise L }
cxr := x[stl]  x[str];
cyr := y[stl]  y[str];
cxI := cxr;
cyl := cyr;
cur := k;
cul := k;
beginpoint := stl;
dst := str;
dcx := cxr;
dcy := cyr;
dcu := cur;
cx := cxr;
{ d?? are }
{ valiables }
{ for }
{ polydefine }
{ for only 'classify' }
cy := cyr;
classify;
segA(k, str, stl, cxr, cyr, cxi, cyl, cur, cul, result)
end {2}
else
k := k + 1
end { while2 }
end { while1 }
end;
procedure modify (stp, cex, cey: integer);
begin
case fig of
1:
