Условие близости точки к конкретной половине эллипса

[Kshvorowiszm]

Вот смотрите, есть такая задача. Есть две точки, координаты их известны. Собственно это соседние точки на растре, которые применяются как гипотетические соседи при алгоритме средней точки и Брэзэнхэма для растризации окружности. Но я применяю их для эллипса. Я выявляю их расстояние до фокусов, и по тому какой пиксел ближе к настоящему аналоговому эллипсу, рисую егó. Причём эллипс наклонный. Ну то что он наклонный тут особо не усложняет, но вот если эллипс очень сжат (сжатие 1%..3%), точнее если обе полудуги могут пролегать по одному пикселу – то это условие с расстоянием до фокусов может удовлетворить и обратная дуга эллипса, которую я не рисую. И скоситься на неё будет ошибка. Так вот я хочу узнать как отсечь обратную полудугу эллипса. И если один из пикселов удовлетворяет той, обратной дуге, а не главной, не брать его.

Просто не брать пиксел, если он сам находится в обратной половине (ниже прямой, соединяющей фокуса), нельзя. Пиксел имеет право быть чуть ниже этой прямой. Это я уже выяснил тэстами. Надо как-то или преобразовать главное условие с суммой расстояния до фокусов:

$$\sqrt{(x_{to1}-x_{f1})^2+(y_{to1}-y_{f1}^2)}+\sqrt{(x_{to1}-x_{f2})^2+(y_{to1}-y_{f2}^2)}-2a\mapsto \min$$

(“to” это сосед),
чтобы его удовлетворяла только одна полудуга; или для пиксела ещё проверить, к какой именно полукривой он ближе. Хоть эллипс наклонный, в принципе подошло бы и какое-то условие для канонического, потому что я могу провернуть проверяемый пиксел обратно в координаты канонического эллипса. Но вот какое это условие? Самым правильным казалось бы поиск просто расстояния от пиксела до кривой, но я нашёл, оно слишком громоздкое (вот). Там уравнение степени 4. Если такое написать, сразу придётся подписывать что-то другое для малых эллипсов, чтобы не было столько вчислений.

Этому недоразумению у меня подлежит только 1 из соседей, потому что второй всегда “дальше от центра эллипса” и на обратную сторону не перекрывается.

[Алексей К.]

Kshvorowiszm, у меня сложилось впечатление, что
(a) русский язык для Вас не родной;
(б) Вы очень неплохо (для иностранца) его знаете.

Я мало что понял из Вашего сообщения. А искать упомянутые Вами алгоритмы ("средней точки" и имени_какого-то_парня) поленился.

Когда я вижу плохо написанное сообщеие, но всё же понимаю, что хотел сказать автор, я обычно помогаю ему сформулировать мысль правильно. Здесь я (пока) беcсилен. И я не выпендриваюсь --- просто (пока) не могу.

Но, как мне показалось, Вам могут пригодиться следующие соображения, касающиеся сравнения расстояний от двух точек, $(x_1,y_1)$ и $(x_2,y_2)$, до эллипса (или любой другой коники, и, наверное, не только коники) $F(x,y)=0$.

Если, известно, что точки довольно близки к эллипсу (а Вы, похоже, выбираете одну из двух таких точек, заведомо близких, с погрешностями порядка ошибок округления), то расстояние можно оценить как $d_i\approx C\cdot |F(x_i,y_i)|$ (плевать, наклонный он, смещёный или ещё какой). Константа $C$ наверняка легко составляется из инвариантов данного эллипса, но для сравнения расстояний она не нужна. И не надо процитированных Вами страшных формул-уравнений.

Это если я хоть чуть-чуть правильно понял Ваши нужды.

-- 14 дек 2014, 23:13:42 --

Нет, константа $C$ не может быть одной и той же для всего эллипса: она связана с локальным (в окрестности тестирумых точек) радиусом кривизны эллипса.
Но это ничего не меняет. Если две точки близки друг к другу (а Вы сами назвали их соседними), и близки к эллипсу, то такое сравнение,

$$|F(x_1,y_1)|\lesseqgtr |F(x_2,y_2)|,$$

вполне оправдано.

[redicka]

(Оффтоп)

По-видимому, программист без математического образования.

[Kshvorowiszm]

Если нужно, могу всё уточнить или объяснить. Но вы всё почти поняли. Только надо не оценить просто расстояние от двух точек до этой кривой (эллипса), а оценить их расстояния до только полуэллипса. Чтобы растеризатор не скосился на другую половину, если вдруг неравенство удовлетворяет близость к ней.

