From 22bfd1396c72e113fadaf1b5cfa746cd22d84be7 Mon Sep 17 00:00:00 2001
From: David Adam <david.adam.cnrs@gmail.com>
Date: Thu, 26 Feb 2009 08:55:07 +0100
Subject: [PATCH] ddraw: Implement ComputeSphereVisibility.

---
 dlls/ddraw/ddraw_private.h |   2 +
 dlls/ddraw/device.c        |  96 ++++++++++++++++++------
 dlls/ddraw/tests/d3d.c     | 180 +++++++++++++++++++++++++++++----------------
 dlls/ddraw/utils.c         |  25 +++++++
 4 files changed, 217 insertions(+), 86 deletions(-)

diff --git a/dlls/ddraw/ddraw_private.h b/dlls/ddraw/ddraw_private.h
index 8b401d5ccfe..27261a1c5f6 100644
--- a/dlls/ddraw/ddraw_private.h
+++ b/dlls/ddraw/ddraw_private.h
@@ -722,6 +722,8 @@ void DDRAW_dump_cooperativelevel(DWORD cooplevel);
  * IDirect3DExecuteBuffer isn't in WineD3D */
 void multiply_matrix(LPD3DMATRIX dest, const D3DMATRIX *src1, const D3DMATRIX *src2);
 
+void multiply_matrix_D3D_way(LPD3DMATRIX result, const D3DMATRIX *m1, const D3DMATRIX *m2);
+
 /* Helper function in main.c */
 BOOL LoadWineD3D(void);
 
diff --git a/dlls/ddraw/device.c b/dlls/ddraw/device.c
index d97b7447b5f..8f8437457e4 100644
--- a/dlls/ddraw/device.c
+++ b/dlls/ddraw/device.c
@@ -4593,6 +4593,19 @@ Thunk_IDirect3DDeviceImpl_3_DrawIndexedPrimitiveVB(IDirect3DDevice3 *iface,
  *  is singular)
  *
  *****************************************************************************/
