# ENIGMA Development Environment

 Pages: 1 2 »
 Author Topic: Custom: Curve drawing functions (Bezier and Spline)  (Read 4435 times)
TheExDeus
 Posted on: December 02, 2010, 09:36:53 AM

Joined: Apr 2008
Posts: 1872

Curve functions

Version:1.1

Changelog:
1.1
-Added new spline functions that have control points
-Made spline_begin() function use vectors and stacks. This decreases memory consumption and allows nesting (several _begin() and _end() inside one another).
-Added new _end() function that optimizes the curve (reduces vertexes based on point distance).

Description: These are functions for drawing curves. Both Bezier and splines. These functions allow drawing them with specific widths, with alpha and color blending, as well as getting points on the curve.

Functions:
Code: (C) [Select]
`void draw_bezier_quadratic(float x1,float y1,float x2,float y2,float x3,float y3);void draw_bezier_cubic(float x1,float y1,float x2,float y2,float x3,float y3, float x4, float y4);void draw_set_curve_color(int c1, int c2);void draw_set_curve_alpha(float a1, float a2);void draw_set_curve_mode(int mode);void draw_set_curve_detail(int detail);void draw_set_curve_width(int width);void draw_set_antialiasing(bool enable, int qual);float draw_bezier_quadratic_x(float x1,float y1,float x2,float y2,float x3,float y3, float t);float draw_bezier_quadratic_y(float x1,float y1,float x2,float y2,float x3,float y3, float t);float draw_bezier_cubic_x(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float t);float draw_bezier_cubic_y(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float t);void draw_spline_part(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, int c1, int c2, float a1, float a2);void draw_spline2c(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4);void draw_spline3(float x1, float y1, float x2, float y2, float x3, float y3);void draw_spline3c(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float x5, float y5);void draw_spline4(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4);void draw_spline4c(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float x5, float y5, float x6, float y6);void draw_spline_begin(int mode);int draw_spline_vertex(float x, float y);int draw_spline_vertex_color(float x, float y, int col, float alpha);void draw_spline_end();int draw_spline_optimized_end();`Most functions are self explanatory (if not, then the example shows most of them at work). Only things I should note is about draw_spline_part, which is not actually meant to be used. It is used in other spline functions and that is the one that actually draws the spline. You can use it separately if you wish, thou then you need to call glBegin and glEnd, because that function only returns vertexes.
Another function I should note is draw_spline2c, it draws a line between two points, but accounts for two control points that shape the actual line. The rest of the spline drawing functions that have c at the end act the same. The first and the last points are control points.
draw_spline_begin() function needs at least 4 points to draw one line. The first and the last point is a control point.
draw_spline_optimized_end() function should be used in some cases like when there are a lot of points and many of them can be close together. This function checks the distance of the two points and then reduces the vertex count as needed. The maximum vertex count is still pr_curve_detail (set by draw_set_curve_detail()). This function returns the vertex number drawn.

