Demo: https://youtu.be/GLVFr3ABoGg

Things changed from Roll-a-ball:

1. Automatically place the power-ups in a script at start-up.
2. A power-up manager that spawns new power-ups randomly across the playground and deletes them after a brief time.
3. A NPC with navagent to chase for the power-ups
4. A player can collect power-ups to change it appearance.

Credits

Gallery

All of these pictures were made through a combination of Layer masks and some adjustments. The second one also used lasso tools to select the aera where I added the setting sun effects.

Introduction

This project Demo Link consists of basic ray-tracing functions and many extra features.

Following features have been implemented:

• Render polygons
• Render spheres
• Use simple Phong Shading (in color)
• Compute shadows
• Compute reflections
• Use point lights
• Write its output to a standard image format(.ppm).
• Depth of field
• Anti-aliasing
• Transparency with refraction
• Use AABB tree to accelerate the computations
• Use iterative flows to trace the bounce rays, instead of recursion.
• Toon shading

Inputs

The inputs include two parts: command lane arguments and an input file(writen in .nnf format)

Command Lane Arguments

All the command line arguments are optional. The default values for each object on the screen is its ambient color. Other pixels will be filled with background color. Detailed specifications are written in the input file.

-c

• This command tells the programm to shade the objects(i.e. running phone shading or toon shading)

-d %g

• This command provides an integer value limiting the number of bounces in reflection and refraction.

-phone

• Switch to phone shading(default)

-toon

• Switch to toon shading(the last command on switching shading methods will be applied)

-samples %g

• Set the number of samples(%g * %g) to be collected to determine each pixel(if greater than one, then automatically run anti-aliasing)

-aabb

• Set to use aabb-tree data structure

-iter

• Set to shift from recursion to iteration bounce ray tracing.

Input files

Specifications

In addition, I added three extra parameters–rr rg rb following the fill color and shading parameters to provide the reflective attenuation, which makes the rendering of image easier.

Gallery

The tracing results generated from my program. All the input datasets were from the Internet.

Environment: Windows10, i7-8750H 2.20GHz CPU, VS Code

teapot.nff

Command Line Arguments: raytracer trace -c (-aabb) teapot.nnf teapot.ppm

Total time: 1415.78s(normal structure & flow)

Total time: 748s(use AABB tree)

balls.nff

Command Line Arguments: raytracer trace -c (-aabb) balls.nnf balls.ppm

Total time: 3267.89s(normal structure & flow)

Total time: 2287.5s(use AABB tree)

More pictures are coming soon!

Introduction

This project Demo Link implements the following features:

• open a window contains an OpenGL rendering area in which a circular shape should be shaded using the Phong Illumination Model for point and directional lights.

• The circular shape should always occupy most of the window. If the window is resized it should update the display so that the shape still occupies most of the window and is still round. (In this context “most” would mean that the diameter of the circle should be 90% of the smaller of the window’s height or width.)

• Press arrow keys to move the circular shape, and either ESC key or Q to terminate the program and close the window.

Command Lane Arguments

All the command line arguments are optional. The default values should be a black sphere with no lights. That is the program display a black circular shape on a black(default) background. If material parameters are multiply specified, the last value should be used.

-ka r g b

• This is the ambient color coefficients of the sphere material. The parameters r g b are numbers between 0 and 1 inclusive.

-kd r g b

• This is the diffuse color coefficients of the sphere material. The parameters r g b are numbers between 0 and 1 inclusive.

-ks r g b

• This is the specular color coefficients of the sphere material. The parameters r g b are numbers between 0 and 1 inclusive.

-spu pu

• This is the power coefficient on the specular term in the u direction for an anisotropic material. It is a number between 0 and max_float.

-spv pv

• This is the power coefficient on the specular term in the v direction for an anisotropic material. It is a number between 0 and max_float.

-sp p

• This is the power coefficient on the specular term for an isotropic material. It is a number between 0 and max_float. (i.e. the same as setting pu and pv the the same value.)

-pl x y z r g b

• This adds a point light to the scene. The x y z values are the location of the light. The r g b values are it’s color. Note that the x y z values are relative to the sphere. That is, the center of the sphere is at the origin and the radius of the sphere defines one unit of length. The Y direction is UP, the X direction is to the right on the screen, and the Z direction is “in your face.” The r g b value are between 0 and max_float, NOT between 0 and 1 (that is, the r g b values encode the brightness of the light).

-dl x y z r g b

• This adds a directional light to the scene. The x y z values are the direction that the light points in. The r g b values are it’s color. See -pl for coordinate system notes.

-bgbmp fp

• This tells which .BMP file would be used as the custom background image.

-bgppm fp

• This tells which .ppm file would be used as the custom background image.

-toon

• switch to the toon shading

-pixellation

• apply the pixellation effect on the final image

