Procedure for filling a closed contour
ZXNet echo conference «code.zx»
Thank you.
I'll try to figure it out.
aci> If we initially assume that everything will be made of triangles, then
aci> trivial =)
Some kind of cunning algorithm was invented that would not slow down on specrum,
for example, breaking up the intricate labyrinth of a 463-gon? Even the fastest
The ear-cutting algorithm on the Spectrum is incredibly slow.
This is off topic at all. Pixel fill is being discussed :)
Dex> What about dividing into triangles? Instantly or what?
If you initially assume that everything will be made of triangles, then it’s trivial =)
--
--
//acidrai
As far as I remember, the fastest fill was in Artist II.
The procedure for filling an area on the screen was in the Impulse 1 newspaper, I even did it a couple of times
I used it, it doesn’t work too fast, but at least faster than in ArtStudio.
Press RESET immediately, Dratov Denis!
On Wed, 28 Sep 05 00:15:54 +0400, Dratov Denis wrote:
DD> Some kind of cunning algorithm was invented that would not slow down on specroom
DD> for example, breaking up the intricate labyrinth of a 463-gon? Even the most
DD> the fast ear-cutting algorithm on the Spectrum is incredibly slow. This is not according to
DD> topic in general. Pixel fill is being discussed :)
What difference does it make what you fill? Essentially one algorithm, resourceful,
expressed in different forms. It is clear that there are different options
may be faster in different cases. But for practical use,
graphics output, pixel fill is only needed in an art studio...
Kir> pixel fill is only needed in an art studio...
That's right, it would be better not to sweat the small stuff, but to do something useful for the spec.
Calculate how much time we spent here discussing such a simple question,
that Mona had to rivet the basis for the game. =) don't worry... buy a chip and think
how to push it into the spec - it will quickly flood your area ;)
--
--
//acidrai
Hello, All
Kir> Who cares what you fill in? Essentially one algorithm, resourceful,
Kir> expressed in different forms is obtained. It is clear that there are different options
Kir> can be faster in different cases. But for practical use,
Kir> graphics output, pixel fill is only needed in an art studio...
This is where you are wrong. What if the graphics are like Micronaut One? How,
Do you think they at least depict the Jelly Fly dome?
--
Can you help Robin in his quest for the Silver Arrow?
WBR, TomCaT aka Kostya
Hello Jerry
jer> Remember Gyron
What, is this taboo - Gyron? Or is it still a game with an original and fast
graphics.
--
Can you help Robin in his quest for the Silver Arrow?
WBR, TomCaT aka Kostya
Hello TomCaT
Tom> what, is this taboo - Gyron? Or is it still a game with an original and fast
Tom> graphics.
3D is very conceptual
--
When will I die?! :mad:
File: GyronAtrium.zip http://zx.pk.ru/attachment.php?attachmentid=1802
WBR, jerry aka Yuri Potapov
Hello TomCaT
Do you remember Gyron?
do not confuse filling a closed contour with drawing filled primitives
--
When will I die?! :mad:
WBR, jerry aka Yuri Potapov
Hello Jerry
jer> 3D is very conceptual
jer> (the message contained attachments: GyronAtrium.zip (53.1 KB, 1 views))
Sorry, my joke was bad. Of course, I know and have seen this game. I just
It seemed like you thought Gyron was a bad example. :) I hope not again
will happen again.
jer> do not confuse filling a closed contour with drawing filled ones
jer> primitives
I don't mean to confuse. I'm giving an example. Good filling procedure in the game m/b
will come in handy. Even if it's a text adventure - most of the time it's like
I went to fill it once. And also on arcs and circles, but this is in bad quests and with
using ROM (Urban Upstart)
--
Can you help Robin in his quest for the Silver Arrow?
WBR, TomCaT aka Kostya
Hello TomCaT
By the way, a crazy idea was born to optimize the filling procedure. If everything
If it works, it will not be filled in with dots, but with bytes, but without errors,
exactly a closed loop. Due to non-recalculation of coordinates and practically
eight times the tempo should be fun!
And then it would be necessary to integrate it into Asterix & Obelix, otherwise the game is beautiful (albeit
a simple plot), but the filling there is incredibly impressive!
Hello TomCaT
Is the filling necessary with a pattern or not?
If it's the first, it's more difficult. Usually the filling is done without a pattern, and then
the calculated mask is filled with the pattern. Then the memory will be consumed in addition to
The recursive algorithm also needs to store the mask.
In general, yes, bytes are possible. Just a long time ago I was making an algorithm,
which filled with bytes, respectively. the x offset is an increment/decrement, and the y offset
It’s clear that it’s more complicated, but not by much.
Alas, there are no sources left, but I have some memories... maybe I’ll try
restore.
Hello, maximk
Yes, we’ll have to figure out the pattern somehow later... For now, I’d like to speed up Solid Fill.
I've already written half of it, everything should work (as always, it SHOULD, but... :). But
if there are no sources, maybe there are some ideas for optimization?.. Unfortunately, I
so far I have planned it well, even the stack is only for saving branches,
no extra memory operations, but it eats up alternative ones. No chance
such commands: EX DE,IX / EX DE,IY? An internet search says it doesn't seem to be the case :(
:/.
In particular, you need to quickly move from the video buffer address to the adjacent line
up and down. You can use a battery and one pair, DE for example.
So far I have only guessed that if unpleasant transitions and address conversions
they are waiting at the top, then they are definitely not there at the bottom, and vice versa... You can also make a sign
of 192 addresses of the left edge of the lines, and one 8-bit reg is used to store
line numbers, changing in parallel with the address and recalculating after removal
addresses from the stack.
__________________________________________
Here are also similar working options: since A, HL are always busy for operations with
the next byte and BC, for storing and counting the current bit, A' - different
flags, then IY could store the old stack (with IY on top -- used
only at the beginning and end of work), and IX and DE are two addresses of adjacent lines. ButThere are already problems with storing the mask. So, if there is no last exchange command,
It’s worth giving up one address (it’s already easy to get INC/DEC HL) by entering
with one flag a sign of the “side” of the line that is now in DE. And also store in E
mask, and in D - the most significant bits 4-0, the lowest 7-5 addresses of the adjacent line, according to
which from HL is also short (AND, OR, pair AND A, SCF, 6 shifts A and 3 --
different register) get the address of the second neighboring line. The old stack was then in IX.
In total, 4 pairs and both batteries are occupied.
Hello, maximk
max> Is it necessary to fill with a pattern or not?
max> If the first one is more difficult. Usually the filling without a pattern is done first.
max> and then filled with a pattern based on the calculated mask. Then the memory will be
max>, in addition to the recursive needs of the algorithm, also costs mask storage.
Why is it so difficult? This is simple texturing, that is, translation of X,Y coordinates
in U,V. Those. fill it with a non-wave algorithm (like the most common one?),
but simply translate the coordinates and read the color of the point from a piece of memory with a texture.
The problem is only in multiplication.
Hello, maximk
max> Well, we have set the next point, and moving on to the next one from
max> is it known - is this an unfilled point or a black point of the pattern?
max>
max> Ah, I understand, I understand. Well, coordinate translation is not a task for the z80, IMHO...
And for whom in this case?
max> Yes, the fill with a mask was in some spec editor, but I didn’t
max> I remember which one, I almost never used it. So, I just looked around.
Ay-ay-ay :) we forget the classics. ArtStudio has it. And by the way it’s called quite
Windows term - brush.
Hello icebear
ice> but simply translate the coordinates and read from a piece of memory with a texture
ice> dot color. The problem is only in multiplication.
Well, we have put another point, and moving on to the next one, from what we know - this
unfilled dot or black dot of the pattern?
Oh, I get it, I get it. Well, coordinate translation is not a task for the z80, IMHO...
Yes, the fill with a mask was in some spec editor, but I don’t remember in
which one, I almost never used it. Yes, I just looked around.
Hello, maximk
max> Damn :) I meant that I don’t yet see any reason to believe that
max> filling with coordinate transformation will be faster than solid fill, yes
max> also in bytes.
Here, as they say, “a double-edged sword” :) Either do it clumsily but quickly,
or beautiful but slow. With textures there are more possibilities for “coloring”.
Just don’t ask me how to do this on the Spectrum, I’ve been at it for 12 years
Z80 assembler did nothing.
max> So, I’m guilty :), but I’m not an artist and I’m not even good at it. Therefore
max> the program impressed me with its capabilities, but I didn’t really use it.
Well, drawing your own font in ArtStudio is the responsibility of every spektrumist. :)
Hello icebear
ice> And for whom in this case?
ice>
Damn :) I meant that I see no reason yet to believe that the fill is with
transforming coordinates will be faster than solid fill, and even in bytes. Those.
if you implement it on the z80 then (most likely) the result will be
unsatisfactory in speed. But, as I understand it, maybe some
mega-coder will show a master class and make me doubt again :)
ice> ArtStudio has
So, I’m guilty :), but I’m not an artist and I’m not even close to it. Therefore the program
I was impressed by the possibilities, but I didn’t really use it.
Hello, maximk
max> But, on the spec due to modest (by modern standards) computing
max> possibilities, the issue of this very optimization is acute. On the other
max> side, there is a certain satisfaction when you have coded something that
max> even 3.5 MHz spins impressively, although inside the devil will break his head :)
But if you do quick texturing (even with restrictions) - it would be
revolution on the Spectrum.
Hello icebear
ice> Here, as they say, “a double-edged sword” Either do it clumsily
ice> fast, or beautiful but slow.
I support. That's right! It’s not for nothing that Uncle Knut said:
> Premature optimization is the root of all evil
>
and
> If you optimize everything, you will always be unhappy.
>
But, on the spec, due to modest (by modern standards) computing
possibilities, the issue of this very optimization is acute. On the other hand, there is
a certain satisfaction when you have coded something that spins spectacularly even without
3.5 MHz, although inside the devil will break his head :)
Hello, Dexus
I recommend watching this http://zxaaa.untergrund.net/DEMO/35mhz.zip - part
from IRIS Ultrademo by Flash Inc.
Hello, drbars
yes, this is a real masterpiece of code. it would be great to get the sources, or even better
article on this topic.
Hello, drbars
In IRIS (and in other things) this is done quite simply - polygonal
polygons. This is not pouring through the seed (by spreading),
This is drawing a polygon along lines, from top to bottom, between the left and right sides.
The texture pattern does not shift bit by bit. He "stands" on the screen. Thanks to this
When filling a polygon, the bytes of the texture pattern are simply transferred.
The only thing is that the pattern bytes are bitten off on the edges using the and-mask.
There is no need to move the texture when filling, otherwise the ribs will turn out ugly.
The algorithm is very simple.
In order for it to work, two conditions must be met - drawable
the polygon must be convex.
(By the way, any convex geometric bodies give a convex projection of the face, i.e.
during projection, the polygon on the screen will be obviously convex - this is a theorem
geometry)
And the second condition is that the vertices must be traversed in order, or everything must be done clockwise
arrow, or all counterclockwise.
There are two side buffers. For the left side of the polygon, and for the right side
polygon. They contain X-coordinates. The length of the buffers must be no less than the height
screen.
The highest vertex (min Y) is searched.
The lowest vertex (max Y) is searched.
Starting from the highest vertex found, in order, each edge is sent
into the procedure ScanConvert(x1, x2, y1, y2).Total - for a triangle there will be three edges and will be called three times
ScanConvert. For a quadrilateral - four, and so on...
Then everything is simple - ScanConvert determines whether this edge is left or right (right
buffer to fill or left) and stepping from top to bottom along the selected buffer
(it turns out that it’s as if by “sweeping” the edge onto the Y axis) step by step enters into the buffer
X-coordinates of the edge. To do this, I found the delta for each step by division. you
you can create a faster algorithm. How to determine whether it is right or left
the edge is easy to guess, because two conditions are given above. Degenerate edges (purely
horizontal) are not included.
And then, when the buffers are full from the highest found Y-vertex to
draw lines at the lowest Y-vertex. Each line is from the X-coordinate of the left buffer
to the X-coordinate of the right.
p.s.
Iris varieties have been available for purchase for many years now.
http://opensourcezx.narod.ru
you can Wh. take advantage of them.
You need to look at the functions POLY3 or POLY4.
File: 35mhz.zip http://zx.pk.ru/attachment.php?attachmentid=3683
Hello Raider
thank you.
Hello elf
I returned from a non-sabbatical vacation, but still completed this procedure. In the end
It didn't work out too quickly. :( :mad; ,; but a kilobyte of buffer (otherwise,
it seems, and less) is enough for all tasks. So the right place for her, apparently, is in
Count editors. With Asterix&Obelix, however, you also need to think about it...
File: ffill.zip http://zx.pk.ru/attachment.php?attachmentid=3703
Hello TomCaT
I wonder how this is implemented? I wish I could figure it out..
example from WOS ftp
File: Fill_2.tap.zip http://zx.pk.ru/attachment.php?attachmentid=3886
Hello jim
called seeded filling.
in the attachments there are examples in C from the book by Shikin and Boreskov
File: FILL1.txt http://zx.pk.ru/attachment.php?attachmentid=3890
File: FILL2.txt http://zx.pk.ru/attachment.php?attachmentid=3891
File: FILL3.txt http://zx.pk.ru/attachment.php?attachmentid=3892
Hello Raider
Check out the game Hard Driving, I think it's very cool for specs. '89. 48k.
And how does it all work at 3.5 MHz....