#157932 - DiscoStew - Mon Jun 02, 2008 3:47 am
Currently for my stuff, I'm using Bezier curves to handle my pathing curves from one point to another. However, I'm noticing that unless I do a lot of tweaking with the points, the increments when going through the curve are not static. What I'd like is to have a curve that with however many points it is split up by, the distance between each increment is the same, rather than having it speed up and down throughout the curve.
EDIT:
Either that, or perhaps a technique or method that makes it easier for dealing with Bezier curves in this manner. thx.
_________________
DS - It's all about DiscoStew
#157947 - silent_code - Mon Jun 02, 2008 10:30 am
i don't know how useful this is to you and it's been some years i have dealt with it, but i remeber hermite spline curves to be quite useful.
happy coding! :^)
_________________
July 5th 08: "Volumetric Shadow Demo" 1.6.0 (final) source released
June 5th 08: "Zombie NDS" WIP released!
It's all on my page, just click WWW below.
#157948 - kusma - Mon Jun 02, 2008 10:38 am
In order to move at constant speed in a spline, you need to be able to calculate the length of each curve-segment. Unfortunately, it seems that there's no way of doing this analytically for Bezier-curves. If you're willing to spend some more processing-time, you could approximate the curve-segments with lines and calculate the length from them. Another option is to use another cuve-type, like silent_code suggested. There seems to be an analytical solution for hermite-curves (and thus it's variants, like catmul-rom and tcb-splines).
#157958 - RickA - Mon Jun 02, 2008 2:08 pm
Another option that someone found (I can search for the sources if you like) which seemed pretty smart, is to generate another bezier spline offline which indicates the dt you need on the main spline to get a constant rate of movement. This apparently only requires two extra points per node, and then at runtime you do two bezier spline interpolations, first on the speed one to get the dt to use on the position (second) one.
#157959 - kusma - Mon Jun 02, 2008 2:13 pm
| RickA wrote: |
| Another option that someone found (I can search for the sources if you like) which seemed pretty smart, is to generate another bezier spline offline which indicates the dt you need on the main spline to get a constant rate of movement. This apparently only requires two extra points per node, and then at runtime you do two bezier spline interpolations, first on the speed one to get the dt to use on the position (second) one. |
Keep in mind that he stated that the curve isn't static, so that speed-curve would have to be regenerated on the fly.
#161056 - mathHeadInClouds - Sun Jul 27, 2008 7:34 am
Here is an implementation of kusma's first suggestion. The code posted below is ready to compile and works, I tested it.
It displays a cubic Bezier curve on the lower screen.
In each point that is drawn, you calculate the "speed" at that point as the length of the vector of the partial derivatives (the tangent vector).
In order for all the next points to be drawn to be always the same distance from the respective previous points, the increment in the parameter
must be inversely proportional to that speed. deltaT = desiredDistToNextPixel / speed does that.
If desiredDistToNextPixel is small, the drawn curve is dense and the approximation is very good.
| Code: |
#include <nds.h>
#include <stdlib.h>
#include <math.h>
double getFirst(int index, double** points){
return points[index][0];
}
double getSecond(int index, double** points){
return points[index][1];
}
double* bAux3(double (*at)(int, double**), double** pts){
double* result = malloc(4*sizeof(double));
result[0] = at(0, pts);
result[1] = -3*at(0, pts) + 3*at(1, pts);
result[2] = 3*at(0, pts) - 6*at(1, pts) + 3*at(2, pts);
result[3] = -at(0, pts) + 3* at(1, pts) - 3*at(2, pts) + at(3, pts);
return result;
}
double** bezier3(double** points){
double** result = malloc(2*sizeof(double*));
result[0] = bAux3(getFirst, points);
result[1] = bAux3(getSecond, points);
return result;
}
double evalPoly( double* poly, int len, double val){
double result = 0;
while (len--) result = result*val + (*(poly+len));
return result;
}
double* paraToPoint(double** curve, int lenCurve, double para){
double* result = malloc(2*sizeof(double));
result[0] = evalPoly(curve[0], lenCurve, para);
result[1] = evalPoly(curve[1], lenCurve, para);
return result;
}
double* deriv( double* poly, int len){
double* result = malloc(sizeof(double)*(len-1));
int exponent;
for ( exponent = 1; exponent < len; exponent++ ){
result[exponent-1] = exponent * poly[exponent];
}
return result;
}
double approximateLengthOf2DVector(double x, double y){
// returns a usable (worst case relative error < 6.5%) approximation of the vector length sqrt(x^2 + y^2), without using the sqrt function
double absx = fabs(x);
double absy = fabs(y);
if ( absx > absy ) return absx + 0.3284271247461903 * absy;
return absy + 0.3284271247461903 * absx;
// 0.3284271247461903 = -2.5 + 2*sqrt(2) solution of minimizing a suitable squared error integral
}
void setPixelForParam( double** curve, int lenCurve, double t, int color){
double* where = paraToPoint(curve, lenCurve, t);
int x = ((int)(0.5 + where[0]));
int y = ((int)(0.5 + where[1]));
VRAM_A[256*y + x] = color;
}
void showSomeBezierCurve(){
int red = RGB15(31, 0, 0);
int degree = 3;
int len = degree + 1;
double p0[2] = {50., 10.}; // start
double p1[2] = {240., 190.}; // control 1
double p2[2] = {10., 190.}; // control 2
double p3[2] = {200., 10.}; // end
double** pts = malloc(len * sizeof(double*));
pts[0] = p0; pts[1] = p1; pts[2] = p2; pts[3] = p3;
double** curve = bezier3(pts);
double* x = curve[0]; // array of coefficients of the polynomial for the x coordinate (highest one first)
double* y = curve[1]; // ditto for y
double* dx = deriv(x, len); // array of coefficients of the derivative with respect to x
double* dy = deriv(y, len); // ditto for y
double t = 0.; // parameter of the curve
double desiredDistToNextPixel = 1.; // to be tweaked
double maxDeltaT = 0.05; // to be tweaked
double tangentX, tangentY, speed, deltaT;
while ( t < 1. ){
setPixelForParam(curve, len, t, red);
tangentX = evalPoly(dx, degree, t);
tangentY = evalPoly(dy, degree, t);
speed = approximateLengthOf2DVector(tangentX, tangentY);
if ( desiredDistToNextPixel > maxDeltaT * speed ) {
deltaT = maxDeltaT;
} else {
deltaT = desiredDistToNextPixel / speed;
}
t += deltaT;
}
}
int main(void){
irqInit(); irqEnable(IRQ_VBLANK);
videoSetMode(MODE_FB0); vramSetBankA(VRAM_A_LCD);
lcdMainOnBottom();
consoleDemoInit();
showSomeBezierCurve();
while (1){
}
return 0;
}
|
And now, I have a question / request.
Please, someone modify my code, so that the bezier curve is displayed on both screens, not just the lower one.
Believe it or not, I don't know how to do that.
#161057 - eKid - Sun Jul 27, 2008 7:58 am
| mathHeadInClouds wrote: |
Please, someone modify my code, so that the bezier curve is displayed on both screens, not just the lower one.
Believe it or not, I don't know how to do that. |
| Code: |
int main(void){
irqInit();
irqEnable(IRQ_VBLANK);
videoSetMode(MODE_FB0);
vramSetBankA(VRAM_A_LCD);
lcdMainOnBottom();
// use mode3 to display 16bit bitmap
videoSetModeSub(MODE_3_2D|DISPLAY_BG3_ACTIVE);
// vram c to hold data
vramSetBankC(VRAM_C_SUB_BG);
// use bg3 to display bitmap
SUB_BG3_CR = BG_BMP16_256x256;
SUB_BG3_XDX = 256; // initialize bg3's matrix
SUB_BG3_XDY = 0;
SUB_BG3_YDX = 0;
SUB_BG3_YDY = 256;
// draw curve
showSomeBezierCurve();
// copy data to sub screen
int i;
for( i = 0; i < 256*192; i++ )
{
// copy data and set opacity bit
BG_GFX_SUB[i] = VRAM_A[i] | 0x8000;
}
while (1){
swiWaitForVBlank(); // idle cpu (lower power consumption)
}
return 0;
}
|
:)
#161063 - mathHeadInClouds - Sun Jul 27, 2008 2:00 pm
thank you so much eKid.
Sorry to hijack your thread, but I think you got a conclusive answer, DiscoStew.
(kusma is right in saying that "there's no way of doing this ["to calculate the length of each curve-segment"]
analytically for Bezier-curves.", meaning that a closed formula for the parameter values that you have to pick
in order to split the curve into segments of equal lengths does not exist.
That's why the next parameter value is calculated using the previous one in the code, rather than using
the non-existent wish-formula i -> ith parameter value).
Since the thread is already hijacked, I might as well ask another question building upon my previous one:
I want to display the string "Hello World" on the top screen.
I know have to add
#include <stdio.h>
on top, and then
iprintf("\x1b[0;0H Hello World");
somewhere later. Yet again, I don't know how to set up things at the beginning - the stuff with the banks and modes is strangely beyond my comprehension.
btw, upon request, i can post functions bezier4, bezier5, etc. for higher bezier curves, if anyone wants to know.
#161068 - silent_code - Sun Jul 27, 2008 8:27 pm
There is a libnds ansi_console example, which answers your question. :^)
_________________
July 5th 08: "Volumetric Shadow Demo" 1.6.0 (final) source released
June 5th 08: "Zombie NDS" WIP released!
It's all on my page, just click WWW below.
#161070 - mathHeadInClouds - Sun Jul 27, 2008 9:50 pm
| Quote: |
There is a libnds ansi_console example, which answers your question. :^)
|
I think I didn't put the question right: I wanted the text to appear IN ADDITION to the two bezier curves on the top and bottom screen, not ONLY text as in the ansi_console example.
I recognize that this is actually a newbie question, and that there is also a thread in the beginner forum ("Text over background" from sUPREz) with the same (or very similar) issue; eKid posted a link in response to that question ("bitmap_console"), but I cannot get that to compile.
#161073 - silent_code - Sun Jul 27, 2008 10:14 pm
Try VSD (open source) from my site. It has a paletted image and text on top of that on the sub screen. :^)
You basically need to set up the console to "skip" past the background image memory. Or set the background to be read from memory past the console... You do that by assigning the right character, tile and bitmap bases.
_________________
July 5th 08: "Volumetric Shadow Demo" 1.6.0 (final) source released
June 5th 08: "Zombie NDS" WIP released!
It's all on my page, just click WWW below.
#161347 - mathHeadInClouds - Fri Aug 01, 2008 9:27 pm
I'll paypal 5 Euros (that's about 8 dollars) to the first person to post code that displays the bezier curve on both screens (as the code here in this thread in my posting + eKids posting already does), and in addition, displays the text "Hello World" on the upper (sub) screen, using "printf" or "iprintf". The code should compile as-is on the newest edition of devkitpro.
Thank you for your time.
#161359 - silent_code - Fri Aug 01, 2008 10:34 pm
| mathHeadInClouds wrote: |
I'll paypal 5 Euros (that's about 8 dollars) to the first person to post code that displays the bezier curve on both screens (as the code here in this thread in my posting + eKids posting already does), and in addition, displays the text "Hello World" on the upper (sub) screen, using "printf" or "iprintf". The code should compile as-is on the newest edition of devkitpro.
Thank you for your time. |
I guess that means you owe me 5? now. :^D
I don't want the money, so please donate it to devkitPro (I kindly request you add something like "With best regards from silent_code / www.robs-basement.de", when possible) and make sure I get notified about the arrival of the donation.
I can explain how it works (obviously), just ask when anything's unclear.
Note: Some (double *) and (double **) castshad to added, as the sources above weren't compiling.
I am using the current releases of devkitARM (R23b) and libnds (20071023).
EDIT 1: Some comments have been added / extended.
EDIT 2: Hopefully you don't mind the minor formating adjustments I made. (I prefer "double *pdfoo;" over "double* pdfoo;", because it's closer to the syntax. Example: "double dada, *pdada, dudu;")
EDIT 3: I hope you do keep your promise. ;^)
| Code: |
#include <nds.h>
#include <stdio.h> // Added by silent_code for *printf()
#include <stdlib.h>
#include <math.h>
double getFirst(int index, double **points)
{
return points[index][0];
}
double getSecond(int index, double **points)
{
return points[index][1];
}
double *bAux3(double(*at)(int, double **), double **pts)
{
double *result = (double *)malloc(4 * sizeof(double));
result[0] = at(0, pts);
result[1] = -3 * at(0, pts) + 3 * at(1, pts);
result[2] = 3 * at(0, pts) - 6 * at(1, pts) + 3 * at(2, pts);
result[3] = -at(0, pts) + 3 * at(1, pts) - 3 * at(2, pts) + at(3, pts);
return result;
}
double **bezier3(double **points)
{
double **result = (double **)malloc(2 * sizeof(double *));
result[0] = bAux3(getFirst, points);
result[1] = bAux3(getSecond, points);
return result;
}
double evalPoly(double *poly, int len, double val)
{
double result = 0;
while(len--) result = result * val + (*(poly + len));
return result;
}
double *paraToPoint(double **curve, int lenCurve, double para)
{
double *result = (double *)malloc(2 * sizeof(double));
result[0] = evalPoly(curve[0], lenCurve, para);
result[1] = evalPoly(curve[1], lenCurve, para);
return result;
}
double *deriv(double *poly, int len)
{
double *result = (double *)malloc(sizeof(double) * (len - 1));
int exponent;
for(exponent = 1; exponent < len; exponent++)
{
result[exponent - 1] = exponent * poly[exponent];
}
return result;
}
double approximateLengthOf2DVector(double x, double y)
{
// returns a usable (worst case relative error < 6.5%) approximation of the vector length sqrt(x^2 + y^2), without using the sqrt function
double absx = fabs(x);
double absy = fabs(y);
if(absx > absy) return absx + 0.3284271247461903 * absy;
return absy + 0.3284271247461903 * absx;
// 0.3284271247461903 = -2.5 + 2*sqrt(2) solution of minimizing a suitable squared error integral
}
void setPixelForParam(double **curve, int lenCurve, double t, int color)
{
double *where = paraToPoint(curve, lenCurve, t);
int x = ((int)(0.5 + where[0]));
int y = ((int)(0.5 + where[1]));
VRAM_A[256 * y + x] = color;
}
void showSomeBezierCurve()
{
int red = RGB15(31, 0, 0);
int degree = 3;
int len = degree + 1;
double p0[2] = {50., 10.}; // start
double p1[2] = {240., 190.}; // control 1
double p2[2] = {10., 190.}; // control 2
double p3[2] = {200., 10.}; // end
double **pts = (double **)malloc(len * sizeof(double *));
pts[0] = p0;
pts[1] = p1;
pts[2] = p2;
pts[3] = p3;
double **curve = bezier3(pts);
double *x = curve[0]; // array of coefficients of the polynomial for the x coordinate (highest one first)
double *y = curve[1]; // ditto for y
double *dx = deriv(x, len); // array of coefficients of the derivative with respect to x
double *dy = deriv(y, len); // ditto for y
double t = 0.; // parameter of the curve
double desiredDistToNextPixel = 1.; // to be tweaked
double maxDeltaT = 0.05; // to be tweaked
double tangentX, tangentY, speed, deltaT;
while(t < 1.)
{
setPixelForParam(curve, len, t, red);
tangentX = evalPoly(dx, degree, t);
tangentY = evalPoly(dy, degree, t);
speed = approximateLengthOf2DVector(tangentX, tangentY);
if(desiredDistToNextPixel > maxDeltaT * speed)
{
deltaT = maxDeltaT;
}
else
{
deltaT = desiredDistToNextPixel / speed;
}
t += deltaT;
}
}
//int main(void){
// irqInit();
// irqEnable(IRQ_VBLANK);
// videoSetMode(MODE_FB0);
// vramSetBankA(VRAM_A_LCD);
// lcdMainOnBottom();
// consoleDemoInit();
// showSomeBezierCurve();
// while(1){
// }
// return 0;
//}
/*
* Modified main() by silent_code
*/
int main(void)
{
lcdMainOnBottom();
irqInit();
irqEnable(IRQ_VBLANK);
// VRAM bank A will hold the source 16bit bitmap for both screens
vramSetBankA(VRAM_A_LCD);
// VRAM bank B will hold a 16bit background bitmap for the main screen
// no offset needed
vramSetBankB(VRAM_B_MAIN_BG_0x06000000);
// VRAM bank C will hold all console data
// as well as a 16bit background bitmap for the sub screen
// no offset needed
vramSetBankC(VRAM_C_SUB_BG_0x06200000);
// Use mode 3 for the main screen to display a 16bit bitmap (BG3)
videoSetMode(MODE_3_2D | DISPLAY_BG3_ACTIVE);
// Set BG3 to display a 16bit bitmap without offset
BG3_CR = BG_BMP16_256x256;
// Initialize BG3's matrix
BG3_XDX = 256;
BG3_XDY = 0;
BG3_YDX = 0;
BG3_YDY = 256;
// Use mode 3 for the sub screen to display a 16bit bitmap (BG3)
// and the console text (BG0)
videoSetModeSub(MODE_3_2D | DISPLAY_BG3_ACTIVE | DISPLAY_BG0_ACTIVE);
// Set the font color
BG_PALETTE_SUB[255] = RGB15(31, 31, 31);
// Use BG3 to display a 16bit bitmap with a 2 * 16kB offset (the BMP base)
// Note: The offset is needed to skip past the console data, which comes first
SUB_BG3_CR = BG_BMP16_256x256 | BG_BMP_BASE(2);
// Initialize BG3's matrix
SUB_BG3_XDX = 256;
SUB_BG3_XDY = 0;
SUB_BG3_YDX = 0;
SUB_BG3_YDY = 256;
// Set BG0 to display an ordinary text layer,
// with the map at the first map memory block (generating a 14kB "hole")
// (map block size 2kB, must be within first 64kB)
// and the tile set at the second character memory block (which it wholly uses)
// (character block size 16kB, must be within first 256kB)
SUB_BG0_CR = BG_32x32 | BG_256_COLOR | BG_MAP_BASE(0) | BG_TILE_BASE(1);
// Initialize the console according to BG0 (map and tile set)
// with the default font
consoleInitDefault((uint16 *)SCREEN_BASE_BLOCK_SUB(0), (uint16 *)CHAR_BASE_BLOCK_SUB(1), 8);
iprintf("Hello World!\n");
// Draw a curve to VRAM bank A
// Note: Should normally be done during VBlank due to possible flickering.
showSomeBezierCurve();
// Copy the image to the screen bitmaps
// Note: Should also be done during VBlank.
int i;
uint32 pixels;
for(i = 0; i < (256 * 192 / 2); i++)
{
// Read two pixels at a time and set the opacity bits
pixels = ((uint32 *)VRAM_A)[i] | 0x80008000;
// Write two pixels at a time
((uint32 *)BG_BMP_RAM_SUB(2))[i] = pixels;
((uint32 *)BG_BMP_RAM(0))[i] = pixels; // This is equivalent to using BG_GFX
}
while(true)
{
swiWaitForVBlank(); // idle cpu (lower power consumption)
}
return 0;
} |
_________________
July 5th 08: "Volumetric Shadow Demo" 1.6.0 (final) source released
June 5th 08: "Zombie NDS" WIP released!
It's all on my page, just click WWW below.
#161381 - mathHeadInClouds - Sat Aug 02, 2008 3:33 pm
Thank you, silent_code!
The code works like a charm!
A remark to all of you out there, who are planning to copy-past-modify the code in order to draw bezier curves: there's memory leaks all over the place (free isn't called), so you would have a crash due to lack of memory somewhere down the road. So if you're going to use it, put in the free-calls in the appropriate places.
#161402 - silent_code - Sat Aug 02, 2008 11:35 pm
<IGNORE THIS BS>
<OFFTOPIC>
In my experience (at least on the PC) that doesn't automatically mean you won't have any leaks... e.g. did anyone ever come along a delete call that didn't do its job?
Might as well be just my memory tracer, but I doubt it (EDIT: <BUZZ> WRONG!), as sometimes rearrangeing a few lines will result in no memory leak. And other (most of them) allocations / deallocations which are just 100% the same, will work fine. ???? (EDIT: Yes, sometimes I'm that stupid and jumping to conclusions! Damn it.)
</OFFTOPIC>
</IGNORE THIS BS>
Anyways, you're welcome! :^)
_________________
July 5th 08: "Volumetric Shadow Demo" 1.6.0 (final) source released
June 5th 08: "Zombie NDS" WIP released!
It's all on my page, just click WWW below.
Last edited by silent_code on Tue Aug 05, 2008 8:07 pm; edited 1 time in total
#161431 - kusma - Sun Aug 03, 2008 12:31 pm
| silent_code wrote: |
In my experience (at least on the PC) that doesn't automatically mean you won't have any leaks... e.g. did anyone ever come along a delete call that didn't do its job?
Might as well be just my memory tracer, but I doubt it, as sometimes rearrangeing a few lines will result in no memory leak. And other (most of them) allocations / deallocations which are just 100% the same, will work fine. ???? |
I'm not quite sure I get what you're saying... Every call to malloc() should be paired with a call to free() so the memory will be returned to the heap. On modern operating systems all memory belonging to the process is released to the system on process termination, but that doesn't prevent you from starving the system within your application. Would you mind elaborating a bit and possibly post some example code?
#161435 - silent_code - Sun Aug 03, 2008 1:34 pm
EDIT: Don't bother about this...
In order to avoid more offtopic posts, I've opened a new thread over here:
http://forum.gbadev.org/viewtopic.php?p=161434#161434
Thanks for participating! :^)
_________________
July 5th 08: "Volumetric Shadow Demo" 1.6.0 (final) source released
June 5th 08: "Zombie NDS" WIP released!
It's all on my page, just click WWW below.