ENIGMA Forums
Contributing to ENIGMA => Function Peer Review => Topic started by: TheExDeus on December 02, 2010, 09:36:53 AM

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).
Added antialiasing functions.
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: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.
Download: GMK and .h/.cpp files can be downloaded from attachments. Exe version of the example (just to check it out or if it doesn't work for you) can be downloaded here: http://www.hosta.net/u/harrikiri/curvesexample.zip (http://www.hosta.net/u/harrikiri/curvesexample.zip).
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:
.eobjs_$(MODE)/GScurves.o: GScurves.cpp OpenGLHeaders.h
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:
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:
double lerp(double x, double y, double a) { return x + ((yx)*a); }
Also, open mathnc.h and add the header:
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 antialiasing. 1Disabled. 2Enabled, fastest. 3Enabled, nicest. 4Enabled, don't care.
ToDo:
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).

They look nice, HaRRi. I'd recommend keeping your own array, though. Here is my suggestion:
#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.

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.

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?

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. :D 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.

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 backandforth sort of thing.

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.

I am having trouble with vectors and structs. This is how I ended up doing it:
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[i3].x, spline[i3].y, spline[i2].x, spline[i2].y, spline[i1].x, spline[i1].y, spline[i].x, spline[i].y, spline[i2].col, spline[i1].col, spline[i2].al, spline[i1].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.

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).

Question: Why do they all have the type int if you're just returning 0? In what case would they be nonzero? Lack of a graphics card? I mean, I can't think of anything.

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.

I actually had trouble making your sample code to run, so I ditched the list. I will try to make it work thou.
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. :D Mostly because I think in arrays, not vectors (which is kind of the same, but still).
Question: Why do they all have the type int if you're just returning 0? In what case would they be nonzero? 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.

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...)

So this is how the code looks like right now:
#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[i3].x, arr[i3].y, arr[i2].x, arr[i2].y, arr[i1].x, arr[i1].y, arr[i].x, arr[i].y, arr[i2].col, arr[i1].col, arr[i2].al, arr[i1].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.

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::listbased implementation might be worth investigating if you are so concerned about temporal complexity.

As far as I know* vectors are better for inserting at the end and iterating trough.** Lists are better for inserting and deleting in the middle (or anywhere). So in my case I think vectors could be better.
*And I know little, as 2 days ago I didn't know that in C++ vectors were arrays.
** http://www.gamedev.net/community/forums/topic.asp?topic_id=211458

I was addressing Josh's concern of O(N) push complexity.

Ou, ok. Thought that suggestion was pointed at me.
I released the current source. Added new functions and changed the _begin() spline functions to use stacks and vectors. The speed seems identical, but the memory usage could be down. Also now it allows nesting.
I added antialiasing function, which makes the splines look a lot better. Thou I have a decision on how to implement it. What I did for now is make curves totally independent from the rest of the system. So you can change color, alpha, aa, drawing mode etc. totally independent from other functions. And I am not sure if that is the best idea. For example, I could have aa code like this:void draw_set_antialiasing(bool enable, int qual)
{
if (enable==1){
glEnable(GL_LINE_SMOOTH);
glHint(GL_LINE_SMOOTH_HINT, qual);
}else{
glDisable(GL_LINE_SMOOTH);
}
}
But that will enable aa for every primitive (circles etc.). I ended up doing this:pr_curve_aa = enable;
pr_curve_aa_qual = qual;
With having this in every drawing function (which of course can slow down the function): if (pr_curve_aa==1){
glEnable(GL_LINE_SMOOTH);
glHint(GL_LINE_SMOOTH_HINT, pr_curve_aa_qual);
}else{
glDisable(GL_LINE_SMOOTH);
}
Of course it is needed only once per function call, and compared to all the trig going on just to draw thous splines and curves, I think this doesn't impact the speed at all. It just seems wrong..
And testing speed is extremely hard because FPS jumps like crazy. I think that number is updated several times too much. Maybe it should be updated once per second or once per half a second. Maybe its normal like this, but I never seen it jump like that in GM.

Why not let the GPU handle it and use transformation matrices? Or do they not work that way? I haven't gone too much into GL, so, I don't know how it's done.

HaRRi, I think if you're going to offer an AA function, it may as well be for all primitives. Let the user make the call to it before and after spline drawing, if they like.
Luis, using a list would increase RAM. It would save push_back for the duration of one frame, then one subtract each frame, but at the cost of another adddereference from there on. It doesn't really seem worth it...

There's also the option of using bezier_reserve() to set vector capacity if the extra performance is that much needed.
That said, it's probably not worth it.