The scanbeam method is used several times in the boolean algorithm
to calculate certain things. The idea is to scan the drawing with a vertical
scanbeam. A scanbeam is defined as being the space between two sequential
vertical scanlines. A scanline is generated for every node in the graph.
First all the begin nodes of the links in the graph are sorted on minimum
X coordinate (also on Y if X is equal). The beginnode of one link is always
the endnode of another link, simply because all polygons are closed loops.
So when generating a scanline for each beginnode of all links, we are sure
to visit all the nodes.
When two sequential beginnodes have the same X coordinate,
the resulting beam will be a flatbeam, the two scanlines are the same,
else we will get a normal beam. The graph in scanbeams
in a graph.. therefore results in 5 scanbeams. It contains one flatbeam
(scanlines shown with a slope, but is in reality also vertical)
A scanbeam is maintained as a C++ class that is
a list of
Record's.
Scanbeam is an inhereted class of a double linked list of void pointers,
the static iterator only knows that the void pointers are really
Record
objects.
Each scanbeam is crossed by several links, those links are part of
the scanbeam as follows. Each
Record
has a pointer to a
Line, each such
Line maintains a pointer to a
Link
in the graph. A scanbeam is always between two sequential nodes. The first
is called the
_low of
the current scanbeam, the second is the
_low for the next scanbeam. From now on
i will refer to those nodes as the _low
and _high,
the _high
node is not maintained as part of the scanbeam, but in the Graph
object it is set and used to set the type of scanbeam
(FLAT
or NORMAL)
that needs to handled next.
Because the graph is sorted, there can never be other nodes within
a scanbeam. For a flatbeam the
_low and
_high node have the same X coordinate,
the
_low Y coordinate will always be
higher then the
_high Y coordinate.
For normal beams this is not the case. While scanning the graph only one
beam will be in memory, this scanbeam is
updated to form the next
scanbeam. Updating the links in a new scanbeam is easy:
-
New links for the coming scan beam will always start or end at the _high
node of the previous beam.
-
Old links that are not part of the new beam will also always start or end
at the _high node of the previous beam.
Notice that the
_high node of the previous
beam
always will be the
_low
node of the next beam. As part of the
Record
object the intersection point of the links with the first scanline will
be maintained. When moving to a new beam the intersection point for the
new first scanline (old second scanline) will be updated.
Data members of object Scanbeam
|
Name
|
Type
|
decsription
|
|
_low
|
Node*
|
A pointer to the node that forms the first scanline in
the beam.
|
|
_type
|
BEAM_TYPE
|
Type of beam (NORMAL, FLAT)
|
| _prevbeam |
BEAM_TYPE |
Type of the previous beam (NORMAL, FLAT) |
|
static _BI
|
TDLI<record>
|
Iterator for Scanbeam itself
|
Scanning a graph with scanbeams
Scanning the drawing (Graph) using a scanbeam object,
is a standard loop the folowing is a copy from the code (
Scanning with a scanbeam. ).
Extra comment has been added, in order to understand
this code without further knowledge.
//the scantype parameter
is used in the scanbeam class to perform specific tasks
//for the boolean operations
int Graph::ScanGraph2(SCANTYPE
scantype)
{
//create an iterator
to traverse the linklist of the graph
TDLI<Link> _LI=TDLI<Link>(_linklist);
int found=0;
//sort links on x and
y value of the beginnode of each link
_LI.mergesort(linkXYsorter);
//bin flag is used in
scanbeam so reset
_LI.foreach_mf(&Link::SetNotBeenHere);
//make a scanbeam instance
ScanBeam* scanbeam = new ScanBeam();
Node* _lowf; //the
current _low node
Link* _highlink; //the
link in the graph that has as beginnode the _high (_low for next scanbeam)
Link* _lowlink; //the
link in the graph that has as beginnode the _lowf (_high of previous beam)
_LI.tohead(); //start
with first link in the beam
_lowf = 0;
//make it zero in order to skip the first if in
the while loop
while (!_LI.hitroot())
{
//same
node pointer as the previous node, we don't have to check this node again
if (_lowf == _LI.item()->GetBeginNode())
_LI++;
else
{ int i;
_lowlink=_LI.item();
_lowf=_lowlink->GetBeginNode();
//find
a new high node, this should be a node not eqaul to _lowf
i=0;
do
{ _LI++;i++;}
while (!_LI.hitroot() && (_lowf == _LI.item()->GetBeginNode()));
//even
the last _lowf node must be processed, no new links will be found
//only old links will be removed
if (_LI.hitroot())
{
_LI--;
_highlink=_LI.item();
_LI++;
}
else
_highlink=_LI.item();
//put
_LI back at the _lowf
_LI << i;
//set the beam _low node and the type of the beam
(FLAT or NORMAL)
scanbeam->Set(_lowlink->GetBeginNode(),_highlink->GetBeginNode());
//find
new links for the new beam and remove the old links
//depending on the scantype parameter also other things will take place
if (scanbeam->Update(scantype,&_LI))
found++;
_LI++;
//next link in the graph, sorted on beginnode
so in fact the next _lowf
}
}
delete scanbeam;
return found;
}
First the begin nodes of links in the graph are sorted on X and Y coordinate.
Each unique beginnode will result in a scanline, so when some links share
the same beginnode it will be skipped. This is the case at a crossing of
several links. We set the low and high node for the beam and based
on this if the scanbeam is of type FLAT or NORMAL. Now we can remove records
that should not be part of the new beam (containing links to the
_lowf node), and find new records for links to the _lowf node.
Finding a new scanbeam .
Scanbeams are defined by there _low and _high node. Sorting
the links on the X,Y coordinate of the beginnode, leads to scanlines through
each beginnode. Because the drawing contains only polygons, each beginnode
is the endnode of another link. So taking only beginnodes results in passing
each node only once. After intersection of the graphs some links can share
the same beginnode. A beginnode has only to be checked once for links in
the new scanbeam. Because the graph is sorted on beginnodes, we can easely
skip the next beginnode if it is equal to the previous.
The rest of the nodes, form flat beams and normal beams.
Only the normal beams need to be processed. For the flat beams only new
links will be inserted into the beam, and old links will be removed. To
achive this, we search the high of the first coming normal beam.The low
is now increased until it reaches the high node, in the mean time the new
and old links in the beam are updated (
skipping
flatbeams. ).
skipping flatbeams
Remove old and FindNew Links for beam.
New links for the coming beam are only to be found at
the high node of the previous beam (low node of the new beam). Links to
be removed are the links connected to the high node of the previous beam.
Each Node has a list of links that are connected to the node. All links
that have the bin flag set, where already used in a previous beams, the
others all need to be put in the current beam as new records. Also the
bin flag will be set at this moment for those links. Before inserting the
new links in the beam, we better remove old links connected to the low
node of the current beam, because they are the only ones connected to the
new low node. In some cases the links to be removed are only marked for
removal (_active flag of record object). So they can easily be removed
later.
removing and inserting links in beam at low node.
Record Object
The scanbeam is a list of Records, each record contains
a pointer to a link in the graph. When the beam is up to date, all the
records contain pointers to links that cross the the current scanbeam.
Next to this, each record contains the Y value of the link its crossing
with the first and the second scanline of the beam. Those crossings (Ysp,Ysn)
are used in several ways, for instance to sort the records in a beam.
The Link has a direction flag (_dir) in the beam record.
For a link in a normal beam, if the direction from begin to endnode is
from left to right, the _dir flag is set to GO_RIGHT else to GO_LEFT. For
a flat beam, a vertical link is said to GO_RIGHT if it points downwards
else GO_LEFT. The _dir flag is used for calculating Left Right Group values
for each link in the graph.
Datamembers of object Record
|
Naam
|
Type
|
Omschrijving
|
|
_line
|
Line
|
Line object for calculating the intersection of two links
in the beam.
|
|
_ysp
|
PointType
|
Y-value of the intersection point of the link with the
first scanline (low node).
|
|
_dir
|
DIRECTION
|
Direction of the link (GO_RIGHT or GO_LEFT ).
|
|
_inc
|
G_BOOL
|
Used for calculating the left right values for links
in the graph.
|
The most important functions or the record object will
be discussed:
The constructor.
Record(Link *link)
Calculating Left and Right values for a Record/Link:
Calc_Set_Left_Right,
Calc_Left_Right.
Calculating _ysn value:
Calc_Ysn.
Setting direction:
Set_Flags.
Constructor
Record::Record(Link* link)
The Record will be constructed for a given link. The
Ysn and Ysp will be set later on, depending on the beam it's low and high
nodes. The same Record can be part of several sequential beams, the Ysp,Ysn
will be updated when moving to the following beam. If the link of the record
is not part of the beam anymore, the record will be destroyed.
The constructor also creates a line object for the given
link, it is used to calculate Ysn,Ysp and intersections with other links.
Calc_Set_Left_Right
void Record::Calc_Left_Right(int& a,int &b)
This function calculates the Group Left and right values
of the link, based on the Group Left Right values of the previous record/link
in the beam. The principle behind this will be discussed in
See
Basic Steps for Boolean Operations. .
Calc_Left_Right
Used only when group Left and Right flags where already
calculated before. This is for speed.
Calc_Ysn
void Record::calc_Ysn(BEAM_TYPE thisbeam,Node* high)
This function calculates the intersection point of the
link with the second scanline (at high node). Calculation is optimized.
For instance if the link begins or ends at the high node, it is clear the
intersection is the Y coordinate ot the high node. For Flat beams the intersection
point is equal to the intersection point of the first scanline, which is
already known. Except for vertical links in a Flatbeam. (
See calculating Ysn value.. )
Set_Flags
void Record::Set_Flags(BEAM_TYPE type)
This function calculates the direction flag (_dir) for
the link in the record, based on the Beamtype (FLAT or NORMAL). How this
is done for Flatbeams (containing vertical links) is shown in
Direction
of links in a flatbeam. .
