I am getting similar performace improvements(in a similar vatti clipper)
just because of the support edges based append code.How much of the improvement can be attributed to just the intersection evaluation method?.
sorry,The measurments got mixed up with the standard vatti method.It is much faster as compared to the bubble method for contours > 200 vertices.
Last edit: Ignorant 2017-09-22
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Half to two thirds of the performance increase is due to the improved sort algorithm (I changed the bubble sort code to a modified merge sort). The rest is just to cleaner code, especially in AddPath.
Note that these performance increases are small when there are relatively few intersections in the clippping op.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
marvelous!.
[I will try it in Murtas vatti clipper.
.The bubbling method was slow compared to even the old vatti method.
The merge sort for linked list is expected to be 10+ times faster than even insertion sort
for > 100 vertex input contours.
Mahesh Naik
Ps: I will do detail profiling after I get a usable delphi/cpp code for
the new clipperEven transfering the output from the vatti process to the
delivered output is very time consuming.!
Half to two thirds of the performance increase is due to the improved sort
algorithm (I changed the bubble sort code to a modified merge sort). The
rest is just to cleaner code, especially in AddPath.
Note that these performance increases are small when there are relatively
few intersections in the clippping op.
marvelous!.
[I will try it in Murtas vatti clipper.
Mahesh Naik
Ps: I will do detail profiling after I get a usable delphi/cpp code for
the new clipperEven transfering the output from the vatti process to the
delivered output is very time consuming.!
Half to two thirds of the performance increase is due to the improved
sort algorithm (I changed the bubble sort code to a modified merge sort).
The rest is just to cleaner code, especially in AddPath.
Note that these performance increases are small when there are relatively
few intersections in the clippping op.
Angus
How about using the merge sort for the open edge intersetions in the beam.?
I am copying the non recursie mergsesort cpp routines from the net to time the improvement.(probably yours only)
Last edit: Ignorant 2017-09-22
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Got it from there within hrs of your posting.A little bit different then
ths pascal clipper code?.
Where do I put the intersection generation statements?.
I will wait till you post your cpp code ,to copy paste the code,in a
alternate parity only clipper.
i got the cpp code....thanks...
you have a lot of goodwill for all your efforts.
Angus,
You have a new method for getting the within beam intersection.!
How much is the time diference?.
Mahesh Naik
I am getting similar performace improvements(in a similar vatti clipper)
just because of the support edges based append code.How much of the improvement can be attributed to just the intersection evaluation method?.
sorry,The measurments got mixed up with the standard vatti method.It is much faster as compared to the bubble method for contours > 200 vertices.
Last edit: Ignorant 2017-09-22
Performance increase is amazing! What is the main reason for the increase?
Half to two thirds of the performance increase is due to the improved sort algorithm (I changed the bubble sort code to a modified merge sort). The rest is just to cleaner code, especially in AddPath.
Note that these performance increases are small when there are relatively few intersections in the clippping op.
marvelous!.
[I will try it in Murtas vatti clipper.
.The bubbling method was slow compared to even the old vatti method.
The merge sort for linked list is expected to be 10+ times faster than even insertion sort
for > 100 vertex input contours.
Mahesh Naik
Ps: I will do detail profiling after I get a usable delphi/cpp code for
the new clipperEven transfering the output from the vatti process to the
delivered output is very time consuming.!
On Tue, Sep 19, 2017 at 3:36 AM, Angus Johnson angusj@users.sf.net wrote:
Last edit: Ignorant 2017-09-22
Also,The perormance is probably better presented as number of open
edge(i.e. excluding horizontal edges) intersection events in a unit of time.
On Wed, Sep 20, 2017 at 1:39 PM, Mahesh Naik maheshnaik.mumbai@gmail.com
wrote:
Last edit: Ignorant 2017-09-23
Angus
How about using the merge sort for the open edge intersetions in the beam.?
I am copying the non recursie mergsesort cpp routines from the net to time the improvement.(probably yours only)
Last edit: Ignorant 2017-09-22
I've posted my modified merge sort algorithm here as a very simple c++ demo: https://stackoverflow.com/a/46319131/359538
Got it from there within hrs of your posting.A little bit different then
ths pascal clipper code?.
Where do I put the intersection generation statements?.
I will wait till you post your cpp code ,to copy paste the code,in a
alternate parity only clipper.
i got the cpp code....thanks...
you have a lot of goodwill for all your efforts.
On Sat, Sep 23, 2017 at 6:14 PM, Angus Johnson angusj@users.sf.net wrote:
Last edit: Ignorant 2017-09-24