2013-02-28: Project update.
-Kernel execution interleaved.
-Patched two memory leaks.
2013-02-10: Project update.
-Objects recursively generate bounds.
-Active pixels from each object are re-processed for all children; inactive pixels are omitted.
-Frame output to window.
This project aims to provide a complete graphics pipeline that provides several advantages over existing raycasting methods:
1. Analytical anti-aliasing.
(a) Based on object geometry.
(b) +Expand to function-defined continuous surfaces.
2. Non-rectilinear camera perspectives.
(a) Minimal performance cost.
(b) Four corners define pixel geometry.
(c) Adjacent pixels share corners.
3. Per-pixel polygon intersection produces an intermediate mesh.
(a) Reflections.
(b) Transmission. (Transparency, refraction, sub-surface scattering, etc.)
(c) Object boundaries may represent various states of matter. (Solid, liquid, gas, etc.)
(d) +Expand to permit any deterministic result based on light-surface interaction.
4. Volumetric lighting.
(a) Fog and atmospheric effects.
(b) Optical effects emerge from scene geometry. (Caustics, lens flares, etc.)
(c) Programmable properties for invisible for scientific analysis. (Radio, infrared, and other radiation propagation.)
Stage 1: Intersect pixel geometry with polygon geometry and crop polygons using planar surfaces defined by the bounds (top, bottom, left, and right) of every pixel. Every pixel in the frame is intersected with every polygon (reduced from total problem size by optimizations).
Stage 2: In pixels where more than one polygon meet or overlap, there will be multiple polygons within the same pixel. These polygons are already cropped to the respective pixel's volume. Sort all relevant polygons by distance from camera and use current polygon to mask the next distant polygon by intersecting the polygons and removing distant sections covered by a closer polygon. Do this until every pixel has no more polygons to intersect and the pixel's mesh is revealed.
Stage 3: As per Stage 2, every pixel will have an associated polygon mesh. The mesh will consist of triangles that comprise a subset of the original polygon set, but they are limited to the volume of the pixel. For every triangle in a given pixel mesh, look up the average color value for the area of the surface that will be represented. This may be done via bitmap sampling or procedurally with a function. Lastly, sum all triangle values, adjusted for distance and visible area, and divide by the area of the pixel.
The result of these stages should produce a final value for each pixel, but if the triangle mesh samples do not return a value and instead depend on a further pass (e.g. transmission through a surface), then the mesh may be stored until the deeper pass returns a value. The recursive nature of this method should permit realistic computation of light using a volumetric approach for each pixel.
Mad Comp Sci technical documentation
Project #1 (Render)
Published 2013-01-23; last revised 2013-01-28.
<Stage 0> - Convert n-sided polygons into triangles. Currently unnecessary, as all polygons used are triangles.
For all planar [polygons] with sides > 3, convert to k equivalent 3-sided polygons. Let n = sum(k) from 0 to [polygons].
setup:
Prior to stage 1, a grid of 3D vectors must be created for use as the corners of each pixel. Because adjacent pixels may share corners, a grid of (x * y) pixels may be represented with an array of (x + 1)*(y + 1) vectors.
As of 2013-01-23, the camera matrix is identical to a traditional projection matrix, but the free nature of the vectors means alternate camera geometry is trivial. A spherical projection could be used instead of rectilinear with no performance penalty.
"Stage 1" - Per-pixel geometry intersection with source [polygons].
_input:
Grid of 3D vectors. 6-float; (x, y, z) (i, j, k)
Arrays of 3D vectors, grouped by [polygons]. (n x i x 3)-float.
(n = number of polygons, <Stage 0> i = 3)
output:
Arrays of 3D vectors, grouped by planar polygons. (n x p x q x 3)-float.
(n see above, p = pixels, q <= 7)
process:
For all pixels in m x n grid, let:
TL = <i, j, k> components of top left corner vector
TR = <i, j, k> components of top right corner vector
BL = <i, j, k> components of bottom left corner vector
BR = <i, j, k> components of bottom right corner vector
TOP = TL x TR = cross(TL, TR)
LEF = TL x BL = cross(TL, BL)
RIG = TR x BR = cross(TR, BR)
BOT = BL x BR = cross(BL, BR)
For all polygons that pass through this pixel:
Let A(x)+B(y)+C(z)+D=0.
Let A, B, C be the <i, j, k> components of the two corners that make up an edge.
Solve D0 for x, y, z in corner vector(s).
Solve Di for x, y, z in polygon vertex i.
Compare D0 and Di (where i is the polygon vertex index).
Depending on the order of the cross products above, greater-than/less-than will indicate the position of the vertex. If the vertex lies "inside" the pixel volume as bound by the edge plane, then the vertex is kept. If a vertex lies "outside" the pixel volume, then the vertex is culled. If all points are outside, the polygon is entirely outside of the pixel, and execution returns.
If a triangle is bisected, one of eight things will happen:
0x0 : All points inside.
No action taken.
0x1 : Vertex A outside; B, C inside.
Vertex A is replaced with the point along the triangle edge AB that exists on the bisecting plane.
Vertex D is added as the point along the triangle edge AC that exists on the bisecting plane.
0x2 : Vertex B outside; A, C inside.
Vertex B is replaced with the point along the triangle edge AB that exists on the bisecting plane.
Vertex D is added as the point along the triangle edge BC that exists on the bisecting plane.
0x3 : Vertex C outside; A, B inside.
Vertex C is replaced with the point along the triangle edge BC that exists on the bisecting plane.
Vertex D is added as the point along the triangle edge AC that exists on the bisecting plane.
0x4 : Vertex A, B outside; C inside.
Vertex A is replaced with the point along the triangle edge AC that exists on the bisecting plane.
Vertex B is added as the point along the triangle edge BC that exists on the bisecting plane.
0x5 : Vertex B, C outside; A inside.
Vertex B is replaced with the point along the triangle edge AB that exists on the bisecting plane.
Vertex C is added as the point along the triangle edge AC that exists on the bisecting plane.
0x6 : Vertex A, C outside; B inside.
Vertex A is replaced with the point along the triangle edge AB that exists on the bisecting plane.
Vertex C is added as the point along the triangle edge BC that exists on the bisecting plane.
0x7 : All vertices outside.
Polygon does not intersect pixel.
This bisection process must be repeated for all edges that bound the pixel volume. Notice first that conditions 4-6 replace the two points that exist outside the pixel volume. Notice second that conditions 1-3 replace the vertex that exists outside the pixel volume AND also add an additional vertex to the pixel mesh.
Every time a plane bisects an n-sided polygon, it has the potential to generate a polygon with 0-, 3-, or any greater integer up to n+1. This means that for a square, rectangle, or other quadrilateral pixel shape, this process must be done four times. Each subsequent bisection must account for one more vertex than the previous. 3 vertices becomes 0, 3, or 4 vertices. 4 vertices becomes 0, 3, 4, or 5 vertices. 5 vertices becomes 0, 3, 4, 5, or 6 vertices. And 6 vertices becomes 0, 3, 4, 5, 6, or 7 vertices. All of these possibilities, with the exclusion of 0, must be accounted for.
In bisecting a 7-sided polygon, there are 2^7 = 128 possible states. In our case, many of these states are rendered moot because our polygon is convex; bisecting it will never result in a condition where two vertices are culled but a vertex between them is not.
The images below are colored based on the number of vertices that intersect a given pixel. Pixels with multiple intersections are blended (averaged).
As of 2013-02-05, I have implemented optimization listed as Stage 4 below. This dramatically improves execution times, as the amount of work being generated is completely dependent upon object visibility as well as per-pixel hierarchical bounds filtering. This has reduced problem size from a quadratic complexity to a logarithmic one.
(deprecated) Execution times for these renders can be found here. Please remember that these are near-brute-force, hardly optimized executions. As further stages are completed, optimizations will be implemented to reduce the number of pixels that must be processed.
(deprecated) Output for test #4 with three objects composed of 256*256*2 triangles each (plus one for top left) fails roughly half-way through the third object. This occurs at different places on different hardware with the same OpenCL kernel code. I suspect this is the fault of the OpenCL driver. [more]
"Stage 2" - Per-pixel, per-polygon, distance sorting, bisection, and occlusion.
_input:
Grid of 3D vectors. 6-float; (x, y, z) (i, j, k)
Arrays of 3D vectors, grouped by planar polygons. (n x p x q x 3)-float.
(n see above, p = pixels, q <= 7)
output:
Arrays of triangles (3 x 3D vectors), grouped by relevant pixel. (Q x 3 x 3)-float.
(Q is a result of the intersection between two polygons in the same pixel volume.)
_input:
Grid of 3D vectors. 6-float; (x, y, z) (i, j, k)
Arrays of triangles (3 x 3D vectors), grouped by relevant pixel. (Q x 3 x 3)-float.
(Q is a result of the intersection between two polygons in the same pixel volume.)
output:
Arbitrary-precision value for each color channel (R, G, B).
(24-bit color allows 8-bit per channel.)
High-precision can be employed to normalize the luminosity of images that would otherwise appear too dark or too light.
