Closed Bug 1292390 Opened 8 years ago Closed 8 years ago

Add BSP tree implementation

Categories

(Core :: Graphics: Layers, defect)

Product:
Core
Component:
Graphics: Layers
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla51
Tracking Flags:
Tracking Status
firefox51 --- fixed

People

(Reporter: mikokm, Assigned: mikokm)

References

Details

Attachments

(2 files, 8 obsolete files)

Add Polygon data structure.
58 bytes, text/x-review-board-request
jrmuizel
: review+
kip
: review+
Details
Bug 1292390 - Add BSP tree implementation
58 bytes, text/x-review-board-request
jrmuizel
: review+
kip
: review+
Details 
This bug is about adding a BSP tree implementation, which is a prerequisite for bug 1274673 and ultimately bug 689498.
Attachment #8778020 - Flags: review?(kgilbert)
Attachment #8778020 - Flags: review?(jmuizelaar)
Attachment #8778021 - Flags: review?(kgilbert)
Attachment #8778021 - Flags: review?(jmuizelaar)
The unit tests were created with Chromium as a reference implementation.
https://reviewboard.mozilla.org/r/69392/#review66554

::: gfx/2d/Polygon.h:47
(Diff revision 1)
> +  BasePolygon3D& operator=(BasePolygon3D && aOther)
> +  {
> +    mPoints = std::move(aOther.mPoints);
> +    mNormal = std::move(aOther.mNormal);
> +    return *this;
> +  }

I believe the implicit copy constructor, move constructor and move assignment operator should be sufficient.
https://reviewboard.mozilla.org/r/69392/#review66778

::: gfx/2d/Polygon.h:33
(Diff revision 1)
> +  explicit BasePolygon3D(const nsTArray<Point3DTyped<Units>>& aPoints)
> +    : mPoints(aPoints)
> +  {
> +    CalculateNormal();
> +  }
> +

This should probably have a constructor that takes an r-value reference:

  explicit BasePolygon3D(const nsTArray<Point3DTyped<Units>>&& aPoints)
    : mPoints(std::move(aPoints))
{
    CalculateNormal();
}

If we don't need the l-value reference constructor we can probably drop it.
https://reviewboard.mozilla.org/r/69394/#review66772

