List, Array, or something else ...

[marc_256]

Hi,

My next question is about the building of my PLC program.
For PLC control I can use [LADDER] or [ST] languages.

But I want to use GUI blocks to build a PLC program. (See image below)
For this I need a lot of [BEZIER] curves to make the connections in between the blocks.
But this is a big part of the CPU calculation cost.

For a smooth bezier curve you need at least 10 points.
So, I need to calculate all the point every time if I add or move a NODE.
- Start point X,Y
- and in between at least 8 X,Y point data
- End Point X,Y

So, my question,
What is the fastest way to store/read a lot of bezier curves data points ?
List, Array, or something else ...


thanks,
marc,

[jacdelad]

I would create an own structure with starting and ending point and a list for the points between.
Since all your data is points, you could also just simply use a list filled with points.

Structure Bezier
List Point.POINT()
EndStructure

Define NewList MyList.Bezier()

Each entry of MyList() contains a list with the points.

[BarryG]

Lots of examples in this forum if you search for "bezier". Maybe check out what others have done?

[STARGÅTE]

For this I need a lot of [BEZIER] curves to make the connections in between the blocks.
But this is a big part of the CPU calculation cost.

For a smooth bezier curve you need at least 10 points.
So, I need to calculate all the point every time if I add or move a NODE.
- Start point X,Y
- and in between at least 8 X,Y point data
- End Point X,Y

If you use the VectorDrawing library, you can use AddPathCurve and get a Bezier curve "for free". I had use this library also in my Pure Circuit programm


To store the two end point and the two control points, I would prefer to use a structure. So no array and no list.

[marc_256]

My question was not how to create a bezier, but ...

So, my question,
What is the fastest way to store/read a lot of bezier curves data points ?
List, Array, or something else ...

@STARGÅTE

thanks, your program is very well done.
very nice GUI ...

marc

[SMaag]

I started with a Spline definition with 2 Arrays
1x for the definition Points
1x for the caluculated or all Points

I decided to use Arrays because sometimes you have to address specific points.
Finding Points in a List is not so effective!
A Redim of the Arrays is necessary OnChangeOf: NumberOfDefintionPoints, CalculationResolution
(in my opinion this is a rare case)


The Advantage (my opinion):
- You have to recalculate only the Splines with changed definition Points
- You can select the grafic library you want to draw with (at my tests Vectordrawing was aprox. 10x slower than 2D-Drawing)
- You can try different algorithm to calculate the Splines (maybe Matrix based calulation with SSE Extention, Different Spline-Types)

I'm working on that stuff! But not ready yet!

Code: Select all

Enumeration ESplineType
  #Spline_NaturalCubic
  #Spline_CatmullRom
  #Spline_CubicBezier
  #Spline_QuadraticBezier
EndEnumeration

Structure TSpline
  Type.i                  ; SplineType
  Array DefPt.Point(0)    ; Definition Points
  Array Pt.Point(0)       ; calculated Points
EndStructure

[marc_256]

@SMaag

Thanks for your reaction.

at my tests Vectordrawing was aprox. 10x slower than 2D-Drawing

Same for my tests, I also use 2D-Drawing now.
And ARRAYs are also working well for me (for now).
I don't know there are faster ways to store/read data ?

thanks,
marc,

[STARGÅTE]

at my tests Vectordrawing was aprox. 10x slower than 2D-Drawing

Same for my tests, I also use 2D-Drawing now.

What kind of comparison did both of you do?
The vector drawing library supports alpha-blending and anti aliasing for example. A fair comparison is therefore not easy.
When I compare DrawVectorText with DrawText, the vector version is faster.
When I compare AddPathCircle with Circle, the 2D drawing is faster, but only 2-3 times.
However, the factor is worse, when the drawing forms are smaller, because more aliasing has been performed compared to the total area of drawing.
So in fact, LineXY is much faster than AddPathLine, but look less pixel art.

Code: Select all

Enumeration
	#Window
	#Gadget1
	#Gadget2
	#Font
EndEnumeration

Define Time1.q, Time2.q

