 Home
 » Viewing Profile: Reputation: Dave Eberly
Dave Eberly
Member Since 22 Aug 2004Offline Last Active Oct 15 2012 01:13 AM
Community Stats
 Group Members
 Active Posts 591
 Profile Views 5,627
 Submitted Links 0
 Member Title Member
 Age Age Unknown
 Birthday Birthday Unknown

Gender
Not Telling

Location
Redmond WA
#4977502 Figuring out ellipsoidellipsoid collision detection
Posted by Dave Eberly on 06 September 2012  11:50 PM
That said, there is an implementation of the ellipsoidellipsoid intersection at my web site.
Regarding capsules, better choice than ellipsoids because the intersection/separation tests are simpler to implement. For capsulecapsule sweep, a simple implementation uses bisection over the desired time interval. At each time you apply a (static) capsulecapsule overlap test, which reduces to a computation of distance between line segments and a comparson involving this distance and capsule radii. You can avoid the iterationI have pseudocode for this in my Game Physics 2nd edition (section 6.3.2).
Regarding bounded cylinders, the game physics book and a document at my web site show the complexity of intersection testing via separating axes. Turns out that it is simpler to do cylindercylinder intersection with infinite cylinders, then clip the intersection set based on the finite cylinder heights. Not an exact test (result is not a closed form solution), but effective. I have a document about this at my web site and a sample application (for the infinite cylindercylinder test).
#4968344 Hieroglyph 3 Rendering engine Question
Posted by Dave Eberly on 10 August 2012  11:46 PM
Is the Hieroglyph 3 well written?
I am trying to learn the right way to make dynamic classes for a engine like rendering system using direct3d 11.
Is there another good open source engine using direct3d?
I want to know how the professionals make the thinks.
The code is good quality. More importantly, purchase the book that goes with it: Practical Rendering & Computation with Direct3D 11, by J. Zink, M. Pettineo, and J. Hoxley. I have requested reading this for the engineers on my realtime graphics team.
#4965099 SSE vector normalization
Posted by Dave Eberly on 31 July 2012  11:44 PM
inline const CVector3SSE& CVector3SSE::Normalize() { static const __m128 almostZero = _mm_set1_ps(1e5f); __m128 dp = _mm_dp_ps(m_fValsSSE, m_fValsSSE, 0x7F); const __m128 cmp = _mm_gt_ps(dp, almostZero); dp = _mm_rsqrt_ps(dp); m_fValsSSE = _mm_mul_ps(m_fValsSSE, _mm_and_ps(dp, cmp)); return *this; }
Although yours is the standard way folks do the normalization, for large components the dot product overflows. If you need something that is robust for all finite floatingpoint inputs,
inline __m128 MaximumAbsoluteComponent (__m128 const v) { __m128 SIGN = _mm_set1_ps(0x80000000u); __m128 vAbs = _mm_andnot_ps(SIGN, v); __m128 max0 = _mm_shuffle_ps(vAbs, vAbs, _MM_SHUFFLE(0,0,0,0)); __m128 max1 = _mm_shuffle_ps(vAbs, vAbs, _MM_SHUFFLE(1,1,1,1)); __m128 max2 = _mm_shuffle_ps(vAbs, vAbs, _MM_SHUFFLE(2,2,2,2)); __m128 max3 = _mm_shuffle_ps(vAbs, vAbs, _MM_SHUFFLE(3,3,3,3)); max0 = _mm_max_ps(max0, max1); max2 = _mm_max_ps(max2, max3); max0 = _mm_max_ps(max0, max2); return max0; } inline __m128 Normalize (__m128 const v) { // Compute the maximum absolute value component. __m128 maxComponent = MaximumAbsoluteComponent(v); // Divide by the maximum absolute component. This is potentially a divide by zero. __m128 normalized = _mm_div_ps(v, maxComponent); // Set to zero when the original length is zero. __m128 zero = _mm_setzero_ps(); __m128 mask = _mm_cmpneq_ps(zero, maxComponent); normalized = _mm_and_ps(mask, normalized); // (sqrLength, sqrLength, sqrLength, sqrLength) __m128 sqrLength = _mm_dp_ps(normalized, normalized, 0x7F); // (length, length, length, length) __m128 length = _mm_sqrt_ps(sqrLength); // Divide by the length to normalize. This is potentially a divide by zero. normalized = _mm_div_ps(normalized, length); // Set to zero when the original length is zero or infinity. In the latter case, this is considered to be an unexpected condition. normalized = _mm_and_ps(mask, normalized); return normalized; }
#4930121 Trying to find a minimal set of polygons that intersect a rectangle.
Posted by Dave Eberly on 10 April 2012  11:27 PM
I have an ordered set of polygons and I am intersecting them with a rectangle, how do I tell when the rectangle is filled so I can stop checking? This is in 2D.
I am trying to get the minimal set of polygons with cover the rectangle. The order of the set is the priority of use and the polygons are simple (don't have holes or self intersecting). So if my set is {A,B,C,D} and A B D intersect the rectangle but A contains B than I want a the set that contains just {A, D}.
Tried googling but wasn't sure what to google really, I was thinking it would fall under polygon coverage but that didn't seem to produce results of what I was looking for.
Thanks
I think this is a hard problem theoretically. For a practical solution, have you thought about rasterizing the rectangle and polygons to a highresolution grid? Rasterize the rectangle first. Rasterizer your polygons one at a time, keeping track of which rectangle pixels are written to (sort of like a stencil buffer) and which polygons have been rasterized to previously unwritten pixels. Once you have rasterized to all pixels, the process terminates. (You have to deal with not writing all rectangle pixels after all polygons have been processed.)
#4919702 SLMATH library and SSE optimisation problem.
Posted by Dave Eberly on 06 March 2012  01:51 AM
Thanks. It does, yes. It's a giant pain, so I think I'll just switch off SSE in the project settings and live without the performance boost.
std::vector should be able to support alignment through custom allocators. However, if you are using MSVS 2010, the dinkumware STL they use has a bug in that the std::vector resize does not do the right thing (fixed in MSVS 2011). For MSVS 2010, you'll have to roll your own std::vector (maybe copy what dinkumware does and "fix" the resize).
#4915790 ID3D11ShaderReflection question
Posted by Dave Eberly on 23 February 2012  12:16 AM
#4860227 Sweep Line Algorithm
Posted by Dave Eberly on 10 September 2011  11:03 PM
#4847025 OBB Computation
Posted by Dave Eberly on 09 August 2011  10:36 PM
Alternatively, you can use the covariance approach. If you have two (nearly) equal eigenvalues (eigenspace of dimension 2) and a third eigenvalue that is different from them (eigenspace of dimension 1), you can project out the eigenvector from the third eigenvalue. You now have a model in the 2dimensional eigenspace. Now you can use the method of rotating calipers to find the minimumarea rectangle containing the (projected) points. Effectively, this allows you to search the 2dimensional eigenspace for a pair of orthogonal eigenvectors that give you a good fit. I suspect this approach is faster than always trying to compute the minimumvolume OBB.
#4846520 OBB Computation
Posted by Dave Eberly on 08 August 2011  10:09 PM
In your square example in 3D, the center does not look right. The center should be the average of the vertices, which is (0,0,1), not (0.5,0.5,1). So your implementation might have other problems. Compute the center first. When building the covariance matrix, do not forget to subtract the center from each vertex before computing the sum of squared values.
#4841423 Closest point on ray to AABB?
Posted by Dave Eberly on 27 July 2011  09:21 PM
#4837794 Math.Sin replaced with lookup table
Posted by Dave Eberly on 19 July 2011  10:48 PM
I am working currently on a core 2 duo in my macbook, but I am targeting the xbox 360 with XNA. I suspect that I am frequently accessing RAM because I am filling 9 buffers 48000 floats long. I am not too sure what the profiler is telling me because I am very inexperienced with it. It is the one that comes with visual studio 2010 professional.
I assume you are using intrinsics to get the SIMD versions of the XNA math functions? The XNA sine function uses a Taylor series with 12 terms. Using a different algorithm (Chebyshev Equioscillation Theorem applied to sin(x)/x), you can double the speed (with a polynomial of 6 terms) at half the maximum error. From my math libraries. It is easy to convert this to SIMD, whether Intel SSE or Xbox360.
template <typename Real> Real Math<Real>::FastSin1 (Real angle) { Real angleSqr = angle*angle; Real result = (Real)2.39e08; result *= angleSqr; result += (Real)2.7526e06; result *= angleSqr; result = (Real)1.98409e04; result *= angleSqr; result += (Real)8.3333315e03; result *= angleSqr; result = (Real)1.666666664e01; result *= angleSqr; result += (Real)1.0; result *= angle; return result; }
#4834630 3D FingerPrint  need to extract ridges and valleys? Estimation Curvatures
Posted by Dave Eberly on 12 July 2011  11:18 PM
You wrote: "I am totally frustated !! Tried all done all situation but nothing is working for me. I have to complete this within one month to defend my thesis. If I am not able to do so I will lose my job that I want to join after that "
The topic area is a difficult one. If you have made no progress at this time, one more month is not going to make a difference. Writing a thesis is one thing, defending it is another, not everyone successfully defends, and whether or not you obtain a job is not relevant to folks helping you here (and is not an incentive to make them want to help). Perhaps now is a good time to meet with your advisor and discuss your situation...
#4828953 Minimum bounding sphere of a Frustum
Posted by Dave Eberly on 28 June 2011  11:06 PM
// void ComputeMinimumVolumeSphereOfFrustum (const float eye[3], const float direction[3], const float dmin, const float dmax, const float rmax, const float umax, float center[3], float& radius) { float invDMin = 1.0f/dmin; float u = umax*invDMin; float r = rmax*invDMin; float u2pr2 = u*u + r*r; float s = 0.5f*(dmin + dmax)*(1.0f + u2pr2); if (s >= dmax) { s = dmax; radius = dmax*sqrt(u2pr2); } else { float diff = 1.0f  s/dmax; radius = dmax*sqrt(diff*diff + u2pr2); } for (int i = 0; i < 3; ++i) { center[i] = eye[i] + s*direction[i]; } } // template <int n, typename Real> void ComputeMiniballFrustum (const Real eye[n], const Real direction[n], const Real min0, const Real max[n], Real center[n], Real& radius) { Real invMin0 = ((Real)1)/min0; float ratio[n], sqrLength = (Real)0; for (int i = 1; i < n; ++i) { ratio[i] = max[i]*invMin0; sqrLength += ratio[i]*ratio[i]; } Real s = ((Real)0.5)*(min0 + max[0])*((Real)1 + sqrLength); if (s >= max[0]) { s = max[0]; radius = max[0]*sqrt(sqrLength); } else { Real diff = (Real)1  s/max[0]; radius = max[0]*sqrt(diff*diff + sqrLength); } for (int i = 0; i < n; ++i) { center[i] = eye[i] + s*direction[i]; } } // int main () { float eye[3] = { 0.0f, 0.0f, 0.0f }; float direction[3] = { 0.0f, 0.0f, 1.0f }; float dmin = 10.0f, dmax = 1000.0f, rmax = 2.0f, umax = 1.0f; float center0[3], radius0; ComputeMinimumVolumeSphereOfFrustum(eye, direction, dmin, dmax, rmax, umax, center0, radius0); float min0 = dmin, max[3] = { dmax, rmax, umax }; float center1[3], radius1; ComputeMiniballFrustum<3,float>(eye, direction, min0, max, center1, radius1); return 0; } //
#4827954 Minimum bounding sphere of a Frustum
Posted by Dave Eberly on 26 June 2011  11:43 AM
Let E be the eyepoint. Let the view direction be D, the up direction be U, and the right direction be R. D, U, and R are unit length and mutually perpendicular. The frustum values are dmin (near), dmax (far), rmax (right), rmax (left), umax (up), and umax (down). The sphere center is C = E + s*D for some s. A vertex of the near plane is P0 = E + dmin*D + umax*U + rmax*R. A vertex of the far plane is P1 = E + dmax*D + (dmax*umax/dmin)*U + (dmax*rmax/dmin)*R. The squared distances from P0 to C and P1 to C must be equal, so (sdmin)^2 + rmax^2 + umax^2 = (s  dmax)^2 + (dmax*rmax/dmin)^2 + (dmax*umax/dmin)^2. This leads to s = ((dmin + dmax)/2)*(1 + (rmax/dmin)^2 + (umax/dmin)^2).
This is actually the circumscribed sphere, which I believe is the minimumvolume sphere as long as center C is inside the frustum, which means as long as s <= dmax. When s > dmax, the minimumvolume sphere is the one whose center is E+dmax*D. The radius is distance from C to a vertex on the far plane. In the case s < dmax, the radius is the distance from C to any of the 8 vertices, but you can just substitute the value of s in either of the squared distances I mentioned and then take the square root.
#4806750 Closest point on cubic bézier curve
Posted by Dave Eberly on 04 May 2011  10:51 PM
I'm trying to find the point on a cubic bézier curve closest to another external point P, in 2D space. I've read the Graphics Gems explanation on the method and other stuff but the math's way over my head. Specifically I don't really understand how finding the roots of the.. curve's polynomial (am I making sense?) gets you closer to the solution. Would somebody be able to explain this in a 14 year old's terms? (:
Generally, let the curve be parameterized by (x(t),y(t)) and let P = (p0,p1) be the external point. The vector from the closest point on the curve to P must be normal to the curve, which means that vector is perpendicular to a tangent of the curve. Such a tangent is the derivative (x'(t),y'(t)). The vector from a curve point to P is (x(t)p0,y(t)p1). To be perpendicular, the dot product is zero: 0 = x'(t)*(x(t)p0) + y'(t)*(y(t)p1) = f(t). When (x(t),y(t)) has polynomial components, f(t) is a polynomial. So the problem reduces to finding roots of f(t). In your case, x(t) and y(t) are degree3 polynomials, x'(t) and y'(t) are degree2 polynomials, so f(t) is a degree5 polynomial. There are no closedform equations for roots of degree5, so you must use a numerical method for root finding.