+
+static DWORD in_plane(UINT plane, D3DVECTOR normal, D3DVALUE origin_plane, D3DVECTOR center, D3DVALUE radius)
+{
+    float distance, norm;
+
+    norm = sqrt( normal.u1.x * normal.u1.x + normal.u2.y * normal.u2.y + normal.u3.z * normal.u3.z );
+    distance = ( origin_plane + normal.u1.x * center.u1.x + normal.u2.y * center.u2.y + normal.u3.z * center.u3.z ) / norm;
+
+    if ( fabs( distance ) < radius ) return D3DSTATUS_CLIPUNIONLEFT << plane;
+    if ( distance < -radius ) return (D3DSTATUS_CLIPUNIONLEFT  | D3DSTATUS_CLIPINTERSECTIONLEFT) << plane;
+    return 0;
+}
+
 static HRESULT WINAPI
 IDirect3DDeviceImpl_7_ComputeSphereVisibility(IDirect3DDevice7 *iface,
                                               D3DVECTOR *Centers,
@@ -4601,30 +4614,65 @@ IDirect3DDeviceImpl_7_ComputeSphereVisibility(IDirect3DDevice7 *iface,
                                               DWORD Flags,
                                               DWORD *ReturnValues)
 {
-    IDirect3DDeviceImpl *This = (IDirect3DDeviceImpl *)iface;
-    FIXME("(%p)->(%p,%p,%08x,%08x,%p): stub!\n", This, Centers, Radii, NumSpheres, Flags, ReturnValues);
-
-    /* the DirectX 7 sdk says that the visibility is computed by
-     * back-transforming the viewing frustum to model space
-     * using the inverse of the combined world, view and projection
-     * matrix. If the matrix can't be reversed, D3DERR_INVALIDMATRIX
-     * is returned.
-     *
-     * Basic implementation idea:
-     * 1) Check if the center is in the viewing frustum
-     * 2) Cut the sphere with the planes of the viewing
-     *    frustum
-     *
-     * ->Center inside the frustum, no intersections:
-     *    Fully visible
-     * ->Center outside the frustum, no intersections:
-     *    Not visible
-     * ->Some intersections: Partially visible
-     *
-     * Implement this call in WineD3D. Either implement the
-     * matrix and vector stuff in WineD3D, or use some external
-     * math library.
-     */
+    D3DMATRIX m, temp;
+    D3DVALUE origin_plane[6];
+    D3DVECTOR vec[6];
+    HRESULT hr;
+    UINT i, j;
+
+    TRACE("(%p)->(%p,%p,%08x,%08x,%p)\n", iface, Centers, Radii, NumSpheres, Flags, ReturnValues);
+
+    hr = IDirect3DDeviceImpl_7_GetTransform(iface, D3DTRANSFORMSTATE_WORLD, &m);
+    if ( hr != DD_OK ) return DDERR_INVALIDPARAMS;
+    hr = IDirect3DDeviceImpl_7_GetTransform(iface, D3DTRANSFORMSTATE_VIEW, &temp);
+    if ( hr != DD_OK ) return DDERR_INVALIDPARAMS;
+    multiply_matrix_D3D_way(&m, &m, &temp);
+
+    hr = IDirect3DDeviceImpl_7_GetTransform(iface, D3DTRANSFORMSTATE_PROJECTION, &temp);
+    if ( hr != DD_OK ) return DDERR_INVALIDPARAMS;
+    multiply_matrix_D3D_way(&m, &m, &temp);
+
+/* Left plane */
+    vec[0].u1.x = m._14 + m._11;
+    vec[0].u2.y = m._24 + m._21;
+    vec[0].u3.z = m._34 + m._31;
+    origin_plane[0] = m._44 + m._41;
+
+/* Right plane */
+    vec[1].u1.x = m._14 - m._11;
+    vec[1].u2.y = m._24 - m._21;
+    vec[1].u3.z = m._34 - m._31;
+    origin_plane[1] = m._44 - m._41;
+
+/* Top plane */
+    vec[2].u1.x = m._14 - m._12;
+    vec[2].u2.y = m._24 - m._22;
+    vec[2].u3.z = m._34 - m._32;
+    origin_plane[2] = m._44 - m._42;
+
+/* Bottom plane */
+    vec[3].u1.x = m._14 + m._12;
+    vec[3].u2.y = m._24 + m._22;
+    vec[3].u3.z = m._34 + m._32;
+    origin_plane[3] = m._44 + m._42;
+
+/* Front plane */
+    vec[4].u1.x = m._13;
+    vec[4].u2.y = m._23;
+    vec[4].u3.z = m._33;
+    origin_plane[4] = m._43;
+
+/* Back plane*/
+    vec[5].u1.x = m._14 - m._13;
+    vec[5].u2.y = m._24 - m._23;
+    vec[5].u3.z = m._34 - m._33;
+    origin_plane[5] = m._44 - m._43;
+
+    for(i=0; i<NumSpheres; i++)
+    {
+        ReturnValues[i] = 0;
+        for(j=0; j<6; j++) ReturnValues[i] |= in_plane(j, vec[j], origin_plane[j], Centers[i], Radii[i]);
+    }
 
     return D3D_OK;
 }
diff --git a/dlls/ddraw/tests/d3d.c b/dlls/ddraw/tests/d3d.c
index f5927bea512..405edc946cf 100644
--- a/dlls/ddraw/tests/d3d.c
+++ b/dlls/ddraw/tests/d3d.c
@@ -2753,9 +2753,9 @@ static void SetMaterialTest(void)
 static void ComputeSphereVisibility(void)
 {
     D3DMATRIX proj, view, world;
-    D3DVALUE radius;
-    D3DVECTOR center;
-    DWORD result[1];
+    D3DVALUE radius[3];
+    D3DVECTOR center[3];
+    DWORD result[3];
     HRESULT rc;
 
     world._11=1.0; world._12=0.0; world._13=0.0; world._14=0.0;
@@ -2773,25 +2773,36 @@ static void ComputeSphereVisibility(void)
     proj._31=0.000000; proj._32=0.000000; proj._33=1.020408, proj._34=1.000000;
     proj._41=0.000000; proj._42=0.000000; proj._43=-0.102041; proj._44=0.000000;
 
-    center.x=11.461533;
-    center.y=-4.761727;
-    center.z=-1.171646;
-
-    radius=38.252632;
-
     IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_WORLD, &world);
     IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_VIEW , &view);
     IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_PROJECTION, &proj);
 
