Does occlusion reject 3D-converted 2D rectangles?

Question

So, for starters, I'm not very good at computer graphics. I am trying to implement a GUI toolkit where one of the possibilities allows you to apply 3D transforms to 2D layers. (the layer has only one Z coordinate, as a previously transformed rectangle with a two-dimensional axis)

Now it's pretty simple until you come to the 3D transforms that would push the layer back, requiring the layer to be split into several polygons to make it right, as shown here. And since we may have transparency, layers may not completely close, but separation is required.

So, here is an illustration depicting a problem and the desired result. In this case, the blue layer (name it B ) is on top of the red layer ( R ), having the same Z position (but B is added after R ). In this case, if we rotate B , its upper two points will get an index Z below 0, while the lower points will get an index above 0 (provided that the anchor point is the only point / line on the left as 0).

Can someone suggest a good way to do this on a processor? I struggled to find a suitable implementation of the algorithm (in C ++ or C) that would fit this scenario.

Edit: To clarify myself, at this point in the pipeline there is no rendering yet. We just need to create a set of polygons for each layer, which then will represent the transformed layer and the occlusal geometry. Then, if required, rendering (either software or hardware) is performed if necessary, which does not always happen (for example, when testing impacts).

Edit 2: I saw binary partitioning as a variant of this, but I managed to find only one implementation (in GL2PS ), which I'm not sure how to use. I have a vague understanding of how BSPs work, but I'm not sure how they can be used to cull occlusion.

Edit 3: I am not trying to do color mixing and transparency at this point. Just pure geometry. Transparency can be handled by the renderer, and overloading is fine. In this case, the blue polygon can simply be drawn under the red one, but with more complex cases, you may need to sort the depth or even split the polygons (an example of such a terrible case, as below). Although the viewport is fixed because all layers can be converted to 3D, it is possible to create the form shown below.

So I'm really looking for an algorithm that will geometrically divide layer B into two blue shapes, one of which will be drawn "on top" and one of which will be displayed below R. The "below" part will be overloaded, yes, but this is not a serious problem. Therefore, B needs to be divided into two polygons in order to apparently cut through R when these polygons are drawn in order. No need to worry about mixing.

Edit 4: We cannot do anything for this. All this must be done exclusively geometrically (creating 2D polygons). This is what I originally received.

Change 5:. It should be noted that the total number of quads in the subnet is about 30 (average). It will definitely not exceed 100. If the layers are not converted to 3D (this is where this problem arises), they are simply sorted by Z-positions before drawing them. Layers with the same Z position are drawn in the order in which they were added (first first, first).

Sorry if I didn’t clarify the original question.

Answer 1

If you are "poorly versed in computer graphics," then doing it on the CPU (software rendering) will be extremely difficult for you if the polygons can be transparent.

The easiest way to do this is to use GPU rendering (OpenGL / Direct3D) with the deep peeling method .

Cpu Solutions:

Soltuion # 1 (extremely difficult) :

(I forgot the name of this algorithm).

You need to split polygon B into two, for example, using polygon A as the clip plane, and then visualize the result using the painter's algorithm. To do this, you will need to change your rendering procedures so that they no longer use squares, but textured polygons, plus you will have to write / debug clipping procedures that will break the triangles present in the scene, so that ll no longer violates the paitner algorithm.

A big problem. If you have many polygons, this solution can potentially split the scene into an infinite number of triangles. In addition, writing yourself texture rendering code is not very fun for yourself, so it is recommended to use OpenGL / Direct3D.

This can be very difficult to do right. I think this method was discussed in Computer Graphics Using OpenGL 2nd edition by Francis S. Hill, somewhere in one of his exercises.

Also check out the wikipedia article on Hidden Surface Removal .

Solution No. 2 (easier) :

You need to implement a multi - layer z-buffer that stores up to N transparent pixels and their depth.

Solution # 3 (computationally expensive) : Just use ray tracing . You will get an excellent rendering result (without restrictions on the depth of peeling and cpu # 2 solution), but it will be expensive, so you will need to optimize the rendering procedures.

Bottom line:

If you are rendering software, use Solution # 2 or # 3. If you are rendering on equipment, use a technique similar to the depth of the peeling, or implement ray tracing on the equipment.

- edit-1 -

The necessary knowledge to implement # 1 and # 2 "intersection of the linear plane . " If you understand how to split a line (in 3d space) into two using a plane, you can easily implement ray tracing or cropping.

The necessary knowledge for # 2 is the “textured 3D triangle” (algorithm). This is a rather complicated topic.

To implement the GPU solution, you need to find several OpenGL tutorials that deal with shaders.

- edit-2 -

Transparency is important because in order to get transparency, you need to draw polygons from beginning to front (from the farthest to the closest) using the painter's algorithms. Correct sorting of polygons is not possible in a certain situation , so they must be separated, or you must use one of the listed methods, otherwise in certain situations there will be artifacts / incorrectly displayed images.

If there is no transparency, you can implement the standard zbuffer or draw using hardware OpenGL, which is a very trivial task.

- edit-3 -

I should note that the total number of quads in the subnet is about 30 (average). Definitely will not exceed 100.

If you split the polygons, it can easily go above 100.

Perhaps you can arrange the polygons so that each polygon divides all the other polygons.

Now, 2 ^ 29 - 536870912, however, it is impossible to divide one surface with a plane in such a way that during each broken number of polygons doubles. If one polygon is divided into 29 times, you will get 30 polygons in the best case and probably several thousand in the worst case, if the splitting planes are not parallel.

Here's a rough outline of the algorithm that should work:

• Prepare a list of all the triangles in the scene.
• Remove inverse triangles.
• Find all the triangles that intersect each other in three-dimensional space and break them into an intersection line.
• calculate screen space coordinates for all vertices of all triangles.
• Depth sorting for the painter's algorithm.
• Prepare an additional list for new primitives.
• Find the triangles that overlap in the 2D (post-projection) space of the screen.
• For all overlapping triangles, check the order in which they appear. Basically, a triangle that will be displayed “below” other triangles should not have any part that is above another triangle. 8.1. To do this, use the reference edges and the edges of the triangle to divide the source triangles into several subregions, then check whether the regions correspond to the established sort order (prepared for the painter's algorithm). Regions are created by separating the existing two triangles using 6 clip planes created by the camera's origin points and the edges of the triangle.
  8.2. If all regions correspond to the order of visualization, leave the triangles. If they do not, remove the triangles from the list and add them to the "new primitives" list.
• If there are any primitives in the list of new primitives, merge the list with the triangular list and go to # 5.

By looking at this algorithm, you can easily understand why everyone is using Z-buffer at the moment.

Think of it as a good training exercise for universities that specialize in CG. This is an exercise that can make your students hate you.

Answer 2

I am going to speak, say, to give a simpler solution that may not correspond to your problem. Why not just change your work so that this problem does not arise.

In task 1, simply divide the polynes into Maya or something else in advance. For a 3-line problem, split your policies again at intersections to prevent a battle. Pre-calculated solutions will always work faster than on the fly, especially on limited equipment. From professional experience, I can say that it also scales, it scales well fine. It just requires some tweaking by art and technical reviews to make sure nothing is created "ilegally". You can end up with more policies, doing it this way than on-the-fly rendering, but at least you don’t have to do a ton of math on processors that might not be up to the task.

If you do not have control over the cover conveyor, this will not work, since writing any converter will take longer than starting the BSP routine. However, KISS is often the best solution.