Specifications:

• There may be up to 5 point lights and 5 directional lights (10 total) in a scene. Image r g b values of 1.0 should be mapped to a display values of 255.

• The coordinate system you use in your program should have a unit sphere at the origin and the viewer looking down the Z-axis. The X-axis points to the right of the screen, the Y-axis points up, and the viewer is located infinitely far away in the positive Z direction. You should assume that the vector from eye to the surface will always be -Z.

• All the background image would automatically fill the screen when the screen has been resized.

Gallery

The shading results generated from my program.

assignment1 -ka 0.1745 0.01175 0.01175 -kd 0.61424 0.04136 0.04136 -ks 0.727811 0.626959 0.626959 -sp 76.8 -bgbmp sampleBG2.BMP -dl -0.5 0.1234 -0.42 0.235 0.263 0.5 -pl 1.512 1.123 1.132 0.125 0.643 0.6423 -dl 0.125 0.125 0.125 0.125 0.125 0.125 -dl 0.6423 0.346 0.634 0.124 0.623 0.623 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612 -dl 0.125 0.1245 0.321 1 1 1 -pl 1.512 1.3123 1.312 0.123 0.6236 0.623 -pl 1.1236 1.1236 1.6234 0.23460 0.3462 0.2346 -pl 1.2346 1.6342 1.423 0.123 0.632 0.6432 -pl 1.1236 1.6423 1.6423 0.123 0.632 0.6432

assignment1 -ka 0.2125 0.1275 0.054 -kd 0.714 0.4284 0.18144 -ks 0.393548 0.271906 0.166721 -sp 25.6 -bgbmp gray.BMP -dl -0.5 0.1234 -0.42 0.235 0.263 0.5 -pl 1.512 1.123 1.132 0.125 0.643 0.6423

assignment1 -ka 0.25 0.25 0.25 -kd 0.4 0.4 0.4 -ks 0.774597 0.774597 0.774597 -spu 10 -spv 70 -bgppm samplebg1.ppm -pl 1.512 1.123 1.132 1 1 1 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612

assignment1 -ka 0 0 0 -kd 0.01 0.01 0.01 -ks 0.5 0.5 0.5 -spu 75 -spv 5 -bgppm samplebg1.ppm -dl -0.5 0.1234 -0.42 0.235 0.263 0.5 -pl 1.512 1.123 1.132 0.125 0.643 0.6423 -dl 0.125 0.125 0.125 0.125 0.125 0.125 -dl 0.6423 0.346 0.634 0.124 0.623 0.623 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612 -dl 0.125 0.1245 0.321 1 1 1

assignment1 -ka 0 0 0 -kd 0.01 0.01 0.01 -ks 0.5 0.5 0.5 -sp 32 -bgppm samplebg1.ppm -dl -0.5 0.1234 -0.42 0.235 0.263 0.5 -pl 1.512 1.123 1.132 0.125 0.643 0.6423 -dl 0.125 0.125 0.125 0.125 0.125 0.125 -dl 0.6423 0.346 0.634 0.124 0.623 0.623 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612 -dl 0.125 0.1245 0.321 1 1 1 -pl 1.2346 1.6342 1.423 0.123 0.632 0.6432 -pl 1.1236 1.6423 1.6423 0.123 0.632 0.6432 -pl 1.512 1.3123 1.312 0.123 0.6236 0.623 -pl 1.1236 1.1236 1.6234 0.23460 0.3462 0.2346

-ka 0 0 0 -kd 0.652 0.232 0.612 -sp 30 -ks 0.65 0.30 0.12 -dl -0.5 0.1234 -0.42 0.235 0.263 0.5 -pl 1.512 1.123 1.132 0.125 0.643 0.6423 -dl 0.125 0.125 0.125 0.125 0.125 0.125 -dl 0.6423 0.346 0.634 0.124 0.623 0.623 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612 -dl 0.125 0.1245 0.321 1 1 1 -pl 1.512 1.3123 1.312 0.123 0.6236 0.623 -pl 1.1236 1.1236 1.6234 0.23460 0.3462 0.2346 -pl 1.2346 1.6342 1.423 0.123 0.632 0.6432 -pl 1.1236 1.6423 1.6423 0.123 0.632 0.6432 -toon

assignment1 -ka 0.1745 0.01175 0.01175 -kd 0.61424 0.04136 0.04136 -ks 0.727811 0.626959 0.626959 -sp 76.8 -bgbmp sampleBG2.BMP -dl -0.5 0.1234 -0.42 0.235 0.263 0.5 -pl 1.512 1.123 1.132 0.125 0.643 0.6423 -dl 0.125 0.125 0.125 0.125 0.125 0.125 -dl 0.6423 0.346 0.634 0.124 0.623 0.623 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612 -dl 0.125 0.1245 0.321 1 1 1 -pl 1.512 1.3123 1.312 0.123 0.6236 0.623 -pl 1.1236 1.1236 1.6234 0.23460 0.3462 0.2346 -pl 1.2346 1.6342 1.423 0.123 0.632 0.6432 -pl 1.1236 1.6423 1.6423 0.123 0.632 0.6432 -pixellation

