Bug 44666

Summary: Expose Vector3 and associated operations
Product: WebKit Reporter: Kenneth Russell <kbr>
Component: Layout and RenderingAssignee: Kenneth Russell <kbr>
Status: RESOLVED INVALID    
Severity: Normal CC: cmarrin, crogers, dglazkov, jamesr, senorblanco, simon.fraser, vangelis, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Bug Depends on:    
Bug Blocks: 44729    
Attachments:
Description Flags
Patch
dglazkov: review+, kbr: commit-queue-
Roll out of previous patch cmarrin: review+, kbr: commit-queue-

Description Kenneth Russell 2010-08-25 23:13:56 PDT
In order to implement cross-platform GPU accelerated path rendering on top of GraphicsContext3D, a Vector3 class and certain basic operations (dot product, cross product, etc.) are needed. Since these operations mostly already exist in TransformationMatrix.cpp, we should move them to a Vector3 class in TransformationMatrix.h.
Comment 1 Kenneth Russell 2010-08-25 23:32:27 PDT
Created attachment 65529 [details]
Patch

Full LayoutTest run is still underway; will post an update if there appear to be any failures caused by these changes.
Comment 2 Stephen White 2010-08-26 06:28:03 PDT
Comment on attachment 65529 [details]
Patch

WebCore/platform/graphics/transforms/TransformationMatrix.h:91
 +      Vector3& operator =(const Vector3& v)
Normally operator= should check for self-assignment.  Not deadly in this case, though.

Looks good to me.
Comment 3 Kenneth Russell 2010-08-26 10:27:21 PDT
All layout tests passed with these changes.
Comment 4 Dimitri Glazkov (Google) 2010-08-26 10:30:52 PDT
Comment on attachment 65529 [details]
Patch

ok.
Comment 5 Kenneth Russell 2010-08-26 10:52:26 PDT
Committed r66113: <http://trac.webkit.org/changeset/66113>
Comment 6 Chris Marrin 2010-08-26 11:44:10 PDT
Wow, that was fast. A change like this really needs to allow for more time to comment.