Installation: As Enigma doesn't have an easy 2 click extension mechanism now (or will never have?!?), you need to put these files in manually. Copy GScurves.h and GScurves.cpp into Enigma\ENIGMAsystem\SHELL\Graphics_Systems\OpenGL (preferably). Then open: Enigma\ENIGMAsystem\SHELL\SHELLmain.cpp and put #include "Graphics_Systems/OpenGL/GScurves.h" into line 63 or so (after #if ENIGMA_GS_OPENGL). Then either use bash script located in Enigma\ENIGMAsystem\SHELL\Developer\automake.sh, or if you are on Windows (like me), then just open Enigma\ENIGMAsystem\SHELL\Graphics_Systems\OpenGL\Makefile and add:
Quote
g++ -c GScurves.cpp      -o .eobjs_\$(MODE)/GScurves.o \$(FLAGS)
To somewhere in the top. And: ".eobjs_Run/GScurves.o" everywhere at the bottom (just look where similar action is done.

Notice: You need to actually do additional things to run the example or use this code as intended. First, you need to fix merge_color function which is buggy in the current repo. To fix this, find and open GScolors.cpp, find merge_color function and replace the code with this:
Code: [Select]
`int merge_color(int c1,int c2,double amount){    amount = amount > 1 ? 1 : (amount < 0 ? 0 : amount);    return    (unsigned char)(fabs(__GETR(c1)+(__GETR(c2)-__GETR(c1))*amount))    | (unsigned char)(fabs(__GETG(c1)+(__GETG(c2)-__GETG(c1))*amount))<<8    | (unsigned char)(fabs(__GETB(c1)+(__GETB(c2)-__GETB(c1))*amount))<<16;}`Second, you need to add a new math function, which I didn't just insert as a script for some reason. Its lerp (linear interpolation) and seemed useful as a standard function. Open mathnc.cpp and put this somewhere:
Code: [Select]
`double lerp(double x, double y, double a) { return x + ((y-x)*a); }`Also, open mathnc.h and add the header:
Code: [Select]
`double lerp(double x, double y, double a);`I think this should be all. Maybe I have forgotten something, so if you get an error post it here.

Example controls: You can scroll through rooms with left and right arrows. In the third room (where there is initially just a black screen) you can draw a curve with your mouse. Left click to add a point, or hold right button to add a lot of points. In the last room you can move that jelly thing to your mouse with left click and increase/decrease detail with up and down arrows. Room system seems buggy, so I couldn't find a way to return back to previous rooms. Its just restarts from the first room when you press left arrow. Press number keys to disable, enable and change quality of anti-aliasing. 1-Disabled. 2-Enabled, fastest. 3-Enabled, nicest. 4-Enabled, don't care.

To-Do:
-Add new functions to get points on splines

Thanks to LSnK for inspiring me to make this for Enigma, as well as making that beautiful example (which modified code is used in this example too).
 « Last Edit: December 04, 2010, 04:18:36 PM by HaRRiKiRi » Logged
Josh @ Dreamland
 Reply #1 Posted on: December 02, 2010, 10:55:54 AM

Prince of all Goldfish

Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

They look nice, HaRRi. I'd recommend keeping your own array, though. Here is my suggestion:
Code: (C) [Select]
`#include <stack>#include <vector>struct splinePoint { float x,y; };typedef std::vector<splinePoint> a_spline;static std::vector<a_spline*> startedSplines;void draw_spline_begin() { startedSplines.push(new a_spline); }void draw_spline_vertex(float x, float y) { startedSplines.top()->push_back(splinePoint(x,y)); }void draw_spline_end() {  a_spline &arr = *startedSplines.top();  for (int i = 0; i < arr.size(); i++)    draw_spline_part( /* I Have no idea of the use case of this function.      Access points with arr[num]. Do bounds checking. It may be frugal      to unroll the first and last four elements; remember, the array can      contain as few as zero points! */ );  delete &arr;  startedSplines.pop();}`
Don't implement any PEBKAC checking until ENIGMA has a centralized error system.

When you're done, feel free to commit your code using your SourceForge details.
...Welcome aboard.
 Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
TheExDeus
 Reply #2 Posted on: December 02, 2010, 11:03:21 AM

Joined: Apr 2008
Posts: 1872

This is something I was looking for. I guess speed hit is minimal or none? Or even a gain? Anyway, thanks for the example.

Also, don't really want to get into all that committing, as I can break more things than I can fix. That is why I post it here so more knowledgeable people can look at it and at some point implement if considered good enough. But I will consider it.
 « Last Edit: December 02, 2010, 11:09:03 AM by HaRRiKiRi » Logged
Josh @ Dreamland
 Reply #3 Posted on: December 02, 2010, 11:09:48 AM

Prince of all Goldfish

Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

Which is why I added you. You understand the implications of committing code; you'll be careful. Adding a couple files typically won't break anything. Just don't forget to commit any files you include. If you keep posting about them here, we can look over it and either have you make changes or implement them ourselves. Ultimately, collaboration should pay off in the end.

You're not Harold.Z on SourceForge?
 Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
TheExDeus
 Reply #4 Posted on: December 02, 2010, 11:14:29 AM

Joined: Apr 2008
Posts: 1872

No I am not. I just registered. HaRRiKiRi was taken (as a username), so its thedeusex.

Also, I thought the point of SVN was not to be able to break anything. As every change is saved, then it should be possible to revert back.. Anyway, I will commit only the few files I myself make. So only functions, not systems as a whole.
 Logged
Josh @ Dreamland
 Reply #5 Posted on: December 02, 2010, 11:26:06 AM

Prince of all Goldfish

Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

Done. And that's probably a good idea until you get the hang of ENIGMA.
I trust you'll commit your merge_color fix, too?

Also, we do have an IRC for this quick back-and-forth sort of thing.
 Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
TheExDeus
 Reply #6 Posted on: December 02, 2010, 03:43:18 PM

Joined: Apr 2008
Posts: 1872

I can't really get why you used lists in that code. I am readying about vectors now and I think I could just use one vector, then clear it when _begin is called and then push_back with every point.
 « Last Edit: December 02, 2010, 03:45:21 PM by HaRRiKiRi » Logged
TheExDeus
 Reply #7 Posted on: December 03, 2010, 04:30:24 PM

Joined: Apr 2008
Posts: 1872

I am having trouble with vectors and structs. This is how I ended up doing it:
Code: (C) [Select]
`struct splinePoint {    float x,y,al;    int col;};std::vector<splinePoint> spline;int draw_spline_begin(int mode){    pr_curve_begin = mode;    return 0;}int draw_spline_vertex(float x, float y){    splinePoint point={x,y,pr_curve_alpha1,pr_curve_color1};    spline.push_back(point);     return 0;}int draw_spline_vertex_color(float x, float y, int col, float alpha){    splinePoint point={x,y,alpha,col};    spline.push_back(point);    return 0;}int draw_spline_end(){    untexture();    glPushAttrib(GL_LINE_BIT);    glLineWidth(pr_curve_width);    glBegin(pr_curve_begin);    if (spline.size()>4){        for (int i = 3; i < spline.size(); i++)        {            draw_spline_part(spline[i-3].x, spline[i-3].y, spline[i-2].x, spline[i-2].y, spline[i-1].x, spline[i-1].y, spline[i].x, spline[i].y, spline[i-2].col, spline[i-1].col, spline[i-2].al, spline[i-1].al);        }   }    glEnd();    glPopAttrib();    glColor4ubv(enigma::currentcolor);    spline.clear();    return 0;}`I have a feeling I have some massive memory leak in there. I basically create the vector at the beginning, add points to it with the vertex functions, draw it in the _end function as well as clearing it so the next time it is empty again. I have a question about that vector declaration and the point adding. The vector will be declared once if its in the beginning right? And the "splinePoint point" will be added to the vector, but when it is cleared the point itself will remain, its just the vector that is cleared right? And so, how can I remove thous points from memory in _end function?

Also,  code=C++  doesn't work for me.. How exactly do you enabled highlighting?
edit: Never mind it seems to need some time to do that.
 « Last Edit: December 03, 2010, 04:33:35 PM by HaRRiKiRi » Logged
Josh @ Dreamland
 Reply #8 Posted on: December 03, 2010, 07:13:55 PM

Prince of all Goldfish

Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

Please make that vector static. You can remove points with vector::clear(). If you don't use a stack, you can't have nested splines (earlier you complained about a lack of nested primitives).

The hope is that the point you declare in the function is never instantiated; that instead, the optimizer makes it so the point is written directly on the space allocated by vector<>.

Instead of clearing it, it would be more efficient (speed wise, not memory wise) to keep your own static index, and only push back if index >= vector::size(). That way, you can just reset the index when begin() is called, and the system doesn't need to waste time on allocation otherwise (especially for repetitive spline drawing).
 Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
RetroX
 Reply #9 Posted on: December 03, 2010, 09:49:55 PM

Master of all things Linux

Location: US
Joined: Apr 2008
Posts: 1055

Question: Why do they all have the type int if you're just returning 0?  In what case would they be non-zero?  Lack of a graphics card?  I mean, I can't think of anything.
 Logged
My Box: Phenom II 3.4GHz X4 | ASUS ATI RadeonHD 5770, 1GB GDDR5 RAM | 1x4GB DDR3 SRAM | Arch Linux, x86_64 (Cube) / Windows 7 x64 (Blob)
Quote from: Fede-lasse
Why do all the pro-Microsoft people have troll avatars?
Josh @ Dreamland
 Reply #10 Posted on: December 04, 2010, 04:28:53 AM

Prince of all Goldfish

Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

The unofficial GM spec says all functions have a return value. I haven't completely decided to stray from that, though I myself tend to use void.
 Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
TheExDeus
 Reply #11 Posted on: December 04, 2010, 06:33:31 AM

Joined: Apr 2008
Posts: 1872

I actually had trouble making your sample code to run, so I ditched the list. I will try to make it work thou.

Quote
Instead of clearing it, it would be more efficient (speed wise, not memory wise) to keep your own static index, and only push back if index >= vector::size(). That way, you can just reset the index when begin() is called, and the system doesn't need to waste time on allocation otherwise (especially for repetitive spline drawing).
So overwriting vectors? Like I have 10 points, and after _end I just make it insert from 0 over the 10 already there? But first, isn't vectors slow at that kind of thing? Like inserting and removing? And what if in the next step I add only 9 points, then the tenth with still be there and draw? Or I just simply didn't understand your idea. Mostly because I think in arrays, not vectors (which is kind of the same, but still).

Quote
Question: Why do they all have the type int if you're just returning 0?  In what case would they be non-zero?  Lack of a graphics card?  I mean, I can't think of anything.
As Josh pointed out, GM has return values for everything. I am not sure if it impacts speed in any way thou. If it is slower then of course it would be better to ditch them for most part. Thou functions like spline_vertex can return the number of points and so on. I actually did make it return that when I did this with arrays.
 Logged
Josh @ Dreamland
 Reply #12 Posted on: December 04, 2010, 07:53:27 AM

Prince of all Goldfish

Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

Yes, overwriting vectors. No, vectors are slow at push_back(). push_back is best case O(1), worst case O(N), and I'd wager the worst case happens the most often. Accessing [] with vectors is O(1). [] just looks up a number, push_back allocates more memory, which often means moving the memory it has. Using push_back for every point every step could mean N^2/2 operations (where N is the number of points) (but I doubt it). Only using push_back when necessary means one frame of N^2/2 disaster case, then the rest are N.

And yes, it's exactly one instruction faster not to return zero. Which could be as much as 20% in the case of draw_primitive_begin(). But that's a really small time, anyway; I'm not too worried. Returning void could mean a compile error if someone tried to assign the return value to a function. (Perhaps I should add checking for that...)
 Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
TheExDeus
 Reply #13 Posted on: December 04, 2010, 01:03:33 PM

Joined: Apr 2008
Posts: 1872

So this is how the code looks like right now:
Code: (C) [Select]
`#include <stack>#include <vector>struct splinePoint {    float x,y,al;    int col;};typedef std::vector< splinePoint > spline;static std::stack< spline, std::vector<spline*> > startedSplines;static std::stack< int > startedSplinesMode;void draw_spline_begin(int mode){    startedSplinesMode.push(mode);    startedSplines.push(new spline);}int draw_spline_vertex(float x, float y){    splinePoint point={x,y,pr_curve_alpha1,pr_curve_color1};    startedSplines.top()->push_back(point);    return startedSplines.top()->size()-2;}int draw_spline_vertex_color(float x, float y, int col, float alpha){    splinePoint point={x,y,alpha,col};    startedSplines.top()->push_back(point);    return startedSplines.top()->size()-2;}void draw_spline_end(){    untexture();    glPushAttrib(GL_LINE_BIT);    glLineWidth(pr_curve_width);    glBegin(startedSplinesMode.top());    spline &arr = *startedSplines.top();    if (arr.size()>4){        for (int i = 3; i < arr.size(); i++)        {            draw_spline_part(arr[i-3].x, arr[i-3].y, arr[i-2].x, arr[i-2].y, arr[i-1].x, arr[i-1].y, arr[i].x, arr[i].y, arr[i-2].col, arr[i-1].col, arr[i-2].al, arr[i-1].al);        }   }    glEnd();    glPopAttrib();    glColor4ubv(enigma::currentcolor);    delete &arr;    startedSplines.pop();    startedSplinesMode.pop();}`This code works, and nesting works too. Thou how did you thought of overwriting vectors? I can't find a way to make vectors start writing from 0 again without clearing the vector list. But now it is destroyed with pop() so I see no reason to clear it at all.
 Logged
luiscubal
 Reply #14 Posted on: December 04, 2010, 02:16:33 PM

Joined: Jun 2009
Posts: 452

Vector push_back worst case only happens when size()==capacity().
I think any decent vector implementation automatically reserves several elements ahead when push_back needs to expand. So I doubt worst case is the most common situation.
Either way, using reserve() could greatly speed things up.

EDIT: Also, since you are only using push, pop and iterating through the vector, a std::list-based implementation might be worth investigating if you are so concerned about temporal complexity.
 « Last Edit: December 04, 2010, 02:19:19 PM by luiscubal » Logged
 Pages: 1 2 »