-    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, &center, &radius, 1, 0, result);
+    center[0].x=11.461533;
+    center[0].y=-4.761727;
+    center[0].z=-1.171646;
+
+    radius[0]=38.252632;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
 
     ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
-    todo_wine ok(result[0] == 0x3f, "Expected 0x3f, got %x\n", result[0]);
+    ok(result[0] == 0x3f, "Expected 0x3f, got %x\n", result[0]);
 
-    world._11=1.0; world._12=0.0; world._13=0.0; world._14=0.0;
-    world._21=0.0; world._22=1.0; world._23=0.0; world._24=0.0;
-    world._31=0.0; world._32=0.0; world._33=1.0; world._34=0.0;
-    world._41=0.0; world._42=0.0; world._43=0.0; world._44=1.0;
+    center[0].x=-3.515620; center[0].y=-1.560661; center[0].z=-12.464638;
+    radius[0]=4.354097;
+    center[1].x=14.290396; center[1].y=-2.981143; center[1].z=-24.311312;
+    radius[1]=12.500704;
+    center[2].x=1.461626; center[2].y=-6.093709, center[2].z=-13.901010;
+    radius[2]=17.251318;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 3, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x103d, "Expected 0x103d, got %x\n", result[0]);
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[1] == 0x3f, "Expected 0x3f, got %x\n", result[1]);
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[2] == 0x3f, "Expected 0x3f, got %x\n", result[2]);
 
     view._11=1.0; view._12=0.0; view._13=0.0; view._14=0.0;
     view._21=0.0; view._22=1.0; view._23=0.0; view._24=0.0;
@@ -2803,80 +2814,125 @@ static void ComputeSphereVisibility(void)
     proj._31=0.0; proj._32=0.0; proj._33=10.0, proj._34=0.0;
     proj._41=0.0; proj._42=0.0; proj._43=0.0; proj._44=1.0;
 
-    center.x=0.0;
-    center.y=0.0;
-    center.z=0.05;
+    center[0].x=0.0;
+    center[0].y=0.0;
+    center[0].z=0.05;
 
-    radius=0.04;
+    radius[0]=0.04;
 
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_WORLD, &world);
     IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_VIEW , &view);
     IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_PROJECTION, &proj);
 
-    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, &center, &radius, 1, 0, result);
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
 
     ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
-    todo_wine ok(result[0] == 0x0, "Expected 0x0, got %x\n", result[0]);
-
-    world._11=1.0; world._12=0.0; world._13=0.0; world._14=0.0;
-    world._21=0.0; world._22=1.0; world._23=0.0; world._24=0.0;
-    world._31=0.0; world._32=0.0; world._33=1.0; world._34=0.0;
-    world._41=0.0; world._42=0.0; world._43=0.0; world._44=1.0;
-
-    view._11=1.0; view._12=0.0; view._13=0.0; view._14=0.0;
-    view._21=0.0; view._22=1.0; view._23=0.0; view._24=0.0;
-    view._31=0.0; view._32=0.0; view._33=1.0; view._34=0.0;
-    view._41=0.0; view._42=0.0; view._43=0.0; view._44=1.0;
+    ok(result[0] == 0x0, "Expected 0x0, got %x\n", result[0]);
 
     proj._11=1.0; proj._12=0.0; proj._13=0.0; proj._14=0.0;
     proj._21=0.0; proj._22=1.0; proj._23=0.0, proj._24=0.0;
     proj._31=0.0; proj._32=0.0; proj._33=1.0, proj._34=0.0;
     proj._41=0.0; proj._42=0.0; proj._43=0.0; proj._44=1.0;
 