Why didn't you just add the needed methods to FloatPoint3D and use that? I don't like the proliferation of redundant classes. If it's the fact that FloatPoint3D uses float and TransformationMatrix uses doubles, then we need to address that. Maybe FloatPoint3D should use doubles, or TransformationMatrix should use floats. If we do need a set of double-based point classes in addition to the float-based ones, we should at least name them better, like DoublePoint3D or something.
Comment 7 Kenneth Russell 2010-08-26 12:00:39 PDT
(In reply to comment #6)
> Wow, that was fast. A change like this really needs to allow for more time to comment.

Sorry, I have a bunch of dependent patches to land and really wanted to get unblocked. We can adjust the code as necessary.

> Why didn't you just add the needed methods to FloatPoint3D and use that? I don't like the proliferation of redundant classes. If it's the fact that FloatPoint3D uses float and TransformationMatrix uses doubles, then we need to address that. Maybe FloatPoint3D should use doubles, or TransformationMatrix should use floats. If we do need a set of double-based point classes in addition to the float-based ones, we should at least name them better, like DoublePoint3D or something.

I'd be very happy to use single precision arithmetic for the work I'm doing. The name "FloatPoint3D" seems  a poor choice, especially when adding operations like cross products which conceptually operate on vectors. This is the primary reason I exposed the Vector3 class and moved the v3Dot, v3Cross, etc. operations from TransformationMatrix.cpp into it.

My preference would be to rename FloatPoint to Vector2 and FloatPoint3D to Vector3, fill them out with the needed operations, and change TransformationMatrix to operate upon them. I'd also ideally like to change TransformationMatrix to use single-precision arithmetic. I gather that the latter change may require lots of layout tests to be rebaselined. One idea would be to parameterize the Vector2, Vector3 and TransformationMatrix types on float or double.
Comment 8 Simon Fraser (smfr) 2010-08-26 12:02:24 PDT
(In reply to comment #7)

> My preference would be to rename FloatPoint to Vector2 and FloatPoint3D to Vector3

I think we want to keep the names FloatPoint2D and FloatPoint3D in the rest of the code. But they could just inherit from Vector*.
Comment 9 Chris Marrin 2010-08-26 12:47:29 PDT
Here is the change of TransformationMatrix to doubles: http://trac.webkit.org/changeset/40761

A lot of tests had to be changed, but the changes were minor and should be easy to change back. I agree with Simon that we should leave FloatPoint and FloatPoint3D as is. How about changing TransformationMatrix to use floats, and add a FloatVector3 (in a separate file) as a subclass of FloatPoint3D? I chose FloatVector3 rather than FloatVector3D because then the corresponding homogenous vector would be FloatVector4D which is not the right nomenclature.

I'm not saying that we need a homogeneous vector right now, but we may well need one in the future, especially if we intend to do projection into a device coordinate space (in software), so we should provide for the possibility.
Comment 10 Kenneth Russell 2010-08-26 17:19:24 PDT
What about AffineTransform and the various TransformOperations, which also operate on doubles?

There may ultimately be good reason for doing this arithmetic using doubles. For large displays I'm not sure single-precision floating point numbers can address sub-pixel locations with sufficient accuracy. Do you have any thoughts on this?

What about the thought to make TransformMatrix a template class with double as the default type parameter, but allowing it to be constructed with float as the type parameter? We could then add similar Vector2, Vector3 and Vector4 classes, and change FloatPoint and FloatPoint3D to inherit from Vector2<float> and Vector3<float>.
Comment 11 Chris Marrin 2010-08-30 06:53:33 PDT
(In reply to comment #10)
> What about AffineTransform and the various TransformOperations, which also operate on doubles?
> 
> There may ultimately be good reason for doing this arithmetic using doubles. For large displays I'm not sure single-precision floating point numbers can address sub-pixel locations with sufficient accuracy. Do you have any thoughts on this?

That was certainly in my mind when I made this change. I believe the big motivation for this had to do with the fact that the TransformOperations use doubles because they are reflected in JS and JS uses doubles. And TransformationMatrix is reflected into JS via CSSMatrix. So the longer we stayed in doubles, the better off we were. We ultimately have to downcast to floats for WebGL and affine matrices for CG (and probably most other 2D libraries), so the question is just how long you stay in doubles. The problem with the way it was before is that we were bouncing back and forth between float and double on every JS call, which gets inefficient. 

Modern hardware (even mobile hardware) has a FP unit which can do double arithmetic as fast as float for most things (division is often a bit slower, but not much). So casting between double and float is the only expensive operation here. So, add in your argument of better precision and it's probably best to just stick with doubles.

> 
> What about the thought to make TransformMatrix a template class with double as the default type parameter, but allowing it to be constructed with float as the type parameter? We could then add similar Vector2, Vector3 and Vector4 classes, and change FloatPoint and FloatPoint3D to inherit from Vector2<float> and Vector3<float>.

I don't think we need to go that far, we just need to decide which we want and stick with that.

So let's stick with doubles. Maybe it would be best to make a Point3 class, which is a double version of FloatPoint3D, and then subclass Vector3 from that. This gives us the opportunity to switch from FloatPoint3D to Point3 down the road. These classes should be in separate files.
Comment 12 Stephen White 2010-08-30 07:01:37 PDT
(In reply to comment #11)
> (In reply to comment #10)
> > What about AffineTransform and the various TransformOperations, which also operate on doubles?
> > 
> > There may ultimately be good reason for doing this arithmetic using doubles. For large displays I'm not sure single-precision floating point numbers can address sub-pixel locations with sufficient accuracy. Do you have any thoughts on this?
> 
> That was certainly in my mind when I made this change. I believe the big motivation for this had to do with the fact that the TransformOperations use doubles because they are reflected in JS and JS uses doubles. And TransformationMatrix is reflected into JS via CSSMatrix. So the longer we stayed in doubles, the better off we were. We ultimately have to downcast to floats for WebGL and affine matrices for CG (and probably most other 2D libraries), so the question is just how long you stay in doubles. The problem with the way it was before is that we were bouncing back and forth between float and double on every JS call, which gets inefficient. 
> 
> Modern hardware (even mobile hardware) has a FP unit which can do double arithmetic as fast as float for most things (division is often a bit slower, but not much). So casting between double and float is the only expensive operation here. So, add in your argument of better precision and it's probably best to just stick with doubles.

Just to play devil's advocate, it also means twice the cost of memory bandwidth for loads and stores.  Also, SSE2 is capable of 4-wide single-precision ops, but only 2-wide double-precision ops, so it would halve the throughput too (although this code doesn't use SSE2 yet AFAIK).  Finally, using doubles also means 80bit on x64 FPU, but then 64bit on other platforms and when using SSE2, which can cause differing test results.

> > What about the thought to make TransformMatrix a template class with double as the default type parameter, but allowing it to be constructed with float as the type parameter? We could then add similar Vector2, Vector3 and Vector4 classes, and change FloatPoint and FloatPoint3D to inherit from Vector2<float> and Vector3<float>.
> 
> I don't think we need to go that far, we just need to decide which we want and stick with that.
> 
> So let's stick with doubles. Maybe it would be best to make a Point3 class, which is a double version of FloatPoint3D, and then subclass Vector3 from that. This gives us the opportunity to switch from FloatPoint3D to Point3 down the road. These classes should be in separate files.
Comment 13 Kenneth Russell 2010-08-30 12:18:29 PDT
Created attachment 65937 [details]
Roll out of previous patch

I'm rolling out the previous patch because we are definitely going to take a different approach. Most immediately I will probably add a cross product to FloatPoint3D, but regardless of how we proceed we definitely don't want the previous change.
Comment 14 WebKit Review Bot 2010-08-30 12:20:46 PDT
Attachment 65937 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/transforms/TransformationMatrix.cpp:265:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/platform/graphics/transforms/TransformationMatrix.cpp:266:  l is incorrectly named. Don't use the single letter 'l' as an identifier name.  [readability/naming] [4]
Total errors found: 2 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 15 Chris Marrin 2010-08-30 15:16:19 PDT
Comment on attachment 65937 [details]
Roll out of previous patch

r+
Comment 16 Kenneth Russell 2010-08-30 15:24:47 PDT
Note: fixing OOPS in ChangeLog while landing.
Comment 17 Kenneth Russell 2010-08-30 15:28:23 PDT
Committed r66416: <http://trac.webkit.org/changeset/66416>
Comment 18 Kenneth Russell 2010-08-30 15:29:10 PDT
Updating the status of this bug to "Resolved Invalid".
Comment 19 Chris Marrin 2010-08-30 16:57:17 PDT
(In reply to comment #12)
> (In reply to comment #11)
> > (In reply to comment #10)
> > > What about AffineTransform and the various TransformOperations, which also operate on doubles?
> > > 
> > > There may ultimately be good reason for doing this arithmetic using doubles. For large displays I'm not sure single-precision floating point numbers can address sub-pixel locations with sufficient accuracy. Do you have any thoughts on this?
> > 
> > That was certainly in my mind when I made this change. I believe the big motivation for this had to do with the fact that the TransformOperations use doubles because they are reflected in JS and JS uses doubles. And TransformationMatrix is reflected into JS via CSSMatrix. So the longer we stayed in doubles, the better off we were. We ultimately have to downcast to floats for WebGL and affine matrices for CG (and probably most other 2D libraries), so the question is just how long you stay in doubles. The problem with the way it was before is that we were bouncing back and forth between float and double on every JS call, which gets inefficient. 
> > 
> > Modern hardware (even mobile hardware) has a FP unit which can do double arithmetic as fast as float for most things (division is often a bit slower, but not much). So casting between double and float is the only expensive operation here. So, add in your argument of better precision and it's probably best to just stick with doubles.
> 
> Just to play devil's advocate, it also means twice the cost of memory bandwidth for loads and stores.  Also, SSE2 is capable of 4-wide single-precision ops, but only 2-wide double-precision ops, so it would halve the throughput too (although this code doesn't use SSE2 yet AFAIK).  Finally, using doubles also means 80bit on x64 FPU, but then 64bit on other platforms and when using SSE2, which can cause differing test results.

This issue clearly intends to never die. Your memory bandwidth and 80 bit vs 64 bit arguments are unconvincing. Unfortunately, your SSE2 argument is a very good one :-) I've been thinking for a while that I wanted to make an SSE version of TransformationMatrix, along with some other changes that make it more WebGL friendly.

So it really comes down to the choice between precision and performance. As far as precision goes, OpenGL seems to do quite well with single precision math. Of course, you can finesse the data sent to the GPU to expand the range while keeping within 32 bit floats. So there is still an argument for having the extra precision at the higher levels. Of course we don't give authors any tools at all to help finesse the numbers, so doing double arithmetic is most likely just wasted when it comes to WebGL or any other rendering library that uses 32 bit floats.

Ken, you've said you will now put your Vector3 logic into FloatPoint3D. Is your intent to change FloatPoint3D to doubles? If not, then it seems clear that TransformationMatrix should be changed back to floats. All the TransformOperations are just interfaces to JS so we can keep doubles there and narrow them when sent into TransformationMatrix. 

If we (finally) agree, we should open a new bug for this work. I am happy to do it since I'm the one who got us into this in the first place.
Comment 20 Kenneth Russell 2010-08-30 17:03:58 PDT
(In reply to comment #19)
> Ken, you've said you will now put your Vector3 logic into FloatPoint3D. Is your intent to change FloatPoint3D to doubles? If not, then it seems clear that TransformationMatrix should be changed back to floats. All the TransformOperations are just interfaces to JS so we can keep doubles there and narrow them when sent into TransformationMatrix. 

No, I'm going to leave FloatPoint3D as floats. From my standpoint the only operation missing on FloatPoint3D is cross product.

> If we (finally) agree, we should open a new bug for this work. I am happy to do it since I'm the one who got us into this in the first place.

Yes, I've already closed this one as invalid.

Note that Chris Rogers recently landed wtf/Vector3.h, which I also hadn't realized when I landed the first of the above two patches. We'll want to avoid code and class duplication when deciding what refactoring to do.