In my projects, it rarely is, so I haven’t bothered implementing these optimizations. On x86, consider using the fist=/=fistp instruction or maybe SSE for cvtsd2si (I haven’t gone this far in optimization).īefore optimizing, profile and make sure linear interpolation is your bottleneck. Floating point vs fixed point If you profile and find Math.round() is expensive, you can switch to fixed point arithmetic, and replace rounding with bit shifting. If these cases are common, write a separate routine for them. For orthogonal lines, one or the other will be 0. You might want to have a separate versions for each case. Separate cases Either Δx or Δy will be ☑.
Would this allow the use of SSE instructions? I don’t know. Unrolling loop You can unroll the loop by keeping four x and y pairs, and then using t += 4*Δt.
This will replace the multiplies with adds. Unrolling lerp Instead of calculating t each time through the loop, and then x = (b.x-a.x)*t (a subtract and multiply), you can calculate Δx = (b.x-a.x)*Δt outside the loop, and then use x += Δx. You can optimize the regular line drawing algorithm with these steps it will turn into the DDA algorithm : Inlining function calls Your compiler will likely do this but you may spot additional optimization opportunities by doing this yourself first. However I haven’t explored this with square grids. I think the thing to do would be to “nudge” the initial points by epsilon. That, and floating point precision, make linear interpolation not always choose points in a way that preserves consistency with rotation, reversing, and other symmetry. What happens when the value is exactly 0.5? Rounding rules vary. Linear interpolation is calculating a position and then rounding it. When T and ΔT are the same type, d = a - b can be implemented as d = a + (-1 * b). For example, T may be a timestamp and ΔT may be a time difference, or T may be an orientation and ΔT may be a rotation. Note that T and ΔT may be the same type, but sometimes they are different. My guide to hexagonal grids uses interpolation to draw lines on a hex grid. T can be a number, a 2d point, a 3d point, an angle, a time, a color, or other things too. We can do interpolation on any vector space. For points, d.x = a.x - b.x d.y = a.y - b.y multiplication by scalar e = k * d where d: ΔT, e: ΔT, and k: number. For points, b.x = a.x + d.x b.y = a.y + d.y subtraction d = a - b where a: T, b: T, and d: ΔT. How about other types T? We need these operations to define interpolation: addition b = a + d where a: T, b: T, and d: ΔT. I defined the lerp function to interpolate between two numbers, and then I defined lerp_point to work on two points. Return new Point(Math.round(p.x), Math.round(p.y)) Return Math.max(Math.abs(dx), Math.abs(dy))
0 kommentar(er)