-    center.x=0.0;
-    center.y=0.0;
-    center.z=0.5;
+    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_PROJECTION, &proj);
 
-    radius=0.5;
+    center[0].x=0.0;
+    center[0].y=0.0;
+    center[0].z=0.5;
 
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_WORLD, &world);
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_VIEW , &view);
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_PROJECTION, &proj);
+    radius[0]=0.5;
 
-    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, &center, &radius, 1, 0, result);
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
 
     ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
-    todo_wine ok(result[0] == 0x0, "Expected 0x0, got %x\n", result[0]);
+    ok(result[0] == 0x0, "Expected 0x0, got %x\n", result[0]);
 
-    world._11=1.0; world._12=0.0; world._13=0.0; world._14=0.0;
-    world._21=0.0; world._22=1.0; world._23=0.0; world._24=0.0;
-    world._31=0.0; world._32=0.0; world._33=1.0; world._34=0.0;
-    world._41=0.0; world._42=0.0; world._43=0.0; world._44=1.0;
+    center[0].x=0.0;
+    center[0].y=0.0;
+    center[0].z=0.0;
 
-    view._11=1.0; view._12=0.0; view._13=0.0; view._14=0.0;
-    view._21=0.0; view._22=1.0; view._23=0.0; view._24=0.0;
-    view._31=0.0; view._32=0.0; view._33=1.0; view._34=0.0;
-    view._41=0.0; view._42=0.0; view._43=0.0; view._44=1.0;
+    radius[0]=0.0;
 
-    proj._11=1.0; proj._12=0.0; proj._13=0.0; proj._14=0.0;
-    proj._21=0.0; proj._22=1.0; proj._23=0.0, proj._24=0.0;
-    proj._31=0.0; proj._32=0.0; proj._33=1.0, proj._34=0.0;
-    proj._41=0.0; proj._42=0.0; proj._43=0.0; proj._44=1.0;
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
 
-    center.x=0.0;
-    center.y=0.0;
-    center.z=0.0;
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x0, "Expected 0x0, got %x\n", result[0]);
 
-    radius=0.0;
+    center[0].x=-1.0;
+    center[0].y=-1.0;
+    center[0].z=0.50;
 
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_WORLD, &world);
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_VIEW , &view);
-    IDirect3DDevice7_SetTransform(lpD3DDevice, D3DTRANSFORMSTATE_PROJECTION, &proj);
+    radius[0]=0.25;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x9, "Expected 0x9, got %x\n", result[0]);
+
+    center[0].x=-20.0;
+    center[0].y=0.0;
+    center[0].z=0.50;
+
+    radius[0]=3.0;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x103d, "Expected 0x103d, got %x\n", result[0]);
+
+    center[0].x=20.0;
+    center[0].y=0.0;
+    center[0].z=0.50;
+
+    radius[0]=3.0f;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x203e, "Expected 0x203e, got %x\n", result[0]);
+
+    center[0].x=0.0;
+    center[0].y=-20.0;
+    center[0].z=0.50;
+
+    radius[0]=3.0;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x803b, "Expected 0x803b, got %x\n", result[0]);
+
+    center[0].x=0.0;
+    center[0].y=20.0;
+    center[0].z=0.5;
+
+    radius[0]=3.0;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x4037, "Expected 0x4037, got %x\n", result[0]);
+
+    center[0].x=0.0;
+    center[0].y=0.0;
+    center[0].z=-20;
+
+    radius[0]=3.0;
+
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
+
+    ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
+    ok(result[0] == 0x1001f, "Expected 0x1001f, got %x\n", result[0]);
+
+    center[0].x=0.0;
+    center[0].y=0.0;
+    center[0].z=20.0;
+
+    radius[0]=3.0;
 
