Monday, 30 March 2020

Calculating area enclosed by intersections

A small math question today.

Given a unit sphere and an arbitrary ellipsoid, calculate the surface area of sphere inside the ellipsoid.

Without loss of generality, we may assume the unit sphere to be centered at origin, then the question depends solely on the 6 parameters defining the ellipsoid, $c_i, \alpha_i$ for $i=1,2,3$ in $\sum (x_i-c_i)^2/\alpha _i ^2 = 1$. Without thinking too much about existence of analytic solution in terms of the parameters, we want to look for ways to calculate or at least approximate the problem.

My own solution is based on the famous Gauss-Bonnet theorem:
$\int _M KdA + \int _{\partial M} \kappa _g ds = 2\pi \chi (M)$

The curvature of a unit sphere is constantly 1, and the Euler characteristic of a disc is 1. As long as you can calculate the geodesic curvature you get
$|M| = 2\pi - \int _{\partial M} \kappa _g ds$.
The intersection is a union of finitely many closed curves we can just calculate one by one.

A simple example would be as follows:

Consider the intersection between $x^2+y^2+z^2=1$ and $(x-1)^2+y^2+z^2=1$. The intersection $\Gamma$ is given by $x = \frac{1}{2}$ and $y^2+z^2 = \frac{3}{4}$. This is a circle of radius $\frac{\sqrt{3}}{2}$ with geodesic curvature $\frac{1}{\sqrt{3}}$. Therefore we have $\int _{\Gamma} \kappa _g ds = \pi$, so $|A| = 2\pi \pm \pi$ depending on the orientation. The surface area can be verified using the formula from Archimedes $|A| = \pi (h^2+a^2)$.


Of course, obtaining the parametrization is sometimes too difficult. Are there any easier ways to approximate the answer? Here are two suggestions from my friends.

- Monte Carlo based: sample points on the surface of the sphere and check whether it is in the ellipsoid.

- Integral approximation: similar to Monte Carlo but instead we split the sphere into pieces using spherical coordinates, then the required area is the integral over the indicator function of the ellipsoid.

And of course we can get an estimation using the Gauss-Bonnet approach. Let us call the sphere $S$ and the ellipsoid $E$. We start from a point of intersection, say $x$. The curve goes in the direction $v\in T_xS \cap T_xE$, the intersection of the tangent spaces of the two objects at $x$. We know the intersection must be of dimension 1 because if the two objects are cotangent at the point then the intersection is a point which generates no area after all.

Obtaining this direction is simply algebra, where we find the intersection between two subspace. With this direction we can numerically obtain a closed curve. There is a gap here because we may not go back to the starting point using numerical approximation. We just assume by smoothness (well sphere and ellipsoid are very nice objects) by doing fine enough approximation things would work (actually I believe we can prove this but I am not an expert in numerical methods) -- then we have an approximated curve of intersection.

From here we can calculate its length as well as its geodesic curvature, and the estimated area follows.

Gauss-Bonnet seems quite universal even if we generalize sphere and ellipsoid to other bounded closed $C^{\infty}$ objects because they are manifolds anyway. The only worry being whether we can get a closed curve without any global features that promises convergence.


Well this is just a funny little problem that I enjoyed during the lockdown. I feel like I should write some maths before I go back to my creation whether it is literature, music or research.

Meanwhile I hope everyone is alright during the pandemic -- whether you call it COVID-19, or Wuhan virus. Stay indoor, and stay healthy.

Monday, 9 March 2020

⑨/3/2020 Cirno's ⑨th Anniversary







YuFu - Holy Moon是自己進入太鼓界的鑰匙,做出自己最高水準似乎理所當然。


然後是IOSYS的算術教室。在東方大舉進攻音遊的世代,這首歌只是眾多東方音遊曲之一,甚至不在最熱門之列。論熱度IOSYS本身的魔理沙大盜、昆布與Usatei都在算術教室之上;其他團如Silver Forest、EastNewSound、Sound Holic等同時也有不少經典大作。除去James鬼畜圖和數學這兩個因素之外實在很難找到我對這張圖特別滿意的原因。是梗嗎?當年我還沒涉足東方,也聽不懂日文呢。


Cirno's Perfect Math Class [Wmf's Taiko]



上面那張是在11年2月5日ranked,⑨年後的2020正是做算術教室⑨週年的好時機。但⑨年後的我,做譜風格早已被「污染」:難度通漲所引致主流風格的偏移、1/6以上的混用、K社音遊的亂來風格等,潛移默化地成為了自己一部分。當我想用自己現有風格造出相近的效果時卻發現自己怎也再寫不出那種感覺。明明連打的紅藍轉換不再限於1/2拍上,自己卻發現dkkdk kkkdd這類連打放哪都不對;明明大家對串圖的接受程度比以前更高,我的成品卻比以前少了快150個音符。


不論如何,這張⑨週年版的譜面即使沒達到我心中的水準[8.5/10],要拿個不錯的分數還是可以的。我會給目前的成品7到7.5分吧。圖包等Guest diff到齊以後就會一併上傳。

Cirno's Perfect Maths Class: The 9th Anniversary Edition [Wmf's 2011 Taiko]

