The
paper [1] formulated the problem of visualization of solid models presented as
a three-parameter set of points in three-dimensional space. The work introduces
a new concept of defining geometric solids in the form of a three-parameter set
of points in three-dimensional space [2, 3]. The analysis of existing
approaches to the visualization of a three-parameter set of points, which are
described by a parametric equations system, carried out in [1], showed the
absence of software solutions which an implement the visualization of
three-dimensional solids obtained in accordance with the new concept. Given the
analytical nature of the solid modeling engine to provide faster rendering on
existing GPUs, it was decided to use the Ray marching method, which is used to
render scenes in real time. The Ray marching method [4-6], by analogy with the
Ray tracing method [7-10], has found wide application in solving a variety of
scientific visualization problems in domestic and foreign practice. The variety
of tasks, in turn, gave rise to many options for real-time visual
representation of scenes. But in most cases, the task is reduced to determining
the function of intersection of the rendered object with the ray and
determining the signed distance function [11-13]. Based on the fact that
geometric solids in the form of a three-parameter set of points in three-dimensional
space are parametrized in point calculus [14-15], to determine the distance
function, it is necessary to solve the problem of intersection of geometric
solids with projecting rays in point calculus.
In point calculus, the projecting
ray is conveniently defined as a straight-line segment. Then the problem is
reduced to determining the point of intersection of a straight-line segment with
a geometric solid. A line is uniquely defined by two points. Then the beam of
projecting rays can be specified by fixing one point in space, and the second
one can be represented as the current point of the picture plane.
The point equation of a straight-line
segment in point calculus has the following form:
where
and
are the points through which the line
passes, which are determined by their coordinates;
is the
parameter;
is the
parameter's addition to 1.
Such a parametrization of the line
ensures its passage through the point
at
and through the point
at
.
If
parameter
,
then we get an infinite line passing
through the points
and
.
And for
we get the segment
.
This feature can be used to determine the points of intersection of a ray with
a geometric solid, if you place one point in front of the geometric solid, and
the second behind it. Then the intersection points of the ray with the geometric
solid will fall within the range of the parameter values
.
To determine a beam of rays, it is
necessary to place a fixed point on one side of the geometric solid, and the
current one, belonging to the plane, on the other side. Such a plane can be
defined using any three points that do not lie on the same straight line. For
example, forming a beam of rays passing through a point
(fig. 1),
plane
can be set by relations on the sides of the
triangular simplex:
where
and
are the current parameters that determine
the position of the point
in plane A1A2A3.
Within the interior of a parallelogram
formed on the basis of a
triangle, these
parameters vary from 0 to 1, but in total they can belong to the interval
.
Fig. 1.
Geometric scheme for determining a beam of rays in three-dimensional space
In Fig. 1, the current
point shows some geometric solid. In
general, the point equation of a three-dimensional solid is determined by the
following point equation:
where
,
,
and
are the points of a three-dimensional
simplex (any four points that do not lie in the same plane);
,
,
and
any continuous and differentiable functions
of parameters
.
The condition for the current
point to belong to the space of a
three-dimensional
simplex is:
Based on this, any of the four free
functions of
parameters can be excluded.
At the intersection of a
straight-line segment and a geometric solid, for all common points, the point
equation will be valid:
To determine the
and
parameters
it is necessary to perform a coordinate-by-coordinate calculation [14]. For
three-dimensional space we can formulate the following equation system:
Thus, we obtain a system of three
equations with four unknown variables. To solve it, we can consider that the
edge values of the
parameters of a geometric solid
determine the shell of its surface, the points of intersection that we need to
find. Since a geometric solid can occupy completely different positions in
space relative to the ray, it is impossible to determine in advance which two
of the surfaces of the shell of the geometric solid will intersect the ray.
Therefore, it is necessary to solve six systems – special cases, which are a
consequence of the use of edge parameter values. In most cases, the parameters
of point equations change from 0 to 1. Then it is necessary to fix in turn the
values of the parameters
(
,
,
,
)
and obtain particular solutions to the
system of parametric equations. From all the solutions, it is necessary to
choose only those, which provide the obtained parameter values in the range
from 0 to 1. There will be only two such solutions if the ray intersects the
geometric solid, and one – if it touches the solid.
Consider an example of determining the
points of intersection of a segment with a solid of a tetrahedron (Fig. 2).
Fig. 2. Geometric scheme of the
segment
intersection with the solid of the tetrahedron
In [1, 2], the point equation of the solid
of a tetrahedron is given, which is determined by the points of the
three-dimensional
simplex and three linear
parameters
:
where
,
è
.
Based on the method described above, we
get:
Next, it is necessary to fix in turn the
edge values of the current parameters of the tetrahedron solid
(,
,
,
,
,
)
and solve the resulting systems of equations.
To conduct computational experiments, we
accept the following test coordinates of the initial points:
Using the coordinates of the initial
points, we obtain 6 systems of parametric equations. Systems for
and
have no
solution. At
and
– the
resulting solutions go beyond the range of parameter values
.
At
parameter
values satisfy the required conditions
,
and
at
–
.
Thus,
it turns out that on the interval of parameter values
part
of the segment
is inside the tetrahedron, and on
the intervals
and
–
outside the tetrahedron
.
The proposed approach can be used to
visualize not only facets, but also other geometric solids. At the same time,
in relation to faceted solids, another approach can be implemented based on the
intersection of the projecting beam with the plane.
In the general case, a
segment (Fig. 2) can have two intersection
points with a
pyramid, one intersection point
(when the segment intersects the edges and vertices of the pyramid) and no
intersection points at all.
As a special case, we define the
point of intersection of the
segment with the
face.
To do this, we set the point equation of a straight line using the parameter
:
,
where
.
and
points are defined in the
simplex using the corresponding parameters:
where
,
,
,
,
,
,
,
.
The volumes
of
the corresponding tetrahedra can be easily determined in terms of the
coordinates of the vertices. In this case, multiplication by 1/6 can be
abolished, because it will still shrink. As an example, we give a determinant
for calculating the volume of a
tetrahedron. All other
volumes of oriented tetrahedra in a
simplex can be found
similarly.
Next, we determine the value of the
parameter, at which the volume of the
tetrahedron is equal to zero. In accordance
with the point calculus
theorem [14], we obtain:
The resulting
point
equation can also be determined in the original
simplex
by replacing the
and
points
with the corresponding equations, but this is not necessary to visualize the
tetrahedron.
In the same way, we define the point
:
As a result, we obtain the following
conditions:
If
,
the
ray segment lies inside the solid of the tetrahedron.
If
,
the
ray segment does not belong to the solid of the tetrahedron.
Based on the relative position of the
projection center and the picture plane, as shown in Fig. 1,
.
At the same time, special cases are
possible when the projecting ray belongs to one of the faces of the
tetrahedron, coincides with its edge, or passes through the vertex. This does
not affect the computational algorithm described above.
To conduct
computational experiments on the visualization of faceted solids, a test
program was written in the GLSL language, containing 167 lines of code (the
source code is available under the MIT license on GitHub:
https://github.com/icosaeder/tpps-raycast).
Visualization is done in the Web browser using a free resource ShaderToy (https://www.shadertoy.com) that provides a
convenient toolkit for launching programs intended for execution on a graphics
card.
The aim of a test program was to check the ability to
efficiently render faceted solids defined in point calculus. The block schema
of the developed numerical algorithm is presented in Fig. 3.
Fig. 3.
Block schema of the proposed rendering algorithm
The input for this algorithm is a definition of a
faceted solid
in
point calculus using the points
,
,
,
,
and the functions
,
,
,
as described in Section 2.
The output is the color of the individual pixel of an image. When executed for
each pixel of an image, this algorithm renders a given faceted solid
from a point of view
determined by points
,
,
and
.
Although the proposed algorithm is written in a
sequential manner, it assumes an implicit parallel execution on a graphics card
within a SIMD (Single Instruction Multiple Data) paradigm. The parallelism is
achieved by executing this algorithm concurrently for a subset of pixels. The
number of pixels in a subset is determined dynamically by the graphics card
based on its hardware capabilities.
The software implementation is based on the numerical
solution of systems of equations using the iterative Newton method [16]. At
each
i-th iteration, a new approximation of the solution
of the
system is calculated by
the formula:
where
is the Jacobian of the
system, which is calculated
numerically by the formula:
The parameters
,
,
alternately act as the
unknown variables
and
,
and the parameter
always acts as the unknown
variable
.
Substitutions are carried out according to the following scheme for all 6
systems described in Section 2:
1.
.
2.
.
3.
.
4.
.
5.
.
6.
.
Partial derivatives in the composition of the Jacobian
are calculated in accordance with the difference scheme, for example:
It was experimentally found that an acceptable
accuracy of the solution is achieved when
.
The first approximation
is taken in our case
identically equal to zero. However, for some
,
such a
may lead to a loss of
solution, since the Jacobian at the first iteration may turn out to be
degenerate, which will make it impossible to calculate
due to the lack of an
inverse matrix for the degenerate Jacobian. To address a problem, the code implements
a check for Jacobian degeneracy at the first iteration, and if it is
degenerate, the identity matrix is substituted for it, which corrects the first
approximation.
Newton's method has two stopping conditions. The first
is the achievement of the specified accuracy of the solution, which is
determined by the formula:
The second stopping condition consists in exceeding
the threshold number of steps, which indicates that the system does not have a
solution. In our case, a threshold value of 100 steps was experimentally
selected. This constant is due to the fact that, according to our observations,
for faceted solids, the corresponding systems are solved on average in 7–10
steps (if they have a solution). Thus, the threshold of 100 steps with a margin
provides reliable protection against loss of the solution, and, at the same
time, does not greatly overload the GPU with unnecessary iterations.
In order for the user to have the opportunity to view
the rendered solid from all sides, a model of an interactive orbital camera is
implemented. The camera position expressed by
point (which corresponds
to the beginning of the segment mentioned in Section 2) is calculated by the
following formula:
where
are the polar angles
calculated based on the coordinates of the mouse cursor in the visualization
area,
is the
radius of the camera's orbit, in our case calculated as twice the maximum value
of the coordinates of the
,
,
,
,
points, which define a
three-dimensional simplex for constructing a rendered solid.
The center of the scene (the point the camera “looks”
at) is selected
point –
the center of mass of the solid. For example, for a tetrahedron:
The orts of the camera coordinate system are defined
as follows:
The
point corresponding to the
end of the segment mentioned in Section 2 is determined by the formula:
where
are the normalized
coordinates of the screen pixel through which the tracing is performed (and
whose color you want to determine),
is the maximum tracing
distance (in our case, the constant 100 is taken).
To increase the visual quality of the displayed
faceted solid and ensure the perception of its three-dimensionality by the
user, a Lambertian shading model has been implemented. In this case, the
normal is calculated as
the gradient of the distance function using the difference scheme:
where
is the function for
determining the distance to a solid on a segment
.
All the calculations described above are performed for
each screen pixel in parallel leveraging the SIMD paradigm. The results of
visualization of faceted solids are shown in Fig. 4 and 5.
Fig. 4.
Visualization of the tetrahedron solid in the service environment ShaderToy
Fig. 5.
Visualization of the prism solid in the service environment ShaderToy
As can be seen from the results of
computational experiments (Fig. 4–5), the proposed approach to the
visualization of solid geometric models justifies itself to a sufficient
extent. Rendering performance delivers an image refresh rate of around 60 frames
per second, matching the refresh rate of today's general-purpose monitors. At
the same time, high image fidelity is maintained without any visible artifacts.
However, when visualizing curvilinear solids, the appearance of artifacts is
still possible. This is due to the fact that Newton's method cannot provide
sufficient accuracy for the numerical solution of the system of equations in
that case. Proceeding from this, the prospect of further research is the
improvement of the method for determining the signed distance function for the
visualization of curvilinear geometric solids with the subsequent integration
of the developed software solutions into the scientific visualization system
SciVi [17-19].
The proposed approach to
visualization of solid geometric models is primarily oriented to application in
computer-aided design, solid-state and information (BIM – Building Information
Modeling) modeling systems. However, given the wide application of
three-dimensional models in various sectors of the economy, after improvement,
the proposed approach can find application not only in mechanical engineering,
construction, and architecture, but also in science, medicine, design,
education, as well as in advertising, film, and video game industry. It seems
promising to use the proposed approach to the definition of solid models in
point calculus to develop a new technology for generating full-fledged
volumetric images in three-dimensional space by analogy with holographic ones.
1.
Konopatskiy E.V., Bezditnyi A.A. The Problem of
Visualizing Solid Models as a Three-Parameter Point Set. Scientific
Visualization, 2022. Vol. 14. No. 2. pp. 49-61. DOI: 10.26583/sv.14.2.05.
2.
Konopatskiy E.V., Bezditnyi A.A., Lagunova M.V.,
Naidysh A.V. Principles of solid modelling in point calculus. IoP conference
series: Journal of Physics: Conf. Series 1901 (2021) 012063. DOI:
10.1088/1742-6596/1901/1/012063.
3.
Konopatskiy E.V., Bezditnyi A.A. Solid modeling
of geometric objects in point calculus. Proceedings of the 31st International
Conference on Computer Graphics and Vision (GraphiCon 2021) Nizhny Novgorod,
Russia, September 27-30, 2021. Vol. 3027. pp. 666-672. DOI:
10.20948/graphicon-2021-3027-666-672.
4.
Kettunen M., D'Eon E., Pantaleoni J.,
Novák J. An unbiased ray-marching transmittance estimator. ACM
Transactions on Graphics. 2021. 40(4). DOI: 10.1145/3450626.3459937.
5.
Coulon R., Matsumoto E. A., Segerman H., Trettel
S. J. Ray-marching thurston geometries. Experimental Mathematics. 2022. DOI:
10.1080/10586458.2022.2030262.
6.
Xu T., Zeng W., Wu E. Viewport-resolution
independent anti-aliased ray marching on interior faces in cube-map space.
Paper presented at the Proceedings - SIGGRAPH Asia 2021 Technical
Communications. SA 2021. DOI: 10.1145/3478512.3488598.
7.
Debelov V.A., Kozlov D.V. Visualization of Light
Polarization to Debug Ray Tracing Algorithms. Scientific Visualization. 2013.
Vol. 5. No 4. pp. 71-87.
8.
Zhdanov D.D., Ershov S.V., Deryabin N.B.
Object-oriented model of photorealistic visualization of complex scenes.
Scientific Visualization. 2013. Vol. 5. No. 4. pp. 88-117.
9.
Sokolov V.G., Voloboy A.G., Potemin I.S.,
Galaktionov V.A. Overview of BSDF Reconstruction Methods for Rough Surfaces.
Scientific Visualization. 2022. Vol. 14. No 3. pp. 132-151. DOI:
10.26583/sv.14.3.10.
10.
Wald I., Zellmann S., Usher W., Morrical N., Lang U., Pascucci V.
Ray tracing structured AMR data using exabricks. IEEE Transactions on
Visualization and Computer Graphics. 2021. 27(2). pp. 625-634. DOI:
10.1109/TVCG.2020.3030470.
11.
Zhang K., Luan F., Wang Q., Bala K., Snavely N. PhySG: Inverse
rendering with spherical gaussians for physics-based material editing and
relighting. Paper presented at the Proceedings of the IEEE Computer Society
Conference on Computer Vision and Pattern Recognition. 2021. 5449-5458. DOI: 10.1109/CVPR46437.2021.00541.
12.
Shen T., Gao J., Yin K., Liu M., Fidler S. Deep marching tetrahedra:
A hybrid representation for high-resolution 3D shape synthesis. Paper presented
at the Advances in Neural Information Processing Systems. 2021. No. 8. pp.
6087-6101.
13.
Soukov S.A. Combined signed distance calculation algorithm for
numerical simulation of physical processes and visualization of solid solids
movement. Scientific Visualization. 2021. 12(5). DOI: 10.26583/SV.12.5.08.
14.
Konopatskiy E.V., Bezditnyi A.A. Point tools of geometric modeling,
invariant relating to parallel projection. Geometry & Graphics. 2021. Vol.
9. No. 4. pp. 11-21. DOI: 10.12737/2308-4898-2022-9-4-11-21.
15.
Konopatskiy E.V., Bezditnyi A.A., Kokareva Ya.A., Kucherenko V.V.
Features visualization of geometric objects in the BN-calculus. Scientific
Visualization. 2020. Vol. 12. No. 2. pp. 98-109. DOI: 10.26583/sv.12.2.08.
16.
Remani C. Numerical Methods for Solving Systems of Nonlinear
Equations. Lakehead University. 2013. 38 p.
17.
Ryabinin K.V., Baranov D.A., Belousov K.I. Integration of Semograph
information system and SCIVI visualizer for solving the tasks of lingual
content expert analysis. Scientific Visualization. 2017. Vol. 9. No. 4. pp.
67-77. DOI: 10.26583/sv.9.4.07.
18.
Ryabinin K.V., Kolesnik M.A., Akhtamzyan A.I., Sudarikova E.V.
Cyber-Physical Museum Exhibits Based on Additive Technologies, Tangible
Interfaces and Scientific Visualization. Scientific Visualization. 2019. Vol.
11. No 4. pp. 27-42. DOI: 10.26583/sv.11.4.03.
19.
Ryabinin K.V., Belousov K.I. Visual Analytics of
Gaze Tracks in Virtual Reality Environment. Scientific Visualization. 2021.
Vol. 13. No 2. pp. 50-66. DOI: 10.26583/sv.13.2.04.
