如何实现二维几何的约束求解器？ [英] How to implement a constraint solver for 2-D geometry?
问题描述
我有一组金属滑动件，按照以下方式限制在x和y轴上：
我需要最大限度地增加由同一滑块约束的所有作品之间的水平距离以及滑块和滑块本身之间的垂直距离。如何解决这个问题？
任何建议和建议都可能导致解决这个问题，我们将不胜感激。
我首先看到了一些功能非常强大的图书馆，例如食火鸡和jsLPSolver，但我在理解核心算法以及如何检查约束的可行性以及如何排列可能的解决方案方面遇到了一些麻烦。
如何在JavaScript中实现一个用于2-D几何约束求解器的（简单）存根，用于解决上述问题？
编辑：
我有以下输入数据：
maxW = 300， maxH = 320
这些部分定义如下（不是强制性的，每个解决方案都被接受） p>
slidingPiece = [pX，pY，width，height，anchorPoint，loopDistance];
我会试着解释我的意思是最大化。
水平间距：
a0-b1，b1-b2，b2-b4，b4-b5和b5-maxX将是相同的，即最大X除以最大数量的垂直相交片+ 1（5）。
b1-b3和b3-b5将由可用剩余空间决定。
垂直间距：
b1-a3，a3-a4和a0-b5将是相同的。理想地，a0-b3，b3-b4，a2-b2，b4-a3和b2-a4也将是相同的值。最大化a1-b4和b3-a2与最大化b3-b4相同。这同样适用于a2-b2和b4-a3：距离b2-b4将成为最大负值。
所以，我需要最大化每个滑动件和他最靠近Y约束的上方或下方。
这个问题的二维几何表示显示水平间距取决于锚的垂直距离（由于锚定件的垂直相交），这这又取决于零件本身的水平位置。例如，想想b2稍微短一些。在这种情况下，b1和b2不再相交并且会变成相同的x值，即最大X除以4.在一些其他情况下，例如b2是在上述部分中要长得多 - 并且将穿过锚点a2，然后它将被间隔为a1。这就是原因，因为会有一组解决方案，一些是可行的，另一些则是不可行的，因为例如全局最大Y约束将被打破。
我会尝试类似于
<看看
class _slider 的来源以获取更多信息。 strong> 短划线表示固定滑块。银色是水平的，水色意味着垂直和黄色由鼠标选择。稍后可能会出现红色意味着某种错误/卡住或出于调试目的。对于力场解算器，我有时会将场强添加为红蓝色的比例，但不知道我是否会在这里实现它。
为了保持这个简单，我不会实现缩放/平移功能，因为您的尺寸非常方便直接渲染而不需要转换。
实施初始设置
$ b
滑块SYS;
int i0，i1，a0，a1，a2，a3，a4，b1，b2，b3，b4，b5;
sys.slider_beg（）; // ia，ib，x，y，a0，a1，b0，b1，_horizontal
i0 = sys.slider_add（-1，-1,25.0,25.0， - 5.0，405.0，0.0，0.0，0）;
a0 = sys.slider_add（i0，-1，0.0，0.0，0.0，400.0，0.0，0.0，1）;
a1 = sys.slider_add（i0，-1，0.0,100.0，0.0，400.0，0.0，0.0，1）;
a2 = sys.slider_add（i0，-1，0.0,200.0，0.0，400.0，0.0，0.0，1）;
a3 = sys.slider_add（i0，-1，0.0,300.0，0.0，400.0，0.0，0.0，1）;
a4 = sys.slider_add（i0，-1，0.0,400.0，0.0，400.0，0.0，0.0，1）;
b1 = sys.slider_add（a0，a2，20.0，0.0，0.0，125.0，125.0，250.0，0）;
b2 = sys.slider_add（a3，-1，40.0，0.0，-70.0，30.0，0.0，0.0，0）;
b3 = sys.slider_add（a1，-1，60.0，0.0，-70.0，30.0，0.0，0.0，0）;
b4 = sys.slider_add（a2，-1，80.0，0.0，-30.0，70.0，0.0，0.0，0）;
b5 = sys.slider_add（a3，a1,100.0，0.0，-125.0，0.0，-125.0，-250.0，0）;
i1 = sys.slider_add（-1，-1,425.0，25.0，-5.0，405.0，0.0，0.0，0）;
sys.slider_end（）;
其中 ia 为父索引， ib 是子索引（滑块类本身包含 ib 作为父项，但是这会让init感到困惑，因为您需要链接到尚不存在的项目，因此在 sys.add 函数中处理 ib 转换。 sys 是持有整个事物的类， sys.add 只需添加新滑块并返回从零开始计数的索引。 x，y 是父级的相对位置。为了减少编码量，此设置不得与限制。
请注意，对于水平滑块，滑块的顺序必须从左到右进行垂直和从上到下，以确保正确的约束功能。
只需简单的滑块移动即可进行调试和调整初始设置值。或处理卡住的案件。您需要处理鼠标事件，如果尚未编辑，请选择最近的滑块。如果鼠标按钮被按下，将选定的滑块移动到鼠标位置......
$ b
我简化了一下，所以我创建了一个谓词函数，该函数被调用指定的滑块，如果它或它的任何子/锚点与定义的约束发生冲突，则返回它。这更容易编码和调试，然后更新位置以匹配实际约束。
用法然后是更多的代码。首先存储更新滑块的实际位置。然后将滑块更新为新的位置/状态。之后，如果不满足约束，停止实际滑动速度并恢复其原始位置。
它会慢一点，但我懒得编写完整的约束更新器（该代码可能变得非常复杂......）。
我认识到2个相互平行和垂直的交互。平行是直截了当的。但垂线是滑块边缘与其附近的垂直滑块之间的相互作用，不包括初始状态下已经相交的滑块（a，b锚定或仅仅是交叉）。所以我在开始时创建了一个相交滑块（ ic ）的列表，这个相互作用将被忽略。
简单的
The choppyness is due to non uniform GIF grabbing sample rate (skipping some frames from the simulation irregularly).
You can play with the constants for vel,acc limits, dampening coefficient and the mode control ifs to change the behavior. If you implement also mouse handler then you can move the sliders with left mouse button so you can get out of stuck cases...
Here stand alone Win32 demo (compiled with BDS2006 C++).
- Demo click on slow download below the big magenta button, enter 4 letter alphanumeric code to start download no registration needed.
For more info about how the solver Force computation works see related/followup QA:
I have a set of metallic sliding pieces which are constrained to the x and y axis in following way:
I would need to maximize the horizontal distance among all pieces constrained by the same slider and the vertical distance among the sliding pieces and the sliders itself. How can this be solved?
Any advice and suggestion which can lead to a solution for this problem would be greatly appreciated.
I looked first at some very powerful libraries like cassowary and jsLPSolver but i had some trouble to understand the core algorithm and how the constraint are checked for feasibility and how the possible solutions are then ranked.
How could be implemented in JavaScript a (simple) stub for a 2-D geometric constraint solver for problems like this one above?
EDIT:
I have following input data:
maxW = 300, maxH = 320
The pieces are defined as follows (not mandatory, every solution is accepted):
slidingPiece = [pX, pY, width, height, anchorPoint, loopDistance];
I will try to explain what i mean under "maximize".
Horizontal spacing:
a0-b1, b1-b2, b2-b4, b4-b5 and b5-maxX will be the same, i.e. max X divided by the greatest number of vertical intersecting pieces + 1 (5). b1-b3 and b3-b5 will be then determined by the available remaining space.
Vertical spacing:
b1-a3, a3-a4 and a0-b5 will be the same. Ideally, a0-b3,b3-b4,a2-b2,b4-a3 and b2-a4 will be also the same value. Maximizing a1-b4 and b3-a2 is the same as maximizing b3-b4. The same applies to a2-b2 and b4-a3: the distance b2-b4 will be then the max negative value.
So, i need to maximize the distance among every sliding piece and his nearest above or below Y-constraint.
The 2-D geometric representation of this problem shows that the horizontal spacing depends from the vertical distance of the anchors (due to the vertical intersection of the anchored pieces), which in turn depends from the horizontal position of the pieces itself. Think for example, b2 is somewhat shorter above. In this case, b1 and b2 are no longer intersecting and would became the same x value, i.e. max X divided by 4.
In some other cases, for example b2 is much longer in the above part - and will cross the anchor a2, then it shall be spaced to a1. This is the reason because there will be a set of solutions, some feasible and some other not, because for example, the global max Y constraint would be broken.
I would try field approach similar to this.
Each slider will retract all sliders away
with force scaled by distance^2 like all of them would have the same polarity electric charge or springs attached in between each other.
On top of that add friction scaled by speed
does not really matter if air
v^2or liquidv^3implement kinematic constraints
for horizontal and vertical only sliding it should be really easy.
Do physical simulation and wait until it converges to stable state
v=~0if hit local min/max shake the whole thing a bit or arrange the whole thing randomly and try again. You can do this also to get another solution.
[Edit4] C++ solver example
structures/classes to represent the slider system
To ease up later code I will not support closed loops or double anchoring. That is why the i1 slider (most right) is not anchored to anything (will just provide forcefield). I ended up with this slider definition:
look at the source of
class _sliderfor more info.render
Dash-dash means fixed slider. Silver ones are horizontal, aqua means vertical and yellow is selected by mouse. May be later on red will mean some kind of error/stuck or something for debug purposes. For force field solvers I sometimes add the field strength as red-blue scale but not sure if I will implement it here or not.
To keep this simple I will not implement zoom/pan functions as your dimensions are convenient for direct render without transforms.
implement initial setup
sliders sys; int i0,i1,a0,a1,a2,a3,a4,b1,b2,b3,b4,b5; sys.slider_beg();//ia,ib, x, y, a0, a1, b0, b1,_horizontal i0=sys.slider_add(-1,-1, 25.0, 25.0, -5.0, 405.0, 0.0, 0.0, 0); a0=sys.slider_add(i0,-1, 0.0, 0.0, 0.0, 400.0, 0.0, 0.0, 1); a1=sys.slider_add(i0,-1, 0.0,100.0, 0.0, 400.0, 0.0, 0.0, 1); a2=sys.slider_add(i0,-1, 0.0,200.0, 0.0, 400.0, 0.0, 0.0, 1); a3=sys.slider_add(i0,-1, 0.0,300.0, 0.0, 400.0, 0.0, 0.0, 1); a4=sys.slider_add(i0,-1, 0.0,400.0, 0.0, 400.0, 0.0, 0.0, 1); b1=sys.slider_add(a0,a2, 20.0, 0.0, 0.0, 125.0, 125.0, 250.0, 0); b2=sys.slider_add(a3,-1, 40.0, 0.0, -70.0, 30.0, 0.0, 0.0, 0); b3=sys.slider_add(a1,-1, 60.0, 0.0, -70.0, 30.0, 0.0, 0.0, 0); b4=sys.slider_add(a2,-1, 80.0, 0.0, -30.0, 70.0, 0.0, 0.0, 0); b5=sys.slider_add(a3,a1,100.0, 0.0,-125.0, 0.0,-125.0,-250.0, 0); i1=sys.slider_add(-1,-1,425.0, 25.0, -5.0, 405.0, 0.0, 0.0, 0); sys.slider_end();Where
iais parent index andibis child index (the slider class itself holdsibas parent but that would be confusing to init as you would need to link to item that do not exist yet so theibtransformation is handled in thesys.addfunction).sysis class holding the whole thing andsys.addjust add new slider to it and returns its index counting from zero. Thex,yis relative position to parent.To ease up amount of coding this setup must not conflict the constraints. The overview of this setup is in previous bullet.
Beware the order of sliders must be left to right for vertical and top to bottom for horizontal sliders to ensure correct constraint functionality.
mouse interaction
just simple slider movement for debug and adjusting initial setup values. And or handling stuck cases. You need to handle mouse events, select closest slider if not editing already. And if mouse button is pressed move selected slider to mouse position...
physical constraint/interaction
I simplify this a bit so I just created a predicate function that is called for specified slider and it returns if it or any its child/anchor is in conflict with defined constraints. This is much more easy to code and debug then to update the position to match actual constraint.
Usage is then a bit more code. First store actual position for updated slider. Then update slider to new position/state. After that if constraints are not met stop actual slider speeds and restore its original position.
It will be a bit slower but I am too lazy to code the full constraint updater (that code could get really complex...).
I recognize 2 interactions parallel and perpendicular. The parallel is straight forward. But the perpendicular is interaction between edge of slider and perpendicular sliders near it not including the already intersecting sliders (a,b anchored or just crossing) during initial state. So I created a list of intersecting sliders (
ic) at start which will be ignored for this interaction.physical simulation
Simple Newton - D'Lambert physics for non relativistic speeds will do. Just on each iteration set the accelerations
ax,ayto the field strength and frictions.field solver
This is set of rules/equations to set simulation accelerations for each slider to converge to solution. I ended up with electrostatic retracting force
F = -Q/r^2and linear dampening of speed. Also have implemented absolute velocity and acceleration limiters to avoid numeric problems.To boost solution time and stability I added precision control modes where the electric charge is lowering when overall max speed of sliders is decreasing.
Here The full C++/VCL class code for this:
//---------------------------------------------------------------------------
//--- Sliders solver ver: 1.01 ----------------------------------------------
//---------------------------------------------------------------------------
#ifndef _sliders_h
#define _sliders_h
//---------------------------------------------------------------------------
#include <math.h>
#include "list.h" // linear dynamic array template List<T> similar to std::vector
//---------------------------------------------------------------------------
const double _slider_w = 3.00; // [px] slider half width (for rendering)
const double _slider_gap = 4.00; // [px] min gap between sliders (for colisions)
const double _acc_limit= 100.00; // [px/s^2]
const double _vel_limit= 100.00; // [px/s]
const double _friction = 0.90; // [-]
const double _charge =250000.00; // [px^3/s^2]
//---------------------------------------------------------------------------
class _slider // one slider (helper class)
{
public:
// properties
double x,y; // actual relative pos
bool _horizontal; // orientation
double a0,a1; // slider vertexes 0 is anchor point
double b0,b1; // anchor zone for another slider
int ia; // -1 for fixed or index of parrent slider
int ib; // -1 or index of parrent slider
// computed
List<int> ic; // list of slider indexes to ignore for perpendicular constraints
double a,b; // force field affected part
double X,Y; // actual absolute position
double vx,vy,ax,ay; // actual relative vel,acc
// temp
int flag; // temp flag for simulation
double x0,x1; // temp variables for solver
// constructors (can ignore this)
_slider() {}
_slider(_slider& a) { *this=a; }
~_slider() {}
_slider* operator = (const _slider *a) { *this=*a; return this; }
//_slider* operator = (const _slider &a) { ...copy... return this; }
};
//---------------------------------------------------------------------------
class sliders // whole slider system main class
{
public:
List<_slider> slider; // list of sliders
double vel_max; // max abs velocity of sliders for solver precision control
double charge; // actual charge of sliders for solve()
int mode; // actual solution precision control mode
// constructors (can ignore this)
sliders();
sliders(sliders& a) { *this=a; }
~sliders() {}
sliders* operator = (const sliders *a) { *this=*a; return this; }
//sliders* operator = (const sliders &a) { ...copy... return this; }
// VCL window API variables (can ignore this)
double mx0,my0,mx1,my1; // last and actual mouse position
TShiftState sh0,sh1; // last and actual mouse buttons and control keys state
int sel;
// API (this is important stuff)
void slider_beg(){ slider.num=0; } // clear slider list
int slider_add(int ia,int ib,double x,double y,double a0,double a1,double b0,double b1,bool _h); // add slider to list
void slider_end(); // compute slider parameters
bool constraints(int ix); // return true if constraints hit
void positions(); // recompute absolute positions
void update(double dt); // update physics simulation with time step dt [sec]
void solve(bool _init=false); // set sliders accelerations to solve this
void stop(); // stop all movements
// VCL window API for interaction with GUI (can ignore this)
void mouse(int x,int y,TShiftState sh);
void draw(TCanvas *scr);
};
//---------------------------------------------------------------------------
sliders::sliders()
{
mx0=0.0; my0=0.0;
mx1=0.0; my1=0.0;
sel=-1;
}
//---------------------------------------------------------------------------
int sliders::slider_add(int ia,int ib,double x,double y,double a0,double a1,double b0,double b1,bool _h)
{
_slider s; double q;
if (a0>a1) { q=a0; a0=a1; a1=q; }
if (b0>b1) { q=b0; b0=b1; b1=q; }
s.x=x; s.vx=0.0; s.ax=0.0;
s.y=y; s.vy=0.0; s.ay=0.0;
s.ia=ia; s.a0=a0; s.a1=a1;
s.ib=-1; s.b0=b0; s.b1=b1;
s.ic.num=0;
if ((ib>=0)&&(ib<slider.num)) slider[ib].ib=slider.num;
s._horizontal=_h;
s.a=a0; // min
if (s.a>a1) s.a=a1;
if (s.a>b0) s.a=b0;
if (s.a>b1) s.a=b1;
s.b=a0; // max
if (s.b<a1) s.b=a1;
if (s.b<b0) s.b=b0;
if (s.b<b1) s.b=b1;
slider.add(s);
return slider.num-1;
}
//---------------------------------------------------------------------------
void sliders::slider_end()
{
int i,j;
double a0,a1,b0,b1,x0,x1,w=_slider_gap;
_slider *si,*sj;
positions();
// detect intersecting sliders and add them to propriet ic ignore list
for (si=slider.dat,i=0;i<slider.num;i++,si++)
for (sj=si+1 ,j=i+1;j<slider.num;j++,sj++)
if (si->_horizontal!=sj->_horizontal)
{
if (si->_horizontal)
{
a0=si->X+si->a; a1=sj->X-w;
b0=si->X+si->b; b1=sj->X+w;
x0=si->Y; x1=sj->Y;
}
else{
a0=si->Y+si->a; a1=sj->Y-w;
b0=si->Y+si->b; b1=sj->Y+w;
x0=si->X; x1=sj->X;
}
if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
if ((x0>x1+sj->a-w)&&(x0<x1+sj->b+w))
{
si->ic.add(j);
sj->ic.add(i);
}
}
}
//---------------------------------------------------------------------------
bool sliders::constraints(int ix)
{
int i,j;
double a0,a1,b0,b1,x0,x1,x,w=_slider_gap;
_slider *si,*sj,*sa,*sb,*s;
s=slider.dat+ix;
// check parallel neighbors overlapp
for (si=slider.dat,i=0;i<slider.num;i++,si++)
if ((i!=ix)&&(si->_horizontal==s->_horizontal))
{
if (s->_horizontal)
{
a0=s->X+s->a; a1=si->X+si->a;
b0=s->X+s->b; b1=si->X+si->b;
x0=s->Y; x1=si->Y;
}
else{
a0=s->Y+s->a; a1=si->Y+si->a;
b0=s->Y+s->b; b1=si->Y+si->b;
x0=s->X; x1=si->X;
}
if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
{
if ((i<ix)&&(x0<x1+w)) return true;
if ((i>ix)&&(x0>x1-w)) return true;
}
}
// check perpendicular neighbors overlapp
for (si=slider.dat,i=0;i<slider.num;i++,si++)
if ((i!=ix)&&(si->_horizontal!=s->_horizontal))
{
// skip ignored sliders for this
for (j=0;j<s->ic.num;j++)
if (s->ic[j]==i) { j=-1; break; }
if (j<0) continue;
if (s->_horizontal)
{
a0=s->X+s->a; a1=si->X-w;
b0=s->X+s->b; b1=si->X+w;
x0=s->Y; x1=si->Y;
}
else{
a0=s->Y+s->a; a1=si->Y-w;
b0=s->Y+s->b; b1=si->Y+w;
x0=s->X; x1=si->X;
}
if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
if ((x0>x1+si->a-w)&&(x0<x1+si->b+w))
return true;
}
// conflict a anchor area of parent?
if (s->ia>=0)
{
si=slider.dat+s->ia;
if (s->_horizontal)
{
x0=si->Y+si->a0;
x1=si->Y+si->a1;
x=s->Y;
}
else{
x0=si->X+si->a0;
x1=si->X+si->a1;
x=s->X;
}
if (x<x0+w) return true;
if (x>x1-w) return true;
}
// conflict b anchor area of parent?
if (s->ib>=0)
{
si=slider.dat+s->ib;
if (si->_horizontal)
{
x0=si->X+si->b0;
x1=si->X+si->b1;
x=s->X;
}
else{
x0=si->Y+si->b0;
x1=si->Y+si->b1;
x=s->Y;
}
if (x<x0+w) return true;
if (x>x1-w) return true;
}
// conflict b anchor area with childs?
for (si=slider.dat,i=0;i<slider.num;i++,si++)
if ((i!=ix)&&(si->ib==ix))
{
if (s->_horizontal)
{
x0=s->X+s->b0;
x1=s->X+s->b1;
x=si->X;
}
else{
x0=s->Y+s->b0;
x1=s->Y+s->b1;
x=si->Y;
}
if (x<x0+w) return true;
if (x>x1-w) return true;
}
// check childs too
for (si=slider.dat,i=0;i<slider.num;i++,si++)
if ((i!=ix)&&(si->ia==ix))
if (constraints(i)) return true;
return false;
}
//---------------------------------------------------------------------------
void sliders::positions()
{
int i,e;
_slider *si,*sa;
// set flag = uncomputed
for (si=slider.dat,i=0;i<slider.num;i++,si++) si->flag=0;
// iterate until all sliders are computed
for (e=1;e;)
for (e=0,si=slider.dat,i=0;i<slider.num;i++,si++)
if (!si->flag)
{
// fixed
if (si->ia<0)
{
si->X=si->x;
si->Y=si->y;
si->flag=1;
continue;
}
// a anchored
sa=slider.dat+si->ia;
if (sa->flag)
{
si->X=sa->X+si->x;
si->Y=sa->Y+si->y;
si->flag=1;
continue;
}
e=1; // not finished yet
}
}
//---------------------------------------------------------------------------
void sliders::update(double dt)
{
int i;
_slider *si,*sa;
double x,X;
// D'Lamnbert integration
for (si=slider.dat,i=0;i<slider.num;i++,si++)
if (si->_horizontal)
{
x=si->y; si->vy+=si->ay*dt; // vel = Integral(acc*dt)
si->vy*=_friction; // friction k*vel
X=si->Y; si->y +=si->vy*dt; // pos = Integral(vel*dt)
positions(); // recompute childs
if ((si->ia<0)||(constraints(i))) // if fixed or constraint hit (stop and restore original position)
{
si->vy=0.0;
si->y =x;
si->Y =X;
positions(); // recompute childs
}
}
else{
x=si->x; si->vx+=si->ax*dt; // vel = Integral(acc*dt)
si->vx*=_friction; // friction k*vel
X=si->X; si->x +=si->vx*dt; // pos = Integral(vel*dt)
positions(); // recompute childs
if ((si->ia<0)||(constraints(i))) // if fixed or constraint hit (stop and restore original position)
{
si->vx=0.0;
si->x =x;
si->X =X;
positions(); // recompute childs
}
}
}
//---------------------------------------------------------------------------
void sliders::solve(bool _init)
{
int i,j,k;
double a0,a1,b0,b1,x0,x1;
_slider *si,*sj,*sa;
// init solution
if (_init)
{
mode=0;
charge=_charge;
}
// clear accelerations and compute actual max velocity
vel_max=0.0;
for (si=slider.dat,i=0;i<slider.num;i++,si++)
{
si->ax=0.0;
si->ay=0.0;
x0=fabs(si->vx); if (vel_max<x0) vel_max=x0;
x0=fabs(si->vy); if (vel_max<x0) vel_max=x0;
}
// precision control of solver
if ((mode==0)&&(vel_max>25.0)) { mode++; } // wait until speed raises
if ((mode==1)&&(vel_max<10.0)) { mode++; charge*=0.10; } // scale down forces to lower jitter
if ((mode==2)&&(vel_max< 1.0)) { mode++; charge*=0.10; } // scale down forces to lower jitter
if ((mode==3)&&(vel_max< 0.1)) { mode++; charge =0.00; stop(); } // solution found
// set x0 as 1D vector to closest parallel neighbor before and x1 after
for (si=slider.dat,i=0;i<slider.num;i++,si++) { si->x0=0.0; si->x1=0.0; }
for (si=slider.dat,i=0;i<slider.num;i++,si++)
for (sj=si+1 ,j=i+1;j<slider.num;j++,sj++)
if (si->_horizontal==sj->_horizontal)
{
// longer side interaction
if (si->_horizontal)
{
a0=si->X+si->a; a1=sj->X+sj->a;
b0=si->X+si->b; b1=sj->X+sj->b;
x0=si->Y; x1=sj->Y;
}
else{
a0=si->Y+si->a; a1=sj->Y+sj->a;
b0=si->Y+si->b; b1=sj->Y+sj->b;
x0=si->X; x1=sj->X;
}
if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
{
x0=x1-x0;
if ((si->ia>=0)&&(x0<0.0)&&((fabs(si->x0)<_slider_gap)||(fabs(si->x0)>fabs(x0)))) si->x0=-x0;
if ((si->ia>=0)&&(x0>0.0)&&((fabs(si->x1)<_slider_gap)||(fabs(si->x1)>fabs(x0)))) si->x1=-x0;
if ((sj->ia>=0)&&(x0<0.0)&&((fabs(sj->x0)<_slider_gap)||(fabs(sj->x0)>fabs(x0)))) sj->x0=+x0;
if ((sj->ia>=0)&&(x0>0.0)&&((fabs(sj->x1)<_slider_gap)||(fabs(sj->x1)>fabs(x0)))) sj->x1=+x0;
}
// shorter side interaction
if (si->_horizontal)
{
a0=si->Y-_slider_gap; a1=sj->Y+_slider_gap;
b0=si->Y+_slider_gap; b1=sj->Y+_slider_gap;
x0=si->X; x1=sj->X;
}
else{
a0=si->X-_slider_gap; a1=sj->X+_slider_gap;
b0=si->X+_slider_gap; b1=sj->X+_slider_gap;
x0=si->Y; x1=sj->Y;
}
if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
{
if (x0<x1) { x0+=si->b; x1+=sj->a; }
else { x0+=si->a; x1+=sj->b; }
x0=x1-x0;
if (si->ia>=0)
{
sa=slider.dat+si->ia;
if ((sa->ia>=0)&&(x0<0.0)&&((fabs(sa->x0)<_slider_gap)||(fabs(sa->x0)>fabs(x0)))) sa->x0=-x0;
if ((sa->ia>=0)&&(x0>0.0)&&((fabs(sa->x1)<_slider_gap)||(fabs(sa->x1)>fabs(x0)))) sa->x1=-x0;
}
if (sj->ia>=0)
{
sa=slider.dat+sj->ia;
if ((sa->ia>=0)&&(x0<0.0)&&((fabs(sa->x0)<_slider_gap)||(fabs(sa->x0)>fabs(x0)))) sa->x0=+x0;
if ((sa->ia>=0)&&(x0>0.0)&&((fabs(sa->x1)<_slider_gap)||(fabs(sa->x1)>fabs(x0)))) sa->x1=+x0;
}
}
}
// set x0 as 1D vector to closest perpendicular neighbor before and x1 after
for (si=slider.dat,i=0;i<slider.num;i++,si++)
for (sj=si+1 ,j=i+1;j<slider.num;j++,sj++)
if (si->_horizontal!=sj->_horizontal)
{
// skip ignored sliders for this
for (k=0;k<si->ic.num;k++)
if (si->ic[k]==j) { k=-1; break; }
if (k<0) continue;
if (si->_horizontal)
{
a0=si->X+si->a; a1=sj->X-_slider_w;
b0=si->X+si->b; b1=sj->X+_slider_w;
x0=si->Y;
}
else{
a0=si->Y+si->a; a1=sj->Y-_slider_w;
b0=si->Y+si->b; b1=sj->Y+_slider_w;
x0=si->X;
}
if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
{
if (si->_horizontal)
{
a1=sj->Y+sj->a;
b1=sj->Y+sj->b;
}
else{
a1=sj->X+sj->a;
b1=sj->X+sj->b;
}
a1-=x0; b1-=x0;
if (fabs(a1)<fabs(b1)) x0=-a1; else x0=-b1;
if ((si->ia>=0)&&(x0<0.0)&&((fabs(si->x0)<_slider_gap)||(fabs(si->x0)>fabs(x0)))) si->x0=+x0;
if ((si->ia>=0)&&(x0>0.0)&&((fabs(si->x1)<_slider_gap)||(fabs(si->x1)>fabs(x0)))) si->x1=+x0;
if (sj->ia<0) continue;
sa=slider.dat+sj->ia;
if ((sa->ia>=0)&&(x0<0.0)&&((fabs(sa->x0)<_slider_gap)||(fabs(sa->x0)>fabs(x0)))) sa->x0=-x0;
if ((sa->ia>=0)&&(x0>0.0)&&((fabs(sa->x1)<_slider_gap)||(fabs(sa->x1)>fabs(x0)))) sa->x1=-x0;
}
}
// convert x0,x1 distances to acceleration
for (si=slider.dat,i=0;i<slider.num;i++,si++)
{
// driving force F = ~ Q / r^2
if (fabs(si->x0)>1e-10) x0=charge/(si->x0*si->x0); else x0=0.0; if (si->x0<0.0) x0=-x0;
if (fabs(si->x1)>1e-10) x1=charge/(si->x1*si->x1); else x1=0.0; if (si->x1<0.0) x1=-x1;
a0=x0+x1;
// limit acc
if (a0<-_acc_limit) a0=-_acc_limit;
if (a0>+_acc_limit) a0=+_acc_limit;
// store parallel acc to correct axis
if (si->_horizontal) si->ay=a0;
else si->ax=a0;
// limit vel (+/- one iteration overlap)
if (si->_horizontal) x0=si->vy;
else x0=si->vx;
if (x0<-_vel_limit) x0=-_vel_limit;
if (x0>+_vel_limit) x0=+_vel_limit;
if (si->_horizontal) si->vy=x0;
else si->vx=x0;
}
}
//---------------------------------------------------------------------------
void sliders::stop()
{
int i;
_slider *si;
for (si=slider.dat,i=0;i<slider.num;i++,si++)
{
si->vx=0.0;
si->vy=0.0;
si->ax=0.0;
si->ay=0.0;
}
}
//---------------------------------------------------------------------------
void sliders::mouse(int x,int y,TShiftState sh)
{
int i,q0,q1;
double d,dd;
_slider *si;
// update mouse state
mx0=mx1; my0=my1; sh0=sh1;
mx1=x; my1=y; sh1=sh;
// slider movement with left mouse button
q0=sh0.Contains(ssLeft);
q1=sh1.Contains(ssLeft);
if ((sel>=0)&&(q1))
{
si=slider.dat+sel;
// stop simulation for selected slider
si->vx=0.0;
si->vy=0.0;
si->ax=0.0;
si->ay=0.0;
// use mouse position instead
if (si->ia>=0)
{
if (si->_horizontal){ d=si->y; dd=si->Y; si->y+=my1-si->Y; si->Y=my1; si->vy=0.0; si->ay=0.0; positions(); if (constraints(sel)) { si->y=d; si->Y=dd; positions(); }}
else { d=si->x; dd=si->X; si->x+=mx1-si->X; si->X=mx1; si->vx=0.0; si->ax=0.0; positions(); if (constraints(sel)) { si->x=d; si->X=dd; positions(); }}
}
}
// select slider (if not left mouse button used)
if (!q1)
for (sel=-1,d=_slider_w+1.0,si=slider.dat,i=0;i<slider.num;i++,si++)
{
dd=_slider_w+1.0;
if (si->_horizontal){ if ((mx1>=si->X+si->a)&&(mx1<=si->X+si->b)) dd=fabs(my1-si->Y); }
else { if ((my1>=si->Y+si->a)&&(my1<=si->Y+si->b)) dd=fabs(mx1-si->X); }
if ((dd<d)&&(dd<=_slider_w)) { sel=i; d=dd; }
}
}
//---------------------------------------------------------------------------
void sliders::draw(TCanvas *scr)
{
int i,j,n;
double w=_slider_w,r,x,y,a0,a1;
AnsiString txt;
_slider *s;
scr->Brush->Style=bsClear;
#define _line(aa,bb) \
if (s->_horizontal) \
{ \
scr->MoveTo(s->X+aa,s->Y); \
scr->LineTo(s->X+bb,s->Y); \
} \
else{ \
scr->MoveTo(s->X,s->Y+aa); \
scr->LineTo(s->X,s->Y+bb); \
}
scr->Pen->Color=clSilver;
scr->Font->Color=clWhite;
scr->TextOutA(40,40,AnsiString().sprintf("mode %i",mode));
scr->TextOutA(40,60,AnsiString().sprintf("vel: %.3lf [px/s]",vel_max));
scr->TextOutA(40,80,AnsiString().sprintf(" Q: %.3lf [px^3/s^2]",charge));
scr->Font->Color=clYellow;
for (s=slider.dat,i=0;i<slider.num;i++,s++)
{
if (s->_horizontal) scr->Pen->Color=clSilver;
else scr->Pen->Color=clAqua;
if (i==sel)
{
scr->Pen->Color=clYellow;
txt=AnsiString().sprintf(" ix:%i ia:%i ib:%i ic:",sel,s->ia,s->ib);
for (j=0;j<=s->ic.num;j++) txt+=AnsiString().sprintf(" %i",s->ic[j]);
scr->TextOutA(40,100,txt);
scr->TextOutA(40,120,AnsiString().sprintf("pos: %.1lf %.1lf [px]",s->X,s->Y));
scr->TextOutA(40,140,AnsiString().sprintf("vel: %.3lf %.3lf [px/s]",s->vx,s->vy));
scr->TextOutA(40,160,AnsiString().sprintf("acc: %.3lf %.3lf [px/s^2]",s->ax,s->ay));
scr->Pen->Color=clYellow;
}
if (s->ia<0) scr->Pen->Style=psDash;
else scr->Pen->Style=psSolid;
// a anchor loop
x=s->X;
y=s->Y;
if (s->ia>=0) scr->Ellipse(x-w,y-w,x+w,y+w);
// b anchor loop
r=0.5*fabs(s->b1-s->b0);
if (s->_horizontal)
{
x=s->X+0.5*(s->b0+s->b1);
y=s->Y;
scr->RoundRect(x-r,y-w,x+r,y+w,w,w);
}
else{
x=s->X;
y=s->Y+0.5*(s->b0+s->b1);
scr->RoundRect(x-w,y-r,x+w,y+r,w,w);
}
// a line cutted by a anchor loop
a0=s->a0; a1=s->a1;
if ((s->ia>=0)&&(a0<=+w)&&(a1>=-w))
{
if (a0<-w) _line(s->a0,-w);
if (a1>+w) _line( w,s->a1);
}
else _line(s->a0,s->a1);
}
scr->Font->Color=clDkGray;
scr->Pen->Style=psSolid;
scr->Brush->Style=bsSolid;
#undef _line
}
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
You can ignore the VCL stuff it is just API for interaction with my App window and rendering. The solver itself does not need anything from it. I used my dynamic linear array template List<T> so here few explanations:
List<double> xxx;is the same asdouble xxx[];xxx.add(5);adds5to end of the listxxx[7]access array element (safe)xxx.dat[7]access array element (unsafe but fast direct access)xxx.numis the actual used size of the arrayxxx.reset()clears the array and setxxx.num=0xxx.allocate(100)preallocate space for100items
Usage is simple after proper init from bullet #3 like this:
sys.solve(true);
for (;;)
{
sys.solve();
sys.update(0.040); // just time step
if (sys.mode==4) break; // stop if solution found or stuck
}
Instead of for cycle I call this in timer and redraw the window so I see the animation:
The choppyness is due to non uniform GIF grabbing sample rate (skipping some frames from the simulation irregularly).
You can play with the constants for vel,acc limits, dampening coefficient and the mode control ifs to change the behavior. If you implement also mouse handler then you can move the sliders with left mouse button so you can get out of stuck cases...
Here stand alone Win32 demo (compiled with BDS2006 C++).
- Demo click on slow download below the big magenta button, enter 4 letter alphanumeric code to start download no registration needed.
For more info about how the solver Force computation works see related/followup QA:
这篇关于如何实现二维几何的约束求解器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
