Closed nkh closed 9 months ago
don't use 0/1 as a format
@nkh In fact, there are only two functions that actually implement the function.
_get_ascii_array_andcrossings _transform_elements_to_charactersarray
Although they do similar things, they are very different internally. I really can't think of a good way to extract the common code of these two functions. I'm worried that this will over-design and destroy the independence of the two functions.
export_to_clipboard_as_ascii -> transform_elements_to_ascii_buffer -> transform_elements_to_ascii_array -> transform_elements_to_array
export_to_clipboard_as_markup -> transform_elements_to_markup_buffer -> transform_elements_to_markup -> transform_elements_to_array
transform_elements_to_ascii_buffer: There are many places where this function is called, Function cannot be deleted.
transform_elements_to_ascii_array: This function is also called in /setup/import_export/perl.pl, so it cannot be removed.
transform_elements_to_array: Convert a character array into a string array, The name of this function can be renamed.
I haven't thought of a good way to optimize these functions. Do you have any specific suggestions?
I've taken an hour to analyse the different usages and try to wrap my head around why there are so many variations.
We didn't have a good way to work together but I believe that we are getting there, my biggest concern, and it reflects in this problem, is that you try to modify the application so there are no changes in the base of it, be it cross mode or markdown, that's a good thing but as we continue modifying Asciio these small changes are everywhere and we spend weeks refactoring. I think that we have now a better system, when we want to add something we discuss it first and have long discussions about how to do it and thus it makes maintenance easier.
The root of the problems in this issue is markdown, you've made a great effort to separate the code but it should never have been together to start with and I believe I know where the problem started.
I have moved this issue to 2.0 as I think it's not a 2 hours change but something that will take longer time.
The stripe elements sometimes needed to be converted to an array of characters to create as a Z-buffer.
This was seldom needed as Asciio spends most of its time drawing stripes and with the port to GTK3 we buffer everything.
The markdown codes are embedded in the stripes which makes it necessary to manipulate and extract them every time we need to render the elements. Fortunately the GTK caching skips that or we'd have a very slow application.
Markup also uses a global variable that must go away.
As exporting to text, the cross mode needs to have a Z-buffer to compute which overlay to use, it also requires the stripes to go through the Markdown filter.
We reach an acceptable speed because of the GTK3 cache but there are still a lot of computation that's not cached.
Let elements cache their 2D map. This means no more cycling over stripes but instead get the 2D map and work on it.
Just use the element's 2D map
This mode is cached but time is spends creating Z-buffers, we could use the element's 2D maps for the computation instead for the stripes.
There are more optimization possible but this will have an impact and will reduce the knowledge the crossing code needs to ave about the elements, it just takes 2D maps and calculate possible crossings overlays.
The 2D map, of plain UTF characters, can be used as a cache in the TUI and maybe in the WEB interface.
No more loops over stripes means less code in the functions we want to refactor.
The functions will also have a clearer goal since the stripes to 2D map code is removed.
Further looking at the code, prior to markup/cross and after markup cross, it seems to me that the problem is because Asciio doesn't keep a character array nor does it have a Z buffer. Let's fastforward in the future and imagine that Asciio has an efficient implementations of:
sub get_cross_mode_overlays
call sub get_ascii_array_and_crossings
computes the overlays
sub get_overlays
{
# Asciio maintains $Z_buffer
my ($asciio, $Z_buffer, $fillers, $start_x, $end_x, $start_y, $end_y) = @_ ;
# Cross needs a filtered Z buffer
my $cross_Z_buffer = filter_z_buffer { any { $_ eq ref($element) } @{$asciio->{CROSS_MODE_IGNORE}} }, $Z_buffer ;
# compute overlay for character and neighbors
map { get_overlay($_->{0}, $_->{1}, $cross_Z_buffer->neighbors($_->{coordinates}) }
# filter out cases that cross doesn't handle
grep { $fillers->{$_->{0}} && $fillers->{$_->{1}} }
# get all the points where elements intersect
$cross_Z_buffer->get_stack(2)
}
sub get_overlay
{
my ($char0, $char1, $neighbors) = @_ ;
# this code doesn't know a thing about Asciio, Z buffer, ... just two characters intersecting and their neighbors
# this makes it very easy to write the tests, specially if the intersections are generated not written by hand
# compute overlay character
...
}
The code we have now is efficient but difficult to optimize, we have different functions doing a lot of the same thing and that even more difficult to optimize.
Even if the Z buffer is less efficient, it opens new optimization opportunities, they can also be shared.
@nkh I roughly read your comment and I roughly understand what you mean, but I still need time to understand the details. Let’s put this issue aside for now.
@qindapao Hi, I've just created a zbuffer branch.
https://github.com/nkh/P5-App-Asciio/tree/zbuffer
I have more plans to optimize it but it fast as it is now and it can, with minimal work, be used to replace the 2D map code we have in the Cross module.
After creating the ZBuffer object, you can get a list of intersection directly from it, you can also ask for neighboring cells; see cross_overlay in the module which will display the cells where there are intersections, the two characters crossing as well as the neighbors that are set.
I haven't tested with unicode yet but the difference should be trivial to fix if needed.
The idea is to completely isolate Cross.pm from Asciio and instead accept data from a ZBuffer object. The object will be passed to Cross.pm when rendering. Today the 2D map is created at each redraw, the idea is to have a ZBuffer object that is updated only for the changes made between two redraw.
Please let me know when you have integrated it so I can start with the element update functionality.
@nkh I will take the time to look at the code and then understand it.
This is the part of ZBuffer you need to understand.
If you run Asciio in the Zbuffer branch you'll see this in the terminal:
You get the intersection, the characters, and the neighbors, here a connector on a box.
Another examples with two boxes crossing
@nkh It's interesting. I'll try it on weekends. I've always wanted to ask a question. Why is it called z-buffer?
In fact, at the beginning, my idea was that it would be best if the data structure could be dynamically updated instead of being rebuilt every time. It's just that I didn't know how to do then.
@nkh I won't have time until the weekend. I'll let you know when I'm finished.Whether I follow the existing architecture or redraw the whole 2D map every time. Then when I'm finished, you can optimize it into elements and dynamically update the 2D map?
Z buffer because it has a third dimension.
Say you have a character at [x,y], then you draw another character also at [x,y], the one at the top is [x,y,0] where 0 is the depth, the other one is at [x,y,1] because it's one level deeper.
Asciio has some type of Zbuffer as everything is drawn on top of each other but we don't keep the data so everything gets flattened.
The current ZBuffer module doesn't really work as a z-buffer except at intersections, future versions will have all the elements at different depths.
ZBuffers take more memory but it can't be worse than the GTK cache.
Dynamically updating the z-buffer is challenging but may be fun, I'm not sure it will be faster than regenerating the whole z-buffer as the code to run is more complex.
Creating the current z-buffer from scratch and computing the intersections takes around 0.0001 second per box element (15 characters).
@qindapao the ZBuffer functionality has been merged to the main branch.
functionality is not complete but this is what we base 2D maps crossing, and a few other things from this point.
@nkh I'm looking at this part of the code, I understand it, I'm coding it. There are some details that need to be worked out, but they may not be completed today, but they should be fine next week.
@qindapao take your time :) Let me know if I can help.
The current implementation of ZBuffer is not complete but it's complete enough to use instead for the 2D map creation that's in the cross module.
I'm thinking about using it to implement the drawing of objects in tasciio. I tested it to 20 000 000 character insertions per second so we should be good with large graphs too. and that would be even faster when I implement buffer caching and update (but that may take a while).
the most interesting part in using a ZBuffer that is computed by Asciio (and not cross) is to be able to compute crossings for groups of objects instead for all of the objects.
@nkh
Hello, I have no objection to the overall framework, but I just want to confirm some small details with you.
(1). Can I specify a range when generating zbuffer. Because whether it is cross-mode or other rendering, we are just for presentation, so we only give the part that the user can see.
When rendering, only the part that can be seen by the eyes can save the time of zbuffer generation.Also saves processing time for external code.
(2). You use spaces to filter the cross points. But these cross points are not really cross points. I need to filter it a second time after I get them.(For example, if a letter a
is covered with a letter b
, no matter what is around them, I don't think there is an cross point here.)
if($char eq ' ')
{
delete $self->{intersecting_elements}{$coordinate}
}
elsif( ($self->{coordinates}{$coordinate} // ' ') ne ' ')
{
$self->{intersecting_elements}{$coordinate} = [ $char, $self->{coordinates}{$coordinate} ] ;
}
$self->{coordinates}{$coordinate} = $char ;
So I put the following code into zbuffer, just to get the real intersection point
my %ALL_CROSS_CHARS = map {$_, 1}
(
'-', '|', '.', '\'', '\\', '/', '+', '╱', '╲', '╳',
'─', '│', '┼', '┤', '├', '┬', '┴', '╭', '╮', '╯', '╰',
... ...
But I understand your design. You want to make the zbuffer module simple and not care about other modules. I also understand that I can perform secondary filtering to get what I want.It depends on what you think, I can accept it.(Using spaces to filter is the fastest. Even if I use secondary filtering, it will not reduce the efficiency too much, and spaces have already filtered out most cases.)
(3). I use an array instead of a string to record each coordinate point because when the intersection is next to an intersection, the top two characters need to be considered.However, we already have the hash of intersecting_elements. When I get the neighbor points, I may have to consider whether the neighbor points are also intersection points. A judgment will be added here. If all points are represented by arrays, this judgment will not be needed. What do you think?
(4). I added the elements_ref hash so that external modules can have element references at each point when filtering. If you think there is a better way, I won't use it.But if I don't have this reference, how can I exclude CROSS_MODE_IGNORE
,You think it’s not good to use CROSS_MODE_IGNORE inside zbuffer, but I have to use it outside.
(5). get_coordinates
the function exports characters based on elements. If there are mutual coverings within the elements, such as multiple wiri arrows or strip groups, then only the top-level characters are saved. Internal crossovers are ignored.This will result in incomplete crossover.So I changed the function to get_strip_coordinates
.
(6). I write comments in the code to let you quickly understand what I wrote and save you time. I will definitely delete them, including unnecessary comments, when I submit them in the end, but if you think this is not good, I will try not to write them in the future. Or write a few notes in important places.I know that code that requires comments is not good code.
Mainly the above, I need your opinion for further action.
Let's take the questions one at the time.
(1). Can I specify a range when generating zbuffer. Because whether it is cross-mode or other rendering, we are just for presentation, so we only give the part that the user can see.
When rendering, only the part that can be seen by the eyes can save the time of zbuffer generation.Also saves processing time for external code.
The ZBuffer is for everything not only the visible part.
Even if we passed a view port it wouldn't make a large difference as we need to compute if the object fits in it and clip anything that partly in the view port.
The idea is to update the Zbuffer not regenerate it, even if it's not implemented the current code is very fast, and when it gets updated it will be faster than generating only data for the viewport.
Another advantage is that elements that are outside the view port also get in the ZBuffer; that means that we'd get correct crossing overlays when the crossing is on the edge of the view port.
I also have the idea of using extra zbuffers for implementing scoped cross mode, in that case we only pass the elements we want to be added to the ZBuffer.
Finally, the cross module and Asciio should know as little as possible about each other. Cross should not know about what is being displayed or not, it does crossing overlay without any other knowledge than the ZBuffer.
If you're OK with this I will answer the next question. Otherwise we discuss this question till we agree.
@nkh All right, I agree. Go ahead.
(2). You use spaces to filter the cross points. But these cross points are not really cross points. I need to filter it a second time after I get them.(For example, if a letter a is covered with a letter b, no matter what is around them, I don't think there is an cross point here.)
if($char eq ' ') { delete $self->{intersecting_elements}{$coordinate} } elsif( ($self->{coordinates}{$coordinate} // ' ') ne ' ') { $self->{intersecting_elements}{$coordinate} = [ $char, $self->{coordinates}{$coordinate} ] ; }
$self->{coordinates}{$coordinate} = $char ; So I put the following code into zbuffer, just to get the real intersection point
my %ALL_CROSSCHARS = map {$, 1} ( '-', '|', '.', '\'', '\', '/', '+', '╱', '╲', '╳', '─', '│', '┼', '┤', '├', '┬', '┴', '╭', '╮', '╯', '╰', ... ... But I understand your design. You want to make the zbuffer module simple and not care about other modules. I also understand that I can perform secondary filtering to get what I want.It depends on what you think, I can accept it.(Using spaces to filter is the fastest. Even if I use secondary filtering, it will not reduce the efficiency too much, and spaces have already filtered out most cases.)
ZBuffer doesn't know or care about the cross module, It provides a list of set cells and their neighbors.
So you do have to filter only the cell that are of interest for the cross module.
Please don't delete anything in intersecting_elements, that data belongs to Asciio, Do not put anything in it either, consider ZBuffer to be read only.
As you have understood, anything that is a space doesn't get added to the ZBuffer, so the number of points in the ZBuffer are usually low.
@nkh I accept that, too. What do you think of the third question? I need to handle the intersection next to the intersection myself.
(3). I use an array instead of a string to record each coordinate point because when the intersection is next to an intersection, the top two characters need to be considered.However, we already have the hash of intersecting_elements. When I get the neighbor points, I may have to consider whether the neighbor points are also intersection points. A judgment will be added here. If all points are represented by arrays, this judgment will not be needed. What do you think?
Can you give me a code example? even pseudo code is fine
Or point at a specific line in the code and I will read it.
@qindapao I also added the code below (commented out) as I thought that it would help.
@nkh
The third question is the special situation I mentioned.Neighbor points sometimes need multiple layers of characters instead of one character.
@qindapao If I'm not reading my own code wrong, get_neighbors() returns a stack of characters.
I'll run a test and get back to you.
@nkh All right. I'm going to bed, and we'll discuss it later. ( ˙-˙ )
Three elements on top of each other
ZBuffer returns a list of the 2 characters that are on top of each other.
Do you need more than 2 characters?
Here's the code I used in Gtk/Asciio.pm
sub expose_event
{
my ( $widget, $gc, $self ) = @_;
$gc->set_line_width(1);
my ($character_width, $character_height) = $self->get_character_size() ;
my ($widget_width, $widget_height) = ($widget->get_allocated_width(), $widget->get_allocated_height()) ;
use App::Asciio::ZBuffer ;
use Data::TreeDumper ;
my $zbuffer = App::Asciio::ZBuffer->new($self->{ELEMENTS}->@*) ;
while( my($coordinate, $elements) = each $zbuffer->{intersecting_elements}->%*)
{
my $neighbors = $zbuffer->get_neighbors($coordinate) ;
print DumpTree { stack => $elements, neighbors => $neighbors }, $coordinate ;
# compute overlay
} # draw background
@qindapao here's a better example
the boxes intersect and there's an extra element "o" on top of the intersection, there's also and extra element "x" that is on top of the box and neighbor to "o"
the current code returns the list of neighbors but you have to check if the neighbors are stacked.
I modified get neighbors, according to what you told me (and understood) and it can return the neighbor's stack at the same time.
That's if two stacked characters are enough for you.
@nkh Hello, that's what I mean. The algorithm document needs to be updated slightly, and there are no restrictions on two characters. Maybe three or more.
Did you forget to upload your code to github?I didn't find the new code.
please take a look at the fourth and fifth questions together. Especially the fifth question.
@qindapao I needed your response first, the code is in the latest f2b982e, with a commented out example for all the get_neighbor_xxx functions in GTK::Asciio::expose_event.
The functions still return a 2 characters stack. once you have refactored the code send me an example where more than 2 characters are needed and we'll devise a system.
(4). I added the elements_ref hash so that external modules can have element references at each point when filtering. If you think there is a better way, I won't use it.But if I don't have this reference, how can I exclude CROSS_MODE_IGNORE,You think it’s not good to use CROSS_MODE_IGNORE inside zbuffer, but I have to use it outside.
(5). get_coordinates the function exports characters based on elements. If there are mutual coverings within the elements, such as multiple wiri arrows or strip groups, then only the top-level characters are saved. Internal crossovers are ignored.This will result in incomplete crossover.So I changed the function to get_strip_coordinates.
(4). remind me why we ignore ellipses and if-boxes
(5). I didn't think of that case so it's a bug. I'll fix it ASAP.
@nkh
@qindapao I needed your response first, the code is in the latest f2b982e, with a commented out example for all the get_neighbor_xxx functions in GTK::Asciio::expose_event.
The functions still return a 2 characters stack. once you have refactored the code send me an example where more than 2 characters are needed and we'll devise a system.
Let me explain, the current cross-mode code actually supports more than two stacked characters.I didn't limit the number of stacked characters, the algorithm documentation here is out of date.
For example, we have the four lines a
, b
, c
, d
above. If the cross mode is turned on, places 2
and 3
will be filled with a cross character.Parts of line b and line d are close together(They are adjacent to each other, there are no other grids).
Pay attention to the cross I marked with a green circle. The reason why it is a cross is because it found that its upper, lower and right sides are satisfied, and one of the two stacked characters on the left meets the condition.
But if we move the line a
to the right, until the position of the first cross character.
At this time, there are actually three characters below the first cross character (the position of the red circle below). The bottom one is -
, and the upper two layers are all |
. If only the characters in the upper two layers are considered, then the characters marked by the green circle on the right cannot be filled with a cross character! Obviously the cross character should still be filled in at this time. Therefore, the three levels of characters on the left must be considered.
(4). remind me why we ignore ellipses and if-boxes
What you set before allows users to choose to ignore certain elements and not participate in crossover.you yourself forgot
(4). I know what it does but why did we decide that ellipses and triangles shouldn't cross?
@qindapao can you put the cross documentation above in the documentation?
I'll update the ZBuffer to have all the intersections but I need to know which of the interfaces you want to use
as I don't want to maintain 4 interfaces.
@nkh
This is the document, but it says at most two top-level characters. Actually, there are more than two floors.Just don't limit to two characters when you generate the intersection stack.
(4). I know what it does but why did we decide that ellipses and triangles shouldn't cross?
@nkh We can don't filter by default. I can also filter before giving zbuffer elements, instead of filtering in zbuffer.But Other scenes how to realize the cross mode of local scope later? I don't have any good ideas.I think it might be useful to refer to the element to which each point belongs.
@nkh The names of your four functions make me dizzy. ๑_๑
@nkh get_neighbors_stack Let me use this.Can save my judgment on undef
@qindapao
new ZBuffer interface in 7f65647 , example code in GTK::Asciio.pm, which return a full stack. Note that ' ' (space) is now part of the stack.
self crossing elements (question 5), not fixed yet.
(5). get_coordinates the function exports characters based on elements. If there are mutual coverings within the elements, such as multiple wiri arrows or strip groups, then only the top-level characters are saved. Internal crossovers are ignored.This will result in incomplete crossover.So I changed the function to get_strip_coordinates.
I have a solution for wirl arrows crossing themselves
But the position where arrow section overlap have a stack 3 deep, the end of the first section, the start of the next section, and a character laid on top of those (a dot).
Not sure how that impacts Cross. But this will be needed when we do some scoped crossing on arrow sections.
What do you think about this solution.
@nkh you seem to have missed a situation.I'll turn on the computer and tell you tomorrow.It's a little late here, so I'll go to bed first.
@nkh How to deal with strip group? alt + g + g The internal intersection of that kind.The data seen outside has been flattened.
@nkh This is the case, all wiri arrow's are one element with cross inside.
@qindapao I have answered your question above. I have a, local, branch, where the self-crossing is reported by the Zbuffer. I also explained that wirl arrow internal arrow will also report an intersection stack
https://user-images.githubusercontent.com/45409/284009333-bc2e0649-dfb4-4718-8742-9331d899f546.png
Would that be enough for the cross functionality?
How to deal with strip group? alt + g + g The internal intersection of that kind.The data seen outside has been flattened.
well, flat is flat, we can't have the speed of flattened groups and Crossing on the flattened groups
it's not impossible just cumbersome and slower
@qindapao the simplest way to deal with to tell me which branch you are using the zbuffer in, I can then develop eventual changes to ZBuffer in that branch. The way we're doing it now is not practical.
@qindapao the simplest way to deal with to tell me which branch you are using the zbuffer in, I can then develop eventual changes to ZBuffer in that branch. The way we're doing it now is not practical.
I haven't integrated in any branch for the time being. Since last time.The weekend is over again. I will to help my children with their homework. We can only wait until we are free again.
be sorry.
@nkh
@qindapao I have answered your question above. I have a, local, branch, where the self-crossing is reported by the Zbuffer. I also explained that wirl arrow internal arrow will also report an intersection stack
https://user-images.githubusercontent.com/45409/284009333-bc2e0649-dfb4-4718-8742-9331d899f546.png
Would that be enough for the cross functionality?
Question 7
How to deal with strip group? alt + g + g The internal intersection of that kind.The data seen outside has been flattened.
Answer
well, flat is flat, we can't have the speed of flattened groups and Crossing on the flattened groups
it's not impossible just cumbersome and slower
- group that's going to be flattened must be "crossed" without any other element
- once flattened return the above crossed elements, IE including the cross overlays
- flattened groups also keep the ZBuffer of it's elements
- when objects cross with a flattened group, its ZBuffer intersection are used
I see, strip group needs a zbuffer cache.When they are generated, they are statically stored in it and dynamically updated according to the position of elements.
I also think of many interesting things that can be realized with zbuffer.It seems that the most important thing now is to realize it correctly.
When I have time, I will take this as the most important work to finish. And ensure that the characteristics of the current crossover algorithm are not lost.
I'm mulling other interesting ideas. I'll discuss with you after I finish the basic work.Things are getting interesting.
@nkh Zbuffer cache for stripe groups, we can save relative coordinates without saving absolute coordinates. So we don't have to update it dynamically. We just need to process the coordinates when calculating.Am I right?In order to save the relative coordinates, the basic code should need some differentiation.
@qindapao what would be the advantage of saving relative coordinates in the ZBuffer?
@nkh
@qindapao what would be the advantage of saving relative coordinates in the ZBuffer
I may be wrong. Just update zbuffer when we change strip group. Forget what I said.
continued in #165
sub transform_elements_to_ascii_two_dimensional_array is a hack!
4 function calls from copy to clipboard to the function creating the ascii, functions that need to be named more properly.
Cross also has a function to create an array, slightly different.
Too many functions doing the same thing, mixing everything and not called what they should.