42 FDF

This project is about creating a simplified 3D graphic representation of a relief landscape. (in C)

      In this project you will discover the basics of graphic programming, and in particular how to place points in space, how to join them with segments and most importantly how to observe the scene from a particular viewpoint.

      You will also discover your first graphic library: miniLibX. This library was developed internally and includes the minimum necessary to open a window, light a pixel and deal with events linked to this window: keyboard and mouse. This project introduces you to “events” programming. [email protected]

Many thanks to:

• Mohammad for helping me out with testing.
• Jimmy for helping me make the python script.
• Jeffrey Senpai for feedbacks.
• Vladyslav Brazhnik for his FDF cook book.
• Tigran Katolikyan for the depth effect.
• Mr Colour for coding advices.
• Jean-Michel Gigault for his map generator.
• And of course 42 Silicon Valley for giving me this opportunity to work on this project.

		   Original gif					   Generated by fdf
	

Table of Content

• Project Overview
  • fdf files
  • Line Algorithm
    • Color Issue
    • Brightness Issue
• Compatibility
• How to run
  • FDF minishell
• Gradient
• Preview
• Gif
• Update Log

Project Overview

Given a .fdf file with this format

0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0 10 10  0  0 10 10  0  0  0 10 10 10 10 10  0  0  0
0  0 10 10  0  0 10 10  0  0  0  0  0  0  0 10 10  0  0
0  0 10 10  0  0 10 10  0  0  0  0  0  0  0 10 10  0  0
0  0 10 10 10 10 10 10  0  0  0  0 10 10 10 10  0  0  0
0  0  0 10 10 10 10 10  0  0  0 10 10  0  0  0  0  0  0
0  0  0  0  0  0 10 10  0  0  0 10 10  0  0  0  0  0  0
0  0  0  0  0  0 10 10  0  0  0 10 10 10 10 10 10  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Each number represents a point with a height in integer.
The goal is to draw a line connecting each point and represent them all together as a landscape.

fdf files

There is no set limit of how big the fdf files should be. However, a valid file should have same amount of points on each line. Each line is ended with a newline. There are no extra empty lines between lines, at the end or at the beginning of the file. Value of the points must be within integer limit.
To further represent a landscape, an integer represent in hex for color can be added behind the points separated by a comma.

0,0xffffff 0,ffffff
0,0xFFFFFF 0,FFFFFF
# All are valid representation of color white

0,0xff 0,0x0000ff
0,0xFF 0,0x0000FF
# Works with 0 paddings as well.

In order to read the files, students are only allowed to use open() and read().
The 2nd project get_next_line() at 42 is the main key for me to parse the file and grab each line. It works similar to getline(3) function.

prototype:

int	get_next_line(const int fd, char **line);
returns
-1 if there's an error     0 if end of file     1 if successful

After grabbing the line, I use ft_strsplit(), a function that I made in my first libft project at 42, to split all the digits up using a space (' ') as a delimiter or 32 in ascii. After splitting them up, I use ft_atoi() similar to atoi() to convert them into integers. I also use ft_strsplit() with (',') as delimiter to extract the color behind the points. To convert the hex to integer, I make a simple ft_atoi_base() that allows me to convert the hex string into integer using base 16. I store the points in t_map struct.

typedef struct		s_map
{
	int		*map; // store points
	int		*c_map; // store color
	int		map_h; // height (how many lines in the file)
	int		map_w; // width (how many points in a line)
	int		map_size; // width x height
	bool		map_color; // true if color mapping exist, false then use default color.
}					t_map;

Line Algorithm

After seeing so many students at the school use the Bresenham's line algorithm for their project, I decided to try to Xiaolin Wu's algorithm instead. Since I cannot have more than 5 variables declared in a function, as stated by school rule, I have to use a struct to store them.

typedef struct		s_var
{
	bool	steep;
	bool	swap; // color swap
	bool	swap_d; // color swap
	double	dx;
	double	dy;
	double	gradient;
	double	xend;
	double	yend;
	double	xgap;
	double	ygap;
	int	xpxl1;
	int	ypxl1;
	double	intery;
	double	interx;
	int	xpxl2;
	int	ypxl2;
}					t_var;

The wikipedia does not declare variables type, so in the beginning all my variables are doubles. But after referencing the rosettacode, I decide to change some doubles to int.
It is not hard to implement the wikipedia algorithm. However I run into issues with color and lightning (brightness).

Color Issue

if (var->steep)
{
	var->swap = true;
	ft_swap(&(p0->x), &(p0->y));
	ft_swap(&(p1->x), &(p1->y));
}
if (p0->x > p1->x)
{
	if (!var->steep)
		var->swap = true;
	var->swap_d = true;
	ft_swap(&(p0->x), &(p1->x));
	ft_swap(&(p0->y), &(p1->y));
}

The points are being swapped around in the algorithm. Each of the points has a certain rgb value and having them swapped around causes all sort of problems for me when I implement color gradient. That is the main reason why I have to add boolean variables to keep track of what's being swapped so the program will draw correct color.

Brightness Issue