-    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, &center, &radius, 1, 0, result);
+    rc = IDirect3DDevice7_ComputeSphereVisibility(lpD3DDevice, center, radius, 1, 0, result);
 
     ok(rc == D3D_OK, "Expected D3D_OK, received %x\n", rc);
-    todo_wine ok(result[0] == 0x0, "Expected 0x0, got %x\n", result[0]);
+    ok(result[0] == 0x2002f, "Expected 0x2002f, got %x\n", result[0]);
 }
 
 START_TEST(d3d)
diff --git a/dlls/ddraw/utils.c b/dlls/ddraw/utils.c
index 68de225640e..a7cef33ca2c 100644
--- a/dlls/ddraw/utils.c
+++ b/dlls/ddraw/utils.c
@@ -1182,6 +1182,31 @@ multiply_matrix(D3DMATRIX *dest,
     memcpy(dest, &temp, 16 * sizeof(D3DVALUE));
 }
 
+void multiply_matrix_D3D_way(D3DMATRIX* result, const D3DMATRIX *m1, const D3DMATRIX *m2)
+{
+    D3DMATRIX temp;
+
+    temp._11 = m1->_11 * m2->_11 + m1->_12 * m2->_21 + m1->_13 * m2->_31 + m1->_14 * m2->_41;
+    temp._12 = m1->_11 * m2->_12 + m1->_12 * m2->_22 + m1->_13 * m2->_32 + m1->_14 * m2->_42;
+    temp._13 = m1->_11 * m2->_13 + m1->_12 * m2->_23 + m1->_13 * m2->_33 + m1->_14 * m2->_43;
+    temp._14 = m1->_11 * m2->_14 + m1->_12 * m2->_24 + m1->_13 * m2->_34 + m1->_14 * m2->_44;
+    temp._21 = m1->_21 * m2->_11 + m1->_22 * m2->_21 + m1->_23 * m2->_31 + m1->_24 * m2->_41;
+    temp._22 = m1->_21 * m2->_12 + m1->_22 * m2->_22 + m1->_23 * m2->_32 + m1->_24 * m2->_42;
+    temp._23 = m1->_21 * m2->_13 + m1->_22 * m2->_23 + m1->_23 * m2->_33 + m1->_24 * m2->_43;
+    temp._24 = m1->_21 * m2->_14 + m1->_22 * m2->_24 + m1->_23 * m2->_34 + m1->_24 * m2->_44;
+    temp._31 = m1->_31 * m2->_11 + m1->_32 * m2->_21 + m1->_33 * m2->_31 + m1->_34 * m2->_41;
+    temp._32 = m1->_31 * m2->_12 + m1->_32 * m2->_22 + m1->_33 * m2->_32 + m1->_34 * m2->_42;
+    temp._33 = m1->_31 * m2->_13 + m1->_32 * m2->_23 + m1->_33 * m2->_33 + m1->_34 * m2->_43;
+    temp._34 = m1->_31 * m2->_14 + m1->_32 * m2->_24 + m1->_33 * m2->_34 + m1->_34 * m2->_44;
+    temp._41 = m1->_41 * m2->_11 + m1->_42 * m2->_21 + m1->_43 * m2->_31 + m1->_44 * m2->_41;
+    temp._42 = m1->_41 * m2->_12 + m1->_42 * m2->_22 + m1->_43 * m2->_32 + m1->_44 * m2->_42;
+    temp._43 = m1->_41 * m2->_13 + m1->_42 * m2->_23 + m1->_43 * m2->_33 + m1->_44 * m2->_43;
+    temp._44 = m1->_41 * m2->_14 + m1->_42 * m2->_24 + m1->_43 * m2->_34 + m1->_44 * m2->_44;
+
+    *result = temp;
+
+    return;
+}
 
 HRESULT
 hr_ddraw_from_wined3d(HRESULT hr)
-- 
2.11.4.GIT