Perspective 3D graphic rendering algorithm in solidity
lack of floating point support by EVM
The first challenge was that Ethereum does not have support for floating-point arithmetic that is necessary for 3D rendering computation. To overcome this limitation, the ABDKMath64x64.sol library is used which provides support for fixed-point arithmetic. since the fixed point is distant relative of floating point, It did the trick.
- fixed point 16x16 as an example
Let's say we have a cube in 3D space, and we want to project it onto a 2D plane. We need to choose a point to act as our "observer," or camera, and a plane to project onto. so we need to find the intersection of the vertices into the plane,(shown in red Xs)
to do that I developed necessary linear algebraic functions like cross product, dot product and norm of a 3D vector. on top of ABDKMath64x64.sol.
// return the cross product of two vector
function cross(
int128[3] memory a,
int128[3] memory b
) internal pure returns (int128[3] memory) {
int128[3] memory d;
d[0] = ABDKMath64x64.sub(
ABDKMath64x64.mul(a[1], b[2]),
ABDKMath64x64.mul(a[2], b[1])
);
d[1] = ABDKMath64x64.sub(
ABDKMath64x64.mul(a[2], b[0]),
ABDKMath64x64.mul(a[0], b[2])
);
d[2] = ABDKMath64x64.sub(
ABDKMath64x64.mul(a[0], b[1]),
ABDKMath64x64.mul(a[1], b[0])
);
return d;
}
// return the dot product of two vector
function dot(
int128[3] memory a,
int128[3] memory b
) internal pure returns (int128) {
int128 d = 0;
d += ABDKMath64x64.mul(a[0], b[0]);
d += ABDKMath64x64.mul(a[1], b[1]);
d += ABDKMath64x64.mul(a[2], b[2]);
return d;
}
// compute the norm of a vector
function norm(int128[3] memory a) internal pure returns (int128) {
return ABDKMath64x64.sqrt(dot(a, a));
}
// returns the vector ab , vector form point a to b, and return it as a fixed point 64x6x integer[3]
function line_vector(
int128[3] memory a,
int128[3] memory b
) internal pure returns (int128[3] memory) {
int128[3] memory d;
d[0] = ABDKMath64x64.sub(b[0], a[0]);
d[1] = ABDKMath64x64.sub(b[1], a[1]);
d[2] = ABDKMath64x64.sub(b[2], a[2]);
return d;
}
Finding the Intersection of each observer vertices line with projection plane
I made 2 assumptions:
- Projection plane is perpendicular to observer and the center of the object.(plane normal vector)
- Projection plane distance from observer is 1 unit of length.
By solving a little bit of vectors equation we can drive the below formula that gives us the projection of the point into the plane.
and the coresipondig code in solidity does this
// points intersection with observer plane in 3d
function projectedPointsIn3d(
int128[3] memory relative_observer0,
int128[3] memory plane_normal0,
int128[3][] memory vertices0
) internal pure returns (int128[] memory) {
int128[] memory _pointsIn3d = new int128[](vertices0.length * 3);
int128[3] memory a;
int128 t;
for (uint256 i = 0; i < vertices0.length; i++) {
a = line_vector(relative_observer0, vertices0[i]);
t = dot(a, plane_normal0);
_pointsIn3d[i * 3 + 0] = ABDKMath64x64.add(
ABDKMath64x64.div(a[0], t),
relative_observer0[0]
);
_pointsIn3d[i * 3 + 1] = ABDKMath64x64.add(
ABDKMath64x64.div(a[1], t),
relative_observer0[1]
);
_pointsIn3d[i * 3 + 2] = ABDKMath64x64.add(
ABDKMath64x64.div(a[2], t),
relative_observer0[2]
);
}
return _pointsIn3d;
}
Finding the 2D points for rendering
After that I could compute the projection of the vertices of the cube into the projection plane, the next step was to create a new coordinate system inside plane to find a 2D equivalent of those point. the new coordinate system origin is the intersection of (observer,center) line with projection plane shown with a green dot. for new coordinate system I considered projecting - Z unit vector to the plane(like gravity) and called it Z_prime. and the X_ prime is the perpendicular vector to Z_prime and plane normal vector(n) . X_prime = Z_prime cross n
after that we can project new coordinate system and get the resualt in 2D
// projecting vector -z uint vector (0,0,-1) to the projection plane and make it a unit vector
function z_prime(
int128[3] memory plane_normal0
) internal pure returns (int128[3] memory) {
int128[3] memory z = [
ABDKMath64x64.fromInt(0),
ABDKMath64x64.fromInt(0),
ABDKMath64x64.fromInt(-1)
];
//svg has left handed coordinate system hence -z
int128[3] memory z_p;
int128 nz;
int128 dz;
dz = dot(z, plane_normal0);
z_p[0] = ABDKMath64x64.sub(
z[0],
ABDKMath64x64.mul(dz, plane_normal0[0])
);
z_p[1] = ABDKMath64x64.sub(
z[1],
ABDKMath64x64.mul(dz, plane_normal0[1])
);
z_p[2] = ABDKMath64x64.sub(
z[2],
ABDKMath64x64.mul(dz, plane_normal0[2])
);
nz = norm(z_p);
z_p[0] = ABDKMath64x64.div(z_p[0], nz);
z_p[1] = ABDKMath64x64.div(z_p[1], nz);
z_p[2] = ABDKMath64x64.div(z_p[2], nz);
return z_p;
}
// cross Z-prime with plane normal to find a perpendicular vetor to z_prime, inside the plane
function x_prime(
int128[3] memory plane_normal0,
int128[3] memory z_prime0
) internal pure returns (int128[3] memory) {
return cross(z_prime0, plane_normal0);
}
// point in projection plane with respect of Z_prime, X_prime as new coordinate system with origin at observer_vs_plane point
function projectedPointsIn2d(
int128[] memory points_3d,
int128[3] memory z_prime0,
int128[3] memory x_prime0,
int128[3] memory observer_vs_plane0
) internal pure returns (int128[] memory) {
uint256 len = (points_3d.length / 3);
int128[] memory points_in_2d = new int128[](len * 2);
for (uint256 i; i < len; i++) {
points_in_2d[i * 2 + 0] = dot(
line_vector(
observer_vs_plane0,
[
points_3d[i * 3 + 0],
points_3d[i * 3 + 1],
points_3d[i * 3 + 2]
]
),
x_prime0
);
points_in_2d[i * 2 + 1] = dot(
line_vector(
observer_vs_plane0,
[
points_3d[i * 3 + 0],
points_3d[i * 3 + 1],
points_3d[i * 3 + 2]
]
),
z_prime0
);
}
return points_in_2d;
}
rendering the scene by Painter's algorithm
for rendering the image I chose the Painter's algorithm. the painters algorithm render a 3D scene by depth sorting, so I perform a depth sorting on the polygons or faces of the cube to find out which is the farthest to the nearest, so I could use the paint them in the scene with the correct order. It's the implementation of Painter's algorithm in solidity. I won't go into more details here.
the following image is rendered on blockchain. by this smart contract.
I build some interactive functionality to show the capability of 3D rendering in EVM, and all of the following changes are done on the blockchain.
as a Benchmark I considered platonic solids to show the correctness and accuracy of the Implementation and deployed it on Goerli testnet.
all of the images bellow are rendered by the smart contract on blockchain.
Conclusion
- creating a 3D graphics rendering with solidity is possible.
- I guess it could be useful for developing new kind of Application such as on-chain art and 3D sculpture, or even games.
- my initial guess was since EVM is a Turing complete machine it can do 3d graphics, so maybe there are algorithms out there that can be implemented in solidity and they are yet to be explored.
Refrences
mint and interact on goerli powered by zora
mint and interact on sepolia
smart contract on github
OnChain3D.xyz Dapp provided by Farzadex.eth