assignment1 -ka 0.25 0.25 0.25 -kd 0.4 0.4 0.4 -ks 0.774597 0.774597 0.774597 -spu 10 -spv 70 -bgppm samplebg1.ppm -pl 1.512 1.123 1.132 1 1 1 -dl 0.12312 0.512 0.1231 0.1231 0.123 0.5612 -pixellation

Record some unfamiliar algorithms

1. 多数投票算法(Boyer-Moore Algorithm)详解

This algorithm serves to finding the major element in a pile of data, and the occurrence of the major element is no less than 50% of the whole.

Question Description:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. (Leetcode 169)

Brute force

HashMap

Double loop

Application

This algorithm logically partitions the elements to two sections. One is the section contains only major elements and the other one contains any other elements.

该算法时间复杂度为O(n)，空间复杂度为O(1)，只需要对原数组进行两趟扫描，并且简单易实现。第一趟扫描我们得到一个候选节点candidate，第二趟扫描我们判断candidate出现的次数是否大于⌊ n/2 ⌋。

第一趟扫描中，我们需要记录2个值：

candidate，初值可以为任何数
count，初值为0
之后，对于数组中每一个元素，首先判断count是否为0，若为0，则把candidate设置为当前元素。之后判断candidate是否与当前元素相等，若相等则count+=1，否则count-=1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

Extension

分布式Boyer-Moore
Boyer-Moore还有一个优点，那就是可以使用并行算法实现。相关算法可见Finding the Majority Element in Parallel
其基本思想为对原数组采用分治的方法，把数组划分成很多段(每段大小可以不相同)，在每段中计算出candidate-count二元组，然后得到最终结果。

举个例子，原数组为[1,1,0,1,1,0,1,0,0]
划分1：
[1,1,0,1,1] –> (candidate,count)=(1,3)
划分2：
[0,1,0,0] –> (candidate,count)=(0,2)
根据(1,3)和(0,2)可得，原数组的多数元素为1.

正因为这个特性，考虑若要从一个非常大的数组中寻找多数元素，数据量可能多大数百G，那么我们甚至可以用MapReduce的方式来解决这个问题。

以上中文解析转载自https://blog.csdn.net/kimixuchen/article/details/52787307

More Algorithms are coming!!!

Maximium and Minimum Question On A Segment of An Array (Merging Intervals)

Statement

Given a set of numbers find an optimal solution for a problem considering the current number and the best you can get from the left and right sides.

Approach

Find all optimal solutions for every interval and return the best possible answer.

The outer loop would be the possible length of the segment from 0 (base) to N (target).

Then using another loop determine one end of the interval, and inside the loop determining another end.

Finally, it might be an additional separator k (like leetcode 312) needs to deal with, or simply applying the DP Function

Related Questions

96. Unique Binary Search Trees Medium

1039. Minimum Score Triangulation of Polygon Medium

546. Remove Boxes Medium

1000. Minimum Cost to Merge Stones Hard

312. Burst Balloons Hard

375. Guess Number Higher or Lower II Medium

Profile

Contact:

• WeChat: JF2655698979

• LinkedIn: https://www.linkedin.com/in/shengyu-jin1024/

• GitHub: https://github.com/GeneralJin1024/

About Me

• An undergraduate programmer proficient in Java and C#, also have application development experience in C++ and Android.

• Now I am learning some web development skills and try to apply the skills on this blog.

• I am also exposing myself to the advanced Unity3D developing environment to design my brand new roguelike game, and I will post it here once finished

A Solution Set Restricted to Java Language

The practice on LeetCode was started late November 2019, writing this post can remind me how I thought about the question at the time.

Problem 2: Add Two Numbers (Medium, List Manipulation)

• we can assign an extra node to form the result list.

• Monitor the current two digits to calculate the carry and then do the normal addition work.

• Remember to check the null node when the length of two adders are different

Problem 3: Longest Substring Without Repeating Characters (Medium, Sliding Window)

My thoughts:

• Using greedy to store the length of longest non-repeating substring
• When encounter a duplicated character, recording the length between two duplicted character
• Then comparing it with the current length plus one to deal with the special case “abba”

1

currentLength = (currentLength + 1) < lengthBetween ? currentLength + 1 : lengthBetween; //deal with "abba"

Provided Solution

• https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/

Problem 4: Median of Two Sorted Arrays (Hard, Optimized Half Search)

• To be continued

Welcome to my little blog. For now, this site is still under construction and may keep up updating till next year XD.