You are not logged in. Please login at www.codechef.com to post your questions!

×

LOGO - Editorial

3
2

Problem Link: contest, practice

Difficulty: Medium-Hard

Pre-requisites: Z-Buffering, Geometry, Stereometry, Implementation

Problem:

We are given N polygons(triangles and quadrilaterals) in 3D. Our task is to project all of them on the 2D plane.

Explanation:

Firstly, in our further explanation we'll assume, that triangles are the only polygons that we have(since every quadrilateral can be splited into two triangles).

OK, now we have M triangles(NM2N, since each quadrilateral has been splitted into two triangles).

Let's fix cell(X,Y). What colour this cell should be coloured with? Intuitively, it should be the color of the triangle, which has the maximal Z for fixed (X,Y). Sounds pretty easy, huh?

But the key part of this problem is the implementation part.

Let's fix a triangle with vertices P1(X1, Y1, Z1), P2(X2, Y2, Z2), P3(X3, Y3, Z3).

Also, let's find a plane, in which triangle P1P2P3 lays. Each plane can be defined by an equation AX + BY + CZ + D = 0. Let's find coefficients A, B, C and D.

A = Y1(Z2 - Z3) + Y2(Z3 - Z1) + Y3(Z1 - Z2);

B = Z1(X2 - X3) + Z2(X3 - X1) + Z3(X1 - X2);

C = X1(Y2 - Y3) + X2(Y3 - Y1) + X3(Y1 - Y2);

D = -X1(Y2Z3 - Y3Z2) - X2(Y3Z1 - Y1Z3) - X3(Y1Z2 - Y2Z1).

If you don’t understand why the coefficient look the way they are, please, visit the following link.

So, let's determine the value of Z for triangle P1P2P3 at the cell(X, Y)(it's also fixed, remember?).

Z = -(D - AX - BY) / C.

Shall we assume that triangle P1P2P3 has the distance Z above the fixed cell? No, we shall not. Well, the plane AX + BY + CZ + D = 0 definitely has the distance Z above the fixed cell, but point T with the coordinates (X, Y, Z) may not belong to our triangle P1P2P3. So, we should check if point T lays in our triangle. There are a lot of ways of doing this. I.e. you can check if S(P1, P2, P3) = S(T, P2, P3) + S(P1, T, P3) + S(P1, P2, T), where S(A, B, C) equals to the square of triangle ABC.

Here is a pseudocode, that shows the implementation of the algorithm described above.

for X from 0 to 319 do
begin
    for Y from 0 to 239 do
    begin
        COLOR = 0
        MAX_Z< = -INFINITY
        for i from 0 to M do
        begin
            P_1, P_2, P_3 - points of i'th triangle

            A = Y_1(Z_2 - Z_3) + Y_2(Z_3 - Z_1) + Y_3(Z_1 - Z_2)
            B = Z_1(X_2 - X_3) + Z_2(X_3 - X_1) + Z_3(X_1 - X_2)
            C = X_1(Y_2 - Y_3) + X_2(Y_3 - Y_1) + X_3(Y_1 - Y_2)
            D = -X_1(Y_2 * Z_3 - Y_3 * Z_2) - X_2(Y_3 * Z_1 - Y_1 * Z_3) - X_3(Y_1 * Z_2 - Y_2 * Z_1)

            Z = Z = -(D - AX - BY) / C

            T - point with the coordinates(X, Y, Z)

            if S(P_1, P_2, P_3) = S(T, P_2, P_3) + S(P_1, T, P_3) + S(P_1, P_2, T) do
            begin
                if Z > MAX_Z do
                begin
                    COLOR = the color of i'th triangle
                    MAX_Z = Z
                end
            end
        end
        print( COLOR )
    end
end

The total complexity is O(N * MAXX * MAXY).

Setter's Solution: link

Tester's Solution: link

This question is marked "community wiki".

asked 21 Apr '14, 00:16

kostya_by's gravatar image

6★kostya_by ♦♦
166143235
accept rate: 0%

edited 21 Apr '14, 00:47

kcahdog's gravatar image

3★kcahdog
10.0k2854129


Hi can anyone explain what onright function in setter's solution is doing ?

link

answered 21 Apr '14, 12:50

deepanshum007's gravatar image

3★deepanshum007
138113
accept rate: 0%

It checks if the points satisfy to the right-hand rule. http://en.wikipedia.org/wiki/Right-hand_rule

(21 Apr '14, 14:22) kostya_by ♦♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,198
×1,219
×795
×632
×5

question asked: 21 Apr '14, 00:16

question was seen: 2,057 times

last updated: 21 Apr '14, 14:22