Szukam dobrej biblioteki C++, aby dać mi funkcje do rozwiązania dla dużych splajnów sześciennych (rzędu 1000 punktów), czy ktoś je zna?Czy istnieją dobre biblioteki do rozwiązywania splajnów sześciennych w C++?
Odpowiedz
Spróbuj sześciennego B-Spline Biblioteka:
i ALGLIB:
Drugi link był prawie tym, czego szukałem ... z wyjątkiem tego, że nie mogę znaleźć żadnej dokumentacji na tej stronie lub w pobrany plik ... – Faken
Większość dokumentacji jest zindeksowana tutaj: http://www.alglib.net/sitemap.php - Nie wierzę, że istnieje jakakolwiek, która może zostać pobrana (jest to od jakiegoś czasu planowane, nie myśl, że to już się stało). – ars
Wydaje się, że ALGLIB ma pewne dziwne ograniczenia: [Nie obsługuje interpolacji 3D] (http://forum.alglib.net/viewtopic.php?f=2&t=137); wymusza okresowe splajny; [Wartości funkcji muszą leżeć na zwykłej siatce] (http://forum.alglib.net/viewtopic.php?f=2&t=137). – Jeff
przyjrzeć David Eberly'ego GeometricTools.com . Właśnie zaczynam, ale kod i dokument są jak dotąd wyjątkowej jakości.
(Ma również książki: narzędzia geometryczne do grafiki komputerowej, projektowanie silników gier 3D.)
Napisz własne. Oto spline()
funkcja napisałem na podstawie doskonałej wiki algorithm:
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef vector<double> vec;
struct SplineSet{
double a;
double b;
double c;
double d;
double x;
};
vector<SplineSet> spline(vec &x, vec &y)
{
int n = x.size()-1;
vec a;
a.insert(a.begin(), y.begin(), y.end());
vec b(n);
vec d(n);
vec h;
for(int i = 0; i < n; ++i)
h.push_back(x[i+1]-x[i]);
vec alpha;
for(int i = 0; i < n; ++i)
alpha.push_back(3*(a[i+1]-a[i])/h[i] - 3*(a[i]-a[i-1])/h[i-1] );
vec c(n+1);
vec l(n+1);
vec mu(n+1);
vec z(n+1);
l[0] = 1;
mu[0] = 0;
z[0] = 0;
for(int i = 1; i < n; ++i)
{
l[i] = 2 *(x[i+1]-x[i-1])-h[i-1]*mu[i-1];
mu[i] = h[i]/l[i];
z[i] = (alpha[i]-h[i-1]*z[i-1])/l[i];
}
l[n] = 1;
z[n] = 0;
c[n] = 0;
for(int j = n-1; j >= 0; --j)
{
c[j] = z [j] - mu[j] * c[j+1];
b[j] = (a[j+1]-a[j])/h[j]-h[j]*(c[j+1]+2*c[j])/3;
d[j] = (c[j+1]-c[j])/3/h[j];
}
vector<SplineSet> output_set(n);
for(int i = 0; i < n; ++i)
{
output_set[i].a = a[i];
output_set[i].b = b[i];
output_set[i].c = c[i];
output_set[i].d = d[i];
output_set[i].x = x[i];
}
return output_set;
}
int main()
{
vec x(11);
vec y(11);
for(int i = 0; i < x.size(); ++i)
{
x[i] = i;
y[i] = sin(i);
}
vector<SplineSet> cs = spline(x, y);
for(int i = 0; i < cs.size(); ++i)
cout << cs[i].d << "\t" << cs[i].c << "\t" << cs[i].b << "\t" << cs[i].a << endl;
}
'for (int i = 0; ...', a następnie uzyskujesz dostęp do 'a [i-1]' i 'h [i-1]' – helium
Dziękuję za ten kod jest bardzo użyteczny Przeprojektowany Brakujący kod do rysowania krzywych splajnu i do sprawdzania błędów Dodałem to i zapakowałem wszystko na lekcje https://github.com/JamesBremner/raven-cSpline Pozwol mi wiedzieć, czy chcesz zmienić swoją nazwę użytkownika (np. prawdziwe imię) – ravenspoint
miałem napisać spline rutynowych dla „podmiot”, który był następujący ścieżkę (seria powiązanych ze sobą GPS) w grze pracuję nad.
Utworzono klasę podstawową do obsługi "SplineInterface" i utworzonych dwóch klas pochodnych, jedną opartą na klasycznej technice spline (np. Sedgewick/Algorithms), a drugą opartą na Splajbach Beziera.
Oto kod. Jest to pojedynczy plik nagłówka, który zawiera wszystkie klasy splining:
#ifndef __SplineCommon__
#define __SplineCommon__
#include "CommonSTL.h"
#include "CommonProject.h"
#include "MathUtilities.h"
/* A Spline base class. */
class SplineBase
{
private:
vector<Vec2> _points;
bool _elimColinearPoints;
protected:
protected:
/* OVERRIDE THESE FUNCTIONS */
virtual void ResetDerived() = 0;
enum
{
NOM_SIZE = 32,
};
public:
SplineBase()
{
_points.reserve(NOM_SIZE);
_elimColinearPoints = true;
}
const vector<Vec2>& GetPoints() { return _points; }
bool GetElimColinearPoints() { return _elimColinearPoints; }
void SetElimColinearPoints(bool elim) { _elimColinearPoints = elim; }
/* OVERRIDE THESE FUNCTIONS */
virtual Vec2 Eval(int seg, double t) = 0;
virtual bool ComputeSpline() = 0;
virtual void DumpDerived() {}
/* Clear out all the data.
*/
void Reset()
{
_points.clear();
ResetDerived();
}
void AddPoint(const Vec2& pt)
{
// If this new point is colinear with the two previous points,
// pop off the last point and add this one instead.
if(_elimColinearPoints && _points.size() > 2)
{
int N = _points.size()-1;
Vec2 p0 = _points[N-1] - _points[N-2];
Vec2 p1 = _points[N] - _points[N-1];
Vec2 p2 = pt - _points[N];
// We test for colinearity by comparing the slopes
// of the two lines. If the slopes are the same,
// we assume colinearity.
float32 delta = (p2.y-p1.y)*(p1.x-p0.x)-(p1.y-p0.y)*(p2.x-p1.x);
if(MathUtilities::IsNearZero(delta))
{
_points.pop_back();
}
}
_points.push_back(pt);
}
void Dump(int segments = 5)
{
assert(segments > 1);
cout << "Original Points (" << _points.size() << ")" << endl;
cout << "-----------------------------" << endl;
for(int idx = 0; idx < _points.size(); ++idx)
{
cout << "[" << idx << "]" << " " << _points[idx] << endl;
}
cout << "-----------------------------" << endl;
DumpDerived();
cout << "-----------------------------" << endl;
cout << "Evaluating Spline at " << segments << " points." << endl;
for(int idx = 0; idx < _points.size()-1; idx++)
{
cout << "---------- " << "From " << _points[idx] << " to " << _points[idx+1] << "." << endl;
for(int tIdx = 0; tIdx < segments+1; ++tIdx)
{
double t = tIdx*1.0/segments;
cout << "[" << tIdx << "]" << " ";
cout << "[" << t*100 << "%]" << " ";
cout << " --> " << Eval(idx,t);
cout << endl;
}
}
}
};
class ClassicSpline : public SplineBase
{
private:
/* The system of linear equations found by solving
* for the 3 order spline polynomial is given by:
* A*x = b. The "x" is represented by _xCol and the
* "b" is represented by _bCol in the code.
*
* The "A" is formulated with diagonal elements (_diagElems) and
* symmetric off-diagonal elements (_offDiagElemns). The
* general structure (for six points) looks like:
*
*
* | d1 u1 0 0 0 | | p1 | | w1 |
* | u1 d2 u2 0 0 | | p2 | | w2 |
* | 0 u2 d3 u3 0 | * | p3 | = | w3 |
* | 0 0 u3 d4 u4 | | p4 | | w4 |
* | 0 0 0 u4 d5 | | p5 | | w5 |
*
*
* The general derivation for this can be found
* in Robert Sedgewick's "Algorithms in C++".
*
*/
vector<double> _xCol;
vector<double> _bCol;
vector<double> _diagElems;
vector<double> _offDiagElems;
public:
ClassicSpline()
{
_xCol.reserve(NOM_SIZE);
_bCol.reserve(NOM_SIZE);
_diagElems.reserve(NOM_SIZE);
_offDiagElems.reserve(NOM_SIZE);
}
/* Evaluate the spline for the ith segment
* for parameter. The value of parameter t must
* be between 0 and 1.
*/
inline virtual Vec2 Eval(int seg, double t)
{
const vector<Vec2>& points = GetPoints();
assert(t >= 0);
assert(t <= 1.0);
assert(seg >= 0);
assert(seg < (points.size()-1));
const double ONE_OVER_SIX = 1.0/6.0;
double oneMinust = 1.0 - t;
double t3Minust = t*t*t-t;
double oneMinust3minust = oneMinust*oneMinust*oneMinust-oneMinust;
double deltaX = points[seg+1].x - points[seg].x;
double yValue = t * points[seg + 1].y +
oneMinust*points[seg].y +
ONE_OVER_SIX*deltaX*deltaX*(t3Minust*_xCol[seg+1] - oneMinust3minust*_xCol[seg]);
double xValue = t*(points[seg+1].x-points[seg].x) + points[seg].x;
return Vec2(xValue,yValue);
}
/* Clear out all the data.
*/
virtual void ResetDerived()
{
_diagElems.clear();
_bCol.clear();
_xCol.clear();
_offDiagElems.clear();
}
virtual bool ComputeSpline()
{
const vector<Vec2>& p = GetPoints();
_bCol.resize(p.size());
_xCol.resize(p.size());
_diagElems.resize(p.size());
for(int idx = 1; idx < p.size(); ++idx)
{
_diagElems[idx] = 2*(p[idx+1].x-p[idx-1].x);
}
for(int idx = 0; idx < p.size(); ++idx)
{
_offDiagElems[idx] = p[idx+1].x - p[idx].x;
}
for(int idx = 1; idx < p.size(); ++idx)
{
_bCol[idx] = 6.0*((p[idx+1].y-p[idx].y)/_offDiagElems[idx] -
(p[idx].y-p[idx-1].y)/_offDiagElems[idx-1]);
}
_xCol[0] = 0.0;
_xCol[p.size()-1] = 0.0;
for(int idx = 1; idx < p.size()-1; ++idx)
{
_bCol[idx+1] = _bCol[idx+1] - _bCol[idx]*_offDiagElems[idx]/_diagElems[idx];
_diagElems[idx+1] = _diagElems[idx+1] - _offDiagElems[idx]*_offDiagElems[idx]/_diagElems[idx];
}
for(int idx = (int)p.size()-2; idx > 0; --idx)
{
_xCol[idx] = (_bCol[idx] - _offDiagElems[idx]*_xCol[idx+1])/_diagElems[idx];
}
return true;
}
};
/* Bezier Spline Implementation
* Based on this article:
* http://www.particleincell.com/blog/2012/bezier-splines/
*/
class BezierSpine : public SplineBase
{
private:
vector<Vec2> _p1Points;
vector<Vec2> _p2Points;
public:
BezierSpine()
{
_p1Points.reserve(NOM_SIZE);
_p2Points.reserve(NOM_SIZE);
}
/* Evaluate the spline for the ith segment
* for parameter. The value of parameter t must
* be between 0 and 1.
*/
inline virtual Vec2 Eval(int seg, double t)
{
assert(seg < _p1Points.size());
assert(seg < _p2Points.size());
double omt = 1.0 - t;
Vec2 p0 = GetPoints()[seg];
Vec2 p1 = _p1Points[seg];
Vec2 p2 = _p2Points[seg];
Vec2 p3 = GetPoints()[seg+1];
double xVal = omt*omt*omt*p0.x + 3*omt*omt*t*p1.x +3*omt*t*t*p2.x+t*t*t*p3.x;
double yVal = omt*omt*omt*p0.y + 3*omt*omt*t*p1.y +3*omt*t*t*p2.y+t*t*t*p3.y;
return Vec2(xVal,yVal);
}
/* Clear out all the data.
*/
virtual void ResetDerived()
{
_p1Points.clear();
_p2Points.clear();
}
virtual bool ComputeSpline()
{
const vector<Vec2>& p = GetPoints();
int N = (int)p.size()-1;
_p1Points.resize(N);
_p2Points.resize(N);
if(N == 0)
return false;
if(N == 1)
{ // Only 2 points...just create a straight line.
// Constraint: 3*P1 = 2*P0 + P3
_p1Points[0] = (2.0/3.0*p[0] + 1.0/3.0*p[1]);
// Constraint: P2 = 2*P1 - P0
_p2Points[0] = 2.0*_p1Points[0] - p[0];
return true;
}
/*rhs vector*/
vector<Vec2> a(N);
vector<Vec2> b(N);
vector<Vec2> c(N);
vector<Vec2> r(N);
/*left most segment*/
a[0].x = 0;
b[0].x = 2;
c[0].x = 1;
r[0].x = p[0].x+2*p[1].x;
a[0].y = 0;
b[0].y = 2;
c[0].y = 1;
r[0].y = p[0].y+2*p[1].y;
/*internal segments*/
for (int i = 1; i < N - 1; i++)
{
a[i].x=1;
b[i].x=4;
c[i].x=1;
r[i].x = 4 * p[i].x + 2 * p[i+1].x;
a[i].y=1;
b[i].y=4;
c[i].y=1;
r[i].y = 4 * p[i].y + 2 * p[i+1].y;
}
/*right segment*/
a[N-1].x = 2;
b[N-1].x = 7;
c[N-1].x = 0;
r[N-1].x = 8*p[N-1].x+p[N].x;
a[N-1].y = 2;
b[N-1].y = 7;
c[N-1].y = 0;
r[N-1].y = 8*p[N-1].y+p[N].y;
/*solves Ax=b with the Thomas algorithm (from Wikipedia)*/
for (int i = 1; i < N; i++)
{
double m;
m = a[i].x/b[i-1].x;
b[i].x = b[i].x - m * c[i - 1].x;
r[i].x = r[i].x - m * r[i-1].x;
m = a[i].y/b[i-1].y;
b[i].y = b[i].y - m * c[i - 1].y;
r[i].y = r[i].y - m * r[i-1].y;
}
_p1Points[N-1].x = r[N-1].x/b[N-1].x;
_p1Points[N-1].y = r[N-1].y/b[N-1].y;
for (int i = N - 2; i >= 0; --i)
{
_p1Points[i].x = (r[i].x - c[i].x * _p1Points[i+1].x)/b[i].x;
_p1Points[i].y = (r[i].y - c[i].y * _p1Points[i+1].y)/b[i].y;
}
/*we have p1, now compute p2*/
for (int i=0;i<N-1;i++)
{
_p2Points[i].x=2*p[i+1].x-_p1Points[i+1].x;
_p2Points[i].y=2*p[i+1].y-_p1Points[i+1].y;
}
_p2Points[N-1].x = 0.5 * (p[N].x+_p1Points[N-1].x);
_p2Points[N-1].y = 0.5 * (p[N].y+_p1Points[N-1].y);
return true;
}
virtual void DumpDerived()
{
cout << " Control Points " << endl;
for(int idx = 0; idx < _p1Points.size(); idx++)
{
cout << "[" << idx << "] ";
cout << "P1: " << _p1Points[idx];
cout << " ";
cout << "P2: " << _p2Points[idx];
cout << endl;
}
}
};
#endif /* defined(__SplineCommon__) */
Kilka uwag
- Klasyczny spline padnie, jeśli dasz mu pionowy zestaw punktów. Właśnie dlatego stworzyłem Beziera ... Mam wiele pionowych linii/ścieżek do naśladowania. Można go zmodyfikować tak, by dawał tylko linię prostą.
- Klasa podstawowa ma opcję usuwania punktów współliniowych po dodaniu ich. Wykorzystuje to proste porównanie nachylenia dwóch linii do obliczenia , jeśli są one w tej samej linii. Nie musisz tego robić, ale dla długich ścieżek, które są liniami prostymi, zmniejsza się liczba cykli. Gdy wykonujesz wiele detekcji ścieżki na wykresie z odstępem regularnym, masz tendencję do otrzymywania szeregu ciągłych segmentów .
Oto przykład użycia tej Beziera Spline:
/* Smooth the points on the path so that turns look
* more natural. We'll only smooth the first few
* points. Most of the time, the full path will not
* be executed anyway...why waste cycles.
*/
void SmoothPath(vector<Vec2>& path, int32 divisions)
{
const int SMOOTH_POINTS = 6;
BezierSpine spline;
if(path.size() < 2)
return;
// Cache off the first point. If the first point is removed,
// the we occasionally run into problems if the collision detection
// says the first node is occupied but the splined point is too
// close, so the FSM "spins" trying to find a sensor cell that is
// not occupied.
// Vec2 firstPoint = path.back();
// path.pop_back();
// Grab the points.
for(int idx = 0; idx < SMOOTH_POINTS && path.size() > 0; idx++)
{
spline.AddPoint(path.back());
path.pop_back();
}
// Smooth them.
spline.ComputeSpline();
// Push them back in.
for(int idx = spline.GetPoints().size()-2; idx >= 0; --idx)
{
for(int division = divisions-1; division >= 0; --division)
{
double t = division*1.0/divisions;
path.push_back(spline.Eval(idx, t));
}
}
// Push back in the original first point.
// path.push_back(firstPoint);
}
Uwagi
- Chociaż cała ścieżka może być wygładzone, w tym zastosowaniu, ponieważ ścieżka zmieniała co jakiś czas lepiej było tylko wygładzić pierwsze punkty, a następnie połączyć je.
- Punkty są ładowane w kolejności "wstecznej" do wektora ścieżki. Ten może, ale nie musi, zapisać cykle (od tej pory spałem).
Ten kod jest częścią znacznie większej bazy kodu, but you can download it all on github i see a blog entry about it here.
Dziękuję za ten kod, szukałem tego, który działa na dowolnym zestawie punktów 2D (nie tylko funkcji o wartościach rzeczywistych) przez wiele godzin. właśnie zrobiłem mój dzień. – Arshia001
- 1. Czy istnieją dobre biblioteki kontrolne WPF?
- 2. Czy istnieją jeszcze dobre biblioteki innych firm oparte na openCL?
- 3. Czy istnieją dobre narzędzia do inżynierii odwrotnej C#?
- 4. Jakie są dobre biblioteki do rozwiązywania układów równań nieliniowych w C++?
- 5. Czy istnieją autonomiczne biblioteki do Firefox Sync?
- 6. Czy istnieją dojrzałe frameworki/biblioteki P2P w języku C#?
- 7. Czy istnieją biblioteki Hierarchical Temporal Memory?
- 8. Czy istnieją proste, bezpłatne biblioteki śledzenia C++ ray?
- 9. Czy istnieją jakieś dobre tutoriale UIScrollView w sieci?
- 10. Dobre authorize.net Biblioteki PHP
- 11. Czy poszarpane tablice istnieją w C/C++?
- 12. program do rozwiązywania równania w C#
- 13. Czy istnieją jakieś biblioteki/frameworki dla SCons?
- 14. Jakieś dobre biblioteki do rysowania postscriptowego?
- 15. Czy istnieją dobre opcje wypalania witryny Django jako pliki statyczne?
- 16. Czy zasoby biblioteki C są podobne do biblioteki Boost C++?
- 17. Czy istnieją dobre tutoriale dla początkujących dotyczące wątków w oknach? C++
- 18. Czy istnieją jakieś dobre, darmowe/tanie sterowanie siatką Delphi?
- 19. Czy istnieją jakieś dobre/interesujące analogi do wyrażeń regularnych w 2d?
- 20. Czy są dostępne dobre biblioteki funkcji do kolekcjonowania w Javie, takie jak
- 21. Czy istnieją biblioteki programu Square Root w wersji BigDecimal?
- 22. Czy istnieją biblioteki narzędzi dla przekleństw z powiązaniami w Pythonie?
- 23. Czy istnieją tak dobre kompilatory C, że fortran staje się językiem nadmiarowym?
- 24. C++ ostrzeżenie rozwiązywania istream :: tellg
- 25. Czy istnieją biblioteki id, które udostępniają funkcję tablic asocjacyjnych?
- 26. Jakieś dobre biblioteki C lub C++ do obsługi dużych chmur punktów?
- 27. Czy istnieją biblioteki graficzne Dart, które szeroko wykorzystują akcelerację sprzętową?
- 28. Program do rozwiązywania równań w zespole
- 29. Czy istnieją jakieś kryptograficznie bezpieczne biblioteki PRNG dla Delphi?
- 30. Czy istnieją inne dobre alternatywy dla zc.buildout i/lub virtualenv do instalowania zależności innych niż python?
Biblioteka ta ma O (n) oraz pamięci do implementacji karane wypustów sześciennych z automatycznego wyrównywania z wykorzystaniem krzyżowego lub skuteczny stopień swobody typu smooth.splines R,(). Zobacz skel__Cspplines.h i skel__TestCspplines.h: https://bitbucket.org/aperezrathke/skel – aprstar