Ну так вот ваше предложение – очень правильно, странно что я с этого соскользнул. Конечно – можно подставить просто в уравнение эллипса, а не в уравнение с фокусами. И тоже найти погрешность.
Но только нужно было из этой функции
$F=\frac{x^2}{a^2}+\frac{y^2}{b^2}-1$

ещё выделить половину, чтобы обе точки считались как бы до верхней дуги, независимо под другой дугой или под этой они оказались. Ну для этого уравнения-то это проще.
$y^2=(1-\frac{x^2}{a^2})b^2$
$F=y-\sqrt{a^2-x^2} \frac ba$
Это для $y\ge0$. И конечно перед этим свернуть точки на угол эллипса, обратно в координаты канонического.

Но это не всё. Растризация в принципе идёт правильно, но эллипс оказывается на краях толще чем я предполагал. Толще чем при оценке через фокусы. Дело-то как раз в том, что это “не в пределах округления” – я использую этот случай именно для тонких эллипсов, у ких ширина сопоставима с размером пиксела. И там это очень заметно. Может быть надо всё-таки оценить эту погрешность – домножить её на какой-либо коэффициент?

Просто говоря: реже выбирать дальнего соседа, и чаще ближнего на краях эллипса. Домножить погрешность для дальнего соседа на ≽ 1.
Я так понимаю коэффициент должен зависеть от места на эллипсе. Если на постоянную, не получается.

-- 16.12.2014, 18:07 --

Вот графически, если это поможет понять что я имею в виду. Диаметр узкого места 1. Широкого 200. Обратная полудуга рисуется симметрично, обсчитывается только в данном случае “верхняя” дуга.

Вот как я предполагаю, правильный. На концах толщина не превосходит просто прямую. В центре – потолще.


Более толстый. Оценка по уравнению, как вы предложили. особенно смущает лишний пиксел у конца.


А вот что было до этого – эллипс скашивается на верёвку. Растризатор начинает вихляться то на ту половину, то на эту. (При диаметре ровно 0 это не происходит, но тут 1).

[Kshvorowiszm]

Хотя нет, ошибаюсь. Домножение на постоянную даёт изменение – утонщает её немного. Вот что при постоянной 0.61 для соседа, ближнего к оси:

Но всё-таки, что вы имели в виду, как постоянная выводится из инвариант или зависит от локального радиуса?

[Алексей К.]

Kshvorowiszm в сообщении #947825 писал(а):

Но всё-таки, что вы имели в виду, как постоянная выводится из инвариант или зависит от локального радиуса?

Мне очевидно, что подробности вывода я в будние дни не приведу.
Вот что я постараюсь сделать (в выходные, если это будет ещё актуально).
На эллипсе $F(X,Y)=0$ возьму точку $(x_0,y_0)$, и вычислю уравнение нормали к эллипсу в этой точке:

$$x(s)=x_0+s\cos\nu,\quad y(s)=y_0+s\sin\nu.$$

При таком эппроче значение $s$ будет расстоянием от точки до эллипса (местами чистым, местами грязным). И функцию $F(x(s),y(s))$ разложу в ряд по $s$. И посмотрю на коэффициент при $s^1$ (остальные неинтересны), несомненно свяжу его с локальны радиусом кривизны (да, когда-то в детстве проделывал это, потому и встрял в обсуждение).

Но ведь чтобы этой ерундой заняться, мотивация какая-то нужна (не подумайте, что я из Вас денег выцарапываю )!
Ну как бы если речь о растеризации какой-то кривой, так это что-то давно решённое и всем (кто в этом ковыряется) давно известное. Вроде как округлили --- и всё!
Чо там за фокусы со второй половинкой эллипса --- так и не понял.

(Оффтоп)

Эх, хорошо бы до выходных кто-то умный понял, чего хочет (и не говорит) автор, и...
Мне кажется, что естественных задач со "второй половинкой" эллипса быть не может, и просто автор решил (по неопытности) так решать какую-то другую задачу, здесь не изложенную.

[Kshvorowiszm]

Обработки второй половины эллипса, вроде правда обычно нет, но это наверно выходит из-за того, что рисуют только канонический, или параметрически через угол.
Нет, тут надо именно сделать алгоритм рисования эллипсов, включая наклонные. Что-то я не смог найти такое, кроме как сделанные параметрически. Во всех программах где наклонные рисуются, везде проходят по углу и считают синусы и косинусы каждый раз. Мне такой алгоритм не нравился потому что я думал он грязный – не удастся избавиться от лишних пикселов, ведь он работает в угловом пространстве, а не точечном. Хотя щас думаю, может и можно, если сделать шаг дуги не меньше $\sqrt2$. Но придётся обязательно достраивать пикселы между дырами. Ещё казалось, что алгоритм средней точки должен быть быстрее по скорости. Хотя опять же, пока я считаю огрешность как $F=y-\sqrt{a^2-x^2} \frac ba$ и ещё поворот (4 умножения 2 сложения), 2 раза, это может и не быстрее. Но в любом случае я хочу уж доделать это, потому что почти докончил.
Вы удивитесь, но кое-где я видел что эллипсы крутят даже рисуя канонный эллипс стандартным средством, а потом крутят весь растр стандартным для этого средством.

