Re: [Algorithms] Solving a system of line equations -- SimpleVersion ; )

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

thanks!

Right now I'm getting pretty good results by initializing all r = rMax and then solving the s<t constraints; the main problem with this is that each frame I have to start from scratch.. your idea sounds promising in that it will let me "warm start" things using the previous frame's solution.

--- On Mon, 12/8/08, Patrick Betremieux <Pa...@li...> wrote:

> From: Patrick Betremieux <Pa...@li...>
> Subject: Re: [Algorithms] Solving a system of line equations -- SimpleVersion ; )
> To: "Game Development Algorithms" <gda...@li...>
> Received: Monday, December 8, 2008, 1:30 PM
> I see two problems with those two constraints being in the
> same solver
> pass. First, the two constraints are really opposite of
> each other. And
> since this problem has a range of solutions per segment,
> and no local
> minimum, you will likely get the solver to just ping pong
> back and forth
> around valid solutions. And if you run this as the user
> moves a point,
> you might very well get all the segments to randomly switch
> between
> valid solutions each frame.
> 
> Since one of your constraints is softer then the other (s
> < t is an
> absolute, whereas r being close to rMax is just to make it
> better), I
> would just iteratively expand the r's one segment at a
> time until they
> all reach their max, or would cause s >= t. First
> compute for all
> segments by how much it could grow its r without causing
> problems. Then
> iteratively pick the segment that has the least room to
> grow its r and
> expand it as much as possible. Recompute the new growth
> potential of the
> two neighbours, and repeat until you've gone through
> all the segments.
> At least, this would have the benefit of giving you the
> same answer each
> time you run it, but you'd have to add some heuristic
> for which solution
> you're more interested in (Maximizing one r might make
> another one
> needing to be zero, which might not be good)
> 
> Patrick.
> 
> -----Original Message-----
> From: metanet software [mailto:met...@ya...] 
> Sent: Friday, December 05, 2008 12:08 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Solving a system of line
> equations --
> SimpleVersion ; )
> 
> I've gotten the basic solver working, but I'm still
> struggling with how
> to deal with additional constraints, such as:
> 
> -drive r[] values towards targets (minimize ||targ[i] -
> r[i]||)
> -enforce a minimum allowable r value (make sure r[i] >
> rmin)
> 
> Currently I'm adding these as additional constraints
> the solver has to
> deal with; this makes sense for enforcing the minimum
> allowable value,
> but it seems wrong to drive r[] values towards targets
> using
> constraints, since they almost always directly
> "fight" with the main
> constraints.. causing the solver to fail to converge to a
> solution.
> 
> Raigan
> 
> 
> 
> --- On Fri, 12/5/08, metanet software
> <met...@ya...> wrote:
> 
> > From: metanet software <met...@ya...>
> > Subject: [Algorithms] Solving a system of line
> equations -- Simple
> Version ; )
> > To: gda...@li...
> > Received: Friday, December 5, 2008, 10:20 AM
> > My first form of this question was needlessly obtuse,
> this
> > version should be much more comprehensible! 
> > 
> > I have the following system:
> > http://www.harveycartel.org/raigan/system.jpg
> > 
> > I'd like to solve for r0,r1,r2 such that s < t;
> > obviously setting r0=r1=r2=0 is a trivial solution;
> I'm
> > more interested in driving r0,r1,r2 towards target
> values
> > r0max,r1max,r2max while maintaining the constraint s
> < t.
> > 
> > My current plan is to construct the constraint
> equation C =
> > s - t < 0 and then solve for the r values (by
> calculating
> > the partial derivatives of C wrt r[i] and doing a
> > non-linear-least-squares fit as in
> >
> http://www.matthiasmueller.info/publications/posBasedDyn.pdf
> > ).
> > 
> > However even if this works, I have no idea how to
> > simultaneously minimize (rmax[i] - r[i]), i.e how I
> should
> > drive the r values towards target values while obeying
> C.
> > 
> > Sorry for the totally obfuscated initial question..
> thanks
> > for your time!
> > 
> > Raigan
> > 
> > p.s - Just in case it's not clear from the
> diagram, s
> > and t are the parametric times of intersection between
> > lines; each line is parallel to a segment (p[i+1] -
> p[i])
> > and passes through the point p[i] + r[i]*Perp(p[i+1] -
> > p[i])/Len(p[i+1] - p[i]).. i.e each line is just a
> > linesegment offset along its normal.
> > 
> > 
> > 
> >      
> >
> __________________________________________________________________
> > Looking for the perfect gift? Give the gift of Flickr!
> 
> > 
> > http://www.flickr.com/gift/
> > 
> >
> ------------------------------------------------------------------------
> ------
> > SF.Net email is Sponsored by MIX09, March 18-20, 2009
> in
> > Las Vegas, Nevada.
> > The future of the web can't happen without you. 
> Join
> > us at MIX09 to help
> > pave the way to the Next Web now. Learn more and
> register
> > at
> >
> http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.
> com/
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> >
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> >
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
> t
> 
> 
>      
> __________________________________________________________________
> Yahoo! Canada Toolbar: Search from anywhere on the web, and
> bookmark
> your favourite sites. Download it now at
> http://ca.toolbar.yahoo.com.
> 
> ------------------------------------------------------------------------
> ------
> SF.Net email is Sponsored by MIX09, March 18-20, 2009 in
> Las Vegas,
> Nevada.
> The future of the web can't happen without you.  Join
> us at MIX09 to
> help
> pave the way to the Next Web now. Learn more and register
> at
> http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.
> com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
> t
> 
> ------------------------------------------------------------------------------
> SF.Net email is Sponsored by MIX09, March 18-20, 2009 in
> Las Vegas, Nevada.
> The future of the web can't happen without you.  Join
> us at MIX09 to help
> pave the way to the Next Web now. Learn more and register
> at
> http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

      __________________________________________________________________
Yahoo! Canada Toolbar: Search from anywhere on the web, and bookmark your favourite sites. Download it now at
http://ca.toolbar.yahoo.com.