# 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 memory a,
int128 memory b
) internal pure returns (int128 memory) {
int128 memory d;
d = ABDKMath64x64.sub(
ABDKMath64x64.mul(a, b),
ABDKMath64x64.mul(a, b)
);
d = ABDKMath64x64.sub(
ABDKMath64x64.mul(a, b),
ABDKMath64x64.mul(a, b)
);
d = ABDKMath64x64.sub(
ABDKMath64x64.mul(a, b),
ABDKMath64x64.mul(a, b)
);
return d;
}

// return the dot product of two vector
function dot(
int128 memory a,
int128 memory b
) internal pure returns (int128) {
int128 d = 0;
d += ABDKMath64x64.mul(a, b);
d += ABDKMath64x64.mul(a, b);
d += ABDKMath64x64.mul(a, b);
return d;
}

// compute the norm of a vector
function norm(int128 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
function line_vector(
int128 memory a,
int128 memory b
) internal pure returns (int128 memory) {
int128 memory d;

d = ABDKMath64x64.sub(b, a);
d = ABDKMath64x64.sub(b, a);
d = ABDKMath64x64.sub(b, a);
return d;
}
``````

## Finding the Intersection of each observer vertices line with projection plane

1. Projection plane is perpendicular to observer and the center of the object.(plane normal vector)
2. 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 memory relative_observer0,
int128 memory plane_normal0,
int128[] memory vertices0
) internal pure returns (int128[] memory) {
int128[] memory _pointsIn3d = new int128[](vertices0.length * 3);

int128 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, t),
relative_observer0
);
_pointsIn3d[i * 3 + 1] = ABDKMath64x64.add(
ABDKMath64x64.div(a, t),
relative_observer0
);
_pointsIn3d[i * 3 + 2] = ABDKMath64x64.add(
ABDKMath64x64.div(a, t),
relative_observer0
);
}

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 memory plane_normal0
) internal pure returns (int128 memory) {
int128 memory z = [
ABDKMath64x64.fromInt(0),
ABDKMath64x64.fromInt(0),
ABDKMath64x64.fromInt(-1)
];
//svg has left handed coordinate system hence -z
int128 memory z_p;
int128 nz;
int128 dz;
dz = dot(z, plane_normal0);
z_p = ABDKMath64x64.sub(
z,
ABDKMath64x64.mul(dz, plane_normal0)
);
z_p = ABDKMath64x64.sub(
z,
ABDKMath64x64.mul(dz, plane_normal0)
);
z_p = ABDKMath64x64.sub(
z,
ABDKMath64x64.mul(dz, plane_normal0)
);
nz = norm(z_p);
z_p = ABDKMath64x64.div(z_p, nz);
z_p = ABDKMath64x64.div(z_p, nz);
z_p = ABDKMath64x64.div(z_p, 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 memory plane_normal0,
int128 memory z_prime0
) internal pure returns (int128 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 memory z_prime0,
int128 memory x_prime0,
int128 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

3 Likes

Side note 1:

There is obviously a limit here of how many points can be processed within a single transaction before exceeding the block gas limit (or even just reaching a high enough value to increase the expected time of execution beyond reasonable).

Side note 2:
Same goes for function `projectedPointsIn3d`.

Side note 3:

Shouldn't you assert `points_3d.length % 3 == 0`?
That is, unless you're assuming that `points_3d` is always the output of function `projectedPointsIn3d`, which kinda make the two functions tightly-coupled.

Side note 4:

Very impressive post!

2 Likes

• the problem that you raised is valid, and actually there is 2 limit here, first is the number of points to be projected that is O(n) and the second is the polygon counts, since I used Painter's algorithm and I needed to depth sort the polygons distances from observer, that sort has O(n^2) complexity, but In this case it did not reach the timeout(I think it's 120 seconds correct me if I'm wrong ) limit of the EVM client, as an example Icosahedron have 20 polygons and it does just fine, but I believe that better Developer will push this limitation future and capability of rendering ever more complex 3D scene will happen.

• since the points are initially stored in `int128[]` and after that they get serialize into `int128[]` the length of points_3d is always divisible by 3 and asserting `points_3d.length % 3 == 0` is not necessary.

1 Like

There's no such limit.
The time to execute your transaction is generally a function of the gas price and the gas limit that you pass as input.
Miners opt for (favor) highest gas price and lowest gas limit first.

You might experience a "timeout" response from your web3 provider (or perhaps it depends on your local web3 package configuration, I'm not really sure).

But this timeout doesn't mean that your transaction is cancelled or anything like that.
It shall remain in the mem-pool until it is mined.

The limit which I was referring to is the block gas limit, which no transaction can exceed, simply because it would be too large to fit in a block.

And the more iterations are executed, the closer your transaction gets to the block gas limit.
Thus, the number of points that your module can process is limited.

1 Like

So like I said, you're assuming that the `points_3d` input to function `projectedPointsIn2d` is always the output of function `projectedPointsIn3d` , which kinda make the two functions tightly-coupled.

1 Like

the rendering function does not make any state changes to the Ethereum so it does not use any transaction for rendering, the whole stack of the rendering function are view functions or pure functions.
for example I can render this cube how ever I wanted without submitting a transaction.

and I can render it from a different point without submitting a transaction.

`tokenURI(uint256 tokenId)` and `renderTokenById(uint256 tokenId)` and `previewRenderTokenById(uint256 tokenId, tokenSetting memory _tokenSetting)` are view functions.

Your assumption should be that this utility function of yours will ultimately be called from a function which DOES change the state of the function, otherwise, there isn't really any point in it to begin with.

And under that scenario, your function WILL consume gas respectively to its runtime contents, which in turn depends (also) on the number of iterations executed.

Well, you can also do that over web2 platform (as well as over many other non-blockchain platforms).
The point in EVM bytecode, I would imagine, is to ultimately be executed on chain, not elsewhere.

There are a lot of utility functions that are widely used that does not change the state of blockchain like `Base64.sol` that almost every on-chain NFT uses to decode their data into base64.

you are right about this, but I'm not sure about that the limit is the same as `estimateGas` and the upper limit is the same as block gas limit or not?

I think other points of EVM are still valid here, decentralized, trustless, temper proof and censor resistant way to get data.

this was really helpful btw, I learned, Thank you.

1 Like

Again - you are missing the point here.
These functions do not change the state of the chain, so they do not cost anything WHEN:

1. You call them from other functions which do not change the state of the chain (i.e., pure or view)
2. You call them from an offchain script (e.g., in order to query the state of your contract)

BUT when they are called from functions which DO change the state of the chain, they DO cost.
How much? Based on "how much action" they perform.
For example, in your case, the more points are processed, the more gas will be consumed.

Decentralization does not come into effect when you use the blockchain just in order to run some pure computation and give you back the result. You may as well do that on any other platform.

Decentralization comes into effect when your actions are signed and stored on the blockchain, becoming visible for everyone, without any doubts about their authenticity.

Woah this is pretty awesome @scinftist.eth .

@barakman I'm not sure why something that is purely for rendering off-chain would need to be called as part of a state changing transaction. The deployment of the code itself is the state change. So @scinftist.eth is totally correct that you get decentralised benefits here: you can see when the bytecode was deployed and by who, you can verify that it hasn't been modified etc.

IPFS offers similar-ish benefits, however this POC could easily be extended to render based on other state changes (e.g. maybe the size of the object changes according to your balance of some token).

1 Like

You're pretty much giving a supportive argument of exactly what I've described.

Just like any other state changing transaction, the deployment of the contract is limited to the size of a block on the chain (aka block gas limit).

Hence, whether you do the rendering upon contract deployment or after contract deployment, it is fundamentally limited to a (relatively small) number of points.