[Sender]

Kshvorowiszm в сообщении #946300 писал(а):

или для пиксела ещё проверить, к какой именно полукривой он ближе

Почему бы просто не сравнить расстояния от пиксела до вершин эллипса, лежащих на его малой оси?

[iifat]

Подозреваю, на концах полуэллипса будет расплываться. То ли их по отдельному алгоритму строить.

[Алексей К.]

Kshvorowiszm в сообщении #948667 писал(а):

Нет, тут надо именно сделать алгоритм рисования эллипсов, включая наклонные. Что-то я не смог найти такое, кроме как сделанные параметрически.

Какая ерунда --- сделать алгоритм рисования эллипса. Просто получить параметрическое уравнение $[x(t),y(t)]$. И $\Delta t$ определить из $\frac{ds}{dt}\approx \text{1 pixel}$. И всё.

Kshvorowiszm в сообщении #948667 писал(а):

Во всех программах где наклонные рисуются, везде проходят по углу и считают синусы и косинусы каждый раз. Мне такой алгоритм не нравился потому что я думал он грязный – не удастся избавиться от лишних пикселов, ведь он работает в угловом пространстве, а не точечном.

Вам он не нравится, потому что Вы математики не знаете. И имеете своё (ничем не обоснованное) отношение к синусам и косинусам.

(Оффтоп)

Примерно, как журналисты и депутаты, ни хрена не понимающие в генетике, имеют, тем не менее, своё "отношение" к генно-модифицированным продуктам.

И что за боязнь "лишних пикселов"? Очевидно, что иногда они возникнут, но столь же очевидно, что иногда, и что это ерунда.

Kshvorowiszm в сообщении #948667 писал(а):

и считают синусы и косинусы каждый раз.

Рисуете эллипс --- будете считать синусы и косинусы, какая мелочь! А логарифмическую спираль рисовать? Синусы-косинусы никуда не денутся, логарифмы добавятся. А спираль Корню рисовать --- будем плакать про "интегралы Френеля каждый раз считать"?
(Замечу, что и тут синусы-косинусы никуда не денутся).

Если Вам известно, что это эллипс, то задача тривиальна. Формула приведена выше, можно попридуриваться с её "оптимизацией".

Когда я создавал тему «Wanted: формула для координат фокуса произвольной коники.», это было именно из желания нарисовать конику (странно, что эта тема не в чулане: формулу-то никто не привёл).
Не эллипс нарисовать хотел, а конику вообще, возможно, эллипс или гиперболу, близкие к параболе (ну и саму параболу, если вдруг...)
Был бы у меня фокус, ближайший к началу координат, я бы по параметрическому уравнению по той же формуле $\frac{ds}{dt}\approx \text{1 pixel}$ всё легко сделал бы.

(Оффтоп)

Я не довёл это до ума, поскольку (по личным причинам) сильно обиделся на математику и перестал ею заниматься. Как бы голодовку объявил. Сериалы пока смореть не научился, но скоро научусь. И понаблюдаю, как она, дура, будет дальше развиваться без моего участия.

[Kshvorowiszm]

В общем пока я думаю над этим. Параметрически с $\frac{dq}{dt}\to1$ точно не то. Это заведомо в эту задачу не входит. Может потом сравню, сделав и так тоже.

Цитата:

сравнить расстояния от пиксела до вершин эллипса, лежащих на его малой оси

Если это условие как главное, то это расстояние ведь не нормировано. Чему оно должно быть равно?
А если как проверочное, то это всё равно что проверить, лежит точка ниже прямой с фокусами. Так нельзя. Я уж так делал (через векторное произведение или просто по коэффициенту прямой длинной оси – ниже / выше), эллипс становится как прямая толщиной 2 пиксела, не меньше.

[Kshvorowiszm]

Ух ты кажется врубился, достаточно чистый метод. И премудрого такого особо нет. Одна из промежуточных форм.

Действительно, надо использовать каноническое уравнение, переведённое в явное. Но не до конца явное с корнем, а просто Y оставить на одной стороне.
(Полностью явное я и не мог использовать, потому что оно даёт уж очень другую погрешность. Наверно потому что от одной ординаты зависит линейно, а не квадратно. Эллипс конечно не разъезжался, но рисовался заметно хуже.)