說句題外話,C97的高質量原創音樂其實不少。但因為它們不屬於東方或其他主流同人,外人接觸它們的機會比較少。在這裡我力推古典歌劇風的love solfege,主唱綾野えいり的歌劇腔與意大利人都對她讚譽有加:

Sunday, 16 February 2020

On three houses (3): Cindered Shadows

DLC 4 is the last scheduled expansion of Three Houses and is also the largest expansion. A completely new side story alongside with new characters, quests and activities that provides further clues about the main story.

Having new characters and activities means you need to play side story plus a complete rundown in the main story to experience everything -- which is too much for a player who have already completed the game 5 times. Below are my thoughts after completing the side story with a taste of main story with the presence of the new contents.

Part I: on game mechanics

Part II: maddening and more

*spoilers alert*

Side story

Did it in hard classic and it does not disappoint me. Enemies have config slightly above the "main story" hard, but with limited resources (though not "lacking resources") and being inaccessible to auxiliary battles it could be pretty hard. The way the game works here is pretty close to that in classic Fire Emblem (like Blazing Blade), so as the difficulty.

The side story consists of 6 unique battles. Enemies are compactly packed that does not allow the slightest bit of excessive training.

I personally like the third battle the most -- the two possible routes gives flexibility on how you can play the stage. Actually I figured that it is the safest to use both of them.

The final boss is also interesting given its gimmicky special attack. I found however, the fight would still be possible without the post-AOE weakening. That would be a lot more interesting as well as pushing the difficulty up to the maddening bar.

Story-wise, there is not a lot that you can do in a 7 chapter span where the second half are all about consecutive battles. Someone data-mined that there will be 13 chapters and a more detailed stories can be delivered in such length.

With the introduction of Abyss, I expect them to focus on interaction among underground students and residents because those residents are reasons the student were there. But with 7 chapters only IS did enough to introduce the students. The interactions are left for support conversations, which are also nicely written.

New classes

Yes that is a great solution to what I pointed out before. The new classes aimed to provide full flexibility between magic accessibility and melee potential of the characters.

Dark fliers is the long awaited class, fliers that can use magic. Even with sacrificed growth the class completely worth it given how overpowered fliers can be in the game.

Valkyries seem to clash with holy/dark knight at the master class, but it bridges well between the mage class and the magic knight classes since the lance requirement is gone. It's range+1 also allows long range magic snipers other than Lorenz.

Tricksters and war monks are adjustments to melee-magical units without the problem of mortal servants where growth were split 50/50 that doesn't really work on characters that fit. These two classes are primarily for melee based (trickster for dex based and war monk for vit/def based) characters who also wants to use heal at times.

Trickster is also a bridge between sword users and mortal servants, if one trains reason and faith simultaneously. However this is really a class taylor made for Yuri with his growth distribution especially with his unique combat art, the foul play. In side story I would made him MVP as he and Edelgard combined are capable to take all physical attacks. And while Edelgard slashes back for 35 damage, Yuri simply goes for 15+45 critical...

In side story, the two magical units are very fragile due to its limited movement (compared to master classes), the abundance of stairs (for valkyries) and team composition that couldn't protect them well. The war monk is kind of balanced -- he can sweep but you do not want to put him up front too often. Yuri of course survives anywhere on the map.

If we are to use these classes in the main story with proper team setup, it is expected that dark fliers will be used as a final form. Valkyrie might be a bridge to magic knight but it may also be used as a final form if one wants to do long range snips. Trickster is probably reserved for Yuri or at most Felix. War still awkward for me.

New region and activities

That I do not have full experience of. But new area's new area. They fill the area with new NPCs and new dialogues that consolidates the story further and this is never a bad thing.

Scraps may be useful for maddening or players who really lack resources. Altar is useful for New Game+ players who wants to get specific item where they didn't get because they skipped some game elements, and that's also good.

The idea of mysterious teacher is nice although I still haven't got a full picture on how it works, but it looks interesting. And for the rest, I am probably won't have the time to explore since it will take me another 15-20 hours to go through the game again...

Cindered Shadows

4 new well-crafted characters and they fit well in Abyss.

Hapi the anti-social who disbeliefs the church. Constance a fallen noble with Schizophrenia. Balthus the bold, the gambler and the alcoholic. Though nothing too surprising you have got to say these settings do work.

And of course Yuri. As a house leader (kind of) he completes the weapon cycle among the leaders, and he also completes the personality quadrants among them. He is charismatic but disbeliefs in the church unlike Claude. His charm and wise fits with his trickster class, but what surrounds him does not give him free will after all. He is the classic Japanese RPG protagonist, and a fitting last piece to this Fire Emblem sequel.

I wish that the support between Yuri and Byleth(s) could have been more romantic -- Yuri can flirt Ingrid without backfiring (just look at Sylvain), but he seems to be so clueless against us...


So, what should I grade Fire Emblem Three Houses for now?

School system that attracts everyone except hardcore classic players. New class system that is pretty much complete upon DLC. Multiple difficulties that can be completed with or without extra battles. Up to 40 characters with thousands of support conversations.

...all in one game. This is Fire Emblem Three Houses.

I would give 7.8/10 after writing (1). But with DLC the game probably worths a score of 8.5/10. A masterpiece that is for everybody, whether you are hardcore SRPG player or not.