# Debug mode
...
bright: 0.658824	 percent: 0.811765	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(55, 39, 23)
bright: 0.882353	 percent: 0.823529	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(74, 53, 31)
bright: 0.117647	 percent: 0.823529	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(9, 7, 4)
bright: 0.423529	 percent: 0.835294	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(35, 25, 15)
bright: 0.576471	 percent: 0.835294	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(48, 34, 20)
bright: 0.964706	 percent: 0.847059	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(81, 58, 34)
bright: 0.035294	 percent: 0.847059	rgb_start(87,63,38)	rgb_end(84,60,35)	rgb_ret(2, 2, 1)
...
ret.r = ((start.r * (1.0 - percent)) + (end.r * percent)) * brightness;

Looking at the value, you can see that the brightness never reaches 1.0 (maximum brightness). That means, the pixel I got out of the algorithm never reaches their true color. The colors return are much dimmer. To counter it, I just add 0.2 brightness to make them 20% brighter. To fully make it brightest possible, I modify my main loop like so.

// before
plot_pixel(fdf, var.xpxl1, ipart(var.intery), get_color(p0, p1, percent, rfpart(var.intery))); //anti-aliasing
// after
plot_pixel(fdf, var.xpxl1, ipart(var.intery), get_color(p0, p1, percent, 1.0)); // not anti-aliasing

By increasing the brightness to 1.0 for every pixel, the lines are no longer anti-aliasing. So basically I have "2" line algorithm inside the program. After the switch, I can see that the lines are twice as thick in parallel view. I make the anti-alias button for users to see the difference.

 	Anti-aliasing with 20% increased			  With 100% brightness

Compatibility

(only tested on this machine)
about this mac
iMac (Retina 5K, 27-inch, Late 2015)
3.2 GHz Intel Core i5
AMD Radeon R9 M380 2048 MB

gcc --version
Apple LLVM version 9.1.0 (clang-902.0.39.1)
Target: x86_64-apple-darwin17.5.0
Thread model: posix

make --version
GNU Make 3.81

How to run

make
./fdf [path to .fdf files]

fdf minishell

Pressing S will enter shell mode.

You can modify fdf maps while the progam is running by using built in fdf_shell command

#for example

change maps maps/t1.fdf // change maps to t1.fdf

change brightness 100 // change brightness to 100

animate maps/animate/matrix_bullet_fdf // enter animation mode and read multiple fdf files

Use the resume command to resume the program.

Gradient

There are multiple linear gradients in the themes I implement. I intend the colors to work like a color ramp. 0 height will be the middle color. Highest z will have the bottom color. Lowest z will have the top color. To get the color index, I have the following function:

int		get_color_index(int z, int size) // size is how many nodes in the color ramp.
{
	int idx_steps;
	int mid_idx;

	idx_steps = 1000 / size; // since there are no maps with z over +-1000, I just leave 1000 as default
	mid_idx = size / 2;
	if (!idx_steps)
		idx_steps = 1;
	mid_idx += (z / idx_steps);
	if (mid_idx < 0)
		mid_idx = 0;
	if (mid_idx >= size)
		mid_idx = size - 1;
	return (mid_idx);

Colors macros I got are from wikipedia about web colors. Macro naming is same with X11 color naming.

Gradient demo

You can customize your own theme (custom default is black to white) in fdf_theme.c.

void fdf_theme_custom(t_ramp **ramp)
{
  color_ramp(ramp, FDF_A, steps, FDF_B); //starting color ramp FDF_A is for lowest z
  ...
  color_ramp(ramp, FDF_Y, steps, FDF_Z); //ending color ramp FDF_Z is for highest z
}

Preview

Gulf of California Ocean

Parallel view:

Without anti-aliasing

With anti-aliasing

Isometric view:

GIF

How to make your own fdf gifs

1. Convert a gif to bmp (make sure to give it an easy name before converting)
   I use this site
   Normally I prefer width around 250 to 300, depending on your program. Just compile with -02 or -03 to make them run faster.
2. Put all the bmp files into a folder and place the bmp folder into the fdf folder
3. Create a new folder to store fdf files
4. Run the the python script like so (located in maps/script)

for f in [BMP FOLDER PATH]/*.bmp; do
python3 pixel.py $f [OUTPUT FOLDER PATH]; done

5. Rename the files
   When converting gif to bmp, you'd often see something like [prefix]-{0...x}.bmp. To read them in lexicographically order run

# replace PREFIX with name of your file without numbers at the end
printf '%s\n' *(n) | cat -n | while read n f; do mv $f `printf "[PREFIX]%04d.fdf" $n`; done
# Your files now have 0 paddings.

6. Start fdf and run any fdf files
7. Enter shell mode and use animate

You can get results like these:

// Something like this
void	delay(int milliseconds)
{
	unsigned long	pause;
	clock_t			now;
	clock_t			then;

	pause = milliseconds * (CLOCKS_PER_SEC / 1000);
	then = clock();
	now = then;
	while ((now - then) < pause)
		now = clock();
}

in fdf_minishell use
change delay [integer] (milliseconds)

Update Log