Но вот если оставить уравнение так: $y^2=b^2-x^2\frac{b^2}{a^2}$
то можно использовать простой модуль, чтобы в самом уравнении отчеркнуть, в какой дуге точка: $y|y|=b^2-x^2\frac{b^2}{a^2}$

Будучи у дальней дуги точка не перетянется к ней и не отбросится, а правильно сосчитается как она близка именно к нужной дуге. Я уж пытался как-то так делать с модулями, но в канонической форме. Но находясь на одной стороне неравенства, модуль Y действовал в разгласование с X-ом. И путного не лучалось, всё разъезжалось.

Этот метод правда не так легко загнать в Брезенхемские оптимизации, поэтому тонкий эллипс будет строиться дольше, но всё равно намного менее долго чем с корнями или косинусом.

[Kshvorowiszm]

Надо написать ещё комментарий, потому что я отказался от той мысли. Хотя это решение уж уехало в программное, а не математическое.
Полуэллипс мог бы пригодиться, но он не очень уж хорош. Трудно узнать, где точно менять проверку с положительного на отрицательный. И всё-таки это не полуэллипс, а кривая спускающаяся за полуэллипсом под ось и расходящаяся там в стороны, поэтому на сáмом конце тоже потусторонний пиксел может вернуть (на некоторых углах). С этим я завяз.

Поэтому так: можно найти проекцию эллипса на прямую, проходящую по центрам рассматриваемых пикселов. То есть перпендикулярную сканированию октанта. Расстояние-то до эллипса найти может и сложно, но вот расстояние только в проекции на эту прямую уже намного проще. А точность всё равно не пострадает. К тому же я понял что, точно, лучше составлять уравнение эллипса сразу повёрнутого, а не канонного и потом крутить, или какие-то разные координатные пространства следить. Потому что составляется оно не сложно, вот так –

$a^2(x\cos\beta+y\sin\beta)+b^2(y\cos\beta-x\sin\beta)=a^2b^2$.

(Оффтоп)

$3$'гонометрика считается только в начале, коэффициенты тут тоже при $x$-е и $y$-е степени $1$. В относительную формулу (“дельтную”) это перевести не принципально сложнее чем с канонным, всё можно сократить. Поэтому скоростные оптимизации те же можно сделать.

Ну а в повёрнутом уравнении эта прямая будет горизонтальная или вертикальная, поэтому просто надо будет сравнить одну координату. Правда пересечения будет или $2$, или $1$, или $0$. Но из двух можно выбрать однозначно опираясь на номер октанта, а если эта прямая с эллипсом не пересекается ($0$ корней), значит как раз до верхухи доехали (центр пиксела чуть за). И там можно откатиться обратно внутри пиксела (это я ещё не сделал).

Формулы являются

$A=b^2\cos^2\beta+a^2\sin^2\beta$
$B=y\cdot2\cos\beta\sin\beta\cdot(b^2-a^2)$
$C=y^2\cdot(b^2\sin^2\beta+a^2\cos^2\beta)$
$D=B^2-4AC$
$K=\dfrac{-B\pm\sqrt{D}}{2A}$

Надо правильно выбрать знак (дугу), а тогда расстояние от этой кooрдинаты до пикселов даёт выбрать нужный пиксел. Это для октантов где сканирование едет по $y$. В других – место $y$ будет $x$ в $B$ $C$.

И ещё важно то, что первичным уравнением (до этого) проверять лучше не $2$ пиксела, а точку между ними. Гораздо меньше вероятности, что она заедет к другой дуге (собственно это и заключает алгоритм средней точки, а так это был алгоритм $2$'ух точек).

-

Ещё (после того как я стал вводить вопросы на форум) Google выдал какую-то диссертацию, в которой это прямо решалось, там использовали параллельно несколько погрешностей на разных сторонах пиксела. Но там и решали более широкую задачу – строили ещё парабол(ы) и гипербол(ы). Ссылка терьнулась, а название – General rendering and antialiasing algorithms for conic sections; M. Golipour-Koujali; School of computing, information systems and mathematics; London South bank university; may $2005$, страницы $78$.

[Lia]

Kshvorowiszm
Проследите, чтобы у всех функций присутствовали аргументы.

[Kshvorowiszm]

Хм. $\sin$, $\cos$? В этом случае, конечно, имеется в виду что угол у всех этих функций это угол наклона эллипса. Это я так напечатал чтобы было яснее, много символов не отвлекало. Сам я путался с такой длинной формулой именно в этой задаче. (.... Обязательно ли это исправить?)