Rasterize 'Bresenham' line segments as parallelograms

The previous 'connected diamonds' polygon that was used to rasterize
Bresenham lines suffered from duplicate rasterization of endpoints,
which violates the diamond exit-rule and is disallowed by the Vulkan
(and OpenGL) spec.

This change rasterizes Bresenham lines as a parallelogram, as described
by Vulkan's non-strictLines algorithm.

This satisfied Vulkan's requirements laid out in section 26.10.2
Bresenham Line Segment Rasterization:

"Implementations may use other line segment rasterization algorithms,
 subject to the following rules:
 - The coordinates of a fragment produced by the algorithm must not
   deviate by more than one unit in either x or y framebuffer
   coordinates from a corresponding fragment produced by the diamond-
   exit rule.
 - The total number of fragments produced by the algorithm must not
   differ from that produced by the diamond-exit rule by no more than
   one.
 - For an x-major line, two fragments that lie in the same framebuffer-
   coordinate column must not be produced (for a y-major line, two
   fragments that lie in the same framebuffer-coordinate row must not be
   produced).
 - If two line segments share a common endpoint, and both segments are
   either x-major (both left-to-right or both right-to-left) or y-mayor
   (both bottom-to-top or both top-to-bottom), then rasterizing both
   segments must not produce duplicate fragments. Fragments also must
   not be omitted so as to interrupt continuity of the connected
   segments."

OpenGL ES line rasterization has not been modified as part of this
change, to not require rebasing of golden images, but the parallelogram
algorithm was made available for easy comparison.

Bug: b/80135519
Change-Id: I09e8b90a393d3a08387d79669d9dbe5f83a0811d
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/38049
Presubmit-Ready: Nicolas Capens <nicolascapens@google.com>
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
Tested-by: Nicolas Capens <nicolascapens@google.com>
Reviewed-by: Chris Forbes <chrisforbes@google.com>
Reviewed-by: Alexis H├ętu <sugoi@google.com>
2 files changed
tree: fd1a7cfb0fde5b4fdaa297a5daeb40c93bf9143f
  1. .dir-locals.el
  2. .gitignore
  3. .gitmodules
  4. .travis.yml
  5. .vscode/
  6. AUTHORS.txt
  7. Android.bp
  8. BUILD.gn
  9. CMakeLists.txt
  10. CMakeSettings.json
  11. CONTRIBUTING.txt
  12. CONTRIBUTORS.txt
  13. LICENSE.txt
  14. OWNERS
  15. README.md
  16. SwiftShader.sln
  17. build/
  18. build_overrides/
  19. docs/
  20. extensions/
  21. include/
  22. src/
  23. tests/
  24. third_party/
README.md

SwiftShader

License Build Status Build status

Introduction

SwiftShader is a high-performance CPU-based implementation of the Vulkan, OpenGL ES, and Direct3D 9 graphics APIs12. Its goal is to provide hardware independence for advanced 3D graphics.

Building

SwiftShader libraries can be built for Windows, Linux, and Mac OS X.
Android and Chrome (OS) build environments are also supported.

  • Visual Studio
    For building the Vulkan ICD library, use Visual Studio 2019 to open the project folder and wait for it to run CMake. Open the CMake Targets View in the Solution Explorer and select the vk_swiftshader project to build it.

    There is also a legacy SwiftShader.sln file for Visual Studio 2017 for building OpenGL ES and Direct3D libraries. Output DLLs will be placed in the out subfolder. Sample executables such as OGLES3ColourGrading can be found under the Tests solution folder and can be run from the IDE.

  • CMake

    Install CMake for Linux, Mac OS X, or Windows and use either the IDE or run the following terminal commands:

    cd build
    cmake ..
    make --jobs=8
    
    ./gles-unittests
    ./OGLES2HelloAPI
    

Usage

The SwiftShader libraries act as drop-in replacements for graphics drivers.

On Windows, most applications can be made to use SwiftShader's DLLs by placing them in the same folder as the executable. On Linux, the LD_LIBRARY_PATH environment variable or -rpath linker option can be used to direct applications to search for shared libraries in the indicated directory first.

Contributing

See CONTRIBUTING.txt for important contributing requirements.

The canonical repository for SwiftShader is hosted at: https://swiftshader.googlesource.com/SwiftShader

All changes must be reviewed and approved in the Gerrit review tool at: https://swiftshader-review.googlesource.com

Authenticate your account here: https://swiftshader-review.googlesource.com/new-password

All changes require a Change-ID tag in the commit message. A commit hook may be used to add this tag automatically, and can be found at: https://gerrit-review.googlesource.com/tools/hooks/commit-msg. To clone the repository and install the commit hook in one go:

git clone https://swiftshader.googlesource.com/SwiftShader && (cd SwiftShader && curl -Lo `git rev-parse --git-dir`/hooks/commit-msg https://gerrit-review.googlesource.com/tools/hooks/commit-msg ; chmod +x `git rev-parse --git-dir`/hooks/commit-msg)

Changes are uploaded to Gerrit by executing:

git push origin HEAD:refs/for/master

Testing

SwiftShader's OpenGL ES implementation can be tested using the dEQP test suite.

See docs/dEQP.md for details.

Third-Party Dependencies

The third_party directory contains projects which originated outside of SwiftShader:

subzero contains a fork of the Subzero project. It is part of Google Chrome‘s (Portable) Native Client project. Its authoritative source is at https://chromium.googlesource.com/native_client/pnacl-subzero/. The fork was made using git-subtree to include all of Subzero’s history, and until further notice it should not diverge from the upstream project. Contributions must be tested using the README instructions, reviewed at https://chromium-review.googlesource.com, and then pulled into the SwiftShader repository.

llvm-subzero contains a minimized set of LLVM dependencies of the Subzero project.

PowerVR_SDK contains a subset of the PowerVR Graphics Native SDK for running several sample applications.

googletest contains the Google Test project, as a Git submodule. It is used for running unit tests for Chromium, and Reactor unit tests. Run git submodule update --init to obtain/update the code. Any contributions should be made upstream.

Documentation

See docs/Index.md.

Contact

Public mailing list: swiftshader@googlegroups.com

General bug tracker: https://g.co/swiftshaderbugs
Chrome specific bugs: https://bugs.chromium.org/p/swiftshader

License

The SwiftShader project is licensed under the Apache License Version 2.0. You can find a copy of it in LICENSE.txt.

Files in the third_party folder are subject to their respective license.

Authors and Contributors

The legal authors for copyright purposes are listed in AUTHORS.txt.

CONTRIBUTORS.txt contains a list of names of individuals who have contributed to SwiftShader. If you‘re not on the list, but you’ve signed the Google CLA and have contributed more than a formatting change, feel free to request to be added.

Disclaimer

  1. Trademarks are the property of their respective owners.
  2. We do not claim official conformance with the Direct3D and OpenGL graphics APIs at this moment.
  3. This is not an official Google product.