OpenWindow(#Window, 0, 0, 800, 400, "Vector vs. 2D Drawing", #PB_Window_ScreenCentered|#PB_Window_SystemMenu)
CanvasGadget(#Gadget1, 0, 0, WindowWidth(#Window)/2, WindowHeight(#Window))
CanvasGadget(#Gadget2, WindowWidth(#Window)/2, 0, WindowWidth(#Window)/2, WindowHeight(#Window))

Define I.i
Define Loops = 10000

RandomSeed(1)
Time1 = ElapsedMilliseconds()
If StartVectorDrawing(CanvasVectorOutput(#Gadget1))
	For I = 1 To Loops
		VectorSourceColor($80000000|Random($FFFFFF))
		AddPathCircle(Random(400), Random(400), Random(50))
		FillPath()
	Next
	StopVectorDrawing()
EndIf
Time1 = ElapsedMilliseconds() - Time1

RandomSeed(1)
Time2 = ElapsedMilliseconds()
If StartDrawing(CanvasOutput(#Gadget2))
	DrawingMode(#PB_2DDrawing_Transparent|#PB_2DDrawing_AlphaBlend)
	For I = 1 To Loops
		FrontColor($80000000|Random($FFFFFF))
		Circle(Random(400), Random(400), Random(50))
	Next
	StopDrawing()
EndIf
Time2 = ElapsedMilliseconds() - Time2

SetClipboardText("Vector: "+Str(Time1)+" ms  |  2D: "+Str(Time2)+" ms")
SetWindowTitle(#Window, "Vector: "+Str(Time1)+" ms  |  2D: "+Str(Time2)+" ms")

Repeat
	Select WaitWindowEvent()
		Case #PB_Event_CloseWindow
			Break
	EndSelect
ForEver

Vector: 375 ms | 2D: 146 ms

Code: Select all

Enumeration
	#Window
	#Gadget1
	#Gadget2
	#Font
EndEnumeration

Define Time1.q, Time2.q

OpenWindow(#Window, 0, 0, 800, 400, "Vector vs. 2D Drawing", #PB_Window_ScreenCentered|#PB_Window_SystemMenu)
CanvasGadget(#Gadget1, 0, 0, WindowWidth(#Window)/2, WindowHeight(#Window))
CanvasGadget(#Gadget2, WindowWidth(#Window)/2, 0, WindowWidth(#Window)/2, WindowHeight(#Window))
LoadFont(#Font, "Arial", 30)

Define I.i
Define Loops = 10000

RandomSeed(1)
Time1 = ElapsedMilliseconds()
If StartVectorDrawing(CanvasVectorOutput(#Gadget1))
	VectorFont(FontID(#Font))
	For I = 1 To Loops
		VectorSourceColor($80000000|Random($FFFFFF))
		MovePathCursor(Random(300), Random(380))
		DrawVectorText("Hello World!")
	Next
	StopVectorDrawing()
EndIf
Time1 = ElapsedMilliseconds() - Time1

RandomSeed(1)
Time2 = ElapsedMilliseconds()
If StartDrawing(CanvasOutput(#Gadget2))
	DrawingFont(FontID(#Font))
	DrawingMode(#PB_2DDrawing_Transparent|#PB_2DDrawing_AlphaBlend)
	For I = 1 To Loops
		FrontColor($80000000|Random($FFFFFF))
		DrawText(Random(300), Random(380), "Hello World!")
	Next
	StopDrawing()
EndIf
Time2 = ElapsedMilliseconds() - Time2

SetClipboardText("Vector: "+Str(Time1)+" ms  |  2D: "+Str(Time2)+" ms")
SetWindowTitle(#Window, "Vector: "+Str(Time1)+" ms  |  2D: "+Str(Time2)+" ms")

Repeat
	Select WaitWindowEvent()
		Case #PB_Event_CloseWindow
			Break
	EndSelect
ForEver

Vector: 415 ms | 2D: 1038 ms

[SMaag]

@Sargate
Thanks for this information about the Vector drawing!
I did one time a quick and dirty test. Only to see if there is a difference and aprox. how much!
I did not test it in details!

@marc256
There was a discussion here or in the forum (or german forum) a longer time ago about the speed
difference between Arrays and Lists.
As I remember a complete step trough all entries was aprox. same speed.
For Next with the Array and For Each with the list.
If you wan't to access an individal entry in a list this needs much longer because you have to step trough the list
or you need a seperate index. Both needs longer than a direct access to an Array-Element!

But the speed often depends more on cache issues than on code.
I guess there will be an advantage with the cache prefetches when using Array's because the Datas are in a block.
At lists you allocate single structures. So the data can be nearly in a block or completely distributed in the memory.
I guess this will depend on how you allocate (If you allocate all together I expect that the datas are in a block)
If you allocate the structures some here and some there, Maybe you allocate it in different memory locations,
what can cause longer chache loading times. But this is not possible to predict correctly!

As I know: a complete Memory page (what is 256Byte) is loaded to the level 1 cache line if you access 1 address.
On level 2, 3 Caches I guess bigger memory Blocks are loaded (maybe 4K or more). So the speed depends extremly on the DataStructure
in the Memory!

[marc_256]

@STARGATE

It is some time now,
but my results for VectorDrawing ware very well for all about WYSIWYG applications.
Slower but better graphical results.

But for my CAD/CAM application, you need 1000s of lines and 1000s of points in one frame, (see image below)
at a refresh rate of 25 FPS, you use a lot of CPU power in VectorDrawing mode.

And for the pure CAM application I need speed, not beauty ...
You can not use GPU power (I think PB can't) for that, because the user can scale, rotate and translate more than 10 time a second.
Sprites are for gaming fixed images, no animations or refreshes of lines and points.

About alpha-blending and anti aliasing,
alpha-blending can be done with 2DDrawing also,
anti aliasing 2, 4, 6 is the big problem here with 1000s of lines ...

But I want to make a selection button choice in my program so the user can select the drawingmode himself.





@sMAAG

Thanks again,

nice piece of explications,
I use for now also the Array solution,
for what I know of PB I think this is the fastest way to access data stored in memory.


greetings,
marc

[SMaag]

And for the pure CAM application I need speed, not beauty ...
You can not use GPU power (I think PB can't) for that,

PB can use GPU Power! But only with the Mesh() Functions!
I did a quick and dirty test: I converted an air Plane with FreeCad to a STL-File.
With the STL-File I created a Mesh()! There are some different MeshTypes
#PB_Mesh_TriangleList
#PB_Mesh_TriangleStrip
#PB_Mesh_TriangleFan
#PB_Mesh_PointList
#PB_Mesh_LineList
#PB_Mesh_LineStrip

The Plane has arraound 100.000 Triangel. Camera-Move + Object Rotation.
All done with GPU (GPU-Load went up from 4% to 13%) CPU-Load 3%

I tried same with the Eifel Tower with 140.000 Triangels! There is nearly no difference compared to
the Plane with 100.000 Triangles

Here is my quick and dirty Test with the Plane!
CAD_STL_DEM_V001.z

https://github.com/Maagic7/PureBasicFra ... main/Demos

because the user can scale, rotate and translate more than 10 time a second.
Sprites are for gaming fixed images, no animations or refreshes of lines and points.

No! The PB-Spirte Library is much more!
The Sprite Library provides a double buffered Screen you can use for ever you want.

If you just do drawing functions it's good to use Sprite-Library and double buffering.
The effect: You always draw into the hidden buffer (it's not painted on the Monitor).
If all drawings are ready you have to swap both buffers with FlipBuffers() command.
This swaps the Pointers of the 2 buffers and make the hidden buffer active so you can
see the drawing on the monitor!

[pf shadoko]

hi,

i may be off topic, i haven't read the whole thread
animating a bezier curve requires no resources
in the example below I animate 1000 (32 segments)

Code: Select all

Structure f2
  x.f
  y.f
EndStructure

Procedure f2(*v.f2,x.f,y.f)
  *v\x=x
  *v\y=y
EndProcedure

Procedure bezier(*p.f2,  *p0.f2,*p1.f2,*p2.f2,*p3.f2,  r.f=0.5)
  Protected.f s=1-r,  r2=r*r,r3=r2*r,s2=s*s,s3=s2*s , c0,c1,c2,c3
  c0=s3:c1=3*r*s2:c2=3*r2*s:c3=r3
  
  *p\x=*p0\x*c0 + *p1\x*c1 + *p2\x*c2 + *p3\x*c3
  *p\y=*p0\y*c0 + *p1\y*c1 + *p2\y*c2 + *p3\y*c3
EndProcedure

Procedure tracebezier(*p0.f2,*p1.f2,*p2.f2,*p3.f2,col=$ffffff,nb=32)
  Protected  i,pos.f2,apos.f2
  f2(pos,*p0\x,*p0\y)
  For i=1 To nb
    apos=pos:bezier(pos,*p0,*p1,*p2,*p3,i/nb)
    LineXY(apos\x,apos\y,pos\x,pos\y,col)
  Next
EndProcedure

Define p0.f2,p1.f2,p2.f2,p3.f2, a.f,aa.f

OpenWindow(0, 0, 0, 1280, 720, "bezier", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
CreateImage(0,1280,720)
ImageGadget(0, 0, 0, 1280,720, ImageID(0))

Repeat  
  StartDrawing(ImageOutput(0))
  Box(0,0,1280,720,0)
  For i=0 To 1000
    a=aa+i/100*2*#PI
    px=Cos(a/10)*200+640
    py=Sin(a/10)*200+360
    r=(i*255/125) & 255
    g=(i*255/500) & 255
    b=(i*255/250) & 255
    col=RGB(r,g,b)
    f2(p0,Cos(a+0.0)*100+px,Sin(a+0.0)*100+py)
    f2(p1,Cos(a+0.4)*200+px,Sin(a+0.4)*200+py)
    f2(p2,Cos(a-0.4)*300+px,Sin(a-0.4)*300+py)
    f2(p3,Cos(a+0.0)*400+px,Sin(a+0.0)*400+py)
    tracebezier(p0,p1,p2,p3,col)
  Next
  StopDrawing()
  SetGadgetState(0,ImageID(0))
  aa+0.01
  Delay(16)
  Event = WindowEvent()
Until Event = #PB_Event_CloseWindow