::: gfx/layers/BSPTree.cpp:15
(Diff revision 1)
> +namespace layers {
> +
> +namespace {
> +
> +static int signum(float d) {
> +  if (d > 0) return 1;

Let's just call this sign()

::: gfx/layers/BSPTree.cpp:75
(Diff revision 1)
> +      aPos++;
> +    } else if (dot < -epsilon) {
> +      aNeg++;
> +    } else {
> +      // The point is within the thick plane.
> +      dotProducts[dotProducts.Length() - 1] = 0.0f;

How about making this dot = 0.0
and moving the dotProducts.AppendElement(dot) below.

::: gfx/layers/BSPTree.cpp:100
(Diff revision 1)
> +    nsTArray<float> dots = CalculateDotProduct(splittingPlane, polygon,
> +                                               pos, neg);
> +
> +    // Back polygon
> +    if (pos == 0 && neg > 0) {
> +      backPolygons.push_back(polygon);

Chrome avoids copying polygons we probably should too.
https://reviewboard.mozilla.org/r/69392/#review66828

::: gfx/2d/Polygon.h:68
(Diff revision 1)
> +  }
> +
> +private:
> +  void CalculateNormal()
> +  {
> +    MOZ_ASSERT(mPoints.Length() >= 3);

A comment here may be useful here to describe how the normal will relate to the winding order of the polygon.

::: gfx/2d/Polygon.h:71
(Diff revision 1)
> +  void CalculateNormal()
> +  {
> +    MOZ_ASSERT(mPoints.Length() >= 3);
> +
> +    // This normal calculation method works only for planar polygons.
> +    mNormal = (mPoints[1] - mPoints[0]).CrossProduct(mPoints[2] - mPoints[0]);

This will work in all cases where a polygon is a quad or triangle; however, this may fail in a couple of scenarios:

mPoints[0], mPoints[1], or mPoints[2] are equal or very close to one another.

The vector formed by mPoints[0] -> mPoints[1] and the vector formed by mPoints[0] -> mPoints[2] are pointing in nearly the same direction.

The Normalize() function may fail if passed in a zero-length vector.

::: gfx/2d/Polygon.h:72
(Diff revision 1)
> +  {
> +    MOZ_ASSERT(mPoints.Length() >= 3);
> +
> +    // This normal calculation method works only for planar polygons.
> +    mNormal = (mPoints[1] - mPoints[0]).CrossProduct(mPoints[2] - mPoints[0]);
> +    mNormal.Normalize();

Perhaps you could detect when mNormal's length is very small (epsilon) and if so, try a new set of points until you find ones that can be used to find the normal.
https://reviewboard.mozilla.org/r/69394/#review66832

::: gfx/layers/BSPTree.cpp:1
(Diff revision 1)
> +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-

This is looking good!  r=me with :jrmuizel's feedback applied.
https://reviewboard.mozilla.org/r/69392/#review66834

This is looking good.  Just need to handle the exceptions in CalculateNormal()
Comment on attachment 8778021 [details]
Bug 1292390 - Add BSP tree implementation

https://reviewboard.mozilla.org/r/69394/#review66836

r=me with :jrmuizel's feedback addressed.
Attachment #8778021 - Flags: review?(kgilbert) → review+
Attachment #8778020 - Flags: review?(kgilbert) → review-
Comment on attachment 8778020 [details]
Add Polygon data structure.

https://reviewboard.mozilla.org/r/69392/#review66838

This is looking very good.  Just see the edge cases to handle and the same feedback as :jrmuizel
Attachment #8779540 - Flags: review?(jmuizelaar)
Attachment #8779541 - Flags: review?(kgilbert)
Attachment #8779542 - Flags: review?(kgilbert)
Attachment #8779543 - Flags: review?(jmuizelaar)
Attachment #8779544 - Flags: review?(jmuizelaar)
Attachment #8779545 - Flags: review?(jmuizelaar)
Attachment #8779546 - Flags: review?(jmuizelaar)
Attachment #8779547 - Flags: review?(kgilbert)
Comment on attachment 8778020 [details]
Add Polygon data structure.

https://reviewboard.mozilla.org/r/69392/#review67860

r=me with those changes once jrmuizel is happy with fixes for his comments.
Attachment #8778020 - Flags: review?(kgilbert) → review+
Comment on attachment 8779547 [details]
Fix Windows compiler error

https://reviewboard.mozilla.org/r/70524/#review67852

<p>r=me once the extra "f" (from search-and-replace?) is removed or if this was intentional.</p>

::: gfx/tests/gtest/TestBSPTree.cpp:385
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate0) {
> +TEST(BSPTree, TwoPlaneIntersectRotate0f) {

Did you mean to add the "f" here?

Perhaps a search-and-replace caught it?

::: gfx/tests/gtest/TestBSPTree.cpp:424
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate20) {
> +TEST(BSPTree, TwoPlaneIntersectRotate20f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:463
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate40) {
> +TEST(BSPTree, TwoPlaneIntersectRotate40f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:502
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate60) {
> +TEST(BSPTree, TwoPlaneIntersectRotate60f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:541
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate80) {
> +TEST(BSPTree, TwoPlaneIntersectRotate80f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:580
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate100) {
> +TEST(BSPTree, TwoPlaneIntersectRotate100f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:619
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate120) {
> +TEST(BSPTree, TwoPlaneIntersectRotate120f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:658
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate140) {
> +TEST(BSPTree, TwoPlaneIntersectRotate140f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:697
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate160) {
> +TEST(BSPTree, TwoPlaneIntersectRotate160f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:736
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate180) {
> +TEST(BSPTree, TwoPlaneIntersectRotate180f) {

Another "f" at the end here, maybe from search-and-replace?

::: gfx/tests/gtest/TestBSPTree.cpp:775
(Diff revision 1)
>      }
>    };
>    ::RunTest(polygons, expected);
>  }
>  
> -TEST(BSPTree, TwoPlaneIntersectRotate200) {
> +TEST(BSPTree, TwoPlaneIntersectRotate200f) {

Looks like a few of these below as well.
Attachment #8779547 - Flags: review?(kgilbert) → review+
Comment on attachment 8779542 [details]
Add missing explicit keyword

https://reviewboard.mozilla.org/r/70514/#review67854

::: gfx/layers/BSPTree.h:23
(Diff revision 1)
>  
>  // Represents a node in a BSP tree. The node contains at least one polygon that
>  // is used as a splitting plane, and at most two child nodes that represent the
>  // splitting planes that further subdivide the space.
>  struct BSPTreeNode {
> -  BSPTreeNode(const gfx::Polygon3D& aPolygon)
> +  explicit BSPTreeNode(const gfx::Polygon3D& aPolygon)

Looks good to me!
Attachment #8779542 - Flags: review?(kgilbert) → review+
Comment on attachment 8779541 [details]
Make CalculateNormal() more robust

https://reviewboard.mozilla.org/r/70512/#review67856

r=me if you add a comment about the winding order to CalculateNormal

::: gfx/2d/Polygon.h:51
(Diff revision 1)
>      MOZ_ASSERT(mPoints.Length() > aIndex);
>      return mPoints[aIndex];
>    }
>  
>  private:
>    void CalculateNormal()

Moved issue from previous changeset:

A comment here may be useful here to describe how the normal will relate to the winding order of the polygon.

::: gfx/2d/Polygon.h:57
(Diff revision 1)
>    {
>      MOZ_ASSERT(mPoints.Length() >= 3);
>  
>      // This normal calculation method works only for planar polygons.
>      mNormal = (mPoints[1] - mPoints[0]).CrossProduct(mPoints[2] - mPoints[0]);
> +

Looks good!
Attachment #8779541 - Flags: review?(kgilbert) → review+
Comment on attachment 8779543 [details]
Use move constructor for points

https://reviewboard.mozilla.org/r/70516/#review68142

Can you flatten this patch set down so that the changes are not separate commits but instead the originals just have the changes applied? (There are ways to do this in hg and git)
Attachment #8779540 - Attachment is obsolete: true
Attachment #8779540 - Flags: review?(jmuizelaar)
Attachment #8779541 - Attachment is obsolete: true
Attachment #8779542 - Attachment is obsolete: true
Attachment #8779543 - Attachment is obsolete: true
Attachment #8779543 - Flags: review?(jmuizelaar)
Attachment #8779544 - Attachment is obsolete: true
Attachment #8779544 - Flags: review?(jmuizelaar)
Attachment #8779545 - Attachment is obsolete: true
Attachment #8779545 - Flags: review?(jmuizelaar)
Attachment #8779546 - Attachment is obsolete: true
Attachment #8779546 - Flags: review?(jmuizelaar)
Attachment #8779547 - Attachment is obsolete: true
Comment on attachment 8778021 [details]
Bug 1292390 - Add BSP tree implementation

https://reviewboard.mozilla.org/r/69394/#review68470

::: gfx/layers/BSPTree.cpp:177
(Diff revision 4)
> +
> +      // Calculate the line segment and plane intersection point.
> +      const gfx::Point3D ab = b - a;
> +      const float dotAB = ab.DotProduct(normal);
> +      const float t = -dotA / dotAB;
> +      const gfx::Point3D p = a + (ab * t);

Chrome's LineIntersectPlane seems to have a much more robust intersection calculation than this one. They seem to make an effort to never divide by a very small number. i.e. total_distance is always >= distance_threshold.
Comment on attachment 8778020 [details]
Add Polygon data structure.

https://reviewboard.mozilla.org/r/69392/#review68474
Attachment #8778020 - Flags: review?(jmuizelaar) → review+
Comment on attachment 8778021 [details]
Bug 1292390 - Add BSP tree implementation

https://reviewboard.mozilla.org/r/69394/#review68470

> Chrome's LineIntersectPlane seems to have a much more robust intersection calculation than this one. They seem to make an effort to never divide by a very small number. i.e. total_distance is always >= distance_threshold.

It seems that this behavior has been removed from the master, and they are currently using similar intersection calculation.
https://cs.chromium.org/chromium/src/cc/quads/draw_polygon.cc?sq=package:chromium&dr=CSs&l=23
https://cs.chromium.org/chromium/src/cc/quads/draw_polygon.cc?sq=package:chromium&dr=CSs&l=275
Ah indeed here's the commit message:
"Perform BSP polygon splitting and orientation selection in a single step.

This eliminates redundant testing of vertices for orientation with
respect to the splitting polygon. Previously, up to 3 sets of tests
were made (once to determine whether the polygon was split, then once
during the split, and then finally to determine the orientation of the
split polygons.

Merging these steps in order to reuse calculated values also eliminates
the possibility that different calculations in testing and splitting
could be inconsistent."

I haven't compared the code closely but do we end up reusing like they do?
Flags: needinfo?(mikokm)
(In reply to Jeff Muizelaar [:jrmuizel] from comment #44)
> Ah indeed here's the commit message:
> "Perform BSP polygon splitting and orientation selection in a single step.
> 
> This eliminates redundant testing of vertices for orientation with
> respect to the splitting polygon. Previously, up to 3 sets of tests
> were made (once to determine whether the polygon was split, then once
> during the split, and then finally to determine the orientation of the
> split polygons.
> 
> Merging these steps in order to reuse calculated values also eliminates
> the possibility that different calculations in testing and splitting
> could be inconsistent."
> 
> I haven't compared the code closely but do we end up reusing like they do?

Yes, we are only calculating the dot products once.
Flags: needinfo?(mikokm)
Comment on attachment 8778021 [details]
Bug 1292390 - Add BSP tree implementation

https://reviewboard.mozilla.org/r/69394/#review68570
Attachment #8778021 - Flags: review?(jmuizelaar) → review+
Keywords: checkin-needed
(In reply to Miko Mynttinen [:miko] from comment #45)
> 
> Yes, we are only calculating the dot products once.

FWIW, it might be worth adding a comment about how the dot products are reused.
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/4357d301465b
Add Polygon data structure. r=jrmuizel, r=kip
https://hg.mozilla.org/integration/mozilla-inbound/rev/538f9779cb43
Add BSP tree implementation. r=jrmuizel, r=kip
Keywords: checkin-needed
Super-nit: I noticed that both of the commits here include new files that end without a newline, as indicated by this warning shown in each of the csets linked in comment 48:
> \ No newline at end of file

In future patches, do make sure to end files with a newline, as noted in one of the "General Practices" here:
 https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Coding_Style#General_C.2FC.2B.2B_Practices

Thanks!
Pushed by dholbert@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a50c6e2ff453
followup: add newline character at the end of Polygon/BSPTree files added in this bug, per coding style guide. (whitespace-only, no review)
https://hg.mozilla.org/mozilla-central/rev/4357d301465b
https://hg.mozilla.org/mozilla-central/rev/538f9779cb43
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
status-firefox51: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla51
Blocks: 1301818
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: