Points and Lines: Computationally fast

In summary, the conversation discusses the development of a basic physics engine for a video game. The main issue is how to efficiently decompose vectors into two components without using square root, sin, or cos functions. The possibility of using approximations and vector algebra is also mentioned. The conversation also touches on the importance of considering efficiency in the development process and suggests using toy programs to test and analyze code performance.
  • #1
_Nate_
20
0
I am working on a basic physics engine for a video game. In it, models are applied forces and deal with those forces by some physics calculations.

Whenever a model is applied a force, the force is in the form of a vector originating from a point in space. The vector must be decomposed into two components: the component that is pointing from the origin of the vector to the center of mass of the object is added to the translational force vector of the model, the component that is perpendicular to the first component goes into rotational force.

I need a way to decompose these vectors into two base vectors, one pointing at the center of mass of the object, and one perpendicular to that. But the catch is, because I am doing this many times a second, the calculation needs to be very fast.

This problem is very easily solved, but I would like to know if there is any way to solve it *without* using square root, sin, or cos. Is this possible?

Keep in mind that if a formula dictates I find sqrt(a^2 + a^2) then this really isn't forcing me to use the square root function: because this is simply sqrt(2) * a, and sqrt(2) is a constant. So it's possible to use sqrt, sin, and cos at computationally fast speeds so long as their use is constant regardless of the vector used.

Is this possible?

Here are several other versions of the problem that, if solved, can be used to solve the problem as a whole:

You have a point c and a line. Find the two points on the line such that their distance from c is equal to a given value r.

You have a circle centered at c with a radius r. A ray starts with a point on the circle. Find out where the ray intersects the circle again.

Anyone have any ideas?
 
Mathematics news on Phys.org
  • #2
First question: have you actually implemented the engine and profiled it? Do you actually know that your calculations are too slow? If so, are you sure that the problem is with calling these numeric functions, rather than other facets of your algorithm?

Second question: how accurate do the calculations need to be? There are ways to quickly compute good approximations to commonly used function; these might be sufficient for your purposes.

Third question: are you familiar with vector algebra? (e.g. dot products, cross products, etc)
 
Last edited:
  • #3
1. No -- I thought it would be safe to assume that calculations happening at this frequency would be likely to create a bottleneck, and thus wanted to evaluate my possibilities before getting too deep in the project.

2. This will be the tradeoff -- I'll probably implement both and allow the user to choose the degree of precision (at the expense of speed)

3. Yes, quite.

Thanks.
 
  • #4
_Nate_ said:
1. No -- I thought it would be safe to assume that calculations happening at this frequency would be likely to create a bottleneck, and thus wanted to evaluate my possibilities before getting too deep in the project.
Some famous quotes from computer science:

“More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity.”

“premature optimization is the root of all evil.”

“Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is.”


Thinking about efficiency is a good thing -- but optimization really belongs near the end of the development process. IMHO, the most important reason is that optimizations make your code more complex; this means it will take longer to design and develop, it will be more difficult to understand, and it will contain more bugs. (as a side benefit, it can also help you avoid wasting time optimizing when none is needed) It is better in almost every way to first focus on getting your code working, and only later focus on getting your code to work fast.


If you want to insist on thinking about speed now, then I suggest trying toy programs -- write short little test programs that allow you to estimate how long it takes to perform various calculations, and thus how many operations per second you can perform. Then, analyze your engine design to see how the numbers compare.


3. Yes, quite.
I would expect that working with dot and cross products would be more efficient than working with sines and cosines, except in certain special cases. I doubt you can avoid square roots entirely (though consider working through the algebra to see if you can delay them -- it might be possible to cancel them out, or gather a bunch together to do at once)... but I expect square roots to be faster than trig functions.
 

1. How can points and lines be computed quickly in science?

In order to compute points and lines quickly in science, computer algorithms are used to efficiently process and analyze large amounts of data. These algorithms are designed to perform specific mathematical operations and can greatly speed up the process of calculating points and lines.

2. Can points and lines be computed accurately using computational methods?

Yes, with the advanced technology and algorithms available today, points and lines can be computed with a high level of accuracy. However, it is important to ensure that the data being used for the computations is accurate and reliable.

3. How do scientists use points and lines in their research?

Points and lines are commonly used in various fields of science such as mathematics, physics, and engineering. Scientists use them to analyze and represent data, identify patterns and trends, and make predictions.

4. What are some benefits of using computational methods for points and lines?

Using computational methods for points and lines allows for faster and more efficient analysis of large datasets. It also enables scientists to perform complex calculations and simulations that would be difficult or impossible to do by hand.

5. Are there any limitations to using computational methods for points and lines?

While computational methods offer many advantages, they also have some limitations. These include the need for accurate and reliable data, potential bias in algorithms, and the possibility of errors or bugs in the code. It is important for scientists to carefully evaluate and validate their results when using computational methods for points and lines.

Similar threads

Replies
2
Views
182
Replies
2
Views
1K
  • General Math
Replies
20
Views
1K
Replies
13
Views
3K
  • General Math
Replies
3
Views
2K
  • General Math
Replies
4
Views
3K
Replies
2
Views
1K
Replies
7
Views
3K
Replies
1
Views
746
  • General Math
Replies
1
Views
2K
Back
Top