LED - Секторный редактор и рендер

Программа - редактор уровня для 2.5 игр типа Doom 1
Уровень представляет собой набор секторов - замкнутых непересекающихся полигональных областей, возможно невыпуклых и возможно вложенных

https://gamedev.ru/files/?id=156994

Управление:

Клавиши:
left mouse down -
  попал в вершину - выделить вершину
  попал на линию  - выделить линию
  попал в пустоту - создать и выделить вершину
left mouse drag - рисовать линию из выделенной вершины в позицию мыши
left mouse mouse up - если выделенна вершина и сдвинули мышь > delta - добавить линию

alt+left mouse down - выделить сектор
right mouse down    - выделить вершину
right mouse drag    - если выделенна вершина - таскать вершину, иначе - таскать карту

Mouse wheel - скэйлить карту
Enter/Space - перекл 2D/3D
Left Mouse Drag - крутить камеру в 3D
WASD - ходить в 3D

В Edit-ах вводить высоту пола и потолка в выделенном секторе

Чтобы выводить 3D - надо создать хоть один сектор или загрузить карту, например 1.map в папке архива

*************************************************************************************

Ниже я опишу алгоритм, который из набора линий на плоскости, строит сектора
Используются след структуры данных:

Вершина содержит XYZ и индекс первой линии

Линия содержит индексы двух вершин и индексы следующей линии для каждой вершины, в порядке CW, и индексы двух прилежащих секторов

Сектор содержит индекс первой линии внешней границы (могут быть и внутренние, если есть вложенные сектора)

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

Для выделения новых образовавшихся секторов применяем обход линий. Двигаемся по линии из одной вершины A в другую вершину

B, потом по следующей исходящей из B итд, пока не вернемся в исходную вершину
Притом, если попали в вершину с единственной исходящей линией - двигаемся по этой же линии в обратную сторону.
Это позволяет обработать незамкнутые линии
Если линия при обходе пройденна1 раз - назовем ее 1-линией, если 2 раза - 2 линией, линия не может быть пройденна больше двух раз. Как видно, 2-линия - незамкнута, по крайней мере одна ее вершина содержит лишь одну исходящую линию
Притом вершина может быть посещенна любое число раз

Интересно заметить, что при обходе контура CCW все пройденные 2-линии оказываются внутри контура (как отростки от внешней границы сектора)

При добавлении линии - делаем обход по ней, пока не вернемся в исходную вершину
Если новая линия пройденна 1 раз (1-линия) - добавляется сектор
Берем из всех вершин 1-линий самую левую (с min X), проверяем, что угол между входящей и исходящей линиями при обходе <180, иначе - меняем направление обхода на противоположное и повторяем

Также для секторов, вложенных в новообразовынный сектор, исправляем для их линий прилежащий с внешней стороны сектор

При выделении происходит вот такой баг

При нажатии на пробел также Access Violation и один раз было вроде Floating Division by Zero.
  Можете реализовать рандомное заполнение линиями квадрата, указав при этом количество точек/линий? Интересно было бы сравнить производительность аналогичных операций с моим движком (например, операция выделения точек).
  И еще вопрос: у Вас линии я так понимаю не компрессятся, а сразу рисуются?

ArtProg
> При выделении происходит вот такой баг
При выделении чего? Вершины, линии, сектора?
У себя не замечал, не знаю

> При нажатии на пробел также Access Violation и один раз было вроде Floating Division by Zero
Надо загрузить карту (1.map) или нарисовать хоть один замкнутый сектор и чтобы плаер был внутри

> Интересно было бы сравнить производительность аналогичных операций с моим движком
Сейчас тормозит в 1024x768 на Celeron, вероятно на перерисовке BitBlt

У меня не 2D движок, а секторный рендер, подобный Doom 1, ближе к Duke3D
LED - Level Editor - редактор карты с возможностью побродить в 3D
Через каждый столбец экрана проводится горизонтальный луч и закрашиваются вертикальные отрезки его пересечения с секторами, на линиях, разделяюющих два сектора различноы высоты, рисуются вертикальные отрезки стен

> у Вас линии я так понимаю не компрессятся, а сразу рисуются
Сразу. Зачем их  компрессить и как?

Aslan

  При выделении вершины, а линии почему то не перетаскиваются, хотя и выделяются по левому клику мыши.

  BitBlt умудряется тормозить даже когда вся остальная часть кода летает, так что может быть лучше  выводить через OpenGL/DirectX. Тем более при аппаратном выводе уже устраняются проблемы с VSync.

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

ArtProg
> При выделении вершины
Да вроде без проблем выделялось у меня, хз
Вот как бы из VCL exception узнать с какой строчки оно вылетело?

> а линии почему то не перетаскиваются
А линии и ненадо перетаскивать, только концы
Притом в явном виде нет создания/удаления вершин, редактор ориентирован на работу с линиями

> BitBlt умудряется тормозить даже когда вся остальная часть кода летает, так что может быть лучше выводить через OpenGL/DirectX
glDrawPixels также берет картинку из RAM. Надо сравнить с BitBlt
Незнаю, можно ли замапить GL FrameBuffer в RAM

> Рисовать все линии одного цвета в одном слое, и потом сжимать и расжимать когда нужно
У вас чтото сложное, ориентированное на векторную графику
Напишите описаловку возможностей к нему
Я же хочу сделать просто удобный редактор карт. Карта состоит из секторов (замкнутых непересекающихся областей), у каждого сектора заданна высота пола и потолка, это называется 2.5D

> не получится сделать супер-быстрого выделения, при котором идет перерисовка не всех линий(одного слоя), а только тех которые примыкают к выделенным вершинам
В чем проблема? В вершине список исходящих линий. Кстати, все время выбирая ближайшую линию в направлении обхода - обходится сектор. Про сектора я могу рассказать многое, я долго с ними возился

Aslan

  Ну, Вам виднее тогда ;)

  Я имел ввиду еще и случаи с пересекающимися линиями. Хотя если все линии не пересекаются, как у Вас, то да каких-то существенных проблем быть не может наверное.

  Если есть где почитать, то было бы неплохо.

ArtProg
> Я имел ввиду еще и случаи с пересекающимися линиями
В Computational Geometry приводят алгоритм поиска всех пересечений N отрезков за N*Log(N)+число пересечений (перебираем вершины по возрастанию X, ловим события добавления/удаления/пересечения отрезков)
Еще вам может понадобится аналог CSG для 2D - объединение/пересечение/вычитание замкнутых фигур
В свое время писал софт, строящий сечения 3D модели для 3D принтера, там проход по скан линии с учетом направления внешней нормали в пересечении с гранью

> Если есть где почитать, то было бы неплохо
Потом напишу здесь описание алгоритма
Вся сложность построить из набора линий сектора
Ну и raytracing 2D уровня

Aslan

  Кстати, неуверен насчет 3D. Там все таки придется видимо перерисовывать весь "слой" линий. В 2D же все в одной плоскости движется и можно просто в спрайт перегнать и потом отрисовывать(это если без масштабирования).

  +