CODEWITHSUNDEEP
javascriptthree.js3d
Rantiev
Rantiev

Reputation: 2242

How to detect faces of a 3d shape hidden by other faces (invisible from angle)?

Let's say we have a 3d cube (actually shapes can be of any form, very complex potentially, but let's start with a cube) represented in XYS coordinates system, we are looking to the cube from some distant point under some angle to front face (for example camera can look at cube on the same angle to all XYZ axes).

How to detect invisible faces programmatically (in this example bottom, left and back will be hidden).

Upvotes: 0

Views: 954

Answers (2)

pid
pid

Reputation: 11607

The simple way of removing non-visible triangles is called Backface Culling. It's basically the idea that three 3D points are projected on the 2D screen and, at that point, are arranged clockwise or counter-clockwise. Based on that arrangement the Normal Vector sticks into or out of the screen. Solely based on the orientation of the normal vector you can tell if the triangle is seen from the front side or the back side. You just drop the triangles you see from the back side.

This is a very simple approach, but what you really are asking is different. If you have convex/concave 3D polyhedra you want to know if a front-facing triangle is still visible or obstructed by other triangles of the same structure.

This is technically very complex and generally not advisable to do. Look at this simple example:

+--------+
|        |  <-- rectangle R
+--------+


+--------+
|        |
|  +--+  |
|  |  |  |  <-- U shape
|  |  |  |
+--+  +--+

If we overlay one to the other you get this:

+--------+
|        |
|  +--+  |
|  |RR|  |  <-- RR is rectangle R looking through the U shape
|  |--|  |
+--+  +--+

In this actually simple example you have to compute the intersections of the two polygons to see if the rectangle R behind shape U is completely obstructed or if there are parts still visible.

As the complexity of the polyhedron increases, so does the algorithm needed to decide which triangles are visible and which aren't.

In other words: this is not a viable approach unless it's not realtime and for some reasons maybe not even graphics-related.

In CG you use instead a Z-buffer and draw ALL front-facing triangles (that means you did backface culling beforehand) and keep the depth (Z) in a buffer. While rendering the fragments (think "pixels") you check if the Z is above or below the previously rendered fragments and as such can decide if the single "pixel" is visible or not.

So until you draw ALL triangles, on current CG hardware (GPU) there's no way to tell if a triangle is fully/partially visible (or fully obstructed) in realtime (that is at 60 Hertz).

Obviously there are algorithms which can do visibility checking on the CPU (not necessarily in realtime) but anyways, there is next to 0 probability that you can implement something equivalent. Those algorithms are extremely complicated and require months of study...

So backface culling is quick and dirty, visibility checking is very complicated and only feasible if you use an external tool and Z-buffer requires to actually render the triangles, so it's not an optimization technique to avoid drawing unnecessary geometry.

Upvotes: 2

jo_va
jo_va

Reputation: 13963

Since your shapes can be arbitrary, a method that would work would be to use ray casting: https://en.wikipedia.org/wiki/Ray_casting.

Basically, you will have to cast rays (vectors) in your scene and calculate the intersection of those rays with your object, this can be done with simple math. If a ray hits more than a point, you know that the first point is visible but the following hits will be on invisible surfaces.

I have written a path tracer that uses this technique to detect what is visible to a camera: https://github.com/jo-va/hop. Feel free to have a look and reuse some code!

Hope that helps.

Upvotes: 1

Related Questions